On Strategyproof Conference Peer Review
Yichong Xu1˚ , Han Zhao1˚ , Xiaofei Shi2 and Nihar B. Shah1
1
Machine Learning Department, Carnegie Mellon University, Pittsburgh, PA, USA
2
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA, USA{yichongx, han.zhao, nihars}@cs.cmu.edu, xiaofeis@andrew.cmu.edu
Abstract

We consider peer review under a conference setting
where there are conflicts between the reviewers andthe submissions. Under such conflicts, reviewers
can manipulate their reviews in a strategic manner
to influence the final rankings of their own papers.
Present-day peer-review systems are not designed
to guard against such strategic behavior, beyond
minimal (and insufficient) checks such as not assigning a paper to a conflicted reviewer. In thiswork, we address this problem through the lens ofsocial choice, and present a theoretical frameworkfor strategyproof and efficient peer review. Given
the conflict graph which satisfies a simple property,
we first present and analyze a flexible framework
for reviewer-assignment and aggregation for the reviews that guarantees not only strategyproofness but
also a natural efficiency property (unanimity). Our
framework is based on the so-called partitioning
method, and can be treated as a generalization ofthis type of method to conference peer review settings. We then empirically show that the requisite
property on the (authorship) conflict graph is indeed satisfied in the ICLR-17 submissions data, andfurther demonstrate a simple trick to make the partitioning method more practically appealing underconference peer-review settings. Finally, we complement our positive results with negative theoreticalresults where we prove that under slightly stronger
requirements, it is impossible for any algorithm tobe both strategyproof and efficient.

1

Introduction

Peer review serves as an effective solution for quality evaluation in reviewing processes, especially in academic paper
review [Dörfler et al., 2017, Shah et al., 2017] and massive
open online courses (MOOCs) [Dı́ez Peláez et al., 2013, Piech
et al., 2013, Shah et al., 2013]. However, despite its scalability, competitive peer review faces the serious challenge ofbeing 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˚Equal contribution.

