Please use this identifier to cite or link to this item:
https://hdl.handle.net/1959.11/26806
Title: | Welfare of Sequential Allocation Mechanisms for Indivisible Goods | Contributor(s): | Aziz, Haris (author); Walsh, Toby (author); Xia, Lirong (author); Kalinowski, Thomas (author) | Publication Date: | 2016 | Open Access: | Yes | DOI: | 10.3233/978-1-61499-672-9-787 | Handle Link: | https://hdl.handle.net/1959.11/26806 | 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. | Publication Type: | Conference Publication | Conference Details: | ECAI 2016: 22nd European Conference on Artificial Intelligence, The Hague, The Netherlands, 29th August - 2nd September, 2016 | Source of Publication: | Frontiers in Artificial Intelligence and Applications, v.285, p. 787-794 | Publisher: | IOS Press | Place of Publication: | Amsterdam, Netherlands | Fields of Research (FoR) 2008: | 010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics) | Fields of Research (FoR) 2020: | 490404 Combinatorics and discrete mathematics (excl. physical combinatorics) | Socio-Economic Objective (SEO) 2008: | 970101 Expanding Knowledge in the Mathematical Sciences | Socio-Economic Objective (SEO) 2020: | 280118 Expanding knowledge in the mathematical sciences | Peer Reviewed: | Yes | HERDC Category Description: | E1 Refereed Scholarly Conference Publication | Series Name: | Frontiers in Artificial Intelligence and Applications |
---|---|
Appears in Collections: | Conference Publication School of Science and Technology |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
openpublished/WelfareKalinowski2016ConferencePublication.pdf | Published version conference publication | 278.77 kB | Adobe PDF Download Adobe | View/Open |
SCOPUSTM
Citations
13
checked on Apr 6, 2024
Page view(s)
1,616
checked on Mar 8, 2023
Download(s)
104
checked on Mar 8, 2023
This item is licensed under a Creative Commons License