Withdraw
Loading…
Algorithms and solution concepts for allocation and collaboration
Murhekar, Aniket
Loading…
Permalink
https://hdl.handle.net/2142/129246
Description
- Title
- Algorithms and solution concepts for allocation and collaboration
- Author(s)
- Murhekar, Aniket
- Issue Date
- 2025-04-24
- 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
- Ye, Yinyu
- Department of Study
- Computer Science
- Discipline
- Computer Science
- Degree Granting Institution
- University of Illinois Urbana-Champaign
- Degree Name
- Ph.D.
- Degree Level
- Dissertation
- Keyword(s)
- algorithmic game theory
- computational social choice
- discrete allocation
- EFX
- federated learning
- data exchange
- core-stability
- Abstract
- 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.
- Graduation Semester
- 2025-05
- Type of Resource
- Thesis
- Handle URL
- https://hdl.handle.net/2142/129246
- Copyright and License Information
- Copyright 2025 Aniket Murhekar
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…