A SUPER* Algorithm to Optimize Paper Bidding in Peer Review

Introduction

It is well known that peer review is essential for ensuring the quality and scientific value of research (Black et al., 1998; Thurner and Hanel, 2011; Bianchi and Squazzoni, 2015). A fundamental challenge in peer review is matching or assigning papers to qualified and willing reviewers. Common methods to deal with this problem often rely on access to a similarity matrix containing scores for each paper-reviewer pair expressing the estimated match quality between them. The similarity matrix is often obtained using feature-based or profile-based matching mechanisms that leverage keywords and available reviewer publications (Charlin and Zemel, 2013; Price and Flach, 2017). A number of automated methods to match papers with reviewers using similarity scores have been proposed that optimize objectives such as cumulative similarity or fairness notions (Karimzadehgan et al., 2008; Garg et al., 2010; Tang et al., 2010; Long et al., 2013; Stelmakh et al., 2019b).

A shortcoming of automating the paper matching process stems from the failure to actively incorporate reviewers within the paper assignment phase of the review process. The outright dependence on the similarity scores can be problematic since the preferences of reviewers can change frequently and the similarity scores themselves can be noisy. Bidding has emerged as an important mechanism for aiding in and improving the peer review process under the guise that active engagement of the reviewer leads to assignments more aligned with their preferences and hence, enhanced review quality (Di Mauro et al., 2005).

In typical peer review process, when the bidding process opens, reviewers enter the system in an arbitrary sequential order. Upon entering, a list of papers is shown to them and they are asked to place bids on papers they would prefer to review. Following the bidding process, bids can be incorporated into the reviewer-paper assignment mechanism. It is known that the order of papers presented to reviewers in the bidding stage can greatly impact the number of bids that a paper receives (Cabanac and Preuss, 2013). From the perspective of the platform, there are two competing goals: (i) ensure that each paper has a sufficient number of bids, and (ii) ensure individual reviewer satisfaction by showing relevant papers.

With regard to goal (i), the platform aims to select a display order for each reviewer such that at the end of the bidding process, each paper has at least a certain number of bids. The main objective of ensuring a minimum number of bids on each paper is to improve review quality for all papers (Shah et al., 2018b). The well-documented primacy effect (Murphy et al., 2006) suggests that papers shown on top of the ordering are the ones on which reviewers are more likely to bid. Consequently, this objective strongly suggests that papers with few bids should be placed higher in the list. Indeed, Cabanac and Preuss (2013) make the following remark:

“It is advised to counterbalance order effects during the bidding phase of peer review by promoting the submissions with fewer bids to potential referees. This manipulation intends to better share bids out among submissions in order to attract qualified referees for all submissions. ”

With regard to goal (ii), the platform aims to display ‘well-matched’ papers to each reviewer. That is, the set of papers to be displayed is composed of papers on which the reviewer is most likely to bid. There are several reasons to select well-matched papers. It is generally assumed that reviewers are more likely to place bids on papers they are qualified to review (Rodriguez et al., 2007). Furthermore, reviewers that place positive bids on papers are more likely to give a review with high confidence and voice sharp opinions of acceptance or rejection that help guide final decisions on papers (Cabanac and Preuss, 2013). A number of comprehensive surveys also indicate that a primary motivation of reviewers is the ability to help and contribute to the work of colleagues (Mulligan et al., 2013; Ware, 2008). Failing to display relevant papers to reviewers can result in several unintended negative consequences. If irrelevant papers are shown early in the order to a reviewer, it may cause the reviewer to opt-out and disengage with the system even if further down the list there was an option that they would have happily bid on. Similarly, a poorly selected ordering may result in significantly fewer bids from a reviewer.

Competing objectives of this form are not unique to peer review systems and they appear in a number of applications. A fitting example is an intermediary between distinct user groups that seeks to facilitate interactions and satisfy each party. For example, in online labor markets, the platform must ensure each job obtains a sufficient number of applicants and that workers are presented with tasks they are qualified enough for to be considered. Similarly, in online e-commerce marketplaces, as the platform decides how to show products to users, there is a definite trade-off between satisfying merchants offering products that need to be sold and users that want to be shown relevant items. In this paper, we maintain peer review as a running example and comment further on relevant applications of our work in a concluding discussion section.

In peer review, it is recognized that actively engaging reviewers in the paper assignment process via bidding can greatly improve the review process. If administered inadequately, bidding can in fact have a significant negative impact on the quality of the review process. In the words of Rodriguez et al. (2007),

“Since bidding is the preliminary component of the manuscript-to-referee matching algorithm, sloppy bidding can have dramatic effects on which referees actually review which submissions.”

A study on the 2016 Neural Information Processing Systems (NeurIPS) conference revealed the distribution of bids arising from a typical bidding process leaves significant challenges to match papers with reviewers (Shah et al., 2018b). It was observed that a considerable number of reviewers do not place a sufficient number of bids and papers commonly fail to obtain as many bids as the number of reviewers needed. This phenomenon is detailed in Shah et al. (2018b) amongst the 3,200 reviewers and 2,400 papers.

“Moreover, there are 148 reviewers with no (positive or negative) bids and 1201 reviewers with at most 2 positive bids… We thus observe that a large number of reviewers do not even provide positive bids amounting to the number of papers they would review. As a consequence of the low number of bids by reviewers, we are left with 278 papers with at most 2 positive bids and 816 papers with at most 5 positive bids… There is thus a significant fraction of papers with fewer positive bids than the number of requisite reviewers.”

The study also found that there were 1090 papers with no positive bids from the area chairs. The inability to elicit meaningful bidding information in NeurIPS is far from an aberration. In a study of the 2005 Joint Conference on Digital Libraries, 146 out of the 264 submissions did not obtain any bids (Rodriguez et al., 2007). The shortfalls of existing bidding systems shift the onus of the reviewing assignments away from the participants and to the paper matching mechanisms.

Despite the importance of the bidding process in peer review, there is not yet much fundamental research on the problem of optimizing the display order during the bidding process, and much less so in consideration of the two objectives identified in this paper. In practice, the display order is typically determined via heuristics such as a fixed ordering (e.g., order of submission), or in decreasing order of the relevance of the papers to that reviewer, or in increasing order of the number of bids received by the paper until then.

A key reason that bidding can fail is that papers are suboptimally displayed to the reviewers. Consider a paper that is not an ideal match for any reviewer in the system. If papers are ranked for display simply by how well-matched they are to reviewers, this particular paper may be shown far down in the ranking for each reviewer and hence, not receive many, if any, bids. The risk of this scenario is elevated for interdisciplinary research, which is know to face significant impediments as a consequence of the lack of ideally matched peers (Travis and Collins, 1991; Porter and Rossini, 1985).

On the other hand, if papers are inversely ranked by the number of bids they have obtained, then papers with fewer bids are more likely to be shown higher on the list regardless of how well-matched they are to any particular reviewer. This display order may cause reviewer dissatisfaction, which in the worst case could result in zero bids. Similarly, ordering heuristics that are based on a fixed baseline may lead to bias in the review process. Indeed, in the report of a study of $42$ peer-reviewed conferences in Computer Science, it was observed that under a fixed ordering (based on the submission time), the number of bids on papers is heavily influenced by the order of submission times of the papers (Cabanac and Preuss, 2013). It was concluded that the later the paper is submitted, the fewer bids it will receive.

Given the flaws of existing peer review bidding systems, we study the important problem of selecting the ordering of papers to display to each arriving reviewer in a principled manner.

The key contributions of this paper are summarized as follows.

The bidding process is highly consequential, yet one of the most understudied components of the conference peer-review process. We identify a key source of unfairness and inefficiency in the bidding process, and develop principled methods to address it. A key challenge is suitably formalizing the peer review bidding process, for which to the best of our knowledge there are no prior formulations. We formulate an objective function that captures the competing goals of the platform while reflecting the underlying decision-making process of reviewers. The framework developed in this paper to analyze the problem is an important step toward future improvements on bidding systems.

We present a sequential decision-making algorithm called SUPER∗ to address this problem. The algorithm takes as input the “similarities” between each reviewer-paper pair and the bids made by all past reviewers, and outputs the ordering of papers to show to any current reviewer.

We show two sets of theoretical results. We first consider a notion of ‘local’ performance: the performance with respect to a single reviewer. We prove that SUPER∗ is locally optimal whereas all popular baselines are considerably suboptimal. Our second set of theoretical results are based on a community model, where we prove that SUPER∗ is near-optimal (globally) and all popular baselines are considerably suboptimal.

We run extensive experiments using similarity scores from ICLR 2018 and on synthetic data. The experiments reveal that the SUPER∗ algorithm outperforms all popular baselines. For instance, it consistently reduces the number of papers with fewer than requisite bids by 50-75% while maintaining individual reviewer satisfaction. In addition, we see that SUPER∗ is very robust to model mismatches and complexities of the real-world review process.

The code for the algorithm is available at github.com/fiezt/Peer-Review-Bidding.

2 Related Work

The paper ordering problem for the bidding process in peer review bears a strong resemblance to the learning to rank problem (Singh and Joachims, 2019; Yadav et al., 2019; Svore et al., 2011; Momma et al., 2019; Aslanyan and Porwal, 2019; Cao et al., 2007). Typically, the goal of learning to rank is to learn an overall ranking of items via supervised methods or by querying users, where the latter provides further information on the relative ranking of items. In peer review, the objective of finding a ranking most suitable for an arriving reviewer during the bidding process is analogous to learning to rank methods that consider the utility of rankings for users along with the impact on the items being ranked (Singh and Joachims, 2019; Yadav et al., 2019). Moreover, the bidding model considered in this work is motivated from that which is commonly adopted in learning to rank models (Aslanyan and Porwal, 2019).

As formulated in this paper, the goal for the design of the bidding process in peer review is to optimize for multiple criteria reflecting the objectives of the reviewers and the papers, respectively. This is not unlike the methods of Singh and Joachims (2019) and Yadav et al. (2019), which consider a fairness objective in combination with a ranking quality objective, or the multi-objective learning to rank problems studied by Svore et al. (2011) and Momma et al. (2019). In the works of Singh and Joachims (2019) and Yadav et al. (2019), the objective of ensuring fairness is encoded as a constraint in the optimization problems. Similarly, Svore et al. (2011) optimize a linear combination of ranking measures referred to as a ‘graded measure’ and Momma et al. (2019) convert a constrained optimization problem into an unconstrained problem by penalizing constraint violations in the objective. In each of the aforementioned works, the ranking measures are separable in the arriving users, meaning that the contribution of any individual user to the overall objective is independent of the other users.

The problem of paper ordering in peer review given multiple objectives is also abstractly similar to online recommendation systems similarly facing competing objectives (Rodriguez et al., 2012; Agarwal et al., 2011; Jambor and Wang, 2010). However, a prevailing approach is to convert the multi-objective problem to a constrained optimization problem (Rodriguez et al., 2012; Jambor and Wang, 2010). Both the approach of incorporating objectives as constraints in the optimization problem formulations and combining objectives in a linear fashion is considered by Agarwal et al. (2011). Analogous to the learning to rank problem, the objectives are separable in the users.

The objective in the peer review problem as formulated in this paper presents unique challenges not addressed in the aforementioned works on learning to rank and recommendation systems. Notably, it is not separable between the reviewers since it depends on the number of bids on each paper after each reviewer has arrived and placed bids on the papers. Being applicable to more general multi-criteria settings, our approach to the design of the bidding processes in peer review may also be applied to the learning to rank problem. This is a direction worthy of further study.

