Fair division of indivisibles through the computational lens

Kulkarni, Rucha Ravi

Permalink

https://hdl.handle.net/2142/122031 Copy

Description

Title

Fair division of indivisibles through the computational lens

Author(s)

Kulkarni, Rucha Ravi

Issue Date

2023-11-29

Director of Research (if dissertation) or Advisor (if thesis)

Mehta, Ruta

Doctoral Committee Chair(s)

Mehta, Ruta

Committee Member(s)

• Chekuri, Chandra
• Erikson, Jeff
• Procaccia, Ariel

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• fair division
• indivisible items
• Nash welfare
• Maximin share
• envy-freeness

Abstract

This thesis studies the computational problem of fairly dividing a set of indivisible and non-shareable items among n agents with heterogeneous preferences. The focus of this work is on three fairness notions -- the Nash social welfare (NSW), Maximin share (MMS), and relaxations of envy-freeness. The thesis thus has three natural parts, one corresponding to each of these. Extensive work on these notions were mainly focused on allocating goods, i.e, positively valued items, among agents with additive valuations. Our work in the first two parts extends state-of-the-art on NSW and MMS respectively to valuations beyond additive and to bads, i.e., negatively valued items. The third part models a real-world setting on network routing as a fairness problem, defines relaxations of envy-freeness applicable here and studies their computability. The first part studies the problem of maximizing Nash welfare, the weighted geometric mean of agent’s utilities, where weights are agents’ entitlements. This notion is well-known for achieving a right balance between fairness and efficiency. Prior work had mainly focused on symmetric weight agents with additive valuation functions. For the asymmetric case, a trivial O(m) approximate factor algorithm was known, where m is the number of goods being distributed. We initiate the study of the case where the agents can have submodular valuation functions. Along with submodular valuations, we also allow the agents to have asymmetric weights. We design two algorithms: (i) When agents have additive valuations and unequal entitlements, to find O(n)-approximate NSW allocation, where n is the number of agents. (ii) When agents have submodular valuations and unequal entitlements, to find O(n log(n))-approximate NSW. For the latter, when n is a constant, show tight lower-upper bounds of (1-1/e)~ 1.5819-approximation, and thereby resolving this case completely. The second part focuses on the MMS notion, one of the most popular share-based notions. Extensive work on MMS largely focused on allocating either goods or bads, but not both together. We initiate the study of MMS for mixed-manna, i.e., allocating both goods and bads together, under additive valuations. We first show non-existence of any non-trival approximation in general. We next design a PTAS to find an alpha-MMS allocation, where alpha is the instance specific optimal factor, under two conditions: (i) constant n, and (ii) for every agent i, her total absolute value for all the items is significantly greater than the minimum of her total value for goods and her total absolute value for chores. Both of these conditions are unavoidable, as we show intractability when either of the condition is dropped. For the goods allocation case when the agents have OXS valuation functions: We show the existence of a 1/3(1+(2/3)/(n-2/3}-MMS allocation and a PTAS for the same, breaking the barrier of 1/3-MMS that was previously known. We also show that a better than 2/3-MMS allocation does not exist for all instances in this class. In the third part we study fairness in the routing problems. also known as congestion games, extending the classical fairness notion of envy freeness to this setting. We obtain the following results. - We define fairness and efficiency notions called envy-free ratio and rank approximation for this setting. Informally, a path has rank k if it's among the k best paths computed according to some optimal algorithm. - When the cost functions are linear, we present 4 approximately fair and 2 approximately efficient algorithm. - For the more general setting where the network may dynamically change over time, we pre-assign alternates, that is a set of paths to each of the n users. We show an algorithm that pre-assigns O(log n) paths such that the assignment is 2 approximately fair, and each user will be able to pick a path that has (1+2/e)cn- approximate rank.

Graduation Semester

2023-12

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Rucha Kulkarni

Owning Collections