chance that their own submissions get accepted. As noted byThurner et al. [2011], even a small number of selfish, strategic reviewers can drastically reduce the quality of scientificstandard. 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 inplace except some basic checks like not assigning a paper toa conflicted reviewer. It is easy to show that these checks are
insufficient, that is, reviewers can manipulate the final rankingof their conflicted papers by strategically manipulating theirreports in current peer-review systems.
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 setof reviewers. We are given a graph which we term as “conflictgraph”. 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 inthe peer review procedure: (i) assigning each paper to a subsetof 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 etal., 2005, Douceur, 2009, Tsukida and Gupta, 2011, Shah etal., 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 canbe 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 inpractice would be a guideline for program chairs to make theirdecisions (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 canchange 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 choicetheory: 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 theoreticallyguarantees strategyproofness along with a notion of efficiency
that we term as “group unanimity”. With only a mild andrealistic assumption on the conflict graph, we establish ourpositive 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 analysisof 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 andpresent it on the ICLR-17 data.
We also complement our positive results with negative results showing that one cannot expect to meet requirementsthat 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, andis 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 highlightthe intrinsic hardness in designing strategyproof conference
review systems.

2

Related WorkAs early as in the 1970s, Gibbard and Satterthwaite had already been aware of the importance of a healthy voting rulethat guarantees strategyproofness under the setting of social
choice [Gibbard, 1973, Satterthwaite, 1975]. Recently, the factthat prominent peer review mechanisms are manipulable, has
further called for strategyproof peer review mechanisms [Merrifield and Saari, 2009, Hazelrigg, 2013]. Our work is mostclosely 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 frommisreporting their preferences over other agents. In all theseworks, each agent is essentially required to evaluate all theother 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) mechanismand 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 theirwork, 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, oursetting of conference peer review is more challenging: We
allow each reviewer to have conflicts with multiple papers andeach paper to have conflicts with multiple reviewers. Formally,
the conflict graph C under conference peer review is a moregeneral 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 , . . . , rm u to be the set of m reviewers
and P :“ tp1 , . . . , pn u 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 ofinterests 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 canbe viewed as a realistic generalization of the authorship graphin 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 graphG, termed as review graph, that also has the reviewers andsubmissions pR, Pq as its vertices. This review graph has anedge 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 forsome 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 haveat least neighbors (in R) in the graph G. For any (directedor undirected) graph H, we let the notation EH denote the setof 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 ⇡j pP 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 pPi q P ⇧pPi q of the papers in Pi . We definea (partial) ranking profile ⇡ :“ p⇡ p1q pP1 q, . . . , ⇡ pmq pPm qq as
the collection of rankings from all the reviewers. When theassignment P1 , . . . , Pm of papers to reviewers is fixed, we use
the shorthand p⇡ p1q , . . . , ⇡ pmq q for profile ⇡. For any subsetof papers P 1 Ñ P, we let ⇡ P 1 denote the restriction of ⇡ toonly the induced rankings on P 1 . Finally, when the ranking
under consideration is clear from context, we use the notationp ° 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±m G, and (b) an associated review aggregation rulef :i“1 ⇧pPi q Ñ ⇧pPq which maps from the ranking
profile to an aggregate total ranking of all papers. For any
aggregation function f , we let fj p⇡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 totake 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 tospace 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 areviewer cannot change the position of her conflicting papers,
by manipulating the ranking she provides.
Definition 1 (Strategyproofness, SP). A review process pG, f q
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 , pj q 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 “1p⇡ p1q , . . . , ⇡ pi´1q , ⇡ piq , ⇡ pi`1q , . . . , ⇡ pmq q, the results remainunchanged as fj p⇡q “ fj p⇡ 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 notionof “unanimity”, which is one of the most prevalent and classic
properties to measure the efficiency of a voting system in theliterature of social choice [Fishburn, 2015]. At a colloquiallevel, 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, f q is said
to be group unanimous (GU) if the following condition holds
for every possible profile ⇡: For every set of papers P 1 Ä Psuch that every reviewer ranks the papers she reviewed fromP 1 higher than those she reviewed from PzP 1 , the output f p⇡qmust satisfy px ° py for every pair of papers px P P 1 andpy P PzP 1 such that at least one reviewer has reviewed bothpx 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 thesecond set, then the final output ranking should respect thisagreement. 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 statedin Arrow’s impossibility theorem [Arrow, 1950]. Notice thatthe 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 asubset of papers.
Definition 3 (Pairwise Unanimity, PU). We define pG, f q to be
pairwise unanimous (PU) if the following condition holds forevery possible profile ⇡ and every pair of papers pj1 , pj2 P P:
If at least one reviewer has reviewed both pj1 and pj2 andall 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, f q is pairwise unanimous, then pG, f q
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 aspecific 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 inthe conflict graph C. We then empirically demonstrate, using
submission data from the ICLR-17 conference, that this classof 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 moregenerally 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) andthe rank aggregation algorithm (Algorithm 2). At a higher
level, our framework performs a partition of the reviewers andpapers 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 longas the conflict graph can be divided into two reasonably-sized
disconnected components.
Importantly, the framework is simple yet flexible in that theassignment within each partition and the aggregation amongcertain 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

Algorithm 2 Divide-and-Rank aggregation

Input: conflict graph C, parameters , µ, assignment algorithm A
Output: an assignment of reviewers to papers
1: pRC , PC q, pRCs , PCs q – PartitionpC, , µq
2: use algorithm A to assign papers PCs to reviewers RC
3: use algorithm A to assign papers PC to reviewers RCs
4: return the union of assignments from step 2 and 3

Input: profile ⇡ “ p⇡ p1q pP1 q, . . . , ⇡ pmq pPm qq, groups
pRC , PC q, pRCs , PCs q with |PC | • |PCs |, aggregation algorithm B
Output: total ranking of all papers
1: compute ⇡ C as the restriction of profile ⇡ to only papers
in PC , and ⇡ C̄ as the restriction of profile ⇡ to only papers
in PCs2: ⇡C – Contract-and-SortpB, ⇡ C q
3: ⇡Cs – Contract-and-SortpB,q´Y] Y] ⇡ C̄ ¯n2n
4: define I “|PC | , |PC | , ..., n
5: return total ranking obtained by filling papers in PC into
positions in I in order given by ⇡C , and papers in PCs into
positions in rnszI in order given by ⇡Cs

5:
6: procedure PARTITION(conflict graph C, parameters , µ)7:
run a BFS on C to get connected K components

tpRk , Pk quK
k“18:
let rk “ |Rk |, pk “ |Pk |, @k P rKs
9:initialize a table T r¨, ¨, ¨s P t0, 1uKˆpm`1qˆpn`1q sothat T r1, r1 , p1 s “ T r1, 0, 0s “ 1, otherwise 0
10:
for k “ 2 to K do
11:
T rk, r, ps “ T rk ´ 1, r, ps _ T rk ´ 1, r ´ rk , p ´
pk s, @0 § r § m, 0 § p § n
12:
end for13:
for 0 § r § m, 0 § p § n, if there is no T rK, r, ps “pµ
1 such that maxt m´r, n´pr u § , return ERROR
14:
use the standard backtracking in the table T r¨, ¨, ¨s toreturn pRC , PC q and pRCs , PCs q
15: end procedurethat meet the requirements specified by µ and . Althoughdividing into more groups can lead to similar unanimity andstrategyproof properties, we use two groups for simplicity andcomputational efficiency. The subroutine Partition first runs abreadth-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 Kconnected components. Here T rk, r, ps “ 1 means that there
exists a partition of the first k components such that one sideof 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 runsin 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 forthe algorithm A include the popular Toronto paper matchingsystem [Charlin and Zemel, 2013] and others [Hartvigsen etal., 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 atopological ordering of all strongly connected components(SCCs) according to the reviews, and then ranking the pa-

6:
7: procedure C ONTRACT- AND -S ORT(aggregation algo1r “ p⇡ p1q , . . . , ⇡ pm q q)
rithm B, profile ⇡r as its
8:
build a directed graph G⇡r with the papers in ⇡vertices and no edges
9:for each i P rm1 s do
10:
Suppose ⇡ piq “ ppj1 ° . . . ° pjti ), add a directededge from pjk to pjk`1 in G⇡r , @k P rti ´ 1s
11:
end for
12:
compute a topological ordering of the strongly connected components (SCCs) in G⇡r
13:
for every SCC in G⇡r , compute a permutation of thepapers in the component using algorithm B
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 algorithm B
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-Ranksatisfies group unanimity and is strategyproof.
Theorem 1. Suppose C can be partitioned into two groups
pRC , PC q and pRCs , PCs q such that there are no edges in C(
|PC | |PC
across the groups and that max |R, Ñ| § µ . Then
Ñ| |RC |CDivide-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 with1
In the case where there are multiple topological orderings, any
one of them suffices.

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 theranking of her own paper via strategic behavior, and that it isefficient from a social choice perspective.
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 ofContract-and-Sort, we add an edge between every pair of
papers pj1 Ñ pj2 if sij1 ° sij2 . This makes sure that thegraph fully reflects the opinion of the reviewer and do not
impose constraints on papers that are equally rated. On theother hand, the aggregation algorithm B can also leverage thereview scores for a more granularized ranking (e.g., averagescores). Our definition of unanimity and strategyproof canalso be straightforwardly extended to the score setting, and ourframework 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 andpapers so that there is no conflict across the partition. In thissubsection we restrict attention to the authorship conflict graph,
where we empirically verify that the partitioning conditionsindeed hold in a conference peer review setting using datafrom the ICLR-17 conference. We then demonstrate how tomake 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 thelargest component in the conflict graph, thus providing great
flexibility towards partitioning the papers and authors.
We analyzed all papers submitted to ICLR-17 with thegiven authorship relationship as the conflict graph. ICLR-17
received 489 submissions by 1,417 authors; we believe it is agood 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 tothe 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 showsthat 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, andthe 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 expertiseand hence their abilities to review any paper varies by the area

#Components
1st #Authors
1st #Papers#Authors removed from reviewer pool
0
5
10
15
20
50

100

253
371
133

389
28
8

268
313
114

278
304
110

292
228
82

302
205
74

334
55
18

Table 1: Statistics of the conflict graph on removing a small number(† 7%) of authors from the reviewer pool of 1,417 authors.

of the paper. In order to accommodate this diversity in areaof 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 expectthat a large number of reviewers with expertise required toreview these 133 papers would also be in the same CC, thusa naı̈ve application of Divide-and-Rank would assign these133 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 (withall papers but only the remaining reviewers) in terms of thenumbers 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 madepractically applicable.

5

Negative Results

The positive results in the previous section focus on group
unanimity, which is weaker than the conventional notion ofunanimity, also known as pairwise unanimity. Moreover, theframework induces a disconnected review graph whereas thereview graphs of conferences today are typically connected[Shah et al., 2017]. It is thus natural to ask the following: Cana peer review system with a connected reviewer graph satisfy
these properties? Can a strategyproof peer review system bepairwise 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, f q is called weakly strategyproof, if for every reviewer ri , there exists some paper pj P P suchthat for every pair of distinct profiles (under assignmentG) ⇡ “ p⇡ p1q , . . . , ⇡ pi´1q , ⇡ piq , ⇡ pi`1q , . . . , ⇡ pmq q and ⇡ 1 “1p⇡ p1q , . . . , ⇡ pi´1q , ⇡ piq , ⇡ pi`1q , . . . , ⇡ pmq q, it is guaranteed
1that fj p⇡q “ fj p⇡ q.

Unanimity
Pairwise
Group
Group

Strategyproof
None
Weak
Yes

Requirement on G
Mild (see Corollary 1)
Mild (Connected G)
None

Possible?
No
Conjecture: No
Yes

Reference
Theorem 2
Proposition 2
Theorem 1

Table 2: Summary of our negative results (first two rows of the table), and a comparison to our positive result (third row).

In other words, weak strategyproofness requires for eachreviewer there is at least one paper (not necessarily authoredby this reviewer) whose ranking cannot be influenced by thereviewer. 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 purposesof 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 propertyof 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 thenotion of a review-relation graph H. Given a paper-review
assignment tPi um
i“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, thenthere is no review process pG, f q that is pairwise unanimous.
The proof of Theorem 2 is similar to a Condorcet cycle
proof. In the corollary below we give some direct implicationsof 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, f q
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 X Pi2 | 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], eachreviewer usually reviews 3 to 6 papers. If the review process ispairwise unanimous, by Corollary 1(iii) the number of distinct
review sets is much smaller than the number of reviewers; thisseverely 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 specializationof reviewers might not allow for such limit of the intersectionof review sets. For instance, there is a large number of pairsof reviewers who review more than one common paper but
none with the same set of papers [Shah et al., 2017]. Insummary, Theorem 2 and Corollary 1 show the difficulty tosatisfy pairwise unanimity, even without strategyproofness.