Our work also contributes to a growing literature on improving various aspects of the peer review process such as reviewer assignment (Charlin and Zemel, 2013; Garg et al., 2010; Lian et al., 2018; Stelmakh et al., 2019b; Kobren et al., 2019), biases (Tomkins et al., 2017; Stelmakh et al., 2019a), subjectivity (Noothigattu et al., 2018), miscalibration (Roos et al., 2012; Wang and Shah, 2019), strategic behavior (Aziz et al., 2019; Xu et al., 2019), and others (Church, 2005; Wing, 2011; Lawrence and Cortes, 2014; Shah et al., 2018a; Kang et al., 2018; Jecmen et al., 2020; Ding et al., 2020; Stelmakh et al., 2020a, b). The present paper addresses the bidding process in conference peer review, which has largely been unexplored in past literature. The concurrent work of Meir et al. (2020), which appeared after an initial workshop version of our work (Fiez et al., 2019), is the only work besides our own that we are aware of to focus on methods for improving bidding in peer review. However, their approach is to design a market for bidding, which is entirely different from ours.

Problem Formulation

Consider $d\geq 2$ papers and $n\geq 2$ reviewers indexed as $\{1,\ldots,d\}$ and $\{1,\ldots,n\}$ respectively.Henceforth, for any positive integer $\kappa$, we will use the standard shorthand $[\kappa]$ to denote the set $\{1,\ldots,\kappa\}$. For each reviewer-paper pair, we have access to a similarity score that captures the similarity between the reviewer and the paper. We use the notation $S_{i,j}\in$ to denote the given similarity between any reviewer $i\in[n]$ and paper $j\in[d]$. A higher similarity score indicates a greater relevance of the paper to that reviewer. There are several systems in use today that compute similarities (Price et al., 2010; Charlin and Zemel, 2013), and in our work, we treat them as being given.

In the bidding period, reviewers sequentially arrive into the system and place bids on the papers. In our work, for any reviewer and paper, we only consider the existence of a bid or not, and do not consider the possibility of multiple bidding options. We assume for simplicity that all $n$ reviewers arrive exactly once, and that a reviewer arrives after the previous reviewer has completed their bidding.However, in Section 5.1, we show that our algorithm is empirically robust to violations of these assumptions. We do not make any assumptions on the arrival order of the reviewers. The problem is to determine the ordering of papers to show each reviewer on arrival in the interest of influencing the papers they decide to bid on while ensuring individual satisfaction. When deciding the paper ordering for any reviewer, the bids made by all reviewers who arrived in the past along with the paper orderings presented to them are known, but the bids made by the current or future reviewers are unknown. Let $\Pi_{d}$ denote the set of all possible $d!$ permutations of the $d$ papers. In what follows, for any reviewer $i\in[n]$, we let $\pi_{i}\in\Pi_{d}$ denote the ordering (permutation) of the papers shown to reviewer $i$. We also use the notation $\pi_{i}(j)$ to denote the position of paper $j\in[d]$ in the ordering $\pi_{i}$.

Any algorithm to determine the ordering of papers must trade-off between two competing objectives: ensuring each paper receives a sufficient number of bids and ensuring each reviewer gets to see relevant papers early in the ordering. A combination of the objectives comprise our “gain function,” which is the objective we aim to optimize. We begin by discussing each objective component.

where $g_{j}$ is the number of bids received by paper $j\in[d]$. We assume the function $\gamma_{p}$ is non-decreasing and concave. The non-decreasing property represents an improved gain if there are more bids, and the concavity property captures diminishing returns.Our algorithm easily adapts to paper-side gains that may also be a function of the similarity scores of the reviewers who bid; for example, a higher gain for bids from expert reviewers. We omit this detail for sake of brevity. An example of a choice for the paper-side gain is the square-root function $\gamma_{p}(x)=\sqrt{x}$. This function is increasing, smooth, and captures the diminishing returns property. The reader may keep this function in mind as a running example for concreteness. A second example is $\gamma_{p}(x)=\min\{x,r\}$ for a given parameter $r\geq 1$, which emphasizes having at least $r$ bids per paper.

The function $\gamma_{r}$ is assumed to be non-increasing in the position (its first argument) and non-decreasing in the similarity (its second argument). One example choice of this function, which the reader may choose to keep in mind as a running example, is the Discounted Cumulative Gain or DCG used commonly in data mining (Järvelin and Kekäläinen, 2000). In our setting, the function is given by

where we have set the “relevance” parameter in DCG to be the similarity $S_{i,j}$.

Overall gain function: Finally, we assume there is a trade-off parameter $\lambda\geq 0$, chosen by the program chairs, which trades off between these two objectives so that the overall gain function is given by

An important aspect of any system that displays a list to users is the presence of primacy effects. In the context of our problem, the primacy effect means a reviewer is more likely to bid on a paper shown at the top of the list rather than later (Murphy et al., 2006). A second aspect of bidding is that a reviewer is more likely to bid on papers with greater similarity, although the reviewer may not bid on exactly the papers with the highest similarity since the similarities are noisy representations of their reviewing interests.

Thus in order to model reviewer bidding, we revert to literature on position-based click models that have a nearly identical setting (where clicks are analogous to our bids). We model the bidding via a given function $f:[d]\times\rightarrow$, where $f(\pi_{i}(j),S_{i,j})$ is non-increasing in the position that a paper is shown (the first argument) and non-decreasing in the similarity score (the second argument). Any reviewer $i\in[n]$ bids on paper $j\in[d]$ independently with probability

As a running example throughout the paper, note that in position-based click models, the click probability decomposes into a product of relevance and position bias (Chuklin et al., 2015). Moreover, the literature considers the click probability to decay logarithmically as a function of the position (Aslanyan and Porwal, 2019). The translation of these models into our setting gives rise to the example bidding function

We consider the following three methods of ordering papers as baselines.

Random baseline (RAND): A commonplace practice (Cabanac and Preuss, 2013) is to show papers to reviewers in some fixed order, such as in order of submission of the papers. As a baseline, we consider a better variant of this practice, in which each reviewer is shown an independently and randomly selected paper ordering.

Similarity baseline (SIM): A second common practice, followed in several conference management systems today, is to order the papers according to their similarities. In other words, any reviewer $i\in[n]$ is shown the papers in order of the values in $\{S_{i,j}\}_{j\in[d]}$ (where the paper with maximum similarity is shown at the top, and so on). Any ties are broken by showing papers with fewer bids higher, and further ties are broken uniformly at random.

Bid baseline (BID): A third baseline shows papers to greedily optimize the minimum bid count. Each reviewer is shown papers in increasing order of the number of bids received so far (from the reviewers who arrived previously). Any ties are broken in favor of the paper with a higher similarity, and further ties are broken uniformly at random.

Algorithm

The key challenge in designing a suitable algorithm for the problem at hand stems from the fact that the paper-side gain is coupled (non-separable) across the orderings of papers presented to all reviewers so the impact of each individual paper ordering cannot be fully realized until the entire bidding process is complete. Conversely, the reviewer-side gain is decoupled (separable) across reviewers. This means the reviewer-side gain that can be obtained from any given reviewer is independent of the ordering of papers presented to any other reviewer. Thus, an algorithm for this problem is required to make local decisions, where the effect of the decision on the global gain (or cost) is only partially known. This perspective is reminiscent of the classical A∗ algorithm (Hart et al., 1968), and using A∗ as an inspiration, we now present an algorithm which we call SUPER∗ for our problemThe name SUPER∗ stands for SUperior PERmutations and also indicates the inspiration from A∗..

The A∗ algorithm operates with a goal of finding the minimum cost path between a pair of vertices in a cost-weighted graph. For any node in consideration, it considers two functions: a function which captures the cost so far and a second function—called the “heuristic”—which captures some estimate of the cost from the current node to the destination. The A∗ algorithm then finds a path based on these two functions. Before moving to a description of SUPER∗, we discuss such a heuristic in the context of the problem at hand.

In a manner analogous to the A∗ algorithm, at any point in time SUPER∗ keeps track of the gains so far and also takes as input a heuristic that captures the “unseen” events. The heuristic in A∗ provides, for every vertex in the given graph, an estimate of the cost incurred in the future. Analogously, the heuristic in SUPER∗ provides, for every arrival of a reviewer, an estimate of the number of bids each paper will receive in the future. Formally, let us index the reviewers as $i\in[n]$ in the order of arrival (note that this order is unknown a priori). The heuristic comprises a collection of vectors $\{h_{1},\ldots,h_{n}\}$, where each $h_{i}\in[0,n-i]^{d}$ represents an estimate of the number of bids each of the $d$ papers will receive from all future reviewers $\{i+1,\ldots,n\}$. The vector $h_{i}$ is provided to the SUPER∗ algorithm on arrival of the $i^{th}$ reviewer. Two examples of heuristic functions that we consider in the subsequent narrative are described as follows.

Zero heuristic: $h_{i}=0$ for every $i\in[n]$.

Mean heuristic: This function computes the expected number of bids each paper will receive if the permutations shown to all future reviewers are chosen independently and uniformly at random. Formally: $h_{i,j}=\frac{1}{d}\sum_{i^{\prime}=i+1}^{n}\sum_{j^{\prime}\in[d]}f(j^{\prime},S_{i^{\prime},j})$ $\forall\ i\in[n-1],j\in[d]$.

We set $h_{n}=0$ for any heuristic, implying there are no bids placed after the last reviewer. This is analogous to setting the heuristic value to zero for the target vertex in the A∗ algorithm.

2 Intuition Behind the Algorithm

We first provide some intuition about the SUPER∗ algorithm, and subsequently present a formal description. Since a primary impediment to designing an algorithm is the inability to fully realize the impact of a paper ordering on the paper-side gain until the end of the bidding process, we begin by considering the scenario where $(n-1)$ reviewers have already departed, and the problem is to determine the ordering of papers to show the final reviewer. In this scenario, we have access to the bids of all $(n-1)$ reviewers that have already arrived and the orderings of papers presented to them. We use the notation $g_{n-1,j}\in\{0,\ldots,n-1\}$ to denote the number of bids received by any paper $j\in[d]$ at the time of arrival of the last reviewer. The values $\{g_{n-1,1},\ldots,g_{n-1,d}\}$ are thus known at the time when the final reviewer arrives. As a result, we can formulate an optimization problem for the final reviewer $n$ to maximize the expected gain from (2) in the following manner. For every $j\in[d]$, let $\mathcal{B}_{n,j}$ denote a Bernoulli random variable with mean $p_{i,j}=f(\pi_{n}(j),S_{n,j})$, independent of all else. The random variable $\mathcal{B}_{n,j}$ represents the bid of the final reviewer on paper $j\in[d]$. The optimization problem can be written as

where the expectation is taken over the distribution of the random variables $\mathcal{B}_{n,1},\ldots,\mathcal{B}_{n,d}$.

Observe that the constraint set for the optimization problem in (4) is the set $\Pi_{d}$ of all permutations. This set is, in general, not very well behaved (Ailon et al., 2008; Shah et al., 2016), which makes even this one-step optimization a challenge. As we discuss later in the formal algorithm description along with Theorem 1 and its proof, SUPER∗ for the final reviewer optimally solves (4) and it is computationally efficient manner (see Proposition 1 in Appendix B.1). The aforementioned subproblem forms the starting point for the SUPER∗ algorithm. Now that we know to handle a single (last) reviewer in an optimal fashion, we now describe the SUPER∗ algorithm for a general reviewer, say, $i\in[n]$. When reviewer $i$ arrives, we have access to the number of bids made by all past reviewers on any paper $j\in[d]$, which we denote by $g_{i-1,j}\in\{0,\ldots,i-1\}$.

