Algorithms and solution concepts for allocation and collaboration

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.

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

• Murhekar, Aniket

Contributors dc:contributor

• Garg, Jugal
• Mehta, Ruta
• Chekuri, Chandra
• Ye, Yinyu

• algorithmic game theory
• computational social choice
• discrete allocation
• EFX
• federated learning
• data exchange
• core-stability

Statement dc:rights

• Copyright 2025 Aniket Murhekar

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

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