15 February 2006, Computational Social Choice Seminar, Vangelis Markakis

We study the problem of fairly allocating a set of indivisible goods to a set of people from an algorithmic perspective. Fair division has been a central topic in the economic literature and several concepts of fairness have been suggested. We use as a measure of fairness the envy between any pair of players. In our model, a monotone utility function is associated with every agent specifying the value of each subset of the goods for the agent. An allocation is envy-free if every player prefers her own share than the share of any other player.

When the goods are divisible, envy-free allocations always exist. In the presence of indivisibilities, we show that there exist allocations in which the envy is bounded by the maximum marginal utility, and present a simple algorithm for computing such allocations. We then look at the optimization problem of finding an allocation with minimum possible envy. In the general case the problem is not solvable or approximable in polynomial time, unless P=NP. We consider natural special cases (e.g. additive utilities) which are closely related to a class of job scheduling problems and present approximation algorithms as well as inapproximability results.

This is joint work with Richard Lipton, Elchanan Mossel and Amin Saberi.

For more information, see http://www.illc.uva.nl/~ulle/seminar/, or contact either Krzysztof Apt (apt at cwi.nl) or Ulle Endriss (ulle at illc.uva.nl).