We now recall the A∗ algorithm: for any vertex, A∗ considers the cost “$g$” so far and a heuristic estimate “$h$” of the subsequent cost. Then, considering the cost of any vertex as “$g+h$”, the A∗ algorithm takes the one-step optimal action given by selecting the neighboring vertex with the smallest value of “$g+h$”. In an analogous fashion, SUPER∗ considers the number of bids so far ($g_{i-1}$) and takes as input a heuristic ($h_{i}$) for the number of bids in the future. Then, considering the number of bids from all other reviewers as “$g_{i-1}+h_{i}$”, the SUPER∗ algorithm takes the action which is the one-step optimal action. In other words, SUPER∗ solves for each paper ordering using:

where $\mathcal{B}_{i,j}$ is a Bernoulli random variable with mean $p_{i,j}=f(\pi_{i}(j),S_{i,j})$ and is independent of all else. As for the final reviewer, SUPER∗ solves this problem in an efficient manner for any arbitrary reviewer (see Proposition 1 in Appendix B.1).

3 Formal Algorithm Description

The SUPER∗ algorithm is presented in Algorithm 3.2. To determine a paper ordering to show any reviewer, SUPER∗ calls a procedure to efficiently solve (5). We give a general method in Algorithm 3.2 and a faster method in Algorithm 3.2 that is applicable for a special class of reviewer-side gain and bidding functions.

In the general version of SUPER∗, Algorithm 3.2 is called to return a paper ordering that is a solution to (5) each time a reviewer arrives. In the proof of Theorem 1, we show that the optimization problem over the set of permutations given in (4) to find the optimal paper ordering for the final reviewer can be reformulated as an integer linear programming problem with a totally unimodular constraint set. The totally unimodular property of the constraint set guarantees that the solution of a relaxed linear program is in fact the integer optimal solution. The application of this reduction from an optimization problem over permutations to a linear programming problem for any given reviewer forms the technique given in Algorithm 3.2 to efficiently obtain a solution to (5). Finally, the per-reviewer time complexity of the general version of SUPER∗ given the evaluations of the heuristic is $\mathcal{O}(d^{3})$ (see Proposition 1 in Appendix B.1) as a consequence of the call to solve a linear assignment problem in Algorithm 3.2.

for some non-negative weights $\{\alpha_{n,j}\}_{j\in[d]}$. The problem in (6) admits a simple solution: $f^{\pi}$ is non-increasing on the domain, so the objective is maximized by presenting papers in decreasing order of the weights $\{\alpha_{n,j}\}_{j\in[d]}$. Obtaining this solution only requires sorting the weights, which has a time complexity of $\mathcal{O}(d\log(d))$. The application of this problem reformulation for the given model class and any reviewer forms the technique given in Algorithm 3.2 to obtain a solution to (5).

Before moving on to present our theoretical results, we comment on the relevance of this model class. Importantly, the DCG reviewer-side gain function and bidding model $f(S_{i,j},\pi_{i}(j))=S_{i,j}/\log_{2}(\pi_{i}(j)+1)$, which we have mentioned as running examples that can be kept in mind, satisfy the decomposition for which SUPER∗ is computationally efficient. This choice of functions is standard in the past literature on ranking models and click behavior (Järvelin and Kekäläinen, 2000; Aslanyan and Porwal, 2019), meaning that the time complexity result for this model class is quite relevant.

Theoretical Results

We now present the main theoretical results of this paper. Complete proofs of all results are in Appendix A.

The property of local optimality, as the name suggests, means that the algorithm is optimal with respect to the reviewer under consideration. Achieving even a good local performance in a computationally efficient manner is challenging due to the optimization over permutations in (4). The following results show that SUPER∗, which is computationally efficient, is locally optimal.

The result is first presented in terms of the final reviewer for simplicity and extended to a general reviewer subsequently. In the following theorem, since we consider only the final reviewer, note that the heuristic for SUPER∗ is irrelevant because the heuristic value for the final reviewer is always set to zero.

Given any history of paper orderings and bids from reviewers that arrived previously, the paper ordering given by SUPER∗ to the final reviewer maximizes the expected gain conditioned on the history.

In other words, the expected amount by which the gain is increased from the final reviewer is maximized. To generalize the previous result to a local optimality result for any reviewer, let the immediate gain from a reviewer be defined as the difference between the gain after and before the reviewer arrived.

Given any history of paper orderings and bids from reviewers that arrived previously, the paper ordering given to any reviewer by SUPER∗ with zero heuristic maximizes the expected immediate gain from that reviewer conditioned on the history.

The property of local optimality also implies optimality of SUPER∗ (with any heuristic) when the paper-side gain function is linear. We refer the reader to Appendix B.2 for more details.

We now show that an analogous statement cannot be made regarding the other baseline methods. In fact, in contrast to SUPER∗, all the popular baselines are considerably suboptimal.

Consider a model with the paper-side gain function $\gamma_{p}(g_{j})=\sqrt{g_{j}}$, the reviewer-side gain function $\gamma_{r}(\pi_{i}(j),S_{i,j})=(2^{S_{i,j}}-1)/\log_{2}(\pi_{i}(j)+1)$, and the bidding function $f(\pi_{i}(j),S_{i,j})=S_{i,j}/\log_{2}(\pi_{i}(j)+1)$. There exists a constant $c>0$ such that for every $d\geq 2$ and $\lambda\geq 0$, in the worst case for the final reviewer: (a) SIM is suboptimal by an additive factor of at least $cd/\log_{2}^{2}(d)$; (b) BID is suboptimal by an additive factor of at least $cd\max\{1,\lambda\}/\log_{2}^{2}(d)$; (c) RAND is suboptimal by an additive factor of at least $cd\max\{1,\lambda\}/\log_{2}^{2}(d)$.

Theorems 1 and 2 in tandem show that SUPER∗ not only is locally optimal but can outperform currently popular algorithms by a wide margin.

2 Global Optimality Under a Community Model

We now transition to consider the global performance of the algorithms. Given our focus on the application of peer review, we are motivated to give guarantees on the performance of SUPER∗ for similarity matrix classes that would be encountered in a real conference.

A common characteristic of networks is community structure (Newman and Girvan, 2004; Porter et al., 2009), where nodes can be grouped into clusters and links between groups are not as common. This phenomena has been documented in social and biological networks among others (Girvan and Newman, 2002). Pertinent to this work, empirical investigations have revealed community structures in scientific collaboration networks (Newman, 2001). Given this close connection, and the fact that scientific research is highly specialized, it is intuitive that communities exist in major conferences pertaining to different subtopics.

We explore the possible existence of such structure in the ICLR 2018 similarity matrix that was reconstructed by Xu et al. (2019) and is of size $n=2435$ and $d=935$. Recall that the ICLR similarity matrix is of size $(2435\times 935)$. To begin, we investigate the spectral properties of the similarity matrix from ICLR 2018, and in particular, whether it is low rank. We plot the singular values of the similarity matrix in Figure 1a, where the (heuristic) elbow method suggests a low rank ($\approx 10$). In Figure 1b we plot the entries of the similarity matrix after permuting its rows and columns according to the spectral co-clustering algorithm (Dhillon, 2001). The result suggests the ICLR 2018 similarity matrix exhibits some characteristics of a noisy block diagonal structure.

In what follows, we now perform an associated theoretical analysis of the algorithms under such community structures of the similarity matrix. We begin by proposing a simple model which we call the ‘noiseless community model’.

Informally, the noiseless community model we study is a set of similarity matrices that up to a permutation of rows and columns belong to a subclass of block diagonal matrices. Formally, let $\mathbf{0}_{q\times q}$ and $\mathbf{1}_{q\times q}$ denote $q\times q$ matrices of all zeros and all ones respectively. Define an $mq\times mq$ block diagonal matrix $B$ as:

Finally, denote by $\mathcal{P}_{mq\times mq}$ the set of all $mq\times mq$ permutation matrices. Recall that a permutation matrix is a matrix obtained by permuting the rows of an identity matrix. Also recall that left multiplying a matrix by a permutation matrix permutes the rows of the matrix and right multiplying a matrix by a permutation matrix permutes the columns of the matrix. With this background, the noiseless community model is defined as the following set of similarity matrices for $m\geq 2$ and $q\geq 2$:

The number of reviewers is given by $n=mq$ and the number of papers is by $d=mq$. In words, this is the set of all similarity matrices obtained via a permutation of the rows and columns of the block matrix $B$.

We begin our theoretical results for this section by showing that under the noiseless community formulation, both SUPER∗ and SIM are optimal, whereas BID and RAND fare poorly. Recall that $d=n=mq$ in the noiseless community model.

Consider a model with a paper-side gain function $\gamma_{p}(g_{j})=\sqrt{g_{j}}$, the reviewer-side gain function $\gamma_{r}(\pi_{i}(j),S_{i,j})=(2^{S_{i,j}}-1)/\log_{2}(\pi_{i}(j)+1)$, and the bidding function $f(\pi_{i}(j),S_{i,j})=\mathds{1}\{\pi_{i}(j)=1\}\mathds{1}\{S_{i,j}>s/2\}$. Then, under the noiseless community model from (7), for all $m\geq 2$, $q\geq 2$ and $\lambda\geq 0$: (a) SUPER∗ with zero heuristic is optimal; (b) SIM is optimal. In contrast, there exists a constant $c>0$ such that for every $m\geq 2$, $q\geq 2$ and $\lambda\geq 0$: (c) BID is suboptimal by an additive factor of at least $c\lambda d/\log_{2}^{2}(d)$; (d) RAND is suboptimal by an additive factor of at least $cd$.

Although SIM is optimal in the noiseless community model, this optimality turns out to be quite brittle. As we show below, even an infinitesimally small amount of noise makes SIM considerably suboptimal. In contrast, SUPER∗ is robust enough and suffers by only a small amount.

More formally, we first define a ‘noisy community model’. Under this model, we assume that the similarity matrix is generated by first selecting any similarity matrix $S^{\prime}$ from the noiseless community model defined in (7), and then adding noise to its entries as:

where $\nu_{i,j}$ is drawn independently and uniformly from $(0,\xi)$ for each reviewer-paper pair, for some small value $\xi$ to be defined subsequently.

The next result shows that even under an arbitrarily small perturbation $\xi$ from a noiseless community model, the baselines become significantly suboptimal. In contrast, SUPER∗ is robust to the noise and is near-optimal. Recall that $d=n=mq$ in the noisy community model.

Consider the gain and bidding functions from Theorem 3 and the noisy community model given in (8) with any noise bound satisfying $\xi\leq(1+\lambda)^{-1}e^{-emq}$. Then, for all $m\geq 2$, $q\geq 2$, and $\lambda\geq 0$: (a) SUPER∗ with zero heuristic is within at least an additive factor of $0.0001$ of the optimal. Moreover, there exists a constant $c>0$ such that for every $m\geq 2$, $q\geq 2$, and $\lambda\geq 0$, with respect to SUPER∗ with zero heuristic: (b) SIM is suboptimal by an additive factor of at least $cd$; (c) BID is suboptimal by an additive factor of at least $c\lambda d/\log_{2}^{2}(d)$; (d) RAND is suboptimal by an additive factor of at least $cd$.

