The Library
Division of indivisible items : fairness, efficiency, and strategyproofness
Tools
Sun, Ankang (2022) Division of indivisible items : fairness, efficiency, and strategyproofness. PhD thesis, University of Warwick.
|
PDF
WRAP_Theses_Sun_2022.pdf - Submitted Version - Requires a PDF viewer. Download (2222Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b3927351
Abstract
This thesis theoretically studies fairness, efficiency, and strategyproofness, in the model of assigning a set of indivisible items to multiple agents. Fairness, with an interpretation of social justice, ensures that everyone is treated unbiasedly. Efficiency, a quantitative indicator, measures the utilization of the total resource. Strategyproofness, a desired property of the assignment protocol, inhibits the strategic behavior of misreporting information from participants. This work, first in Chapter 3, focuses on the allocation of chores (items with non-positive value) and studies two envy-based and two share-based fairness criteria. The analysis provides the connections between fairness criteria and also investigates, in the worst-case scenario, the efficiency loss when requiring allocations to be fair by establishing the corresponding price of fairness. This thesis, then in Chapter 4, studies two relaxations of equitability, a fairness notion that ensures agents the same level of value. This chapter cares about both cases of goods (items with non-negative value) and chores. The chapter first investigates the trade-off between efficiency and fairness and then provides the picture of the computational complexity of (i) deciding the existence of approximately equitable and welfare-maximizing allocation; (ii) computing a welfare maximizer among all approximately equitable allocation. Chapter 5 considers the setting where agents’ preferences over items are their private information and not publicly known anymore. Agents are required to report their preferences so that assignment procedures can be carried on. Agents can and will report false information if they are able to receive additional value by doing so. This chapter proposes deterministic and randomised (group) strategyproof mechanisms in which each agent’s (expected) value is maximized when she reports the true preference. Besides strategyproofness, the proposed mechanisms can output efficient allocations that capture a certain degree of fairness.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | H Social Sciences > HD Industries. Land use. Labor | ||||
Library of Congress Subject Headings (LCSH): | Resource allocation, Strategic planning, Business planning, Fairness, Industrial efficiency | ||||
Official Date: | December 2022 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Warwick Business School | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Chen, Bo ; Doan, Xuan Vinh | ||||
Format of File: | |||||
Extent: | viii, 141 pages | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |