The universal upper-bound conjecture for proportional cake-cutting with different entitlements

Let nn be a positive integer, let there be nn value measures on a cake, and let tt be an entitlement vector. A tt-proportional allocation assigns each agent a piece whose value according to that agent's measure is at least their entitlement.

Universal upper-bound conjecture. For every nn, every set of nn value measures, and every entitlement vector tt, there exists a tt-proportional allocation with at most 2n22n-2 cuts.

The preceding theorem establishes this bound when at least n1n-1 entitlements are equal to 1/D1/D for some integer D1D\geq 1. The conjecture asserts that the same lower bound is always attainable; the simplest case in which it remains open is n=3n=3 with entitlements (1/7,2/7,4/7)(1/7,2/7,4/7).

Sources & referencesView supporting material

Primary source

Erel Segal-Halevi, “Cake-Cutting with Different Entitlements: How Many Cuts are Needed?”, arXiv:1803.05470 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.