Combating Collusion Rings is Hard but Possible
This addresses the issue of biased acceptance in peer review for academic conferences, though it is incremental as it builds on known problems and methods.
The paper tackles the problem of collusion rings in academic peer reviewing by introducing the Cycle-Free Reviewing problem to eliminate review cycles where reviewers give favorable reviews to each other's papers, showing it is NP-hard in restricted cases but proving that assignments without small cycles exist in some realistic settings and providing an efficient heuristic that performs well in practice.
A recent report of Littmann [Commun. ACM '21] 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.