A SUPER∗ Algorithm to Optimize Paper Bidding in Peer Review

Tanner Fiez 1 Nihar Shah 2 Lillian Ratliff 1

Abstract
A number of applications involve the sequential
arrival of users, and require showing each user a
set of items. It is well known that the order inwhich the items are presented to a user can have asignificant impact on the performance of the system, due to phenomenon such as primacy effects.
An example application (which forms the focusof this paper) is the bidding process in conference
peer review. Here reviewers enter the system sequentially, each reviewer needs to be shown thelist of submitted papers, and the reviewer then“bids” to review some papers. In deciding on theordering of the list of papers to show, there are
two competing goals: (i) satisfying reviewers byshowing them relevant items, and (ii) obtaining
sufficiently many bids for each paper to ensurehigh quality reviews for all papers. In this paper,
we first develop a framework to study this problem in a principled manner. We then design analgorithm called SUPER∗ , inspired by the A∗ algorithm, for this goal. We show that SUPER∗ has
a number of attractive properties (some analogous
to that of A∗ ). Finally, we conduct experiments
which reveal that our algorithm is quite robust to
the complexities arising in the real world.

1. Introduction
It is well-known that peer review is an essential process for
ensuring the quality and scientific value of research (Blacket al., 1998; Thurner & Hanel, 2011). One of the more
daunting challenges in peer review is matching or assigning papers to qualified and willing reviewers. Bidding has
emerged as a mechanism for aiding in and improving thisprocess under the guise that 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 phase begins, reviewers enter the system in an arbitrary sequential
order. Upon entering, a list of papers is shown and thereviewer places bids on papers they would prefer to review.
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 & Preuss, 2013). From theperspective 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 (i), the platform aims tochoose a display order for each reviewer such that following
the bidding process, each paper has at least a certain numberof bids. The main objective of ensuring a minimum numberof bids on each paper is to improve review quality for all
papers (Shah et al., 2018). The well-documented primacy
effect suggests that papers shown on top of the ordering are
the ones on which reviewers are more likely to bid. Thisobjective, strongly suggests that papers with few bids shouldbe placed relatively high in the list.
With regard to (ii), the platform aims to choose an orderingof papers to display that are ‘well-matched’ to the particularreviewer. That is, the set of papers to be displayed is the setof papers on which the particular reviewer is most likely tobid. There are a number of reasons to select well-matchedpapers: for instance, showing poorly matched papers at
the top may cause the reviewer to opt-out and disengage
with the system even if further down the list there was an
option on which they would have happily bid. In particular,a poorly selected ordering may result in a significantly lower
overall bid quantity from a particular reviewer.
There is a limited amount of fundamental research on the
problem of optimizing the display order during the bidding
process, and much less so in consideration of both of theobjectives identified above. In practice, the display orderis typically determined via heuristics such as a predetermined fixed ordering (e.g., order of submission), ordering
by number of bids, or ordering by ‘similarity scores’.

1

Department of Electrical and Computer Engineering, University of Washington 2 Machine Learning and Computer Science
Departments, Carnegie Mellon University. Correspondence to:Tanner Fiez <fiezt@uw.edu>.
Real-World Sequential Decision Making Workshop at ICML 2019.
Copyright 2019 by the author(s).

Poor bidding can in fact have a significant negative impact
on the overall quality of the review process (Rodriguez et al.,2007). One of the key reasons that bidding can fail is that papers are suboptimally displayed to the reviewers. Consider
a paper that is not an ideal match for any of the reviewers inOptimizing Paper Bidding in Peer Review

the system. If papers are ranked for display simply by how
well matched they are to reviewers (e.g., by commonly usedsimilarity score), this particular paper may be very low inthe ranking and hence, not receive many, if any, bids. For
instance, a recent study from (Shah et al., 2018) conductedon the Neural Information Processing Systems (NeurIPS)
2016 conference revealed that 1090 papers (out of the 2000
used in the study) had no positive bids at all.
On the other hand, if papers are inversely ranked by thecurrent number of bids they have, then papers with low bids
are more likely to be higher up on the list regardless of
how well-matched they are to a particularly 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 thereport of a study of 42 peer-reviewed conferences in Computer Science, it was observed that under a fixed ordering,
the number of bids decreases with relative order of submission (Cabanac & Preuss, 2013). It was concluded that thelater the paper is submitted, the less bids it will receive.
Given the shortcomings of existing peer review bidding
systems, we study the important problem of selecting theordering of papers to display to each arriving reviewer
from a fundamental perspective. We begin with a formal
problem description in the next section, and then move on
to present our main results.

