Algorithmic Stability in Fair Allocation of Indivisible Goods Among Two Agents
Many allocation problems in multiagent systems rely on agents specifying cardinal preferences. However, allocation mechanisms can be sensitive to small perturbations in cardinal preferences, thus causing agents who make `small" or `innocuous" mistakes while reporting their preferences to experience a large change in their utility for the final outcome. To address this, we introduce a notion of algorithmic stability and study it in the context of fair and efficient allocations of indivisible goods among two agents. We show that it is impossible to achieve exact stability along with even a weak notion of fairness and even approximate efficiency. As a result, we propose two relaxations to stability, namely, approximate-stability and weak-approximate-stability, and show how existing algorithms in the fair division literature that guarantee fair and efficient outcomes perform poorly with respect to these relaxations. This leads us to explore the possibility of designing new algorithms that are more stable. Towards this end, we present a general characterization result for pairwise maximin share allocations, and in turn use it to design an algorithm that is approximately-stable and guarantees a pairwise maximin share and Pareto optimal allocation for two agents. Finally, we present a simple framework that can be used to modify existing fair and efficient algorithms in order to ensure that they also achieve weak-approximate-stability.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessVocal Bursts Valence PredictionSimilar Papers 제목 키워드 기반
Fair 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 …
FairnessPROPm Allocations of Indivisible Goods to Multiple Agents
We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocati…
FairnessA Characterization of Maximum Nash Welfare for Indivisible Goods
In the allocation of indivisible goods, the maximum Nash welfare (MNW) rule, which chooses an allocation maximizing the product of the agents' utilities, has received substantial attention for its fairness. We characteri…
FairnessAlmost Group Envy-free Allocation of Indivisible Goods and Chores
We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established in the literature and…
FairnessGroupwise Maximin Fair Allocation of Indivisible Goods
We study the problem of allocating indivisible goods among n agents in a fair manner. For this problem, maximin share (MMS) is a well-studied solution concept which provides a fairness threshold. Specifically, maximin sh…
Fairness