Abstract | ||
---|---|---|
This article deals with the fair allocation of indivisible goods and its generalization to matroids. The notions of fairness under consideration are equitability, proportionality and envy-freeness. It is long known that some instances fail to admit a fair allocation. However, an almost fair solution may exist if an appropriate relaxation of the fairness condition is adopted. This article deals with a matroid problem which comprises the allocation of indivisible goods as a special case. It is to find a base of a matroid and to allocate it to a pool of agents. We first adapt the aforementioned fairness concepts to matroids. Next we propose a relaxed notion of fairness said to be near to fairness. Near fairness respects the fairness up to one element. We show that a nearly fair solution always exists and it can be constructed in polynomial time in the general context of matroids. |
Year | DOI | Venue |
---|---|---|
2014 | 10.3233/978-1-61499-419-0-393 | FRONTIERS IN ARTIFICIAL INTELLIGENCE AND APPLICATIONS |
Keywords | DocType | Volume |
matroids | Conference | 263 |
ISSN | Citations | PageRank |
0922-6389 | 1 | 0.36 |
References | Authors | |
10 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Laurent Gourvès | 1 | 241 | 30.97 |
Jérôme Monnot | 2 | 512 | 55.74 |
Lydia Tlilane | 3 | 23 | 2.93 |