PeerReview4All: Fair and Accurate Reviewer Assignment in Peer Review

Introduction

Peer review is the backbone of academia. In order to provide high-quality peer reviews, it is of utmost importance to assign papers to the right reviewers (Thurner and Hanel, 2011; Black et al., 1998; Bianchi and Squazzoni, 2015). Even a small fraction of incorrect reviews can have significant adverse effects on the quality of the published scientific standard (Thurner and Hanel, 2011) and dominate the benefits yielded by the peer-review process that may have high standards otherwise (Squazzoni and Gandelli, 2012). Indeed, researchers unhappy with the peer review process are somewhat more likely to link their objections to the quality or choice of reviewers (Travis and Collins, 1991).

We focus on peer-review in conferences where a number of papers are submitted at once. These papers must simultaneously be assigned to multiple reviewers who have load constraints. The importance of the reviewer-assignment stage of the peer-review process cannot be overestimated; quoting Rodriguez et al., 2007:

“one of the first and potentially most important stage is the one that attempts to distribute submitted manuscripts to competent referees.”

Given the massive scale of many conferences such as NeurIPS and ICML, these reviewer assignments are largely performed in an automated manner. For instance, NeurIPS 2016 assigned 5 out of 6 reviewers per paper using an automated process (Shah et al., 2017). This problem of automated reviewer assignments forms the focus of this paper.

Various past studies show that small changes in peer review quality can have far reaching consequences (Thorngate and Chowdhury, 2014; Squazzoni and Gandelli, 2012) not just for the papers under consideration but more generally also for the career trajectories of the researchers. These long term effects arise due to the widespread prevalence of the Matthew effect (“rich get richer”) in academia (Merton, 1968).

It is also known (Travis and Collins, 1991; Lamont, 2009) that works that are novel or not mainstream, particularly those interdisciplinary in nature, face significantly higher difficulty in gaining acceptance. A primary reason for this undesirable state of affairs is the absence of sufficiently many good “peers” to aptly review interdisciplinary research (Porter and Rossini, 1985).

These issues strongly motivate the dual goals of the reviewer assignment procedure we consider in this paper — fairness and accuracy. By fairness, we specifically consider the notion of max-min fairness which is studied in various branches of science and engineering (Rawls, 1971; Lenstra et al., 1990; Hahne, 1991; Lavi et al., 2003; Bonald et al., 2006; Asadpour and Saberi, 2010). In our context of reviewer assignments, max-min fairness posits maximizing the review-quality of the paper with the least qualified reviewers. The max-min fair assignment guarantees that no paper is discriminated against in favor of more lucky counterparts. That is, even the most ambivalent paper with a small number of reviewers being competent enough to evaluate its merits will receive as good treatment as possible. The max-min fair assignment also ensures that in any other assignment there exists at least one paper with the fate at least as bad as the fate of the most disadvantaged paper in the aforementioned fair assignment.

Alongside, we also consider the requirement of statistical accuracy. One of the main goals of the conference peer-review process is to select the set of “top” papers for acceptance. Two key challenges towards this goal are to handle the noise in the reviews and subjective opinions of the reviewers; we accommodate these aspects in terms of existing (Ge et al., 2013; McGlohon et al., 2010; Dai et al., 2012) and novel statistical models of reviewer behavior. Prior works on the reviewer assignment problem (Long et al., 2013; Garg et al., 2010; Karimzadehgan et al., 2008; Tang et al., 2010) offer a variety of algorithms that optimize the assignment for certain deterministic objectives, but do not study their assignments from the lens of statistical accuracy. In contrast, our goal is to design an assignment algorithm that can simultaneously achieve both the desired objectives of fairness and statistical accuracy.

We make several contributions towards this problem. We first present a novel algorithm, which we call PeerReview4All, for assigning reviewers to papers. Our algorithm is based on a construction of multiple candidate assignments, each of which is obtained via an incremental execution of max-flow algorithm on a carefully designed flow network. These assignments cater to different structural properties of the similarities and a judicious choice between them provides the algorithm appealing properties.

Our second contribution is an analysis of the fairness objective that our PeerReview4All algorithm can achieve. We show that our algorithm is optimal, up to a constant factor, in terms of the max-min fairness objective. Furthermore, our algorithm can adapt to the underlying structure of the given similarity data between reviewers and papers and in various cases yield better guarantees including the exact optimal solution in certain scenarios. Finally, after optimizing the outcome for the most worst-off paper and fixing the assignment for that paper, our algorithm aims at finding the most fair assignment for the next worst-off paper and proceeds in this manner until the assignment for each paper is fixed.

As a third contribution, we show that our PeerReview4All algorithm results in strong statistical guarantees in terms of correctly identifying the top papers that should be accepted. We consider a popular statistical model (Ge et al., 2013; McGlohon et al., 2010; Dai et al., 2012) which assumes existence of some true objective score for every paper. We provide a sharp analysis of the minimax risk in terms of “incorrect” accept/reject decisions, and show that our PeerReview4All algorithm leads to a near-optimal solution.

Fourth, noting that paper evaluations are typically subjective (Kerr et al., 1977; Mahoney, 1977; Ernst and Resch, 1994; Bakanic et al., 1987; Lamont, 2009), we propose a novel statistical model capturing subjective opinions of reviewers, which may be of independent interest. We provide a sharp minimax analysis under this subjective setting and prove that our assignment algorithm PeerReview4All is also near-optimal for this subjective-score setting.

Our fifth and final contribution comprises empirical evaluations. We designed and conducted an experiment on the Amazon Mechanical Turk crowdsourcing platform to objectively compare the performance of different reviewer-assignment algorithms. The design of the experiment is done carefully to circumvent the challenge posed by the absence of a ground truth in peer review settings, so that we can evaluate accuracy objectively. In addition to the MTurk experiment, we provide an extensive evaluation of our algorithm on synthetic data, provide an evaluation on a reconstructed similarity matrix from the ICLR 2018 conference, and report the results of the experiment on real conference data conducted by Kobren et al., 2019. The results of these experiments highlight the promise of PeerReview4All in practice, in addition to the theoretical benefits discussed elsewhere in the paper. The dataset pertaining to the MTurk experiment, as well as the code for our PeerReview4All algorithm, are available on the first author’s website.

The remainder of this paper is organized as follows. We discuss related literature in Section 2. In Section 3, we present the problem setting formally with a focus on the objective of fairness. In Section 4 we present our PeerReview4All algorithm. We establish deterministic approximation guarantees on the fairness of our PeerReview4All algorithm in Section 5. We analyze the accuracy of our PeerReview4All algorithm under an objective-score model in Section 6, and introduce and analyze a subjective score model in Section 7. We empirically evaluate the algorithm in Section 8 using synthetic and real-world experiments. We then provide the proofs of all the results in Section 9. We conclude the paper with a discussion in Section 10.

Related literature

The reviewer assignment process consists of two steps. First, a “similarity” between every (paper, reviewer) pair that captures the competence of the reviewer for that paper is computed. These similarities are computed based on various factors such as the text of the submitted paper, previous papers authored by reviewers, reviewers’ bids and other features. Second, given the notion of good assignment, specified by the program chairs, papers are allocated to reviewers, subject to constraints on paper/reviewer loads. This work focuses on the second step (assignment), assuming the first step of computing similarities as a black box. In this section, we give a brief overview of the past literature on both of the steps of the reviewer-assignment process.

Computing similarities. The problem of identifying similarities between papers and reviewers is well-studied in data mining community. For example, Mimno and McCallum, 2007 introduce a novel topic model to predict reviewers’ expertise. Liu et al., 2014 use the random walk with restarts model to incorporate both expertise of reviewers and their authority in the final similarities. Co-authorship graphs (Rodriguez and Bollen, 2008) and more general bibliographic graph-based data models (Tran et al., 2017) give appealing methods which do not require a set of reviewers to be pre-determined by conference chair. Instead, these methods recommend reviewers to be recruited, which might be particularly useful for journal editors.

One of the most widely used automated assignment algorithms today is the Toronto Paper Matching System or TPMS (Charlin and Zemel, 2013) which also computes estimations of similarities between submitted papers and available reviewers using techniques in natural language processing. These scores might be enhanced with reviewers’ self-accessed expertise adaptively queried from them in an automatic manner.

Our work uses these similarities as an input for our assignment algorithm, and considers the computation of these similarity values as a given black box.

Cumulative goal functions. With the given similarities, much of past work on reviewer assignments develop algorithms to maximize the cumulative similarity, that is, the sum of the similarities across all assigned reviewers and all papers. Such an objective is pursued by the organizers of SIGKDD conference (Flach et al., 2010) and by the widely employed TPMS assignment algorithm (Charlin and Zemel, 2013). Various other popular conference management systems such as EasyChair (easychair.org) and HotCRP (hotcrp.com) and several other papers (see Long et al., 2013; Charlin et al., 2012; Goldsmith and Sloan, 2007; Tang et al., 2010 and references therein) also aim to maximize various cumulative functionals in their automated reviewer assignment procedures. In the sequel, we argue however that optimizing such cumulative objectives is not fair — in order to maximize them, these algorithms may discriminate against some subset of papers. Moreover, it is the non-mainstream submissions that are most likely to be discriminated against. With this motivation, we consider a notion of fairness instead.

Fairness. In order to ensure that no papers are discriminated against, we aim at finding a fair assignment — an assignment that ensures that the most disadvantaged paper gets as competent reviewers as possible. The issue of fairness is partially tackled by Hartvigsen et al., 1999, where they necessitate every paper to have at least one reviewer with expertise higher than certain threshold, and then maximize the value of that threshold. However, this improvement only partially solves the issue of discrimination of some papers: having assigned one strong reviewer to each paper, the algorithm may still discriminate against some papers while assigning remaining reviewers. Given that nowadays large conferences such as NeurIPS and ICML assign 4-6 reviewers to each paper, a careful assessment of the paper by one strong reviewer might be lost in the noise induced by the remaining weak reviews. In the present study, we measure the quality of assignment with respect to any particular paper as sum similarity over reviewers assigned to that paper. Thus, the fairness of assignment is the minimum sum similarity across all papers; we call an assignment fair if it maximizes the fairness. We note that assignment computed by our PeerReview4All algorithm is guaranteed to have at least as large max-min fairness as that proposed by Hartvigsen et al., 1999.

Benferhat and Lang, 2001 discuss different approaches to selection of the “optimal” reviewer assignment. Together with considering a cumulative objective, they also note that one may define the optimal assignment as an assignment that minimizes a disutility of the most disadvantaged reviewer (paper). This approach resembles the notion of max-min fairness we study in this paper, but Benferhat and Lang, 2001 do not propose any algorithm for computing the fair assignment.

The notion of max-min fairness was formally studied in context of peer-review by Garg et al., 2010. While studying a similar objective, our work develops both conceptual and theoretical novelties which we highlight here. First, Garg et al., 2010 measure the fairness in terms of reviewers’ bids — for every reviewer they compute a value of papers assigned to that reviewer based on her/his bids and maximize the minimum value across all reviewers. While satisfying reviewers is a useful practice, we consider fairness towards the papers in their review to be of utmost importance. During a bidding process reviewers have limited time resources and/or limited access to papers’ content to evaluate their relevance, and hence reviewers’ bids alone are not a good proxy towards the measure of fairness. In contrast, in this work we consider similarities — scores that are designed to represent a competence of reviewer in assessing a paper. Besides reviewers’ bids, similarities are computed based on the full text of the submissions and papers authored by reviewer and can additionally incorporate various factors such as quality of previous reviews, experience of reviewer and other features that cannot be self-assessed by reviewers.

The assignment algorithm proposed in Garg et al., 2010 works in two steps. In the first step, the problem is set up as an integer programming problem and a linear programming relaxation is solved. The second step involves a carefully designed rounding procedure that returns a valid assignment. The algorithm is guaranteed to recover an assignment whose fairness is within a certain additive factor from the best possible assignment. However, the fairness guarantees provided in Garg et al., 2010 turn out to be vacuous for various similarity matrices. As we discuss later in the paper, this is a drawback of the algorithm itself and not an artifact of their guarantees. In contrast, we design an algorithm with multiplicative approximation factor that is guaranteed to always provide a non-trivial approximation which is at most constant factor away from the optimal.

Next, Garg et al., 2010 consider fairness of the assignment as an eventual metric of the assignment quality. However, we note that the main goal of the conference paper reviewing process is an accurate acceptance of the best papers. Thus, in the present work we both theoretically and empirically study the impact of the fairness of the assignment on the quality of the acceptance procedure.

