Match Up 2017: April 20-21 at Microsoft Research New England

MATCH-UP 2017, the fourth workshop in the series of interdisciplinary and international workshops on matching under preferences, will take place April 20-21, 2017.

Venue:Microsoft Research New England Cambridge, MA 02142

	DAY 1
8:00 A.M.	Breakfast
8.45 A.M.	Invited Talk 1 —Estelle Cantillon, Université libre de Bruxelles The efficiency – stability tradeoff in school choice: Lessons for market design Abstract: A well-known result for the school choice problem is that ex-post efficiency and stability may not be compatible. In the field, that trade-off is sometimes small, sometimes big.  This talk will summarize existing and new results on the drivers of this trade-off and derive the implications for the design of priorities and tie-breaking rules.
9.30 A.M.	Session 1
10.30 A.M.	Break
10.50 A.M.	Session 2
12.30 P.M.	Lunch
1:00 P.M.	Outlook Talk 1 – Al Roth, Stanford Frontiers of Kidney Exchange Abstract: Kidney exchange is different from many market design efforts I’ve been involved in, because it affects the everyday conduct of transplant centers, so we’re constantly adapting to their big strategy sets…(in contrast to e.g. annual labor markets or school choice which don’t affect the daily conduct of residency programs and schools …)The early design challenges in kidney exchange mostly involved dealing with congestion (and the solutions involved long chains, standard acquisition charges, and attempts to better elicit surgeons’ preferences over kidneys).The current challenges to kidney exchange involve creating more thickness in the markets, and I’ll touch on several new initiatives: 1. Frequent flier programs to encourage transplant centers to enroll more of their easy to match pairs; 2. Global kidney exchange; 3. Information deserts: populations of Americans who don’t get transplants; 4. Deceased donor initiated chains ; a. Increasing deceased donation: military share, priority in Israel
2:00 P.M.	Session 3
3.40 P.M.	Break
4:00 P.M.	Session 4
5:00 P.M.	Invited Talk 2 – Aaron Roth, UPENN Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy) Abstract: In this talk, we will walk through a case study of how techniques developed to design “stable” algorithms can be brought to bear to design asymptotically dominant strategy truthful mechanisms in large markets, without the need to make any assumptions about the structure of individual preferences. Specifically, we will consider the many-to-one matching problem, and see a mechanism for computing school optimal stable matchings, that makes truthful reporting an approximately dominant strategy for the student side of the market. The approximation parameter becomes perfect at a polynomial rate as the number of students grows large, and the analysis holds even for worst-case preferences for both students and schools. Joint work with: Sampath Kannan, Jamie Morgenstern, and Zhiwei Steven Wu.
5.45 P.M.	Break
6:00 P.M.	Poster Lightning Talks
6.30 P.M.	Reception and Poster Session
8:00 P.M.	END
	DAY 2
8:00 A.M.	Breakfast
8.45 A.M.	Invited Talk 3 — Michael Ostrovsky, Stanford Matching under preferences: beyond the two-sided case Abstract: I will present an overview of several recent papers showing that most of the key results of matching theory generalize naturally to a much richer setting: trading networks. These networks do not need to be two-sided, and agents do not have to be grouped into classes (“firms”, “workers”, and so on). What is essential for the generalization is that the bilateral contracts representing relationships in the network have a direction (e.g., one agent is the seller and the other is the buyer), and that agents’ preferences satisfy a suitably adapted substitutability notion. For this setting, for the cases of discrete and continuous sets of possible contracts, I will discuss the existence of stable outcomes, the lattice structure of the sets of stable outcomes, the relationship between various solution concepts (stability, core, competitive equilibrium, etc.), and other results familiar from the literature on two-sided markets.
9.30 A.M.	Session 5
10.30 A.M.	Break
10.50 A.M.	Session 6
12.30 P.M.	Lunch
1:00 P.M.	Lunch w/Outlook Talk 2 — David Manlove, University of Glasgow Selected Algorithmic Open Problems in Matching Under Preferences Abstract: The research community working on matching problems involving preferences has grown in recent years, but even so, plenty of interesting open problems still exist, many with large-scale practical applications.  In this talk I will outline some of these open problems that are of an algorithmic flavour, thus giving an outlook on some of the research challenges in matching under preferences that the computer science community might seek to tackle over the next decade.
2:00 P.M.	Session 7
	Making it Safe to Use Centralized Markets: Epsilon - Dominant Individual Rationality and Applications to Market Design Speakers: Ben Roth and Ran Shorrer Abstract: A critical, yet under-appreciated feature of market design is that centralized markets operate within a broader context; often market designers cannot force participants to join a centralized market. Well-designed centralized markets must induce participants to join voluntarily, in spite of pre-existing decentralized institutions they may already be using. We take the view that centralizing a market is akin to designing a mechanism to which people may voluntarily sign away their decision rights. We study the ways in which market designers can provide robust incentives that guarantee agents will participate in a centralized market. Our first result is negative and derives from adverse selection concerns. Near any game with at least one pure strategy equilibrium, we prove there is another game in which no mechanism can eliminate the equilibrium of the original game. In light of this result we offer a new desideratum for mechanism and market design, which we term epsilon-dominant individual rationality. After noting its robustness, we establish two positive results about centralizing large markets. The first offers a novel justification for stable matching mechanisms and an insight to guide their design to achieve epsilon-dominant individual rationality. Our second result demonstrates that in large games, any mechanism with the property that every player wants to use it conditional on sufficiently many others using it as well can be modified to satisfy epsilon-dominant individual rationality while preserving its behavior conditional on sufficient participation. The modification relies on a class of mechanisms we refer to as random threshold mechanisms and resembles insights from the differential privacy literature.
3.40 P.M.	Break
4:00 P.M.	Session 8
5.20 P.M.	Break
5.30 P.M.	Invited Talk 4 — Marek Pycia, UCLA Invariance and Matching Market Outcomes Abstract: The empirical studies of school choice provide evidence that standard measures of admission outcomes are the same for many Pareto efficient mechanisms that determine the market allocation based on ordinal rankings of individual outcomes. The paper shows that two factors drive this intriguing puzzle: market size and the invariance properties of the measures for which the regularity has been documented. In addition, the talk will explore the consequences of these findings: the usefulness of non-invariant outcome measures and of mechanisms that elicit preference intensities.
6.15 P.M.	Closing Remarks
6.30 P.M.	END