This result thus establishes the global optimality of the proposed SUPER∗ algorithm under the community model, while in contrast all popular baselines are considerably suboptimal.

Experimental Results

We now empirically evaluate SUPER∗ (with zero and mean heuristics) and compare it with the baselines SIM, BID, and RAND (discussed earlier in Section 2). The experimentation methodology is as follows for any chosen set of model parameters including the gain functions, bidding probability, trade-off parameter, and number of reviewers and papers. Given a fixed similarity matrix, we shuffle the rows of the matrix to randomize the sequence of reviewer arrivals and simulate each of the algorithms. Then, for each algorithm, we record the gain along with the number of papers that end up with bid counts in the intervals $\{0,1,2\}$, $\{3,4,5\},\{6,7,8\}$, and $\{9+\}$. We repeat this process 20 times for a given similarity matrix if it is fixed and draw a similarity matrix at random for each run if the score structure being simulated is a distribution. To evaluate performance, we show the means of the relative gains (additive gains relative to the gain of a baseline) across the runs and include error bars representing the standard error of the mean. Moreover, we present the mean number of papers across the repeated simulations that finish with bid counts in each of the previously given bid count intervals. The code and data to reproduce each of the experiments is available at github.com/fiezt/Peer-Review-Bidding.

To begin our experiments, we perform evaluations on a similarity matrix from the ICLR 2018 conference discussed earlier in Section 4. Recall that the similarity matrix consists of $n=2435$ reviewers and $d=935$ papers. In the following experiments, we run a simulation using a default model configuration, then we explore the impact of changing components of the model, and we finish by exploring the robustness of the algorithm to various real-world complexities.

We begin by evaluating a default model configuration that is considered throughout the the remainder of the experiments unless otherwise specified. The model consists of the paper-side gain function $\gamma_{p}(g_{j})=\min\{g_{j},6\}$, the reviewer-side gain function $\gamma_{r}(\pi_{i}(j),S_{i,j})=(2^{S_{i,j}}-1)/\log_{2}(\pi_{i}(j)+1)$, and the bidding probability model $f(\pi_{i}(j),S_{i,j})=S_{i,j}/\log_{2}(\pi_{i}(j)+1)$. We remark that the paper-side gain function is a natural choice given that conferences often assign three reviewers to each paper and as such they may seek twice the number of bids per paper. Moreover, recall that for this pair of reviewer-side gain and bidding functions, the efficient routine in Algorithm 3.2 can be called in place of Algorithm 3.2 in SUPER∗ to retrieve a paper ordering, which is what we implement.

The results of the experiment are presented in Figure 2. In Figures 2a–2b we compare SUPER∗ to each baseline and in Figures 2c–2d we zoom in and only show the results for SUPER∗ and SIM. In terms of the gain results shown in Figures 2a and 2c, each version of SUPER∗ outperforms the baseline algorithms, while BID outperforms SIM when minimal weight $\lambda$ is given to the reviewer-side gain and vice versa when a significant amount of weight $\lambda$ is given to the reviewer-side gain. In Figures 2b and 2d, the distribution of the bid counts obtained for the algorithms are shown with $\lambda=0.8$, which was chosen since this parameter choice gave nearly equal paper-side and weighted reviewer-side gain for RAND. While BID has a similar number of papers with fewer than the minimum number of desired bids as each version of SUPER∗, the gain demonstrates why it is not a generally adopted method. As a result of showing papers of limited relevance early in the paper orderings to elicit bids on papers with few bids, the overall gain is significantly smaller than SIM and SUPER∗ since the reviewer-side gain is worse. The distributions also illustrate that both versions of SUPER∗ end the bidding process with approximately a 60% reduction of the number of papers with fewer than the desired minimum number of bids compared to SIM and RAND.

We now consider variations of the default model consideration. In Figures 3a–3d, results are shown when the paper-side gain function is changed from $\gamma_{p}(g_{j})=\min\{g_{j},6\}$ to $\gamma_{p}(g_{j})=\sqrt{g_{j}}$. In Figures 3a–3b we compare SUPER∗ to each baseline and in Figures 3c–3d we zoom in and only show the results for SUPER∗ and SIM. In Figures 3b and 3d, the distribution of the bid counts obtained for the algorithms are shown with $\lambda=0.4$, which was chosen since this parameter choice gave nearly equal paper-side and weighted reviewer-side gain for RAND. For this model configuration, BID and RAND are significantly suboptimal in terms of the gain. SUPER∗ with the mean heuristic outperforms SIM by a marginal amount in terms of the gain, while SIM outperforms SUPER∗ with the zero heuristic by a marginal amount in terms of the gain. The bid distributions show that each version of SUPER∗ ends the bidding process with a smaller number of papers obtaining fewer than six bids compared to SIM. Compared to the default paper-side gain function, the discrepancy is not as significant since SUPER∗ is optimizing an objective that rewards getting more than five bids per paper even though the returns are diminishing.

In Figures 3a–3d, the default paper-side gain function is considered, but the reviewer-side gain function is changed to $\gamma_{r}(\pi_{i}(j),S_{i,j})=(2^{S_{i,j}}-1)/\sqrt{\pi_{i}(j)}$ and the bidding function is changed to $f(\pi_{i}(j),S_{i,j})=S_{i,j}/\sqrt{\pi_{i}(j)}$. The effect of this change is that the probability of obtaining a bid on a paper from a reviewer decays faster with the position the paper is shown and similarly the reviewer-side gain from a paper diminishes faster as a function of the position the paper is shown to a reviewer. In Figures 3e–3f we compare SUPER∗ to each baseline and in Figures 3g–3h we zoom in and only show the results for SUPER∗ and SIM. In Figures 3f and 3h, the distribution of the bid counts obtained for the algorithms are shown with $\lambda=1.2$, which was chosen since this parameter choice gave nearly equal paper-side and weighted reviewer-side gain for RAND. For this model configuration, each version of SUPER∗ significantly outperforms each of the baselines in terms of the gain. The bid count distributions show SUPER∗ with zero and mean heuristic reduce the number of papers with fewer than three bids by 35% and 60% compared to SIM, respectively. Moreover, both versions of SUPER∗ end up with half as many papers obtaining fewer than six bids compared to BID.

The previous experiments were performed under settings faithful to the model described earlier in Section 2. We now evaluate the robustness of SUPER∗ to the models by evaluating the performance under various vagaries and complexities of real-world peer review. For this set of experiments, we consider that SUPER∗ is optimizing the default model configuration described previously in this section. The results of the following simulations that consider deviations from the model being optimized are given in Figure 4. For each experiment we show the gains of each of the algorithms relative to RAND across a sweep of the parameter $\lambda$ and the bid count distributions for each of algorithms with $\lambda=0.8$ as selected for the default model previously.

We begin looking at model mismatch for the bidding function. In Figures 4a and 4f, the situation is considered in which the actual bids are performed under the bidding function $f(\pi_{i}(j),S_{i,j})=S_{i,j}/\sqrt{\pi_{i}(j)}$, whereas SUPER∗ assumes $f(\pi_{i}(j),S_{i,j})=S_{i,j}/\log_{2}(\pi_{i}(j)+1)$. The results show each version of SUPER∗ is robust to this deviation and outperforms the baselines in terms of the gain. Moreover, SUPER∗ with zero heuristic is especially robust since it is not as dependent on the model of bids as SUPER∗ with mean heuristic. The bid count distributions show that SUPER∗ with mean heuristic reduces the number of papers with fewer than three bids by 85% relative to SIM, and SUPER∗ with zero heuristic reduces the number of papers with fewer than six bids by 50% compared to BID. In Figures 4b and 4g, we consider that the probability of a reviewer bidding on a paper is actually given by $f(\pi_{i}(j),S_{i,j})=(S_{i,j}+\mathcal{N}(0,\sigma^{2}))/\log_{2}(\pi_{i}(j)+1)$ where $\sigma=0.01$ and we remark that the mean of the similarity scores is approximately $0.03$ so the noise magnitude is not insignificant. We clip the noisy bid probabilities to guarantee that they remain in the interval $$. We observe that SUPER∗ is again robust to this model mismatch and outperforms the baselines in terms of the gain and each version ends up reducing the fewer the number of papers having below the minimum desired number of bids by approximately 60% compared to SIM and RAND.

In practice, not all reviewers may participate in the bidding process. We consider that only three quarters of the reviewers arrive, but this is unknown a priori to the algorithms. This proportion is roughly based on the number of reviewers that were found to not place any positive bids during the NeurIPS 2016 review process (Shah et al., 2018b). The results under this real-world complexity are shown in Figures 4c and 4h. Moreover, reviewers may not actually arrive sequentially. Figures 4d and 4i consider the setting where Poisson(1) reviewers arrive at each time, and the algorithm must present paper orderings to all these reviewers simultaneously. For this pair of real-world complexities, SUPER∗ remains quite robust and generally performs favorably compared to the baselines in terms of both the gain and the bid count distributions. It is worth noting that when not all reviewers arrive, SUPER∗ with zero heuristic outperforms SUPER∗ with zero heuristic since it does attempt to account for bids that may come from reviewers that have not arrived.

A common feature in peer review bidding systems is the ability for a reviewer to search papers by subject area or keyword and then only bid within the resulting subset of papers. We now evaluate the robustness of SUPER∗ to this type of reviewer behavior in the following manner. In our simulations, on arrival of any reviewer, one quarter of the papers are randomly selected and required to be shown to the reviewer (these are the papers that are assumed to meet the search query). The remaining papers are not presented to the reviewer, are bid on with probability zero, and do not factor into the reviewer-side gain. The algorithms compute the paper orderings over only the selected subset of papers. The results of this experiment are shown in Figures 4e and 4j. We observe that SUPER∗ with zero heuristic outperforms the rest of the algorithms in terms of the gain while obtaining a favorable bid distribution. SUPER∗ with mean heuristic is not quite as robust since fewer bids come from future reviewers than anticipated when computing the mean heuristic – if one has estimates of the amount of selection done by reviewers via search, then this issue may be mitigated by appropriately scaling down the heuristic value.

2 Synthetic Similarities

We perform several simulations on synthetic similarity scores comparing the algorithms as presented in Figure 5. For this set of simulations, we consider the default model configuration from the previous section. Moreover, for each similarity structure we let the number of reviewers and the number of papers $(n,d)$ be among the set of pairs $\{(250,250),(500,500),(750,750),(1000,1000)\}$ and fix the trade-off parameter to be $\lambda=0.8$ since this gave roughly equal paper-side and weighted reviewer-side gains for RAND with $n=d=750$.

Homogeneous similarity scores. We consider a synthetic similarity matrix structure where each entry is drawn from at random from a Beta distribution with parameters $\alpha=1$ and $\beta=15$. This distribution is highly skewed and the expected value of a draw from it is $0.0625$. The results of this experiment are given in Figures 5a and 5e. The gain of SUPER∗ with each heuristic exceeds that of each of the baselines and similarly the bid count distributions show SUPER∗ with each heuristic ends up with at least 50% fewer papers obtaining under the minimum desired by the paper-side gain function compared to the baselines. We tried other homogeneous similarity structures and observed similar trends throughout.

