| paper | d4-conf-ijcai-2021-0403 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
The named results establish existence or nonexistence of fairness guarantees, but make no claim about allocation algorithms, running times, or the complexity of computing an allocation. Theorem 4.6(b) concerns which fairness guarantee is attainable, while the feedback vertex set hardness mentioned in a footnote concerns a separate graph problem. Bit (a) therefore fails, even though the paper could motivate a new computational fair-division project.
fails bit a — no named computational result to mirror
Theorem 3.2 and Theorem 4.4 establish maximin allocation existence for forests; Theorem 4.6(b) shows a fairness guarantee can fail. None gives a computational allocation result to mirror.
I can’t make an anchor-compliant case for a continuous mirror: the paper has no named result about the computational complexity or running time of a fair-allocation problem. Its results establish whether allocations exist, not how hard they are to compute.
The closest named result to a hardness anchor is Theorem 4.6(b), proved here: for every \(r\geq1\), there is a graph with feedback vertex set number \(r\)—a union of \(r\) cycles, possibly with trees—and \(n\) agents with additive valuations such that no allocation gives every agent at least \(\mathrm{MMS}_i^{N-1}\), where \(N=\min(n+r,2n-1)\). That is a nonexistence result for a fairness guarantee, not a computational hardness result. Theorem 3.2 and Theorem 4.4, also proved here, give existence guarantees for forests under different separation assumptions; they likewise make no algorithmic claim. The footnote to Theorem 3.4 mentions that computing the feedback vertex set number is NP-hard, citing Karp, but that is not a named result of this paper about computing fair allocations.
There is a plausible population regime: many residents dividing a road or land network, with residents grouped into a small number of shared valuation types. But turning that into the paper’s continuous-population problem would require defining how the maximin-share benchmark and resource supply scale with population. The paper does not do so, and its existence theorems do not provide computational anchors to mirror. The strongest honest positive claim is therefore only that its allocation questions might motivate future continuous computational work—not that this paper supplies a qualifying anchor or a precise mirror problem.
The strongest case against a mirror is that the paper supplies no computational result to mirror. Theorem 3.2 and Theorem 4.4 prove existence of maximin allocations; Theorem 4.6(b) proves that a particular fairness guarantee can fail. None gives a complexity bound or an algorithm. The NP-hardness mentioned in the footnote concerns computing a graph’s feedback vertex set, not computing an allocation. So a continuous version of these theorems would still be about existence or fairness guarantees, outside ChoCo’s computational brief.
The best version of the positive existence anchors would ask for an algorithm that constructs the allocation. But the paper allows arbitrary monotone continuous valuations and gives no input representation or oracle model for them; without one, there is no running time to study. Restricting valuations to a succinct family and supplying an oracle or encoding could make a computational problem, but its complexity would be a new result, not a mirror of the existence theorem. Theorem 4.6(b) has the same problem: optimizing the shortfall from its fairness guarantee could be a worthwhile new question, but the theorem itself makes no computational claim.
The suggested resident cohort does give a plausible high-multiplicity story. Its fit with the paper’s allocation model is the harder part. On a finite graph with positive separation, only finitely many nonempty pieces can be mutually \(s\)-separated, so an atomless population cannot each receive a piece. With zero separation, extending the model to atomless agents either makes almost all individual pieces valueless on a fixed finite cake or requires a new definition of the maximin-share benchmark. Assigning an average bundle to each valuation type does not resolve this: an average need not be a connected piece, and it does not ensure the individual disjointness or separation constraints. Scaling the network with the population might repair the capacity issue, but then the graph and benchmark belong to a new limiting model whose computational questions this paper does not anchor.
The cake’s geometric continuity is already present in the paper, but it is continuity of the resource, not of the population. Overall, the negative case is strong for the paper as written: its named results do not pose computational questions, and a natural atomless extension strains the individual allocation constraints. The universal claim is less secure. A carefully designed scaled-network model with finitely many succinct valuation types might be worth studying, but that would be a new computational fair-division project rather than a continuous mirror of these results.
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.