Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries

Avrim Blum (), John P. Dickerson (), Nika Haghtalab (), Ariel D. Procaccia (), Tuomas Sandholm () and Ankit Sharma ()
Additional contact information
Avrim Blum: Toyota Technological Institute, Chicago, Illinois 60637
John P. Dickerson: University of Maryland, College Park, Maryland 20742
Nika Haghtalab: Microsoft Research, Cambridge, Massachusetts 02142
Ariel D. Procaccia: Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Tuomas Sandholm: Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Ankit Sharma: Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Operations Research, 2020, vol. 68, issue 1, 16-34

Abstract: We study the stochastic matching problem with the goal of finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic k -cycle packing, in which the problem is to find a maximum packing of cycles, each of which exists with some probability. We provide polynomial-time adaptive and nonadaptive algorithms that provably yield a near-optimal solution, using a number of edge queries that is linear in the number of vertices. We are especially interested in kidney exchange, with which pairs of patients with end-stage renal failure and their willing but incompatible donors participate in a mechanism that performs compatibility tests between patients and donors and swaps the donors of some patients so that a large number of patients receive compatible kidneys. Because of the significant cost of performing compatibility tests, currently, kidney exchange programs perform at most one compatibility test per patient. Our theoretical results applied to kidney exchange show that, by increasing the number of compatibility tests performed per patient from one to a larger constant, we effectively get the full benefit of exhaustive testing at a fraction of the cost. We show, on both generated and real data from the UNOS nationwide kidney exchange, that even a small number of nonadaptive edge queries per vertex results in large gains in expected successful matches.

Keywords: stochastic matching; kidney exchange; matching with queries (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1856 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:1:p:16-34

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().