About
MATCHUP 2017 is the fourth workshop in an interdisciplinary and international workshop series on matching under preferences.
Matching problems with preferences occur in widespread applications such as the assignment of schoolleavers to universities, junior doctors to hospitals, students to campus housing, children to schools, kidney transplant patients to donors and so on. The common thread is that individuals have preference lists over the possible outcomes and the task is to find a matching of the participants that is in some sense optimal with respect to these preferences.
The remit of this workshop is to explore matching problems with preferences from the perspective of algorithms and complexity, discrete mathematics, combinatorial optimization, game theory, mechanism design and economics, and thus a key objective is to bring together the research communities of the related areas.
List of Topics
The matching problems under consideration include, but are not limited to:
 Twosided matchings involving agents on both sides (e.g., college admissions, medical resident allocation, job markets)
 Twosided matchings involving agents and objects (e.g., house allocation, course allocation, project allocation, assigning papers to reviewers, and school choice)
 Onesided matchings (e.g., roommate problems and kidney exchanges)
 Matching with payments (e.g., assignment games and supply chain/trading network exchange)
Invited Speakers
 Estelle Cantillon, Université libre de Bruxelles
 David Manlove, University of Glasgow
 Michael Ostrovsky, Stanford Graduate School of Business
 Marek Pycia, University of California, Los Angeles
 Aaron Roth, University of Pennsylvania
 Al Roth, Stanford
Submissions
We solicit papers and posters on matching under preferences. The matching problems under consideration include, but are not limited to:
 Twosided matchings involving agents on both sides (e.g., college admissions, medical resident allocation, job markets)
 Twosided matchings involving agents and objects (e.g., house allocation, course allocation, project allocation, assigning papers to reviewers, and school choice)
 Onesided matchings (e.g., roommate problems and kidney exchanges)
Poster Submissions
MATCHUP solicits posters of papers not previously published in another conference or journal. Papers may be under submission to another conference or journal. To have your paper be considered for the MATCHUP poster session, please email the following information to MATCHUP2017@microsoft.com :
 Presenting author name
 Presenting author institution
 Presenting author email address
 Title
 Complete list of authors
 Working draft of paper
 Posters may be up to 48″W x 36″H
 The deadline for poster submissions has now passed, and is closed.
Paper Submissions
Authors should indicate which format type their paper should be considered under. The proceedings will take the form of informal working notes distributed at the workshop and online.
Format A
 Original contribution, not previously published in (or accepted by) another conference proceedings or journal
 Not under review for a conference or journal elsewhere
 At most 12 pages (including bibliography) using 11 point font or larger with at least 1″ margins all round, and in singlecolumn format. Any material beyond this limit should be placed in a clearly marked appendix which will be read at the discretion of the programme committee
 Accepted papers will be published in proceedings (however, this should not prevent the simultaneous or subsequent submission of contributed papers to other workshops, conferences or journals)
Format B
 Not necessarily original work
 Can have been published already in (or accepted by) another conference proceedings or journal
 Can be under review for a conference or journal elsewhere
 No page limit
 Only the abstract will be published in proceedings
Information on submitting papers:
 Submission site: EasyChair
 Paper submission deadline : Friday, December 9th, 2016
 The deadline for paper submissions has now passed, and is closed.
Schedule
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 wellknown result for the school choice problem is that expost efficiency and stability may not be compatible. In the field, that tradeoff is sometimes small, sometimes big. This talk will summarize existing and new results on the drivers of this tradeoff and derive the implications for the design of priorities and tiebreaking rules. 
9.30 A.M.  Session 1 
A Simple Model for the Top Trading Cycles School Choice Mechanism Using Fluid Approximation
Authors: Jacob Leshno and Irene Lo Abstract:
Many cities determine the assignment of students to schools through a school choice mechanism which calculates an assignment based on student preferences and school priorities. The prominent Top Trading Cycles (TTC) algorithm can be applied to give a strategyproof and Pareto efficient assignment, but the combinatorial description of TTC makes it nontransparent to parents and difficult to analyze for designers. Using a fluid approximation model, we give a tractable characterization of the TTC mechanism for school choice: the TTC assignment can be simply described by n^{2} admission thresholds, where n is the number of schools, and these thresholds can be calculated by a differential equation. The model also allows us to analyze general sequential trade procedures, and show that changes in trading priority can have nontrivial indirect effects on the allocation. We also apply this model to solve for optimal investment in school quality, and help explain empirical findings about the relation between the TTC assignment and the Deferred Acceptance assignment. To validate the fluid model we show that it gives a good approximation for strongly converging economies. Our analysis draws on an interesting connection between continuous trading procedures and continuous time Markov chains. 

