On Strategyproof Conference Peer Review

1 Introduction

Peer review serves as an effective solution for quality evaluation in reviewing processes, especially in academic paper review [D¨orfler et al., 2017, Shah et al., 2017] and massive open online courses (MOOCs) [D´ıez Pel´aez et al., 2013, Piech et al., 2013, Shah et al., 2013]. However, despite its scalability, competitive peer review faces the serious challenge of being vulnerable to strategic manipulations [Anderson et al., 2007, Thurner and Hanel, 2011, Alon et al., 2011, Kurokawa et al., 2015, Kahng et al., 2018]. By manipulating the ratings or rankings provided reviewers may be able to increase the chance that their own submissions get accepted. As noted by Thurner et al. [2011], even a small number of selfish, strategic reviewers can drastically reduce the quality of scientific standard. Thus the importance of peer review in academia and its considerable influence over the careers of researchers significantly underscores the need to design peer review systems that are insulated from strategic manipulations. Presentday peer-review systems are, however, ill-equipped to handle strategic behavior, and do not have any rigorous framework in place except some basic checks like not assigning a paper to a conflicted reviewer. It is easy to show that these checks are insufficient, that is, reviewers can manipulate the final ranking of their conflicted papers by strategically manipulating their reports in current peer-review systems.

˚Equal contribution.

In this work, we present a framework for conference peer review that addresses the problem of strategic behavior. Our problem setup comprises a set of submitted papers and a set of reviewers. We are given a graph which we term as "conflict graph". The conflict graph is a bipartite graph with the reviewers and papers as the two partitions of vertices, and an edge if there exists a conflict between the reviewer and the paper. Conflicts may arise due to authorship or other reasons such as institutional conflicts. Given this, there are two design steps in the peer review procedure: (i) assigning each paper to a subset of reviewers, and (ii) aggregating the review results provided by the reviewers to give a final evaluation of each paper.

We focus on ordinal preferences where each reviewer is asked to give a total ranking of the assigned papers, as ordinal data avoids biases and miscalibrations and provides a more direct comparison between papers [Barnett, 2003, Stewart et al., 2005, Douceur, 2009, Tsukida and Gupta, 2011, Shah et al., 2013, Shah et al., 2016]. Some modern large conferences (e.g., NeurIPS [Shah et al., 2017]) have also collected ordinal preferences for experimental purposes. Also, our methods can be extended easily to a score-based review system (cf. Section 4.1). Under the setting, we require our mechanism to output a total ranking over all papers, since this automated output in practice would be a guideline for program chairs to make their decisions (e.g., orals, posters, best papers, etc.).

We consider two important goals for designing a good conference review procedure - strategyproofness and efficiency. In our context, strategyproofness means that no reviewer can change the outcome of any papers which she/he has a conflict with, and efficiency means that the final output of the procedure reflects the opinion of most reviewers. Here, we consider efficiency in terms of the notion of unanimity in social choice theory: an agreement among all reviewers must be reflected in the final aggregation.

In addition to the conceptual contributions, we make several technical contributions towards this important problem. We first design a peer review framework which theoretically guarantees strategyproofness along with a notion of efficiency that we term as "group unanimity". With only a mild and realistic assumption on the conflict graph, we establish our positive results for the peer review design task. Importantly, our framework and the specific algorithms are quite flexible in that it guarantees strategyproofness and unanimity, while also leaving open a significant room for program chairs to implement their choice of decision-making strategies.

On the practical front, we validate that the aforementioned assumption indeed holds in practice via an empirical analysis of the submissions made to the International Conference on Learning Representations 2017 (ICLR-17). Furthermore, we demonstrate a simple trick to make the partitioning method more practically appealing for conference peer review and present it on the ICLR-17 data.

