One-day Workshop and Inaugural Lecture, 2nd March 2010
We will be holding a one-day mini-workshop to coincide with Paul Goldberg's inaugural lecture on the 2nd of March.
Remember to register here for the inaugural lecture. (Electronic invitation including abstract of the talk)
Provisional timetable (still under construction!)
| 10:30 | coffee | |
| talks in room G.12 | ||
| 11:00 | Piotr Krysta | Algorithmic Mechanism Design |
| 11:30 | Martin Gairing | network congestion games |
| 12:00 | Rahul Savani | Wiretapping a hidden network |
| 12:30 | lunch break | |
| talks in room G.12 | ||
| 2:00 | Troels Bjerre Sørensen (Warwick) | playing poker for an infinite number of chips |
| 2:30 | David Manlove (Glasgow) | Keeping Partners Together: Algorithmic Results for the Hospitals/Residents Problem with Couples (abstract below) |
| 3:00 | coffee | |
| 3:30 | Kousha Etessami (Edinburgh) | On the complexity of approximating Nash and other equilibria and fixed points of algebraic functions |
| 4:00 | Bernhard von Stengel (LSE) | Abstractions of Equilibrium-Finding Algorithms |
| 4:30 | break | |
| Inaugural lecture in Leggate Theatre, Victoria Building | ||
| 5:30-6:30 | Paul Goldberg | Computational Game Theory |
Abstract of David Manlove's talk:
The classical Hospitals / Residents problem (HR) has many practical applications: in particular it models the assignment of junior doctors to hospitals, which is carried out by large-scale centralised matching schemes in many countries. The Hospitals / Residents problem with Couples (HRC) is a generalisation of HR that models the important case where couples submit joint preference lists over pairs of hospitals (hi, hj) that are typically geographically close.
We consider a natural restriction of HRC in which the members of a couple wish to be placed at the same hospital, i.e., hi=hj for every such pair. We show that, in this context, the problem of deciding whether a stable matching exists is NP-complete, even if each resident's preference list is of length at most 3 and each hospital has capacity at most 2. However we show that if each hospital's preference list is of length at most 2, then a stable matching always exists and can be found in linear time (for arbitrary hospital capacities).
We also consider a more general restriction of HRC in which the members of a couple have individual preference lists over hospitals, and the joint preference list of the couple is consistent with these individual lists in a precise sense. In this context, with respect to classical (Gale-Shapley) stability, we give a linear-time algorithm to find a stable matching or report that none exists, regardless of the preference list lengths or the hospital capacities.