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