Computer Science – Computer Science and Game Theory
Scientific paper
2010-06-09
Computer Science
Computer Science and Game Theory
10 pages, 5 figures. Appeared in Proceedings of 11th ACM Conference on Electronic Commerce, Pages 305-314
Scientific paper
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 efficiency, i.e., produce a matching that is close in cardinality to the maximum cardinality matching. Our main result is the design and analysis of the eponymous Mix-and-Match mechanism; we show that this randomized mechanism is strategyproof and provides a 2-approximation. Lower bounds establish that the mechanism is near optimal.
Ashlagi Itai
Fischer Felix
Kash Ian A.
Procaccia Ariel D.
No associations
LandOfFree
Mix and Match does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Mix and Match, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mix and Match will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-40378