Pairwise matching in large economies
Authors: Michael Greinecker and Christopher Kah Abstract:
We formulate a general model of twosided pairwise matching for continuum economies and prove the existence of stable matchings. The data of our model are not individual agents but the population distribution of their characteristics, which can be multidimensional and need not lie in a compact set. Our model allows for transfers as well as their absence, general widespread externalities, and match specific contracts and activities. Continuum versions of the assignment game or the marriage model can be obtained as special cases, as well as intermediate models with limited side payments. Our distributional model can be interpreted as both a limit of finite matching models and as a reduced form of a genuine continuum model in which individual agents are explicitly modeled. 

Lone wolves in infinite, discrete matching markets
Author: Ravi Jagadeesan Abstract:
In finite twosided matching markets, the lone wolf theorem guarantees that the same agents remain unmatched in all stable outcomes. I show by example that this assertion is not true in infinite, discrete markets. However, despite the fact that the lone wolf theorem is often used to derive strategyproofness, deferred acceptance remains (group) strategyproof in many infinite markets. 

10.30 A.M.  Break 
10.50 A.M.  Session 2 
Dynamic Reserves in Matching Markets: Theory and Applications
Authors: Bertan Turhan and Orhan Aygun Abstract:
Indian engineering school admissions, which draw more than 500,000 applications per year, suffer from an important market failure: Through their affirmative action program, a certain number of seats are reserved for different castes and tribes. How ever, when some of these seats are unfilled, they are not offered to other groups, and the system is vastly wasteful. Moreover, since students care not only about the school they are assigned to but also whether they are assigned through reserves or not, they may manipulate the system both by not revealing their privilege type and by changing their preferences over programs. In this paper, we propose a new matching model with the ability to release vacant seats to the use of other students by respecting certain affirmative action objectives. We design a new choice function for schools that respects affirmative action objectives, and increases efficiency. We propose a mechanism that is stable, strategy proof, and respects testscore improvements with respect to these choice functions. Moreover, we show that some distributional objectives that can be achieved by capacitytransfers cannot be achieved by slotspecific priorities. 

Strategyproof ParetoStable Mechanisms for TwoSided Matching with Indifferences
Authors: Nevzat Onur Domanic, ChiKit Lam and C. Gregory Plaxton Abstract:
We study variants of the stable marriage and college admissions models in which the agents are allowed to express weak preferences over the set of agents on the other side of the market and the option of remaining unmatched. For the problems that we address, previous authors have presented polynomialtime algorithms for computing a “Paretostable” matching. In the case of college admissions, these algorithms require the preferences of the colleges over groups of students to satisfy a technical condition related to responsiveness. We design new polynomialtime Paretostable algorithms for stable marriage and college admissions that correspond to strategyproof mechanisms. For stable marriage, it is known that no Paretostable mechanism is strategyproof for all of the agents; our algorithm provides a mechanism that is strategyproof for the agents on one side of the market. For college admissions, it is known that no Paretostable mechanism can be strategyproof for the colleges; our algorithm provides a mechanism that is strategyproof for the students. 

First ChoiceMaximizing School Choice Mechanisms
Authors: Umut Dur, Timo Mennle and Sven Seuken Abstract:
We investigate first choicemaximality (FCM) (i.e., a maximal share of students is matched to their reported first choices), a common desideratum in many school districts. No FCM mechanism can be stable; however, we find first choicestability (FCS) (i.e., no student forms a blocking pair with her first choice) to be the strongest rankbased relaxation of stability that is compatible with FCM. Focusing on the class of FCM and FCS mechanisms (which includes the widely used Boston mechanism and its variants), we show that the Pareto efficient members of this class form a minimally manipulable subset. Moreover, we identify the Nash equilibrium outcomes of any mechanism in this class when all students are strategic and when some student are sincere. Our analysis generalizes that of Ergin and Sönmez (2006) and Pathak and Sönmez (2008) from the Boston mechanism to the general class of FCM and FCS mechanisms. Our results suggest a novel approach to the design of school choice mechanisms where strategic students selfselect into receiving their reported school in a first step, so that in a second step, the matching of sincere students can be made independently of the usual incentive constraints. 

Endowments, Exclusion, and Exchange
Authors: Ivan Balbuzanov and Maciej Kotowski Abstract:
We study a discrete exchange and assignment economy with a rich endowment structure. Identifying deficiencies with classic solutions, such as the core, we propose a new cooperative solution concept for resource allocation problems, the exclusion core. The exclusion core is neither weaker nor stronger than the (strong) core and it rests upon a foundational idea in the legal understanding of property, the right to exclude others. We extend the exclusion core to relational economies where ownership rights and endowments are qualified by social hierarchies or priorities. A generalization of the top trading cycles algorithm can identify exclusion core allocations. 