Interdisciplinary papers. To conclude our simulations, we consider the impact our algorithm could have on interdisciplinary papers. As mentioned in Section 1, such papers face additional challenges in the peer review process owing to the lack of ideally matched peers. To simulate this phenomena, we consider a similarity matrix structure where there are two groups of reviewers of equal size and then three groups of papers which make up 40%, 40%, and 20% of the papers, respectively. Each reviewer in group one has similarity scores of $0.17$, $0.005$, and $0.085$ with the respective paper groups and each reviewer in group two has similarity scores of $0.005$, $0.17$, and $0.085$ with the respective paper groups. This reflects a scenario where the reviewer pool has two distinct areas of expertise and there is a set of interdisciplinary papers (paper group with similarity score of $0.075$ with all reviewers). We show the results of the experiment in Figures 5d and 5h. In terms of the gain, SUPER∗ and SIM perform significantly outperform BID and RAND. For the bid count distribution in Figure 5h, we only consider the interdisciplinary papers. SUPER∗ with each heuristic mitigates negative impacts on the interdisciplinary papers as the number with an insufficient number of bids is curtailed by 65% and 50% compared to SIM and RAND. This is a result of the fact that SUPER∗ works to trade-off the paper-side and reviewer-side objectives so the interdisciplinary papers end up not always being shown after the papers matching the reviewers expertise as occurs for SIM.

Discussion

This work develops a principled framework to improve bidding in peer review. We develop a sequential decision-making algorithm called SUPER∗ to optimize the process and show that it empirically outperforms baseline methods on real conference data and has several compelling theoretical guarantees.

This work leads to several interesting and potentially impactful open problems:

An obvious open problem is that of developing an online algorithm that is globally optimal for every similarity matrix. Conversely, showing possible computational hardness of the problem as a negative result could be a path of future work.

In several automated reviewer-paper assignment methods, bids and and similarities are combined to form the scores used to compute the assignment (Shah et al., 2018b). Given the tight connection between the bidding and matching systems, it is natural to design methods for jointly optimizing the components that govern the assignment process.

Finally, given the online nature of reviewer arrivals and the need to immediately show the paper ordering to an arriving reviewer, it is of interest to solve the passive problem. That is, develop an algorithm which selects the paper orderings to present to each reviewer before any of the reviewers arrive, which can be presented to a reviewer in the event of insufficient computational time. We also think that a solution to the passive problem would serve as an effective heuristic function for SUPER∗.

Although our work primarily focuses on peer review, there are a number of other applications for which this work is relevant. One such application is crowdsourcing, where a common goal of the crowdsourcing platform is to ensure that each task gets sufficiently many qualified workers. From the perspective of the worker, it has been documented quite extensively that workers put a non-trivial emphasis on a task if it is of interest to them (Kaufmann et al., 2011; Hossain, 2012). This means there is a trade-off of ensuring each worker is satisfied while ensuring a minimum number of workers for each job. As such, it is reasonable to formulate the crowdsourcing problem as a multi-objective optimization problem using analogous approach to the one presented in this paper for the bidding process in peer review. Indeed, the crowdsourcing platform in this formulation seeks to optimize both for a task-side objective, which ensures each task gets a sufficient number of workers selecting it, and for a user-side objective, which is to present relevant tasks to users.

Another potentially viable application is crowdfunding and microlending platforms such as Kiva or KickStarter. In crowdfunding, users pledge toward funding a project, and the project is only funded if the cumulative contributions of the crowd meet a known target threshold. The platforms seek to maximize the number of funded projects by deciding, when, how often, and to which users the projects are displayed. Past work (Jain and Jamieson, 2018) has modeled the optimization as a multi-armed bandit problem where the goal is to maximize the number of funded projects with a minimum amount of user impressions. This problem has a fundamental trade-off between showing relevant projects to users while ensuring that the projects themselves are given a fair shot to be funded. As such, a model-dependent approach such of ours could be of potential interest.

A final potential application outside of peer review for our work is in recommender systems and online advertising where there is the common trade-off between exploration (gaining sufficient feedback on all items) and exploitation (showing the most relevant items to users). In recommender systems, the cold start problem refers to the situation where the system is just beginning to interact with users or items are freshly included in the catalogue and no past user interaction information is available. The common trade-off arises again where there is a need to show relevant items to users, while the system benefits from gaining feedback on items for which the utility is unknown. Our framework easily adapts to a changing action set and could be relevant to this task.

Acknowledgments

This work was supported by NSF grants CIF 1763734, CAREER: CIF 1942124 and CRII: CIF 1755656. Tanner Fiez was also supported by the DoD NDSEG Fellowship Program.

References

Appendix A Proofs

In this section, we present proofs of the theoretical results presented in the main text. We begin by formally defining the history of information available to an algorithm when a reviewer arrives and restating important notation that will be found throughout the proofs.

We let $d\geq 2$ denote the number of papers and $n\geq 2$ denote the number of reviewers. We use the notation $S_{i,j}\in$ to denote the given similarity score between any reviewer $i\in[n]$ and paper $j\in[d]$. In general, we let $i$ index a reviewer and $j$ index a paper. We commonly use the set notation $[\kappa]=\{1,2,\dots,\kappa\}$ for any positive integer $\kappa$. $\Pi_{d}$ denotes the set of $d!$ permutations of $d$ papers. For any reviewer $i\in[n]$, we let $\pi_{i}\in\Pi_{d}$ denote the ordering (permutation) of the papers shown to reviewer $i$. We use the notation $\pi_{i}(j)$ to denote the position of paper $j\in[d]$ in the ordering $\pi_{i}$. The notation $\mathcal{B}_{i,j}$ represents the random variable of reviewer $i\in[n]$ biding on paper $j\in[d]$ which follows a Bernoulli distribution with parameter $p_{i,j}=f(\pi_{i}(j),S_{i,j})$. We use the notation $g_{i-1,j}\in\{0,\ldots,i-1\}$ to denote the number of bids received by any paper $j\in[d]$ at the time of arrival of reviewer $i\in[n]$ and $g_{j}$ to denote the number of bids at the end of the bidding process on paper $j\in[d]$. The heuristic estimating the number of bids paper $j\in[d]$ will obtain from reviewers $\{i+1,\dots,n\}$ is denoted as $h_{i,j}$ and it is provided to the SUPER∗ algorithm on arrival of reviewer $i\in[n]$. Finally, we abbreviate ‘with probability’ by w.p and use the terminology almost surely to mean with probability one and almost never to mean with probability zero.

A.1 Proof of Theorem 1: Local Optimality of SUPER∗ for Final Reviewer

In this proof, we show that selecting the optimal ordering to present to the final reviewer can be simplified to a tractable optimization problem. The SUPER∗ algorithm solves exactly this problem to determine an ordering of papers to present the final reviewer, and is hence an optimal algorithm for the final reviewer.

The optimization problem for the final reviewer $n$ to maximize the expected gain conditioned on the history is

where the expectation is taken over the randomness in the bid to be placed by the reviewer. Conditioned on the history $\mathcal{H}_{n-1}$, the final number of bids on any paper $j\in[d]$ given by $g_{j}$ is the sum of the deterministic number of bids prior to the final reviewer denoted as $g_{n-1,j}$ and a Bernoulli random variable $\mathcal{B}_{n,j}$ with parameter $p_{n,j}=f(\pi_{n}(j),S_{n,j})$ representing the random bid of the final reviewer. We incorporate this fact and remove terms independent of the optimization variable from the problem in (9) to equivalently obtain

where the expectation on the reviewer-side gain is removed as it is independent of the random reviewer bids.

We now simplify the paper-side gain term by expanding the expectation for each $j\in[d]$. Observe that

Substituting (11) into (10) and removing the term independent of the optimization variable gives the problem

We now reformulate (12) into the following equivalent integer linear programming problem:

In this formulation, $x$ is a $d\times d$ matrix for which $x_{j,k}$ is an indicator of paper $j\in[d]$ being shown at position $k\in[d]$. The constraint $\sum_{k\in[d]}x_{j,k}=1\ \forall\ j\in[d]$ ensures each paper is included strictly once in the ordering shown to the reviewer. The constraint $\sum_{j\in[d]}x_{j,k}=1\ \forall\ k\in[d]$ ensures strictly one paper is selected to be shown at each position. The final constraint ensures that each index of $x$ is integer valued. This integer linear programming problem is known as a linear sum assignment problem.

The key step of this proof is to recall that the linear sum assignment problem can be solved as a linear program. Indeed, the final constraint ensuring an integer solution can be relaxed to $0\leq x_{j,k}\leq 1\ \forall\ j,k\in[d]$ and the optimal solution of the relaxed linear program will be the integer optimal solution. This property of the linear sum assignment problem is a consequence of the relaxed linear program containing a totally unimodular constraint set which guarantees the optimal solution to be the integral solution (see, e.g., Chapter 4 in Burkard et al., 2012).

The optimization problem arising from recognizing that the integer constraint can be relaxed is given by

This formulation shows that the paper ordering for the final reviewer that maximizes the expected gain conditioned on the history can be obtained efficiently by solving a linear program.

To determine the ordering of papers to show any reviewer $i\in[n]$ for the general class of assumed gain and bidding functions, SUPER∗ calls Algorithm 3.2. Algorithm 3.2 solves the optimization problem in (13) using the weights

Given any heuristic function, the heuristic for the final reviewer is such that $h_{n}=0$. This means SUPER∗ selects the paper ordering for the final reviewer by solving the optimization problem from (13–14) to maximize the expected gain conditioned on the history. As a result, we conclude SUPER∗ is locally optimal for the final reviewer with any heuristic function.

A.2 Proof of Corollary 1: Local Optimality of SUPER∗ for Any Reviewer

The immediate gain from any reviewer $i\in[n]$ is the difference between the gain after and before the reviewer arrived. Formally, the immediate gain from any reviewer $i\in[n]$ is given by the quantity

The optimization problem to maximize the immediate expected gain from reviewer $i\in[n]$ conditioned on the history (see Definition 1) is thus given by

We now evaluate the expectation in (16) using (11) and then simplify to obtain the optimization problem

The problem in (17) is equivalent to that given in (12) from the proof of Theorem 1 up to the reviewer index. Consequently, we follow the steps after (12) in the proof of Theorem 1 to simplify (17) into a tractable representation. In doing so, we get that the problem in (17) is equivalent to the linear program in (13) with the weights

To determine the ordering of papers to show any reviewer $i\in[n]$ for the general class of assumed gain and bidding functions, SUPER∗ calls Algorithm 3.2. Algorithm 3.2 solves the optimization problem in (13) using the weights

For any reviewer $i\in[n]$, given the zero heuristic function, $h_{i}=0$ by definition. This means SUPER∗ with zero heuristic selects the paper ordering for any reviewer by solving the optimization problem to maximize the immediate expected gain conditioned on the history, so we conclude it is locally optimal for any reviewer.

A.3 Proof of Theorem 2: Suboptimality of Baselines for Final Reviewer

The organization of this proof is as follows. In Section A.3.1, we present notation and preliminary information common to the analysis for each of the baselines. We prove the suboptimality bounds for the SIM, BID, and RAND baselines separately in Sections A.3.2, A.3.3, and A.3.4, respectively. Combining the results for each of the baselines proves the theorem statement. We conclude in Section A.3.5 with proofs of technical lemmas invoked in the analysis of the baselines.

We denote the gain from the final reviewer $n$ of an arbitrary algorithm ALG presenting a potentially random paper ordering $\pi_{n}^{\texttt{ALG}}$ to the reviewer as

The paper-side gain from the final reviewer $\mathcal{G}_{p,n}^{\texttt{ALG}}$ is given by

