Division of indivisible items : fairness, efficiency, and strategyproofness

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