Efficient and Essentially Stable Assignments
Authors: Andrew Kloosterman and Peter Troyan Abstract:
An important desideratum in prioritybased allocation is stability: no agent should claim an object because she has higher priority than the agent to whom it is assigned. However, stable matchings are in general Pareto inefficient, forcing upon designers a difficult tradeoff. This paper alleviates this tension between efficiency and stability by defining an assignment to be essentially stable if any claim an agent has to an object she prefers is vacuous, in the sense that it initiates a chain of reassignments that ultimately results in the initial claimant losing the object to a third student with even higher priority; on the other hand, if a nonvacuous claim exists, the assignment is strongly unstable. A main practical advantage to our definition is its simplicity: under an essentially stable assignment, explaining to agents why their claims are vacuous becomes straightforward, even to nonexperts who may not fully understand the inner workings of a given mechanism. We show that mechanisms based on Shapley and Scarf’s TTC algorithm, while efficient, are strongly unstable, while Kesten’s EADA mechanism is both Pareto efficient and essentially stable. 

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:

2:00 P.M.  Session 3 
On likely solutions of the stable matching problem with unequal numbers of men and women
Author: Boris Pittel Abstract:
Consider a set of men and a set of women contemplating selection of a marriage partner. It is assumed that each man and each woman has his/her preferences for a marriage partner, with no ties allowed. A maximal matching is called stable if there is no unmarried pair who prefer each other to their respective partners in the matching. A classic theorem, due to Gale and Shapley, asserts that, given any system of preferences, there exists at least one stable matching. Most of algorithmic/probabilistic research had been focused on the case of two sides having the same size. Recently Ashlagi, Kanoria and Leshno discovered that even a relatively slight difference between two sizes leads to a dramatic change in the likely properties of the stable matchings. As a followup, we extend our previous work on the expected number of stable matchings for the balanced case and derive an asymptotic formula for the expected number of stable matchings for the full range of tthe unequal sizes. For the size difference 1, the expected number is instantly smaller than its counterpart for the balanced case by a squared logarithmic factor, but remains quite sizable. As soon as the size difference is of the order of smaller size, the expected, whence the likely, number of stable matchings becomes bounded as both sizes grow indefinitely. 

Circulation under Responsive Preferences
Authors: Peter Biro, Flip Klijn and Szilvia Papai Abstract:
We study markets in which each agent is endowed with multiple units of an indivisible and agentspecific good. Monetary compensations are not possible. An outcome of a market is given by a circulation which consists of a balanced exchange of goods. Agents only have (responsive) preferences over the bundles they receive.We prove that for general capacity configurations there is no circulation rule that satisfies individual rationality, Paretoefficiency, and strategyproofness. We characterize the capacity configurations for which the three properties are compatible, and show that in this case the Circulation Top Trading Cycle (cTTC) rule is the unique rule that satisfies all three properties. We explore the incentive and efficiency properties of the cTTC rule for general capacity configurations and provide a characterization of the rule for lexicographic preferences.Next, we introduce and study two families of individually rational serial rules in which agents sequentially choose single goods or bundles. We show that in the first (second) case the rules are Paretoefficient for lexicographic (responsive) preferences. Finally, we consider the family of Segmented Trading Cycle (STC) rules where agents are required to exchange their goods in market segments. We show that STC rules are strategyproof. 

StrategyProof TieBreaking
Authors: Lars Ehlers and Alexander Westkamp Abstract:
A set of indivisible objects is allocated among agents with strict preferences. Each object has a weak priority ranking of the agents. A collection of priority rankings, a priority structure, is solvable if there is a strategyproof mechanism that is constrained efficient, i.e. that always produces an agentoptimal stable matching. We characterize all solvable priority structures satisfying the following two restrictions: (A) Either there are no ties, or there is at least one fourway tie. (B) For any two agents i and j, if there is an object that assigns higher priority to i than j, there is also an object that assigns higher priority to j than i. We show that there are at most three types of solvable priority structures: The strict type, the house allocation with existing tenants (HET) type, where, for each object, there is at most one agent who has strictly higher priority than another agent, and the task allocation with unqualied agents (TAU) type, where, for each object, there is at most one agent who has strictly lower priority than another agent. Out of these three, only HET priority structures are shown to admit a strongly group strategyproof and constrained ecient mechanism. 

Strategyproof Pareto Improvement
Authors: Samson Alva and Vikram Manjunath Abstract:
We consider a general model of resource allocation with unitdemand agents, each of whom have an outside option of privately known value. The model encompasses (prioritybased) object allocation, matching with contracts, provision of a public good when agents may choose not to participate, and more. If a mechanism designer’s choice of a strategyproof allocation rule must weakly Paretodominate an individually rational and participationmaximal benchmark rule, we show there is a unique solution to his problem, if one exists. As a consequence, for many market design applications, many known rules are on the efficient frontier of strategyproof rules. We relate strategyproof Pareto improvements of a rule with expansions in the set of participating agents. This implies a revenue equivalence result for dominant strategy incentive compatible and individually rational rules in settings with quasilinear preferences and transfers. 