where again $\mathcal{B}_{i,j}$ is a Bernoulli random variable representing the random bid of a reviewer $i\in[n]$ on a paper $j\in[d]$ that depends on the position the paper was shown to the reviewer. The reviewer-side gain from the final reviewer $\mathcal{G}_{r,n}^{\texttt{ALG}}$ is given by

The expected gain from the final reviewer conditioned on the history of bids and paper orderings $\mathcal{H}_{n-1}$ (see Definition 1) is given by

where the expectation is with respect to the randomness in the algorithm and the bids from the final reviewer. Observe that

since $\sum_{i\in[n-1]}\mathcal{B}_{i,j}$ is the deterministic quantity $g_{n-1,j}$ for each $j\in[d]$ conditioned on $\mathcal{H}_{n-1}$ and $\mathcal{B}_{n,j}$ is a Bernoulli random variable with parameter $p_{n,j}=f(\pi_{n}^{\texttt{ALG}}(j),S_{n,j})$ for each $j\in[d]$ given the fixed paper ordering $\pi_{n}^{\texttt{ALG}}$. Moreover,

The given biding function can be decomposed into the form

denotes the component of the bidding function $f$ that only depends on the paper ordering and is independent of the similarity score. The reviewer-side gain function can similarly be decomposed into the form

Using the decomposed forms of the bidding function and the reviewer-side gain function from (18) and (19), the expected gain from the final reviewer $n$ of an arbitrary algorithm ALG is given by

The optimal paper ordering for the final reviewer is thus given by the solution to the following optimization problem

The optimal solution to (21) ranks papers in a decreasing order of their corresponding values in {$\alpha_{n,j}\}_{j\in[d]}$ since the function $f^{\pi}$ is decreasing in the decision variable. This observation will be used to obtain an explicit form of $\pi_{n}^{\ast}$ for each problem we subsequently construct to show the suboptimality of the baselines. From Theorem 1, SUPER∗ with any heuristic is optimal for the final reviewer, which means \pi^{\texttt{SUPER}\text{{}^{*}}}_{n}=\pi^{\ast}_{n}. See that \pi^{\texttt{SUPER}\text{{}^{*}}}_{n} is a non-random quantity given a deterministic tie-breaking mechanism and the expected gain is independent of the tie-breaking mechanism. Thus, without loss of generality, we assume ties are broken by the paper indexes in favor of $j<j^{\prime}$ for SUPER∗.

We need to compare the expected gain obtained from the final reviewer using the SUPER∗ algorithm presenting the optimal paper ordering \pi^{\texttt{SUPER}\text{{}^{*}}}_{n}=\pi^{\ast}_{n} with any baseline ALG $\in\{\texttt{SIM},\texttt{BID},\texttt{RAND}\}$ presenting a potentially random ordering $\pi^{\texttt{ALG}}_{n}$. Therefore, we analyze the quantity

for each baseline ALG $\in\{\texttt{SIM},\texttt{BID},\texttt{RAND}\}$. The SIM and BID algorithms are deterministic for the final reviewer conditioned on the history, up to the tie-breaking mechanism. The RAND algorithm is random, so the expectation over the paper ordering in (23) is necessary when analyzing RAND. In the remainder of the proof, we analyze SIM, then BID, and finish with RAND.

A.3.2 Suboptimality of SIM for Final Reviewer

In this section, we prove the worst case performance of the SIM baseline for the final reviewer.

The SIM algorithm directly optimizes the expected reviewer-side gain since it shows papers in a decreasing order of the similarity scores. Consequently, it obtains the maximum expected reviewer-side gain that can be achieved. However, the algorithm gives no attention to the number of bids on each paper, which play an important role in the expected paper-side gain that can be obtained upon the arrival of the final reviewer. This point suggests that SIM may be suboptimal for the combined objective.

To build intuition for when this can occur, consider that there is only a pair of papers $j$ and $j^{\prime}$. Moreover, suppose paper $j$ has only marginally higher similarity score than paper $j^{\prime}$, but paper $j$ has significantly more bids than paper $j^{\prime}$. In this scenario, the expected reviewer-side gain of any paper ordering is nearly equal. However, showing paper $j^{\prime}$ ahead of paper $j$ results in significantly higher expected paper-side gain owing to the diminishing returns of bids from the paper-side gain function. Since SIM instead shows paper $j$ ahead of paper $j^{\prime}$, it would be suboptimal. The following construction now generalizes this observation.

We now construct a problem instance that will be used to prove SIM is significantly suboptimal for the final reviewer in the worst case. Consider the similarity scores for the final reviewer to be $S_{n,j}=1-1/(j\epsilon)$ for each paper $j\in[d]$, where $\epsilon=(1+\lambda)e^{e^{e}}$ and $\lambda\geq 0$ is the fixed and given trade-off parameter. In this construction, the similarity scores for the final reviewer are nearly equal, but they are increasing in the paper index. For the time being, assume the number of papers $d$ is even. At the end of this section, we handle when the number of papers $d$ is odd. Let the number of bids on the papers from previous reviewers be

The bid counts are such that papers among the top half of the similarity scores obtained a bid in the past, and papers among the bottom half of the similarity scores did not obtain any bids from previous reviewers.

We now derive the explicit form of the optimal paper ordering for the final reviewer. Recall from (22) that the weights of the optimization problem for the final reviewer given in (21) are defined by

Moreover, from the structure of the optimization problem in (21), if $\alpha_{n,j}>\alpha_{n,j^{\prime}}$, then \pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j)<\pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j^{\prime}) so that paper $j$ is shown ahead of paper $j^{\prime}$ in the ranking. Observe that $\alpha_{n,j}$ is increasing in the similarity score $S_{n,j}$ and decreasing in the number of bids $g_{n-1,j}$ for each $j\in[d]$. Consequently, if a pair of papers $j,j^{\prime}\in[d]$ are such that $g_{n-1,j}=g_{n-1,j^{\prime}}$ and $S_{n,j}>S_{n,j^{\prime}}$, then $\alpha_{n,j}>\alpha_{n,j^{\prime}}$ and in turn, \pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j)<\pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j^{\prime}).

We now show that in the optimal ordering for this instance, each paper with zero bids is shown ahead of each paper with a non-zero number of bids. Among the set of papers with zero bids, namely those indexed by $\{1,\dots,d/2\}$, the minimum similarity score $S_{n,j}$ and minimum weight $\alpha_{n,j}$ occur at $j=1$. Among the set of papers with a non-zero number of bids, namely those indexed by $\{d/2+1,\dots,d\}$, the maximum similarity score $S_{i,j^{\prime}}$ and maximum weight $\alpha_{n,j^{\prime}}$ occur at $j^{\prime}=d$. Thus, if $\alpha_{n,1}-\alpha_{n,d}>0$, then we can conclude each paper with zero bids is shown ahead of each paper with a non-zero number of bids. To prove this, we need the following lemma, the proof of which can be found in Section A.3.5.1.

For $\gamma_{p}(x)=\sqrt{x}$, any $\lambda\geq 0$, $d\geq 2$, and $\epsilon=(1+\lambda)e^{e^{e}}$, it must be that

From the given similarity scores and bid counts, and then applying Lemma 25, we obtain

Therefore, the optimal paper ordering shows all papers with zero bids ahead of every paper with a non-zero number of bids. Moreover, recall if a pair of papers $j,j^{\prime}\in[d]$ are such that $g_{n-1,j}=g_{n-1,j^{\prime}}$ and $S_{n,j}>S_{n,j^{\prime}}$, then $\alpha_{n,j}>\alpha_{n,j^{\prime}}$. This fact allows us to determine that among each group of papers (zero and non-zero bids), the optimal paper ordering presents the papers in decreasing order of the similarity scores.

Combining the previous conclusions, SUPER∗ shows the optimal paper ordering

The SIM algorithm shows papers in a decreasing order of the similarity scores so that $\pi_{n}^{\texttt{SIM}}(j)=d-j+1$ for $j\in[d]$. Observe that for this problem, SUPER∗ shows the papers with zero bids much earlier in the paper ordering than SIM. We now move on to lower bounding (23) for this construction and begin by considering the expected paper-side gain.

Substituting the similarity scores, the number of bids on each paper, and the (deterministic) paper orderings presented by each algorithm for this construction into the paper-side component of (23), we obtain

Manipulating the indexing of the sum over the last half of the papers gives

Noting that $(f^{\pi}(d/2-j+1)-f^{\pi}(d-j+1))=-(f^{\pi}(d-j+1)-f^{\pi}(d/2-j+1))$, we obtain

Finally, manipulating the indexing of the sum gives

We now bound the expected reviewer-side gain including the trade-off parameter $\lambda$ from (23). The steps that follow are analogous to those exercised in bounding the expected paper-side gain.

Substituting the values of the similarity scores, the number of bids on each paper, and the (deterministic) paper orderings presented by each algorithm into the reviewer-side component of (23), we obtain

Manipulating the indexing of the sum over the last half of the papers results in

Noting that $f^{\pi}(d/2-j+1)-f^{\pi}(d-j+1)=-(f^{\pi}(d-j+1)-f^{\pi}(d/2-j+1))$, we obtain

To finish this sequence of steps, we manipulate the indexing of the sum to conclude

Combining the bounds on the expected paper-side and reviewer-side gain terms from (27) and (28), we obtain an initial lower bound given by

We apply Lemma 25 to get that $\mathcal{C}\geq 1/2$. The following lemma, the proof of which can be found in Section A.3.5.2, provides a bound on the sum in (29).

Let $f^{\pi}(x)=1/\log_{2}(x+1)$. Fix $d$ to be an even integer such that $d\geq 2$. Then,

From (29) along with the fact that $\mathcal{C}\geq 1/2$ and Lemma 2, we obtain

Lemma 2, and consequently the bound in (31), are applicable when $d$ is even. The following lemma shows that an equivalent result (up to constants) holds when the number of papers $d$ is odd. The bound is obtained by looking at an identical problem construction for $d^{\prime}=d-1$ papers, and then including an additional paper that has a similarity score of zero with the final reviewer and one previous bid. This change is such that both SUPER∗ and SIM show the additional paper last, and moreover, the expected gain from paper $d$ is zero since the similarity score is zero.

If $d$ is odd, then in the worst case for the final reviewer under the assumptions of Theorem 2,

The proof of Lemma 3 is in Section A.3.5.3.

Combining the bound from (31) which holds for $d$ even with the bound from Lemma 3 which holds for $d$ odd, we find that for every $d\geq 2$ and $\lambda\geq 0$,

This proves the claim in Theorem 2 stating that there exists a constant $c>0$ such that for every $d\geq 2$ and $\lambda\geq 0$, SIM is suboptimal by an additive factor of at least $cd/\log_{2}^{2}(d)$ in the worst case for the final reviewer.

A.3.3 Suboptimality of BID for Final Reviewer

In this section, we prove the worst case performance of the BID baseline for the final reviewer.

The BID algorithm greedily optimizes the minimum bid count since it shows papers in an increasing order of the number of bids received previously. The underlying problem with this method is that the paper ordering selected for any reviewer is independent of the similarity scores for that reviewer (up to serving as a tie-breaking mechanism). Since the paper-side gain function and the reviewer-side gain function both depend on the similarity scores, this property of BID leads to suboptimality in terms of both the expected paper-side gain and the reviewer-side gain.