Finally, although Garg et al., 2010 present their algorithm for the case of discrete reviewer’s bids, we note that this assumption can be relaxed to allow real-valued similarities with a continuous range as in our setting. In this paper we refer to the corresponding extension of their algorithm as the Integer Linear Programming Relaxation (ILPR) algorithm.

Fair division. A direction of research that is relevant to our work studies the problem of fair division where max-min fairness is extensively developed. The seminal work of Lenstra et al., 1990 provides a constant factor approximation to the minimum makespan scheduling problem where the goal is to assign a number of jobs to the unrelated parallel machines such that the maximal running time is minimized. Recently Asadpour and Saberi, 2010; Bansal and Sviridenko, 2006 proposed approximation algorithms for the problem of assigning a number of indivisible goods to several people such that the least happy person is as happy as possible. However, we note that techniques developed in these papers cannot be directly applied for reviewer assignments problem in peer review due to the various idiosyncratic constraints of this problem. In contrast to the classical formulation studied in these works, our problem setting requires each paper to be reviewed by a fixed number of reviewers and additionally has constraints on reviewers’ loads. Such constraints allow us to achieve an approximation guarantee that is independent of the total number of papers and reviewers, and depends only on $\lambda$, the number of reviewers required per paper, as $\frac{1}{\lambda}$. In contrast, the approximation factor of Asadpour and Saberi, 2010 gets worse at a rate of $\frac{1}{\sqrt{m}\log^{3}m}$, where $m$ is a number of persons (papers in our setting).

Statistical aspects. Different statistical aspects related to conference peer-review have been studied in the literature. McGlohon et al., 2010 and Dai et al., 2012 studied aggregation of consumers ratings to generate a ranking of restaurants or merchants. They come up with objective score model of reviewer which we also use in this work. Ge et al., 2013 also use similar model of reviewer and propose a Bayesian approach to calibrating reviewer’ scores, which allows to incorporate different biases in context of conference peer-review. Sajjadi et al., 2016 empirically compare different methods of score aggregation for peer grading of homeworks. Peer grading is a related problem to conference peer review, with the key difference that the questions and answers (“papers”) are more closed-ended and objective. They conclude that although more sophisticated methods are praised in the literature, the simple averaging algorithm demonstrates better performance in their experiment. Another interesting observation they make is an edge of cardinal grades over ordinal in their setup. In this work we also consider the conferences with cardinal grading scheme of submissions.

To the best of our knowledge, no prior works on conference peer-review has studied the entire pipeline — from assignment to acceptance — from a statistical point of view. In this work we take the first steps to close this gap and provide a strong minimax analysis of naïve yet interesting procedure of determining top $k$ papers. Our findings suggest that higher fairness of the assignment leads to better quality of acceptance procedure. We consider both the objective score model (Ge et al., 2013; McGlohon et al., 2010; Dai et al., 2012) and a novel subjective-score model that we propose in the present paper.

Coverage and Diversity. For completeness, we also discuss several related works that study reviewer assignment problem.

Li et al., 2015 present a greedy algorithm that tries to avoid assigning a group of stringent reviewers or a group of lenient reviewers to a submission, thus maintaining diversity of the assignment in terms of having different combinations of reviewers assigned to different papers.

Another way to ensure diversity of the assignment is proposed by Liu et al., 2014. Instead of designing the special assignment algorithm, they try to incentivize the diversity by special construction of similarities. Besides incorporating expertise and authority of reviewers in similarities, they add an additional term to the optimization problem which balances similarities by increasing scores for reviewers from different research areas.

Karimzadehgan et al., 2008 consider topic coverage as an objective and propose several approaches to maintain broad coverage, requiring reviewers assigned to paper being expert in different subtopics covered by the paper. They empirically verify that given a paper and a set of reviewers, their algorithms lead to better coverage of paper’s topics as compared to baseline technique that assigns reviewers based on some measure of similarity between text of submission and papers authored by reviewers, but does not do topic matching.

A similar goal is formally studied by Long et al., 2013. They measure the coverage of the assignment in terms of the total number of distinct topics of papers covered by the assigned reviewers. They propose a constant factor approximation algorithm that benefits from a sub-modular nature of the objective. As we show in Appendix C, the techniques of Long et al., 2013 can be combined with our proposed algorithm to obtain an assignment which maintains not only fairness, but also a broad topic coverage.

Research on peer review. The explosion in the number of submissions in many conferences has spurred research in computer science on improving peer review. In addition to problems of fairness and accuracy of the reviewer-paper assignment process, there are a number of challenges in peer review which are addressed in the literature to various extents. These include problems of bias (Tomkins et al., 2017; Stelmakh et al., 2019a), miscalibration (Ge et al., 2013; Roos et al., 2011; Flach et al., 2010; Wang and Shah, 2019), subjectivity (Noothigattu et al., 2018), strategic behavior (Balietti et al., 2016; Xu et al., 2019a; Xu et al., 2019b), and others (Lawrence and Cortes, 2014; Gao et al., 2019). Of particular interest is the work by Fiez et al., 2019 which optimizes the process by which reviewers can bid on which papers they prefer to review. In most automated reviewer-paper assignment systems, the bids and the text-matching similarities are then combined (Shah et al., 2017) to form the similarities used to compute the assignment. The bidding and the reviewer-paper assignments are executed separately in current systems, and given the intrinsic relations between the two, it is of interest to jointly design the two systems in the future.

Problem setting

In this section we present the problem setting formally with a focus on the objective of fairness. (We introduce the statistical models we consider in Sections 6 and 7.)

Given a collection of $m\geq 2$ papers, suppose that there exists a true, unknown total ranking of the papers. The goal of the program chair (PC) of the conference is to recover top $k$ papers, for some pre-specified value $k<m$. In order to achieve this goal, the PC recruits $n\geq 2$ reviewers and asks each of them to read and evaluate some subset of the papers. Each reviewer can review a limited number of papers. We let $\mu$ denote the maximum number of papers that any reviewer is willing to review. Each paper must be reviewed by $\lambda$ distinct reviewers. In order to ensure this setting is feasible, we assume that $n\mu\geq m\lambda$. In practice, $\lambda$ is typically small (2 to 6) and hence should conceptually be thought of as a constant.

The PC has access to a similarity matrix $S=\left\{s_{ij}\right\}\in^{n\times m}$, where $s_{ij}$ denotes the similarity between any reviewer $i\in[n]$ and any paper $j\in[m]$. Here, we adopt the standard notation $[\nu]=\left\{1,2,\ldots,\nu\right\}$ for any positive integer $\nu$. These similarities are representative of the envisaged quality of the respective reviews: a higher similarity between any reviewer and paper is assumed to indicate a higher competence of that reviewer in reviewing that paper (this assumption is formalized later). We do not discuss the design of such similarities, but often they are provided by existing systems (Charlin and Zemel, 2013; Mimno and McCallum, 2007; Liu et al., 2014; Rodriguez and Bollen, 2008; Tran et al., 2017).

Our focus is on the assignment of papers to reviewers. We represent any assignment by a matrix $A\in\{0,1\}^{n\times m}$, whose $(i,j)^{\text{th}}$ entry is $1$ if reviewer $i$ is assigned paper $j$ and $0$ otherwise. We denote the set of reviewers who review paper $j$ under an assignment $A$ as $\mathcal{R}_{A}(j)$. We call an assignment feasible if it respects the $(\mu,\lambda)$ conditions on the reviewer and paper loads. We denote the set of all feasible assignments as $\mathcal{A}$:

Our goal is to design a reviewer-assignment algorithm with a two-fold objective: (i) fairness to all papers, (ii) strong statistical guarantees in terms of recovering the top papers.

Although the goal of exact recovering of top $k$ papers is appealing, given the large number of papers submitted to a conference such as ICML and NeurIPS, this goal might be too optimistic. Another alternative is to recover top $k$ papers allowing for a certain Hamming error tolerance $t\in\{0,\ldots,k-1\}$. For any two subsets $\mathcal{M}_{1},\mathcal{M}_{2}$ of $[m]$, we define their Hamming distance to be the number of items that belong to exactly one of the two sets — that is

2 Fairness objective

An assignment objective that is popular in past papers (Charlin and Zemel, 2013; Charlin et al., 2012; Taylor, 2008) is to maximize the cumulative similarity over all papers. Formally, these works choose an assignment $A\in\mathcal{A}$ which maximizes the quantity

An assignment algorithm that optimizes this objective (2) is implemented in the widely used Toronto Paper Matching System (Charlin and Zemel, 2013). We will refer to the feasible assignment that maximizes the objective (2) as $A^{\text{TPMS}}$ and denote the algorithm which computes $A^{\text{TPMS}}$ as TPMS.

We argue that the objective (2) does not necessarily lead to a fair assignment. The optimal assignment can discriminate some papers in order to maximize the cumulative objective. To see this issue, consider the following example.

Consider a toy problem with $n=m=3$ and $\mu=\lambda=1$, with a similarity matrix shown in Table 1. In this example, paper $c$ is easy to evaluate, having non-zero similarities with all the reviewers, while papers $a$ and $b$ are more specific and weak reviewer $2$ has no expertise in reviewing them. Reviewer $1$ is an expert and is able to assess all three papers. Maximizing total sum of similarities (2), the TPMS algorithm will assign reviewers $1$, $2$, and $3$ to papers $a$, $b$, and $c$ respectively. Observe that under this assignment, paper $b$ is assigned a reviewer who has insufficient expertise to evaluate the paper. On the other hand, the alternative assignment which assigns reviewers $1$, $2$, and $3$ to papers $a$, $c$, and $b$ respectively ensures that every paper has a reviewer with similarity at least $1/5$. This “fair” assignment does not discriminate against papers $a$ and $b$ for improving the review quality of the already benefitting paper $c$.

With this motivation, we now formally describe the notion of fairness that we aim to optimize in this paper. Inspired by the notion of max-min fairness in a variety of other fields (Rawls, 1971; Lenstra et al., 1990; Hahne, 1991; Lavi et al., 2003; Bonald et al., 2006; Asadpour and Saberi, 2010), we aim to find a feasible assignment $A\in\mathcal{A}$ to maximize the following objective $\Gamma^{S}$ for given similarity matrix $S$:

The assignment optimal for (3) maximizes the minimum sum similarity across all the papers. In other words, for every other assignment there exists some paper which has the same or lower sum similarity. Returning to our example, the objective (3) is maximized when reviewers $1$, $2$, and $3$ are assigned to papers $a$, $c$, and $b$ respectively.

Our reviewer assignment algorithm presented subsequently guarantees the aforementioned fair assignment. Importantly, while aiming at optimizing (3), our algorithm does even more — having the assignment for the worst-off paper fixed, it finds an assignment that satisfies the second worst-off paper, then the next one and so on until all papers are assigned.

It is important to note that similarities $s_{ij}$ obtained by different techniques (Charlin and Zemel, 2013; Mimno and McCallum, 2007; Rodriguez and Bollen, 2008; Tran et al., 2017) all have different meanings. Therefore, the PC might be interested to consider a slightly more general formulation and aim to maximize

Unfortunately, the assignment optimal for (4) is hard to compute for any reasonable choices of function $f$. Garg et al., 2010 showed that finding a fair assignment is an NP-hard problem even if $f(s)\in\left\{1,2,3\right\}$ and $\lambda=2$.

Finally we note that for our running example (Table 1 above), the ILPR algorithm (Garg et al., 2010), despite trying to optimize fairness of the assignment, also returns an unfair assignment $A^{\text{ILPR}}$ which coincides with $A^{\text{TPMS}}$. The reason for this behavior lies in the inner-working of the ILPR algorithm: a linear programming relaxation splits reviewers $1$ and $2$ in two and makes them review both paper $a$ and paper $b$. During the rounding stage, reviewer $1$ is assigned to either paper $a$ or paper $b$, ensuring that the remaining paper will be reviewed by reviewer $2$. Given that reviewer $2$ has zero similarity with both papers $a$ and $b$, the fairness of the resulting assignment will be $0$. Such an issue arises more generally in the ILPR algorithm and is discussed in more detail subsequently in Section 5.3 and in Appendix A.1.

Reviewer assignment algorithm

In this section we first describe our PeerReview4All algorithm followed by an illustrative example.

