| Title |
|
Welfare of Sequential Allocation Mechanisms for Indivisible Goods |
|
|
| Publication Date |
|
| Author(s) |
|
| Editor |
|
Editor(s): Gal A Kaminka, Maria Fox , Paolo Bouquet , Eyke Hüllermeier , Virginia Dignum , Frank Dignum and Frank van Harmelen |
|
|
| Type of document |
|
| Language |
|
| Entity Type |
|
| Publisher |
|
| Place of publication |
|
| Series |
|
Frontiers in Artificial Intelligence and Applications |
|
|
| DOI |
|
10.3233/978-1-61499-672-9-787 |
|
|
| UNE publication id |
|
| Abstract |
|
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. |
|
|
| Link |
|
| Citation |
|
Frontiers in Artificial Intelligence and Applications, v.285, p. 787-794 |
|
|
| ISBN |
|
| Start page |
|
| End page |
|
| Rights |
|
Attribution-NonCommercial-NoDerivatives 4.0 International |
|
|