Fair Allocation of Indivisible Goods and Chores
Fair Allocation of Indivisible Goods and Chores
Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, Toby Walsh
Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 53-59.
https://doi.org/10.24963/ijcai.2019/8
We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are ``goods'' i.e., they yield positive utility for the agents. There is also some work where the items are ``chores'' that yield negative utility for the agents. In this paper, we consider a more general scenario where an agent may have negative or positive utility for each item. This framework captures, e.g., fair task assignment, where agents can have both positive and negative utilities for each task. We show 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 satisfying certain fairness and efficiency properties and further study the complexity of computing such allocations.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Resource Allocation