We also complement our positive results with negative results showing that one cannot expect to meet requirements that are stronger than that provided by our framework. First, we show that under mild assumptions on the conflict graph, there is no algorithm that satisfies "pairwise unanimity", which is a stronger notion of efficiency than group unanimity, and is also known as Pareto efficiency in the literature of social choice [Brandt et al., 2016]. Second, we provide a conjecture and insightful results to show that if we require the assignment to satisfy a simple "connectivity" condition, our negative result continues to hold even when the notion of strategyproofness is made extremely weak. These negative results highlight the intrinsic hardness in designing strategyproof conference review systems.

2 RelatedWork

As early as in the 1970s, Gibbard and Satterthwaite had already been aware of the importance of a healthy voting rule that guarantees strategyproofness under the setting of social choice [Gibbard, 1973, Satterthwaite, 1975]. Recently, the fact that prominent peer review mechanisms are manipulable, has further called for strategyproof peer reviewmechanisms [Merrifield and Saari, 2009, Hazelrigg, 2013]. Our work is most closely related to a series of works on strategyproof peer selection [Alon et al., 2011, Holzman and Moulin, 2013, Fischer and Klimm, 2015, Kurokawa et al., 2015, Aziz et al., 2016, Kahng et al., 2018], where agents cannot benefit from misreporting their preferences over other agents. In all these works, each agent is essentially required to evaluate all the other agents except herself. This is impractical for conference peer review, where each reviewer only has to review a small subset of submissions. In light of such constraints, Kurokawa et al. [2015] propose a strategyproof (impartial) mechanism and provide associated approximation guarantees in which each agent is only required to review a few other agents, but their algorithm might return an empty set. Based on their work, Aziz et al. [2016] then propose an improved mechanism for peer selection which is strategyproof and satisfies a natural monotonicity property. However, even if the target output size is k, it may return a subset of size strictly larger than k. Past works focus on applications of peer-grading and grant proposal review, and hence consider only the case where every reviewer is conflicted with exactly one paper. In contrast, our setting of conference peer review is more challenging: We allow each reviewer to have conflicts with multiple papers and each paper to have conflicts with multiple reviewers. Formally, the conflict graph C under conference peer review is a more general bipartite graph, where conflicts between reviewers and papers can arise not only because of authorships, but also advisor-advisee relationships, institutional conflicts, etc.

3 Problem Setting

We define R :" tr1↪ ▷ ▷ ▷ ↪ rmu to be the set of m reviewers and P :" tp1↪ ▷ ▷ ▷ ↪ pnu to be the set of n submitted papers. To characterize conflicts of interest, we use a bipartite graph C with vertices pR↪ Pq, where an edge is connected between a reviewer r and a paper p if there exists some conflict of interests between the r and p. Given the set of submitted papers and reviewers, the conflict graph is fixed and cannot be controlled. Note that the conflict graph C defined above can be viewed as a realistic generalization of the authorship graph in the previously-studied settings of peer grading and grant proposal review, in which each reviewer (paper) is connected to at most one paper (reviewer).

The review process is modeled by a second bipartite graph G, termed as review graph, that also has the reviewers and submissions pR↪ Pq as its vertices. This review graph has an edge between a reviewer and a paper if that reviewer reviews that submission. For each reviewer ri pi P rmsq, we let Pi Ñ P denote the set of papers assigned to this reviewer for review, or in other words, the neighborhood of node ri in the bipartite graph G. To ensure balanced workloads across reviewers, we require that every reviewer is assigned at most θ papers for some integer 1 § θ § n. In other words, every node in R has at most θ neighbors (in P) in graph G. Additionally, each paper must be reviewed by at least λ reviewers for some integer 1 § λ § m. Thus every node in the set P must have at least λ neighbors (in R) in the graph G. For any (directed or undirected) graph H, we let the notation EH denote the set of edges in graph H.