A high level idea of the algorithm is the following. For every integer $\kappa\in[\lambda]$, we try to assign each paper to $\kappa$ reviewers with maximum possible similarities while respecting constraints on reviewer loads. We do so via a carefully designed “subroutine” that is explained below. Continuing for that value of $\kappa$, we complement this assignment with $(\lambda-\kappa)$ additional reviewers for each paper. Repeating the procedure for each value of $\kappa\in[\lambda]$, we obtain $\lambda$ candidate assignments each with $\lambda$ reviewers assigned to each paper, and then choose the one with the highest fairness. The assignment at this point ensures guarantees of worst-case fairness (4). We then also optimize for the second worst-off paper, then the third worst-off paper and so on in the following manner. In the assignment at this point, we find the most disadvantaged papers and permanently fix corresponding reviewers to these papers. Next, we repeat the procedure described above to find the most fair assignment among the remaining papers, and so on. By doing so, we ensure that our final assignment is not susceptible to bottlenecks which may be caused by irrelevant papers with small average similarities.

The higher-level idea behind the aforementioned subroutine to obtain the candidate assignment for any value of $\kappa\in[\lambda]$ is as follows. The subroutine constructs a layered flow network graph with one layer for reviewers and one layer for papers, that captures the similarities and the constraints on the paper/reviewer loads. Then the subroutine incrementally adds edges between (reviewer, paper) pairs in decreasing order of similarity and stops when the paper load constraints are met (each paper can be assigned to $\kappa$ reviewers using only edges added at this point). This iterative procedure ensures that the papers are assigned reviewers with approximately the highest possible similarities.

We formally present our main algorithm as Algorithm 1 and the subroutine as Subroutine 1. In what follows, we walk the reader through the steps in the subroutine and the algorithm in more detail.

Subroutine. A key component of our algorithm is a construction of a flow network in a sequential manner in Subroutine 1. The subroutine takes as input, among other arguments, the set $\mathcal{M}$ of papers that are not yet assigned and the required number of reviewers per paper $\kappa\leq\lambda$. The goal of the subroutine is to assign each paper in $\mathcal{M}$ with $\kappa$ reviewers, respecting the reviewer load constraints, in a way that minimum similarity across all paper-reviewer pairs in resulting assignment is maximized.

The output of the subroutine is an assignment (represented by variable $A$) which is initially set as empty (Step 1). The subroutine begins (Step 2) with a construction of a directed acyclic graph (a “flow network”) comprising 4 layers in the following order: a source, all reviewers, all papers in $\mathcal{M}$, and a sink. An edge may exist only between consecutive layers. The edges between the first two layers control the reviewers’ workloads and edges between the last two layers represent the number of reviews required by the papers. Finally, costs of the all edges in this initial construction are set to $0$. Note that in subsequent steps, the edges are added only between the second and third layers. Thus, the maximum flow in the network is at most $|\mathcal{M}|\kappa$.

The crux of the subroutine is to incrementally add edges one at a time between the layers, representing the reviewers and papers, in a carefully designed manner (Steps 3 and 4). The edges are added in order of decreasing similarities. These edges control a reviewer-paper relationship: they have a unit capacity to ensure that any reviewer can review any paper at most once and their costs are equal to the similarity between the corresponding (reviewer, paper) pair.

After adding each edge, the subroutine (Step 5) tests whether a max-flow of size $|\mathcal{M}|\kappa$ is feasible. Note that a feasible flow of size $|\mathcal{M}|\kappa$ corresponds to a feasible assignment: by construction of the flow network described earlier, we know that the reviewer and paper load constraints are satisfied. The capacity of each edge in our flow network is a non-negative integer, thereby guaranteeing that the max-flow is an integer, that it can be found in polynomial time, and that the flow in every edge is a non-negative integer under the max-flow. Once the max-flow of size $|\mathcal{M}|\kappa$ is reached, the subroutine stops adding edges. At this point, it is ensured that the value of the lowest similarity in the resulting assignment is maximized.

Finally, the subroutine assigns each paper to $\kappa$ reviewers, using only the “high similarity” edges added to the network so far (Steps 6 and 7). The existence of the corresponding assignment is guaranteed by max-flow in the network being equal to $|\mathcal{M}|\kappa$. There may be more than one feasible assignments that attain the max-flow. While any of these assignments would suffice from the standpoint of optimizing the worst-case fairness objective (4), the PC may wish to make a specific choice for additional benefits and specify the heuristic to pick the max-flow in Step 6 of the subroutine. For example, if the max-flow with the maximum cost is selected, then the resulting assignment nicely combines fairness with the high average quality of the assignment. Another choice, discussed in Appendix C, helps with broad topic coverage of the assignment. Importantly, the approximation guarantees established in Theorem 1 and Corollary 1, as well as statistical guarantees from Sections 6 and 7 hold for any max-flow assignment chosen in Steps 6 and 7.

For comparison, we note that the TPMS algorithm can equivalently be interpreted in this framework as follows. The TPMS algorithm would first connect all reviewers to all papers in layers 2 and 3 of the flow graph. It will then compute a max-flow with max cost in this fully connected flow network and make reviewer-paper assignments corresponding to the edges with unit flow between layers 2 and 3. In contrast, our sequential construction of the flow graph prevents papers from being assigned to weak reviewers and is crucial towards ensuring the fairness objective.

Algorithm. The algorithm calls the subroutine iteratively and uses the outputs of these iterates in a carefully designed manner. Initially, all papers belong to a set $\mathcal{M}$ which represents papers that are not yet assigned. The algorithm repeats Steps 2 to 7 until all papers are assigned. In every iteration, for every value of $\kappa\in[\lambda]$, the algorithm first calls the subroutine to assign $\kappa$ reviewers to each paper from $\mathcal{M}$ (Step 2b), and then adjusts reviewers’ capacities and the similarity matrix (Step 2c) to prevent any reviewer being assigned to the same paper twice. Next, the subroutine is called again (Step 2d) to assign another $(\lambda-\kappa)$ reviewers to each paper. As a result, after completion of Step 2, $\lambda$ feasible candidate assignments $A_{1},\ldots,A_{\lambda}$ are constructed. Each assignment $A_{\kappa},\kappa\in[\lambda]$, is guaranteed (through the Step 2b) to maximize the minimum similarity across pairs $(i,j)$ where $j\in\mathcal{M}$ and reviewer $i$ is among $\kappa$ strongest reviewers assigned to paper $j$ in $A_{\kappa}$; and (through the Steps 2d and 2e) to have each paper assigned with exactly $\lambda$ reviewers.

In Step 3, the algorithm chooses the assignment with the highest fairness (4) among the $\lambda$ candidate assignments and the assignment $A_{0}$ from the previous iteration (empty in the first iteration). Note that since $A_{0}$ is also included in the maximizer, the fairness cannot decrease in subsequent iterations.

In the chosen assignment, the algorithm identifies the papers that are most disadvantaged, and fixes the assignment for these papers (Step 4). The assignment for these papers will not be changed in any subsequent step. The next steps (Steps 5 and 6) update the auxiliary variables to account for this assignment that is fixed — decreasing the corresponding reviewer capacities and removing these assigned papers from the set $\mathcal{M}$. Step 7 then keeps a track of the present assignment $\widetilde{A}$ for use in subsequent iterations, ensuring that fairness cannot decrease as the algorithm proceeds.

We make a few additional remarks regarding the PeerReview4All algorithm.

1. Computational cost: A naïve implementation of the PeerReview4All algorithm has a computational complexity $\widetilde{\mathcal{O}}\left(\lambda(m+n)m^{2}n\right)$. We give more details on implementation and computational aspects in Appendix B.

2. Variable reviewer or paper loads: More generally, the PeerReview4All algorithm allows for specifying different loads for different reviewers and/or papers. For general paper loads, we consider $\kappa\leq\max_{j\in[m]}\lambda^{(j)}$ and define the capacity of edge between node corresponding to any paper $j$ and sink as $\min\{\kappa,\lambda^{(j)}\}$.

3. Incorporating conflicts of interest: One can easily incorporate any conflict of interest between any reviewer and paper by setting the corresponding similarity to $-\infty$.

4. Topic coverage: The techniques developed in Long et al., 2013 can be employed to modify our algorithm in a way that it first ensures fairness and then, among all approximately fair assignments, picks one that approximately maximizes the number of distinct topics of papers covered. We discuss this modification in Appendix C.

2 Example

To provide additional intuition behind the design of the algorithm, we now present an example that we also use in the next section to explain our approximation guarantees.

Let for a moment assume that $f(s)=s$ and let $\zeta$ be a constant close to $1$. Consider the following two scenarios:

The optimal assignment $A^{\text{HARD}}$ is such that all the papers are assigned to reviewers with high similarity:

The optimal assignment $A^{\text{HARD}}$ is such that there are some “critical” papers which have $\eta<\lambda$ assigned reviewers with similarities higher than $\zeta$ and the remaining assigned reviewers with small similarities. All other papers are assigned to $\lambda$ reviewers with similarity higher than $\zeta$.

Intuitively, the first scenario corresponds to an ideal situation since there exists an assignment such that each paper has $\lambda$ competent reviewers (with similarity $\zeta\approx 1$). In contrast, in the second scenario, even in the fair assignment, some papers lack expert reviewers. Such a scenario may occur, for example, if some non-mainstream papers were submitted to a conference. This case entails identifying and treating these disadvantaged papers as well as possible. To be able to find the fair assignment in both scenarios, the assignment algorithm should distinguish between them and adapt its behavior to the structure of similarity matrix. Let us track the inner-workings of PeerReview4All algorithm to demonstrate this behaviour.

We note that by construction, the fairness of the resulting assignment $A^{\text{PR4A}}$ is determined in the first iteration of Steps 2 to 7 of Algorithm 1, so we restrict our attention to $\mathcal{M}=[m]$. First, consider scenario (S1). The subroutine called with parameter $\kappa=\lambda$ will add edges to the flow network until the maximal flow of size $m\lambda$ is reached. Since the optimal assignment $A^{\text{HARD}}$ is such that the lowest similarity is higher than $\zeta$, the last edge added to the flow network will have similarity at least $\zeta$, implying that the fairness of the candidate assignment $A_{\lambda}$, which is a lower bound for the fairness of resulting assignment, will be at least $\lambda\zeta$. Given that $\zeta$ is close to one, we conclude that in this case algorithm is able to recover an assignment which is at least very close to optimal.

Now, let us consider scenario (S2). In this scenario, the subroutine called with $\kappa=\lambda$ may return a poor assignment. Indeed, since there is a lack of competent reviewers for critical papers, there is no way to assign each paper with $\lambda$ reviewers having a high minimum similarity in the assignment. However, the subroutine called with parameter $\kappa=\eta$ will find $\eta$ strong reviewers for each paper (including the critical papers), thereby leading to a fairness $\Gamma^{S}\left(A^{\text{PR4A}}\right)\geq\eta\zeta$. The obtained lower bound guarantees that the assignment recovered by the PeerReview4All algorithm is also close to the optimal, because in the fair assignment $A^{\text{HARD}}$ some papers have only $\eta$ strong reviewers.

This example thus illustrates how the PeerReview4All algorithm can adapt to the structure of the similarity matrix in order to guarantee fairness, as well as other guarantees that are discussed subsequently in the paper.

Approximation guarantees

In this section we provide guarantees on the fairness of the reviewer-assignment by our algorithm. We first establish guarantees on the max-min fairness objective introduced earlier (Section 5.1). We subsequently show that our algorithm optimizes not only the worst-off paper but recursively optimizes all papers (Section 5.2). We then conclude this section on deterministic approximation guarantees with a comparison to past literature (Section 5.3).

We begin with some notation that will help state our main approximation guarantees. For each value of $\kappa\in[\lambda]$, consider the reviewer-assignment problem but where each paper requires $\kappa$ (instead of $\lambda$) reviews (each reviewer still can review up to $\mu$ papers). Let us denote the family of all feasible assignments for this problem as $\mathcal{A}_{\kappa}$. Now define the quantities

Intuitively, for every assignment from the family $\mathcal{A}_{\kappa}$, the quantity $s^{\ast}_{\kappa}$ upper bounds the minimum similarity for any assigned (reviewer, paper) pair. It also means that the value $s^{\ast}_{\kappa}$ is achievable by some assignment in $\mathcal{A}_{\kappa}$. The value $s^{\ast}_{0}$ captures the value of the largest entry in the similarity matrix $S$ and gives a trivial upper bound $\Gamma^{S}_{f}\left(A\right)\leq\lambda f(s^{\ast}_{0})$ for every feasible assignment $A\in\mathcal{A}$. Likewise, the value $s^{\ast}_{\infty}$ captures the smallest entry in the similarity matrix $S$ and yields a lower bound $\Gamma^{S}_{f}\left(A\right)\geq\lambda f(s^{\ast}_{\infty})$ for every feasible assignment $A\in\mathcal{A}$.

