Establishing a Theory for Exchange of Multiple Indivisible Goods with Indifferences

Microsoft Research CORE11

''Establishing a Theory for Exchange of Multiple Indivisible Goods with Indifferences''

In this project we investigate a problem of exchanging indivisible goods where each agent is initially endowed with multiple goods and agents' preferences contain indifferences. Our main objective is to clarify the existence of exchange mechanisms that satisfy three desirable properties, namely individual rationality, strategy-proofness, and Pareto efficiency. More precisely, we would like to establish a complete characterization of agents' preferences under which the existence of such mechanisms are guaranteed. This is considered a generalization of the results by Sonoda et al (2014). If we find some cases where such mechanisms do not exist, we then develop a mechanism that is not perfectly strategy-proof but approximately strategy-proof, e.g., for most of the cases no agent has an incentive to cheat. This project is financially supported by Microsoft Research CORE11, as a part of Mt.Fuji Plan.

Keywords: algorithmic game theory; mechanism design; matching; Core assignments; top-trading-cycles; microeconomics; kidney exchange; housing market

Detail

• Program: Microsoft Research CORE11
• PI: Taiki Todo (Kyushu University, Japan)
• Duration: Apr 2015 - Mar 2016
• Amount: 1,768,000 JPY

Resources

• Interview Slides (PDF, November 2014)

Articles/Activities Supported by the Project:

1. [Poster] Establishing a Theory for Exchange of Multiple Indivisible Goods with Indifferences. In Microsoft Research Korea-Japan Academic Day 2016. Tokyo, Japan. May 2015.
2. [Talk] Establishing a Theory for Exchange of Multiple Indivisible Goods with Indifferences. In Microsoft Research Korea-Japan Academic Day 2015. Seoul, Korea. May 2015.

Other Related Articles:

1. Zhaohong Sun, Hideaki Hata, Taiki Todo, and Makoto Yokoo. Exchange of Indivisible Goods with Asymmetry. IJCAI-15. [link]
2. Etsushi Fujita, Julien Lesca, Akihisa Sonoda, Taiki Todo and Makoto Yokoo. A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences. AAAI-15. [link]
3. Akihisa Sonoda, Etsushi Fujita, Taiki Todo and Makoto Yokoo. Two case studies for trading multiple indivisible goods with indifferences. AAAI-14. [link]
4. Taiki Todo, Haixin Sun and Makoto Yokoo. Strategyproof exchange with multiple private endowments. AAAI-14. [link]