At the end of the reviewing period, each reviewer provides a total ranking of the papers that she/he reviewed. For any set of papers P 1 Ñ P, we let ⇧pP 1 q denote the set of all permutations of papers in P 1 . Furthermore, for any paper pj P P 1 and any permutation ⇡pP 1 q P ⇧pP 1 q, we let ⇡jpP 1 q denote the position of paper pj in the permutation ⇡pP 1 q. At the end of the reviewing period, each reviewer ri submits a total ranking ⇡piq pPiq P ⇧pPiq of the papers in Pi. We define a (partial) ranking profile ⇡ :" p⇡p1q pP1q↪ ▷ ▷ ▷ ↪ ⇡pmq pPmqq as the collection of rankings from all the reviewers. When the assignment P1↪ ▷ ▷ ▷ ↪ Pm of papers to reviewers is fixed, we use the shorthand p⇡p1q ↪ ▷ ▷ ▷ ↪ ⇡pmq q for profile ⇡. For any subset of papers P 1 Ñ P, we let ⇡P 1 denote the restriction of ⇡ to only the induced rankings on P 1 . Finally, when the ranking under consideration is clear from context, we use the notation p ° p1 to say that paper p is ranked higher than paper p1 .

Under this problem setup, the goal is to jointly design: (a) a paper-reviewer assignment scheme, that is, edges of the graph G, and (b) an associated review aggregation rule f : ±mi"1 ⇧pPiq Ñ ⇧pPq which maps from the ranking profile to an aggregate total ranking of all papers. For any aggregation function f, we let fjp⇡q be the position of paper pj when the input to f is the profile ⇡.

Although we assume ordinal feedback from the reviewers, our results continue to hold if we have review scores as our input instead of rankings; our framework is flexible enough to take the scores into account (cf. Section 4.1). In what follows we define strategyproofness and efficiency that any conference review mechanism f should satisfy under our setting. Due to space limit, we omit all the proofs and refer interested readers to an online version [Xu et al., 2018] for all the further details.

3.1 Strategyproofness

In the context of conference review, strategyproofness is defined with respect to a given conflict graph C. It means that a reviewer cannot change the position of her conflicting papers, by manipulating the ranking she provides.

