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.

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 strategy-proof and Pareto efficient assignment, but the combinatorial description of TTC makes it non-transparent 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 non-trivial 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.

We formulate a general model of two-sided 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.

In finite two-sided 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 strategy-proofness, deferred acceptance remains (group) strategy-proof in many infinite markets.

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 test-score improvements with respect to these choice functions. Moreover, we show that some distributional objectives that can be achieved by capacity-transfers cannot be achieved by slot-specific priorities.

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 polynomial-time algorithms for computing a “Pareto-stable” 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 polynomial-time Pareto-stable algorithms for stable marriage and college admissions that correspond to strategyproof mechanisms. For stable marriage, it is known that no Pareto-stable 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 Pareto-stable mechanism can be strategyproof for the colleges; our algorithm provides a mechanism that is strategyproof for the students.

We investigate first choice-maximality (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 choice-stability (FCS) (i.e., no student forms a blocking pair with her first choice) to be the strongest rank-based 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 self-select 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.

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.

An important desideratum in priority-based 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 trade-off. 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 non-vacuous 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 non-experts 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.

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;
   1. Increasing deceased donation: military share, priority in Israel

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 follow-up, 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.

We study markets in which each agent is endowed with multiple units of an indivisible and agent-specific 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, Pareto-efficiency, and strategy-proofness. 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 Pareto-efficient 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 strategy-proof.

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 strategy-proof mechanism that is constrained efficient, i.e. that always produces an agent-optimal 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 four-way 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 strategy-proof and constrained ecient mechanism.

We consider a general model of resource allocation with unit-demand agents, each of whom have an outside option of privately known value. The model encompasses (priority-based) 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 strategy-proof allocation rule must weakly Pareto-dominate an individually rational and participation-maximal 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 strategy-proof rules.

We relate strategy-proof 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.

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.

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 Gale-Shapley 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 “socially-optimal assortment planning” problem, and show that it is a generalization of the revenue-maximizing assortment planning problem studied in the revenue management literature. We give efficient algorithms for the socially-optimal 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.

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.

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.

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.

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.

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 trail-stable 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. Trail-stable 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 trail-stable outcomes, we prove results on the lattice structure, the rural hospitals theorem, strategy-proofness and comparative statics of firm entry and exit. We pin down a condition under which trail-stable and fully trail-stable 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) trail-stable.

We study stable outcomes in a one-to-one matching market with firms and workers. The model endogenizes how transferable utility is within a match: when a firm-worker pair is matched, they play an infinite-horizon discounted dynamic game with one-sided, 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 lower-type 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.

We study mediated many-to-many 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 straight-forward 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.

We study the amount of communication needed to find a stable matching in a two-sided matching market with private preferences when agents have some knowledge of the preference distribution. We show that in a two-sided market with workers and firms, when the preferences of workers are arbitrary and private and the preferences of firms follow a multinomial-logit (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.

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 NP-hard 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 polynomial-time 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.

We study the stable matching problem in non-bipartite 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 NP-hard 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 polynomial-time 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 2-approximation 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.

Stable flows generalize the well-known 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 augmenting-path algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocation as a black-box 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 graph-based reductions that show that it is without loss of generality to assume that no commodity-specific preference lists at the vertices and no commodity-specific capacities on the edges exist. We further show that it is NP-complete to decide whether an integral solution exists.

In this paper we study a two-sided 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 NP-hard, 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 polynomial-time solvable if only one side can have cyclic preferences and the other side has transitive preferences, but that this problem becomes NP-hard 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.

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.

We present direct field evidence of preference misrepresentation under deferred acceptance. A large fraction of highly educated participants, who had been informed about the strategy-proof nature of the mechanism in numerous ways, failed to play truthfully: they ranked a non-funded position above a funded position in the same program. This is despite being informed that rank-ordered 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.

Many two-sided matching markets, from labor markets to school choice programs, use a clearinghouse based on the applicant-proposing deferred acceptance algorithm, which is well known to be strategy-proof 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 strategy-proof for any side of the market, a stronger incentive property than strategy-proofness introduced by Li (2015). A stable mechanism that is obviously strategy-proof for applicants is introduced for the case in which agents on the other side have acyclical preferences. Our findings suggest that strategic reasoning in two-sided markets requires more cognitive effort by participants than in one-sided markets.

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 (Gale-Shapley) man-optimal, which we prove yields the woman-optimal 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 egalitarian-optimal 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.

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.

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.

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 strategy-proof mechanism that results in the best competitive equilibrium. We then propose a Nash incentive-compatible dynamic auction that results in the same competitive equilibrium allocation.

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 non-existence of equilibria also a knife-edge 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.

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 well-known desirable resource allocation properties, characterize immediate acceptance mechanisms. Moreover, we show that replacing one of the properties, consistency, with a weaker property, non-bossiness, leads to a characterization of a much larger class of mechanisms, which we call choice-based 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 choice-based immediate acceptance mechanism.

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 single-valued 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 welfare-wise 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.

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.