| paper | d4-conf-aaai-2018-0370 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1.6
statement extracted from the paper’s text layer
For an \(n\)-day repeated cut-and-choose service on the square, does there exist a non-adaptive forced-cut protocol using \(3n\) cuts such that, after every reachable history of divisions and exact aggregate choice shares, each legal next division admits two finite-support rational distributions over chooser types consistent with that history whose next shares choosing one side are respectively below and above \(1/2\)?
The society is a finite-support rational mass distribution \(\mu\) over complete chooser types, each specifying a non-atomic valuation and tie rule. Every member receives a whole piece from the same offered division; the cutter observes aggregate choice shares across days. The design objective is to minimize the worst-case cut count while keeping both majority responses consistent with every observed history and legal next division.
Majority uncertainty does not guarantee the paper’s original payoff property that a cutter cannot secure more than half of her own value; the proposed mirror measures uncertainty about aggregate response instead.
fatal: False
The mirror covers Theorems 1.4 and 1.6: the one-dimensional linear-cut lower bound and the square’s \(3n\)-cut construction. It leaves Theorems 1.2, 1.3, and 1.5 and the paper’s other discussions unaddressed.
The best positive case is for the paper’s cut-complexity results. It contains no named theorem classifying a decision problem as being in P or NP-hard. My lead anchor is Theorem 1.4, which gives a lower bound in the paper’s own resource measure: number of cuts. Theorem 1.6 provides a complementary upper bound.
A plausible population regime is a recurring fair-division service: on each of \(n\) days, a supplier offers the same division of a standardized cake to a large, stable customer cohort, and each customer receives a copy. Customers with the same valuation and tie-breaking rule form a type; \(\mu_t\) is that type’s fraction of the cohort. Take rational masses, support size \(\tau\le n+1\), and population size \(N\gg\tau\). The supplier sees only the fraction choosing each side on previous days, not customer identities. A type is a complete normalized, non-atomic valuation of the cake plus its tie rule. For a finite encoding, one can use piecewise-constant rational densities and rational cuts.
Here is the continuous problem I would hand to a prover. Call it Cohort Mass-Non-Exploitable Forced-Cut Design, with dimension-specific versions \(\mathrm{CMNE\mbox{-}FCD}_1(n,B)\) and \(\mathrm{CMNE\mbox{-}FCD}_2(n,B)\). The instance fixes the cake, horizon \(n\), and cut budget \(B\). A solution is a non-adaptive forced-cut protocol using at most \(B\) cuts in every execution, with the paper’s per-segment bisection feasibility for the cutter. On day \(i\), if the offered pieces are \(X_i\) and \(C\setminus X_i\), the observed share choosing \(X_i\) is \(a_i=\sum_t\mu_t\,\mathbf 1[\text{type }t\text{ chooses }X_i]\). Call the protocol cohort-non-exploitable if, after every reachable history of divisions and aggregate shares, and for every legal next division, there are two finite-support rational-mass societies consistent with that *same* history, one with \(a_i<1/2\) and one with \(a_i>1/2\). The next majority response therefore cannot be inferred from the aggregate history. The continuous object is the population; each customer still receives a whole piece.
Theorem 1.4 is the lead anchor, proved in this paper. As printed: for any constant \(c>0\), if \(P\) is a non-adaptive, envy-free forced-cut protocol using at most \(cn\) cuts, then there is an \(n_0\) such that \(P\) is exploitable for every \(n>n_0\). In other words, a one-dimensional non-adaptive protocol cannot use a constant number of cuts per day and remain non-exploitable. I would mirror this with \(\mathrm{CMNE\mbox{-}FCD}_1(n,B)\): can a protocol meet the cohort-majority condition with \(B=cn\) cuts? I expect the answer to be no for sufficiently large \(n\). The reason is a direct singleton embedding: when \(\mu\) has one type, the aggregate share is either \(0\) or \(1\), and opposite-majority ambiguity reduces to the paper’s question of whether both chooser actions remain possible after the history. The theorem’s lower-bound construction therefore rules out a linear-cut family in the continuous version too. This is a cut-resource lower bound transferred through a one-type instance, not an NP-hardness result.
Theorem 1.6 is a useful second anchor, also proved here: there is a non-adaptive, non-exploitable \(n\)-day forced-cut protocol for the square \((0,1)\times(0,1)\) using \(3n\) cuts. Its mirror is \(\mathrm{CMNE\mbox{-}FCD}_2(n,3n)\), asking whether such a cohort-safe protocol exists. I expect yes. Protocol 5.1 uses one fixed vertical forced cut and two horizontal cuts per day. Its proof constructs a chooser valuation for every binary sequence of choices. For any rational vector of past aggregate shares, a finite mixture of at most \(n+1\) such choice sequences can reproduce those shares; choosing witness valuations with opposite next choices gives the same history but opposite next majorities. Thus the theorem’s protocol appears to satisfy the stated cohort condition, with support still small compared with a sufficiently large customer base. This is the constructive, tractable side in cut count, rather than a claim about running time.
These mirrors cover the paper’s forced-cut protocol design results about information revealed by repeated choices. They do not continuize the cake: it is already divisible. Nor do they cover the paper’s separate discussions of stochastic priors, truthfulness, or multi-agent cake division. Further questions include the gap between the one-dimensional lower bound excluding \(O(n)\) cuts and the paper’s \(\Theta(n^2)\)-cut construction, and how the minimum cut count depends on \(\tau\) or on coarser aggregate observations.
The weakest point is that the cohort question changes the information and success criterion: it observes aggregate shares and asks whether the *majority* response is uncertain, rather than whether a particular cutter can obtain more than half of their own value against one chooser. The two-dimensional lifting establishes the former, not a per-capita utility guarantee for a fixed society. A fixed finite type dictionary could also omit the witness valuations used by the paper’s proofs. The case survives as a precise population analogue of the paper’s information-leakage question, but it should not be presented as an exact restatement of the paper’s payoff notion.
The central mismatch is that the paper studies one persistent chooser, whose private valuation must explain their choices across days. The number \(n\) counts rounds, not members of a society. A large panel is possible to imagine, but it creates a fork: if everyone has the same type and faces the same offers, adding customers just duplicates the original game; if types differ and cutters observe aggregate responses, the object becomes a game about learning a population distribution.
Theorem 1.4 does transfer to the proposed cohort condition in a limited, precise sense. Because singleton societies are allowed, its universal requirement includes histories generated by one chooser. The theorem’s predictable-choice obstruction therefore rules out the proposed linear cut budget. But that conclusion comes entirely from the singleton case; it says nothing new about what population masses do. And the theorem bounds the number of physical cuts in a protocol, not the running time for solving a computational problem on a society.
Theorem 1.6 is the proponent’s strongest anchor. Its individual choice-sequence witnesses can plausibly be mixed to produce populations with the same past response shares and different next majorities. That is a valid aggregate-inference question. But opposite majority predictions do not capture the paper’s payoff guarantee. The cohort criterion tracks whether the share choosing a side can cross \(1/2\); the paper asks whether a cutter can secure more than half of *her own value* from the piece she receives. A protocol can leave the majority uncertain while doing little to protect against a cutter’s gain. To preserve the payoff question, one would need to specify how cutters interact with the cohort and define their value from the resulting allocation across types. That is a new model, not a population version of the theorem as stated.
The same fork applies to a better scenario, such as a recurring service that gives copies of a standardized cake to a large customer panel. With one homogeneous customer type, population size is a multiplier and the cut results carry over unchanged. With heterogeneous types, aggregate choice data and type-weighted cutter utility replace the paper’s single chooser and single valuation. That model might be worth studying, especially as a question about privacy or market-share inference, but the paper does not supply a computational problem or payoff definition for it.
So the negative case is strongest as a scope argument, not an impossibility claim: the proposed Theorem 1.4 mirror is population-inert, and the Theorem 1.6 mirror changes the target from exploitability to majority uncertainty. I would not object that cake cutting already has divisible outcomes, or that high-multiplicity work exists; neither point settles the population question. The weakness in my case is that the aggregate-inference extension is coherent and may be interesting in its own right. I just do not see it as a worthwhile continuous mirror of this paper under ChoCo’s computational brief.
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.