Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.18979 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912364329172992 |
|---|---|
| author | Jojić, Duško Panina, Gaiane Živaljević, Rade |
| author_facet | Jojić, Duško Panina, Gaiane Živaljević, Rade |
| contents | 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 $\binom{2p-1}{p-1} \cdot 2^{2-p}$ envy-free divisions such that the measure $μ$ is equidistributed among the players. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_18979 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lower bounds on the number of envy-free divisions Jojić, Duško Panina, Gaiane Živaljević, Rade Combinatorics Geometric Topology 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 $\binom{2p-1}{p-1} \cdot 2^{2-p}$ envy-free divisions such that the measure $μ$ is equidistributed among the players. |
| title | Lower bounds on the number of envy-free divisions |
| topic | Combinatorics Geometric Topology |
| url | https://arxiv.org/abs/2504.18979 |