[4]: 83–87 For convenience we normalize the valuations such that the value of the entire cake is n for all agents.
One player chosen arbitrarily, called the divider, cuts the cake into n pieces whose value in his/her eyes is exactly 1.
Construct a bipartite graph G = (X + Y, E) in which each vertex in X is an agent, each vertex in Y is a piece, and there is an edge between an agent x and a piece y iff x values y at least 1.
Find a maximum-cardinality envy-free matching in G. Note that the divider is adjacent to all n pieces, so |NG(X)| = n ≥ |X| (where NG(X) is the set of neighbors of X in Y).
Note that each matched agent has a value of at least 1, and thus goes home happily.
Note that each remaining agent values each piece given away at less than 1, so he values the remaining cake at more than the number of agents, so the precondition for recursion is satisfied.