Inverting Top Trading Cycles: Characterizing the Endowments that Implement a Pareto-Optimal Allocation

Abstract

In one-sided matching with strict ordinal preferences, the Top Trading Cycles (TTC) mechanism maps every initial endowment to a Pareto-optimal (PO) allocation, and many distinct endowments converge to the same outcome. We study the \emph{inverse} problem: given a PO allocation $\sigma$, characterize and enumerate its preimage $f^{-1}(\sigma )$, the set of endowments from which TTC produces $\sigma$. We characterize $f^{-1}(\sigma )$ via ordered partitions of the agents and present a sound and complete enumeration algorithm, invTTC. The preimage carries direct economic meaning: $|f^{-1}(\sigma )|/n!$ equals the probability that random serial dictatorship selects $\sigma$, and $f^{-1}(\sigma )$ is the basin of attraction of $\sigma$, quantifying robustness to the assignment of initial property rights. We analyze the enumeration's complexity and report experiments on preimage structure.

arXiv commentAccepted at PRIMA 2026 (https://www.prima2026.org/)