Loading…
Fair allocation of indivisible goods and chores
We consider the problem of fairly dividing a set of indivisible items. Much of the fair division literature assumes that the items are “goods” that yield positive utility for the agents. There is also some work in which the items are “chores” that yield negative utility for the agents. In this paper...
Saved in:
Published in: | Autonomous agents and multi-agent systems 2022-04, Vol.36 (1), Article 3 |
---|---|
Main Authors: | , , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | We consider the problem of fairly dividing a set of indivisible items. Much of the fair division literature assumes that the items are “goods” that yield positive utility for the agents. There is also some work in which the items are “chores” that yield negative utility for the agents. In this paper, we consider a more general scenario in which an agent may have positive or negative utility for each item. This framework captures, e.g., fair task assignment, where agents can experience both positive and negative utility for each task. We demonstrate that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations that satisfy certain fairness and efficiency properties and examine the complexity of computing such allocations. |
---|---|
ISSN: | 1387-2532 1573-7454 |
DOI: | 10.1007/s10458-021-09532-8 |