Lunch In Theory This Thursday (12:00 PM, 04/23, GCS 302c)
Devansh Gupta
Title: Learning Fair Allocation of Indivisible Items from Limited Feedback
Abstract: We study a setting in which an algorithm must output a fair allocation of indivisible items while “learning on the job”. More specifically, the algorithm is to output an allocation satisfying EF1, PROP1, or similar fairness notions; however, the algorithm initially has no information about the agents’ valuations, and can only learn about them by (repeatedly) proposing an allocation, and obtaining feedback about a fairness violation in the proposed allocation. Importantly, the observed fairness violation may be adversarially chosen. The algorithm’s goal is to converge to a fair allocation in a number of rounds polynomial in the number of agents and items, and ideally to also involve only a polynomial amount of computation.
We prove two main results: first, when the valuations are additive, then even for mixed items (goods and chores), an allocation satisfying EF1 or PROP1 can be found in polynomial time using the corresponding feedback. These results are instantiations of a more general framework which maintains a polytope of candidate valuations consistent with all past feedback. The algorithm repeatedly constructs putative valuations and uses them to propose allocations; the observed violations then define separating hyperplanes, allowing the algorithm to emulate the ellipsoid method.
When the valuations are monotone, but not necessarily additive, our results are more subtle. We present an algorithm which is guaranteed to find an EF1 allocation in a number of iterations which is polynomial in the number of agents and items; however, the internal calculations of the algorithm are not guaranteed to be polynomial. The algorithm again maintains putative valuations, and only considers allocations in which each agent obtains the union of an interval plus one additional item with respect to an (arbitrary) ordering of the items. We (non-constructively) prove that there always exist EF1 allocations of this form, allowing us to use a further generalization of the preceding ellipsoid-based ideas. However, because the existence proof is non-constructive, the internal step of constructing an allocation from the putative valuations is not known to take polynomial time.
Finally, we consider weaker and stronger feedback models. When the algorithm only learns whether the allocation satisfies the fairness notion, but does not obtain further information on specific violations, we show that any algorithm must in the worst case take a number of iterations exponential in the number of agents; this result is matched by showing that for a constant number of agents, a fair allocation can be found in a polynomial number of iterations. If the algorithm learns of all violations of the proposed allocation, then even for general monotone valuations, a fair allocation can be found in polynomial time, by straightforwardly emulating the Envy-Cycle Elimination Algorithm.