Sequential resource allocation

Having a set of indivisible objects (say, candies) in the hand, how would you allocate them fairly to a set of agents (say, children) without bothering to ask them their preferences ?

The easiest way to proceed is probably to ask the agents in turn to take their most preferred item among those that remain. Of course the first one to choose has a clear advantage, but this can be compensated for example by the fact that the last one is allowed to pick two objects while the first one is only allowed to pick one. For example, the sequence [1, 2, 2] (the first agent chooses first, then the second agent picks the two remaining objects) is probably fairer than the sequence [1, 1, 2]. Then the question is: What is the best sequence ?

This page is dedicated to this problem. The formal model is described in the paper below. The small applet at the bottom of the page computes optimal sequences for given instances of the problem.

The paper

Paper - Long version
Click on the icon to download the long version of the paper, with proofs and examples added.
[Download]

The applet

This small Scala applet computes an optimal allocation sequence. All you have to do is to fill-in the input boxes and click the button.

Remarks: Your browser must be able to interpret Java applets, otherwise it will not work. This program has been tested with Java 1.6. It may or may not work with previous versions of the Java Virtual Machine.

Sorry, this browser does not understand applets or they are not enabled.