Felix Fischer: "Mix and Match"

Date: 

Wednesday, February 3, 2010, 10:00am to 11:30am

Location: 

Pierce Hall 100F

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.