{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/112976"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/112976","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithms for fair division through competitive equilibrium","abstract":"I study the age old problem of fair and efficient resource allocation. While many fairness notions exist, competitive equilibrium (CE) is often the most preferred as it satisfies multiple other fairness properties simultaneously. The approach creates a fictitious market for the items by endowing agents with virtual currency. In an equilibrium, aggregate demand equals aggregate supply when agents purchase utility maximizing bundles. My work explores two main directions: algorithms for computing CE of mixed manna (goods and bads), and applications to the fair division of indivisible goods. First, I examine the problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bars that everyone dislikes, as well as items that some like and other dislike. The seminal work of Bogomolnaia et al. (’17) argues why allocating a mixed manna is genuinely more complicated than a good or bad manna, and why CE is the best mechanism. They also prove the existence of equilibrium and establish its peculiar properties, e.g., non-convex and disconnected set of equilibria even under linear utilities, but leave the problem of computing an equilibrium open. My main result is a simplex-like algorithm based on Lemke’s scheme for computing a competitive allocation of a mixed manna under SPLC utilities. Experimental results on randomly generated instances suggest the algorithm will be fast in practice. The problem is known to be PPAD-hard for the case of good manna, and I also show a similar result for the case of bad manna. Given these PPAD-hardness results, designing such an algorithm is the only non-brute-force (non-enumerative) option known, e.g., the classical Lemke-Howson algorithm for computing a Nash equilibrium in a two player game is still the most widely used algorithm. My algorithm also yields several new structural properties of CE as simple corollaries. I obtain constructive proof of existence for a far more general setting, membership of the problem in PPAD, rational-valued solution, and odd number of solutions property (settling a conjecture of Bogomolnaia et al. in the affirmative). Furthermore, I show that if either the number of agents or the number of items is constant, then the number of pivots in the algorithm is strongly polynomial when the mixed manna contains only bads, providing additional evidence to the practicality of my approach. Second, I focus on the case of indivisible goods. Various fairness notions have been proposed with the rapidly growing field of fair division, but the Nash social welfare (NSW) serves as a focal point. In part, this follows from the ‘unreasonable’ fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously. However, existing approximation algorithms fail to satisfy all of the remarkable fairness guarantees offered by a max NSW allocation, instead targeting only the specific NSW objective. I address this issue by presenting a 2 max NSW, Prop-1, 1/(2n) MMS, and Pareto optimal allocation in strongly polynomial time. My techniques are based on a market interpretation of a fractional max NSW allocation. I present novel definitions of fairness concepts in terms of market prices, and design a new scheme to round a variation of a CE into an integral allocation in way that provides most of the fairness properties of an integral max NSW allocation.","abstract_html":"I study the age old problem of fair and efficient resource allocation. While many fairness notions exist, competitive equilibrium (CE) is often the most preferred as it satisfies multiple other fairness properties simultaneously. The approach creates a fictitious market for the items by endowing agents with virtual currency. In an equilibrium, aggregate demand equals aggregate supply when agents purchase utility maximizing bundles. My work explores two main directions: algorithms for computing CE of mixed manna (goods and bads), and applications to the fair division of indivisible goods. First, I examine the problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bars that everyone dislikes, as well as items that some like and other dislike. The seminal work of Bogomolnaia et al. (’17) argues why allocating a mixed manna is genuinely more complicated than a good or bad manna, and why CE is the best mechanism. They also prove the existence of equilibrium and establish its peculiar properties, e.g., non-convex and disconnected set of equilibria even under linear utilities, but leave the problem of computing an equilibrium open. My main result is a simplex-like algorithm based on Lemke’s scheme for computing a competitive allocation of a mixed manna under SPLC utilities. Experimental results on randomly generated instances suggest the algorithm will be fast in practice. The problem is known to be PPAD-hard for the case of good manna, and I also show a similar result for the case of bad manna. Given these PPAD-hardness results, designing such an algorithm is the only non-brute-force (non-enumerative) option known, e.g., the classical Lemke-Howson algorithm for computing a Nash equilibrium in a two player game is still the most widely used algorithm. My algorithm also yields several new structural properties of CE as simple corollaries. I obtain constructive proof of existence for a far more general setting, membership of the problem in PPAD, rational-valued solution, and odd number of solutions property (settling a conjecture of Bogomolnaia et al. in the affirmative). Furthermore, I show that if either the number of agents or the number of items is constant, then the number of pivots in the algorithm is strongly polynomial when the mixed manna contains only bads, providing additional evidence to the practicality of my approach. Second, I focus on the case of indivisible goods. Various fairness notions have been proposed with the rapidly growing field of fair division, but the Nash social welfare (NSW) serves as a focal point. In part, this follows from the ‘unreasonable’ fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously. However, existing approximation algorithms fail to satisfy all of the remarkable fairness guarantees offered by a max NSW allocation, instead targeting only the specific NSW objective. I address this issue by presenting a 2 max NSW, Prop-1, 1/(2n) MMS, and Pareto optimal allocation in strongly polynomial time. My techniques are based on a market interpretation of a fractional max NSW allocation. I present novel definitions of fairness concepts in terms of market prices, and design a new scheme to round a variation of a CE into an integral allocation in way that provides most of the fairness properties of an integral max NSW allocation.","abstract_has_math":false,"creators":["McGlaughlin, Peter"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Garg, Jugal","Beck, Carolyn","Srikant, Rayadurgam","Stolyar, Alexander"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-01-12T21:45:22Z","date_published":"2022-01-12T21:45:22Z","updated_at":"2026-07-22T22:24:52Z","subjects":["fair division, equilibrium computation, mixed manna"],"languages":["en"],"rights":["Copyright 2021 Peter McGlaughlin"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/112976","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Garg, Jugal","Beck, Carolyn","Srikant, Rayadurgam","Stolyar, Alexander"]},{"key":"dc:creator","label":"Author","values":["McGlaughlin, Peter"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-01-12T21:45:22Z","2021-06-30","2021-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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, equilibrium computation, mixed manna"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Peter McGlaughlin"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/112976"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["I study the age old problem of fair and efficient resource allocation. While many fairness notions exist, competitive equilibrium (CE) is often the most preferred as it satisfies multiple other fairness properties simultaneously. The approach creates a fictitious market for the items by endowing agents with virtual currency. In an equilibrium, aggregate demand equals aggregate supply when agents purchase utility maximizing bundles. My work explores two main directions: algorithms for computing CE of mixed manna (goods and bads), and applications to the fair division of indivisible goods. First, I examine the problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bars that everyone dislikes, as well as items that some like and other dislike. The seminal work of Bogomolnaia et al. (’17) argues why allocating a mixed manna is genuinely more complicated than a good or bad manna, and why CE is the best mechanism. They also prove the existence of equilibrium and establish its peculiar properties, e.g., non-convex and disconnected set of equilibria even under linear utilities, but leave the problem of computing an equilibrium open. My main result is a simplex-like algorithm based on Lemke’s scheme for computing a competitive allocation of a mixed manna under SPLC utilities. Experimental results on randomly generated instances suggest the algorithm will be fast in practice. The problem is known to be PPAD-hard for the case of good manna, and I also show a similar result for the case of bad manna. Given these PPAD-hardness results, designing such an algorithm is the only non-brute-force (non-enumerative) option known, e.g., the classical Lemke-Howson algorithm for computing a Nash equilibrium in a two player game is still the most widely used algorithm. My algorithm also yields several new structural properties of CE as simple corollaries. I obtain constructive proof of existence for a far more general setting, membership of the problem in PPAD, rational-valued solution, and odd number of solutions property (settling a conjecture of Bogomolnaia et al. in the affirmative). Furthermore, I show that if either the number of agents or the number of items is constant, then the number of pivots in the algorithm is strongly polynomial when the mixed manna contains only bads, providing additional evidence to the practicality of my approach. Second, I focus on the case of indivisible goods. Various fairness notions have been proposed with the rapidly growing field of fair division, but the Nash social welfare (NSW) serves as a focal point. In part, this follows from the ‘unreasonable’ fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously. However, existing approximation algorithms fail to satisfy all of the remarkable fairness guarantees offered by a max NSW allocation, instead targeting only the specific NSW objective. I address this issue by presenting a 2 max NSW, Prop-1, 1/(2n) MMS, and Pareto optimal allocation in strongly polynomial time. My techniques are based on a market interpretation of a fractional max NSW allocation. I present novel definitions of fairness concepts in terms of market prices, and design a new scheme to round a variation of a CE into an integral allocation in way that provides most of the fairness properties of an integral max NSW allocation.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Peter McGlaughlin, accepted the attached license on 2021-06-27 at 17:02.","The student, Peter McGlaughlin, submitted this Dissertation for approval on 2021-06-27 at 17:11.","This Dissertation was approved for publication on 2021-06-30 at 09:22.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16726 on 2022-01-12 at 12:43:39","Made available in DSpace on 2022-01-12T21:45:22Z (GMT). No. of bitstreams: 2 MCGLAUGHLIN-DISSERTATION-2021.pdf: 1166650 bytes, checksum: 0d3826cc75355eeb947f40ec0a0eb2c1 (MD5) LICENSE.txt: 4214 bytes, checksum: da9636b8f0fc9f8ab40bc6b03063d89f (MD5) Previous issue date: 2021-06-30"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Algorithms for fair division through competitive equilibrium"]}]}],"canonical_facts":{"dc:contributor":["Garg, Jugal","Beck, Carolyn","Srikant, Rayadurgam","Stolyar, Alexander"],"dc:creator":["McGlaughlin, Peter"],"dc:date":["2022-01-12T21:45:22Z","2021-06-30","2021-08"],"dc:description":["I study the age old problem of fair and efficient resource allocation. While many fairness notions exist, competitive equilibrium (CE) is often the most preferred as it satisfies multiple other fairness properties simultaneously. The approach creates a fictitious market for the items by endowing agents with virtual currency. In an equilibrium, aggregate demand equals aggregate supply when agents purchase utility maximizing bundles. My work explores two main directions: algorithms for computing CE of mixed manna (goods and bads), and applications to the fair division of indivisible goods. First, I examine the problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bars that everyone dislikes, as well as items that some like and other dislike. The seminal work of Bogomolnaia et al. (’17) argues why allocating a mixed manna is genuinely more complicated than a good or bad manna, and why CE is the best mechanism. They also prove the existence of equilibrium and establish its peculiar properties, e.g., non-convex and disconnected set of equilibria even under linear utilities, but leave the problem of computing an equilibrium open. My main result is a simplex-like algorithm based on Lemke’s scheme for computing a competitive allocation of a mixed manna under SPLC utilities. Experimental results on randomly generated instances suggest the algorithm will be fast in practice. The problem is known to be PPAD-hard for the case of good manna, and I also show a similar result for the case of bad manna. Given these PPAD-hardness results, designing such an algorithm is the only non-brute-force (non-enumerative) option known, e.g., the classical Lemke-Howson algorithm for computing a Nash equilibrium in a two player game is still the most widely used algorithm. My algorithm also yields several new structural properties of CE as simple corollaries. I obtain constructive proof of existence for a far more general setting, membership of the problem in PPAD, rational-valued solution, and odd number of solutions property (settling a conjecture of Bogomolnaia et al. in the affirmative). Furthermore, I show that if either the number of agents or the number of items is constant, then the number of pivots in the algorithm is strongly polynomial when the mixed manna contains only bads, providing additional evidence to the practicality of my approach. Second, I focus on the case of indivisible goods. Various fairness notions have been proposed with the rapidly growing field of fair division, but the Nash social welfare (NSW) serves as a focal point. In part, this follows from the ‘unreasonable’ fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously. However, existing approximation algorithms fail to satisfy all of the remarkable fairness guarantees offered by a max NSW allocation, instead targeting only the specific NSW objective. I address this issue by presenting a 2 max NSW, Prop-1, 1/(2n) MMS, and Pareto optimal allocation in strongly polynomial time. My techniques are based on a market interpretation of a fractional max NSW allocation. I present novel definitions of fairness concepts in terms of market prices, and design a new scheme to round a variation of a CE into an integral allocation in way that provides most of the fairness properties of an integral max NSW allocation.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Peter McGlaughlin, accepted the attached license on 2021-06-27 at 17:02.","The student, Peter McGlaughlin, submitted this Dissertation for approval on 2021-06-27 at 17:11.","This Dissertation was approved for publication on 2021-06-30 at 09:22.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16726 on 2022-01-12 at 12:43:39","Made available in DSpace on 2022-01-12T21:45:22Z (GMT). No. of bitstreams: 2 MCGLAUGHLIN-DISSERTATION-2021.pdf: 1166650 bytes, checksum: 0d3826cc75355eeb947f40ec0a0eb2c1 (MD5) LICENSE.txt: 4214 bytes, checksum: da9636b8f0fc9f8ab40bc6b03063d89f (MD5) Previous issue date: 2021-06-30"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/112976"],"dc:language":["en"],"dc:rights":["Copyright 2021 Peter McGlaughlin"],"dc:subject":["fair division, equilibrium computation, mixed manna"],"dc:title":["Algorithms for fair division through competitive equilibrium"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}