Algorithms and solution concepts for allocation and collaboration

Murhekar, Aniket

Permalink

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

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