{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/129857"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/129857","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Fair division: addressing complement-free valuations and online settings","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","abstract_has_math":false,"creators":["Kulkarni, Pooja Ravi"],"institution":"University of Illinois Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Garg, Jugal","Mehta, Ruta","Chekuri, Chandra","Vondrak, Jan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-07-11","date_published":"2025-07-11","updated_at":"2026-07-22T22:25:06Z","subjects":["Fair Division","Multiobjective Submodular Optimization","Online Allocation"],"languages":["en","eng"],"rights":["Copyright 2025 Pooja Kulkarni"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/129857","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Garg, Jugal","Mehta, Ruta","Chekuri, Chandra","Vondrak, Jan"]},{"key":"dc:creator","label":"Author","values":["Kulkarni, Pooja Ravi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-07-11","2025-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Fair Division","Multiobjective Submodular Optimization","Online Allocation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Pooja Kulkarni"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/129857"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","The student, Pooja Kulkarni, accepted the attached license on 2025-07-10 at 11:30.","The student, Pooja Kulkarni, submitted this Dissertation for approval on 2025-07-10 at 15:54.","This Dissertation was approved for publication on 2025-07-11 at 11:07.","DSpace SAF Submission Ingestion Package generated from Vireo submission #22486 on 2025-10-20 at 16:57:42","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Fair division: addressing complement-free valuations and online settings"]}]}],"canonical_facts":{"dc:contributor":["Garg, Jugal","Mehta, Ruta","Chekuri, Chandra","Vondrak, Jan"],"dc:creator":["Kulkarni, Pooja Ravi"],"dc:date":["2025-07-11","2025-08"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","The student, Pooja Kulkarni, accepted the attached license on 2025-07-10 at 11:30.","The student, Pooja Kulkarni, submitted this Dissertation for approval on 2025-07-10 at 15:54.","This Dissertation was approved for publication on 2025-07-11 at 11:07.","DSpace SAF Submission Ingestion Package generated from Vireo submission #22486 on 2025-10-20 at 16:57:42","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/129857"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Pooja Kulkarni"],"dc:subject":["Fair Division","Multiobjective Submodular Optimization","Online Allocation"],"dc:title":["Fair division: addressing complement-free valuations and online settings"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:06Z"}