deciding the ordering, one has access to the actual bids by all
reviewers who arrived in the past (but does not have accessto the bids made by the current or future reviewers). In thissetting, the goal is to optimize the following objective.
Objective (gain function). Any algorithm to determine
the ordering of papers must trade-off between two competing objectives: ensuring that each paper receives at least areasonable number of bids and ensuring that each reviewer
gets to see relevant papers at the top. A combination of these
two objectives will comprise our “gain function,” which is
the objective we aim to optimize. We first separately discuss
the two competing objectives.
Paper-side objective: The paper-side objective is associatedwith a given function γp : {0, . . . , n} → R. At the end of
the entire bidding procedure, the paper-side objective isP
G p = j∈[d] γp (gj ),where gj is the number of bids received by paper j. We
assume that the function γ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.

2. Problem Statement

While our algorithm handles general functions γp , we discuss two examples here for concreteness. One choice, associated with a given parameter r ≥ 1, is γp (x) = min{x, r}
and indicates that the program chairs emphasize having atleast r bids per paper, but fewer√ bids also provide utility. A
second example is γp (x) = x, which is a smooth functionof x and also captures the diminishing returns on bids.

Let d denote the number of papers and n denote the numberof reviewers. For each reviewer-paper pair, we have accessto a similarity score that captures the similarity between thereviewer and the paper. We use the notation Si,j ∈ [0, 1]
to denote the given similarity between any reviewer i ∈ [n]and paper j ∈ [d]. A higher value of the similarity indicatesa greater relevance of the paper to that reviewer. There arevarious systems (Price et al., 2010; Charlin & Zemel, 2013)in use today that compute the similarities, and in our work,
we will treat them as being given.

Reviewer-side objective: In the bidding process, we wish toensure that reviewers are shown papers with high relevanceat the top. For any reviewer i ∈ [n], we let πi ∈ Πddenote the ordering (permutation) of the papers shown to
the reviewer. Let Si,: ∈ [0, 1]d denote a d-length vector
representing the similarities of reviewer i with the d papers.
The reviewer-side gain is associated with some pre-specified
function γr : [d] × [0, 1] → R and defined byPP
G r = i∈[n] j∈[d] γr (πi (j), Si,j ).

In the bidding period, reviewers sequentially arrive into thesystem. The goal is to determine the ordering of the papers
to show to a reviewer on arrival. We assume for simplicity
that a reviewer arrives only after the previous reviewer has
completed their bidding. We do not make any assumptions
on the order of arrival of the reviewers.

The function γr is assumed to be continuous, as well as
non-increasing in the position and non-decreasing in thesimilarity to reflect the objective.

Let Πd denote the set of all possible d! permutations ofd papers. In what follows, for any reviewer i ∈ [n], we
let πi ∈ Πd denote the ordering of the papers shown toreviewer i. We additionally use the notation πi (j) to denotethe position of paper j ∈ [d] in the ordering πi . When

There are several suitable choices for the function γr . A
function commonly found in data mining, known as Discounted Cumulative Gain (DCG) (Järvelin & Kekäläinen,
2000), which we consider for our application, is given by:
γr (πi (j), Si,j ) =2Si,j − 1,
log2 (πi (j) + 1)

where we have set the “relevance” parameter in DCG to be
the similarity Si,j .

Optimizing Paper Bidding in Peer Review