Effect of selfish choices in deferred acceptance with short lists
Authors: Hedyeh Beyhaghi, Daniela Saban and Eva Tardos Abstract:
We study the outcome of deferred acceptance when prospective medical residents can only apply to a limited set of hospitals. This limitation requires residents to make a strategic choice about the quality of hospitals they apply to. Through a mix of theoretical and experimental results, we study the effect of this strategic choice on the preferences submitted by participants, as well as on the overall welfare. We find that residents’ choices in our model mimic the behavior observed in real systems where individuals apply to a mix of positions consisting mostly of places where they are reasonably likely to get accepted, as well as a few “reach” applications to hospitals of very high quality, and a few “safe” applications to hospitals of lower than their expected level. Surprisingly, the number of such “safe” applications is not monotone in the number of allowed applications. We also find that selfish behavior can hurt social welfare, but the deterioration of overall welfare is very minimal. 

3.40 P.M.  Break 
4:00 P.M.  Session 4 
Assortment Planning in School Choice
Author: Peng Shi Abstract:
In many public school systems across the US, school choice has become the preferred alternative to the traditional method of assigning each student to a neighborhood school. In a typical school choice system, each student submits a preference ranking for a set of schools called the student’s \emph{menu}. The school board then assigns students to schools using the GaleShapley deferred acceptance (DA) algorithm, which takes into account \emph{priorities} that differentiate certain types of students, as well as \emph{quotas} for students at each school. The menus, priorities and quotas are policy levers with which the school board may induce socially desirable outcomes. This paper presents a systematic approach for optimizing these policy levers. Our methodology is based on a novel connection between stable matching and assortment planning, which allows us to approximate school choice as a convex optimization problem. The key to solving this convex optimization is to find an assortment of schools for each student type that maximizes the sum of utilities for this type and externalities for others. We refer to this as the “sociallyoptimal assortment planning” problem, and show that it is a generalization of the revenuemaximizing assortment planning problem studied in the revenue management literature. We give efficient algorithms for the sociallyoptimal assortment planning problem for the multinomial logit (MNL), nested logit, and Markov chain based utility distributions. We demonstrate the effectiveness of our methodology by applying it to actual data from Boston Public Schools. We construct optimized menus and priority distributions that outperform the status quo, improving the expected utilities of students and the predictability of the assignment outcome while maintaining the same amount of busing. 

The Iterative Deferred Acceptance Mechanism
Authors: Inacio Bo and Rustamdjan Hakimov Abstract:
We introduce a new mechanism for matching students to schools or universities, denoted Iterative Deferred Acceptance Mechanism (IDAM), inspired by procedures currently being used to match millions of students to public universities in Brazil and China. Unlike most options available in the literature, IDAM is not a direct mechanism. Instead of requesting from each student a full preference over all colleges, the student is instead repeatedly asked to choose one college among those which would accept her given the current set of students choosing that college. Although the induced sequential game has no dominant strategy, when students simply choose the most preferred college in each period (denoted the straightforward strategy), the matching that is produced is the Student Optimal Stable Matching. Moreover, under imperfect information, students following the straightforward strategy is an Ordinal Perfect Bayesian Equilibrium. Based on data from 2016, we also provide evidence that, due to shortcomings which are absent in the modified version that we propose, the currently used mechanism in Brazil fails to assist the students with reliable information about the universities that they are able to attend, and are subject to manipulation via cutoffs, a new type of strategic behavior that is introduced by this family of iterative mechanisms and observed in the field. 

Dynamic Matching in School Choice: Efficient Seat Reallocation After Late Cancellations
Authors: Itai Feigenbaum, Yash Kanoria, Irene Lo and Jay Sethuraman Abstract:
In many centralized school admission systems, a significant fraction of allocated seats are later vacated, often due to students obtaining better outside options. We consider the problem of reassigning these seats in a fair and efficient manner while also minimizing the movement of students between schools. Centralized admissions are typically conducted using the deferred acceptance (DA) algorithm, with a lottery used to break ties caused by indifferences in school priorities. The key idea we introduce is to reassign vacated seats using a suitable permutation of the first round lottery numbers. In particular, we show that a mechanism based on a simple reversal of the first round lottery order performs the best among all truthful mechanisms satisfying some natural efficiency and fairness properties. Empirical investigations based on data from NYC high school admissions support our theoretical findings. 

5:00 P.M.  Invited Talk 2 – Aaron Roth, UPENNApproximately Stable, School Optimal, and StudentTruthful ManytoOne 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 manytoone 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 worstcase 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, StanfordMatching under preferences: beyond the twosided 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 twosided, 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 twosided markets. 
9.30 A.M.  Session 5 
Trading Networks with Bilateral Contracts
Authors: Alexander Teytelboym, Tamas Fleiner, Zsuzsanna Jankó and Akihisa Tamura Abstract:
We consider general networks of bilateral contracts that include supply chains. We define a new stability concept, called trail stability, and show that any network of bilateral contracts has a trailstable outcome whenever agents’ choice functions satisfy full substitutability. Trail stability is a natural extension of chain stability, but is a stronger solution concept in general contract networks. Trailstable outcomes are not immune to deviations of arbitrary sets of firms. In fact, we show that outcomes satisfying an even more demanding stability property – full trail stability – always exist. For fully trailstable outcomes, we prove results on the lattice structure, the rural hospitals theorem, strategyproofness and comparative statics of firm entry and exit. We pin down a condition under which trailstable and fully trailstable outcomes coincide. We then completely describe the relationships between various other concepts. When contracts specify trades and prices, we also show that competitive equilibrium exists in networked markets even in the absence of fully transferrable utility. The competitive equilibrium outcome is (fully) trailstable. 

