Files in this item
Files  Description  Format 

application/pdf MURHEKARTHESIS2020.pdf (480kB)  (no description provided) 
Description
Title:  Algorithms and complexity results for problems on fair division and imitation games 
Author(s):  Murhekar, Aniket 
Advisor(s):  Garg, Jugal; Mehta, Ruta 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  M.S. 
Genre:  Thesis 
Subject(s):  fair division
indivisible goods envyfreeness public goods Nash Social Welfare imitation games Nash equilibrium 
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 envyfreeness up to one good (EF1) and envyfreeness up to any good (EFX) in conjuction with Paretooptimality (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.067approximation 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 NPhard, even where there are at most two nonzero 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 NPhard, even when the valuations are all binary. Next, we present a linearfactor approximation algorithm and polynomial time algorithms when the number of agents or the number of goods to be picked is constant. Finally we present NSWpreserving 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 PPADhard, where $n$ is the number of moves available to the players. On the other hand, we design a polynomialtime 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$. 
Issue Date:  20200720 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/108721 
Rights Information:  Copyright 2020 Aniket Murhekar 
Date Available in IDEALS:  20201007 
Date Deposited:  202008 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois