Wednesday, February 6, 2013, London School of Economics
ESRC Game Theory Workshop
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".
"Matching Under Preferences"
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)
"A Many-to-Many Rural Hospital Theorem"
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.)
"Strategy-Proofness Makes the Difference: Deferred-Acceptance with Responsive Priorities"
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.)
"Junior Doctor Allocation and Kidney Exchange: Theory and Practice"
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.)
"Prioritizing Diversity in School Choice"
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.)
"Pareto Optimal, Strategy Proof, Non-Bossy and Anonymous Random Matching Mechanisms"
Take any Pareto optimal, strategy proof and non-bossy matching mechanism for a housing problem. Define a uniform randomization over this mechanism by drawing the assignment of agents to the roles in the mechanism from a uniform distribution over all possible such assignments. I show that any such uniform randomization is equivalent to random serial dictatorship. According to random serial dictatorship the probability of a matching is calculated as the fraction of all orders of dictators according to which said matching arises divided by the grand set of all possible orders of dictators. This extends the Abdulkadiroglu and Soenmez' (1998) celebrated equivalence result between the uniform randomization over Gale's top trading cycles mechanism and random serial dictatorship to the entire set of all Pareto optimal, strategy proof and non-bossy matching mechanisms. 15:30-16:05 coffee break
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.