To build some intuition for when BID is suboptimal, consider there is only a pair of papers $j$ and $j^{\prime}$. Moreover, suppose paper $j$ has a much higher similarity score than paper $j^{\prime}$ and paper $j$ has only one more bid than $j^{\prime}$. In this scenario, the expected reviewer-side gain from showing paper $j$ ahead of paper $j^{\prime}$ is significantly higher than showing paper $j^{\prime}$ ahead of paper $j$. Moreover, since the probability of obtaining a bid on paper $j$ is significantly higher at a given position in the paper ordering than for paper $j^{\prime}$ and the number of bids on the papers are nearly equal, the expected paper-side gain is also maximized if paper $j$ is shown ahead of paper $j^{\prime}$. Since BID instead shows paper $j^{\prime}$ ahead of paper $j$, it would be suboptimal for both paper-side and reviewer-side gain. The following construction now generalizes this observation.

We now construct a problem instance that will be used to prove BID is significantly suboptimal for the final reviewer in the worst case. Consider the similarity scores for the final reviewer as

For now, assume the number of papers $d$ is even. We handle when the number of papers $d$ is odd at the end of this proof. Let the number of bids on the papers from previous reviewers be such that

In words, half of the papers have a similarity score of one and have recieved bids, and the other half of the papers have a similarity score of zero and have obtained no bids.

We now derive the optimal paper ordering for the final reviewer. Recall from (22) that the weights of the optimization problem for the final reviewer given in (21) are defined by

Moreover, from the structure of the optimization problem in (21), if $\alpha_{n,j}>\alpha_{n,j^{\prime}}$, then \pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j)<\pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j^{\prime}) so that paper $j$ is shown ahead of paper $j^{\prime}$ in the ranking. Observe that for each $j\in\{1,\dots,d/2\}$, $\alpha_{n,j}$ is a fixed number. Similarly, for each $j^{\prime}\in\{d/2+1,\dots,d\}$, $\alpha_{n,j^{\prime}}$ is a fixed number. If $\alpha_{n,j}-\alpha_{n,j^{\prime}}>0$ for any $j\in\{1,\dots,d/2\}$ and $j^{\prime}\in\{d/2+1,\dots,d\}$, then we can conclude each paper with a bid is shown ahead of each paper without a bid. We consider $j=1$ and $j^{\prime}=d$. Since $\gamma_{p}(x)=\sqrt{x}$ and $\alpha_{n,d}=0$,

Consequent of the fact $\lambda\geq 0$, we conclude $\alpha_{n,1}-\alpha_{n,d}>0$, which means SUPER∗ shows each paper with a bid ahead of each paper without a bid. Finally, since $\alpha_{n,j}$ is a fixed number for each $j\in\{1,\dots,d/2\}$ and $\alpha_{n,j^{\prime}}$ is a fixed number for each $j^{\prime}\in\{d/2+1,\dots,d\}$, as long as \pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j)<\pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j^{\prime}) for every $j,j^{\prime}$ pair, then the paper ordering is optimal. In other words, any paper ordering which shows the papers with a bid in an arbitrary order followed by the papers without a bid in an arbitrary order is optimal.

We conclude \pi^{\texttt{SUPER}\text{{}^{*}}}_{n}(j)=j for each $j\in[d]$, where without loss of generality, to simplify the analysis, we assume if a pair of papers have equal weights in the optimization problem, then ties are broken in order of the paper indexes since the tie-breaking mechanism will not change the expected gain the paper ordering obtains from the final reviewer.

The BID baseline will show papers in an increasing order of the number of bids so that

This paper ordering is derived from recalling that BID breaks ties by the similarity scores and further ties are broken uniformly at random. However, without loss of generality, to simplify the analysis, we assume if a pair of papers have equal similarity scores and bid counts, then ties are broken in order of the paper indexes since the tie-breaking mechanism among this set of papers will not impact the expected gain. We now move on to lower bounding (23) for this construction.

Substituting the similarity scores, the number of bids on each paper, and the (deterministic) paper orderings presented by each algorithm for this construction into (23), we obtain

where the terms for papers in the set $\{d/2+1,\dots,d\}$ dropped out since the similarity scores are zero. Simplifying the expression, we obtain

Combining (33), (34), and (35), we obtain

whenever the number of papers $d$ is even.

Lemma 2 and the bound in (36) are applicable when $d$ is even. The following lemma shows that an equivalent result (up to constants) holds when the number of papers $d$ is odd. The approach to obtain the result is similar to that for deriving Lemma 3. We obtain the bound for an odd number of papers $d$ by looking at an identical problem construction for $d^{\prime}=d-1$ papers, and then include an additional paper that has a similarity score of zero with the final reviewer and one previous bid. This change is such that both SUPER∗ and BID show the additional paper last, and moreover, the expected gain from paper $d$ is zero since the similarity score is zero.

If $d$ is odd, then in the worst case for the final reviewer under the assumptions of Theorem 2,

The proof of Lemma 4 is in Section A.3.5.4.

Combining the bound from (36) which holds for $d$ even with the bound from Lemma 4 which holds for $d$ odd, we find that for every $d\geq 2$ and $\lambda\geq 0$,

This proves the claim in Theorem 2 that there exists a constant $c>0$ such that for all $d\geq 2$ and $\lambda\geq 0$, BID is suboptimal by an additive factor of at least $cd\max\{1,\lambda\}/\log_{2}^{2}(d)$ in the worst case for the final reviewer.

A.3.4 Suboptimality of RAND for Final Reviewer

In this section, we prove the the worst case performance of the RAND baseline for the final reviewer.

The RAND algorithm selects an ordering of papers to show a reviewer uniformly at random from the set of permutations. Since this method is agnostic to the similarity scores and the number of bids, RAND can select highly suboptimal paper orderings with some non-zero probability.

To see when this can occur, consider the example that provided intuition for the suboptimality of BID in Section A.3.3 that consisted of only a pair of papers $j$ and $j^{\prime}$. In this example, paper $j$ has a much higher similarity score than paper $j^{\prime}$ and paper $j$ has only one more bid than $j^{\prime}$. The expected reviewer-side gain from showing paper $j$ ahead of paper $j^{\prime}$ is significantly higher than showing paper $j^{\prime}$ ahead of paper $j$. Moreover, since the probability of obtaining a bid on paper $j$ is significantly higher at a given position in the paper ordering than for paper $j^{\prime}$ and the number of bids on the papers are nearly equal, the expected paper-side gain is also maximized if paper $j$ is shown ahead of paper $j^{\prime}$. Since there are only two permutations of the papers that can be selected, with probability $1/2$, RAND would show paper $j^{\prime}$ ahead of paper $j$ and be suboptimal for both paper-side and reviewer-side gain. The problem construction from Section A.3.3 is sufficient to generalize this observation. For completeness, we repeat the construction below.

In the remainder of the proof, we show the problem construction from Section A.3.3 can be used to prove RAND is significantly suboptimal for the final reviewer in the worst case. In this construction, the similarity scores for the final reviewer are

For now, assume the number of papers $d$ is divisible by four. We deal with a number of papers $d$ that is not divisible by four at the end of this section. The number of bids on the papers from previous reviewers are

In Section A.3.3, we showed that SUPER∗ selects the optimal ordering \pi^{\texttt{SUPER}\text{{}^{*}}}_{n}(j)=j for each $j\in[d]$. The RAND baseline will select a paper ordering $\pi_{n}^{\texttt{RAND}}$ uniformly at random from the set of permutations $\Pi_{d}$.

For this construction, we need to lower bound (23). As an initial step, we simplify the quantity by substituting the similarity scores, the number of bids on each paper, and the paper ordering presented by SUPER∗ to obtain

where the terms for papers in the set $\{d/2+1,\dots,d\}$ dropped out since the similarity scores are zero. Combining the sums and using the fact that $\gamma_{p}(2)-\gamma_{p}(1)=\sqrt{2}-1\geq 1/3$ gives

Toward formalizing this line of reasoning, the following lemma provides a lower bound on the probability that RAND selects a paper ordering that shows fewer than $d/4$ papers from the set $\{1,\dots,d/2\}$ in the set of positions $\{1,\dots,d/2\}$. The proof is given in Section A.3.5.5.

Define $T_{1}\subset\Pi_{d}$ as the set of paper orderings with fewer than $d/4$ of the papers from the set $\{1,\dots,d/2\}$ in the set of positions $\{1,\dots,d/2\}$ and $T_{2}\subset\Pi_{d}$ as the set containing the remaining paper orderings so that $T_{1}\cup T_{2}=\Pi_{d}$. Now, beginning from (38), we evaluate and bound the expectation as follows:

is a minimizer of $\sum_{j=1}^{d/2}(f^{\pi}(j)-f^{\pi}(\pi_{n}(j)))$ among the set $T_{1}$. Substituting the paper ordering from (40) as the minimizer into (39), we obtain

The following lemma provides a bound on the sum in (41).

Let $f^{\pi}(x)=1/\log_{2}(x+1)$ and fix $d\geq 4$ and divisible by four. Then,

The proof of Lemma 6 can be found in Section A.3.5.6.

Combining (41) and Lemma 6 results in the following bound whenever $d$ is divisible by four:

The next lemma shows that if the number of papers $d$ is not divisible by four, an equivalent result (up to constants) holds. For $d\in\{2,3\}$, the bound is rather immediate since we can compute the probability that RAND selects the paper ordering BID shows for this construction and then apply the bound from (37) on the suboptimality of BID that holds for any $d$. For $d>3$ and not divisible by four, the bound is obtained by looking at an identical problem construction for the maximum $d^{\prime}<d$ divisible by four and then including $d-d^{\prime}$ papers with a similarity score of zero and one previous bid. This change is such that the bound from (42) applies as a function of $d^{\prime}$, so the result then follows immediately.

If $d$ is not divisible by four, then in the worst case for the final reviewer under the assumptions of Theorem 2,

The proof of Lemma 7 can be found in Section A.3.5.7.

Combining the bound from (42) which holds for $d$ divisible by four with the bound from Lemma 7 which holds for $d$ not divisible by four, we find that for every $d\geq 2$ and $\lambda\geq 0$,

This proves there is a constant $c>0$ such that for all $d\geq 2$ and $\lambda\geq 0$, RAND is suboptimal by an additive factor of at least $cd\max\{1,\lambda\}/\log_{2}^{2}(d)$ in the worst case for the final reviewer as claimed in Theorem 2.

A.3.5 Proofs of Lemmas 25–7

In this section, we present the proofs of technical lemmas stated in the primary proof of Theorem 2.

Recall from the lemma statement, $\gamma_{p}(x)=\sqrt{x}$. Moreover, the fixed and given quantities are $\lambda\geq 0$, $d\geq 2$, and $\epsilon=(1+\lambda)e^{e^{e}}$. We derive the following bound justified below:

We obtain (43) using the fact that $(1-1/(d\epsilon))\leq 1$ for any given $d$. Equation (44) follows from plugging in the explicit form of $\epsilon=(1+\lambda)e^{e^{e}}$. To see the inequality in (45), observe that $(1-((1+\lambda)e^{e^{e}})^{-1})$ is an increasing function of $\lambda$. Consequently, $(1-((1+\lambda)e^{e^{e}})^{-1})\geq(1-(e^{e^{e}})^{-1})\geq 0.99$. Furthermore, the quantity $\lambda(2^{(1-1/((1+\lambda)e^{e^{e}}))}-2)$ is a decreasing function of $\lambda$, from which we determine

Then, we obtain the final bound in (46) as follows:

Recall that $f^{\pi}(x)=1/\log_{2}(x+1)$. Fixing $d=2$, we obtain

The inequality in (47) follows from the fact that $\log_{2}(3)-1\geq 1/2$ and $\log_{2}(3)\leq 2\log_{2}(2)$.

