Fair division: addressing complement-free valuations and online settings

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Kulkarni, Pooja Ravi

Contributors dc:contributor

• Garg, Jugal
• Mehta, Ruta
• Chekuri, Chandra
• Vondrak, Jan

• Fair Division
• Multiobjective Submodular Optimization
• Online Allocation

Statement dc:rights

• Copyright 2025 Pooja Kulkarni

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129857