| paper | d4-conf-aaai-2014-0469 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
Theorem 3 is a computational impossibility result, and an exact mass-allocation analogue could be worth studying. But the proposed \(q\)-scaled supply makes exact envy-freeness trivial, while fixed supply permits zero-size bundles and makes the approximate guarantee vacuous for fixed types. Whether a nondegenerate scarcity rule would still be the authors’ cake-cutting problem is unresolved.
fails bit b-changes — the continuum limit changes the question
The unresolved point is whether a precise scarcity rule for mass allocations can avoid both zero-size allocations under fixed supply and a whole cake per unit under \(q\)-scaled supply, while remaining a problem the authors would recognize. A concrete nontrivial capacity and consumption rule would settle whether Theorem 3 has a continuous analogue.
The proposed mirror concerns Theorems 3 and 4; it does not cover the proportionality results in Theorems 1 and 2 or the general linear-property result in Theorem 5.
The strongest honest mirror is the paper’s exact-versus-approximate envy-freeness boundary. The cake is already divisible in the paper; the continuization here is the population, represented by masses of agents with the same complete valuation type.
Let \(T\) be a finite set of valuation densities \(v_t\), and let \(\mu_t\) be the fraction of the population of type \(t\), with \(\sum_t\mu_t=1\). A plausible regime is a large recurring allocation of heterogeneous capacity—such as bandwidth across locations—where many participants share one of a modest number \(\tau=|T|\) of valuation profiles. To keep each participant’s share meaningful as the population grows, include a population scale \(q\) and scale total capacity with \(q\). Type \(t\) has mass \(q\mu_t\), and all members of that type submit the same simultaneous sketch: cut points and the value of each resulting interval.
The output is a mass allocation: for each type \(t\), a distribution \(\pi_t\) over integral cake bundles describes which fraction of that type’s mass receives each bundle. The bundles must respect aggregate resource capacity. Envy-freeness is required between every pair of bundles assigned positive mass: for types \(t,s\), every \(A\in\operatorname{supp}\pi_t\), and every \(B\in\operatorname{supp}\pi_s\), type \(t\) values its own bundle at least as much as \(B\), up to the stated error. Each unit of mass receives an integral bundle; averages across a type may be fractional. A protocol reads the type sketches simultaneously and outputs such a mass allocation. Its complexity is the maximum number of intervals reported per type; the computational question is its worst-case complexity in \(q,\tau,L\), and the error parameter. This keeps the paper’s question about information and fair allocation while making the population distribution the continuous object.
Theorem 3, proved in this paper, is the exact-fairness anchor: for every \(n\ge 3\), no simultaneous protocol guarantees an exactly envy-free allocation for every profile of integrable, nonnegative, non-atomic valuations normalized to value the whole cake at \(1\). Its proof fixes one uniform agent and constructs valuations for the others against that agent’s reported intervals. The mirror problem is whether any finite per-type sketch protocol can guarantee exact envy-freeness for every mass society. I expect an impossibility result. The paper’s obstruction already uses one exceptional valuation type and many agents sharing another, so it speaks to a high-multiplicity regime. Whether it persists when every type has a mass bounded away from zero is a further question.
Theorem 4, also proved here, is the approximate-fairness anchor: for every \(\epsilon>0\), there is an \(\epsilon\)-envy-free simultaneous protocol with complexity \(O(n/\epsilon^2)\). Its proof sketches coarse and fine discretizations, then applies a result of Lipton et al. on approximately envy-free allocations of indivisible goods. The mirror problem is to find the smallest per-type sketch complexity that guarantees \(\epsilon\)-envy-freeness for every mass society, robustly over valuation functions consistent with the sketches. I expect this to be tractable for fixed or moderate \(\tau\). The paper’s proof suggests a route: only \(\tau\) distinct coarse discretizations need to generate goods, even when many agents share each type. Whether the resulting type-level allocation can be computed efficiently, and what dependence on \(q,\tau,L,\epsilon\) is necessary, are the main questions. The indivisible-goods lemma is cited; the paper’s theorem and protocol are proved here.
This case covers the paper’s simultaneous envy-free allocation results; it does not claim that divisible outcomes by themselves are a continuous-population model. Its weakest point is the scaling needed to keep per-person fairness non-degenerate. In a fixed cake with an ever-growing population, individual shares vanish, while a literal continuum of people cannot each receive a positive-measure disjoint piece. The mass allocation and population-scaled supply are defensible co-modifications for a replenished-resource regime, but they need to be accepted as part of the authors’ problem for this to be a strong mirror.
The strongest objection is a scaling problem in both envy-freeness anchors. The paper has \(n\) people sharing one cake. A continuous society has mass, not a count of people, so the mirror must say how much cake that mass consumes. The proposed repair—scale cake supply with population size—does not by itself preserve the paper’s scarcity.
For Theorem 3, if a continuum of individuals partitions the fixed cake pointwise, assign individual \(x\) the singleton \(\{x\}\). Every valuation in the paper is non-atomic, so every person values every such bundle at zero: the allocation is exactly envy-free without any reports. A mass-allocation model that measures consumption in expectation would rule this out, since singleton bundles use zero aggregate resource. But that choice exposes the scale issue: with fixed cake and population mass \(q\), per-capita supply vanishes as \(q\) grows; with \(q\) identical copies of the cake, each person can receive a whole copy and envy-freeness is again immediate. To keep scarcity, one must specify an additional capacity or demand constraint. That could define a sensible new problem, but it is not yet supplied by the mirror.
Theorem 4’s approximate guarantee is more vulnerable to this limit. Keep the cake fixed, let population mass be \(q\), and divide it into \(q\) equal slices, assigning mass one to each slice. This exhausts aggregate capacity. For each fixed type \(t\), integrability implies
\[
\delta_t(q)=\sup_{|S|\le 1/q} V_t(S)\longrightarrow 0.
\]
Every assigned slice is worth at most \(\delta_t(q)\) to every type, while each person’s own value is nonnegative. Thus, for any fixed \(\epsilon>0\), sufficiently large \(q\) gives \(\epsilon\)-envy-freeness with no valuation sketches at all. This makes the paper’s \(O(n/\epsilon^2)\) communication bound lose its force in the fixed-cake continuum limit. The argument is for fixed types; a worst-case family whose densities become more concentrated with \(q\) could evade it, but that needs to be part of the model.
The proponent’s stronger formulation—finite valuation types, aggregate capacity, and envy comparisons between every pair of bundles actually assigned—avoids some shortcuts. It may support a worthwhile exact-information problem. But I cannot honestly rule it out: with scarcity and the allocation semantics fixed carefully, Theorem 3’s impossibility could still have a meaningful mass version, and the high-multiplicity setting is plausible. The negative case is therefore strongest against the stated scaling and the approximate anchor; it does not defeat every well-specified exact mirror.
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.