Paper Info
Title
A matroid approach to the worst case allocation of indivisible goods
Abstract
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.
Year
Venue
Keywords
2013
IJCAI
maximum value,deterministic algorithm,worst case allocation,new function,indivisible goods,happy agent,polynomial time,nonincreasing function,matroid approach
Field
DocType
Citations 
Matroid,Discrete mathematics,Constructive,Upper and lower bounds,Deterministic algorithm,Time complexity,Mathematics
Conference
10
PageRank 
References 
Authors
0.59
10
3
Name
Order
Citations
PageRank
Laurent Gourvès124130.97
Jérôme Monnot251255.74
Lydia Tlilane3232.93