This paper considers a decentralized process in many-to-many matching problems. We show that if agents on one side of the market have substitutable preferences and those on the other side have responsive preferences, then, from an arbitrary matching, there exists a finite path of matchings such...

We study the problem of dissolving an equal-entitlement partnership when the objective is to minimize maximum regret. We initially focus on the family of linear-pricing mechanisms and derive regret-optimizing strategies. We also demonstrate that there exist linear-pricing mechanisms satisfying...

In this paper, we consider two-sided, many-to-one matching problems where agents in one side of the market (schools) impose some distributional constraints (e.g., a maximum quota for a set of schools), and develop a strategyproof mechanism that can handle a very general class of distributional...

Assume it is known that one player in a 2 x 2 game can detect the strategy choice of its opponent with some probability before play commences. We formulate conditions under which the detector can, by credibly committing to a strategy of probabilistic tit-for-tat (based on its imperfect...

Many procedures have been suggested for the venerable problem of dividing a set of indivisible items between two players. We propose a new algorithm (AL), related to one proposed by Brams and Taylor (BT), which requires only that the players strictly rank items from best to worst. Unlike BT, in...

A number of labor markets and student placement systems can be modeled as many-to-one matching markets. We analyze the scope for manipulation in many-to-one matching markets under the student-optimal stable mechanism when the number of participants is large. Under some regularity conditions, we...

Randomization is commonplace in everyday resource allocation. We generalize the theory of randomized assignment to accommodate multi-unit allocations and various real-world constraints, such as group-specific quotas ("controlled choice") in school choice and house allocation, and scheduling and...

The Boston mechanism is a popular student-placement mechanism in school-choice programs around the world. We provide two characterizations of the Boston mechanism. We introduce a new axiom, respect of preference rankings. A mechanism is the Boston mechanism for some priority if and only if it...

Hatfield and Milgrom (2005) present a unified model of matching with contracts phrased in terms of hospitals and doctors, which subsumes the standard two-sided matching and some package auction models. They show that a stable allocation exists if contracts are substitutes for each hospital. They...