A Matroid Approach to the Worst Case Allocation of Indivisible Goods

摘要

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,1988] showed the existence of an allocation where every agent values his share at least Vn(α),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 [Markakis and Psomas,2011].Interestingly,Vn(α) 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 Wn such that Wn(x) ≥ Vn(x) for all x,and Wn(x) ＞ Vn(x) for values of x where Vn(x) is not tight.The new functions Wn 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.