Withdraw
Loading…
Fair division: addressing complement-free valuations and online settings
Kulkarni, Pooja Ravi
Loading…
Permalink
https://hdl.handle.net/2142/129857
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
Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at IllinoisManage Files
Loading…
Edit Collection Membership
Loading…
Edit Metadata
Loading…
Edit Properties
Loading…
Embargoes
Loading…