Too Good to Fire: NonAssortative Matching to Play a Dynamic Game
Authors: Benjamin Sperisen and Thomas Wiseman Abstract:
We study stable outcomes in a onetoone matching market with firms and workers. The model endogenizes how transferable utility is within a match: when a firmworker pair is matched, they play an infinitehorizon discounted dynamic game with onesided, observable effort. Partners’ types are complementary in determining the maximal feasible payoffs. In our setting, the classic result that with complementary types stable matchings are positively assortative does not hold. Increasing the quality of a match harms dynamic incentives, because a firm cannot credibly threaten to fire a worker who is productive even with low effort. Thus, firms may prefer lowertype workers who will exert more effort. Our analysis suggests a new interpretation of efficiency wages: committing to pay a high wage can improve effort incentives indirectly by making the firm more willing to walk away. 

Matching Auctions
Authors: Alessandro Pavan and Daniel Fershtman Abstract:
We study mediated manytomany matching in markets in which valuations evolve over time as the result of shocks, learning through experimentation, or a preference for variety. The matching dynamics that maximize either the platform’s profits, or welfare can be sustained through auctions implementing the matches with the highest bilateral score up to capacity. In equilibrium, bidding is straightforward and myopic. The analysis also sheds light on the merits of regulating such markets. When match values are positive, proÖt maximization involves fewer and shorter interactions than welfare maximization. This conclusion need not extend to markets where certain agents dislike certain interactions. 

10.30 A.M.  Break 
10.50 A.M.  Session 6 
Communication Requirements and Informative Signaling in Matching Markets
Authors: Itai Ashlagi, Mark Braverman, Yash Kanoria and Peng Shi Abstract:
We study the amount of communication needed to find a stable matching in a twosided matching market with private preferences when agents have some knowledge of the preference distribution. We show that in a twosided market with workers and firms, when the preferences of workers are arbitrary and private and the preferences of firms follow a multinomiallogit (MNL) choice model with commonly known and heterogeneous parameters, there exists an algorithm that finds a stable matching with high probability and requires at most $O^*(\sqrt{n})$ bits of communication per agent. (We show that this is the best possible under this setting.) The algorithm, which we call communication efficient deferred acceptance (CEDA), is a modification of the deferred acceptance algorithm with workers applying. In this algorithm, firms help workers better target applications by signaling workers that they idiosyncratically like and broadcasting to the market a qualification requirement to discourage those with no realistic chances from applying. In the special case in which preferences of both workers and firms follow a tiered structure, we show that the signaling can be done in a parallel and decentralized way. In terms of incentives, the protocols we propose inherit many properties of DA under full preference elicitation. In large markets with a small core, they are incentive compatible for everyone. These results yield insights on how matching markets can be better organized to reduce congestion. 

A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas
Author: Yu Yokoi Abstract:
Classified stable matching, proposed by Huang, describes a matching model between academic institutes and applicants, in which each institute has upper and lower quotas on classes, i.e., subsets of applicants. Huang showed that it is NPhard to decide whether there exists a stable matching or not in general. On the other hand, he showed that the problem is solvable if classes form a laminar family. For this case, Fleiner and Kamiyama gave a concise interpretation in terms of matroids and showed the lattice structure of stable matchings.In this paper, we introduce stable matchings on generalized matroids, extending the model of Fleiner and Kamiyama. We design a polynomialtime algorithm which finds a stable matching or reports the nonexistence. We also show that, the set of stable matchings, if nonempty, forms a lattice with several significant properties. Furthermore, we extend this structural result to the polyhedral framework, which we call stable allocations on generalized polymatroids. 

The weighted stable matching problem
Authors: Linda Farczadi and Natalia Guricanova Abstract:
We study the stable matching problem in nonbipartite graphs with incomplete but strict preference lists, where the edges have weights and the goal is to compute a stable matching of minimum or maximum weight. This problem is known to be NPhard in general. Our contribution is two fold: a polyhedral characterization and an approximation algorithm. Previously Chen et al. have shown that the stable matching polytope is integral if and only if the subgraph obtained after running phase one of Irving’s algorithm is bipartite. We improve upon this result by showing that there are instances where this subgraph might not be bipartite but one can further eliminate some edges and arrive at a bipartite subgraph. Our elimination procedure ensures that the set of stable matchings remains the same, and thus the stable matching polytope of the final subgraph contains the incidence vectors of all stable matchings of our original graph. This allows us to characterize a larger class of instances for which the weighted stable matching problem is polynomialtime solvable. We also show that our edge elimination procedure is best possible, meaning that if the subgraph we arrive at is not bipartite, then there is no bipartite subgraph that has the same set of stable matchings as the original graph. We complement these results with a 2approximation algorithm for the minimum weight stable matching problem for instances where each agent has at most two possible partners in any stable matching. This is the first approximation result for any class of instances with general weights. 

