  This paper focuses on the problem of fairly and efficiently allocating
resources to agents. We consider a specific setting, usually referred to as a
housing market, where each agent must receive exactly one resource (and
initially owns one). In this framework, in the domain of linear preferences,
the Top Trading Cycle (TTC) algorithm is the only procedure satisfying
Pareto-optimality, individual rationality and strategy-proofness. Under the
restriction of single-peaked preferences, Crawler enjoys the same properties.
These two centralized procedures might however involve long trading cycles. In
this paper we focus instead on procedures involving the shortest cycles:
bilateral swap-deals. In such swap dynamics, the agents perform pairwise
mutually improving deals until reaching a swap-stable allocation (no improving
swap-deal is possible). We prove that in the single-peaked domain every
swap-stable allocation is Pareto-optimal, showing the efficiency of the swap
dynamics. In fact, this domain turns out to be maximal when it comes to
guaranteeing this property. Besides, both the outcome of TTC and Crawler can
always be reached by sequences of swaps. However, some Pareto-optimal
allocations are not reachable through improving swap-deals. We further analyze
the outcome of swap dynamics through social welfare notions, in our context the
average or minimum rank of the resources obtained by agents in the final
allocation. We start by providing a worst-case analysis of these procedures.
Finally, we present an extensive experimental study in which different versions
of swap dynamics are compared to other existing allocation procedures. We show
that they exhibit good results on average in this domain, under different
cultures for generating synthetic data.
