| paper | Resource-monotonicity and population-monotonicity in connected cake-cutting |
| authors | Erel Segal-Halevi, B. Sziklai |
| venue | MSS 2018 |
| filed under | fairalloc · cake |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Neither proposed anchor satisfies bit (a): Theorem 5.2 is an axiomatic incompatibility theorem, and Theorem 6.2 is a structural property theorem, with neither asserting an algorithm, hardness result, or computational formulation. The displayed type-average LP also replaces individual connected bundles and per-agent guarantees with aggregate averages, so it is a nearby research problem rather than a computational result of this paper. A repaired high-multiplicity connected-cake question may be worthwhile, but it cannot make this paper's mirror green.
fails bit a — no named computational result to mirror
The displayed LP controls only \(v_t(A_t)/\lambda_t\), so it neither enforces every individual's proportionality nor represents individual connected intervals; repairing this requires a different formulation.
fatal: False
The attempted mirror covers Theorems 5.2 and 6.2, but leaves the protocol counterexamples, exact-proportional rule, absolute-equitable rule, rightmost-mark results, and moving-knife construction without a computational counterpart.
The paper is a good, though not perfect, candidate. Its cake is already continuous; that is not the ChoCo mirror. The mirror is the population: replace named agents by a high-multiplicity distribution of valuation types.
Take a finite type set \(T\). Type \(t\) has an absolutely continuous valuation \(v_t\) over \(C=[0,c]\), and mass \(\lambda_t\) represents the number or measure of indistinguishable agents of that type. Write \(\Lambda=\sum_t\lambda_t\) and \(\mu_t=\lambda_t/\Lambda\). If \(A_t\) is the aggregate cake assigned to type \(t\), its per-agent average utility is
\[ U_t(A)=\frac{v_t(A_t)}{\lambda_t}, \qquad R_t(A)=\frac{U_t(A)}{v_t(C)}. \]
A finite rational instance is implemented by giving each agent one connected interval. In the high-multiplicity representation, \(A_t\) may be disconnected because different agents of type \(t\) can receive different connected intervals. The type-level average is fractional, but every finite realization still gives every individual an integral connected bundle. For piecewise-constant valuations, this is represented by variables \(y_{tj}\), the fraction of cake cell \(j\) assigned to type \(t\).
This is a natural regime for land division: many firms, households, or public agencies share one of a small number of land-use valuation templates. The paper’s own piecewise-homogeneous examples already have this form. The population may be very large while the number of distinct valuation types remains two or three.
My lead anchor is Theorem 5.2, proved in the paper:
When agents have connected utilities, no division rule can be simultaneously proportional, Pareto-optimal, and population-monotonic.
The proof uses three agents and seven slices, with valuation rows
\[ A=(2,0,3,0,2,0,0),\quad B=(0,0,0,0,0,7,0),\quad C=(0,2,0,2,0,0,3). \]
All agents value the whole cake at \(7\). With all three present, proportionality and Pareto-optimality force Bob to receive the \(7\)-slice, Carl to receive the right-hand part with utility \(3\), and Alice to receive the left-hand part with utility \(7\). If Bob leaves, Carl must obtain at least \(7/2\); because his positive slices are separated, his new connected piece must touch the middle \(2\)-slice, leaving Alice with utility at most \(5\). Thus Alice is worse off when Bob leaves, violating population-monotonicity.
The corresponding continuous problem is:
HM-Connected-POP. Given \(T\), \(\lambda\), \(C\), and valuation measures \(v_t\), construct a rule \(R_\infty\) that returns a high-multiplicity connected allocation for every mass vector and every mass reduction. Require
\[ U_t(R_\infty(\lambda))\ge \frac{v_t(C)}{\Lambda} \]
for every type \(t\) (proportionality), require Pareto-optimality with respect to the per-agent utilities \(U_t\), and require that removing any positive mass of agents weakly increases the utilities of all retained types.
A solution is either such a rule, together with an algorithm for computing its allocation, or a finite type-and-valuation counterexample showing that no such rule exists.
My expectation is that the high-multiplicity version is likely tractable in the fluid model, rather than inheriting Theorem 5.2 unchanged. The obstruction in the paper comes from one agent of type \(C\) needing a single connected piece. With many \(C\)-agents, different agents can occupy the two separated \(C\)-valuable regions, while every individual still receives a connected interval. The aggregate problem becomes a divisible allocation problem. A weighted Nash or lexicographic max-min program is a natural candidate:
\[ \max \sum_{t\in T}\lambda_t\log U_t \]
over the fractional cell-allocation variables \(y_{tj}\). This suggests Class A, with the exact population-monotonicity and Pareto proofs as the substantive questions. If the obstruction survives even this fluid limit, that would instead be a genuinely continuum-specific boundary result.
My second anchor is Theorem 6.2, also proved in the paper. It states that the relative-equitable rule—among connected divisions, choose one maximizing the common relative value—is weakly Pareto-optimal, population-monotonic, and proportional, but not resource-monotonic. The paper proves existence and uniqueness of the equitable value for each agent ordering, then uses the moving-knife construction to establish these properties. Its non-resource-monotonicity example has two agents with values
\[ A=(M,M,1,1),\qquad B=(1,1,M,M), \]
where adding two \(A\)-valuable slices changes the maximum relative-equitable value from \(M/(M+2)\) to \(1/2\).
The corresponding computational problem is:
HM-Max-Relative-Equitable. Given \(T\), \(\lambda\), \(C\), and piecewise-constant rational valuation densities, find a high-multiplicity allocation and the largest \(\rho\) satisfying
\[ \frac{v_t(A_t)}{\lambda_t v_t(C)}=\rho \]
for every type \(t\). Equivalently, compute the largest \(\rho\) for which
\[ v_t(A_t)\ge \lambda_t\rho\,v_t(C) \]
for all \(t\), and return an allocation that equalizes the ratios whenever possible. A valid output must also provide an \(\varepsilon\)-accurate connected realization by finitely many agents of each type.
For a piecewise-constant cake this is an LP over \(y_{tj}\):
\[ \sum_j \ell_j d_{tj}y_{tj}\ge \lambda_t\rho\,v_t(C), \qquad \sum_t y_{tj}\le 1. \]
Thus the fluid high-multiplicity problem is plausibly Class A. The remaining computational issue is the relationship between the compressed type-level solution and finite connected realizations, especially the dependence on the number of types and the approximation error. This is not already done by Theorem 6.2: the theorem gives structural properties of the finite-agent rule, not a high-multiplicity algorithm or complexity bound.
The paper contains no numbered NP-hardness, membership-in-\(\mathrm{P}\), or parameterized-complexity theorem, so I cannot honestly present a hardness anchor. These two anchors are structural and algorithmic rather than complexity-theoretic. The mirror nevertheless gives the authors’ questions a clear computational continuation: does repeated population smooth away their impossibility, and can their moving-knife rules be compressed into LP or convex-optimization algorithms?
The weakest point is unavoidable. A literal continuum of agents cannot each receive a positive-length, pairwise-disjoint interval of a finite one-dimensional cake. The mirror therefore needs the high-multiplicity interpretation above: finite connected allocations followed by a type-level limit, with average utilities for indistinguishable cohorts. If the authors insist that connectedness must remain a property of each infinitesimal agent without this aggregate interpretation, the mirror fails. I think the finite-realization semantics makes the modification legitimate: it preserves their individual connected-bundle problem and changes only the population representation.
The negative case is strongest at the level of what is being mirrored: this paper contains no numbered computational result. Its theorems are impossibility and characterization results about division rules, and its moving-knife construction is an existence/protocol argument, not a complexity theorem or a finite-input algorithm. Thus both proposed anchors require inventing a new computational problem before continuization begins.
Theorem 5.2 does not survive the proposed type compression faithfully. In the paper, proportionality and Pareto-optimality apply to every named agent. If two identical agents of type \(t\) receive values \(0\) and \(2\), the proponent’s quantity
\[ U_t=\frac{v_t(A_t)}{\lambda_t}=1 \]
may satisfy a type-average proportionality constraint, while one actual agent violates proportionality. The same issue affects Pareto comparisons: improving the type average can harm one member of the type. This is not merely a technical representation choice; it changes the fairness and efficiency concepts proved in the paper.
The proposed cell LP makes that change explicit. Variables \(y_{tj}\) describe a divisible allocation to types, but impose neither that every individual receives one connected interval nor that members of a type receive comparable utilities. A faithful repair would need either the utility distribution of each type or a distribution over connected intervals. In the latter formulation, the ordering and endpoints of up to \(\Lambda=\sum_t\lambda_t\) individual intervals become part of the object. The simple high-multiplicity LP disappears; a compressed type-average allocation is no longer a representation of the paper’s problem.
This also makes the proposed “find a rule or produce a counterexample” formulation unsuitable as a computational-social-choice problem. Population-monotonicity is a global property of a rule over all population reductions, not a property of one finite instance. If small multiplicities are allowed, the original three-agent counterexample immediately returns. If they are excluded to force a genuine high-multiplicity regime, the threshold and the replacement axiom must be newly specified. That may be an interesting mechanism-design question, but it is not a computational mirror supplied by Theorem 5.2.
Theorem 6.2 has the same defect. The paper’s relative-equitable rule equalizes the relative utility of every individual. The proposed condition
\[ \frac{v_t(A_t)}{\lambda_t v_t(C)}=\rho \]
equalizes only type averages. A disconnected aggregate allocation can give members of one type different utilities while satisfying this equation. Hence the displayed LP is a max-min fractional cake-allocation problem, not the high-multiplicity version of max-relative-equitable connected cake-cutting. Requiring an \(\varepsilon\)-accurate connected realization is not a harmless output condition: it is precisely the missing feasibility problem, and the LP gives no reason that every feasible \(y\) admits such a realization.
Moreover, the paper’s relative-equitable value is obtained by maximizing over agent orderings. With many copies, the relevant object is an ordering of individual intervals, or at least a sequence of type labels with multiplicities. The proposed LP has no ordering variable at all. Removing those variables is what makes it tractable, but also what removes the connected equitable-division problem being mirrored.
The non-resource-monotonicity example in Theorem 6.2 is especially weak as an anchor for ChoCo: it concerns enlargement of the cake, not population. Its population-monotonicity statement is axiomatic, while the paper gives no complexity result for computing the rule. The moving-knife procedure already addresses finite-agent existence; replacing named agents by type masses does not by itself create a computational question with a defined encoding, output size, or approximation model.
There is a legitimate high-multiplicity land-division problem nearby, especially for many firms sharing valuation templates. But to make it faithful one must retain individual connected bundles and individual fairness; to obtain the proposed LP one must relax both into aggregate fractional allocation. The former is a new interval-partition problem whose computational formulation the paper does not provide, and the latter is a different divisible-resource problem. I therefore do not find either anchor a worthwhile continuous mirror of this paper, though I would not claim that no related high-multiplicity cake-cutting project could ever be worthwhile.
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.