PhD Dissertation Proposal: Vignesh Viswanathan, Fair Allocation of Indivisible Items: New Algorithms and Hardness Results
Content
Speaker:
Abstract:
The problem of how to fairly divide a set of indivisible items among a set of heterogeneous agents is a fundamental problem in computational economics. This problem models several important applications like job scheduling, reviewer allocation and course allocation. In this thesis, I focus on the computability of allocations which maximize well known fairness objectives. Specifically, most of this thesis presents algorithms and hardness results for the Nash social welfare and egalitarian welfare objectives. Rather unfortunately, the problem of computing fair allocations is computationally intractable for most natural fairness objectives. We work around this in two ways.
In the first part of this thesis, we identify cases where fair allocations can be computed efficiently. We identify a class of valuation functions we refer to as simple submodular valuations, for which several fairness objectives can be achieved in polynomial time. We complement this set of results by presenting lower bounds which show that for all the cases where we do not present polynomial time algorithms, the problem of computing fair allocations is computationally intractable.
In the second part of this thesis, we study the approximability of fair allocations under general (but linear) valuation functions. We show that there is some constant c > 0, such that there exists an (e^{1/e} - c)-approximation algorithm for the max Nash welfare problem, which improves on the previous best known approximation factor of e^{1/e}. We also improve the best known lower bound, showing that the max Nash welfare problem cannot be approximated by a factor better than 1.076 unless the unique games conjecture is false. This improves on the previous best known inapproximability factor of 1.069.
Advisor:
Yair Zick