Fair division: addressing complement-free valuations and online settings

Kulkarni, Pooja Ravi

Permalink

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

Description

Title

Fair division: addressing complement-free valuations and online settings

Author(s)

Kulkarni, Pooja Ravi

Issue Date

2025-07-11

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

• Garg, Jugal
• Mehta, Ruta

Doctoral Committee Chair(s)

• Garg, Jugal
• Mehta, Ruta

Committee Member(s)

• Chekuri, Chandra
• Vondrak, Jan

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Fair Division, multiobjective submodular optimization, online allocation

Abstract

We study computational aspects of fair division of m indivisible goods among n competing agents with heterogeneous preferences. The preferences of the agents are captured using valuation functions (v_i) for all i in [n]. An instance of the fair division problem is characterized by: (1) The class of functions that the valuations of the agents fall into, (2) The intrinsic entitlement of the agent to the goods and, (3) The amount of information of the instance that is known upfront. In this thesis, we address these three aspects as follows: 1) Valuation functions: We study valuation functions from the complement-free hierarchy---specifically, SPLC, submodular, and XOS functions---and design algorithms for the well-studied fairness notions of Nash social welfare (NSW), Maximin Share (MMS) and Any Price Share (APS). Out of these, NSW and APS are defined for agents who have unequal entitlements (called asymmetric agents). Highlights of our computational results are: a) Nash Social Welfare (NSW): We give an O(n log n) approximation algorithm for maximum NSW with submodular valuations. For XOS valuations, we design a sublinear (O(n^{53/54})) approximation algorithm. b) Maximin Share (MMS): We design a 1/2 approximation algorithm for MMS with SPLC valuations. This is currently the best known guarantee for MMS for any valuation class beyond additive. c) Any Price Share (APS):} We show that a simple modification of greedy algorithm can achieve a (1/3) approximation for APS with submodular valuations. Additionally, we give a polynomial time exact algorithm for matroid rank functions and a constant factor (approximately 0.1222) approximation algorithm for XOS valuations with binary marginals. 2) Asymmetric Entitlements:} Our O(n log n) approximation for NSW with submodular valuation functions and O(n) approximation algorithm for NSW with SPLC valuations give the same guarantee for asymmetric agents. Our 1/3 approximation for APS also works for asymmetric agents. 3) Online Fair Division: We initiate the study of allocating offline goods to agents that arrive online. This problem had strong lower bounds and we circumvent these by introducing a relaxed model that can predict future arrivals. We show that this model helps us achieve ex-post constant fraction approximation to MMS under a stochastic arrival order. We also provide evidence of non-triviality of the model by showing strong lower bound in adversarial arrival model. This thesis develops new algorithmic tools---such as capped-social welfare, release-and-rematch strategy, and sparsification of fractional allocations in beyond-additive fair division that may have (and have previously had) broader implications in algorithmic game theory and combinatorial optimization. Similarly, the OnlineKTypeFD model should see more applications with other fairness notions.

Graduation Semester

2025-08

Type of Resource

Thesis

Handle URL

https://hdl.handle.net/2142/129857

Copyright and License Information

Copyright 2025 Pooja Kulkarni

Owning Collections