Abstract
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