Author name cluster

Lydia Tlilane

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

TCS Journal 2015 Journal Article

Worst case compromises in matroids with applications to the allocation of indivisible goods

Laurent Gourvès
Jérôme Monnot
Lydia Tlilane

We consider the problem of equitably allocating a set of indivisible goods to n agents with additive utilities so as to provide worst case guarantees on agents' utilities. Demko and Hill [6] showed the existence of an allocation where every agent values his share at least V n ( α ), which is a family of nonincreasing functions of α, 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 [15]. Interestingly, V n ( α ) is tight for some values of α, i. e. it matches the highest possible utility of the least happy agent. However, this 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 functions W n apply on a problem that generalizes the allocation of indivisible goods. It is to find a 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. We also present an upper bound on the utility of the least happy agent.

Details DOI

ECAI Conference 2014 Conference Paper

Near Fairness in Matroids

Laurent Gourvès
Jérôme Monnot
Lydia Tlilane

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.

Details

IJCAI Conference 2013 Conference Paper

A Matroid Approach to the Worst Case Allocation of Indivisible Goods

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, 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.

PDF Details DOI

ECAI Conference 2012 Conference Paper

Approximate Tradeoffs on Matroids

Laurent Gourvès
Jérôme Monnot
Lydia Tlilane

We consider problems where a solution is evaluated with a couple. Each coordinate of this couple represents an agent's utility. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for both agents. Then, a natural aim is to find tradeoffs. We investigate tradeoff solutions with guarantees for the agents. The focus is on discrete problems having a matroid structure. We provide polynomial-time deterministic algorithms which achieve several guarantees and we prove that some guarantees are not possible to reach.

Details