In this article we propose a probabilistic framework in order to study the fair division of a divisible good, e.g. a cake, between n players. Our framework corresponds to the “Full independence model" used in the study of fair division of indivisible goods. We show that, if we consider a uniform distribution in this framework, then there exists an envy-free division algorithm satisfying the following probability estimate: \(\begin{aligned} \mathbb {P}\left( C\left( \mu _1, \ldots ,\mu _n\right) \ge n^{7+b}\right) = \mathcal {O}\left( n^{-\frac{b-1}{3}+1+o(1)}\right) , \end{aligned}\) where \(\mu _1,\ldots , \mu _n\) correspond to the preferences of the n players, \(C(\mu _1, \ldots ,\mu _n)\) is the number of queries used by the algorithm and \(b>4\) . In particular, this gives \(\begin{aligned} \lim _{n \rightarrow + \infty }\mathbb {P}\left( C(\mu _1, \ldots ,\mu _n) \ge n^{12}\right) = 0. \end{aligned}\) It must be noticed that nowadays few things are known about the complexity of envy-free division algorithms. Indeed, Procaccia has given a lower bound in \(\Omega (n^2)\) and Aziz and Mackenzie have given an upper bound in \(n^{n^{n^{n^{n^{n}}}}}\) . As our estimate means that we have \(C(\mu _1, \ldots , \mu _n)<n^{12}\) with a high probability, this gives a new insight on the complexity of envy-free cake cutting algorithms. Our result follows from a study of Webb’s algorithm and a theorem of Tao and Vu about the smallest singular value of a random matrix.
