Date:
Location:
CRCS Seminar
Date: Wednesday, February 3, 2010
Time: 10:00am – 11:30am
Place: Pierce Hall 100F
Speakers: Felix Fischer
Title: Mix and Match
Abstract: We consider a matching problem on a graph in which disjoint sets of vertices are controlled by self-interested agents. Agents reveal subsets of their vertices, and a matching is determined for (the subgraph induced by) these vertices. Each agent then receives a payoff equivalent to the number of its own vertices that have been matched plus the maximum number of its hidden vertices that can be matched with each other.
A prominent application of this model is to kidney exchanges, where agents correspond to hospitals and vertices to donor-patient pairs. Hospitals may game an exchange by holding back some of these pairs, thus harming social welfare.
We will present a randomized mechanism that is strategyproof—in the sense that agents cannot benefit from hiding vertices—and provides a 2-approximation with respect to social welfare—i.e., always produces a matching of size at least half that of a maximum cardinality matching. Lower bounds establish that the mechanism is near optimal.
This talk is based on joint work with Itai Ashlagi, Ian Kash, and Ariel Procaccia.