AAMAS Tutorial on Fair Division
Resource allocation has always been a central topic of concern in the multiagent systems research community. Mechanisms for dividing a set of goods amongst several agents need to balance (economic) efficiency and fairness requirements. For instance, for an allocation to be efficient we may want it to maximise the sum of individual agent utilities, while a common interpretations of fairness is envy-freeness: no agent should prefer someone else's bundle of goods to their own lot. While efficiency issues are routinely being addressed in multiagent systems research, fairness is only just starting to receive broad attention.
This tutorial, to be held at the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2008), will be an introduction to fair division for multiagent systems researchers.
The tutorial will cover three main topics:
- What makes a good allocation of goods to agents?
A number of different criteria have been proposed in the literature, which
can roughly be divided into fairness and efficiency criteria.
We will give an overview of these, covering concepts such as
collective utility functions, social welfare orderings, and
envy-freeness. We will also briefly discuss the axiomatic
foundations of social welfare orderings.
- In terms of algorithms we will first address the case of divisible goods.
The classical example from the fair division literature is the
problem of dividing a cake (a single divisible good) amongst
several players. We will review several
cake-cutting procedures and analyse their properties.
- Finally, we will discuss the allocation of indivisible goods.
Recent work on resource allocation problems in multiagent systems
has mostly concentrated on this kind of scenario,
which gives rise to a combinatorial optimisation problem.
Amongst other things we will discuss distributed approaches based
on negotiation for finding fair and efficient allocations.