Top Trading Cycles

The paper studies two games of capacity manipulation in hospital-intern markets. The focus is on the stability of Nash equilibrium outcomes. We provide minimal necessary and sufficient conditions guaranteeing the existence of pure strategy Nash Equilibria and the stability of outcomes.

The paper studies two games of capacity manipulation in hospital-intern markets. The focus is on the stability of Nash equilibrium outcomes. We provide minimal necessary and sufficient conditions guaranteeing the existence of pure strategy Nash Equilibria and the stability of outcomes.

BY SZILVIA PAPAI 1 give a characterization of the set of group-strategyproof, Pareto-optimal, and reallocation-proof allocation rules for the assignment problem, where individuals are assigned at most one indivisible object, without any medium of exchange. Although there are no property rights in the model, the rules satisfying the above criteria imitate a trading procedure with individual endowments, in which individuals exchange objects from their hierarchically determined endowment sets in an iterative manner. In particular, these assignment rules generalize Gale's top trading cycle procedure, the classical rule for the model in which each individual owns an indivisible good.

We consider three popular affirmative action policies in school choice: quota-based, priority-based, and reserve-based affirmative actions. The Boston mechanism (BM) is responsive to the latter two policies in that a stronger priority-based or reserve-based affirmative action makes some minority student better off. However, a stronger quotabased affirmative action may yield a Pareto inferior outcome for the minority under the BM . These positive results disappear once we look for a stronger welfare consequence on the minority or focus on BM equilibrium outcomes.

How should students be assigned to schools? Two mechanisms have been suggested and implemented around the world: deferred acceptance (DA) and top trading cycles (TTC). These two mechanisms are widely considered excellent choices owing to their outstanding stability and incentive properties. We show theoretically and empirically that both mechanisms perform poorly with regard to two key desiderata such as efficiency and equality, even in large markets. In contrast, the rank-minimizing mechanism is significantly more efficient and egalitarian. It is also Pareto optimal for the students, unlike DA, and generates less justified envy than TTC.

We study the welfare effects of school district consolidation, i.e. the integration of disjoint school districts into a centralised clearinghouse. We show theoretically that, in the worst-case scenario, district consolidation may unambiguously reduce students' welfare, even if the student-optimal stable matching is consistently chosen. However, on average all students experience expected welfare gains from district consolidation, particularly those who belong to smaller and over-demanded districts. Using data from the Hungarian secondary school assignment mechanism, we compute the actual welfare gains from district consolidation in Budapest and compare these to our theoretical predictions. We empirically document substantial welfare gains from district consolidation for students, equivalent to attending a school five kilometres closer to the students' home addresses. As an important building block of our empirical strategy, we describe a method to consistently estimate students' preferences over schools and vice versa that does not fully assume that students report their preferences truthfully in the student-proposing deferred acceptance algorithm.

We study school choice markets where the non-strategy-proof Boston mechanism is used to assign students to schools. Inspired by previous field and experimental evidence, we analyze a type of behavior called priority-driven: students have a common ranking over the schools and then give a bonus in their submitted preferences to those schools for which they have high priority. We first prove that under this behavior, there is a unique stable and efficient matching, which is the outcome of the Boston mechanism. Second, we show that the three most prominent mechanisms on school choice (Boston, deferred acceptance, and top trading cycles) coincide when students' submitted preferences are priority-driven. Finally, we run some computational simulations to show that the assumption of priority-driven preferences can be relaxed by introducing an idiosyncratic preference component, and our qualitative results carry over to a more general model of preferences.

We explore the possibility of designing matching mechanisms that can accommodate non-standard choice behavior. We pin down the necessary and sufficient conditions on participants' choice behavior for the existence of stable and incentive compatible mechanisms. Our results imply that well-functioning matching markets can be designed to adequately accommodate a plethora of choice behaviors, including the standard behavior that is consistent with preference maximization. To illustrate the significance of our results in practice, we show that a simple modification in a commonly used matching mechanism enables it to accommodate non-standard choice behavior.

* We wish to thank Teodosia del Castillo, Pablo Revilla and Antonio Romero-Medina for their comments. This work is partially supported by the IVIE. Alcalde acknowledges support by FEDER and the Spanish Ministerio de Educación y Ciencia under project SEJ2007-62656/ECON.