We are now ready to present the main result on the approximation guarantees for the PeerReview4All algorithm as compared to the optimal assignment $A^{\text{HARD}}$.

Consider any feasible values of $(n,m,\lambda,\mu)$, any monotonically increasing function $f:\to[0,\infty]$, and any similarity matrix $S$. The assignment $A^{\text{PR4A}}_{f}$ given by the PeerReview4All algorithm guarantees the following lower bound on the fairness objective (4):

The numerator of (7a) is a lower bound on the fairness of the assignment returned by our algorithm. It is important to note that if $\lambda=1$, that is, if we only need to assign one reviewer for each paper, then our PeerReview4All Algorithm finds exact solution for the problem, recovering the classical results of Garfinkel, 1971 as a special case.

In practice, the number of reviewers $\lambda$ required per paper is a small constant (typically set as $3$), and in that case, our algorithm guarantees a constant factor approximation. Note that the fraction in the right hand side of (7a) can become $0/0$ or $\infty/\infty$, and in both cases it should be read as $1$.

The bound (7a) can be significantly tighter than $1/\lambda$, as we illustrate in the following example.

Consider two scenarios (S1) and (S2) from Section 4.2, and consider $f(s)=s$. One can see that under scenario (S1), we have $s^{\ast}_{\lambda}\geq\zeta$. Setting $\kappa=\lambda$ in the numerator and $\kappa=1$ in the denominator of the bound (7a), and recalling that $\zeta\approx 1$, we obtain:

where we have also used the fact that $s^{\ast}_{1}\leq 1$. Let us now consider the second scenario (S2) in the example of Section 4.2. In this scenario, since each paper can be assigned to $\eta$ strong reviewers with similarity higher than $\zeta$, we have $s^{\ast}_{\eta}=\zeta\approx 1$. We then also have $s^{\ast}_{0}\leq 1$. Moreover, there are some papers which have only $\eta$ strong reviewers in optimal assignment $A^{\text{HARD}}$, and hence we have $s^{\ast}_{\eta+1}\ll s^{\ast}_{0}$. Setting $\kappa=\eta$ in the numerator and $\kappa=\eta+1$ in the denominator of the bound (7a), some algebraic simplifications yield the bound

We now briefly provide more intuition on the bound (7a) by interpreting it in terms of specific steps in the algorithm. Setting $f(s)=s$, let us consider the first iteration of the algorithm. Recalling the definition (6) of $s^{\ast}_{\kappa}$, the PeerReview4All subroutine called with parameter $\kappa$ on Step 2b finds an assignment such that all the similarities are at least $s^{\ast}_{\kappa}$. This guarantee in turn implies that the fairness of the corresponding assignment $A_{{\kappa}}$ is at least $\kappa s^{\ast}_{\kappa}+(\lambda-\kappa)s^{\ast}_{\infty}$, thereby giving rise to the numerator of (7a). The denominator is an upper bound of the fairness of the optimal assignment $A^{\text{HARD}}$. The expression for any value of $\kappa$ is obtained by simply appealing to the definition of $s^{\ast}_{\kappa}$ which is defined in terms of the optimal assignment. By definition (6) of $s^{\ast}_{\kappa}$, for every feasible assignment $A$ exists at least one paper such that at most $\kappa-1$ of the assigned reviewers are of similarity larger than $s^{\ast}_{\kappa}$. Thus, the fairness of the optimal assignment is upper-bounded by the sum similarity of the paper that has $\kappa-1$ reviewers with similarity $s^{\ast}_{0}$ (the highest possible similarity), and $\lambda-\kappa+1$ reviewers with similarity $s^{\ast}_{\kappa}$.

Finally, one may wonder whether optimizing the objective (2) as done by prior works (Charlin and Zemel, 2013; Charlin et al., 2012) can also guarantee fairness. It turns out that this is not the case (see the example in Table 1 for intuition), and optimizing the objective (2) is not a suitable proxy towards the fairness objective (4). In Appendix A.2 we show that in general the fairness objective value of the TPMS algorithm which optimizes (2) may be arbitrarily bad as compared to that attained by our PeerReview4All algorithm.

In Appendix A.3 we show that the analysis of the approximation factor of our algorithm is tight in a sense that there exists a similarity matrix for which the bound (7b) is met with equality. That said, the approximation factor of our PeerReview4All algorithm can be much better than $\frac{1}{\lambda}$ for various other similarity matrices, as demonstrated in examples (S1) and (S2).

2 Beyond worst case

The previous section established guarantees for the PeerReview4All algorithm on the fairness of the assignment in terms of the worst-off paper. In this section we formally show that the algorithm does more: having the assignment for the worst-off paper fixed, the algorithm then satisfies the second worst-off paper, and so on.

Recall that Algorithm 1 iteratively repeats Steps 2 to 7. In fact, the first time that Step 3 is executed, the resulting intermediate assignment $\widetilde{A}$ achieves the max-min guarantees of Theorem 1. However, the algorithm does not terminate at this point. Instead, it finds the most disadvantaged papers in the selected assignment and fixes them in the final output $A^{\text{PR4A}}_{f}$ (Step 4), attributing these papers to reviewers according to $\widetilde{A}$. Then it repeats the entire procedure (Steps 2 to 7) again to identify and fix the assignment for the most disadvantaged papers among the remaining papers and so on until the all papers are assigned in $A^{\text{PR4A}}_{f}$. We denote the total number of iterations of Steps 2 to 7 in Algorithm 1 as $p~(\leq m)$. For any iteration $r\in[p]$, we let $\mathcal{J}_{r}$ be the set of papers which the algorithm, in this iteration, fixes in the resulting assignment. We also let $\widetilde{A}_{r},r\in[p],$ denote the assignment selected in Step 3 of the $r^{\text{th}}$ iteration. Note that eventually all the papers are fixed in the final assignment $A^{\text{PR4A}}_{f}$, and hence we must have $\bigcup\limits_{r\in[p]}\mathcal{J}_{r}=[m]$.

Once papers are fixed in the final output $A^{\text{PR4A}}_{f}$, the assignment for these papers are not changed any more. Thus, at the end of each iteration $r\in[p]$ of Steps 2 to 7, the algorithm deletes (Step 6) the columns of similarity matrix that correspond to the papers fixed in this iteration. For example, at the end of the first iteration, columns which correspond to $\mathcal{J}_{1}$ are deleted from $S$. For each iteration $r\in[p]$, we let $S_{r}$ denote the similarity matrix at the beginning of the iteration. Thus, we have $S_{1}=S$, because at the beginning of the first iteration, no papers are fixed in the final assignment $A^{\text{PR4A}}_{f}$.

Moving forward, we are going to show that for every iteration $r\in[p]$, the sum similarity of the worst-off papers $\mathcal{J}_{r}$ (which coincides with the fairness of $\widetilde{A}_{r}$) is close to the best possible, given the assignment for the all papers fixed in the previous iterations. As in Theorem 1, we will compare the fairness $\Gamma^{S}_{f}\left(\widetilde{A}_{r}\right)$ with the fairness of the optimal assignment that Hard algorithm would return if called at the beginning of the $r^{\text{th}}$ iteration. We stress that for every $r\in[p]$, the Hard algorithm assigns papers $\bigcup\limits_{l=r}^{p}\mathcal{J}_{l}$ and respects the constraints on reviewers’ loads, adjusted for the assignment of papers $\bigcup\limits_{l=1}^{r-1}\mathcal{J}_{l}$ in $A^{\text{PR4A}}_{f}$. We denote the corresponding assignment as $A^{\text{HARD}}_{f}(\mathcal{J}_{\{r:p\}})$. Note that $A^{\text{HARD}}_{f}(\mathcal{J}_{\{1:p\}})=A^{\text{HARD}}_{f}$. The following corollary summarizes the main result of this section:

For any integer $r\in[p]$, the assignment $\widetilde{A}_{r}$, selected by the PeerReview4All algorithm in Step 3 of the $r^{\text{th}}$ iteration, guarantees the following lower bound on the fairness objective (4):

where values $s^{\ast}_{\kappa},\kappa\in\{0,\ldots,\lambda\}\cup\{\infty\}$, are defined with respect to the similarity matrix $S_{r}$ and constraints on reviewers’ loads adjusted for the assignment of papers $\bigcup\limits_{l=1}^{r-1}\mathcal{J}_{l}$ in $A^{\text{PR4A}}_{f}$.

The corollary guarantees that each time the algorithm fixes the assignment for some papers $j\in\mathcal{M}$ in $A^{\text{PR4A}}_{f}$, the sum similarity for these papers (which is smallest among papers from $\mathcal{M}$) is close to the optimal fairness, where optimal fairness is conditioned on the previously assigned papers. In case $r=1$, the bound (8) coincides with the bound (7) from Theorem 1. Hence, once the assignment for the most worst-off papers is fixed, the PeerReview4All algorithm adjusts maximum reviewers’ loads and looks for the most fair assignnment of the remaining papers.

3 Comparison to past literature

In this section we discuss how the approximation results established in previous sections relate to the past literature.

First, we note that the assignment $A_{1}$, computed in Step 2 in the first iteration of Steps 2 to 7 of Algorithm 1, recovers the assignment of Hartvigsen et al., 1999, thus ensuring that our algorithm is at least as fair as theirs. Second, if the goal is to assign only one reviewer ($\lambda=1$) to each of the papers, then our PeerReview4All algorithm finds the optimally fair assignment and recovers the classical result of Garfinkel, 1971.

In the remainder of this section, we provide a comparison between the guarantees of the PeerReview4All algorithm established in Theorem 1 and the guarantees of the ILPR algorithm (Garg et al., 2010). Rewriting the results of Garg et al., 2010 in our notation, we have the bound:

Note that our bound (7) for our PeerReview4All algorithm is multiplicative and bound for the ILPR algorithm is additive which makes them incomparable in a sense that neither one dominates another. However, we stress the following differences. First, if we assume $f$ to be upper-bounded by one, then assignment $A^{\text{ILPR}}$ satisfies the bound

This bound gives a nice additive approximation factor — for a large value of the optimal fairness $\Gamma^{S}_{f}\left(A^{\text{HARD}}_{f}\right)$, the constant additive factor is negligible. However, if the optimal fairness is small, which can happen if some papers do not have a sufficient number of high-expertise reviewers, then the lower bound on the fairness of the ILPR assignment (10) becomes negative, making the guarantees vacuous as any arbitrary assignment will achieve a non-negative fairness. Note that this issue is not an artifact of the analysis but is inherent in the ILPR algorithm itself, as we demonstrate in the example presented in Table 1 and in Appendix A.1. In contrast, our algorithm in the worst case has a multiplicative approximation factor $1/\lambda$ ensuring that it always returns a non-trivial assignment.

This discrepancy becomes more pronounced if the function $f$ is allowed to be unbounded, and the similarities are significantly heterogeneous. Suppose there is some reviewer $i\in[n]$ and paper $j\in[m]$ such that $f(s_{ij})\gg\Gamma^{S}_{f}\left(A^{\text{HARD}}\right)$. Then the bound (9) for the ILPR algorithm again becomes vacuous, while the bound (7) for the PeerReview4All algorithm continues to provide a non-trivial approximation guarantee.

Finally, we note that the bound (9) is also extended by Garg et al., 2010 to obtain guarantees on the fairness for the second worst-off paper and so on.

Objective-score model

We now turn to establishing statistical guarantees for our PeerReview4All algorithm from Section 4. We begin by considering an “objective” score model which we borrow from past works.

Note that McGlohon et al., 2010; Dai et al., 2012 and Sajjadi et al., 2016 consider the restricted setting with $\sigma_{ij}=\sigma_{i}$ for all $(i,j)\in[n]\times[m]$, which implies that the variance of the reviewers’ scores depends only on the reviewer, but not on the paper reviewed. We claim that this assumption is not appropriate for our peer-review problem: conferences today (such as ICML and NeurIPS) cover a wide spectrum of research areas and it is not reasonable to expect the reviewer to be equally competent in all of the areas.

In our analysis, we assume that the noise variances are some function of the underlying computed similarities. Recall that the similarities can capture not only affinity in research areas but may also incorporate the bids or preferences of reviewers, past history of review quality, etc. We assume that for any $i\in[n]$ and $j\in[m]$, the noise variance

