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

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Gupta, Vanshika

Contributors dc:contributor

• Nagi, Rakesh
• Garg, Jugal

• Fair Division
• Chores
• Pareto Optimal
• Ef1
• Resource Allocation
• Nash Welfare
• Mixed Integer Linear Program
• Market-based Algorithm

Statement dc:rights

• Copyright 2023 Vanshika Gupta

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

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