| paper | Beyond Cake Cutting: Allocating Homogeneous Divisible Goods |
| authors | — |
| venue | AAMAS 2022 |
| filed under | fairalloc · cake |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5.1
statement extracted from the paper’s text layer
Given a finite type set \(T\) with rational masses \(\mu_t\), \(m\) homogeneous divisible goods with per-capita capacities \(b_k\), nondecreasing \(C\)-Lipschitz valuation oracles \(f_{t,k}:[0,1]\to\mathbb{R}_{\ge 0}\), and \(\epsilon>0\), where \(u_t(x)=\sum_k f_{t,k}(x_k)\), compute a finite-support lottery over measurable ex-post feasible allocation fields \(a\) satisfying \(\int a_k(p)\,dp\le b_k\) that is ex-ante envy-free between types and has no alternative feasible envy-free lottery \(L'\) with \(U_t(L')\ge(1+\epsilon)U_t(L)\) for every positive-mass type and strict inequality for one type.
A nonatomic population of total mass \(1\) partitioned into complete valuation types, with measurable mass allocation fields \(a(p)\in[0,1]^m\) and a distribution over feasible fields as decision variables; resource use is \(\int a_k(p)\,dp\le b_k\), utilities are \(u_t(x)=\sum_k f_{t,k}(x_k)\), and the objective is approximate Pareto efficiency subject to type-level ex-ante envy-freeness.
The original \(n\)-column flow and \(1/n\)-based utility guarantee do not transfer automatically: weighted cumulative mass states and per-capita resource normalization require a new finite encoding or configuration theorem.
fatal: False
The mirror covers Theorems 5.1 and 4.1 as, respectively, an approximate ex-ante Pareto-efficient envy-free lottery problem and a valuation-query lower-bound problem over types; it leaves Theorem 6.1 and the paper's auxiliary observations and open problems aside.
My strongest case is a genuine high-multiplicity mirror of Theorem 5.1. The paper contains no named NP-hardness, W[1]-hardness, or completeness result, so I would not manufacture a hardness anchor. Theorem 5.1 is proved in this paper and is the lead.
The regime is a large population of households sharing a small catalogue of complete valuation types. For example, a national energy or computing-allocation service may serve millions of households, but their nonlinear demand curves may fall into \(\tau\) standardized profiles: each type specifies its value function for every homogeneous resource, including thresholds, saturation, complementarity, and substitutability. Here \(N\) is enormous while \(\tau\) is small or moderate, and \(\mu_t\) is the fraction of households of type \(t\). This is a high-multiplicity regime, not a claim about every fair-division instance.
The continuous object is the population distribution \(\mu\), not the divisible goods or the lottery. Let \(M=\{1,\ldots,m\}\) be the resources and let type \(t\) have nondecreasing, \(C\)-Lipschitz functions \(f_{t,k}:[0,1]\to\mathbb{R}_{\ge0}\). Its utility for bundle \(x\in[0,1]^m\) is
\[ u_t(x)=\sum_{k\in M}f_{t,k}(x_k). \]
A pure allocation is a measurable assignment \(a\) of bundles to the nonatomic population, satisfying
\[ \int a_k(p)\,d p\le b_k \]
for every resource \(k\). A lottery \(L\) is a finite-support distribution over such ex-post feasible allocations. For type \(t\), let \(U_t(L)\) be its expected utility from its own allocation, averaged over its mass, and let \(U_{t\leftarrow s}(L)\) be the expected utility type \(t\) would obtain from the allocation assigned to type \(s\). The lottery is ex-ante envy-free when
\[ U_t(L)\ge U_{t\leftarrow s}(L) \qquad\text{for every }t,s\in T. \]
The problem I would name \( \mathrm{Mass\mbox{-}EF\mbox{-}PEF}_\infty \) is:
Given \(m\), rational masses \(\mu_t\), resource capacities \(b_k\), valuation oracles for the \(f_{t,k}\), and \(\epsilon>0\), output an ex-post feasible lottery \(L\) that is ex-ante envy-free and \(\epsilon\)-Pareto optimal among all ex-ante envy-free lotteries; that is, there must be no envy-free \(L'\) with
\[ > U_t(L')\ge (1+\epsilon)U_t(L) > \]
for every positive-mass type \(t\), with strict inequality for at least one type.
The output may be represented by a finite list of grid-valued allocation fields and probabilities, or equivalently by a flow certificate describing that lottery. This preserves the paper’s substantive question: arbitrary nonlinear within-resource valuations, additive utility across resources, ex-ante envy-freeness, ex-ante rather than ex-post Pareto efficiency, and the requirement that the lottery be decomposable into ex-post feasible allocations. Only named individuals have been replaced by masses of indistinguishable complete types.
The expected classification is Class A. Theorem 5.1 states, in the original model, that an ex-ante \(\epsilon\)-Pareto optimal envy-free lottery can be computed using \(\mathrm{O}(mn/\epsilon^2)\) queries; this theorem is proved here. In the mirror, valuation queries are made once per type-resource pair, not once per household. The discretization and flow construction should therefore become a mass-weighted flow LP whose size depends on \(m\), \(\tau\), the accuracy parameter, and the encoding length of the masses—not on \(N\). In a regular regime such as \(\mu_t\ge 1/\operatorname{poly}(\tau)\), the natural target is \(\operatorname{poly}(m,\tau,1/\epsilon,L)\) queries and LP time, with an \(\mathrm{O}(m\tau/\epsilon^2)\)-type bound under the paper’s normalization.
The flow point matters. A naive mass LP would enforce only expected resource usage and could produce an unrealizable lottery, exactly as in Section 5.1 of the paper. The continuous mirror should retain the corrected flow-based formulation from Section 5.2, with mass-weighted transitions and every support allocation ex-post feasible. That is a recognizable continuation of the authors’ problem rather than a tractable welfare problem obtained by deleting its difficult fairness and lottery structure.
A supporting anchor is Theorem 4.1, also proved here. It states that computing an ex-ante \(\epsilon/16\)-Pareto optimal envy-free lottery requires at least \(1/(2\epsilon)\) adaptive queries even with two agents and two goods. Its continuous counterpart, \( \mathrm{Type\mbox{-}Oracle\mbox{-}PEF}_\infty \), has two positive-mass valuation types, two goods, and the same value and cut oracles; it asks for an \(\epsilon/16\)-Pareto optimal envy-free lottery over the nonatomic population. I would expect the same \(\Omega(1/\epsilon)\) information lower bound after mass and capacity normalization: the adversary’s hidden interval in a valuation curve remains hidden from every member of that type, however large its population is. This is not an NP-hardness claim and not evidence that population multiplicity itself creates hardness; it is a useful boundary showing that continuization removes repeated identities, not arbitrary black-box valuation complexity.
The weakest point is that the \(n\)-to-\(\tau\) replacement is not automatic. The paper’s proof of Theorem 5.1 uses a lower utility scale tied to \(1/n\), while a mass model with highly unequal \(\mu_t\) may require dependence on the smallest positive mass or a different Pareto-normalization argument. Also, allowing arbitrary within-type allocation fields may require a more careful mass-flow representation than simply replacing an agent index by a type index. Those are real technical obligations.
Nevertheless, the mirror is persuasive because it keeps the paper’s actual problem intact and makes the continuous population assumption do computational work: one oracle description and one LP-flow representation serve an arbitrarily large mass of identical agents. The main follow-up questions are whether the \(n\)-dependence can be replaced cleanly by \(\tau\), whether the dependence on mass encoding can be made polynomial, and how accurately the resulting lottery can be rounded back to a finite \(N\)-agent allocation.
The strongest negative case is that the proposed mirror confuses aggregation with continuization. This paper’s computational difficulty lies in discovering the shapes of the agents’ valuation oracles, not in the number of agents. Replacing repeated agents by valuation types is sensible, but it does not make population mass the computational object.
Theorem 4.1 is the clearest failure as a population anchor. Its lower bound uses two agents, two goods, and three possible valuation functions hidden between queried points. No part of the adversary depends on there being many agents. Replicating each of the two agents into a positive-mass type gives exactly the same two-oracle lower bound, with \(\mu\) playing no algorithmic role. Conversely, increasing the number of types measures the number of distinct valuation oracles, not population multiplicity. This is a valid type-level oracle problem, but it is not a population-computational phenomenon.
Theorem 5.1 is a more serious candidate, but the claimed \(n\)-to-\(\tau\) substitution does not follow. The paper’s flow has one column per named agent and a resource-consumption state on an \(\epsilon\)-grid. With type masses, a transition for type \(t\) consumes \(\mu_t y\epsilon\), so the reachable states are weighted sums of rational masses. Even with every \(\mu_t\) bounded below by \(1/\operatorname{poly}(\tau)\), their denominators may have exponentially many distinct weighted sums as a function of encoding length. The paper’s polynomial-size flow therefore does not become an \(O(m\tau/\epsilon^2)\) flow by replacing agent indices with types.
There is also a normalization problem. In the paper, each good has capacity \(1\), so grouping \(n_t\) agents gives
\[ \sum_t n_t x_{t,k}\le 1, \]
or, with \(\mu_t=n_t/n\),
\[ \sum_t \mu_t x_{t,k}\le \frac{1}{n}. \]
The proponent instead uses \(\sum_t\mu_t x_{t,k}\le b_k\) with constant \(b_k\). That is an extensive-supply model in which the stock of each good grows with the population. It may be a sensible new application, but it is not the high-multiplicity relaxation of the stated theorem. Keeping fixed supply makes per-agent allocations vanish and the paper’s multiplicative Pareto guarantee degenerate; scaling supply avoids degeneration only by changing the resource regime.
Finally, the proposed “allocation field” does not automatically preserve the paper’s feasible lottery space. With nonlinear \(f_t\), a type’s average bundle does not determine its average utility. A continuum type may need to be split across different bundles within each ex-post allocation, and correlations among those splits matter for feasibility. Enforcing one bundle per type shrinks the feasible set; allowing arbitrary measurable fields creates a new infinite-dimensional representation problem. Establishing a finite flow or configuration certificate would be a new theorem, not an inheritance from Theorem 5.1.
So the negative case can defeat both claimed anchors as evidence that the paper already supplies a population-complexity problem: Theorem 4.1 is insensitive to multiplicity, while Theorem 5.1 does not survive by a formal mass substitution. But the universal conclusion is honestly weak. A standardized-demand application with per-capita supply and carefully bounded type encodings could still yield a worthwhile new high-multiplicity fair-division problem. The paper therefore supports a speculative mirror, though not the proponent’s claimed direct continuation of its two theorems.
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.