A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences
Fujita, Etsushi; Lesca, Julien; Sonoda, Akihisa; Todo, Taiki; Yokoo, Makoto (2018), A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences, Journal of Artificial Intelligence Research, 63, p. 515–555. 10.1613/jair.1.11254
TypeArticle accepté pour publication ou publié
Journal nameJournal of Artificial Intelligence Research
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)Core-selection is a crucial property of rules in the literature of resource allocation. It is also desirable, from the perspective of mechanism design, to address the incentive of agents to cheat by misreporting their preferences. This paper investigates the exchange problem where (i) each agent is initially endowed with (possibly multiple) indivisible goods, (ii) agents' preferences are assumed to be conditionally lexicographic, and (iii) side payments are prohibited. We propose an exchange rule called augmented top-trading-cycles (ATTC), based on the original TTC procedure. We first show that ATTC is core-selecting and runs in polynomial time with respect to the number of goods. We then show that finding a beneficial misreport under ATTC is NP-hard. We finally clarify relationship of misreporting with splitting and hiding, two different types of manipulations, under ATTC.
Subjects / KeywordsCore-selection
Showing items related by title and author.
A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences Lesca, Julien; Fujita, Etsushi; Sonoda, Akihisa; Todo, Taiki; Yokoo, Makoto (2015) Communication / Conférence