A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods Under Lexicographic Preferences
Abstract
Core-selection is a crucial property of social choice functions, or rules, in social choice literature. It is also desirable to address the incentive of agents to cheat by misreporting their preferences. This paper investigates an exchange problem where each agent may have multiple indivisible goods, agents' preferences over sets of goods are assumed to be lexicographic, and side payments are not allowed. We propose an exchange rule called augmented top-trading-cycles (ATTC) procedure based on the original TTC procedure. We first show that the ATTC procedure is core-selecting. We then show that finding a beneficial misreport under the ATTC procedure is NP-hard. Under the ATTC procedure, we finally clarify the relationship between preference misreport and splitting, which is a different type of manipulation.
Cite
Text
Fujita et al. "A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods Under Lexicographic Preferences." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9318Markdown
[Fujita et al. "A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods Under Lexicographic Preferences." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/fujita2015aaai-complexity/) doi:10.1609/AAAI.V29I1.9318BibTeX
@inproceedings{fujita2015aaai-complexity,
title = {{A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods Under Lexicographic Preferences}},
author = {Fujita, Etsushi and Lesca, Julien and Sonoda, Akihisa and Todo, Taiki and Yokoo, Makoto},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2015},
pages = {907-913},
doi = {10.1609/AAAI.V29I1.9318},
url = {https://mlanthology.org/aaai/2015/fujita2015aaai-complexity/}
}