- Title
- Welfare of sequential allocation mechanisms for indivisible goods
- Creator
- Aziz, Haris; Kalinowski, Thomas; Walsh, Toby; Xia, Lirong
- Relation
- 22nd European Conference on Artificial Intelligence (ECAI 2016). Proceedings of the 22nd European Conference on Artificial Intelligence [presented in Frontiers in Artificial Intelligence and Applications, Vol. 285] (The Hague, Netherlands 29 August - 2 September, 2016) p. 787-794
- Publisher Link
- http://dx.doi.org/10.3233/978-1-61499-672-9-787
- Publisher
- IOS Press
- Resource Type
- conference paper
- Date
- 2016
- Description
- Sequential allocation is a simple and attractive mechanism for the allocation of indivisible goods used in a number of real world settings. In sequential allocation, agents pick items according to a policy, the order in which agents take turns. Sequential allocation will return an allocation which is Pareto efficient - no agent can do better without others doing worse. However, sequential allocation may not return the outcome that optimizes the social welfare. We consider therefore the relationship between the welfare and the efficiency of the allocations returned by sequential allocation mechanisms. We then study some simple computational questions about what welfare is possible or necessary depending on the choice of policy. Over half the problems we study turn out to be tractable, and we give polynomial time algorithms to compute them. We also consider a novel control problem in which the Chair chooses a policy to improve social welfare. Again, many of the control problems we study turn out to be tractable, and our results give polynomial time algorithms. In this case, tractability is a good thing so that the Chair can improve the social welfare of the allocation.
- Subject
- sequential allocation; indivisible goods
- Identifier
- http://hdl.handle.net/1959.13/1325071
- Identifier
- uon:25179
- Identifier
- ISBN:9781614996729
- Rights
- This article is published online with Open Access by IOS Press and distributed under the terms of the Creative Commons Attribution Non-Commercial License 4.0 (CC BY-NC 4.0).
- Language
- eng
- Full Text
- Reviewed
- Hits: 4021
- Visitors: 4284
- Downloads: 360
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Publisher version (open access) | 278 KB | Adobe Acrobat PDF | View Details Download |