There exists a discrete bounded envy-free cake cutting protocol for any number of agents

You need to know: Algorithm.

Background: Let us call interval $[0,1]$ a cake, and any finite union of subintervals of $[0,1]$ – a piece of cake. Let ${\cal X}$ be the set of all pieces of cake. Let $N=\{1,\dots,n\}$ be the set of agents, each agent i having its own valuation function $V_i:{\cal X}\to[0,\infty)$ such that (i) $V_i(X\cup X')=V_i(X)+V_i(X')$ for all disjoint $X, X' \in {\cal X}$ , and (ii) for every $X\in {\cal X}$ and $0\leq \lambda\leq 1$ , there exists $X'\subset X$ in ${\cal X}$ with $V_i(X') = \lambda V_i(X)$ . A cake allocation is a partition $[0,1]=\bigcup\limits_{i=1}^n X_i$ into disjoint pieces $X_i\in{\cal X}$ . We say that agent i is envious if $V_i(X_i)<V_i(X_j)$ for some j. A discrete protocol is an algorithm which returns an allocation after a sequence of queries which either (1) for given $x \in [0,1]$ and $r \geq 0$ , ask agent i to return a point $y\in[0,1]$ such that $V_i([x,y])=r$ (CUT query), or (2) for given $x,y\in[0,1]$ , ask agent i to return $V_i([x,y])$ (EVALUATE query). A protocol is called envy-free if no agent is envious if he/she follows the protocol truthfully. A protocol is bounded if the number of queries required to return a solution is bounded by a constant $C=C(n)$ depending only on n but not on $V_i$ .

The Theorem: On 13th April 2016, Haris Aziz and Simon Mackenzie submitted to arxiv a paper in which they proved the existence of a discrete bounded envy-free cake cutting protocol for any number of agents.

Short context: Cake cutting is a metaphor for the allocation of a heterogeneous divisible good among multiple agents with possibly different preferences over different parts of the cake. The existence of a discrete and bounded envy-free cake cutting protocol was the central open problem in this area. Such protocol is easy to $n\leq 3$ . In 2015, Aziz and Mackenzie solved the problem for $n=4$ . The Theorem solves it for all n.