Definition 1 (Strategyproofness, SP). A review process pG↪ fq is called strategyproof with respect to a conflict graph C if for every reviewer ri P R and every paper pj P P with pri↪ pjq P EC, under assignment G, for every pair of profiles that differ only in the ranking given by reviewer ri, the position of pj is unchanged. Formally, for every ⇡ " p⇡p1q ↪ ▷ ▷ ▷ ↪ ⇡pi´1q ↪ ⇡piq ↪ ⇡pi`1q ↪ ▷ ▷ ▷ ↪ ⇡pmq qq and ⇡1 " p⇡p1q ↪ ▷ ▷ ▷ ↪ ⇡pi´1q ↪ ⇡piq 1 ↪ ⇡pi`1q ↪ ▷ ▷ ▷ ↪ ⇡pmq q, the results remain unchanged as fjp⇡q " fjp⇡1 q.

A strategyproof peer review procedure alone is inadequate with respect to any practical requirements - simply giving out a fixed, arbitrary evaluation makes the peer review procedure strategyproof. We therefore consider efficiency of the procedure in the next section, to ensure that the authors receive meaningful and helpful feedback for their work.

3.2 Efficiency (Unanimity)

We consider efficiency of a peer review process in the notion of "unanimity", which is one of the most prevalent and classic properties to measure the efficiency of a voting system in the literature of social choice [Fishburn, 2015]. At a colloquial level, unanimity states that when there is a common agreement among all reviewers, the aggregation of the opinions must also respect this agreement. We discuss two kinds of unanimity, termed as group unanimity (GU) and pairwise unanimity (PU). Both kinds of unanimity impose requirements on the aggregation function for given paper-reviewer assignment. The group unanimity is defined as follows:

Definition 2 (Group Unanimity, GU). The pair pG↪ fq is said to be group unanimous (GU) if the following condition holds for every possible profile ⇡: For every set of papers P 1 Ä P such that every reviewer ranks the papers she reviewed from P 1 higher than those she reviewed fromPzP 1 , the output fp⇡q must satisfy px ° py for every pair of papers px P P 1 and py P PzP 1 such that at least one reviewer has reviewed both px and py.

Intuitively, group unanimity says that if papers can be partitioned into two sets such that every reviewer who has reviewed papers from both sets agrees that the papers she has reviewed from the first set are better than what she reviewed from the second set, then the final output ranking should respect this agreement. Our second notion of unanimity, termed pairwise unanimity, is a local refinement of group unanimity. This notion is identical to the classical notion of unanimity stated in Arrow's impossibility theorem [Arrow, 1950]. Notice that the classical unanimity considers every reviewer to review all papers (that is, Pi " P↪ @i P rms), whereas our notion is generalized to settings where reviewers may review only a subset of papers.

Definition 3 (Pairwise Unanimity, PU). We define pG↪ f q to be pairwise unanimous (PU) if the following condition holds for every possible profile ⇡ and every pair of papers pj1 ↪ pj2 P P: If at least one reviewer has reviewed both pj1 and pj2 and all the reviewers that have reviewed pj1 and pj2 agree on pj1 ° pj2 , then fj1 p⇡q ° fj2 p⇡q.

An important property is that pairwise unanimity is stronger than group unanimity.

Proposition 1. If pG↪ fq is pairwise unanimous, then pG↪ fq is also group unanimous.

4 Positive Results

In this section we consider the design of paper-reviewer assignments and aggregation rules for strategyproofness and group unanimity (efficiency). Prior works on this topic consider a specific and restricted class of conflict graphs - - those with one-to-one relations between papers and reviewers - which do not capture conference peer review settings. We consider a more general class of conflict graphs and present an framework based on the partitioning-based method [Alon et al., 2011], which we show can achieve group unanimous and strategyproofness. The key idea is to assign a paper to a reviewer only if there is no path between this paper and reviewer in the conflict graph C. We then empirically demonstrate, using submission data from the ICLR-17 conference, that this class of conflict graphs is indeed representative of peer review settings. In addition to the feasibility, we present a simple trick to improve the practical appeal of our framework (and more generally the partitioning method) to conference peer review.

4.1 The Divide-and-Rank Framework

We now present our "Divide-and-Rank" framework consisting of the reviewer assignment algorithm (Algorithm 1) and the rank aggregation algorithm (Algorithm 2). At a higher level, our framework performs a partition of the reviewers and papers for assignment, and aggregates the reviews by computing a ranking which is consistent with any group agreements. Divide-and-Rank works for a general conflict graph C as long as the conflict graph can be divided into two reasonably-sized disconnected components.

Importantly, the framework is simple yet flexible in that the assignment within each partition and the aggregation among certain groups of papers can leverage any existing algorithm for assignment and aggregation respectively, which is useful as it allows to further optimize various other metrics in addition to strategyproofness and unanimity.

The Divide-and-Rank assignment algorithm begins by partitioning the conflict graph into two disconnected components

Algorithm 1 Divide-and-Rank assignment

Input: conflict graph C, parameters λ↪ θ, assignment algorithm A

Output: an assignment of reviewers to papers

• 1: pRC↪PCq, pRsC ↪PsC q -PartitionpC↪ λ↪ θq
• 2: use algorithm A to assign papers P sC to reviewers RC

5:

• 3: use algorithm A to assign papers PC to reviewers RsC 4: return the union of assignments from step 2 and 3
• 6: procedure PARTITION(conflict graph C, parameters λ↪ θ)
• 7: run a BFS on C to get connected K components tpRk ↪ PkquKk"1
• 9: initialize a table Tr¨↪ ¨↪ ¨s P t0↪ 1uKˆpm`1qˆpn`1q so that T r1↪ r1↪ p1s " T r1↪ 0↪ 0s " 1, otherwise 0
• 8: let rk " |Rk|↪ pk " |Pk|, @k P rKs
• 10: for k " 2 to K do
• 12: end for
• 11: T rk↪ r↪ ps " T rk ´ 1↪ r↪ ps _ T rk ´ 1↪ r ´ rk ↪ p ´ pks↪ @0 § r §m↪ 0 § p § n
• 13: for 0 § r § m↪ 0 § p § n, if there is no T rK↪ r↪ ps " 1 such that maxt p m´r ↪ n´p r u § θλ , return ERROR
• 14: use the standard backtracking in the table Tr¨↪ ¨↪ ¨s to return pRC↪ PCq and pR sC ↪ P sC q 15: end procedure

that meet the requirements specified by θ and λ. Although dividing into more groups can lead to similar unanimity and strategyproof properties, we use two groups for simplicity and computational efficiency. The subroutine Partition first runs a breadth-first-search (BFS) algorithm to partition the original conflict graph into K connected components, where the kth connected component contains rk · 0 reviewers and pk · 0 papers. Next, the algorithm performs a dynamic programming to compute all the possible subset sums achievable by the K connected components. Here T rk↪ r↪ ps " 1 means that there exists a partition of the first k components such that one side of the partition has r reviewers and p papers, and 0 otherwise. The last step is to check whether there exists a subset C satisfying the requirement, and if so, runs a standard backtracking algorithm along the table to find the actual subset C. Clearly the Partition runs in OpKnmq, and since K § n`m, it runs in polynomial time in the size of the input conflict graph C.