for some monotonically decreasing function $h:\rightarrow[0,\infty)$. We assume that this function $h$ is known; this assumption is reasonable as the function can, in principle, be learned from the data from the past conferences.

We note that the model (11) does not consider reviewers’ biases. However, some reviewers might be more stringent while others are more lenient. This difference results in score of any reviewer $i$ for any paper $j$ being centered not at $\theta^{\ast}_{j}$, but at $(\theta^{\ast}_{j}+b_{i})$. A common approach to reduce biases in reviewers’ scores is a post-processing. For example, Ge et al., 2013 compared different statistical models of reviewers in attempt to calibrate the biases; the techniques developed in that work may be extended to the reviewer model (11). Thus, we leave that bias term out for simplicity.

2 Estimator

Given a valid assignment $A\in\mathcal{A}$, the goal of an estimator is to recover the top $k$ papers. A natural way to do so is to compute the estimates of true paper scores $\theta^{\ast}_{j}$ and return top $k$ papers with respect to these estimated scores. The described estimation procedure is a significantly simplified version of what is happening in the real-world conferences. Nevertheless, this fully-automated procedure may serve as a guideline for area chairs, providing a first-order estimate of the total ranking of submitted papers. In what follows, we refer to any estimator as $\widehat{\theta}$ and to the estimated score of any paper $j$ as $\widehat{\theta}_{j}$. Specifically, we consider the following two estimators:

Maximum likelihood estimator (MLE) ${\widehat{\theta}}^{\text{MLE}}$

Under the model (11), $\widehat{\theta}^{\text{MLE}}_{j}$ is known to have minimal variance across all linear unbiased estimations. The choice of ${\widehat{\theta}}^{\text{MLE}}$ follows a paradigm that more experienced reviewers should have higher weight in decision making.

Mean score estimator (MEAN) ${\widehat{\theta}}^{\text{MEAN}}$

The mean score estimator is convenient in practice because it is not tied to the assumed statistical model, and in the past has been found to be predictive of final acceptance decisions in peer-review settings such as National Science Foundation grant proposals (Cole et al., 1981) and homework grading (Sajjadi et al., 2016). This observation is supported by the program chair of ICML 2012 John Langford, who notices in his blog (Langford, 2012) that in ICML 2012 the decisions on the acceptance were “surprisingly uniform as a function of average score in reviews”.

3 Analysis

Here we present statistical guarantees for both ${\widehat{\theta}}^{\text{MLE}}$ and ${\widehat{\theta}}^{\text{MEAN}}$ estimators and for both exact top $k$ recovery and recovery under a Hamming error tolerance.

Let us use $(k)$ and $(k+1)$ to denote the indices of the papers that are respectively ranked $k^{\text{th}}$ and $\left(k+1\right)^{\text{th}}$ according to their true qualities. Similar to the past work by Shah and Wainwright, 2015 on top $k$ item recovery, a central quantity in our analysis is a $k$-separation threshold $\Delta_{k}$ defined as:

Intuitively, if the difference between $k^{\text{th}}$ and $\left(k+1\right)^{\text{th}}$ papers is large enough, it should be easy to recover top $k$ papers. To formalize this intuition, for any value of a parameter $\delta\geq 0$, consider a family $\mathcal{F}_{k}$ of papers’ scores

For the first half of this section, we assume that function $h$ is bounded, that is, $h:\to$. More generally, we could consider bounded function $h$ with range $[0,c]$ for some $c>0$. Without loss of generality, we set $c=1$ which can always be achieved by appropriate scaling. This assumption implicitly assumes that every reviewer $i\in[n]$ can provide a minimum level of expertise while reviewing any paper $j\in[m]$ even if she/he has zero similarity $s_{ij}=0$ with that paper.

In addition to the gap $\Delta_{k}$, the hardness of the problem also depends on the similarities between reviewers and papers. For instance, if all reviewers have near-zero similarity with all the papers, then recovery is impossible unless the gap is extremely large. In order to quantify the tractability of the problem in terms of the similarities we introduce the following set $\mathcal{S}$ of families of similarity matrices parameterized by a non-negative value $q$:

In words, if similarity matrix $S$ belongs to $\mathcal{S}(q)$, then the fairness of the optimally fair (with respect to $f=1-h$) assignment is at least $q$.

Finally, we define a quantity $\tau_{q}$ that captures the quality of approximation provided by PeerReview4All:

Note that Theorem 1 gives lower bounds on the value of $\tau_{q}$.

Having defined all the necessary notation, we are ready to present the first result of this section on recovering the set of top $k$ papers $\mathcal{T}^{\ast}_{k}$.

(a) For any $\epsilon\in(0,1/4)$, $q\in[\lambda\left(1-h(0)\right),\lambda]$ and any monotonically decreasing $h:\to$, if $\delta>\frac{2\sqrt{2}}{\lambda}\sqrt{\left(\lambda-q\tau_{q}\right)\ln\frac{m}{\sqrt{\epsilon}}}$, then for $\left(A,\widehat{\theta}\right)\in\left\{\left(A^{\text{PR4A}}_{1-h},{\widehat{\theta}}^{\text{MEAN}}\right),\left(A^{\text{PR4A}}_{h^{-1}},{\widehat{\theta}}^{\text{MLE}}\right)\right\}$

(b) Conversely, for any continuous strictly monotonically decreasing $h:\to$ and any $q\in[\lambda\left(1-h(0)\right),\lambda]$, there exists a universal constant $c>0$ such that if $m>6$ and $\delta<\frac{c}{\lambda}\sqrt{\left(\lambda-q\right)\ln m}$, then

1. The PeerReview4All assignment algorithm thus leads to a strong minimax guarantee on the recovery of the top $k$ papers: the upper and lower bounds differ by at most a $\tau_{q}\geq\frac{1}{\lambda}$ term in the requirement on $\delta$ and constant pre-factor. Also note that as discussed in Section 5.1, approximation factor $\tau_{q}$ of the PeerReview4All algorithm can be much better than $1/\lambda$ for various similarity matrices.

2. In addition to quantifying the performance of PeerReview4All, an important contribution of Theorem 2 is a sharp minimax analysis of the performance of every assignment algorithm. Indeed, the approximation ratio $\tau_{q}$ (17) can be defined for any assignment algorithm, by substituting corresponding assignment instead of $A^{\text{PR4A}}_{1-h}$. For example, if one has access to the optimal assignment $A^{\text{HARD}}$ (e.g., by using PeerReview4All if $\lambda=1$) then we will have corresponding approximation ratio $\tau_{q}=1$ thereby yielding bounds that are sharp up to constant pre-factors.

3. While on one hand the estimator ${\widehat{\theta}}^{\text{MLE}}$ is preferred over ${\widehat{\theta}}^{\text{MEAN}}$ when model (11) is correct, on the other hand, if $h(s)\in$, then the estimator ${\widehat{\theta}}^{\text{MEAN}}$ is more robust to model mismatches.

4. The technical assumption $q\in[\lambda\left(1-h(0)\right),\lambda]$ is made without loss of any generality, because values of $q$ outside this range are vacuous. In more detail, for any similarity matrix $S\in^{n\times m}$, it must be that $\Gamma^{S}_{1-h}\left(A^{\text{HARD}}_{1-h}\right)\geq\lambda\left(1-h(0)\right)$. Moreover, the co-domain of function $h$ comprises only non-negative real values, implying that $\Gamma^{S}_{1-h}\left(A^{\text{HARD}}_{1-h}\right)\leq\lambda$ for any similarity matrix $S\in^{n\times m}$.

5. The upper bound of the theorem holds for a slightly more general model of reviewers — reviewers with sub-Gaussian noise. Formally, in addition to the Gaussian noise model (11), the proof of Theorem 2(a) also holds for the following class of distributions of the score $y_{ij}$:

where $sG\left(\sigma^{2}\right)$ is an arbitrary mean zero sub-Gaussian random variable with scale parameter $\sigma^{2}$.

The conditions of Theorem 2 require function $h$ to be bounded. We now relax our earlier boundedness assumption on $h$ and consider $h:\to[0,\infty)$.

In what follows we restrict our attention to MLE estimator ${\widehat{\theta}}^{\text{MLE}}$ which represents the paradigm that reviewers with higher similarity should have more weight in the final decision. In order to demonstrate that our PeerReview4All algorithm is able to adapt to different structures of similarity matrices — from hard cases when optimal assignment provides only one strong reviewer for some of the papers, to ideal cases when there are $\lambda$ strong reviewers for every paper — let us consider the following set $\mathcal{S}_{\kappa}$ of families of similarity matrices parametrized by a non-negative value ${v}$ and integer parameter $\kappa\in[\lambda]$:

Here $s^{\ast}_{\kappa}$ is as defined in (6).

In words, the parameter ${v}$ defines the notion of strong reviewer while parameter $\kappa$ denotes the maximum number of strong (with similarity higher than ${v}$) reviewers that can be assigned to each paper without violating the $(\mu,\lambda)$ conditions.

Then the following adaptive analogue of Theorem 2 holds:

(a) For any $\epsilon\in(0,1/4)$, ${v}\in$, $\kappa\in[\lambda]$ and any monotonically decreasing $h:\to[0,\infty)$, if $\delta>2\sqrt{2}\sqrt{\frac{h({v})h(0)}{\kappa h(0)+({\lambda-\kappa})h({v})}\ln\frac{m}{\sqrt{\epsilon}}}$, then

(b) Conversely, for any continuous strictly monotonically decreasing $h:\to[0,\infty)$, any ${v}\in$, and any $\kappa\in[\lambda]$, there exists a universal constant $c>0$ such that if $m>6$ and $\delta\leq c\sqrt{\frac{h({v})h(0)}{\kappa h(0)+({\lambda-\kappa})h({v})}\ln m}$, then

1. Observe that there is no approximation factor in the upper bound. Thus, the PeerReview4All algorithm together with ${\widehat{\theta}}^{\text{MLE}}$ are simultaneously minimax optimal up to a constant pre-factor in classes of similarity matrices $\mathcal{S}_{\kappa}({v})$ for all $\kappa\in[\lambda]$, ${v}\in$.

2. Corollary 2(a) remains valid for generalized sub-Gaussian model of reviewer (19).

3. Corollary 2 together with Theorem 2 show that our PeerReview4All algorithm produces the assignment $A^{\text{PR4A}}_{h^{-1}}$ which is simultaneously minimax (near-)optimal for various classes of similarity matrices. We thus see that our PeerReview4All algorithm is able to adapt to the underlying structure of similarity matrix $S$ in order to construct an assignment in which even the most disadvantaged paper gets reviewers with sufficient expertise to estimate the true quality of the paper.

3.2 Approximate recovery under Hamming error

Although our ultimate goal is to recover set $\mathcal{T}^{\ast}_{k}$ of top $k$ papers exactly, we note that often scores of boundary papers are close to each other so it may be impossible to distinguish between the $k^{\text{th}}$ and $(k+1)^{\text{th}}$ papers in the total ranking. Thus, a more realistic goal would be to try to accept papers such that the set of accepted papers is in some sense “close” to the set $\mathcal{T}^{\ast}_{k}$. In this work we consider the standard notion of Hamming distance (1) as a measure of closeness. We are interested in minimizing the quantity:

for some user-defined value of $t\in[k-1]$.

Similar to the exact recovery setup, the key role in the analysis is played by generalized separation threshold (compare with equation 14):

where $(k-t)$ and $(k+t+1)$ are indices of papers that take $(k-t)^{\text{th}}$ and $(k+t+1)^{\text{th}}$ positions respectively in the underlying total ranking. For any value of $\delta>0$ we consider the following generalization of the set $\mathcal{F}_{k}(\delta)$ defined in (15):

Also recall the family of matrices $\mathcal{S}(q)$ from (16) and the approximation factor $\tau_{q}$ from (17) for any parameter $q$. With this notation in place, we now present the analogue of Theorem 2 in case of approximate recovery under the Hamming error.

(a) For any $\epsilon\in(0,1/4)$, $q\in[\lambda\left(1-h(0)\right),\lambda]$, $t\in[k-1]$, and any monotonically decreasing $h:\to$, if $\delta>\frac{2\sqrt{2}}{\lambda}\sqrt{\left(\lambda-q\tau_{q}\right)\ln\frac{m}{\sqrt{\epsilon}}}$, then for $\left(A,\widehat{\theta}\right)\in\left\{\left(A^{\text{PR4A}}_{1-h},{\widehat{\theta}}^{\text{MEAN}}\right),\left(A^{\text{PR4A}}_{h^{-1}},{\widehat{\theta}}^{\text{MLE}}\right)\right\}$

