Generalized Top Trading Cycles: An Iterative Approach for Exchange Economies With Money

Abstract

Exchange economies for indivisible items and with initial ownership typically require the absence of money when agents interact. By excluding money, the previously proposed models ignore a rich class of problems with broad practical applicability. I therefore present an exchange economy model with indivisibilities, initial ownership, and money. I focus on constructing a mechanism that does not run a deficit and that guarantees at least a constant approximation of welfare, properties that the previous and well-known Vickrey-Clarke-Groves (VCG) and top trading cycles (TTC) mechanisms, respectively, do not satisfy. By extending the well-known Myerson-Satterthwaite impossibil- ity, I show that no mechanism can be simultaneously no-deficit and approximately efficient while also guaranteeing that agents will be willing to participate and report their preferences truthfully. Following common practice among practical mechanism designers, I then relax strategy-proofness and propose a novel mechanism, NetAscendingClock, that takes an iterative approach to find exactly efficient equilibrium solutions. I prove that NetAscendingClock is both computation- ally tractable and game theoretically reasonable. Finally, I experimentally verify both that VCG and TTC’s undesirable properties manifest themselves in practice and that NetAscendingClock addresses the shortcomings of both of these when participants submit truthful preferences.