An (f, g)-semi-matching in a bipartite graph G = (U ∪ V, E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f (u) edges of M , and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f, g)-semi-matching in running time O(m • min{ u∈U f (u), v∈V g(v)}). Using the reduction of [5] our result on maximum (f, g)-semi-matching problem directly implies an algorithm for the optimal semi-matching problem with running time O(√ nm log n).

This short paper gives a detailed proof of identity between two classic formulas for the computation of the exact Miss Rate of LRU caches. An extension to the identity of two formulas of the expected time of a partial collection in the coupon collector problem is also presented.

A classic trade-off that school districts face when deciding which matching algorithm to use is that it is not possible to always respect both priorities and preferences. The student-proposing deferred acceptance algorithm (DA) respects priorities but can lead to inefficient allocations. The top trading cycle algorithm (TTC) respects preferences but may violate priorities. We identify a new condition on school choice markets under which DA is efficient and there is a unique allocation that respects priorities. Our condition generalizes earlier conditions by placing restrictions on how preferences and priorities relate to one another only on the parts that are relevant for the assignment. We discuss how our condition sheds light on existing empirical findings. We show through simulations that our condition significantly expands the range of known environments for which DA is efficient.

We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted $\mathcal{R}_1$ and $\mathcal{R}_2$. In round $\mathcal{R}_1$, the capacity of each school is fixed and mechanism $\mathcal{M}_1$ finds a student optimal stable matching. In round $\mathcal{R}_2$, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations. It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results, the first simply disallows any re-allocations in round $\mathcal{R}_2$, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable ma...

In this paper, we analyze capacity manipulation games in hospital-intern markets inspired by the real-life entry-level labor markets for young physicians who seek residencies at hospitals. In a hospital-intern market, the matching is determined by a centralized clearinghouse using the preferences revealed by interns and hospitals and the number of vacant positions revealed by hospitals. We consider a model in which preferences of hospitals and interns are common knowledge. Hospitals play a capacity-reporting game. We analyze the equilibria of the game-form under the two most widely used matching rules: hospital-optimal and intern-optimal stable rules. We show that (i) there may not be a pure strategy equilibrium in general; and (ii) when a pure strategy equilibrium exists, every hospital weakly prefers this equilibrium outcome to the outcome of any larger capacity proÞle. Finally, we present conditions on preferences to guarantee the existence of pure strategy equilibria. JEL ClassiÞcation Numbers: C72, C78, I11, J44 * We would like to thank Alvin Roth, Tayfun Sönmez, an associate editor and three anonymous referees of the journal for their helpful comments and suggestions which signiÞcantly improved the paper.

The Blocking Lemma identifies a particular blocking pair for each non-stable and individually rational matching that is preferred by some agents of one side of the market to their optimal stable matching. Its interest lies in the fact that it has been an instrumental result to prove key results on matching. For instance, the fact that in the college admissions problem the workers-optimal stable mechanism is group strategy-proof for the workers and the strong stability theorem in the marriage model follow directly from the Blocking Lemma. However, it is known that the Blocking Lemma and its consequences do not hold in the general many-to-one matching model in which firms have substitutable preference relations. We show that the Blocking Lemma holds for the many-to-one matching model in which firms' preference relations are, in addition to substitutable, quota q-separable. We also show that the Blocking Lemma holds on a subset of substitutable preference profiles if and only if the workers-optimal stable mechanism is group strategy-proof for the workers on this subset of profiles.

We present an experimental study where we analyze three wellknown matching mechanisms-the Boston, the Gale-Shapley, and the Top Trading Cycles mechanisms-in three di¤erent informational settings. Our experimental results are consistent with the theory, suggesting that the TTC mechanism outperforms both the Boston and the Gale-Shapley mechanisms in terms of e¢ ciency and it is as successful as the Gale-Shapley mechanism regarding the proportion of truthful preference revelation, whereas manipulation is stronger under the Boston mechanism. In addition, even though agents are much more likely to revert to truthtelling in lack of information about the others' payo¤s-ignorance may be bene…cial in this context-, the TTC mechanism results less sensitive to the amount of information that participants hold. These results therefore suggest that the use of the TTC mechanism in practice is more desirable than of the others.