(b) Conversely, for any continuous strictly monotonically decreasing $h:\to$, any $q\in[\lambda\left(1-h(0)\right),\lambda]$, and any $0<t<k$, there exists a universal constant $c>0$ such that for given constants $\nu_{1}\in(0;1)$ and $\nu_{2}\in(0,1)$ if $2t\leq\frac{1}{1+\nu_{2}}\min\left\{m^{1-\nu_{1}},k,m-k\right\}$ and $\delta\leq\frac{c}{\lambda}\sqrt{\left(\lambda-q\right)\nu_{1}\nu_{2}\ln m}$, then for $m$ larger than some $(\nu_{1},\nu_{2})$-dependent constant,

This theorem provides a strong minimax characterization of the PeerReview4All algorithm for approximate recovery. Note that upper and lower bounds differ by the approximation factor $\tau_{q}$, which is at most $\frac{1}{\lambda}$, and a pre-factor which depends only on the constants $\nu_{1}$ and $\nu_{2}$.

To conclude the section, we state the result for the family $\mathcal{S}_{\kappa}({v})$ of similarity matrices defined in (20) for any parameter ${v}$, showing that adaptive behavior of PeerReview4All algorithm (Corollary 2) also carries over to the Hamming error metric.

(a) For any $\epsilon\in(0,1/4)$, ${v}\in$, $\kappa\in[\lambda]$, $t\in[k-1]$, and any monotonically decreasing $h:\to[0,\infty)$, if $\delta>2\sqrt{2}\sqrt{\frac{h({v})h(0)}{\kappa h(0)+({\lambda-\kappa})h({v})}\ln\frac{m}{\sqrt{\epsilon}}}$, then

(b) Conversely, for any continuous strictly monotonically decreasing $h:\to[0,\infty)$, any ${v}\in$, $\kappa\in[\lambda]$ and any $t\in[k-1]$, there exists a universal constant $c>0$ such that for given constants $\nu_{1}\in(0;1)$ and $\nu_{2}\in(0,1)$ if $2t\leq\frac{1}{1+\nu_{2}}\min\left\{m^{1-\nu_{1}},k,m-k\right\}$ and $\delta\leq c\sqrt{\frac{h({v})h(0)}{\kappa h(0)+({\lambda-\kappa})h({v})}\nu_{1}\nu_{2}\ln{m}}$, then for $m$ larger than some $(\nu_{1},\nu_{2})$-dependent constant,

The results established in this section thus show that our PeerReview4All algorithm produces an assignment which is minimax (near-)optimal for both exact and approximate recovery of the top $k$ papers.

Subjective-score model

In the previous section, we analyzed the performance of our PeerReview4All assignment algorithm under a model with objective scores. Indeed, various past works on peer-review (as well as various other domains of machine learning) assume existence of some “true” objective scores or ranking of the underlying items (papers). However, in practice, reviewers’ opinions on the quality of any paper are typically highly subjective (Kerr et al., 1977; Mahoney, 1977; Ernst and Resch, 1994; Bakanic et al., 1987; Lamont, 2009). Even two highly experienced researchers with vast experience and expertise may have considerably differing opinions about the contributions of a paper. Following this intuition, we wish to move away from the assumption of some true objective scores $\{\theta^{\ast}_{j}\}_{j\in[m]}$ of the paper.

With this motivation, in this section we develop a novel model to capture such subjective opinions and present a statistical analysis of our assignment algorithm under this subjective-score model.

Let us now exit our hypothetical world and return to reality. In a real conference peer-review setting the reviews will be noisy. Following the previous noise assumptions, we assume that score of any reviewer $i\in[n]$ for any paper $j\in[m]$ that she/he reviews is distributed as

for some known continuous strictly monotonically decreasing function $h:\rightarrow$. Under this model, the higher the similarity $s_{ij}$, the better the score $y_{ij}$ represents the subjective score $\widetilde{\theta}_{ij}$ which reviewer $i\in[n]$ would give to paper $j\in[m]$ if she/he had infinite expertise.

The goal under this model is to assign reviewers to papers such that reviewers are of enough ability to convey their opinions $\widetilde{\theta}_{ij}$ from the hypothetical full-competence world to the real world with scores $y_{ij}$. In other words, the goal of the assignment is to ensure the recovery of the top $k$ papers in terms of the mean full-competence subjective scores $\{\widetilde{\theta}^{\star}_{j}\}_{j\in[m]}$.

2 Analysis

In this section we present statistical guarantees for ${\widehat{\theta}}^{\text{MEAN}}$ in context of subjective-score model.

Since the true scores for any reviewer-paper pair are subjective, and since we are interested in mean full-competence subjective scores, a natural choice for estimating $\{\widetilde{\theta}^{\star}_{j}\}$ from the actual provided scores $\{y_{ij}\}$ is the averaging estimator ${\widehat{\theta}}^{\text{MEAN}}$ which for every paper $j\in[m]$ estimates $\widetilde{\theta}^{\star}_{j}$ as $\widehat{\theta}^{\text{MEAN}}_{j}=\frac{1}{\lambda}\sum\limits_{i\in\mathcal{R}_{A}(j)}y_{ij}$. Having defined the model and estimator, we now provide a sharp minimax analysis for the subjective-score model. In order to state our main result, we recall the family of similarity matrices $\mathcal{S}(q)$ defined earlier in (16) and the approximation ratio $\tau_{q}$ defined in (17), both parameterized by some non-negative value $q$.

Note that the notion of the $k$-separation threshold (14) does not carry over directly from the objective score model to the subjective score model. The reason is that the ranking now is induced by the assignment and changes as we change the assignment. Consequently, we introduce the following family of papers’ scores that are governed by the assignment $A$ and parametrized by a positive real value $\delta$:

Since in this section we consider only mean score estimator ${\widehat{\theta}}^{\text{MEAN}}$, we omit index $1-h$ from $A^{\text{PR4A}}_{1-h}$, but always imply that assignment $A^{\text{PR4A}}$ is built with respect to the function $1-h$. For every feasible assignment $A$, we augment the notation $\mathcal{T}^{\ast}_{k}$ with $\mathcal{T}^{\star}_{k}\left(A,\widetilde{\theta}^{\star}(A)\right)$ to highlight that the set of the top $k$ papers is induced by the assignment $A$. Let us now present the main result of this section.

(a) For any $\epsilon\in(0,1/4)$, $q\in[\lambda\left(1-h(0)\right),\lambda]$ and any monotonically decreasing $h:\to$, if $\delta>\frac{2\sqrt{2}}{\lambda}\sqrt{\left(\lambda-q\tau_{q}\right)\ln\frac{m}{\sqrt{\epsilon}}}$, then

(b) Conversely, for any continuous strictly monotonically decreasing $h:\to$ and any $q\in[\lambda\left(1-h(0)\right),\lambda]$, there exists a universal constant $c>0$ such that if $m>6$ and $\delta<\frac{c}{\lambda}\sqrt{\left(\lambda-q\right)\ln m}$, then

We thus see that our assignment algorithm PeerReview4All not only leads to the strong guarantees under the objective-score model but simultaneously also under the setting where the opinions of reviewers may be subjective.

2.2 Approximate recovery under Hamming error

We now present guarantees for approximate recovering under the Hamming error for the PeerReview4All algorithm. We generalize the family of score matrices (22), for which we consider any integer error tolerance parameter $t\in\{0,\ldots,k-1\}$ and any any feasible assignment $A$. Then we define the following family of subjective papers’ scores, parameterized by non-negative value $\delta$:

Observe that the class $\mathcal{F}_{k,t}(A,\delta)$ coincides with the class $\mathcal{F}_{k}(\delta)$ from (22) when $t=0$.

(a) For any $\epsilon\in(0,1/4)$, $q\in[0,\lambda]$, $t\in[k-1]$, and any monotonically decreasing $h:\to$, if $\delta>\frac{2\sqrt{2}}{\lambda}\sqrt{\left(\lambda-q\tau_{q}\right)\ln\frac{m}{\sqrt{\epsilon}}}$, then

Conversely, for any continuous strictly monotonically decreasing $h:\to$, any $q\in[\lambda\left(1-h(0)\right),\lambda]$, and any $0<t<k$, there exists a universal constant $c>0$ such that for given constants $\nu_{1}\in(0,1)$ and $\nu_{2}\in(0,1)$ if $2t\leq\frac{1}{1+\nu_{2}}\min\left\{m^{1-\nu_{1}},k,m-k\right\}$ and $\delta\leq\frac{c}{\lambda}\sqrt{\left(\lambda-q\right)\nu_{1}\nu_{2}\ln m}$, then for $m$ larger than some $(\nu_{1},\nu_{2})$-dependent constant,

Similar to Theorem 4, Theorem 5 shows that PeerReview4All algorithm is minimax optimal up to a constant pre-factor and approximation factor given that reviewers’ subjective scores $\widetilde{\Theta}$ belong to the class $\mathcal{F}_{k,t}(A,\delta)$.

Experiments

In this section we conduct empirical evaluations of the PeerReview4All algorithm and compare it with the TPMS (Charlin and Zemel, 2013), ILPR (Garg et al., 2010) and Hard algorithms. Our implementation of the PeerReview4All algorithm picks max-flow with maximum cost in Step 6 of Subroutine 1.

Previous work on the conference paper assignment problem (Garg et al., 2010; Long et al., 2013; Karimzadehgan et al., 2008; Tang et al., 2010) conducted evaluations of the proposed algorithms in terms of various objective functions that measure the quality of the assignment. For example, Garg et al., 2010 compared fairness from reviewers’ perspective using the number of satisfied bids as a criteria. While these evaluations allow to compare algorithms in terms of particular objective, we note that the main goal of the peer-review system is to accept the best papers. It is not straightforward whether an improvement of some other objective will lead to the improvement of the quality of the paper acceptance process.

In contrast to the prior works, in this section we not only consider the fairness objective (Subsections 8.2 and 8.3), but also design experiments (Subsections 8.1 and 8.4) to directly evaluate the accuracy resulting from the assignment procedures.

We begin with synthetic simulations. We consider the instance of the reviewer assignment problem with $m=n=100$ and $\lambda=\mu=4$. We select the moderate values of $m$ and $n$ to keep track of the optimal assignment $A^{\text{HARD}}$ which we find as a solution of the corresponding integer linear programming problem. For every real-valued constant $c$, we denote the matrix with all entries being equal to $c$ as $\mathbf{c}$. Similarly, we denote the matrix with entries independently sampled from a Beta distribution with parameters $\left(\alpha,\beta\right)$ as $\mathbf{\mathcal{B}\left(\alpha,\beta\right)}$.

We consider the objective-score model of reviewers (11) with $h(s)=1-s$ together with estimator ${\widehat{\theta}}^{\text{MLE}}$. Thus, assignments $A^{\text{PR4A}}$, $A^{\text{ILPR}}$ and $A^{\text{HARD}}$ aim to optimize $\Gamma^{S}_{\left(1-s\right)^{-1}}\left(A\right)$ while assignment $A^{\text{TPMS}}$ aims to maximize the cumulative sum of similarities $G^{S}\left(A\right)$ as defined in (2).

In what follows we simulate the following problem instances:

Non-mainstream papers. There are $m_{1}=80$ conventional papers for which there exist $n_{1}=80$ expert reviewers with high similarity, and $m_{2}=20$ non-mainstream papers for which all the reviewers have similarity smaller than or equal to $0.5$. There are also $n_{2}=20$ weak reviewers who have moderate similarities with papers from the first group and low similarities with papers from the second group. The similarities are given by the block matrix:

Many weak reviewers. In this scenario there are $n_{1}=25$ strong reviewers with high similarity with every paper and $n_{2}=75$ weak reviewers with small similarity with every paper:

Few super-strong reviewers. The following example tests the algorithms in scenario when some small number of the reviewers are much stronger than the others. Similarities for this scenario are given by the block matrix:

Adverse case. Having analyzed the inner working of our PeerReview4All algorithm, we construct a similarity matrix which is hard for the algorithm to compute the fair assignment. We do not give an explicit expression of the matrix $S_{4}$ for this case, due to its complicated structure.

Sparse similarities. Each entry of similarity matrix $S_{5}$ is zero with probability $0.8$ or otherwise is drawn independently and uniformly at random from $[0.1,0.9]$.

