CRCS Seminar: Mix and Match

CRCS Seminar
Date: Wednesday, February 3, 2010
Time: 10:00am – 11:30am
Place: Pierce Hall 100F

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

About Felix

Felix Fischer is a postdoctoral researcher at Harvard SEAS and a CRCS affiliate. He received his doctorate in Computer Science from LMU Munich in 2009 for work on the computational complexity of solution concepts in restricted classes of strategic games. His research is more generally concerned with computational aspects of game theory and social choice, and with strategic aspects of computation. His work at Harvard SEAS is supported by a DFG Research Fellowship.