Efficiency and Sequenceability in Fair Division of Indivisible Goods with Additive Preferences
In fair division of indivisible goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is the following: at each stage, a designated agent picks one object among those that remain. This paper, restricted to the case where the agents have numerical additive preferences over objects, revisits to some extent the seminal paper by Brams and King [9] which was specific to ordinal and linear order preferences over items. We point out similarities and differences with this latter context. In particular, we show that any Pareto-optimal allocation (under additive preferences) is sequenceable, but that the converse is not true anymore. This asymmetry leads naturally to the definition of a "scale of efficiency" having three steps: Pareto-optimality, sequenceability without Pareto-optimality, and non-sequenceability. Finally, we investigate the links between these efficiency properties and the "scale of fairness" we have described in an earlier work [7]: we first show that an allocation can be envy-free and non-sequenceable, but that every competitive equilibrium with equal incomes is sequenceable. Then we experimentally explore the links between the scales of efficiency and fairness.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessSimilar Papers 제목 키워드 기반
Efficiency, Sequenceability and Deal-Optimality in Fair Division of Indivisible Goods
In fair division of indivisible goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is as follows: at each stage, a designated agent picks one object among …
FairnessFair Division Under Cardinality Constraints
We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of goods---i.e., the goods …
FairnessChore division on a graph
The paper considers fair allocation of indivisible nondisposable items that generate disutility (chores). We assume that these items are placed in the vertices of a graph and each agent's share has to form a connected su…
Temporal Fair Division of Indivisible Items
We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results in achieving approximat…
Honor Among Bandits: No-Regret Learning for Online Fair Division
We consider the problem of online fair division of indivisible goods to players when there are a finite number of types of goods and player values are drawn from distributions with unknown means. Our goal is to maximize …
FairnessMulti-Armed Bandits