We experimentally investigate in the laboratory two prominent mechanisms that are employed in school choice programs to assign students to public schools. We study how individual behavior is influenced by preference intensities and risk aversion. Our main results show that (a) the Gale-Shapley mechanism is more robust to changes in cardinal preferences than the Boston mechanism independently of whether individuals can submit a complete or only a restricted ranking of the schools and (b) subjects with a higher degree of risk aversion are more likely to play "safer" strategies under the Gale-Shapley but not under the Boston mechanism. Both results have important implications for the efficiency and the stability of the mechanisms.

We analyze two well-known matching mechanisms-the Gale-Shapley, and the Top Trading Cycles (TTC) mechanisms-in the experimental lab in three different informational settings, and study the role of information in individual decision making. Our results suggest that-in line with the theory-in the college admissions model the Gale-Shapley mechanism outperforms the TTC mechanisms in terms of efficiency and stability, and it is as successful as the TTC mechanism regarding the proportion of truthful preference revelation. In addition, we find that information has an important effect on truthful behavior and stability. Nevertheless, regarding efficiency, the Gale-Shapley mechanism is less sensitive to the amount of information participants hold.

In many-to-one matching with contracts, agents on one side of the market, e.g., workers, can ful ll at most one contract, while agents on the other side of the market, e.g., rms, may desire multiple contracts. Hat eld and Milgrom [6] showed that when rms' preferences are substitutable and size monotonic, the worker-proposing cumulative o er mechanism is stable and strategy-proof (for workers). 1 Recently, stable and strategy-proof matching has been shown to be possible in a number of real-world se ings in which preferences are not necessarily substitutable (see, e.g., Sönmez and Switzer [13], Sönmez [12], Kamada and Kojima [7], and Aygün and Turhan [1]); this has motivated a search for weakened substitutability conditions that guarantee the existence of stable and strategy-proof mechanisms. Hat eld and Kojima [3] introduced unilateral substitutability and showed that when all rms' preferences are unilaterally substitutable (and size monotonic), the cumulative o er mechanism is stable and strategy-proof. Kominers and Sönmez [9] identi ed a novel class of preferences, called slot-speci c priorities, and showed that if each rm's preferences are in this class, then the cumulative o er mechanism is again stable and strategy-proof. Subsequently, Hat eld and Kominers [4] developed a concept of substitutable completion and showed that when each rm's preferences admit a size monotonic substitutable completion, the cumulative o er mechanism is once more stable and strategy-proof. In this paper, we introduce three novel conditions-observable substitutability, observable size monotonicity, and non-manipulability via contractual terms-and show that when these conditions are satis ed, the cumulative o er mechanism is the unique mechanism that is stable and strategy-proof. Moreover, when the choice function of any rm fails one of our three conditions, we can construct unit-demand choice functions for the other rms such that no stable and strategy-proof mechanism exists.

We study the effect of different school choice mechanisms on schools' incentives for quality improvement. To do so, we introduce the following criterion: A mechanism respects improvements of school quality if each school becomes weakly better off whenever that school becomes more preferred by students. We first show that no stable mechanism, or mechanism that is Pareto efficient for students (such as the Boston and top trading cycles mechanisms), respects improvements of school quality. Nevertheless, for large school districts, we demonstrate that any stable mechanism approximately respects improvements of school quality; by contrast, the Boston and top trading cycles mechanisms fail to do so. Thus a stable mechanism may provide better incentives for schools to improve themselves than the Boston and top trading cycles mechanisms.

We run a field experiment to test the truth-telling rates of the theoretically strategy-proof Top Trading Cycles mechanism (TTC) under different information conditions. First, we asked first-year economics students enrolled in an introductory microeconomics unit about which topic, among three, they would most like to write an essay on. Most students chose the same favorite topic. Then we used TTC to distribute students equally across the three options. We ran three treatments varying the information the students received about the mechanism. In the first treatment students were given a description of the matching mechanism. In the second they received a description of the strategy-proofness property without details of the mechanism. Finally, in the third, they were given both pieces of information. We find a significant and positive effect of describing the strategy-proofness on truth-telling rates. On the other hand, describing the matching mechanism has a negative effect on truth-telling.  We thank three anonymous referees and Dorothea Kübler for their valuable comments. We are grateful to Jennifer Rontganger for copy editing.

