Department of Mathematics

Wednesday, February 6, 2013, London School of Economics

ESRC Game Theory Workshop
"Matching Under Preferences"

The 2012 Nobel Memorial Prize in Economic Sciences was awarded to Alvin E. Roth and Lloyd S. Shapley "for the theory of stable allocations and the practice of market design". The LSE Department of Mathematics has a strong research group on Game Theory and Discrete Mathematics. At the occasion of the Nobel prize, it organises this workshop, sponsored by a grant from the Economic and Social Research Council (ESRC) on "Games and Economic Behaviour".

The highlight of this workshop is a popular talk by Alvin Roth himself: "Who Gets What? The New Economics of Matchmaking and Market Design", and its summary shows the practical importance of the topic of the workshop.

Speakers:


Sophie Bade (Royal Holloway)	Lars Ehlers (Université de Montreal)	Aytek Erdil (Cambridge)

Flip Klijn (Institute for Economic Analysis, Barcelona)	David Manlove (Glasgow)	Alvin Roth (Stanford)

Location: Shaw Library (6th floor, Old Building, LSE)

Maps of the LSE campus can be found here: http://www2.lse.ac.uk/mapsAndDirections/findingYourWayAroundLSE.aspx

Everybody is welcome and participation is free. However, due to the expected popularity of the event, in particular the talk by Alvin Roth at 4:10pm, it is compulsory to register on a FIRST REGISTERED, FIRST SERVE basis by email to Rebecca Lumb at R.C.Lumb@lse.ac.uk.
Please note that participation for the following talks is now fully booked and reservations can no longer be taken:
Erdil at 2pm; Bade at 2:45pm; Roth at 4:10pm.
Refreshments and lunch will be provided to registered participants.

Schedule and Abstracts

(2-page downloadable PDF)

10:05 welcome

10:15 Flip Klijn (Institute for Economic Analysis, Barcelona)
"A Many-to-Many Rural Hospital Theorem"

Abstract:
We show that the full version of the so-called "rural hospital theorem" generalizes to many-to-many matching problems where agents on both sides of the problem have substitutable and weakly separable preferences. In contrast with the existing literature, we reinforce our result by showing that when agents' preferences satisfy substitutability, the domain of weakly separable preferences is also maximal for the rural hospital theorem to hold.
(Joint work with Ayse Yazici.)

11:00-11:30 coffee break

11:30 Lars Ehlers (Université de Montreal, Canada)
"Strategy-Proofness Makes the Difference: Deferred-Acceptance with Responsive Priorities"

Abstract:
In college admissions and student placements at public schools, the admission decision can be thought of as assigning indivisible objects with capacity constraints to a set of students such that each student receives at most one object and monetary compensations are not allowed. In these important market design problems, the agent-proposing deferred-acceptance (DA-)mechanism with responsive strict priorities performs well and economists have successfully implemented DA-mechanisms or slight variants thereof. We show that almost all real-life mechanisms used in such environments--including the large classes of priority mechanisms and linear programming mechanisms--satisfy a set of simple and intuitive properties. Once we add strategy-proofness to these properties, DA-mechanisms are the only ones surviving. In market design problems that are based on weak priorities (like school choice), generally multiple tie-breaking (MTB) procedures are used and then a mechanism is implemented with the obtained strict priorities. By adding stability with respect to the weak priorities, we establish the first normative foundation for MTB-DA-mechanisms that are used in New York City.
(Joint work with Bettina Klaus.)

12:15 David Manlove (Glasgow)
"Junior Doctor Allocation and Kidney Exchange: Theory and Practice"

Abstract:
Matching problems typically involve assigning agents to commodities, possibly on the basis of ordinal preferences or other metrics. These problems have large-scale applications to centralised clearinghouses in many countries and contexts. Moreover, these problems have received much exposure in recent months due to the award of the Nobel Prize in Economic Sciences to Al Roth and Lloyd Shapley.
In this talk I will describe the matching problems featuring in two centralised clearinghouses in the UK that have involved collaborations between the National Health Service and the University of Glasgow. One of these deals with the allocation of junior doctors to Scottish hospitals, and the other is concerned with finding kidney exchanges among incompatible donor-patient pairs across the UK.
In each case I will describe the applications, briefly outline the theoretical underlying problems, discuss the algorithmic techniques for their solution, and give an overview of results arising from real data connected with the matching schemes in recent years.
(Joint work with Rob Irving and Gregg O'Malley.)

13:00-14:00 lunch (buffet at the Shaw Library)

14:00 Aytek Erdil (Cambridge)
"Prioritizing Diversity in School Choice"

Abstract:
Promoting diversity in schools has recently emerged as an important policy goal. Typically school choice programs take into account student preferences and allocate scarce schools on the basis of priorities, using stability as the solution concept. Therefore a notion of prioritizing diversity is essential. We introduce a rich class of priorities which capture intuitive notions of diversity. Substitutable priorities with ties not only ensure existence of stable assignments, but also allow students of same types to be treated equally. Moreover we describe an algorithm which finds an optimal stable assignment.
(Joint work with Taro Kumano.)

14:45 Sophie Bade (Royal Holloway)
"Random Serial Dictatorship - the One and Only"

Abstract:
Given any Pareto optimal, strategy-proof and non-bossy deterministic matching mechanism for a housing problem, define a random matching mechanism by assigning agents to the roles in the deterministic mechanism via a uniform lottery over all possible assignments. I show that the resulting random matching mechanism is equivalent to the random serial dictatorship, where the order of dictators is determined by the uniform distribution over all possible orders. The present result extends the celebrated equivalence between a uniform randomization over Gale's top trading cycle mechanism and the random serial dictatorship to the grand set of all Pareto optimal, strategy-proof and non-bossy matching mechanisms. 15:30-16:05 coffee break

15:30-16:00 coffee break

16:10 Alvin Roth (Stanford)
"Who Gets What? The New Economics of Matchmaking and Market Design"

Abstract:
What are markets and marketplaces? How do they work? How do they fail? How can we fix them when they are broken? In recent years economists have stepped forward as market designers to try to craft answers to these questions. These questions are particularly difficult for matching markets, which are markets in which you cannot just choose what you want, but also have to be chosen. If a market has an application or selection procedure then it is a matching market, and matching markets determine some of the most important transitions in life. Who goes to which schools and universities? Who gets which jobs? Who gets scarce organs for transplant? I'll illustrate with examples of recent market designs, in school choice, labor markets, and kidney exchange.

17:15-18:30 reception in the Senior Common Room (5th floor)

This workshop is part of an ESRC sponsored series of one-day workshops. At LSE these are organised by Olivier Gossner and Bernhard von Stengel.

The previous workshop at LSE took place on Friday, June 10, 2011, on "Correlation and Coordination in Games", with speakers Francoise Forges, Vince Crawford, Michalis Drouvelis, Eran Shmaya, Nick Vriend, Joel Sobel.