An Exponential Envy-Free Cake Cutting Protocol for n Agents

06/06/2023

∙

by   Georgy Sokolov, et al.

∙

0

∙

share

We consider a classical envy-free cake cutting problem. The first limited protocol was proposed by Aziz and McKenzie in 2016 arXiv:1604.03655. The disadvantage of this protocol is its high complexity. The authors proved that the maximum number of queries required by the protocol is n^n^n^n^n^n. We made minor changes to the Aziz-Mackenzie protocol, improved estimation of the required number of queries and made an algorithm that uses at most n^8n^2(1 + o(1)) queries.