We approach the roommate problem by focusing on well-behaved matchings, which are those individually rational matchings whose blocking pairs, if any, are formed with unmatched agents. We show that the set of stable matchings is non-empty if and only if no well-behaved and unstable matching is Pareto optimal among all well-behaved matchings. The economic intuition underlying this condition is that blocking can be done so that the transactions at any well-behaved and unstable matching need not be undone as agents reach the the set of stable matchings. We also give a sufficient condition on the preferences of the agents for the non-emptiness of the set of stable matchings. New properties of economic interest are proved

Gale and Shapley showed in their well known paper of 1962 (Amer. Math. Monthly 69, 9-14) that stable matchings always exist for the marriage market. Their proof was constructed by means of an algorithm. Except for the existence of stable matchings, all the results for the marriage market which were proved by making use of the Gale and Shapley algorithm could also be proved without the algorithm. The purpose of this note is to fill out this case. We present here a nonconstructive proof of the existence of a stable matching for the marriage market, which is quite short and simple and applies directly to both cases of preferences: strict and nonstrict.

Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public.

We give parallel and distributed algorithms for the housing allocation problem. In this problem, there is a set of agents and a set of houses. Each agent has a strict preference list for a subset of houses. We need to find a matching such that some criterion is optimized. One such criterion is Pareto Optimality. A matching is Pareto optimal if no coalition of agents can be strictly better off by exchanging houses among themselves. We also study the housing market problem, a variant of the housing allocation problem, where each agent initially owns a house. In addition to Pareto optimality, we are also interested in finding the core of a housing market. A matching is in the core if there is no coalition of agents that can be better off by breaking away from other agents and switching houses only among themselves. In the first part of this work, we show that computing a Pareto optimal matching of a house allocation is in {\bf CC} and computing the core of a housing market is {\bf CC}-...

Centralized school admission mechanisms are an attractive way of improving social welfare and fairness in large educational systems. In this paper we report the design and implementation of the newly established school choice mechanism in Chile, where over 274,000 students applied to more than 6,400 schools. The Chilean system presents unprecedented design challenges that make it unique. On the one hand, it is a simultaneous nationwide system, making it one of the largest school admission problems worldwide. On the other hand, the system runs at all school levels, from Pre-K to 12th grade, raising at least two issues of outmost importance; namely, the system needs to guarantee their current seat to students applying for a school change, and the system has to favor the assignment of siblings to the same school. As in other systems around the world, we develop a model based on the celebrated Deferred Acceptance algorithm. The algorithm deals not only with the aforementioned issues, but also with further practical features such as soft-bounds and overlapping types. In this context we analyze new stability definitions, present the results of its implementation and conduct simulations showing the benefits of the innovations of the implemented system. CCS Concepts: • Theory of computation → Algorithmic mechanism design; • Applied computing → Economics.

Centralized school admission mechanisms are an attractive way of improving social welfare and fairness in large educational systems. In this paper we report the design and implementation of the newly established school choice mechanism in Chile, where over 274,000 students applied to more than 6,400 schools. The Chilean system presents unprecedented design challenges that make it unique. On the one hand, it is a simultaneous nationwide system, making it one of the largest school admission problems worldwide. On the other hand, the system runs at all school levels, from Pre-K to 12th grade, raising at least two issues of outmost importance; namely, the system needs to guarantee their current seat to students applying for a school change, and the system has to favor the assignment of siblings to the same school. As in other systems around the world, we develop a model based on the celebrated Deferred Acceptance algorithm. The algorithm deals not only with the aforementioned issues, but also with further practical features such as soft-bounds and overlapping types. In this context we analyze new stability definitions, present the results of its implementation and conduct simulations showing the benefits of the innovations of the implemented system. CCS Concepts: • Theory of computation → Algorithmic mechanism design; • Applied computing → Economics.

We study problems of allocating objects among people. Some objects may be initially owned and the rest are unowned. Each person needs exactly one object and initially owns at most one object. We drop the common assumption of strict preferences. Without this assumption, it suffices to study problems where each person initially owns an object and every object is owned. For such problems, when preferences are strict, the "top trading cycles" algorithm provides the only rule that is efficient, strategy-proof, and individually rational [1]. Our contribution is to generalize this algorithm to accommodate indifference without compromising on efficiency and incentives.

