JSAI2019

JSAI2019

Jun 4 - Jun 7, 2019TOKI MESSE, Niigata Convention Center
The Japanese Society for Artificial Intelligence
JSAI2019

JSAI2019

Jun 4 - Jun 7, 2019TOKI MESSE, Niigata Convention Center

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

〇Taiki Todo1(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.