In this section we analyze the quality of assignments produced by PeerReview4All, Hard, ILPR and TPMS algorithms and for all the five cases described above. The results are summarized in Table 2 where we compute the measures of fairness $\Gamma^{S}_{(1-s)^{-1}}\left(A\right)$ and the conventional sum of similarities $G^{S}\left(A\right)$ for each of the assignments.

The results in Table 2 show that in all five cases PeerReview4All algorithm finds an assignment $A^{\text{PR4A}}$ with at least as much fairness as $A^{\text{TPMS}}$. At the same time, the max cost heuristic that we use in Step 6 of Subroutine 1 helps the average quality (total sum similarity) of the assignment $A^{\text{PR4A}}$ to be either close to or larger than average quality of both $A^{\text{ILPR}}$ and $A^{\text{HARD}}$.

In Case (C1), the TPMS algorithm sacrifices the quality of reviewers for non-mainstream papers, assigning them to weak reviewers. In contrast, all other algorithms assign four best possible reviewers to these unconventional papers in order to maintain fairness. In Case (C2), the PeerReview4All and Hard algorithms assign one strong reviewer for each paper while TPMS, in attempt to maximize the value of its goal function, assigns strong reviewers according to their highest similarities which leads to an unfair assignment. The ILPR algorithm fails to find a fair assignment in Cases (C2) and (C3): the poor performance of ILPR algorithm is caused by the fact that some of the reviewers in our examples have similarities close to maximal, making the value of $f(s)=\frac{1}{1-s}$ large, which, in turn, makes the approximation guarantee (9) of ILPR algorithm weak. In Case 6, the PeerReview4All algorithm was unable to recover the fair assignment. Instead, the assignment within approximation ratio $1/3$, which is a bit better than the worst case $1/\lambda=1/4$ approximation, was discovered. Finally, in Case (C5), the all algorithms managed to recover fair assignment. However, we note that the total sum similarity of the $A^{\text{HARD}}$ assignment is low as compared to other algorithms. The reason is that the corresponding solution of the integer linear programming problem in the Hard algorithm is optimized for the fairness towards the worst-off paper and does not try to continue optimization, once the assignment for that paper is fixed. In contrast, both PeerReview4All and ILPR algorithms try to maximize the fate of the second worst-off paper, when the assignment for the most worst-off paper is fixed.

1.2 Statistical accuracy

As we have pointed out, the main goal of the assignment procedure is to ensure the acceptance of the $k$ best papers $\mathcal{T}^{\ast}_{k}$. While in real conferences the acceptance process is complicated and involves discussions between reviewers and/or authors, here we consider a simplified scenario. Namely, we assume an objective-score model defined in Section 6 and reviewer model (11) with $h(s)=1-s$.

The experiment executes 1,000 iterations of the following procedure. We randomly choose $k=20$ indices of the “true best” papers $\mathcal{T}^{\ast}_{k}=\left\{j_{1},\ldots,j_{k}\right\}\subset[m]$. Each of these papers $j\in\mathcal{T}^{\ast}_{k}$ is assigned score $\theta^{\ast}_{j}=1$, while for each of the remaining papers $j\in[m]\backslash\mathcal{T}^{\ast}_{k}$ we set $\theta^{\ast}_{j}=1-\Delta_{k}$, where $\Delta_{k}\in(0,2]$. Next, given the similarity matrix $S$, we compute assignments $A^{\text{PR4A}}$, $A^{\text{HARD}}$, $A^{\text{ILPR}}$ and $A^{\text{TPMS}}$. For each of these assignments we compute the estimations of the set of top $k$ papers using the ${\widehat{\theta}}^{\text{MLE}}$ estimator and calculate the fraction of wrongly accepted papers.

For every similarity matrix $S_{r},r\in$, and for every value of $\Delta_{k}\in\left\{0.1k\ |k\in\right\}$, we compute the mean of the obtained values over the 1,000 iterations. Figure 1 summarizes the dependence of the fraction of incorrectly accepted papers on the value of separation threshold $\Delta_{k}$ for all five cases (C1)-(C5).

The obtained results suggest that the increase in fairness of the assignment leads to an increase in the accuracy of the acceptance procedure, provided that the average sum similarity of the assignment does not decrease dramatically. The PeerReview4All algorithm significantly outperforms TPMS both in terms of fairness and in terms of fraction of incorrectly accepted papers for the first four cases. The low fairness of assignments computed by ILPR in Cases (C2) and (C3) lead to the large fraction of errors in the acceptance procedure. As we noted earlier, the ILPR algorithm has weak approximation guarantees when the function $f$ is allowed to be unbounded. In section 8.4 we will consider the mean score estimator ($f(s)=s$) which is more suitable scenario for ILPR algorithm.

Interestingly, in Case 6, the PeerReview4All algorithm recovers sub-optimal assignment in terms of fairness, but still performs well in terms of the accuracy of the acceptance procedure. To understand this effect, for each of the assignments $A^{\text{TPMS}},A^{\text{HARD}},A^{\text{ILPR}}$ and $A^{\text{PR4A}}$ we compute the sum similarity for all papers in the assignments and plot these values for $50$ the most worst-off papers in each of the assignment in Figure 2. Despite the inability of PeerReview4All to find the fair assignment for the most worst-off paper, Corollary 1 guarantees that sum similarities for the remaining papers will not be too far from the optimal, and we see this aspect in Figure 26. As one can see, the sum similarity for all but tiny fraction of papers in $A^{\text{PR4A}}$ is large enough, thus ensuring the low fraction of incorrectly accepted papers.

Finally, note that in Case (C5), the Hard algorithm, while having optimal fairness, has a lower accuracy as compared to other algorithms. As Figure 2(C5) demonstrates, the Hard algorithm does not optimize for the second worst off paper and recovers sub-optimal assignment for all but the most disadvantaged paper. In contrast, as Figure 2 suggests, the ILPR and PeerReview4All algorithms do not stop their work after the most disadvantaged paper is satisfied, but instead continue to optimize the assignment for the remaining papers and eventually ensure not only fairness, but also high average quality of the assignment.

2 Experiment on the approximation of ICLR similarity matrix

In absence of publicly available similarity matrices from conferences, we are unable to compare the assignment computed by the PeerReview4All algorithm to the actual conference assignment. To circumvent this issue, we use an approximate version of the similarity matrix from the International Conference on Learning Representations (ICLR’18) that was constructed by Xu et al., 2019b and compare the performance of the PeerReview4All and TPMS assignment algorithms on this matrix.

The similarity matrix we use for comparison was constructed by Xu et al., 2019b as follows. OpenReview (openreview.net) — increasingly popular conference management system — maintains a public database of all papers (with author identities being visible) submitted to the ICLR’18 conference, thereby giving access to the pool of submissions. Next, it was assumed that all authors of submissions are simultaneously reviewers and that there are no additional reviewers. The publication profiles of reviewers were constructed by scraping the data from databases of scientific publications. Finally, the open-source code (bitbucket.org/lcharlin/tpms/) and the material of the original paper (Charlin and Zemel, 2013) were used to compute the similarity matrix according to the TPMS procedure.

The process outlined above resulted in the similarity matrix $S$ that has $n=2435$ reviewers and $m=911$ papers. Additionally, it was assumed that any reviewer has a conflict of interests with the submitted papers that she/he has authored; these conflicts are represented by a binary matrix $C$ whose $(i,j)^{\text{th}}$ entry equals $1$ if and only if reviewer $i$ has a conflict with paper $j$. Similarity matrix $S$ possesses a considerable heterogeneity as demonstrated by some papers having mean similarity with non-conflicting reviewers almost four times larger than others.

The large size of the similarity matrix makes computation of the optimally fair assignment infeasible, and hence in this section we do not compute the Hard assignment. Additionally, our implementation of the ILPR assignment algorithms was computationally inefficient and in absence of the publicly available source code we also exclude this algorithm from comparison.

2.2 Evaluation

Having defined the similarity matrix and matrix of conflicts, we compute assignments of papers to reviewers with $\lambda=4$ (each paper is assigned to 4 reviewers) and $\mu=2$ (each reviewer is allocated at most 2 papers) using the TPMS and PeerReview4All assignment algorithms with the identity transformation function $f(s)=s$. In addition to the standard load constraints, we require that no paper is assigned to a conflicting reviewer. Finally, as pointed out in Section 5.2, the fairness guarantees of Theorem 1 are achieved after the first iteration of Steps 2 to 7 of Algorithm 1. Hence, we include the corresponding assignment for comparison and denote it as $A^{\text{PR4A}}_{1}$.

Table 3 summarizes the results of the experiment, comparing the resulting assignments in terms of fairness (3) and cumulative similarity (2). We see that the fairness of the assignment computed by the PeerReview4All algorithm is significantly higher than the fairness of the TPMS algorithm. Similar to the case of synthetic simulations, the max cost heuristic used in Step 6 of Subroutine 1 helps our algorithm to maintain a high value of cumulative similarity, which is only marginally below the optimal value.

The large size of the similarity matrix at hands makes evaluation of the optimal fairness achieved by $A^{\text{HARD}}$ computationally prohibitive. However, we can still find an upper bound on $\Gamma^{S}\left(A^{\text{HARD}}\right)$ by dropping reviewer load constraints and allowing all reviewers to review unlimited number of papers. The resulting bound allows us to compute a lower bound on the approximation ratio of the PeerReview4All algorithm:

which shows that in practice the approximation factor of the PeerReview4All algorithm can be much better than the worst-case approximation factor $\frac{1}{\lambda}$ guaranteed by Theorem 1.

Continuing the analysis, for each of the assignments $A^{\text{TPMS}}$, $A^{\text{PR4A}}_{1}$ and $A^{\text{PR4A}}$ we compute the sum similarity for all papers in the assignments and plot these values for $100$ the most worst-off papers in each of the assignment in Figure 3(a). This figure demonstrates that while the fairness guarantees of Theorem 1 can be achieved by a single iteration of Steps 2 to 7, subsequent iterations help to improve the assignment for the second worst-off paper and so on. Finally, for each of the assignments $A^{\text{TPMS}}$ and $A^{\text{PR4A}}$ we sort papers in order of increasing sum similarity of assigned reviewers and plot the ratios (PeerReview4All to TPMS) of these sums in Figure 3(b). Figure 3(b) shows that the PeerReview4All algorithm indeed balances the assignment by improving the quality for the worst-off papers at the expense of decreasing the quality for the most benefiting papers.

3 Experiment on MIDL and CVPR similarity matrices

Subsequent to the publication of the first version of this paper (Stelmakh et al., 2019b), a follow-up paper by Kobren et al., 2019 has been published. There authors propose two novel assignment algorithms that also aim at ensuring the fairness of the assignment. In that work, the PeerReview4All algorithm with the identity transformation function $(f(s)=s)$ was compared with other assignment algorithms on similarity matrices from three real conferences: Medical Imaging and Deep Learning Conference (MIDL), and two editions of the Conference on Computer Vision and Pattern Recognition (CVPR’17 and CVPR’18). With the kind permission of Ari Kobren, we describe the results of their experiments in which our algorithm was evaluated.

We begin with a brief theoretical comparison of the PeerReview4All algorithm with the algorithms proposed by Kobren et al., 2019. Recall that the PeerReview4All algorithm aims at optimizing fairness of the assignment (3) and does not directly optimize for the total sum similarity. However, when in its inner workings the algorithm faces a choice between different suitable similarity matrices (Step 6 of the Subroutine 1), it can heuristically optimize for the total sum similarity by using the max cost heuristic. In contrast, Kobren et al., 2019 consider a problem of optimizing for the total sum similarity of the assignment with an additional constraint of each paper having the sum similarity larger than some threshold $T$, which can be specified by user or found by the binary search. They design two novel algorithms which we refer to as FairIr and FairFlow.

Given a feasible instance of the reviewer assignment problem, the FairIr algorithm is able to compute the assignment with the optimal value of the total sum similarity, violating the fairness constraints by an additive factor which is upper bounded by the maximum entry of the similarity matrix. In that, fairness guarantees of FairIr are equivalent to those of ILPR (and hence may become vacuous when similarity matrix is significantly heterogeneous), but additionally the FairIr algorithm achieves the highest possible value of sum similarity. Observe that this value is lower than those achieved by TPMS as FairIr has additional constraint on the fairness of the assignment. The FairFlow algorithm is a heuristic which does not have theoretical guarantees, but in return has much lower computational complexity.

