{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/108721"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/108721","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Algorithms and complexity results for problems on fair division and imitation games","abstract":"\"We study the problem of allocating indivisible goods to agents in a fair and efficient manner. We consider different notions of fairness such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) in conjuction with Pareto-optimality (PO). We present polynomial time algorithms for computing allocations that are EF1 and PO when (i) the number of agents is constant, and (ii) the number of different values that every agent has for the goods is constant. We also show that when there are exactly two values for the goods, an allocation that is EFX, PO and gives a 1.067-approximation to the Nash Social Welfare (NSW) can be computed in polynomial time. We also present algorithms that satisfy a different notions of fairness, like equitability up to one good (EQ1), and equitability up to any good (EQX) along with PO in some of these cases. On the complexity front, we show that the problem of computing EF1 and PO allocations belongs to class PLS. Further we show that deciding if EFX and PO allocations exist is NP-hard, even where there are at most two non-zero values for the goods. We next consider the problem of computing the Nash Social Welfare maximizing allocation for the case of public goods subject to a cardinality constraint. We show that the NSW problem is NP-hard, even when the valuations are all binary. Next, we present a linear-factor approximation algorithm and polynomial time algorithms when the number of agents or the number of goods to be picked is constant. Finally we present NSW-preserving reductions from the model of private goods to that of public goods, and from the public goods model to that of public decision making, thus showing how the models are related. Lastly, we study the problem of computing approximate Nash equilibria in imitation games. An imitation game is represented by two payoff matrices $(A,B)$, in which $B$ is the identity matrix, implying that the second player gets a positive payoff only if she ``imitates\"\" the first. We show that much like the general case, for any $c>0$, computing a $\\frac{1}{n^c}$-approximate NE of imitation games remains PPAD-hard, where $n$ is the number of moves available to the players. On the other hand, we design a polynomial-time algorithm to find $\\epsilon$-approximate NE for any given constant $\\epsilon>0$ (PTAS). The former result also rules out the smooth complexity being in $\\Ptime$, unless $\\PPAD \\subset \\RP$.\"","abstract_html":"&quot;We study the problem of allocating indivisible goods to agents in a fair and efficient manner. We consider different notions of fairness such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) in conjuction with Pareto-optimality (PO). We present polynomial time algorithms for computing allocations that are EF1 and PO when (i) the number of agents is constant, and (ii) the number of different values that every agent has for the goods is constant. We also show that when there are exactly two values for the goods, an allocation that is EFX, PO and gives a 1.067-approximation to the Nash Social Welfare (NSW) can be computed in polynomial time. We also present algorithms that satisfy a different notions of fairness, like equitability up to one good (EQ1), and equitability up to any good (EQX) along with PO in some of these cases. On the complexity front, we show that the problem of computing EF1 and PO allocations belongs to class PLS. Further we show that deciding if EFX and PO allocations exist is NP-hard, even where there are at most two non-zero values for the goods. We next consider the problem of computing the Nash Social Welfare maximizing allocation for the case of public goods subject to a cardinality constraint. We show that the NSW problem is NP-hard, even when the valuations are all binary. Next, we present a linear-factor approximation algorithm and polynomial time algorithms when the number of agents or the number of goods to be picked is constant. Finally we present NSW-preserving reductions from the model of private goods to that of public goods, and from the public goods model to that of public decision making, thus showing how the models are related. Lastly, we study the problem of computing approximate Nash equilibria in imitation games. An imitation game is represented by two payoff matrices $(A,B)$, in which $B$ is the identity matrix, implying that the second player gets a positive payoff only if she ``imitates&quot;&quot; the first. We show that much like the general case, for any $c&gt;0$, computing a <span class=\"etd-inline-math\">\\frac{1}{n<sup>c</sup>}</span>-approximate NE of imitation games remains PPAD-hard, where $n$ is the number of moves available to the players. On the other hand, we design a polynomial-time algorithm to find <span class=\"etd-inline-math\">&epsilon;</span>-approximate NE for any given constant <span class=\"etd-inline-math\">&epsilon;&gt;0</span> (PTAS). The former result also rules out the smooth complexity being in $\\Ptime$, unless $\\PPAD \\subset \\RP$.&quot;","abstract_has_math":true,"creators":["Murhekar, Aniket"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Garg, Jugal","Mehta, Ruta"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2020,"date_issued":"2020-10-07T22:50:05Z","date_published":"2020-10-07T22:50:05Z","updated_at":"2026-07-22T22:24:48Z","subjects":["fair division","indivisible goods","envy-freeness","public goods","Nash Social Welfare","imitation games","Nash equilibrium"],"languages":["en"],"rights":["Copyright 2020 Aniket Murhekar"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/108721","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Garg, Jugal","Mehta, Ruta"]},{"key":"dc:creator","label":"Author","values":["Murhekar, Aniket"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2020-10-07T22:50:05Z","2022-10-07T22:50:13Z","2020-07-20","2020-08"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"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","indivisible goods","envy-freeness","public goods","Nash Social Welfare","imitation games","Nash equilibrium"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2020 Aniket Murhekar"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/108721"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"We study the problem of allocating indivisible goods to agents in a fair and efficient manner. We consider different notions of fairness such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) in conjuction with Pareto-optimality (PO). We present polynomial time algorithms for computing allocations that are EF1 and PO when (i) the number of agents is constant, and (ii) the number of different values that every agent has for the goods is constant. We also show that when there are exactly two values for the goods, an allocation that is EFX, PO and gives a 1.067-approximation to the Nash Social Welfare (NSW) can be computed in polynomial time. We also present algorithms that satisfy a different notions of fairness, like equitability up to one good (EQ1), and equitability up to any good (EQX) along with PO in some of these cases. On the complexity front, we show that the problem of computing EF1 and PO allocations belongs to class PLS. Further we show that deciding if EFX and PO allocations exist is NP-hard, even where there are at most two non-zero values for the goods. We next consider the problem of computing the Nash Social Welfare maximizing allocation for the case of public goods subject to a cardinality constraint. We show that the NSW problem is NP-hard, even when the valuations are all binary. Next, we present a linear-factor approximation algorithm and polynomial time algorithms when the number of agents or the number of goods to be picked is constant. Finally we present NSW-preserving reductions from the model of private goods to that of public goods, and from the public goods model to that of public decision making, thus showing how the models are related. Lastly, we study the problem of computing approximate Nash equilibria in imitation games. An imitation game is represented by two payoff matrices $(A,B)$, in which $B$ is the identity matrix, implying that the second player gets a positive payoff only if she ``imitates\"\" the first. We show that much like the general case, for any $c>0$, computing a $\\frac{1}{n^c}$-approximate NE of imitation games remains PPAD-hard, where $n$ is the number of moves available to the players. On the other hand, we design a polynomial-time algorithm to find $\\epsilon$-approximate NE for any given constant $\\epsilon>0$ (PTAS). The former result also rules out the smooth complexity being in $\\Ptime$, unless $\\PPAD \\subset \\RP$.\"","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2022-08-01","The student, Aniket Murhekar, accepted the attached license on 2020-07-17 at 20:25.","The student, Aniket Murhekar, submitted this Thesis for approval on 2020-07-17 at 20:34.","This Thesis was approved for publication on 2020-07-20 at 10:18.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15689 on 2020-10-02 at 15:51:47","Made available in DSpace on 2020-10-07T22:50:05Z (GMT). No. of bitstreams: 2 MURHEKAR-THESIS-2020.pdf: 479836 bytes, checksum: 9b218fda07cba3a8d088ffdfa2255d91 (MD5) LICENSE.txt: 4212 bytes, checksum: 27635a26a37e7e16ffcd5eed856a1b62 (MD5) Previous issue date: 2020-07-20","Embargo set by: Seth Robbins for item 116350 Lift date: 2022-10-07T22:50:13Z Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","Author requested closed access (OA after 2yrs) in Vireo ETD system","Limited"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Algorithms and complexity results for problems on fair division and imitation games"]}]}],"canonical_facts":{"dc:contributor":["Garg, Jugal","Mehta, Ruta"],"dc:creator":["Murhekar, Aniket"],"dc:date":["2020-10-07T22:50:05Z","2022-10-07T22:50:13Z","2020-07-20","2020-08"],"dc:description":["\"We study the problem of allocating indivisible goods to agents in a fair and efficient manner. We consider different notions of fairness such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) in conjuction with Pareto-optimality (PO). We present polynomial time algorithms for computing allocations that are EF1 and PO when (i) the number of agents is constant, and (ii) the number of different values that every agent has for the goods is constant. We also show that when there are exactly two values for the goods, an allocation that is EFX, PO and gives a 1.067-approximation to the Nash Social Welfare (NSW) can be computed in polynomial time. We also present algorithms that satisfy a different notions of fairness, like equitability up to one good (EQ1), and equitability up to any good (EQX) along with PO in some of these cases. On the complexity front, we show that the problem of computing EF1 and PO allocations belongs to class PLS. Further we show that deciding if EFX and PO allocations exist is NP-hard, even where there are at most two non-zero values for the goods. We next consider the problem of computing the Nash Social Welfare maximizing allocation for the case of public goods subject to a cardinality constraint. We show that the NSW problem is NP-hard, even when the valuations are all binary. Next, we present a linear-factor approximation algorithm and polynomial time algorithms when the number of agents or the number of goods to be picked is constant. Finally we present NSW-preserving reductions from the model of private goods to that of public goods, and from the public goods model to that of public decision making, thus showing how the models are related. Lastly, we study the problem of computing approximate Nash equilibria in imitation games. An imitation game is represented by two payoff matrices $(A,B)$, in which $B$ is the identity matrix, implying that the second player gets a positive payoff only if she ``imitates\"\" the first. We show that much like the general case, for any $c>0$, computing a $\\frac{1}{n^c}$-approximate NE of imitation games remains PPAD-hard, where $n$ is the number of moves available to the players. On the other hand, we design a polynomial-time algorithm to find $\\epsilon$-approximate NE for any given constant $\\epsilon>0$ (PTAS). The former result also rules out the smooth complexity being in $\\Ptime$, unless $\\PPAD \\subset \\RP$.\"","Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2022-08-01","The student, Aniket Murhekar, accepted the attached license on 2020-07-17 at 20:25.","The student, Aniket Murhekar, submitted this Thesis for approval on 2020-07-17 at 20:34.","This Thesis was approved for publication on 2020-07-20 at 10:18.","DSpace SAF Submission Ingestion Package generated from Vireo submission #15689 on 2020-10-02 at 15:51:47","Made available in DSpace on 2020-10-07T22:50:05Z (GMT). No. of bitstreams: 2 MURHEKAR-THESIS-2020.pdf: 479836 bytes, checksum: 9b218fda07cba3a8d088ffdfa2255d91 (MD5) LICENSE.txt: 4212 bytes, checksum: 27635a26a37e7e16ffcd5eed856a1b62 (MD5) Previous issue date: 2020-07-20","Embargo set by: Seth Robbins for item 116350 Lift date: 2022-10-07T22:50:13Z Reason: Author requested closed access (OA after 2yrs) in Vireo ETD system","Author requested closed access (OA after 2yrs) in Vireo ETD system","Limited"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/108721"],"dc:language":["en"],"dc:rights":["Copyright 2020 Aniket Murhekar"],"dc:subject":["fair division","indivisible goods","envy-freeness","public goods","Nash Social Welfare","imitation games","Nash equilibrium"],"dc:title":["Algorithms and complexity results for problems on fair division and imitation games"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:48Z"}