Get 20M+ Full-Text Papers For Less Than $1.50/day. Subscribe now for You or Your Team.

Learn More →

Mix and match

Mix and match Mix and Match Itai Ashlagi Harvard Business School Boston, MA 02163, USA Felix Fischer Harvard SEAS Cambridge, MA 02138, USA iashlagi@hbs.edu Ian A. Kash scherf@seas.harvard.edu Ariel D. Procaccia Harvard SEAS Cambridge, MA 02138, USA Harvard SEAS Cambridge, MA 02138, USA kash@seas.harvard.edu 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. In this paper we seek to design mechanisms that are strategyproof, in the sense that agents cannot bene t from hiding vertices, and approximately maximize e ƒciency, i.e., produce a matching that is http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Mix and match

Association for Computing Machinery — Jun 7, 2010

Loading next page...
 
/lp/association-for-computing-machinery/mix-and-match-JHU9f1trbu

References (27)

Datasource
Association for Computing Machinery
Copyright
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
ISBN
978-1-60558-822-3
doi
10.1145/1807342.1807392
Publisher site
See Article on Publisher Site

Abstract

Mix and Match Itai Ashlagi Harvard Business School Boston, MA 02163, USA Felix Fischer Harvard SEAS Cambridge, MA 02138, USA iashlagi@hbs.edu Ian A. Kash scherf@seas.harvard.edu Ariel D. Procaccia Harvard SEAS Cambridge, MA 02138, USA Harvard SEAS Cambridge, MA 02138, USA kash@seas.harvard.edu 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. In this paper we seek to design mechanisms that are strategyproof, in the sense that agents cannot bene t from hiding vertices, and approximately maximize e ƒciency, i.e., produce a matching that is

There are no references for this article.