Overall gain function: Finally, we assume there is a hyperparameter λ ≥ 0, chosen by the program chairs, which
trades off between these two objectives:
E[G] = E G p + λG r ,where the expectation is taken over the randomness in thebids made by the reviewers and any randomness in thealgorithm. The goal is to determine the orderings of papers
to show to each reviewer in order to maximize the expectedvalue of the overall gain. The expectation is necessary since
the bids by reviewers are stochastic, as explained below.
Reviewer bidding model. An important aspect of any
system that displays a list is the presence of primacy effects. In the context of our problem setting, the primacy
effect means a reviewer is more likely to bid on a paper
shown at the top of the list rather than much later. We
capture this using a pre-specified non-increasing function
f : {1, . . . , d} → [0, 1], where f (x) captures the primacy
effect at position x. A second aspect of bidding is that areviewer is more likely to bid on papers with greater similarity, although the reviewer may not bid on exactly the highest
similarity papers since the similarities are noisy. We now
encapsulate both these aspects by assuming each reviewer ibids on papers independently with probability
P(reviewer i bids on paper j) = Si,j × f (πi (j)) ∀ j ∈ [d].
Baselines. The following are three baselines to which wecompare. These baselines are used commonly in practice.
Random baseline (RAND): A commonplace practice is toshow the papers to reviewers in some fixed order, such as, inorder of submission of the papers. We consider a variant of
this practice, in which each reviewer is shown a randomly
selected paper ordering.
Similarity baseline (SIM): A second commonplace practiceis to order the papers according to their similarities. In otherwords, any reviewer i ∈ [n] is shown the papers in order ofthe values in Si,: (where the paper with maximum similarity
is shown at the top, and so on). Any ties are broken byshowing papers with fewer bids higher, and further ties arebroken uniformly at random.
Bid baseline (BID): A third baseline shows papers in orderto greedily optimize the minimum bids. Each reviewer isshown papers in increasing order of bids received so far(from the reviewers who arrived before this reviewer). Any
ties are broken in favor of the paper with a higher similarity,and further ties are broken uniformly at random.