5.2

Group Unanimity and Strategyproofness for aConnected 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 bothgroup 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 thissetting.
Proposition 2. Consider any n • 4 and suppose P “ P1 YP2 YP3 YP4 , where P1 , P2 , P3 , P4 are disjoint nonempty setsof papers. Consider a review graph G with m “ 3 reviewers,
where reviewer r1 reviews tP1 , P2 u, r2 reviews tP2 , P3 u, andr3 reviews tP3 , P4 u. Then there is no aggregation function fthat 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 anegative 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 graphin 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 forany 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 (ornot) strategyproofness.

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

References[Alon et al., 2011] Noga Alon, Felix Fischer, Ariel Procaccia, and Moshe Tennenholtz. Sum of us: Strategyproof
selection from the selectors. In TARK. ACM, 2011.
[Anderson et al., 2007] Melissa S Anderson, Emily A Ronning, Raymond De Vries, and Brian C Martinson. The
perverse effects of competition on scientists’ work andrelationships. Science and engineering ethics, 2007.
[Arrow, 1950] Kenneth J Arrow. A difficulty in the conceptof social welfare. Journal of political economy, 1950.
[Aziz et al., 2016] Haris Aziz, Omer Lev, Nicholas Mattei,
Jeffrey S Rosenschein, and Toby Walsh. Strategyproof
peer selection: Mechanisms, analyses, and experiments. In
AAAI, pages 397–403, 2016.
[Barnett, 2003] William Barnett. The modern theory of consumer behavior: Ordinal or cardinal? The Quarterly Journal of Austrian Economics, 6(1):41–65, 2003.
[Brandt et al., 2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, Ariel D Procaccia, and Jérôme Lang. Handbook ofcomputational social choice. 2016.
[Caragiannis et al., 2017] Ioannis Caragiannis, Xenophon
Chatzigeorgiou, George A Krimpas, and Alexandros A
Voudouris. Optimizing positional scoring rules for rankaggregation. In AAAI, pages 430–436, 2017.
[Charlin and Zemel, 2013] L. Charlin and R. S. Zemel. The
Toronto Paper Matching System: An automated paperreviewer assignment system, 2013.
[Dı́ez Peláez et al., 2013] Jorge Dı́ez Peláez, Óscar Luaces Rodrı́guez, Amparo Alonso Betanzos, Alicia Troncoso, and Antonio Bahamonde Rionda. Peer assessment inmoocs using preference learning via matrix factorization.
In NIPS Workshop on Data Driven Education, 2013.
[Dörfler et al., 2017] Florian Dörfler, Yuanzhang Xiao, andMihaela van der Schaar. Incentive design in peer review:
Rating and repeated endogenous matching. IEEE Transactions on Network Science and Engineering, 2017.
[Douceur, 2009] John R Douceur. Paper rating vs. paper ranking. ACM SIGOPS Operating Systems Review, 2009.
[Emerson, 2013] Peter Emerson. The original Borda countand partial voting. Social Choice and Welfare, 2013.
[Fischer and Klimm, 2015] Felix Fischer and Max Klimm.
Optimal impartial selection. SIAM Journal on Computing,44(5):1263–1285, 2015.
[Fishburn, 2015] Peter C Fishburn. The theory of social
choice. Princeton University Press, 2015.
[Garg et al., 2010] N. Garg, T. Kavitha, A. Kumar,
K. Mehlhorn, and J. Mestre. Assigning papers to referees.
Algorithmica, 58(1):119–136, Sep 2010.
[Gibbard, 1973] Allan Gibbard. Manipulation of voting
schemes: a general result. Econometrica: journal of the
Econometric Society, pages 587–601, 1973.
[Hajek et al., 2014] Bruce Hajek, Sewoong Oh, and Jiaming
Xu. Minimax-optimal inference from partial rankings. In
Advances in Neural Information Processing Systems, pages
1475–1483, 2014.

[Hartvigsen et al., 1999] David Hartvigsen, Jerry C. Wei, andRichard Czuchlewski. The conference paper-reviewer assignment problem. Decision Sciences, 1999.
[Hazelrigg, 2013] GA Hazelrigg. Dear colleague letter: Information to principal investigators (PIs) planning to submit
proposals to the Sensors and Sensing Systems (SSS) program October 1, 2013, deadline. 2013.
[Holzman and Moulin, 2013] Ron Holzman and HervéMoulin. Impartial nominations for a prize. Econometrica,
81(1):173–196, 2013.
[Kahng et al., 2018] Anson Kahng, Yasmine Kotturi, Chinmay Kulkarni, David Kurokawa, and Ariel D Procaccia.
Ranking wily people who rank each other. In AAAI, 2018.
[Kurokawa et al., 2015] David Kurokawa, Omer Lev, Jamie
Morgenstern, and Ariel D Procaccia. Impartial peer review.
In IJCAI, pages 582–588, 2015.
[Merrifield and Saari, 2009] Michael R Merrifield and Donald G Saari. Telescope time without tears: a distributed
approach to peer review. Astronomy & Geophysics, 2009.
[Piech et al., 2013] Chris Piech, Jonathan Huang, Zhenghao
Chen, Chuong Do, Andrew Ng, and Daphne Koller. Tuned
models of peer assessment in moocs. arXiv preprint
arXiv:1307.2579, 2013.
[Satterthwaite, 1975] Mark Allen Satterthwaite. Strategyproofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare
functions. Journal of economic theory, 1975.
[Shah et al., 2013] Nihar B Shah, Joseph K Bradley, Abhay
Parekh, Martin Wainwright, and Kannan Ramchandran. A
case for ordinal peer-evaluation in moocs. In NIPS Workshop on Data Driven Education, 2013.
[Shah et al., 2016] Nihar B Shah, Sivaraman Balakrishnan,
Joseph Bradley, Abhay Parekh, Kannan Ramchandran, andMartin J Wainwright. Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence.
The Journal of Machine Learning Research, 2016.
[Shah et al., 2017] Nihar B Shah, Behzad Tabibian, Krikamol
Muandet, Isabelle Guyon, and Ulrike von Luxburg. Design
and Analysis of the NIPS 2016 Review Process. arXiv
preprint arXiv:1708.09794, 2017.
[Stelmakh et al., 2018] Ivan Stelmakh, Nihar B Shah, andAarti Singh. PeerReview4All: Fair and accurate reviewer
assignment in peer review. 2018.
[Stewart et al., 2005] Neil Stewart, Gordon DA Brown, andNick Chater. Absolute identification by relative judgment.
Psychological review, 112(4):881, 2005.
[Thurner and Hanel, 2011] Stefan Thurner and Rudolf Hanel.
Peer-review in a world with rational scientists: Toward
selection of the average. The European Physical Journal B,
84(4):707–711, 2011.
[Tsukida and Gupta, 2011] Kristi Tsukida and Maya R Gupta.
How to analyze paired comparison data. Technical report,
DTIC Document, 2011.
[Xu et al., 2018] Yichong Xu, Han Zhao, Xiaofei Shi, andNihar B Shah. On Strategyproof Conference Peer Review.
arXiv preprint arXiv:1806.06266, 2018.