Mechanisms for fair allocation problems: no-punishment payment rules in verifiable settings

DOI10.1613/JAIR.4224zbMATH Open1286.68439arXiv1209.3418OpenAlexW935602133MaRDI QIDQ5404397FDOQ5404397

Gianluigi Greco, Francesco Scarcello

Publication date: 24 March 2014

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Abstract: Mechanism design is addressed in the context of fair allocations of indivisible goods with monetary compensation. Motivated by a real-world social choice problem, mechanisms with verification are considered in a setting where (i) agents' declarations on allocated goods can be fully verified before payments are performed, and where (ii) verification is not used to punish agents whose declarations resulted in incorrect ones. Within this setting, a mechanism is designed that is shown to be truthful, efficient, and budget-balanced, and where agents' utilities are fairly determined by the Shapley value of suitable coalitional games. The proposed mechanism is however shown to be #P-complete. Thus, to deal with applications with many agents involved, two polynomial-time randomized variants are also proposed: one that is still truthful and efficient, and which is approximately budget-balanced with high probability, and another one that is truthful in expectation, while still budget-balanced and efficient.

Full work available at URL: https://arxiv.org/abs/1209.3418

Recommendations

• A general strategy proof fair allocation mechanism
• Strategy-proof assignment with fair compensation
• EFFICIENT STRATEGY PROOF FAIR ALLOCATION ALGORITHMS
• Truthful Fair Division
• Characterizations of strategy-proof and fair mechanisms for allocating indivisible goods

zbMATH Keywords

computational complexitycoalitional gamesmechanism design

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Agent technology and artificial intelligence (68T42)

Cited In (4)

• On the expected payment of mechanisms for task allocation
• Answers set programs for non-transferable utility games: expressiveness, complexity and applications
• Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value
• Mechanism design with costly verification and limited punishments

This page was built for publication: Mechanisms for fair allocation problems: no-punishment payment rules in verifiable settings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404397)