We study many-to-one matching markets where hospitals have responsive preferences over students. We study the game induced by the student-optimal stable matching mechanism. We assume that students play their weakly dominant strategy of truth-telling. Roth and Sotomayor (1990) showed that equilibrium outcomes can be unstable. We prove that any stable matching is obtained in some equilibrium. We also show that the exhaustive class of dropping strategies does not necessarily generate the full set of equilibrium outcomes. Finally, we find that the 'rural hospital theorem' cannot be extended to the set of equilibrium outcomes and that welfare levels are in general unrelated to the set of stable matchings. Two important consequences are that, contrary to one-to-one matching markets, (a) filled positions depend on the equilibrium that is reached and (b) welfare levels are not bounded by the optimal stable matchings (with respect to the true preferences).

We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted $\mathcal{R}_1$ and $\mathcal{R}_2$. In round $\mathcal{R}_1$, the capacity of each school is fixed and mechanism $\mathcal{M}_1$ finds a student optimal stable matching. In round $\mathcal{R}_2$, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations. It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results, the first simply disallows any re-allocations in round $\mathcal{R}_2$, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable ma...

V acation Timeshare is a form of ownership or "right to use" of a resort property for a specific time period (typically a week) each year. Timeshare exchange refers to the non-monetary trading of timeshare weeks among owners, so that they can interchange their vacation homes to experience new destinations. The need for member participation during the exchange process has been well-recognized for a variety of practical reasons, including the reluctance of members to accept an authoritarian solution that does not provide any information about the exchange process and their desire to experience some control over the process. Another important need is to ensure that, given the members' preferences, an exchange solution offers collectively the best-possible improvement over their currently-owned weeks, while being "fair" to all participants. We suggest two objectives to capture the efficiency and fairness of an exchange solution. For the resulting bi-criteria problem, we show that a solution that is simultaneously near-optimal on both objectives may not exist. Our main contribution is an efficient algorithm in which (i) each member uses her private preference list to communicate with other members, and the members, through such communications, collectively achieve an individually rational allocation, and (ii) for any desired approximation bounds a and b on, respectively, efficiency and fairness, the following property holds: if an (a, b)approximate solution exists, then the solution provided by the algorithm satisfies this approximation guarantee; otherwise, the solution is an a-approximation on the efficiency measure and, among all such allocations, has the best fairness measure.

It is well known that the core of an exchange market with indivisible goods is always non empty, although it may contain Pareto inefficient allocations. The strict core solves this shortcoming when indifferences are not allowed, but when agents' preferences are weak orders the strict core may be empty. On the other hand, when indifferences are allowed, the core or the strict core may fail to be stable sets, in the von Neumann and Morgenstern sense.We introduce a new solution concept that improves the behaviour of the strict core, in the sense that it solves the emptiness problem of the strict core when indifferences are allowed in the individuals' preferences and whenever the strict core is non-empty, our solution is included in it. We define our proposal, the MS-set, by using a stability property (m-stability) that the strict core fulfills. Finally, we provide a min-max interpretation for this new solution.

We study the house allocation with existing tenants model (Abdulkadiroglu and Sönmez, 1999) and consider rules that allocate houses based on priorities. We introduce a new acyclicity requirement and show that for house allocation with existing tenants a top trading cycles (TTC) rule is consistent if and only if its underlying priority structure satisfies our acyclicity condition. Next we give an alternative description of TTC rules based on ownership-adapted acyclic priorities in terms of two specific rules, YRMH-IGYT (you request my house-I get your turn) and efficient priority rules, that are applied in two steps. Moreover, even if no priority structure is a priori given, we show that a rule is a top trading cycles rule based on ownership-adapted acyclic priorities if and only if it satisfies Pareto-optimality, individual-rationality, strategyproofness, consistency, and either reallocation-proofness or non-bossiness.

We consider three popular affirmative action policies in school choice: quota-based, priority-based, and reserve-based affirmative actions. The Boston mechanism (BM) is responsive to the latter two policies in that a stronger priority-based or reserve-based affirmative action makes some minority student better off. However, a stronger quotabased affirmative action may yield a Pareto inferior outcome for the minority under the BM . These positive results disappear once we look for a stronger welfare consequence on the minority or focus on BM equilibrium outcomes.