In the next step, the algorithm assigns papers to reviewers in a fashion that guarantees each paper is going to be reviewed by at least λ reviewers and each reviewer reviews at most θ papers. The assignment of papers in any individual component (to reviewers in the other component) can be done using any assignment algorithm (taken as an input A) as long as the algorithm can satisfy the pθ↪ λq-requirements. Possible choices for the algorithm A include the popular Toronto paper matching system [Charlin and Zemel, 2013] and others [Hartvigsen et al., 1999, Garg et al., 2010, Stelmakh et al., 2018].

We then introduce the aggregation procedure in Algorithm 2. Generally speaking, the papers in each component are aggregated separately using the subroutine Contract-and-Sort. This aggregation in Contract-and-Sort is performed by a topological ordering of all strongly connected components (SCCs) according to the reviews, and then ranking the pa-

Algorithm 2 Divide-and-Rank aggregation

• Input: profile ⇡ " p⇡p1q pP1q↪ ▷ ▷ ▷ ↪ ⇡pmq pPmqq, groups pRC↪ PCq↪ pR sC ↪ P sC q with |PC| · |P sC |, aggregation algorithm B
• 1: compute ⇡C as the restriction of profile ⇡ to only papers in PC , and ⇡ ¯ C as the restriction of profile ⇡ to only papers
• in P sC 2: ⇡C -Contract-and-SortpB↪⇡Cq
• 3: ⇡ sC -Contract-and-SortpB↪⇡ ¯ Cq 4: define I " ´Y n |PC| ] ↪ Y 2n |PC| ] ↪ ▷▷▷↪ n¯

Output: total ranking of all papers

6:

