Abstract (EN)

We study a problem that generalizes the fair allocation of indivisible goods. The input is a matroid and a set of agents. Each agent has his own utility for every element of the matroid. Our goal is to build a base of the matroid and provide worst case guarantees on the additive utilities of the agents. These utilities are private, an assumption that is commonly made for the fair division of divisible resources, Since the use of an algorithm is not appropriate in this context, we resort to protocols, like in cake cutting problems. Our contribution is a protocol where the agents can interact and build a base of the matroid. If there are up to 8 agents, we show how everyone can ensure that his worst case utility for the resulting base is the same as those given by Markakis and Psomas [18] for the fair allocation of indivisible goods, based on the guarantees of Demko and Hill [8].