d4-conf-wine-2021-0003

The strongest case is Theorem 3, because it treats the paper’s distinctive two-layer feasibility constraint and gives an algorithmic result. The natural setting is a large workforce sharing a small number of standardized schedule preferences: for example, thousands of workers divided among three teams, with two activities available over the day and each worker able to do at most one activity at a time. A type is the worker’s complete valuation function over layered schedules, including any relevant contract or preference parameters. Mass is the fraction of workers of each type. The regime is \(N\) workers with \(\tau\ll N\) exact types—perhaps dozens of schedule-preference classes. Bounded, monotone values for longer usable schedules make the paper’s assumptions plausible. The continuous object here is the workforce distribution; the cake is already an interval in the paper.

My lead anchor is Theorem 3, proved in this paper. It says that for \(n\ge 3\) agents with monotone valuation functions satisfying the Lipschitz condition with constant \(K\), and for any \(\varepsilon>0\), an algorithm runs in \(O(n\log^2(K/\varepsilon))\) time and finds a feasible, contiguous division of a two-layered cake into three pieces using one short knife and one long knife. Whichever piece the birthday agent chooses, the remaining agents can be assigned to pieces they value within \(\varepsilon\) of their favorite, with the numbers assigned to the three pieces differing by at most one. The theorem computes the division; the paper notes that the assignment can then be recovered separately.

Here is the continuous problem I would hand to a prover.

Three-Group Two-Layer Cake Division with Type Masses — the lead mirror. An instance consists of two layers of \([0,1]\), a finite set \(T\) of \(\tau\) valuation types, rational masses \(\mu_t>0\) summing to \(1\), a known Lipschitz constant \(K\), and \(\varepsilon>0\). Each \(v_t\) is a complete valuation function of type \(t\), monotone and \(K\)-Lipschitz as in the paper. Values are available through the same kind of oracle assumed there.

The solution is a feasible, contiguous three-piece division \(A(x,y)\) of the paper’s one-short-knife, one-long-knife form, together with an assignment for each possible birthday choice \(r\in\{1,2,3\}\). Represent the assignment by masses \(z^{(r)}_{tj}\ge 0\), where \(z^{(r)}_{tj}\) is the mass of type \(t\) sent to piece \(j\). Require
\[ \sum_{j=1}^{3}z^{(r)}_{tj}=\mu_t,\qquad \sum_{t\in T}z^{(r)}_{tj}=\frac13, \]
and
\[ z^{(r)}_{tj}>0 \ \Longrightarrow\ v_t(A_j(x,y))+\varepsilon\ge \max_{k\in\{1,2,3\}}v_t(A_k(x,y)). \]
The distinguished birthday chooser is external to the mass distribution and may choose any piece; the bulk population must still be divided into three equal-mass groups. This is the limit of the finite theorem’s one distinguished agent and almost-equal group counts as the population grows. Splitting a type’s mass among groups means partitioning a continuum of otherwise identical agents, which is exactly the population-level co-modification.

I expect this problem to be tractable, in Class A. The paper’s proof aggregates preferences across agents, searches over a fixed two-dimensional knife space, and then uses a flow argument to balance group sizes. In the mirror, the aggregate becomes the weighted sum \(\sum_t\mu_t f_t\), and the balancing step becomes a fractional transportation problem. A natural target is polynomial dependence on \(\tau\) and the binary input length \(L\), with roughly \(O(\tau\log^2(K/\varepsilon))\) type-oracle work. That bound is a conjectured extension, not a result proved by this paper; handling weighted degeneracies and bit complexity is part of the research question.

A useful second anchor is Theorem 4, also proved here. It gives an algorithm running in \(O(n\log^2(K/\varepsilon))\) time for monotone, \(K\)-Lipschitz valuations on a one-layer cake and any positive integer group sizes \(k_1,k_2,k_3\) summing to \(n\). It finds a contiguous three-piece division such that, for any birthday-agent choice, the remaining agents can be assigned to \(\varepsilon\)-approximate favorite pieces, with exactly \(k_j\) agents assigned to piece \(j\). This is a distinct, simpler mirror that tests nonuniform quotas.

Three-Group Cake Division with Prescribed Type Masses takes a one-layer cake, the same finite rational type distribution, and rational target masses \(\alpha_1,\alpha_2,\alpha_3>0\) summing to \(1\). Its solution is two cuts defining three contiguous intervals and, for each birthday choice \(r\), masses \(z^{(r)}_{tj}\) satisfying
\[ \sum_{j=1}^{3}z^{(r)}_{tj}=\mu_t,\qquad \sum_{t\in T}z^{(r)}_{tj}=\alpha_j, \]
with positive assignment mass only to \(\varepsilon\)-favorite intervals for that type. I also expect this problem to be tractable, with dependence on the number of types, rational input size, and \(\log(K/\varepsilon)\). The prescribed shares are the limit of the paper’s exact integer group sizes.

These mirrors cover the paper’s algorithmic results in Theorems 3 and 4. They do not try to continuize the purely existential topological results, the proportionality result, or the cake outcomes themselves. The paper has no comparable named hardness theorem proved here; its conclusion says the precise complexity of the underlying existence problem remains unsettled. The cited PPAD-hardness result is external and concerns a different choice-function model, so it is not an anchor for this case.

The main follow-up questions are whether the exact \(\varepsilon=0\) finite-type problem admits an efficient algorithm in a specified valuation-oracle model, and whether the two-layer result extends to arbitrary target shares or more layers and groups.

My weakest point is the change from indivisible agents to divisible type mass: the birthday agent becomes a zero-mass selector, and integer group counts become exact mass shares. That is the ordinary high-multiplicity limit and preserves the group-assignment question, but the finite theorem does not itself establish the weighted algorithm or its bit complexity. Its preference map averages \(n\) individual choices; replacing that construction with a rationally weighted average is plausible, not automatic. The mirror is strongest as a well-posed computational question the authors could recognize as their group-division problem at high multiplicity, rather than as a claim that their theorem already solves it.