{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/120133"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/120133","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Exploratory analysis of algorithms for fair and efficient allocation of indivisible chores","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_has_math":false,"creators":["Gupta, Vanshika"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Nagi, Rakesh","Garg, Jugal"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-05","date_published":"2023-05","updated_at":"2026-07-22T22:24:56Z","subjects":["Fair Division","Chores","Pareto Optimal","Ef1","Resource Allocation","Nash Welfare","Mixed Integer Linear Program","Market-based Algorithm"],"languages":["en","eng"],"rights":["Copyright 2023 Vanshika Gupta"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/120133","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nagi, Rakesh","Garg, Jugal"]},{"key":"dc:creator","label":"Author","values":["Gupta, Vanshika"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-05","2023-05-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Fair Division","Chores","Pareto Optimal","Ef1","Resource Allocation","Nash Welfare","Mixed Integer Linear Program","Market-based Algorithm"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Vanshika Gupta"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/120133"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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","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."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Exploratory analysis of algorithms for fair and efficient allocation of indivisible chores"]}]}],"canonical_facts":{"dc:contributor":["Nagi, Rakesh","Garg, Jugal"],"dc:creator":["Gupta, Vanshika"],"dc:date":["2023-05","2023-05-05"],"dc:description":["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","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."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/120133"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Vanshika Gupta"],"dc:subject":["Fair Division","Chores","Pareto Optimal","Ef1","Resource Allocation","Nash Welfare","Mixed Integer Linear Program","Market-based Algorithm"],"dc:title":["Exploratory analysis of algorithms for fair and efficient allocation of indivisible chores"],"dc:type":["text"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:56Z"}