Combating Collusion Rings Is Hard but Possible

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 RE-VIEWING 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. We next prove that a c * reviews p c * for all c ∈ [k]. For this, we need the following lemma: then only vertex and dummy agents from class c ′ and special agents can review dummy and vertex papers from class c. Proof. Note that the special agent a c * is an author of all dummy and vertex papers from color class c. Moreover, paper p c ′ * is authored by all dummy and vertex agents from color classes different from c ′ . Thus, if a c * reviews p c ′ * , then no vertex or dummy agent from a class different from c ′ can review papers written by a c * . As a c * authors all dummy and vertex papers from class c, the lemma follows. Using this, we are able to prove that each special agent reviews the corresponding special paper. Lemma 4. In every 1-1 valid 2-cycle-free assignment in the constructed instance Proof. By Lemma 2, a * is assigned to p * , which is authored by all dummy agents and vertex agents. Thus, to prevent the existence of reviewing cycles, only special agents can review papers written by a * . As for each c ∈ For the sake of contradiction, let us assume that special agent a c * reviews paper We assume without loss of generality that c ′ < c (if there exists a pair where a c * reviews paper p c′ * with c < c′ there also has to exist one with c ′ < c). By Lemma 3 and as special agents need to review special papers, from this it follows that only dummy and vertex agents from color c ′ can review the vertex and dummy agents from class c (which are all written by a c * ). As we have assumed that c ′ < c, the number of these agents (2n + 2c ′ -3) does not suffices to review all of these papers (2n + 2c -3), a contradiction. We are now ready to prove the correctness of the backwards direction of the reduction: Lemma 5. If the constructed instance I ′ of CYCLE-FREE REVIEWING is a YES-instance, then the given instance I of MULTICOLORED INDEPENDENT SET is a YES-instance.