# Generalizing Top Trading Cycles

for Housing Markets with Fractional Endowments

###### Abstract

The housing market setting constitutes a fundamental model of exchange economies of goods. In most of the work concerning housing markets, it is assumed that agents own and are allocated discrete houses. The drawback of this assumption is that it does not cater for randomized assignments or allocation of time-shares. Recently, house allocation with fractional endowment of houses was considered by Athanassoglou and Sethuraman (2011) who posed the open problem of generalizing Gale’s Top Trading Cycles (TTC) algorithm to the case of housing markets with fractional endowments. In this paper, we address the problem and present a generalization of TTC called FTTC that is polynomial-time as well as core stable and Pareto optimal with respect to stochastic dominance even if there are indifferences in the preferences. We prove that if each agent owns one discrete house, FTTC coincides with a state of the art strategyproof mechanism for housing markets with discrete endowments and weak preferences.

We show that FTTC satisfies a maximal set of desirable properties by proving two impossibility theorems. Firstly, we prove that with respect to stochastic dominance, core stability and no justified envy are incompatible. Secondly, we prove that there exists no individual rational, Pareto optimal and weak strategyproof mechanism, thereby answering another open problem posed by Athanassoglou and Sethuraman (2011). The second impossibility implies a number of results in the literature.

###### keywords:

House allocation, Housing markets, Core, Top Trading Cycles,*JEL*: C62, C63, and C78

## 1 Introduction

The housing market is a fundamental model of exchange economy of goods. It been used to model online barter markets and nation-wide kidney markets (Roth et al., 2007; Sönmez and Ünver, 2011).
The housing market (also called the *Shapley-Scarf* market)
consists of a set of agents each of whom owns a house and has preferences over the set of houses. The goal is to redistribute the houses among the agents in an efficient and stable manner.
The desirable properties include the following ones: *Pareto optimality* (there exists no other assignment which each agent weakly prefers and at least one agent strictly prefers); *individual rationality* (the resultant allocation is at least as preferred by each agent as his endowment); and *core stability* (there exists no subset of agents who could have redistributed their endowments among themselves so as to get a more preferred outcome than the resultant assignment).

Shapley and Scarf (1974) showed that for housing markets with strict preferences, an elegant mechanism called *Gale’s Top Trading Cycles (TTC)* (that is based on multi-way exchanges of houses between agents) is strategyproof and finds an allocation that is in the core (Shapley and Scarf, 1974; Ma, 1994).^{1}^{1}1The seminal paper of Shapley and Scarf (1974) was referenced prominently in the scientific background document of the *2012 Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel* given to Lloyd Shapley and Alvin Roth. Along with the Deferred Acceptance Algorithm, TTC has provided the foundations for many of the developments in matching market design (Manlove, 2013; Sönmez and Ünver, 2011). The Shapley-Scarf market has been used to model important real-world problems for allocation of human organs and seats at public schools.
Since the formalization of TTC, considerable work has been done to extend and generalize TTC for more general domains that allow indifference in preferences (Alcalde-Unzu and Molis, 2011; Jaramillo and Manjunath, 2012; Aziz and de Keijzer, 2012; Plaxton, 2013; Saban and Sethuraman, 2013) or multiple units in endowment (Fujita et al., 2015; Konishi et al., 2001; Sonoda et al., 2014; Todo et al., 2014).