| paper | Combating Collusion Rings Is Hard but Possible |
| authors | Niclas Boehmer, Robert Bredereck, André Nichterlein |
| venue | AAAI 2022 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | no |
The paper clearly satisfies the computational bit through Theorems 2 and 4. However, both proposed mirrors replace individual-cycle exclusion with a stricter type-support condition, and the opponent's shifted-copy construction demonstrates that the two are not equivalent under genuine multiplicity. A faithful continuous version would need an individual-level measurable assignment or graphing, which the proposed finite type-mass questions do not provide.
fails bit b — no continuous question survives
The proposed type-level prohibition can reject assignments with no actual collusion cycle, while retaining the exact predicate requires individual identity or measurable fibre structure absent from the stated models.
fatal: True
The proposed mirror covers Theorems 4 and 2, but neither survives the identity objection; the paper's remaining hardness, algorithmic, and experimental results are not continuized.
The strongest mirror I see is a high-multiplicity review-assignment problem in which the forbidden object is a cycle in the positive type-support. This is genuinely population continuization: reviewers and papers become mass distributions over recurring role types, while authorship and review eligibility remain part of the instance.
My lead anchor is Theorem 4 (⋆), proved by the authors rather than cited from elsewhere. It shows that CYCLE-FREE REVIEWING is NP-hard even when \(z=3\), \(c_{\mathrm{reviewer}}=d_{\mathrm{paper}}=2\), every agent writes exactly one single-author paper, \(n_A=n_P\), every agent is qualified to review exactly four papers, and qualification is symmetric.
A plausible high-multiplicity regime is a large reviewing service operating over many parallel tracks or repeated submission cohorts. There are \(\tau\) reviewer-role types, and \(K\) agents of each type, with \(K\gg\tau\). Every agent of type \(t\) writes one paper of the corresponding paper type \(t\), has the same expertise and conflict profile, and can review papers in exactly four eligible paper-type classes. Qualification is symmetric at the type level. Thus the number of agents and papers is \(K\tau\), while the relevant description has only \(\tau\) types.
Call the resulting problem HM-\(2\)-\(2\)-\(3\) Type-Cycle-Free Reviewing. An instance consists of a finite type set \(T\), a rational mass distribution \(\mu\in\Delta(T)\), and a symmetric irreflexive relation \(Q\subseteq T\times T\) in which every type has exactly four neighbours. The mass \(\mu_t\) is the fraction of reviewers and papers of type \(t\). A variable \(x_{t,u}\) is the mass of type-\(t\) reviewers assigned to papers of type \(u\). We ask whether there exists \(x\) satisfying
\[ 0\le x_{t,u}\le \min\{\mu_t,\mu_u\}, \]
\[ x_{t,u}=0\quad\text{if }(t,u)\notin Q, \]
\[ \sum_{u\in T}x_{t,u}\le 2\mu_t \quad\text{for every reviewer type }t, \]
and
\[ \sum_{t\in T}x_{t,u}=2\mu_u \quad\text{for every paper type }u, \]
such that the directed type-support graph containing \(t\to u\) whenever \(x_{t,u}>0\) has no directed cycle of length at most \(3\). A solution is precisely such a mass assignment; the objective is feasibility, matching the unweighted theorem.
This is not merely a tractable surrogate. On uniform masses \(\mu_t=1/\tau\), let \(y_{t,u}=\tau x_{t,u}\). Then \(y\) is a fractional bipartite \(2\)-matching with edge capacities \(1\). The bipartite \(b\)-matching polytope is integral, so any feasible support contains an integral \(2\)-factor. Since taking a subset of a cycle-free support cannot create a short cycle, a feasible continuous solution exists exactly when the corresponding discrete type graph has a \(2\)-valid, \(3\)-cycle-free assignment. The theorem-4 hardness therefore transfers: the combinatorics live in the qualification graph on types, not in the number \(K\) of repeated agents. I would classify this mirror as Class B.
The paper’s authors should recognize this as their problem after collapsing identical copies. The review assignment remains the decision variable, authorship is still what turns review edges into directed cycles, the capacities and cycle bound are unchanged, and mass is simply the high-multiplicity representation of many indistinguishable reviewer-paper pairs. The literal statement “four eligible papers per individual” becomes “four eligible paper classes per type,” which is the meaningful aggregate version.
A second, independently useful anchor is Theorem 2 (⋆), also proved by the authors. It removes the sparse-neighbourhood assumption: every agent is qualified to review every paper, \(n_A=n_P\), \(c_{\mathrm{reviewer}}=d_{\mathrm{paper}}=1\), and \(z=2\). Its continuous mirror, HM-Dense-\(2\)-Cycle-Free Reviewing, has reviewer masses \(\mu\), paper masses \(\nu\), an authorship relation \(H(p,t)\) saying that type \(t\) authors paper type \(p\), and variables \(x_{t,p}\) satisfying
\[ \sum_p x_{t,p}\le\mu_t,\qquad \sum_t x_{t,p}=\nu_p,\qquad 0\le x_{t,p}\le\min\{\mu_t,\nu_p\}. \]
All reviewer types may review all paper types. The positive support must contain neither a self-cycle \(H(p,t)\land x_{t,p}>0\) nor a two-cycle formed by two cross-assigned reviewer-paper edges. With uniform masses, scaling gives a fractional perfect matching, and integrality of the matching polytope again yields a discrete cycle-free assignment. Thus this mirror also plausibly lies in Class B. It is valuable because it shows that the mirror does not depend on scarcity of qualifications or on an artificial sparse expertise graph.
I would scope the claim to these two hardness results. I am not claiming that the paper’s weighted experiments, Corollary 1, or the polynomial-time propositions have already been continuized. Natural follow-up problems include weighted mass assignment,
\[ \max\sum_{t,u}w_{t,u}x_{t,u}, \]
parameterized complexity in \(z\) and the type-interaction graph, and rounding guarantees for nonuniform masses.
The weakest point is the cycle semantics. In an atomless population, a type-level cyclic support might sometimes be implemented by an aperiodic matching of individual agents, avoiding literal individual cycles. My formulation deliberately treats a positive type-level cycle as a persistent collusion-ring template, because that is the structure a review system can detect and prohibit uniformly across a high-multiplicity class. If one insists on forbidding only exact named-agent cycles, the continuous condition may become much weaker or even vacuous. That is a real modeling choice, but it does not make the stated type-support problem artificial: it is a precise, operational high-multiplicity version of the paper’s central question.
The strongest negative case is that the paper’s central predicate is not population-additive. CYCLE-FREE REVIEWING is not primarily about how much review mass flows between classes; it is about whether named reviewers and named authors form a short directed cycle.
For Theorem 4, collapse each single-author paper into its author and write an arc \(a\to b\) when \(a\) reviews \(b\)’s paper. The theorem asks for a bounded-degree directed graph with no cycle of length at most \(3\). A type-flow variable \(x_{t,u}\) records only how much mass travels from reviewer type \(t\) to paper type \(u\). It does not determine whether the underlying individual arcs form a cycle.
This is not a technical nuisance. Take three replicated types with aggregate flows \(A\to B\), \(B\to C\), and \(C\to A\). With \(K\) copies of each type, one can route these flows as
\[ A_i\to B_i,\qquad B_i\to C_i,\qquad C_i\to A_{i+1}, \]
with indices modulo \(K\). The type-support graph contains a directed \(3\)-cycle, but the individual assignment need not contain any \(3\)-cycle. The same phenomenon exists in the atomless limit: on a unit interval, use irrational rotations such as \(r\mapsto r+\alpha\). The aggregate type flow is unchanged, while all finite individual cycles disappear.
Thus the proponent’s prohibition on cycles in positive type support is not the high-multiplicity version of Theorem 4. It is a stricter, newly invented policy: prohibit any cyclic pattern among role classes, even when the actual assignment has no collusion ring. That may be a defensible administrative rule, but the paper’s theorem does not establish its relevance or hardness. At \(K=1\), the proposed model does reproduce the original instance, but then the “continuous” population is merely a uniform encoding of the original finite graph. At \(K>1\), the claimed equivalence fails.
The faithful continuous analogue fares no better. One would need to retain a measurable assignment on individual fibres, not just \(x\), and require that this graphing contain no short cycles. But exact finite cycles have zero population measure in an atomless society and can generally be removed by measure-preserving rewirings without changing type-level flows or aggregate weights. Replacing “there exists a cycle” by “a positive fraction of agents lies in cycles” makes the limit quantitative and potentially meaningful, but it is a different robustness problem from the theorem’s exact feasibility question.
Theorem 2 has the same obstruction, despite its dense qualification graph. Its two-cycle condition depends on the specific pairing
\[ a\text{ reviews a paper authored by }b \quad\text{and}\quad b\text{ reviews a paper authored by }a. \]
The aggregate relation \(H(p,t)\) and flow \(x_{t,p}\) do not say whether the two assignments involve the same individuals. Positive flows in both directions can be implemented using disjoint copies and cyclically shifted pairings, with no individual two-cycle. Conversely, a type-level prohibition on such flows rules out assignments that are perfectly cycle-free at the agent level. Again, \(K=1\) is the original problem; genuine replication changes the semantics.
To preserve the exact predicate, one must add individual coordinates, the author–paper matching, and a measurable review relation. If those coordinates are arbitrary, the agents are no longer represented by finitely many complete types; if they are discretized, one is back to the finite graph problem. The mass vector alone is insufficient because identity is not incidental here—it is exactly what defines a collusion ring.
There is a possible new research direction in forbidding “cyclic type templates” or minimizing the mass of agents participating in cycles. But that would be a new type-level network-design problem, not a continuous mirror of Theorems 2 or 4. The proponent’s Class B conclusion therefore rests on the \(K=1\) shadow of the paper, while the genuinely high-multiplicity limit either forgets the cycle predicate or makes it vanish.
This is not an airtight universal proof that no peer-review continuization could ever be useful. A deliberately type-level collusion policy might be worth studying. But against the two anchors actually offered, the negative case is strong: the paper’s defining object is relational individual identity, and the proposed mass models replace it with a different support constraint.
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.