ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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 2n−22n-2 cuts.

The preceding theorem establishes this bound when at least n−1n-1 entitlements are equal to 1/D1/D for some integer D≥1D\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).

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.