gain function is coupled between the orderings of papers
presented to all reviewers and cannot be realized until theentire bidding process is complete. Conversely, the reviewerside gain is decoupled across reviewers so that the choices ofan algorithm prior to and after a reviewer arrives do not alter
the reviewer-side gain that can be obtained from any given
reviewer. Thus, an algorithm for this problem is required
to make local decisions, where the effect of the decisionon the global gain (or cost) is only partially known. This
perspective is reminiscent of the A* algorithm (Hart et al.,1968), and using A* as an inspiration, we now present analgorithm which we call SUPER∗ for our problem1 .
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 first
discuss the heuristic in the context of the problem at hand.
3.1. Heuristic for future bids.
In a manner analogous to the A* algorithm, at any point intime 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 areviewer, an estimate of the number of bids each paper will
receive in the future. Formally, let us index the reviewers as
1, . . . , n in the order of their arrival (note that this order is
unknown a priori). The heuristic comprises a collection ofvectors h1 , . . . , hn , where each hi ∈ {0, . . . , n}d represents
an estimate of the number of bids each of the d papers will
receive from all future reviewers {i + 1, . . . , n}. The vector
hi is provided to the SUPER∗ algorithm on arrival of the
ith reviewer. Two examples of heuristic functions that we
consider in the subsequent narrative are defined as follows:• Zero heuristic: hi = 0 for every i ∈ [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, forevery i P
∈ [n − 1], the mean heuristic
P is defined asnhi = f0 i0 =i+1 Si0 ,: where f0 = d1 j 0 ∈[d] f (j 0 ).

3. SUPER∗ Algorithm

We set hn = 0, implying that there will be no more bids
on any paper after the last reviewer. This is analogous tosetting the heuristic value to zero for the target vertex in the

The key challenge in designing a suitable algorithm for the
problem at hand stems from the fact that the paper-side

1
The name SUPER∗ stands for SUperior PERmutations andalso indicates the inspiration from A*.

Optimizing Paper Bidding in Peer Review

Algorithm 1: SUPER∗

Algorithm 2: FindPaperOrder

Input: γp : {0, . . . , n} → R, paper-side gain function
γr : [d] × [0, 1]d → R, reviewer-side gainf : [d] → [0, 1], bidding modelλ ≥ 0, hyper-parameter on reviewer-side gainS ∈ [0, 1]n×d , similarity matrix.
Algorithm:

1. Compute weight matrix w ∈ Rd×d such that

1. Initialize bids on each paper to zero: g1 ← 0d
2. For each reviewer arrival i ∈ [n](a) Compute or take input heuristic hi ∈ {0, . . . , n}d(b) πi ← FindPaperOrder(c) Present papers to reviewer in an order following πi(d) Observe vector of bids bi ∈ {0, 1}d(e) Update paper bid counts: gi+1 ← gi + bi

wj,k ← λγr (k, Si,j )+ Si,j f (k)(γp (gi−1,j + hi,j + 1) − γp (gi−1,j + hi,j ))2. Solve linear program to obtain x∗ ∈ Rd×d :X X
x∗ = arg max
wj,k xj,kx∈[0,1]d×d

s.t.

X
k∈[d]

j∈[d] k∈[d]

xj,k = 1 ∀ j ∈ [d],

X
j∈[d]

xj,k = 1 ∀ k ∈ [d].

3. πi (j) ← k such that x∗j,k = 1 for each j ∈ [d]Output: πi

A* algorithm.
3.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 isthe inability to realize the paper-side gain until the end of
the bidding process, we begin by considering the setting
when (n − 1) reviewers have already departed, and the
problem is to determine the ordering of papers shown to
the final reviewer. In this scenario, we have access to thebids of all (n − 1) reviewers that have already arrived andthe orderings of papers presented to them. We use thenotation gn,j ∈ {0, . . . , n} to denote the number of bids
received by any paper j ∈ [d] at the time of arrival of thelast reviewer. The values gn,1 , . . . , gn,d are thus known at
the time when the final reviewer arrives. As a result, we canformulate an optimization problem for the final reviewer n
to maximize the gain (2) in the following manner. For everyj ∈ [d], let Bn,j denote a Bernoulli random variable withmean Sn,j f (πn (j)) independent of all else. The randomvariable Bn,j represents the bid of the final reviewer on
paper j. The optimization problem can be written as:Parg maxj∈[d] E[γp (gn,j + Bn,j )]πn ∈ΠdP+ λ j∈[d] γr (πn (j), Sn,j )(1)computationally efficient manner. 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 fora general reviewer, say, i ∈ [n]. When reviewer i arrives, wehave access to the number of bids made by all past reviewers
on any paper j, which we denote by gi,j ∈ {0, . . . , i − 1}.
We now recall the A* algorithm: for any vertex, A* considers the cost “g” so far and a heuristic estimate “h” ofthe cost-to-go. Then, considering the cost of any vertex
as “g + h”, the A* algorithm takes the action which is theone-step optimal action (i.e., chooses the neighboring vertex
with the smallest value of “g + h”).
In an analogous fashion, SUPER∗ considers the numberof bids so far (gi ) and takes as input a heuristic (hi ) for
the number of bids in the future. Then, considering thenumber of bids from all other reviewers as “gi + hi ”, theSUPER∗ algorithm takes the action which is the one-step
optimal action. In other words, SUPER∗ solves for each
paper ordering using:X
arg max
E[γp (gi,j + hi,j + Bi,j )]πi ∈Πd

j∈[d]

+λ

X

γr (πi (j), Si,j )

(2)

j∈[d]

where the expectation is taken over the distribution of therandom variables Bn,1 , . . . , Bn,d .

where Bi,j is a Bernoulli random variable with meanSi,j f (πi (j)) independent of all else.

Observe that the constraint set for the optimization problem
in (1) is the set Πd of all permutations. This set is, ingeneral, not very well behaved (Ailon et al., 2008; Shahet al., 2016), which makes even this one-step optimization achallenge. As we discuss later (in Theorem 1 and its proof),
SUPER∗ for the final reviewer optimally solves (1) in a

3.3. SUPER∗ formal description
The SUPER∗ algorithm is in Algorithm 1. Each time areviewer arrives, SUPER∗ calls to a routine, FindPaperOrder (Algorithm 2), which uses the information available
to SUPER∗ and determines an ordering of papers to show.

Optimizing Paper Bidding in Peer Review

0

20
10

200
300
400
Number of papers

500

0

−20

0
100

20

100

(a)

200
300
400
Number of papers

500

Relative gain

10

30

30

30

Relative gain

20

Relative gain

Relative gain

Relative gain

40

40

30

20

10

0
100

200
300
400
Number of papers

(b)

(c)

500

20

10

0
100

200
300
400
Number of papers

(d)

500

100

200
300
400
Number of papers

500

(e)

√
1
Figure 1. (a) Model holds and γp (x) = x; (b) Model holds and γp (x) = min{x, 3}; (c) f (x) is assumed to be log (x+1)
but instead it
2
is f (x) = √1x ; (d) n/2 reviewers out of the n reviewers arrive to bid; (e) Poisson(1) reviewers arrive at each discrete time interval. The√
paper-side gain function in (c–e) is γp (x) = x. The gain reported in the figures is relative to the RAND baseline.

In the proof of Theorem 1, we show the problem in (1)can equivalently be formulated as the linear program with a
totally unimodular constraint set. As a result, the optimal solution is integer valued. In fact, the optimization problem isin the form of the linear assignment problem and the optimal
solution can be obtained with a time complexity of O(d3 )using the Hungarian algorithm. The FindPaperOrder subprocedure exactly solves this problem. In Appendix B, we
discuss conditions under which a solution can be obtainedin a more efficient manner from a simple sorting routine that
requires a time complexity of only O(d log(d)).

4. Theoretical Results
SUPER∗ has a number of attractive theoretical properties,
including some analogous to the A* algorithm. We discuss
one such property (“local optimality”) here and relegate therest to a future longer version of the paper.
The property of local optimality, as the name suggests,
means that the algorithm is optimal with respect to thereviewer under consideration. Achieving even a good local
performance in a computationally efficient manner is challenging due to the optimization over permutations in (1).
The following result shows that SUPER∗ , which is computationally efficient, is indeed locally optimal. The result ispresented in terms of the final reviewer for simplicity.
Theorem 1 (Local optimality). SUPER∗ , with any heuristic,
is optimal for the final reviewer.
The proof of Theorem 1 is provided in Appendix A.

5. Experimental Results
In our simulations, we show the empirical results of theSUPER∗ algorithm with a zero and mean heuristics, along
the baselines described in Section 2. A consistent procedure

is performed to evaluate performance. Given a class of similarity matrix, we sample a similarity matrix and shuffle therows of the matrix so that the order of reviewers is arbitrary
and then simulate each algorithm using this similarity matrix and record the gains obtained. We repeat the process
50 times and track the mean gains and standard error foreach algorithm. We present figures showing the relative
mean gain of each algorithm to the mean gain of the RAND
baseline so it is clear how the relative performance scales.
For each simulation we consider a DCG reviewer-side gain1
function and a bidding function of f (x) = log (x+1). The
2
hyper-parameter λ is selected so that each component of thegain function is nearly equal. The similarity matrix class
we consider is matrices of rank 10 generated from summing
rank-1 matrices for which the vectors are drawn from a Beta
distribution with parameters α = 5, β = 2. We fix thenumber of reviewers to be 100 and sweep the paper count.
We begin showing simulations for situations that faithfullyreflect our model.
In Fig. 1a the paper-side gain function√
is γp (x) = x and in Fig. 1b the paper-side gain function is γp (x) = min{x, 3}. For the remaining√ simulations,the paper-side gain function is γp (x) = x. In Fig. 1c
we show an example where the assumed bidding model1
is f (x) = log (x+1), but the underlying bidding model is2instead f (x) = √1x . Fig. 1d shows an example where only
half of the reviewers arrive, and the algorithms do not haveknowledge of this event. Finally, in Fig. 1e we show an example where Poisson(1) reviewers arrive at once, and eachalgorithm must present paper orderings to each at once.
The simulations show our proposed algorithm performs
well when the model holds, and can be robust to realistic
scenarios where the model fails to hold. While we only
show results for a certain similarity matrix class, we observe
qualitatively similar results more generally.

Optimizing Paper Bidding in Peer Review

References
Ailon, N., Charikar, M., and Newman, A. Aggregating
inconsistent information: ranking and clustering. Journalof the ACM (JACM), 55(5):23, 2008.
Black, N., Van Rooyen, S., Godlee, F., Smith, R., and Evans,
S. What makes a good reviewer and a good review for ageneral medical journal? Jama, 280(3):231–233, 1998.
Cabanac, G. and Preuss, T. Capitalizing on order effects
in the bids of peer-reviewed conferences to secure reviews by expert referees. Journal of the American Society
for Information Science and Technology, 64(2):405–415,
2013.
Charlin, L. and Zemel, R. The toronto paper matchingsystem: an automated paper-reviewer assignment system.
2013.
Di Mauro, N., Basile, T. M., and Ferilli, S. Grape: An expert
review assignment component for scientific conference
management systems. In International conference on
industrial, engineering and other applications of applied
intelligent systems, pp. 789–798. Springer, 2005.
Diaconis, P. and Graham, R. L. Spearman’s footrule as ameasure of disarray. Journal of the Royal Statistical Society: Series B (Methodological), 39(2):262–268, 1977.
Hart, P. E., Nilsson, N. J., and Raphael, B. A formal basis
for the heuristic determination of minimum cost paths.
IEEE transactions on Systems Science and Cybernetics,
4(2):100–107, 1968.
Järvelin, K. and Kekäläinen, J. Ir evaluation methods for
retrieving highly relevant documents. In Proceedings ofthe 23rd annual international ACM SIGIR conference on
Research and development in information retrieval, pp.
41–48. ACM, 2000.
Price, S., Flach, P. A., and Spiegler, S. Subsift: a novel application of the vector space model to support the academic
research process. In Proceedings of the First Workshop
on Applications of Pattern Analysis, pp. 20–27, 2010.
Rodriguez, M. A., Bollen, J., and Van de Sompel, H. Mapping the bid behavior of conference referees. Journal of
Informetrics, 1(1):68–82, 2007.
Shah, N., Balakrishnan, S., Guntuboyina, A., and Wainwright, M. Stochastically transitive models for pairwise
comparisons: Statistical and computational issues. In International Conference on Machine Learning, pp. 11–20,
2016.
Shah, N. B., Tabibian, B., Muandet, K., Guyon, I., and
Von Luxburg, U. Design and analysis of the nips 2016 review process. The Journal of Machine Learning Research,
19(1):1913–1946, 2018.

Thurner, S. and Hanel, R. Peer-review in a world withrational scientists: Toward selection of the average. The
European Physical Journal B, 84(4):707–711, 2011.

Optimizing Paper Bidding in Peer Review

A. Proof of Theorem 1
Proof. We consider optimizing the objective to determine the ordering of papers to present a reviewer, given the history ofobservable information and a heuristic. In this proof, we show that selecting the optimal ordering to present to the final
reviewer can be reduced to an optimization problem that can be solved efficiently. Since the SUPER∗ algorithm solves thisoptimization problem to determine an ordering of papers to present the final reviewer, it is an optimal algorithm for the final
reviewer.
We now formally define the history available to an algorithm when a reviewer arrives.
Definition 1 (History). The history available to an algorithm when a reviewer arrives is defined as the set containing theorderings presented and the bids obtained from each reviewer previously. The history set available when reviewer i ∈ [n]arrives is defined as Hi−1 = {πs , bs : s = 1, . . . , i − 1} where πs is the paper ordering presented to reviewer s and bs
contains the bid realizations on each paper. Observe that the number of bids on each paper when a reviewer arrives isdeterministic given the history.
The optimization problem for the final reviewer n isX
X X
arg max
E[γp (gj )|Hn−1 ] + λE[γr (πi (j), Si,j )|Hn−1 ]
πn

s.t.

j∈[d]

(3)

i∈[n] j∈[d]

π n ∈ Πd ,where the expectation is taken over the randomness in the bid to be placed by the reviewer. Equivalently, the optimization
problem is defined asXX
arg max
E[γp (gn−1,j + Bn,j )] + λγr (πn (j), Sn,j )
πn

s.t.

j∈[d]

j∈[d]

π n ∈ Πd .

This representation follows from simplifying the expression and removing terms that do not depend on the optimization
variable. The number of bids on paper j ∈ [d] is expressed as the sum of the deterministic number of bids on the paper prior
to the final reviewer denoted as gi−1,j and a Bernoulli random variable Bn,j with parameter Sn,j f (πn (j)) representing therandom bid of the final reviewer on the paper.
We can simplify the paper-side loss term by expanding the expectation for each j ∈ [d]. Observe that(γp (gn−1,j + 1) w.p. Sn,j f (πn (j))γp (gn−1,j + Bn,j ) =.
γp (gn−1,j )w.p. 1 − Sn,j f (πn (j))
Hence,
E[γp (gn−1,j + Bn,j )] = Sn,j f (πn (j))γp (gn−1,j + 1) + (1 − Sn,j f (πn (j)))γp (gn−1,j )= Sn,j f (πn (j))(γp (gn−1,j + 1) − γp (gn−1,j )) + γp (gn−1,j ).

Dropping the term that does not depend on the optimization variable gives the problem
XX
arg max
Sn,j f (πn (j))(γp (gn−1,j + 1) − γp (gn−1,j )) + λγr (πn (j), Sn,j )
πn

j∈[d]

j∈[d]

s.t. πn ∈ Πd .
We now reformulate the problem into an integer programming problem as follows:
X X
X X
arg max
Sn,j f (k)(γp (gn−1,j + 1) − γp (gn−1,j )) · xj,k + λγr (k, Sn,j ) · xj,kx∈Rd×ds.t.

j∈[d] k∈[d]

X
k∈[d]

X
j∈[d]

xj,k = 1 ∀ j ∈ [d]xj,k = 1 ∀ k ∈ [d]xj,k ∈ {0, 1} ∀ j, k ∈ [d].

j∈[d] k∈[d](4)

Optimizing Paper Bidding in Peer Review

In this formulation
x is a d × d matrix for which xj,k is an indicator of paper j ∈ [d] being shown at position k ∈ [d]. The
P
constraint k∈[d] xj,k = 1 ∀ j ∈ [d] ensures each paper is included strictly once in the ordering shown to the reviewer. The
P
constraint j∈[d] xj,k = 1 ∀ k ∈ [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. Since the constraint matrix is totally unimodular, we can simplify the final
constraint to be 0 ≤ xj,k ≤ 1 ∀ j, k ∈ [d] and the optimal solution will be the integral optimal solution. For notational
purposes, we now define weights
wj,k = Sn,j f (k)(γp (gn−1,j + 1) − γp (gn−1,j )) + λγr (k, Sn,j ) ∀ j, k ∈ [d].
The optimization problem arising from recognizing that the integer constraint can be relaxed and substituting the weights wedefined is as follows
X X
x∗ = arg max
wj,k xj,kx∈Rd×ds.t.

j∈[d] k∈[d]

X
k∈[d]

X
j∈[d]

xj,k = 1 ∀ j ∈ [d]xj,k = 1 ∀ k ∈ [d]0 ≤ xj,k ≤ 1 ∀ j, k ∈ [d].
This optimization problem is in the form of the linear assignment problem. As a result, using the Hungarian algorithm theoptimal solution can be obtained with a time complexity of O(d3 ). The position paper j ∈ [d] is shown to reviewer i ∈ [n]is extracted from x∗ using the relation πi (j) = k such that x∗j,k = 1.
Optimality of SUPER∗ . The SUPER∗ algorithm solves the problem given above for the final reviewer with any heuristic
since hn = 0. As a result, it is optimal for the final reviewer.

B. Computationally More Efficient SUPER∗ in Certain Settings
We now consider when it is feasible to obtain a problem formulation that can be solved with improved time complexity
under certain conditions. The problem in (3) can be formulated in a favorable way when the reviewer-side gain function γrand the bidding model function f are of an equivalent form. Precisely, when each function is of a fractional form with thedependence on the position a paper is shown only appearing in the denominators, we can obtain the following optimization
problem directly from (4):X
arg max
αi,j f (πi (j))
πi
j∈[d]
(5)
s.t. πn ∈ Πd ,where
αi,j = Si,j (γp (gi−1,j + hi,j + 1) − γp (gi−1,j + hi,j )) + λγ˜r (Si,j ) ∀ j ∈ [d],and γ˜r is a function only including the numerator of γr and no longer depending on the paper ordering that is presented.
We can also consider this formulation when the hyper-parameter on the reviewer-side gain function is set to zero so that
reviewer-side gain function no longer factors into the objective.
The optimal solution to (5) is simply to order the papers in decreasing order of their corresponding values of αi,j and, as aresult, requires a time complexity of just O(d log(d)). To be explicit, we obtain the solution using the relation πi = r(αi ),where r : Rd → [d]d is a function that returns the rank from maximum to minimum of each input in place given a vector ofordered inputs.