Fair resource allocation in rich domains

• Main Author: Lu, Xinhang
• Other Authors: Bei Xiaohui
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Science::Mathematics::Applied mathematics::Game theory; Science::Mathematics::Discrete mathematics::Algorithms
• Online Access: https://hdl.handle.net/10356/152488
• Institution: Nanyang Technological University

How should one allocate scarce resources among a group of people in a satisfactory manner when the participants have different preferences over the resources, like how to divide an inheritance or ration healthcare? Fairness is one of the desirable properties in resource allocation applications. This thesis aims at allocating scarce resources among interested agents in such a way that every agent involved feels that she gets a fair share. To this end, we present our results in three parts: (i) axiomatic study of fairness for mixed goods, (ii) quantitative measure of trade-offs between competing objectives, and (iii) mechanism design for sharing public goods. In Part I, we study the problem of fair division when the resources to be divided consist of both divisible and indivisible goods, or mixed goods for short. In this setting, we propose a novel notion of fairness, envy-freeness for mixed goods (EFM), and show that EFM can always be satisfied for any number of agents with additive valuations. In addition, we extend the analysis of a well-known fairness notion of maximin share (MMS) guarantee to the mixed goods setting by providing insights on how the MMS approximation guarantee would be affected when divisible resources are introduced as well as designing algorithms that could find allocations with good MMS approximations. In Part II, we focus on indivisible goods settings, and study trade-offs between fairness and other desiderata. An issue orthogonal to fairness is efficiency, or social welfare. The concept of (strong) price of fairness quantitatively measures the worst-case loss of social welfare due to fairness constraints. We study the (strong) price of fairness for indivisible goods by focusing on several well-established fairness notions with guaranteed existence. Next, in the same vein, we introduce the price of connectivity to quantify the price in terms of fairness that we have to pay if we desire connectivity in a fair division model where indivisible goods form an undirected graph and each agent must receive a connected subgraph, and derive bounds on this quantity. In Part III, we depart from the “division” framework and study a public goods variant of the classic cake cutting problem where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We refer to this setting as cake sharing. Our focus in this setting is on the design of truthful and fair mechanisms in the presence of strategic agents.