2017/06/20 by Ariel D. Procaccia, Junxing Wang · 2 citations
Economics, Econometrics and Finance · Decision Sciences · #Game Theory and Voting Systems #Auction Theory and Applications #Game Theory and Applications
paper · doi:10.1145/3033274.3085107
openalex publication_date 2017/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We are interested in the problem of dividing a cake -- a heterogeneous divisible good -- among n players, in a way that is ε-equitable: every pair of players must have the same value for their own allocated pieces, up to a difference of at most ε. It is known that such allocations can be computed using O(n ln(1/ε)) operations in the standard Robertson-Webb Model. We establish a lower bound of Ω(ln(1/ε)/lnln(1/ε)) on the complexity of this problem, which is almost tight for a constant number of players. Importantly, our result implies that allocations that are exactly equitable cannot be computed.