Now consider $d\geq 4$ and $d$ even. We derive a bound as follows that is justified below:

Combining the bound for $d=2$ from (48) and the bound for $d\geq 4$ and even from (52), we conclude

In this proof, we show a simple adaptation of the problem construction from Section A.3.2 results in a suboptimality bound on SIM for the final reviewer when the number of papers $d$ is odd that matches (up to constants) the bound given in (31) that holds whenever the paper count $d$ is even.

Fix $d$ odd and let $d^{\prime}=d-1$ (and hence $d^{\prime}$ is an even number). We consider an identical problem construction for the papers $j\in[d^{\prime}]$ as from Section A.3.2 and then include a paper $d$ that has a similarity score of zero and one bid. This change is such that for the given class of functions in the model, SUPER∗ and SIM show the paper $d$ after the papers in the set $[d^{\prime}]$ and the expected gain from paper $d$ is deterministically zero since the similarity score is zero.

In particular, let the similarity scores for the final reviewer be $S_{n,j}=1-1/(j\epsilon)$ for each paper $j\in[d^{\prime}]$, where $\epsilon=(1+\lambda)e^{e^{e}}$ and $\lambda\geq 0$ is the fixed and given trade-off parameter. Moreover, let $S_{n,d}=0$. Set the number of bids on the papers from previous reviewers to be

In Section A.3.2, we showed if a pair of papers $j,j^{\prime}$ are such that $g_{n-1,j}=g_{n-1,j^{\prime}}$ and $S_{n,j}>S_{n,j^{\prime}}$, then \pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j)<\pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j^{\prime}). Since paper $j^{\prime}=d$ is such that for every paper $j\in\{d^{\prime}/2+1,\ldots,d^{\prime}\}$, $g_{n-1,j}=g_{n-1,j^{\prime}}$ and $S_{n,j}>S_{n,j^{\prime}}$, we find \pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j^{\prime})<\pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j^{\prime}). From (26), this means for this construction \pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(d)=d and that SUPER∗ shows the paper ordering

The SIM algorithm shows papers in a decreasing order of the similarity scores so that

Observe that this construction is identical to the problem construction from Section A.3.2 for papers in the set $[d^{\prime}]$. Moreover, from (20) it is clear that the expected gain from papers with zero similarity score is zero independent of the paper ordering. This allows us to conclude that the bound given in (31) for $d$ even applies to this construction as a function of $d^{\prime}$. In other words, given $d$ odd, we obtain

Moreover, since $d^{\prime}=d-1$, whenever $d$ is odd,

where the final inequality follows from the facts that $\log_{2}^{2}(d-1)\leq\log_{2}^{2}(d)$ and $d-1\geq d/2$ for $d\geq 2$.

In this proof, we show a simple adaptation of the problem construction from Section A.3.3 leads to a suboptimality bound on BID for the final reviewer when the number of papers is odd that matches (up to constants) the bound given in (36) that holds whenever the number of papers $d$ is even. This approach is analogous to the method to obtain a suboptimality bound for SIM with an odd number of papers using the bound that held for an even number of papers from Lemma 3.

Fix $d$ odd and let $d^{\prime}=d-1$ (and hence $d^{\prime}$ is an even number). We consider an identical problem construction for the papers $j\in[d^{\prime}]$ as from Section A.3.3 and then include a paper $d$ that has a similarity score of zero and one bid. This change is such that for the given class of functions in the model, SUPER∗ and BID show the paper $d$ after the papers in the set $[d^{\prime}]$ and the expected gain from paper $d$ is deterministically zero since the similarity score is zero.

Let the similarity scores for the final reviewer be

and the number of bids on the papers from previous reviewers be

We now derive the optimal paper ordering for the final reviewer. Recall from (22) that the weights of the optimization problem for the final reviewer given in (21) are defined by

Moreover, from the structure of the optimization problem in (21), if $\alpha_{n,j}>\alpha_{n,j^{\prime}}$, then \pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j)<\pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j^{\prime}) so that paper $j$ is shown ahead of paper $j^{\prime}$ in the ranking. Observe that for each paper $j\in\{1,\dots,d^{\prime}/2\}$, $\alpha_{n,j}$ is a fixed number. Similarly, for each $j^{\prime}\in\{d^{\prime}/2+1,\dots,d^{\prime}\}\cup\{d\}$, $\alpha_{n,j^{\prime}}$ is a fixed number. In Section A.3.3, we showed if a pair of papers $j,j^{\prime}$ are such that $g_{n-1,j}=1$ and $g_{n-1,j^{\prime}}=0$ along with $S_{n,j}=1$ and $S_{n,j^{\prime}}=0$, then $\alpha_{n,j}>\alpha_{n,j^{\prime}}$ so that \pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j)<\pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j^{\prime}). This immediately guarantees \pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j)<\pi_{n}^{\texttt{SUPER}\text{{}^{*}}}(j^{\prime}) for each pair of papers $j\in\{1,\dots,d^{\prime}/2\}$, $j^{\prime}\in\{d^{\prime}/2+1,\dots,d^{\prime}\}\cup\{d\}$. We conclude \pi^{\texttt{SUPER}\text{{}^{*}}}_{n}(j)=j for each $j\in[d]$, where without loss of generality, to simplify the analysis, we assume if a pair of papers have equal weights in the optimization problem, then ties are broken in order of the paper indexes since the tie-breaking mechanism will not change the expected gain the paper ordering obtains from the final reviewer.

The BID baseline will show papers in an increasing order of the number of bids so that

This paper ordering is derived from recalling that BID breaks ties by the similarity scores and further ties are broken uniformly at random. However, without loss of generality, to simplify the analysis, we assume if a pair of papers have equal similarity scores and bid counts, then ties are broken in order of the paper indexes since the tie-breaking mechanism among this set of papers will not impact the expected gain.

The construction in this proof and the paper orderings selected by SUPER∗ and BID are identical to the problem construction and paper orderings selected by SUPER∗ and BID from Section A.3.3 for papers in the set $[d^{\prime}]$. From (20) it is clear that the expected gain from papers with zero similarity score is zero independent of the paper ordering. This allows us to conclude that the bound given in (36) for $d$ even applies to this construction as a function of $d^{\prime}$. In other words, given $d$ odd, we obtain

Since $d^{\prime}=d-1$, whenever $d$ is odd,

where the final inequality follows from the facts that $\log_{2}^{2}(d-1)\leq\log_{2}^{2}(d)$ and $d-1\geq d/2$ for $d\geq 2$.

Recall that from the lemma statement, the number of papers $d$ is assumed to be divisible by four. Let $\mathcal{E}$ denote the event that a permutation $\pi$ of the paper set $[d]$ drawn uniformly at random from $\Pi_{d}$ has fewer than $d/4$ of the papers from the set $[d/2]$ in the position set $[d/2]$.

The probability of the event $\mathcal{E}$ can be explained in the following manner. The number of outcomes presenting $j$ papers from the paper set $[d/2]$ in the position set $[d/2]$ consists of ${d/2\choose j}$ combinations of potential papers that can be selected from the paper set $[d/2]$ and ${d/2\choose j}$ combinations of potential positions in the position set $[d/2]$. Moreover, there are $j!$ permutations of the selected papers in the chosen positions. Given that there are $j$ papers selected from the paper set $[d/2]$ placed in the position set $[d/2]$, there are ${d/2\choose d/2-j}$ combinations of papers from the paper set $\{d/2+1,\dots,d\}$ that can be placed in the remaining spots in the position set $[d/2]$. This set of papers can be permuted $(d/2-j)!$ ways in the given set of positions, and the remaining $d/2$ papers can be permuted $(d/2)!$ ways in the position set $\{d/2+1,\dots,d\}$. To obtain the final probability of the event $\mathcal{E}$, we sum the number of outcomes for each $j<d/4$ and then normalize by the total number of outcomes $d!$. Accordingly,

From the symmetry property, ${d/2\choose j}^{2}={d/2\choose d/2-j}^{2}$, so we get

Manipulating the indexing of the sum $\sum_{j=0}^{d/4}{d/2\choose d/2-j}^{2}$, we obtain

Now, moving the term $\frac{1}{2}{d/2\choose d/4}^{2}$ out of the sum $\frac{1}{2}\sum_{j=d/4}^{d/2}{d/2\choose j}^{2}$ results in

Finally, applying Vandermonde’s identity as given above, we get

Combing (54) with (55) and then simplifying, we get

The quantity \Big{(}\frac{(d/2)!(d/2)!}{2d!}\Big{)}\Big{(}\frac{(d/2)!}{(d/4)!(d/4)!}\Big{)}^{2} is decreasing in $d$. Consequently, for every $d\geq 4$,

This proof follows in a similar manner to the proof of Lemma 2. Recall that $f^{\pi}(x)=1/\log_{2}(x+1)$. Fixing $d\geq 4$ and divisible by four, we obtain the following bound justified below:

where the final inequality in (60) follows since $\log_{2}(d/2+1)-\log_{2}(3d/8+1)$ is increasing in $d$ and $d\geq 4$ by assumption. Moreover, $\log_{2}(d/2+1)\log_{2}(\lfloor 3d/8\rfloor+1)\leq\log_{2}^{2}(d)$ for $d\geq 4$. The final inequality in (59) holds since $\log_{2}(3)-\log_{2}(12/8+1)\geq 1/4$ and

Let us begin with $d\in\{2,3\}$. It is immediate that RAND selects the paper ordering of BID with probability at least $1/6$ since $|\Pi_{d}|\leq 6$. Moreover, any paper ordering selected by RAND cannot obtain higher expected gain from the final reviewer than SUPER∗ since it is optimal for the final reviewer. Accordingly, combined with the bound on BID from (37) which holds for any $d\geq 2$, we obtain for $d\in\{2,3\}$,

We now focus on $d>3$ and not divisible by four. The problem construction we consider is similar to that from Lemma 4 where the number of papers was odd and it was derived from including a paper with zero similarity score and a bid as an extra paper to the problem construction from Section A.3.3. We follow the same approach, but let $d^{\prime}$ be the maximum number divisible by four such that $d^{\prime}<d$ and consider an identical problem construction for the papers in the set $[d^{\prime}]$, but then include $d-d^{\prime}$ extra papers with zero similarity and a bid. This change is such that the papers in the set $\{d^{\prime}+1,\dots,d\}$ are shown after the papers in the set $[d^{\prime}]$ by SUPER∗ and the expected gain from them is deterministically zero since the similarity scores are zero.

In particular, let the similarity scores for the final reviewer be

and the number of bids on the papers from previous reviewers be

Following the exact reasoning from the proof of Lemma 4, we conclude \pi^{\texttt{SUPER}\text{{}^{*}}}_{n}(j)=j for each $j\in[d]$.

For this construction and RAND, we need to lower bound (23). We simplify the expression by substituting the similarity scores and the number of bids on each paper, and the paper ordering presented by SUPER∗ for this construction to obtain

where the terms for papers in the set $\{d^{\prime}/2+1,\dots,d\}$ dropped out since the similarity scores are zero. From this point, it is clear that the analysis beginning from (38) in Section A.3.4 can be repeated as a function of $d^{\prime}$ to obtain the bound

Since $d^{\prime}\geq d-3$, we obtain for $d>3$ and not divisible by four,

where the final inequality follows from the facts that $\log_{2}^{2}(d-3)\leq\log_{2}^{2}(d)$ and $d-3\geq d/3$ for $d\geq 5$.