Prof. Milan Vlach presents Envy-free divisions

Undoubtedly, one of the oldest questions faced through the history of human
society is the problem of dividing a divisible object among a finite number of
individuals in such a way that every individual beliefs that he or she received
a fair piece. After formalization of the basic notions of object divisibility
and of division fairness, we mainly follow the history of mathematical and
computational models dealing with proportional and envy-free divisions. We
begin
with recalling the results of Steinhaus, Knaster, and Banach on proportional
solutions, the results of Dubins and Spanier on the existence of such
solutions,
and extensions of the existence results obtained by Sagara and Vlach for
envy-freeness in situations that permit infinite number of individuals and
nonadditive preferences. Then we present recent results of Woeginger and Sgall,
Edmonds and Pruhs, and Procaccia, which show that, for a fairly general model
of
computation, achieving envy-freeness is provably harder than achieving
proportionality, and that we now understand the case of proportionality much
better than that of envy-freeness.

In particular, we know that there exist fast finite discrete proportional
procedures whose number of steps can be bounded by a function that depends on
the number of individuals and not on the individual preferences. On the other
hand, until very recently, it was generally believed that no such a procedure
exists for envy-freeness. We conclude with a brief discussion of the recent
claim of Aziz and Mackenzie that such a procedure exists. The gap between known
lower bounds and the upper bound of the Aziz and Mackenzie procedure is
extremely wide, and we can therefore expect a lot of improvements possibly
leading to a practical method, provided the result is correct.