| paper | Fair and Efficient Cake Division with Connected Pieces |
| authors | E. Arunachaleswaran, Siddharth Barman, Rachitesh Kumar, Nidhi Rathi |
| venue | WINE 2019 |
| filed under | fairalloc · cake |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Achieving some fixed multiplicative approximation factor \(c>1\) is \(\mathrm{NP}\)-hard; no PTAS exists unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite set \(T\) of complete piecewise-constant valuation types on \([0,1]\), rational masses \(\mu_t>0\) with \(\sum_t\mu_t=1\), and type-dependent densities \(\nu_t\), choose a permutation \(\pi\) and cuts \(0=x_0\leq\cdots\leq x_{|T|}=1\), assigning \(I_{\pi(j)}=[x_{j-1},x_j]\), to maximize \(\operatorname{NSW}_{\infty}=\prod_{t\in T}\left(v_t(I_t)/\mu_t\right)^{\mu_t}\), where each type block can be subdivided among its mass into contiguous individual pieces.
A finite type set \(T\) carries rational population masses \(\mu\) and piecewise-constant valuations \(\nu_t\). Decision variables are the type order and block cuts; each block \(I_t\) is divided into \(N\mu_t\) contiguous equal-value pieces for interchangeable agents, and the objective is the mass-weighted Nash welfare \(\prod_t(v_t(I_t)/\mu_t)^{\mu_t}\).
Unrestricted \(q\)-copy allocations can scatter each type across separated intervals, so the one-block-per-type rule is an added group-contiguity restriction rather than a consequence of high multiplicity.
fatal: False
The mirror covers the welfare-maximization hardness results in Theorems 2 and 3, while leaving approximate envy-freeness, the JISP discretization, constant-agent approximation, and price-of-envy-freeness results aside.
The strongest honest positive case is a high-multiplicity, cohort-based version of contiguous cake division. The cake remains divisible; the continuization is of the population.
Let \(T\) be a finite set of complete valuation types. A type \(t\) consists of a piecewise-constant density \(\nu_t\) on the cake, together with all parameters relevant to the problem. Let \(\mu_t\) be the fraction of the population with type \(t\), with \(\sum_t\mu_t=1\). The regime is \(N\gg \tau=|T|\): there are \(N\mu_t\) interchangeable agents of type \(t\), while only \(\tau\) distinct valuation profiles exist.
The natural scenario is a large housing cooperative or land-allocation exercise. Members of one cohort have identical spatial valuations and are assigned a contiguous neighbourhood block; that block is then divided among the cohort’s members into contiguous subpieces. This is a genuine high-multiplicity regime, not a claim that every cake-cutting instance has few types.
For a type-block allocation, choose a permutation \(\pi\) of \(T\) and cuts
\[ 0=x_0\le x_1\le\cdots\le x_\tau=1, \]
with \(I_{\pi(j)}=[x_{j-1},x_j]\). The interval \(I_t\) is the connected block assigned to type \(t\). If there are \(N\mu_t\) agents of type \(t\), divide \(I_t\) into \(N\mu_t\) consecutive equal-value subintervals. Each individual therefore receives one integral, connected piece, and the average value received by a type-\(t\) agent is
\[ u_t(I_t)=\frac{v_t(I_t)}{N\mu_t}. \]
The factor \(N^{-1}\) is common to all allocations, so the continuous population objective can be written as
\[ \operatorname{NSW}_{\infty}(\mathcal I) = \prod_{t\in T} \left(\frac{v_t(I_t)}{\mu_t}\right)^{\mu_t}. \]
Equivalently, for fixed \(\rho\in(0,1]\),
\[ M_{\rho,\infty}(\mathcal I) = \left( \sum_{t\in T} \mu_t \left(\frac{v_t(I_t)}{\mu_t}\right)^\rho \right)^{1/\rho}. \]
Thus the continuous problem is:
Given rational type masses \(\mu\), piecewise-constant valuation densities \(\{\nu_t\}_{t\in T}\), and a one-dimensional cake, find a type-block partition into connected pieces maximizing \(\operatorname{NSW}_{\infty}\), or maximizing \(M_{\rho,\infty}\).
This is the mirror I would lead with.
The strongest anchor is the paper’s printed Theorem 2, proved in this paper. It states that, given a cake-division instance with piecewise-constant valuations, computing an allocation of connected pieces maximizing Nash social welfare is \({\rm APX}\)-hard. The reduction uses normalized valuations and is gap-preserving from the cited \({\rm Gap}\,3\)-SAT-5 problem; consequently, a PTAS would imply \({\rm P}={\rm NP}\).
The continuous question above is genuinely the same underlying question in a high-multiplicity regime. Take the paper’s valuation functions as the types and let \(\mu_t=1/\tau\). If each type has \(q\) identical members, then \(N=q\tau\gg\tau\). Dividing the type block among its \(q\) members gives each one value \(v_t(I_t)/q\), and hence
\[ \operatorname{NSW}_N = \frac{1}{q} \left(\prod_{t\in T}v_t(I_t)\right)^{1/\tau}. \]
The factor \(1/q\) is independent of the allocation. Therefore the continuous problem has exactly the same optimizer and the same approximation gaps as the paper’s problem. In particular, the paper’s separator, base, clause, and auxiliary valuation profiles can be treated as population types, with the Boolean-variable/clause incidence still encoded in the cake geometry.
I therefore expect this mirror to be Class B in general: hardness transfers. The hard combinatorics in Theorem 2 live in the number of valuation types and in their spatial gadget structure, not in the fact that the agents were individually named. Replicating each role many times does not remove that combinatorics. The continuous formulation is nevertheless useful: it asks whether the problem remains hard when the population is specified by type masses rather than by an explicit list of individuals.
A second, independent anchor is the paper’s printed Theorem 3, also proved here. For every fixed \(\rho\in(0,1]\), maximizing \(\rho\)-mean welfare with connected pieces and piecewise-constant valuations is \({\rm APX}\)-hard. The theorem explicitly permits valuations that are not normalized over the cake. The proof again gives a gap-preserving reduction from \({\rm Gap}\,3\)-SAT-5; for \(\rho=1\), the authors note that the construction can be adapted to normalized valuations.
The corresponding continuous problem is exactly the \(M_{\rho,\infty}\) problem stated above: given type masses and valuation densities, choose connected type blocks maximizing the mass-weighted \(\rho\)-mean welfare. For uniform masses,
\[ M_{\rho,\infty}(\mathcal I) = \tau\, M_\rho(\mathcal I) \]
up to the common per-agent scaling factor, so the paper’s \({\rm APX}\)-hardness gap transfers directly. This second anchor matters because it shows that the mirror is not an artefact of the logarithmic/geometric-mean objective: the same population formulation remains hard throughout the fixed-\(\rho\) welfare family.
The scope is deliberately limited. This case mirrors the paper’s welfare-maximization results—Theorem 2 and Theorem 3. It does not claim to mirror the approximate-envy-free algorithm, the JISP discretization, or Theorem 4’s constant-agent approximation result.
The weakest point is the cohort-block condition. The original paper allows agents of the same valuation type to receive several separated pieces, whereas my continuum model groups each type into one connected block and then subdivides that block. If a referee regards that as an excessive restriction, the mirror may be judged a different group-allocation problem. The defence is that the restriction describes a concrete high-multiplicity scenario—cohorts receiving contiguous neighbourhoods—and preserves the paper’s essential ingredients: cardinal valuation densities, connected individual pieces, cake partitioning, and the same welfare objectives. It also makes the continuum mathematically well-defined: without per-capita scaling and type-level aggregation, uncountably many agents cannot each receive a positive-length disjoint interval.
The strongest negative case is not that the paper lacks computational anchors: it plainly has two, Theorems 2 and 3. The real problem is that both anchors depend on a finite-agent feature with no stable high-multiplicity limit: every named agent must receive one connected interval.
Take \(q\) identical copies of every paper agent. In the actual \(q\)-copy cake-division problem, each copy receives one connected interval, but the aggregate allocation of a type may be a union of \(q\) separated intervals. As \(q\) grows, this aggregate can approximate essentially any measurable allocation of cake mass to that type. Individual connectedness then becomes vacuous at population scale.
That is not the model proposed by the proponent. Their requirement that all copies of type \(t\) occupy one common block \(I_t\) is an additional group-contiguity constraint. It is not forced by high multiplicity and is absent from the paper. It changes the problem from allocating connected pieces to individuals into allocating one connected block to each type and then subdividing it. A housing-cohort story may make that a coherent new problem, but it does not make it the paper’s continuous-population mirror.
Indeed, under that block restriction, the population largely disappears. With \(q\) copies of each of \(\tau\) types,
\[ \operatorname{NSW}_N = \left( \prod_{t\in T}\prod_{j=1}^{q} \frac{v_t(I_t)}{q} \right)^{1/(q\tau)} = \frac{1}{q} \left(\prod_{t\in T}v_t(I_t)\right)^{1/\tau}. \]
The factor \(1/q\) is irrelevant to optimization and approximation. Likewise,
\[ M_{\rho,N} = \frac{1}{q} \left( \frac{1}{\tau} \sum_{t\in T} v_t(I_t)^\rho \right)^{1/\rho}. \]
For nonuniform masses, one obtains a finite weighted type-block problem; \(N\) still has no role. Thus the proposed mirror is not a genuinely population-continuous version of the paper. It is the same finite ordered-partition problem, with optional weights, surrounded by a story about many copies.
This defeats the Theorem 2 anchor as a transfer from the paper. Its Gap-\(3\)-SAT construction relies on one separator, base, clause, and auxiliary agent each making one connected claim on the cake. In the genuine high-multiplicity lift, copies of a role can share and distribute the valued cells among themselves, so the type aggregate need not obey the single-interval structure used in the reduction. The structural claim and the extraction of a Boolean assignment are statements about named-agent allocations, not about a nonatomic population allocation. The theorem therefore does not establish anything about the proper high-multiplicity limit.
If one imposes the proponent’s one-block-per-type rule, the theorem can be made to reappear—but only because that rule reconstructs the original finite-agent geometry by fiat. The resulting hardness is evidence for a weighted type-block problem, not evidence that continuization reveals a new computational regime.
Theorem 3 has the same defect, not an independent one. Its \(\rho\)-mean gap uses the same single-agent gadget: a base agent chooses a positive or negative half, while each clause agent receives one literal cell or suffers a loss. The key inequality \(4t+p'\geq\alpha m\) counts agents whose individual interval is forced into trouble. Under the genuine high-multiplicity lift, a type can distribute its mass across many small connected pieces, and that named-agent counting invariant no longer describes the feasible object. Under the block restriction, the theorem again reduces to the finite weighted problem above. Changing the welfare exponent does not repair the population-model obstruction.
I am not claiming that cake division’s existing divisibility is prior art for population continuization; that would be the wrong objection. Nor can I claim that the proper nonatomic problem is uninteresting merely because its answer might be easier. The narrower point is that the paper’s distinctive computational content is precisely the interaction between individual connectedness and one-piece-per-agent allocation. Continuization either destroys that interaction, or preserves it only by adding an artificial type-block constraint that makes the population multiplicity mathematically redundant.
The honest negative case is therefore conditional rather than airtight: if the reader accepts cohort-level contiguity as an independently compelling application requirement, the proponent has a coherent weighted mirror and the negative fails. But without that extra rule, neither Theorem 2 nor Theorem 3 supplies a worthwhile continuous-population mirror; both anchors are finite-agent results dressed in a block-allocation reformulation.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.