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.
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:
- Topological Ordering: Suitable for simplified cases.
- 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.
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