{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/129246"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/129246","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithms and solution concepts for allocation and collaboration","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","abstract_has_math":false,"creators":["Murhekar, Aniket"],"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","Ye, Yinyu"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-04-24","date_published":"2025-04-24","updated_at":"2026-07-22T22:25:04Z","subjects":["algorithmic game theory","computational social choice","discrete allocation","EFX","federated learning","data exchange","core-stability"],"languages":["en","eng"],"rights":["Copyright 2025 Aniket Murhekar"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/129246","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","Ye, Yinyu"]},{"key":"dc:creator","label":"Author","values":["Murhekar, Aniket"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-04-24","2025-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"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":["algorithmic game theory","computational social choice","discrete allocation","EFX","federated learning","data exchange","core-stability"]}]},{"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 Aniket Murhekar"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/129246"]}]},{"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-19 without embargo terms","The student, Aniket Murhekar, accepted the attached license on 2025-04-24 at 13:37.","The student, Aniket Murhekar, submitted this Dissertation for approval on 2025-04-24 at 13:46.","This Dissertation was approved for publication on 2025-04-24 at 15:12.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21957 on 2025-10-19 at 18:10:55","Algorithmic decision-making is increasingly used to address several societal and industrial challenges, particularly in problems of allocation -- distributing resources or tasks -- and problems of collaboration -- developing protocols for cooperative resource sharing. Three key guiding principles for trustworthy solutions are fairness, efficiency, and incentives. While fairness, efficiency, and incentives have been extensively studied in economics, game theory, and social choice, much of the work focuses on goods -- items that provide value and are non-replicable. However, many modern applications involve chores -- items that impose a cost -- or data -- a freely replicable resource. These applications motivate novel solution concepts and algorithms for allocation and collaboration problems involving chores or data, that are backed by strong axiomatic foundations and rigorous mathematical guarantees. The first part of this thesis studies fair and efficient allocations of indivisible chores to agents with additive preferences. The existence of allocations that satisfy the prominent fairness notion of envy-freeness up to any chore (EFX) is a major open problem in discrete fair division, prompting the study of multiplicative approximations. We prove the existence of 4-EFX allocations, improving over the previous known approximation of O(n^2)-EFX for n agents, thereby establishing the first constant-factor approximation of EFX. We also study another major open problem -- the existence of allocations that simultaneously satisfy the fairness notion of envy-freeness up to one good (EF1) and the efficiency notion of Pareto-optimality (PO). We prove the existence and polynomial-time computation of EF1 and PO allocations for three types of agents or two types of chores, even with asymmetric agents, comprising some of the only non-trivial results for this problem. The second part proposes solution concepts for collaborative data sharing frameworks such as federated learning (FL) and data exchange economies. The success of these frameworks depends on broad participation and high-quality contributions, but this can be undermined by a lack of reciprocity, defecting coalitions, or strategic agents withholding data due to sharing costs. We address these issues by adapting ideas from mechanism design, social choice, and cooperative game theory. For FL, we propose two payment-based mechanisms that ensure fairness, optimal welfare, and incentivize data sharing. We also extend the classical notion of proportional veto core (PVC) from social choice theory to FL, and prove the existence of PVC-stable models in general learning paradigms. Lastly, we propose a formal model of data exchange, and prove the existence of reciprocally fair and core-stable exchanges under mild assumptions, ensuring both mutual benefit and stability."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Algorithms and solution concepts for allocation and collaboration"]}]}],"canonical_facts":{"dc:contributor":["Garg, Jugal","Mehta, Ruta","Chekuri, Chandra","Ye, Yinyu"],"dc:creator":["Murhekar, Aniket"],"dc:date":["2025-04-24","2025-05"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms","The student, Aniket Murhekar, accepted the attached license on 2025-04-24 at 13:37.","The student, Aniket Murhekar, submitted this Dissertation for approval on 2025-04-24 at 13:46.","This Dissertation was approved for publication on 2025-04-24 at 15:12.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21957 on 2025-10-19 at 18:10:55","Algorithmic decision-making is increasingly used to address several societal and industrial challenges, particularly in problems of allocation -- distributing resources or tasks -- and problems of collaboration -- developing protocols for cooperative resource sharing. Three key guiding principles for trustworthy solutions are fairness, efficiency, and incentives. While fairness, efficiency, and incentives have been extensively studied in economics, game theory, and social choice, much of the work focuses on goods -- items that provide value and are non-replicable. However, many modern applications involve chores -- items that impose a cost -- or data -- a freely replicable resource. These applications motivate novel solution concepts and algorithms for allocation and collaboration problems involving chores or data, that are backed by strong axiomatic foundations and rigorous mathematical guarantees. The first part of this thesis studies fair and efficient allocations of indivisible chores to agents with additive preferences. The existence of allocations that satisfy the prominent fairness notion of envy-freeness up to any chore (EFX) is a major open problem in discrete fair division, prompting the study of multiplicative approximations. We prove the existence of 4-EFX allocations, improving over the previous known approximation of O(n^2)-EFX for n agents, thereby establishing the first constant-factor approximation of EFX. We also study another major open problem -- the existence of allocations that simultaneously satisfy the fairness notion of envy-freeness up to one good (EF1) and the efficiency notion of Pareto-optimality (PO). We prove the existence and polynomial-time computation of EF1 and PO allocations for three types of agents or two types of chores, even with asymmetric agents, comprising some of the only non-trivial results for this problem. The second part proposes solution concepts for collaborative data sharing frameworks such as federated learning (FL) and data exchange economies. The success of these frameworks depends on broad participation and high-quality contributions, but this can be undermined by a lack of reciprocity, defecting coalitions, or strategic agents withholding data due to sharing costs. We address these issues by adapting ideas from mechanism design, social choice, and cooperative game theory. For FL, we propose two payment-based mechanisms that ensure fairness, optimal welfare, and incentivize data sharing. We also extend the classical notion of proportional veto core (PVC) from social choice theory to FL, and prove the existence of PVC-stable models in general learning paradigms. Lastly, we propose a formal model of data exchange, and prove the existence of reciprocally fair and core-stable exchanges under mild assumptions, ensuring both mutual benefit and stability."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/129246"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Aniket Murhekar"],"dc:subject":["algorithmic game theory","computational social choice","discrete allocation","EFX","federated learning","data exchange","core-stability"],"dc:title":["Algorithms and solution concepts for allocation and collaboration"],"dc:type":["text","Thesis"],"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:04Z"}