A Matroid Approach to the Worst Case Allocation of Indivisible Goods / 136
Laurent Gourvès, Jérôme Monnot, Lydia Tlilane

We consider the problem of equitably allocating a set of indivisible goods to n agents so as to maximize the utility of the least happy agent. Demko and Hill sowed in [Demko, S., and Hill, T. P. (1988). Equitable distribution of indivisible objects. Mathematical Social Sciences, 16(2), 145-158.] the existence of an allocation where every agent values his share at least V_n(α), which is a family of nonincreasing functions in a parameter α, defined as the maximum value assigned by an agent to a single good. A deterministic algorithm returning such an allocation in polynomial time was proposed in [Markakis, E., & Psomas, C. A. (2011). On worst-case allocations in the presence of indivisible goods. In Workshop Internet and Network Economics (pp. 278-289). Springer Berlin Heidelberg.]. Interestingly, V_n(α) is tight for some values of α, i.e. it is the best lower bound on the valuation of the least happy agent. However, it is not true for all values of α. We propose a family of functions W_n such that W_n(x) ≥ V_n(x) for all x, and W_n(x) ≥ V_n(x) for values of x where V_n(x) is not tight. The new functions W_n apply on a problem which generalizes the allocation of indivisible goods. It is to find a solution (base) in a matroid which is common to n agents. Our results are constructive, they are achieved by analyzing an extension of the algorithm of Markakis and Psomas.