BEGIN:VCALENDAR
VERSION:2.0
X-WR-CALNAME;VALUE=TEXT:Felix Fischer: "Mix and Match"
PRODID:-//Harvard events data//EN
BEGIN:VEVENT
UID:event_71911_0
SUMMARY:Felix Fischer: "Mix and Match"
DESCRIPTION:<p><strong>CRCS  Seminar</strong></p><p>Date:  Wednesday,  February 3, 2010<br>Time:  10:00am – 11:30am<br>Place:  Pierce Hall 100F</p><p>Speakers:  Felix Fischer</p><p>Title:   Mix and Match</p><p><drupal-media data-entity-type="media" data-entity-uuid="ff9e23a1-dca8-4508-b856-7ef3c2c0be34"></drupal-media></p><p>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.</p><p>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.</p><p>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.</p><p>This talk is based on joint work with Itai Ashlagi, Ian Kash, and Ariel Procaccia.</p>
LOCATION:Pierce Hall 100F
STATUS:CONFIRMED
DTSTART:20100203T150000Z
DTEND:20100203T163000Z
END:VEVENT
END:VCALENDAR