New and simple algorithms for stable flow problems
Authors: Ágnes Cseh and Jannik Matuschke Abstract:
Stable flows generalize the wellknown concept of stable matchings to markets in which transactions may involve several agents, forwarding flow from one to another. An instance of the problem consists of a capacitated directed network, in which the vertices express their preferences over their incident edges. A network flow is stable if there is no group of vertices that all could benefit from rerouting the flow along a walk.Fleiner established that a stable flow always exists by reducing it to the stable allocation problem. We present an augmentingpath algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocation as a blackbox subroutine. We further consider the problem of finding a stable flow such that the flow value on every edge is within a given interval. For this problem, we devise a simple and fast algorithm, which also can be used to find a solution to the stable marriage problem with forced and forbidden edges in an elegant way. Finally, we study the stable multicommodity flow model by Király and Pap. We present several graphbased reductions that show that it is without loss of generality to assume that no commodityspecific preference lists at the vertices and no commodityspecific capacities on the edges exist. We further show that it is NPcomplete to decide whether an integral solution exists. 

Stable Matching with Uncertain Pairwise Preferences
Authors: Haris Aziz, Peter Biro, Tamas Fleiner, Serge Gaspers, Ronald de Haan, Nicholas Mattei and Baharak Rastegari Abstract:
In this paper we study a twosided matching problem under preferences, where the agents have independent pairwise comparisons on their possible partners and these preferences may be uncertain. In this case preferences may be intransitive and agents may even have certain cycles in their preferences; e.g. an agent $a$ may prefer $b$ to $c$, $c$ to $d$, and $d$ to $b$, all with probability one. If an instance has such a cycle, then there may not exist any matching that is stable with positive probability. We focus on the computational problems of checking the existence of possibly and certainly stable matchings, i.e., matchings whose probability of being stable is positive or one, respectively. We show that finding possibly stable matchings is NPhard, even if only one side can have cyclic preferences. On the other hand we show that the problem of finding a certainly stable matching is polynomialtime solvable if only one side can have cyclic preferences and the other side has transitive preferences, but that this problem becomes NPhard when both sides can have cyclic preferences. The latter complexity result also implies the hardness of finding a kernel in a special class of directed graphs. 

12.30 P.M.  Lunch 
1:00 P.M.  Lunch w/Outlook Talk 2 — David Manlove, University of GlasgowSelected 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 largescale 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 
“STRATEGIC” BEHAVIOR IN A STRATEGYPROOF ENVIRONMENT
Authors: Avinatan Hassidim, Assaf Romm and Ran Shorrer Abstract:
We present direct field evidence of preference misrepresentation under deferred acceptance. A large fraction of highly educated participants, who had been informed about the strategyproof nature of the mechanism in numerous ways, failed to play truthfully: they ranked a nonfunded position above a funded position in the same program. This is despite being informed that rankordered lists are never made public, that funding is a positive signal of ability, and that funding comes with no strings attached. Preference misrepresentation is associated with weaker applicants. A laboratory experiment documents a strong negative causal relationship between applicants’ expected desirability and preference misrepresentation. 

Stable matching mechanisms are not obviously strategyproof
Authors: Itai Ashlagi and Yannai A Gonczarowski Abstract:
Many twosided matching markets, from labor markets to school choice programs, use a clearinghouse based on the applicantproposing deferred acceptance algorithm, which is well known to be strategyproof for the applicants. Nonetheless, a growing amount of empirical evidence reveals that applicants misrepresent their preferences when this mechanism is used. This paper shows that no mechanism that implements a stable matching is obviously strategyproof for any side of the market, a stronger incentive property than strategyproofness introduced by Li (2015). A stable mechanism that is obviously strategyproof for applicants is introduced for the case in which agents on the other side have acyclical preferences. Our findings suggest that strategic reasoning in twosided markets requires more cognitive effort by participants than in onesided markets. 

Strategic Stable Marriage
Authors: James Bailey and Craig Tovey Abstract:
We study stable marriage where individuals strategically submit private preference information to a publicly known stable marriage algorithm. We prove that no stable marriage algorithm ensures actual stability at a Nash equilibrium when individuals are strategic. Thus the set of Nash equilibria provides no predictive value nor guidance for mechanism design. We propose the following new minimal dishonesty equilibrium refinement, supported by experimental economics results: an individual will not strategically submit preference list $L$ if there exists a more honest $L’$ that yields as preferred an outcome. Then for all marriage algorithms satisfying monotonicity and IIA, every minimally dishonest equilibrium yields a sincerely stable marriage. This result supports the use of algorithms less biased than the (GaleShapley) manoptimal, which we prove yields the womanoptimal marriage in every minimally dishonest equilibrium. However, bias cannot be totally eliminated, in the sense that no monotonic IIA stable marriage algorithm is certain to yield the egalitarianoptimal marriage in a minimally dishonest equilibrium — thus answering an open question of Gusfield and Irving’s in the negative. Finally, we show that these results extend to student placement problems, where women are polyandrous and honest. but not to admissions problems, where women are both polyandrous and strategic. 