School districts that implement stable matchings face various decisions that affect students' assignments to schools. We study the properties of the rank distribution of students with random preferences when schools use different tie-breaking rules to rank equivalent students. Under a single tie-breaking rule, where all schools use the same ranking, a constant fraction of students are assigned to one of their top choices. In contrast, under a multiple tie-breaking rule, where each school independently ranks students, a vanishing fraction of students are matched with one of their top choices. However, if students are allowed to submit only relatively short preference lists under a multiple tie-breaking rule, a constant fraction of students will be matched with one of their top choices, while only a "small" fraction of students will remain unmatched.

Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence.

We present an experimental study of three school choice mechanisms. The Boston mechanism is influential in practice, while the two alternative mechanisms, the Gale-Shapley and Top Trading Cycles mechanisms, have superior theoretical properties in terms of incentives and efficiency. Consistent with theory, this study indicates a high preference manipulation rate under the Boston mechanism. As a result, efficiency under Boston is significantly lower than that of the two competing mechanisms in the designed environment. However, contrary to theory, Gale-Shapley outperforms the Top Trading Cycles mechanism and generates the highest efficiency. Our results suggest that replacing the Boston mechanism with the Gale-Shapley mechanism in practice might significantly improve efficiency.

* We wish to thank Teodosia del Castillo, Pablo Revilla and Antonio Romero-Medina for their comments. This work is partially supported by the IVIE. Alcalde acknowledges support by FEDER and the Spanish Ministerio de Educación y Ciencia under project SEJ2007-62656/ECON.

Despite its widespread use, the Boston mechanism has been criticized for its poor incentive and welfare performances compared to the Gale-Shapley deferred acceptance algorithm (DA). By contrast, when students have the same ordinal preferences and schools have no priorities, we find that the Boston mechanism Pareto dominates the DA in ex ante welfare, that it may not harm but rather benefit participants who may not strategize well, and that, in the presence of school priorities, the Boston mechanism also tends to facilitate greater access than the DA to good schools for those lacking priorities at those schools. (JEL D82, I21, I28)

The literature on school choice assumes that families can submit a preference list over all the schools they want to be assigned to. However, in many real-life instances families are only allowed to submit a list containing a limited number of schools. Subjects' incentives are drastically affected, as more individuals manipulate their preferences. Including a safety school in the constrained list explains most manipulations. Competitiveness across schools plays an important role. Constraining choices increases segregation and affects the stability and efficiency of the final allocation. Remarkably, the constraint reduces significantly the proportion of subjects playing a dominated strategy (JEL D82, I21)

We show that one of the main results in Chen and Sönmez (2006, 2008) does no longer hold when the number of recombinations is sufficiently increased to obtain reliable conclusions. No school choice mechanism is significantly superior in terms of efficiency.

We consider matching markets at a senior level, where workers are assigned to firms at an unstable matching-the status-quo-which might not be Pareto efficient. It might also be that none of the matchings Pareto superior to the status-quo are Core stable. We propose two weakenings of Core stability: status-quo stability and weakened stability, and the respective mechanisms which lead any status-quo to matchings meeting the stability requirements above mentioned. The first one is inspired by the Top trading cycle and Deferred Acceptance procedures, the other one belongs to the family of Branch and Bound algorithms. The last procedure finds a core stable matching in many-to-one markets whenever it exists, dispensing with the assumption of substitutability.

In this paper we propose a new family of matchingsas solution for the roommate problem with strict preferences, when stable matchings may not exist. To define these matchings we proceed as follows: We introduce the solution of maximum irreversibility, a strong notion of stability, and consider two other existing solutions that deal with unsolvable roommate problems: the almost stable matchings (Abraham et al. [2]) and the maximum stable matchings (Tan [31] [33]). Although each of these core consistent solutions is a good candidate for solving roommate problems, we find that it is not possible to reconcile almost stability with any of the other two. Hence we select the family of matchings, the Q-stable family, that lie in the intersection of the maximum irreversible matchings and maximum stable matchings. Then we offer an efficient algorithm to compute a member of this family: a Q∗-stable matching. ∗This research is supported by the Spanish Ministry of Science and Innovation (ECO2010...