2025/04/26 by Jojić, Duško, Panina, Gaiane, Živaljević, Rade
#Combinatorics (math.CO) #FOS: Mathematics #Geometric Topology (math.GT)
paper · doi:10.48550/arxiv.2504.18979
We analyze lower bounds for the number of envy-free divisions, in the classical Woodall-Stormquist setting and in a non-classical case, when envy-freeness is combined with the equipartition of a measure. 1. In the first scenario, there are r hungry players, and the cake (that is, the segment [0,1]) is cut into r pieces. Then there exist at least two different envy-free divisions. This bound is sharp: for each r, we present an example of preferences such that there are exactly two envy-free divisions. 2. In the second (hybrid) scenario, there are p not necessarily hungry players (p is a prime) and a continuous measure μ on [0,1]. The cake is cut into 2p-1 pieces, the pieces are allocated to p boxes (with some restrictions) and the players choose the boxes. Then there exists at least \binom2p-1p-1 ⋅ 22-p envy-free divisions such that the measure μ is equidistributed among the players.