Making it Safe to Use Centralized Markets: Epsilon – Dominant Individual Rationality and Applications to Market Design
Authors: Ben Roth and Ran Shorrer Abstract:
A critical, yet underappreciated feature of market design is that centralized markets operate within a broader context; often market designers cannot force participants to join a centralized market. Welldesigned centralized markets must induce participants to join voluntarily, in spite of preexisting 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 epsilondominant 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 epsilondominant 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 epsilondominant 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. 

Integrating Schools for Centralized Admissions
Authors: Mehmet Ekmekci and M. Bumin Yenmez Abstract:
As school districts integrate charter schools for centralized admissions in Denver, New Orleans, Newark and Washington D.C., some schools have stayed out. Likewise, there is a recent proposal in Boston to unify public school admissions in a centralized clearinghouse. We provide a new framework to study the incentives of a school to join a clearinghouse and we show that each school prefers to remain out of the system when others join it. Therefore, our analysis provides an explanation of why some charter schools have evaded (or may evade) the clearinghouse. To overcome this issue, we propose two schemes that can be used by policymakers to incentivize schools to join the system, which achieves the desired integration of schools. 

3.40 P.M.  Break 
4:00 P.M.  Session 8 
Competitive Equilibrium and a Dynamic Auction for Allocation with Priorities
Authors: Isa Hafalir and Tayfun Sonmez Abstract:
We consider an assignment problem where a set of items need to be allocated to a set of agents. Agents have different priorities for claiming different items, and personalized (discrete) pricesterms of the contracts can be used in the allocation process. We allow each item having some copies are for sale and some copies for free. In this model, we first define a competitive equilibrium with personalized prices and show that there exists a strategyproof mechanism that results in the best competitive equilibrium. We then propose a Nash incentivecompatible dynamic auction that results in the same competitive equilibrium allocation. 

Competitive Equilibria with Indivisible Goods and Generic Budgets
Authors: Moshe Babaioff, Noam Nisan and Inbal TalgamCohen Abstract:
We study competitive equilibria in the basic Fisher market model, but with indivisible goods. Such equilibria fail to exist in the simplest possible market of two players with equal budgets and a single good, yet this is a knife’s edge instance as equilibria exist once budgets are not precisely equal. Is nonexistence of equilibria also a knifeedge phenomenon in complex markets with multiple goods? Our computerized search has indicated that equilibria often exist when budgets are “generic”. We prove several existence results both for the case of general preferences and for the special case of additive preferences, and relate competitive equilibria to notions of fair allocation of indivisible items. 

Object Allocation via ImmediateAcceptance: Characterizations and an Affirmative Action Application
Authors: Battal Dogan and Bettina Klaus Abstract:
Which mechanism to use to allocate school seats to students still remains a question of hot debate. Meanwhile, immediate acceptance mechanisms remain popular in many school districts. We formalize desirable properties of mechanisms when respecting the relative rank of a school among the students’ preferences is crucial. We show that those properties, together with wellknown desirable resource allocation properties, characterize immediate acceptance mechanisms. Moreover, we show that replacing one of the properties, consistency, with a weaker property, nonbossiness, leads to a characterization of a much larger class of mechanisms, which we call choicebased immediate acceptance mechanisms. It turns out that certain objectives that are not achievable with immediate acceptance mechanisms, such as affirmative action, can be achieved with a choicebased immediate acceptance mechanism. 

Fair Division of goods, bads, and satiable items
Authors: Anna Bogomolnaia, Herve Moulin, Fedor Sandomirskiy and Elena Yanovskaya Abstract:
How to divide items that can be desirable (goods), or not (bads), and can also allow satiation? When all items are goods and preferences are represented by utility functions homothetic and concave, the Competitive Equilibrium with Equal Incomes (CEEI) is famously compelling because it maximizes the Nash product of utilities, is singlevalued and easy to compute. The CEEI to divide only bads captures similarly all critical points of the Nash product in the efficient frontier. But it is far from resolute or easy to compute: the number of allocations distinct welfarewise can be exponential in the number of agents and items.General problems behave as if we divide only goods, or as if we divide only bads. In the former case, everyone who can is strictly better off than zero (the ex ante utility), the CEEI is unique and maximizes the Nash product of utilities. In the latter everyone is strictly worse off than zero, and the CEEI collects all critical points of the Nash product of disutilities. Thus the task of dividing a mixed manna is either good news for everyone, or bad news for everyone.We refine our results in the practically important case of linear preferences, where the axiomatic comparison between the division of goods and that of bads is especially sharp. When we divide goods and the manna improves, everyone weakly benefit under the CEEI rule; but no reasonable rule to divide bads can be similarly Resource Monotonic. Also, the much larger set of Non Envious and Efficient divisions of bads can be disconnected so that it will admit no continuous selection. 

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 noninvariant outcome measures and of mechanisms that elicit preference intensities.

