Fair resource allocation in rich domains

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...

Full description

Saved in:
Bibliographic Details
Main Author: Lu, Xinhang
Other Authors: Bei Xiaohui
Format: Thesis-Doctor of Philosophy
Language:English
Published: Nanyang Technological University 2021
Subjects:
Online Access:https://hdl.handle.net/10356/152488
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-152488
record_format dspace
spelling sg-ntu-dr.10356-1524882023-02-28T23:41:39Z Fair resource allocation in rich domains Lu, Xinhang Bei Xiaohui School of Physical and Mathematical Sciences xhbei@ntu.edu.sg Science::Mathematics::Applied mathematics::Game theory Science::Mathematics::Discrete mathematics::Algorithms 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. Doctor of Philosophy 2021-08-23T01:01:31Z 2021-08-23T01:01:31Z 2021 Thesis-Doctor of Philosophy Lu, X. (2021). Fair resource allocation in rich domains. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/152488 https://hdl.handle.net/10356/152488 10.32657/10356/152488 en This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0). application/pdf Nanyang Technological University
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Science::Mathematics::Applied mathematics::Game theory
Science::Mathematics::Discrete mathematics::Algorithms
spellingShingle Science::Mathematics::Applied mathematics::Game theory
Science::Mathematics::Discrete mathematics::Algorithms
Lu, Xinhang
Fair resource allocation in rich domains
description 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.
author2 Bei Xiaohui
author_facet Bei Xiaohui
Lu, Xinhang
format Thesis-Doctor of Philosophy
author Lu, Xinhang
author_sort Lu, Xinhang
title Fair resource allocation in rich domains
title_short Fair resource allocation in rich domains
title_full Fair resource allocation in rich domains
title_fullStr Fair resource allocation in rich domains
title_full_unstemmed Fair resource allocation in rich domains
title_sort fair resource allocation in rich domains
publisher Nanyang Technological University
publishDate 2021
url https://hdl.handle.net/10356/152488
_version_ 1759854921465724928