• 7: procedure CONTRACT-AND-SORT(aggregation algo-
• 5: return total ranking obtained by filling papers in PC into positions in I in order given by ⇡C, and papers in P sC into positions in rnszI in order given by ⇡ sC
• rithmB, profile r⇡ " p⇡p1q ↪ ▷ ▷ ▷ ↪ ⇡pm1 q q) 8: build a directed graph Gr⇡ with the papers in r⇡ as its vertices and no edges
• 9: for each i P rm1 s do
• 12: compute a topological ordering of the strongly con-
• 10: Suppose ⇡piq " ppj1 ° ▷ ▷ ▷ ° pjti ), add a directed edge from pjk to pjk`1 in Gr⇡, @k P rti ´ 1s 11: end for
• nected components (SCCs) in Gr⇡ 13: for every SCC in Gr⇡, compute a permutation of the papers in the component using algorithmB
• 14: return the permutation of all papers that is consistent with the topological ordering of the SCCs and the permutations within the SCCs
• 15: end procedure

pers within each set using any arbitrary aggregation algorithm (taken as an input B) 1 . Possible choices for the algorithmB include the modified Borda count [Emerson, 2013], PlackettLuce aggregation [Hajek et al., 2014], or others [Caragiannis et al., 2017]. Moving back to Algorithm 2, the two rankings returned by Contract-and-Sort respectively for the two components are simply interlaced to obtain a total ranking over all the papers: the slots for C are reserved in set I, and rnszI contain the slots for the remaining papers. In our extended version of the paper we also show that the interleaving only causes a small change w.r.t an underlying optimal ranking. The following theorem now shows that Divide-and-Rank satisfies group unanimity and is strategyproof.

Theorem 1. Suppose C can be partitioned into two groups pRC↪PCq and pRsC ↪PsC q such that there are no edges in C across the groups and that max |PC| |RÑ C | ↪ |PÑ C | |RC| ( § θλ . Then Divide-and-Rank is group unanimous and strategyproof.

Remark. Our Divide-and-Rank framework aptly handles the various nuances of real-world conferences peer review, which render other existing methods inapplicable. This includes the facts that each reviewer can have conflicts with multiple papers and each paper can have conflicts with multiple reviewers, and furthermore that each reviewer may review only a subset of papers. Even under this challenging setting, our framework guarantees that no reviewer can influence the ranking of her own paper via strategic behavior, and that it is efficient from a social choice perspective.

1 In the case where there are multiple topological orderings, any one of them suffices.

Extension to review scores. Our framework can easily extend to a score-based setting, wherein each reviewer ri provides a score sij for every paper pj P Pi. The assignment algorithm remains the same in this setting; for aggregation, we can use the same procedure with the ranking induced by the review scores. The only difference is that in step 10 of Contract-and-Sort, we add an edge between every pair of papers pj1 Ñ pj2 if sij1 ° sij2 . This makes sure that the graph fully reflects the opinion of the reviewer and do not impose constraints on papers that are equally rated. On the other hand, the aggregation algorithmB can also leverage the review scores for a more granularized ranking (e.g., average scores). Our definition of unanimity and strategyproof can also be straightforwardly extended to the score setting, and our framework still preserves these properties under these definitions. See our extended version of this paper [Xu et al., 2018] for further details.

4.2 Analysis of ICLR-17 Submissions

Our Divide-and-Rank framework is based on a partitioning method that relies on a partition of the set of reviewers and papers so that there is no conflict across the partition. In this subsection we restrict attention to the authorship conflict graph, where we empirically verify that the partitioning conditions indeed hold in a conference peer review setting using data from the ICLR-17 conference. We then demonstrate how to make the partitioning method more appealing for conference peer review. In particular, we show that removing only a small number of reviewers can drastically reduce the size of the largest component in the conflict graph, thus providing great flexibility towards partitioning the papers and authors.

We analyzed all papers submitted to ICLR-17 with the given authorship relationship as the conflict graph. ICLR-17 received 489 submissions by 1,417 authors; we believe it is a good representative of a medium-sized modern conference. It is important to note that we consider only the set of authors as the entire reviewer pool (since we do not have access to the actual reviewer identities). Adding reviewers from outside the set of authors would only improve the results since these additional reviewers will have no edges in the (authorship) conflict graph. We first investigate the existence of (moderately sized) components in the conflict graph,which shows that the authorship graph is not only disconnected, but also has more than 250 components. The largest connected component(CC) contains 133 (that is, about 27%) of all papers, and the 2nd largest CC is much smaller, hence empirically verify our assumptions in Theorem 1.

The partitioning method is previously considered for the problem of peer grading [Kahng et al., 2018], where the setting is quite homogeneous in that each reviewer (student) goes through the same course and hence any paper (homework) can be assigned to any reviewer. In peer review, however, different reviewers typically have different areas of expertise and hence their abilities to review any paper varies by the area of the paper. In order to accommodate this diversity in area of expertise in peer review, one must have a greater flexibility in terms of paper assignment. In our analysis, the largest CC contains 372 authors and 133 papers. It is reasonable to expect that a large number of reviewers with expertise required to review these 133 papers would also be in the same CC, thus a na¨ıve application of Divide-and-Rank would assign these 133 papers to reviewers who may have a much less expertise. This is indeed a concern, and in what follows, we discuss a simple yet effective way to ameliorate this problem.

We show empirically using the ICLR-17 data that by removing only a small number of authors from the reviewer pool of the ICLR-17 data, the conflict graph can be much more sparse, allowing for more flexible application of Divide-and-Rank. Specifically, we remove a small fraction of authors from the reviewer pool using the simple heuristic of removing the authors with the maximum degree in the (authorship) conflict graph. We then study the statistics of the resulting conflict graph (with all papers but only the remaining reviewers) in terms of the numbers and sizes of the CC. The results are shown in Table 1. After removing a small fraction - 100 authors which is only about 7% - the number of papers in the largest CC reduces by 94% to just 8. Likewise, the number of authors in the largest CC reduces to as small as 28 from 371 originally. It demonstrates that despite all the idiosyncrasies of conference peer review, the Divide-and-Rank and partitioning can be made practically applicable.

5 Negative Results

The positive results in the previous section focus on group unanimity, which is weaker than the conventional notion of unanimity, also known as pairwise unanimity. Moreover, the framework induces a disconnected review graph whereas the review graphs of conferences today are typically connected [Shah et al., 2017]. It is thus natural to ask the following: Can a peer review system with a connected reviewer graph satisfy these properties? Can a strategyproof peer review system be pairwise unanimous? In this section we present some negative results toward these questions, thereby highlighting the critical impediments towards stronger results. Before stating our results, we give another notion of strategyproofness, which is significantly weaker than the notion of strategyproofness (Definition 1), and is hence termed as weak strategyproofness.

Definition 4 (Weak Strategyproofness, WSP). A review process pG↪ fq is called weakly strategyproof, if for every reviewer ri, there exists some paper pj P P such that for every pair of distinct profiles (under assignment G) ⇡ " p⇡p1q ↪ ▷ ▷ ▷ ↪ ⇡pi´1q ↪ ⇡piq ↪ ⇡pi`1q ↪ ▷ ▷ ▷ ↪ ⇡pmq q and ⇡1 " p⇡p1q ↪ ▷ ▷ ▷ ↪ ⇡pi´1q ↪ ⇡piq 1 ↪ ⇡pi`1q ↪ ▷ ▷ ▷ ↪ ⇡pmq q, it is guaranteed that fjp⇡q " fjp⇡1 q.

In other words, weak strategyproofness requires for each reviewer there is at least one paper (not necessarily authored by this reviewer) whose ranking cannot be influenced by the reviewer. As the name suggests, strategyproofness is strictly stronger than weak strategyproofness, when each reviewer has at least one paper of conflict. We define the notion of weak strategyproofness mainly for our theoretical purposes of negative results, since WSP is too weak to be practical. However, even this extremely weak requirement is impossible to satisfy.

We summarize our results in Table 2. We show the property of group unanimity and strategyproofness for Divide-andRank; as the first direction of possible extension, we show in Theorem 2 that the slightly stronger notion of pairwise unanimity is impossible to satisfy under mild assumptions, even without strategyproof constraints. Then we explore the second direction of extension, by requiring a connected G, and give conjectures that group unanimity and weak strategyproofness is impossible under this setting.

5.1 Impossibility of Pairwise Unanimity

In order to precisely state our result, we first introduce the notion of a review-relation graph H. Given a paper-review assignment tPiumi"1 , the review-relation graph H is an undirected graph with rns as its vertices and where any two papers pj1 and pj2 are connected iff there exists at least one reviewer who reviews both the papers. With this preliminary in place, we are now ready to state our results:

Theorem 2. If H has a cycle of length 3 or more and there is no single reviewer reviews all the papers in the cycle, then there is no review process pG↪ fq that is pairwise unanimous.

The proof of Theorem 2 is similar to a Condorcet cycle proof. In the corollary below we give some direct implications of the condition in Theorem 2 when |P1| " ¨ ¨ ¨ " |Pm| " θ, that is, when every reviewer ranks a same number of papers.

Corollary 1. Suppose |P1| " ¨ ¨ ¨ " |Pm| " θ · 2. If pG↪ fq is pairwise unanimous, the following conditions hold:

• (i) H does not contain any cycles of length θ ` 1 or more.
• (ii) The set of papers reviewed by any pair of reviewers ri1 and ri2 must satisfy the condition |Pi1 XPi2 | P t0↪ 1↪ θu. In words, if a pair of reviewers review more than one common papers, they must review exactly the same set.
• (iii) The number of distinct sets in Pi↪ ▷ ▷ ▷ ↪Pm is at most n´1 θ´1 .

Remark. In modern conferences [Shah et al., 2017], each reviewer usually reviews 3 to 6 papers. If the review process is pairwise unanimous, by Corollary 1(iii) the number of distinct review sets is much smaller than the number of reviewers; this severely limits the design of review sets, since many reviewers would be necessitated to review identical sets of papers. (ii) is also a relatively strong requirement, since the specialization of reviewers might not allow for such limit of the intersection of review sets. For instance, there is a large number of pairs of reviewers who review more than one common paper but none with the same set of papers [Shah et al., 2017]. In summary, Theorem 2 and Corollary 1 show the difficulty to satisfy pairwise unanimity, even without strategyproofness.

5.2 Group Unanimity and Strategyproofness for a Connected Review Graph

Having shown that pairwise unanimity is too strong a requirement to satisfy, we now consider another direction for extension - conditions on the review graph G. A natural question follows: Under what condition on the review graph G are both group unanimity and strategyproofness possible? Although we will leave the question of finding the exact condition open, we conjecture that if we require G to be connected, then group unanimity and strategyproofness cannot be simultaneously satisfied. To show our insights, we analyze an extremely simplified review setting and present a negative result under this setting.

Proposition 2. Consider any n · 4 and suppose P " P1 Y P2 YP3 YP4, where P1↪ P2↪ P3↪ P4 are disjoint nonempty sets of papers. Consider a review graph G with m " 3 reviewers, where reviewer r1 reviews tP1↪ P2u, r2 reviews tP2↪ P3u, and r3 reviews tP3↪ P4u. Then there is no aggregation function f that is both weakly strategyproof and group unanimous.

Proposition 2 thus shows for simple review graph considered in the statement, group unanimity and weak strategyproofness cannot hold at the same time. We conjecture that such a negative result may hold for more general connected review graphs, which could be shown by identifying a component of the general review graph satisfying the condition of Proposition 2. This shows that our design process of the review graph in Section 4 is quite essential.

6 Discussion

We provide a framework and associated algorithms to impart strategyproofness to conference peer review. Our framework, besides guaranteeing strategyproofness, is importantly very flexible in allowing the program chairs to use the decisionmaking criteria of their choice. We complement these positive results with negative results showing that it is impossible for any algorithm to remain strategyproof and satisfy the stronger notion of pairwise unanimity. Future work includes considering efficiency from a statistical perspective and characterizing the precise set of conflict-of-interest graphs that permit (or not) strategyproofness.

Acknowledgements

YX was partially supported by DARPA award FA8750-172-0130. HZ would like to acknowledge the support from DARPA XAI project, contract FA87501720152. NBS was partially supported by NSF 1755656 and 1763734.