#  Felix Fischer: "Mix and Match" 

 



####  calendar\_today Date and Time 

 **February 3, 2010** 

 10:00AM - 11:30AM EST 

####  pin\_drop 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.



 

 



 

 See also:- [ CRCS Lunch Seminar ](/events/crcs-lunch-seminar)
 
 

 Share on:- [     Facebook ](#)
- [     Twitter ](#)
- [     Linkedin ](#)
 


 Save: [ Add to calendar calendar\_today ](https://crcs.seas.harvard.edu/node/71911/event-feed.ics)  Copy link link