[2F1-E-3] Agents: interaction and decision

[2F1-E-3-04] Analysis of Incentive Ratio in Top-Trading-Cycles Algorithms

〇Taiki Todo¹ (1. Kyushu University)

Keywords:Algorithmic Game Theory, Incentive, Algorithm

The main objective of this paper is to analyze some variants of the classical top-trading-cycles (TTC) algorithm for slightly modified models of the housing market. Extensions of TTC for such modified models are not necessarily strategy-proof, as pointed out by Fujita et al.\ (2015), and thus some alternative analysis of agents' selfish behavior is needed. In this paper, the incentive ratio, originally proposed by Chen et al.\ (2011), of the variants of TTC algorithm is analyzed in both (i) the multi-item exchange and (ii) an exchange model with a specific form of externalities.