Characterizing General Top Trading Cycles Mechanisms

In many applied matching problems, indivisible goods that are in unit demand have to be assigned without monetary transfers. One of the most prominent such problems is modeled by classical Shapley-Scarf housing markets (Shapley and Scarf, 1974). Shapley and Scarf (1974) consider an exchange economy in which each agent owns an indivisible object (say, a house); each agent has preferences over houses and wishes to consume exactly one house. The objective of the market designer then is to reallocate houses among agents. When preferences are strict, Shapley and Scarf (1974) show that the strict core (defined by a weak blocking notion) has remarkable features: it is non-empty, and can be easily calculated by the so-called top-trading-cycles (TTC) algorithm (due to David Gale). Moreover, the TTC mechanism that assigns the unique strict core allocation satisfies important incentive properties, strategy-proofness (Roth, 1982) as well as the stronger property of group strategy-proofness (Bird, 1984). Furthermore, Ma (1994) and Svensson (1999) show that the TTC mechanism is the unique mechanism satisfying Pareto efficiency, individual rationality, and strategy-proofness.

After giving a short survey over the wonderful properties the top-trading cycles mechanism has, I’ll consider an extension of Shapley-Scarf housing markets to object allocation problems with coalitional endowments (housing markets with existing tenants are an example). For this relatively new class of problems, I present recent results obtained together with Di Feng during our current stay at the Simons Laufer Mathematical Sciences Institute (formerly MSRI). Our main result is the characterization of sequential priorities-augmented top trading cycles mechanisms.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.