Mix and match
Published 7 June 2010
Itai Ashlagi, Felix Fischer, Ian A. Kash, Ariel D. Procaccia
Citations107
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The main result is the design and analysis of the eponymous Mix-and-Match mechanism, which shows that this randomized mechanism is strategyproof and provides a 2-approximation, and lower bounds establish that the mechanism is near optimal.
Abstract
Consider a matching problem on a graph where disjoint sets of vertices are privately owned by self-interested agents. An edge between a pair of vertices indicates compatibility and allows the vertices to match. We seek a mechanism to maximize the number of matches despite self-interest, with agents that each want to maximize the number of their own vertices that match. Each agent can choose to hide some of its vertices, and then privately match the hidden vertices with any of its own vertices that go unmatched by the mechanism. A prominent application of this model is to kidney exchange, where agents correspond to hospitals and vertices to donor-patient pairs. Here hospitals may game an exchange by holding back pairs and harm social welfare.
Keywords
Decision SciencesEconomics, Econometrics and Finance
Journal of the ACMTruth revelation in approximately efficient combinatorial auctions
660 Citations2002Daniel Lehmann, Liadan O'Callaghan +1 more
It is shown that the GVA payment scheme does not provide for a truth revealing mechanism, and another scheme is introduced that does guarantee truthfulness for a restricted class of players.
The Quarterly Journal of EconomicsKidney Exchange
625 Citations2004Alvin E. Roth, Tayfun Sönmez +1 more
There is a wide class of constrained-efficient mechanisms that are strategy-proof when patient-donor pairs and surgeons have 0-1 preferences, which includes deterministic mechanisms that would accommodate the kinds of priority setting that organ banks currently use for the allocation of cadaver organs, as well as stochastic mechanisms that allow considerations of distributive justice to be addressed.
Symposium on Discrete AlgorithmsData structures for weighted matching and nearest common ancestors with linking
405 Citations1990Harold N. Gabow
It is shown that the weighted matching problem on general graphs can be solved in time O(n(m + n log n)), f or n and m the number of vertices and edges, respectively.
Digital Access to Scholarship at Harvard (DASH) (Harvard University)Efficient Kidney Exchange: Coincidence of Wants in a Markets with Compatibility-Based Preferences
391 Citations2009Alvin E. Roth, Tayfun Sönmez +1 more
Developing infrastructure to perform three-way as well as two-way exchanges will have a substantial effect on the number of transplants that can be arranged.
Approximate mechanism design without money
319 Citations2009Ariel D. Procaccia, Moshe Tennenholtz
This paper establishes tight upper and lower bounds for the approximation ratio given by strategyproof mechanisms without payments, with respect to both deterministic and randomized mechanisms, under two objective functions: the social cost, and the maximum cost.
American Economic ReviewA Kidney Exchange Clearinghouse in New England
292 Citations2005Alvin E. Roth, Tayfun Sönmez +1 more
There have started to be kidney exchanges involving two donor–patient pairs such that each (living) donor cannot give a kidney to the intended recipient because of blood type or immunological incompatibility, but each patient can receive a kidney from the other donor.
Clearing algorithms for barter exchange markets
283 Citations2007David Abraham, Avrim Blum +1 more
This work replaces CPLEX as the clearing algorithm of the Alliance for Paired Donation, one of the leading kidney exchanges, and presents the first algorithm capable of clearing these markets on a nationwide scale.
Truthful and Near-Optimal Mechanism Design via Linear Programming
225 Citations2005Ron Lavi, Chaitanya Swamy
Truth revelation in rapid, approximately efficient combinatorial auctions
222 Citations2001Daniel Lehmann, Liaden Ita O'Callaghan +1 more
It is shown that the GVA payment scheme does not provide for a truth revealing mechanism, and another scheme is introduced that does guarantee truthfulness for a restricted class of players.
Journal of Computer and System SciencesIncentive compatible regression learning
143 Citations2010Ofer Dekel, Felix Fischer +1 more
It is established that, in the general setting, the VCG mechanism goes a long way in guaranteeing truthfulness and economic efficiency.
Lecture notes in computer scienceTighter Bounds for Facility Games
109 Citations2009Pinyan Lu, Yajun Wang +1 more
This paper studies the approximation ratio of social welfare for strategy-proof mechanisms, where no agent can benefit by misreporting its location, and uses the total cost of agents as social welfare function.
Sum of us
85 Citations2011Noga Alon, Felix Fischer +2 more
A randomized strategyproof mechanism is presented that provides an approximation ratio that is bounded from above by four for any value of k, and approaches one as k grows.
Truthful assignment without money
85 Citations2010Shaddin Dughmi, Arpita Ghosh
A general LP-based technique is developed to reduce designing a truthful approximate mechanism without money to designing such a mechanism for the fractional version of the problem, and it is shown that no strategyproof mechanism, deterministic or randomized, can be optimal.
Discrete Mathematics Algorithms and ApplicationsMAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS
77 Citations2009Péter Bíró, David F. Manlove +1 more
Here it is proved the APX-completeness of the problem of finding a maximum size exchange involving only 2-cycles and 3-cycles, and an approximation algorithm and an exact algorithm are presented for the Problem ofFinding a maximum weight exchange involving cycles of bounded length.
Strategy-proof allocation of multiple items between two agents without payments or priors
60 Citations2010Mingyu Guo, Vincent Conitzer
The results imply that in some cases, it is possible to design good allocation mechanisms without payments and without priors, and this work introduces the family of linear increasing-price mechanisms, which are strategy-proof, prior-free, and payment-free.
Truthful Approximation Schemes for Single-Parameter Agents
58 Citations2008Peerapong Dhangwatnotai, Shahar Dobzinski +2 more
AlgorithmicaA Lower Bound for Scheduling Mechanisms
53 Citations2008George Christodoulou, Ηλίας Κουτσουπιάς +1 more
The lower bound to the lower bound for the approximation ratio of mechanisms is improved to $1+\sqrt{2}$ for 3 or more machines.
Oxford University Press eBooksMarket Design for Kidney Exchange
46 Citations2013Tayfun Sönmez, M. Utku Ünver
This survey is prepared for the Oxford Handbook of Market Design edited by Z. Neeman, M. Niederle, and N. Vulkan.
National Bureau of Economic ResearchIndividual Rationality and Participation in Large Scale, Multi-Hospital Kidney Exchange
45 Citations2011Itai Ashlagi, Alvin E. Roth
Strategyproof classification with shared inputs
15 Citations2009Reshef Meir, Ariel D. Procaccia +1 more
It is demonstrated that variations of a truthful random dictator mechanism can guarantee approximately optimal outcomes with respect to any class of classifiers.
National Conference on Artificial IntelligenceStrategyproof classification under constant hypotheses: a tale of two functions
13 Citations2008Reshef Meir, Ariel D. Procaccia +1 more
Original early experimental work and clinical reports from the literature are discussed with a view toward future directions for research in improving patency in microvascular surgery.