The parameterized complexity of manipulating Top Trading Cycles

摘要

We study the problem of exchange when agents are endowed with heterogeneous indivisible objects, and there is no money. In this setting, no rule satisfies Pareto-efficiency, individual rationality, and strategy-proofness; there is no consensus in the literature on satisfactory second-best mechanisms. A natural generalization of the ubiquitous Top Trading Cycles (TTC) satisfies the first two properties on the lexicographic domain, rendering it manipulable. We characterize the computational complexity of manipulating this mechanism; we show that it is \(\mathbf {W[P]}\)-hard by reduction from MONOTONE WEIGHTED CIRCUIT SATISFIABILITY. We provide a matching upper bound for a wide range of preference domains. We further show that manipulation by groups (when parameterized by group size) is \(\mathbf {W[P]}\)-hard. This provides support for TTC as a second-best mechanism. Lastly, our results are of independent interest to complexity theorists: there are few natural \(\mathbf {W[P]}\)-complete problems and, as far as we are aware, this is the first such problem arising from the social sciences.