Combating Collusion Rings Is Hard but Possible

Niclas Boehmer, Robert Bredereck, André Nichterlein

Abstract

Peer-review integrity is increasingly threatened by collusion rings—groups of authors who coordinate to review and accept each other's work. This study investigates the computational complexity of eliminating these review cycles and proposes practical heuristics. While finding a cycle-free assignment is proven to be NP-hard, experimental results demonstrate that simple greedy algorithms can eliminate these rings with a negligible impact on overall review quality, maintaining over 96% of the optimal similarity weight.

Introduction

In academic publishing, the merit-based system relies on impartial peer review. However, "collusion rings" have emerged as a significant threat. These rings consist of authors who coordinate to review each other's papers, ensuring mutual acceptance. A simple 2-cycle occurs when Author A reviews Author B, and vice versa. Longer cycles (e.g., length $z$) create more complex dependencies that are harder to detect manually.

Current automated assignment tools used by major conferences typically optimize for reviewer-paper similarity scores but often fail to account for these cyclical dependencies. Research indicates that standard "optimal" assignments can leave a substantial portion of participants in review cycles, creating vulnerabilities for unethical behavior. For instance, in an assignment for 150 papers, up to 76% of agents can be part of a cycle of length 4 or less.

Standard assignments often result in a high fraction of agents participating in review cycles, especially as the number of papers increases.

Methodology

The researchers formalize the problem as CYCLE-FREE REVIEWING, modeled on a directed bipartite graph where vertices represent agents and papers, and edges represent authorship or potential review assignments.

Complexity and Algorithms

The study provides mathematical proofs showing that finding a cycle-free assignment is NP-hard, even under very restrictive conditions. To address this, they developed two greedy heuristics:

  1. Topological Ordering: Suitable for simplified cases.
  2. Greedy Re-wiring: A robust algorithm that assigns reviewers greedily and "re-wires" assignments—replacing one review with two others—to break cycles when the algorithm becomes stuck.

The performance of these heuristics was compared against "Optimal" assignments (via Linear Programming) and "Optimal Cycle-Free" assignments (via Integer Linear Programming) using a real-world dataset from ICLR 2018.

Key Results

The Low Cost of Integrity

A primary concern for conference organizers is that forbidding cycles might significantly degrade review quality by forcing the use of less qualified reviewers. However, the "price of freeness" is remarkably low. Results show that you can eliminate all 2-cycles with less than a 1% drop in total assignment weight (similarity). Even using the greedy heuristic, the drop remains within 3-4% of the theoretical maximum.

The normalized weight (similarity score) remains high even when enforcing cycle-free constraints, demonstrating that review quality is largely preserved.

Efficiency and Practicality

The proposed heuristic is highly efficient. For cycles of length 3 ($z=3$), it outperformed optimal ILP solvers by over 100 times in speed, consistently finding valid assignments in under 30 seconds. This makes it a practical addition to existing conference management software, which currently facilitates collusion by ignoring these dependencies.

Conclusion

The findings suggest that the prevalence of collusion rings in current conference assignments is a result of algorithmic choice rather than necessity. By implementing greedy heuristics, conference organizers can effectively eliminate these loopholes with minimal impact on the quality of the reviewer-paper match. Future work may extend these methods to detect more complex, non-cyclical collusion patterns, but the tools to break simple cycles are available today.

Summary updated

Abstract

A recent report of Littmann published in the Communications of the ACM outlines the existence and the fatal impact of collusion rings in academic peer reviewing. We introduce and analyze the problem Cycle-Free Reviewing that aims at finding a review assignment without the following kind of collusion ring: A sequence of reviewers each reviewing a paper authored by the next reviewer in the sequence (with the last reviewer reviewing a paper of the first), thus creating a review cycle where each reviewer gives favorable reviews. As a result, all papers in that cycle have a high chance of acceptance independent of their respective scientific merit. We observe that review assignments computed using a standard Linear Programming approach typically admit many short review cycles. On the negative side, we show that Cycle-Free Reviewing is NP-hard in various restricted cases (i.e., when every author is qualified to review all papers and one wants to prevent that authors review each other's or their own papers or when every author has only one paper and is only qualified to review few papers). On the positive side, among others, we show that, in some realistic settings, an assignment without any review cycles of small length always exists. This result also gives rise to an efficient heuristic for computing (weighted) cycle-free review assignments, which we show to be of excellent quality in practice.
BibTeX
@inproceedings{boehmer2022combating,
  author = {Niclas Boehmer and Robert Bredereck and André Nichterlein},
  title = {{Combating Collusion Rings Is Hard but Possible}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20412},
}
Figure