6.15 P.M.  Closing Remarks 
6.30 P.M.  END 
Local Information
Arrival Guidance
Upon arrival to One Memorial Drive, visitors should be prepared to show a valid photo ID and sign the Building Visitor Log when approaching the Lobby Floor Security Desk. Alert them to the name of the event you are attending and ask them to direct you to the appropriate floor. Typically, the talks are located in the Conference Center on the first floor, however sometimes the location may change.
Accommodations
 Boston Marriott Cambridge (0.27 mi)
 Residence Inn Boston Cambridge (0.09 mi)
 The Kendall Hotel (0.28 mi)
 The Liberty Hotel (0.56 mi)
 Hotel Marlow (0.55 mi)
Restaurants
 Catalyst (0.7 mi)
 Commonwealth (0.3 mi)
 Abigail’s (0.5 mi)
 Cafe Arts and Sciences (0.5 mi)
 Firebrand Saints (0.3 mi)
*Hospitality Notice: Microsoft Research may provide hospitality at this event. Because different universities and legal jurisdictions have differing rules, we rely on you to know whether acceptance of this invitation would be inconsistent with those rules. Accordingly, by accepting our invitation, you confirm that this invitation is compliant with your institution’s policies.
Committees
Program Committee
 Nicole Immorlica (cochair), Microsoft Research
 Scott Kominers (cochair), Harvard
 Nikhil Agarwal, Massachusetts Institute of Technology
 Itai Ashlagi, Stanford University
 Peter Biro, Hungarian Academy of Sciences
 Yan Chen, University of Michigan
 Christine Cheng, University of WisconsinMilwaukee
 Ágnes Cseh, Hungarian Academy of Science
 Brian Dean, Clemson University
 Umut Dur, University of Texas at Austin
 Clayton Featherstone, University of Pennsylvania
 Tamas Fleiner , Budapest University of Technology and Economics
 John Hatfield, University of Texas at Austin
 Martin Hoefer, Max Planck Institut für Informatik
 ChienChung Huang, CNRS, ENS
 Onur Kesten, Carnegie Mellon University
 Fuhito Kojima, Stanford University
 Sangmok Lee, University of Pennsylvania
 Jacob Leshno, Columbia University
 Thanh Nguyen, Purdue University
 Alexandru Nichifor, University of St. Andrews
 Renato PaesLeme, Google
 Patrick Prosser, Glasgow University
 Baharak Rastegari, University of Glasgow
 Assaf Romm, Hebrew University
 Jay Sethuraman, Columbia University
 Ran Shorrer, Harvard University
 Alex Teytelboym, Oxford University
 Rob van Stee, University of Leicester
 Alexander Westkamp, Maastricht University
 M. Bumin Yenmez, Carnegie Mellon University
Steering Committee
 Péter Biró, Hungarian Academy of Sciences, Hungary
 Brian Dean, Clemson University, USA
 Bettina Klaus, University of Lausanne, Switzerland
 David Manlove, University of Glasgow, UK
Previous Workshops
The first MATCHUP was held on July 6, 2008 at Reykjavík University as a satellite workshop of ICALP 2008.
MATCHUP 2012, second in this series, was held on July 1920, 2012 at Corvinus University of Budapest.
MATCHUP 2015, the third and latest in its series, was held on April 1416, 2015 at The University of Glasgow in Scotland.
Poster Sessions
Title 
Author(s) 
Mechanism Design for MultiType Housing Markets  Sibel Adali, Sujoy Sikdar and Lirong Xia 
Integer Programming Formulations for the StudentProject Allocation Problem  Frances Cooper and David Manlove 
Matching with Quantity  David Delacretaz 
Lexicographic Choice under Variable Capacity Constraints  Battal Dogan, Kemal Yildiz and Serhat Dogan 
Spatiotemporal Pricing for Ridesharing Platforms  Fei Fang, Hongyao Ma and David C. Parkes 
Deferred Acceptance and Regretfree Truthtelling: A Characterization Result  Marcelo Ariel Fernandez 
Graphical Algorithms for the Nucleolus of BinaryValued Assignment Games  John Hardwick 
Cadetbranch matching in a KelsoCrawford economy  Ravi Jagadeesan 
Endogenous Market Formation: Theory and Evidence from Chilean College Admissions  Soohyung Lee, Ricardo Espinoza and Hector Lopez 
Prices and Efficiency in Networked Markets  Eduard Talamas 
Finalizing Tentative Matches from Truncated Preference Lists  Hisao Tamaki 
Takeitorleaveit contracts in manytomany matching markets  Matteo Triossi and Antonio RomeroMedina 