Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness


Amanatidis, Georgios, Birmpas, Georgios, Christodoulou, George and Markakis, Evangelos (2017) Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness. In: EC '17: ACM Conference on Economics and Computation.

[img] Text (admin)
2017-05-12T18:06:09Z.atom - Unspecified
Download (9kB)
[img] Text
00-characterization-ec17_cr.pdf - Author Accepted Manuscript
Download (690kB)
[img] Text (admin)
2017-05-12T18:06:25Z.atom - Unspecified
Download (9kB)
[img] Text (admin)
2017-05-12T19:47:12Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-12T20:46:14Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-12T21:46:22Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-12T22:47:45Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-12T23:54:26Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T01:49:08Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T02:47:38Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T03:47:43Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T05:12:04Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T05:47:52Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T06:46:39Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T07:47:07Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T08:47:55Z.atom - Unspecified
Download (0B)
[img] Text (admin)
2017-05-13T09:46:45Z.atom - Unspecified
Download (0B)

Abstract

We study the mechanism design problem of allocating a set of indivisible items without monetary transfers. Despite the vast literature on this very standard model, it still remains unclear how do truthful mechanisms look like. We focus on the case of two players with additive valuation functions and our purpose is twofold. First, our main result provides a complete characterization of truthful mechanisms that allocate all the items to the players. Our characterization reveals an interesting structure underlying all truthful mechanisms, showing that they can be decomposed into two components: A selection part where players pick their best subset among prespecified choices determined by the mechanism, and an exchange part where players are offered the chance to exchange certain subsets if it is favorable to do so. In the remaining paper, we apply our main result and derive several consequences on the design of mechanisms with fairness guarantees. We consider various notions of fairness, (indicatively, maximin share guarantees and envy-freeness up to one item) and provide tight bounds for their approximability. Our work se.les some of the open problems in this agenda, and we conclude by discussing possible extensions to more players.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: mechanism design without money, fair division, maximin share fairness, envy-freeness up to one item
Depositing User: Symplectic Admin
Date Deposited: 17 May 2017 14:34
Last Modified: 19 Jan 2023 07:04
DOI: 10.1145/3033274.3085147
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3007450
Dimensions
Altmetric
CORE (COnnecting REpositories)