Another difference between PeerReview4All and the algorithms proposed by Kobren et al., 2019 is that both FairIr and FairFlow allow to specify a lower bound on reviewer load, thereby ensuring that each reviewer reviews at least some number of papers. In our work, we do not study such constraints and PeerReview4All does not support such constraints as is. Hence, below we report only those comparisons in which our algorithm was evaluated by Kobren et al., 2019, that is, the comparisons in which the lower bound on reviewer load was not enforced.

Overall, the FairIr and FairFlow algorithms aim at balancing the fairness and the total sum similarity of the assignment. By choosing an appropriate heuristic in Step 6 of the Subroutine 1, one can ensure that PeerReview4All also heuristically optimizes for the total sum similarity. Let us now report the experimental results of Kobren et al., 2019 that allows to compare the algorithms on both objectives of fairness and total sum similarity.

3.2 Summary of the experiments

The key summary statics of the Kobren et al., 2019 experiments are represented in Table 4. We omit some statistics which are not of direct interest (for example, max sum similarity in the assignment). For each similarity matrix, the assignments respecting the corresponding paper and reviewer load constraints were computed by the TPMS, PeerReview4All, FairIr and FairFlow algorithms. These assignments were then compared based on (a) running time of the algorithm, (b) fairness of the assignment and (c) mean sum similarity of the assignment. First, we notice that our naive implementation of the PeerReview4All algorithm is significantly slower than all other algorithms, and for large instances only a single iteration of the algorithm can be computed in a reasonable time (recall that even one iteration is sufficient to satisfy the fairness guarantees of Theorem 1). Nonetheless, even on the largest instance with more than 5,000 papers the running time of the first iteration of our algorithm took less than three hours which is still feasible given that the full assignment procedure needs to be run only once in the conference timeline.

The remaining two dimensions of comparison represent two notions of quality of the assignment: fairness and total sum similarity. Ideally, we would like to have an algorithm which simultaneously optimizes both of these notions. Figure 4 visualizes the comparison of the algorithms and is constructed as follows. For each of the three experiments, we compute the maximum value of fairness achieved by any of the algorithms. Using this value, for each algorithm we compute its “competetiveness” as the fairness achieved by that algorithm divided by the maximum fairness. We then repeat the same for the total sum similarity. As a result, in each experiment the performance of each algorithm can be represented as a data point in two-dimensional space where x-axis represents the competitiveness in terms of fairness and y-axis represents the competitiveness in terms of the total sum similarity.

Figure 4 demonstrates that in each of the three experiments the PeerReview4All algorithm (even with one iteration) was able to achieve maximum or close-to-maximum values of both fairness and total sum similarity. In contrast, each of the other algorithms under consideration achieved considerably lower value of either fairness or total sum similarity in two out of three experiments.

Overall, we conclude that while being considerably (but not prohibitively) slower than other algorithms, PeerReview4All managed to achieve the best balance of fairness and total sum similarity, despite optimizing the latter objective only heuristically.

4 Experiment on Amazon Mechanical Turk

Even if peer-review data from conferences was available to us, it would not allow for an objective evaluation of any assignment algorithm with respect to accuracy of the acceptance procedure. There are two reasons for this hinderance: (a) No ground truth ranking is available; and (b) The data contains only reviews that correspond to one particular assignment and has missing reviews for other assignments.

In this section we present an experiment which we carefully design to overcome the fundamental issues with objective empirical evaluations of reviewer assignments. Our experiment allows us to directly measure the accuracy of final decisions to evaluate any assignment. We execute our experiment on the Amazon Mechanical Turk (mturk.com) crowdsourcing platform.

We designed the experiment in a manner that allows us to objectively evaluate the performance of any assignment algorithm. Specifically, the experiment should provide us access to some similarities between reviewers and papers, execute any assignment algorithm, and eventually objectively evaluate the final outcome.

The experiment considers crowdsourcing workers as reviewers and a number of general knowledge questions as papers. Specifically, 80 workers were recruited and presented with a list of 60 flags of different countries. The workers were asked to determine the country of each flag, choosing one of five options for each question. The interface of the task is represented in Figure 5. Unknown to the worker, the 60 countries comprised 10 countries each from 6 different geographic regions. Three participants did not attempt some of the questions and their responses were discarded from the dataset. The dataset is available on the first author’s website.

4.2 Evaluation

After obtaining the data from Amazon Mechanical Turk, we executed the following procedure for 1,000 iterations. In each of the 6 regions, we first split the 10 questions into two sets: a “gold standard” set of 8 questions chosen uniformly at random and an “unresolved” set comprising the 2 remaining questions. The set of all 12 unresolved questions are analogous to papers in the peer-review setting ($m=12$). We computed the similarity of any worker to any paper (question) as the fraction of questions that the worker answered correctly among the 8 gold standard questions for the region corresponding to that paper (question). Having computed the similarities, we selected $n=40$ of the workers uniformly at random and created five assignments $A^{\text{TPMS}},A^{\text{PR4A}}$, $A^{\text{ILPR}}$, $A^{\text{HARD}}$ and $A^{\text{RAND}}$, with identity transformation function $f(s)=s$, where $A^{\text{RAND}}$ is a random feasible assignment. In each of these assignments, every question was answered by $\lambda=3$ workers and every worker answered at most $\mu=2$ questions. Finally, for each assignment, we computed the answers for the remaining $m=12$ questions by taking a majority vote of the responses from workers assigned to each question. Ties are also considered as mistakes.

At the end of all iterations, we computed the fraction of questions whose final answers are estimated incorrectly under the five assignments as well as the mean fairness $\Gamma^{S}\left(A\right)$ and conventional sum of similarities $G^{S}\left(A\right)$. We summarize the results in Table 5. We see that all non-trivial algorithms significantly outperform random assignment. However, $A^{\text{TPMS}}$ incurs about $8\%$ increased error as compared to $A^{\text{PR4A}}$.

Similar to Case (C5) of synthetic experiments, the optimally fair assignment $A^{\text{HARD}}$ turns out to incur larger fraction of errors as compared to approximations $A^{\text{PR4A}}$ and $A^{\text{ILPR}}$. The reason is that the assignment $A^{\text{HARD}}$ maximizes the quality of the assignment with respect to the most “disadvantaged” question, but in contrast to $A^{\text{PR4A}}$ and $A^{\text{ILPR}}$, does not care about the fate of remaining questions.

We also see that $A^{\text{PR4A}}$ slightly outperforms $A^{\text{ILPR}}$ in terms of the fraction of errors while having slightly smaller average fairness. One reason for this is that in parallel with $\Gamma^{S}\left(A^{\text{PR4A}}\right)$ being close to optimal, PeerReview4All algorithm managed to achieve the high value of conventional sum of similarities, thus maintaining a balance between the fairness $\Gamma^{S}\left(A\right)$ and the global objective $G^{S}\left(A\right)$.

We find these observations to be of notable interest for the actual conference peer-review scenarios. The task of identifying flags in the experiment involved a rather homogeneous set of similarities (in the sense that each worker either knew many or only few flags) where optimizing (2) or (3) would yield similar results. In contrast, the significantly higher heterogeneity in peer-review, the presence of many non-mainstream papers as well as both very strong and very weak reviewers, is expected to further amplify the observed improvements offered by the PeerReview4All algorithm as compared to TPMS and ILPR.

Proofs

We now present the proofs of our main results.

We prove the result in three steps. First, we establish a lower bound on the fairness of the PeerReview4All algorithm. Then we establish an upper bound on the fairness of the optimal assignment. Finally, we combine these bounds to obtain the result (7).

Lower bound for the PeerReview4All algorithm.

We show a lower bound for the intermediate assignment $\widetilde{A}$ at Step 3 during the first iteration of Steps 2 to 7. We denote this particular assignment as $\widetilde{A}_{1}$. Note that in Step 4 we fix the assignment for $\widetilde{A}_{1}$’s worst-off papers into the final output, and hence we have $\Gamma^{S}_{f}\left(\widetilde{A}_{1}\right)\geq\Gamma^{S}_{f}\left(A^{\text{PR4A}}_{f}\right)$. On the other hand, by keeping track of $A_{0}$ (Step 7), we ensure that in all of the subsequent iterations of Steps 2 to 7, the temporary assignment $\widetilde{A}$ will be at least as fair as $\widetilde{A}_{1}$, which implies $\Gamma^{S}_{f}\left(\widetilde{A}_{1}\right)=\Gamma^{S}_{f}\left(A^{\text{PR4A}}_{f}\right)$.

Getting back to the first iteration of Steps 2 to 7, we note that when Step 2 is completed, we have $\lambda$ assignments $A_{1},\ldots,A_{\lambda}$ as candidates. Notice that for every $\kappa\in[\lambda]$, assignment $A_{\kappa}$ is constructed with a two-step procedure by joining the outputs $A_{\kappa}^{1}$ and $A_{\kappa}^{2}$ of Subroutine 1. Recalling the definition (6) of $s^{\ast}_{\kappa}$, we now show that for every value of $\kappa\in[\lambda]$, the assignment $A_{\kappa}^{1}$ satisfies:

Consider any value of $\kappa\in[\lambda]$. The definition of $s^{\ast}_{\kappa}$ ensures that there exist an assignment, say $A^{\ast}$, which assigns $\kappa$ reviewers to each paper in a way that minimum similarity in this assignment equals $s^{\ast}_{\kappa}$. Now note that Subroutine 1, called in Step 2b of the algorithm, adds edges to the flow network in order of decreasing similarities. Thus, at the time all edges with similarity higher or equal to $s^{\ast}_{\kappa}$ are added, we have that no edges with similarity smaller that $s^{\ast}_{\kappa}$ are added, and that all edges which correspond to the assignment $A^{\ast}$ are also added to the network. Thus, a maximum flow of size $m\kappa$ is achieved and hence each assigned (reviewer, paper) pair has similarity at least $s^{\ast}_{\kappa}$.

Recalling that $s^{\ast}_{\infty}$ is the lowest similarity in similarity matrix $S$, one can deduce that $\Gamma^{S}_{f}\left(A_{\kappa}\right)\geq\kappa f(s^{\ast}_{\kappa})+\left(\lambda-\kappa\right)f(s^{\ast}_{\infty})$ due to the monotonicity of $f$. Consequently, we have

for all $\kappa\in[\lambda]$. Taking a maximum over all values of $\kappa\in[\lambda]$ concludes the proof.

Upper bound for the optimal assignment $A^{\text{HARD}}_{f}$.

Consider any value of $\kappa\in[\lambda]$. By definition (6) of $s^{\ast}_{\kappa}$, for any feasible assignment $A\in\mathcal{A}$, there exists some paper $j_{\kappa}^{\ast}\in[m]$ for which at most $(\kappa-1)$ reviewers have similarity strictly greater than $s^{\ast}_{\kappa}$. Let us now consider assignment $A^{\text{HARD}}_{f}$ and corresponding paper $j_{\kappa}^{\ast}$. This paper is assigned to at most $(\kappa-1)$ reviewers with similarity greater than $s^{\ast}_{\kappa}$ and to at least $(\lambda-\kappa+1)$ reviewers with similarity smaller or equal to $s^{\ast}_{\kappa}$. Recalling that $s^{\ast}_{0}$ is the largest possible similarity, we conclude that due to monotonicity of $f$, the following upper bound holds:

Taking a minimum over all values of $\kappa\in[\lambda]$, then yields an upper bound on the fairness of $A^{\text{HARD}}_{f}$.

Putting it together. To conclude the argument, it remains to plug in the obtained bounds (23) and (24) into ratio $\frac{\Gamma^{S}_{f}\left(A^{\text{PR4A}}_{f}\right)}{\Gamma^{S}_{f}\left(A^{\text{HARD}}_{f}\right)}$:

Setting $\kappa=1$ in both numerator and denominator and recalling that $f(s)\geq 0\ \forall s\in$, we obtain a worst-case approximation in terms of required paper load: $\frac{\Gamma^{S}\left(A^{\text{PR4A}}\right)}{\Gamma^{S}\left(A^{\text{HARD}}\right)}\geq\frac{1}{\lambda}$.

2 Proof of Corollary 1

Let us pause the PeerReview4All algorithm at the beginning of the $r^{\text{th}}$ iteration of Steps 2 to 7 and inspect its state.

The set $\mathcal{M}$ consists of papers that are not yet assigned:

The vector of reviewers’ loads $\overline{\mu}$ is adjusted with respect to assigned papers. For every reviewer $i\in[n]$, we have: