Exploratory analysis of algorithms for fair and efficient allocation of indivisible chores

Gupta, Vanshika

Permalink

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

Description

Title

Exploratory analysis of algorithms for fair and efficient allocation of indivisible chores

Author(s)

Gupta, Vanshika

Issue Date

2023-05-05

Director of Research (if dissertation) or Advisor (if thesis)

• Nagi, Rakesh
• Garg, Jugal

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Fair Division
• Chores
• Pareto Optimal
• EF1
• Resource allocation
• Nash welfare
• Mixed Integer Linear Program
• market-Based Algorithm

Abstract

This thesis explores algorithms for computing fair and efficient allocations of indivisible chores among agents. We use Envy-Freeness up to One Chore (EF1) and Pareto Optimality (PO) as a measure of fairness and efficiency, respectively. While a proof of existence and a pseudo-polynomial time algorithm exist for items with positive utility (goods), the existence of such an allocation for chores has not yet been proven. We draw parallels from market equilibrium-based algorithms for goods to develop a similar algorithm for chores. We conduct rigorous experiments by randomly generating millions of samples using a developed codebase and no counterexamples indicating non-existence were found. We also graph the time the algorithm takes as a function of the number of agents and items. However, our attempts to theoretically prove such an allocation’s existence have not yielded substantial results. In addition to the market-based approach, we formulate the problem using a Mixed Integer Program and develop a sequential algorithm that computes EF1 allocations with increasing social welfare and evaluates each allocation for efficiency constraints. We also disprove or present counterexamples to some additional results that hold for the goods problem. Overall, this study provides insights into potential algorithms for finding EF1+PO allocations of chores among agents and suggests possible directions for future research. The algorithm proposed can still be applied to most practical chore allocation problems in real-world scenarios, as indicated by the computational experiments.

Graduation Semester

2023-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Vanshika Gupta

Owning Collections