English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this article we propose a probabilistic framework in order to study thefair division of a divisible good, e.g., a cake, between n players. Ourframework follows the same idea than the ''Full independence model'' used inthe study of fair division of indivisible goods. We show that, in thisframework, there exists an envy-free division algorithm satisfying thefollowing probability estimate:$$\mathbb{P}\big( C(\mu_1, \ldots,\mu_n) \geqn^{7+b}\big) = \mathcal{O}\Big(n^{-\frac{b-1}{3}+1+o(1)}\Big),$$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 algorithmand $b>4$. In particular, this gives$$\lim_{n \rightarrow +\infty}\mathbb{P}\big( C(\mu_1, \ldots,\mu_n) \geq n^{12}\big) = 0.$$ It mustbe noticed that nowadays few things are known about the complexity of envy-freedivision 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$. Asour estimate means that we have $C(\mu_1, \ldots, \mu_n)<n^{12}$ with a highprobability, this gives a new insight on the complexity of envy-free cakecutting algorithms. Our result follows from a study of Webb's algorithm and atheorem of Tao and Vu about the smallest singular value of a random matrix.

Envy-free cake cutting: A polynomial number of queries with high probability