2026-09-22T22:09:30Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/120133 2023-09-04 col_2142_5131 col_2142_16359 com_2142_5130 com_2142_16358 com_2142_234

Nagi, Rakesh Garg, Jugal 2023-05 application/pdf en text Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms The student, Vanshika Gupta, accepted the attached license on 2023-05-05 at 15:02. The student, Vanshika Gupta, submitted this Thesis for approval on 2023-05-05 at 15:14. This Thesis was approved for publication on 2023-05-05 at 16:31. DSpace SAF Submission Ingestion Package generated from Vireo submission #19231 on 2023-09-01 at 16:55:52 Exploratory analysis of algorithms for fair and efficient allocation of indivisible chores Gupta, Vanshika 2023-05-05 Fair Division Chores Pareto Optimal Ef1 Resource Allocation Nash Welfare Mixed Integer Linear Program Market-based Algorithm 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. Text eng https://hdl.handle.net/2142/120133 Copyright 2023 Vanshika Gupta M.S. Thesis Industrial Engineering University of Illinois at Urbana-Champaign Industrial&Enterprise Sys Eng