A One-Size-Fits-All Approach to Improving Randomness in Paper Assignment
Authors: Yixuan Even Xu
Steven Jecmen
Zimeng Song
Fei Fang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: peer review
randomized paper assignment
mitigating malicious behavior
convex optimization
TL;DR: We propose a practical, general-purpose method for randomizing paper assignments in peer review, and show its effect both theoretically and empirically.

Abstract: The assignment of papers to reviewers is a crucial part of the peer review processes of large publication venues, where organizers (e.g., conference program chairs) rely on algorithms to perform automated paper assignment. As such, a major challenge for the organizers of these processes is to specify paper assignment algorithms that find appropriate assignments with respect to various desiderata. Although the main objective when choosing a good paper assignment is to maximize the expertise of each reviewer for their assigned papers, several other considerations make introducing randomization into the paper assignment desirable: robustness to malicious behavior, the ability to evaluate alternative paper assignments, reviewer diversity, and reviewer anonymity. However, it is unclear in what way one should randomize the paper assignment in order to best satisfy all of these considerations simultaneously. In this work, we present a practical, one-size-fits-all method for randomized paper assignment intended to perform well across different motivations for randomness. We show theoretically and experimentally that our method outperforms currently-deployed methods for randomized paper assignment on several intuitive randomness metrics, demonstrating that the randomized assignments produced by our method are general-purpose.

A One-Size-Fits-All Approach to Improving Randomness in Paper Assignment
Yixuan Even Xu
Steven Jecmen2 Zimeng Song Fei Fang?
Tsinghua University
Carnegie Mellon University $Independent Researcher
xuyx20@mails tsinghua. edu. cn
{sj (sjecmen,feif]@ee. cmu, edu
zmsongzm@gmail.. com
Abstract
The assignment of papers to reviewers is crucial part of the peer review processes of large publication venues, where organizers (e.g., conference program chairs) rely on algorithms perform automated paper assignment. As such, a major challenge for the organizers of these processes is to specify paper assignment algorithms that find appropriate assignments with respect various desiderata. Although the main objective when choosing a good paper assignment is to maximize the expertise of each reviewer for their assigned papers, several other considerations make introducing randomization into the paper assignment desirable: robustness to malicious behavior, the ability to evaluate alternative paper assignments, reviewer diversity, and reviewer anonymity. However, it is unclear in what way one should randomize the paper assignment in order to best satisfy all of these considerations simultaneously. In this work, we present practical, one-size-fits-all method for randomized paper assignment intended to perform well across different motiva- tions for randomness. We show theoretically and experimentally that our method outperforms currently-deploeed methods for randomized paper assignment on sev- eral intuitive randomness metrics, demonstrating that the randomized assignments produced by our method are general-purposs.
1 Introduction
Peer review the process in which submissions (such as scientific papers) are evaluated by expert reviewers. It is considered critical part of the scientific process and is commonly used to determine which papers get published in journals and conferences. For concreteness, we set this work in the academic conference setting, although the approach can be generalized to other settings, such as peer review for grant proposals and peer grading elassrooms. Due to the large scale of modern conferences like NeurIPS and AAAL, conference program chairs work closely with assignment algorithms to assign papers to reviewers automatically. Among many other challenges involved in managing huge numbers of reviewers and submissions, these organizers faced with the difficult task of balancing various considerations for the paper assignment. -fiindfrr automated paper assignment algorithms thus crucial for helping them find desirable paper assignments.
In a standard paper assignment setting, set P of np papers need to be assigned reviewers. To ensure each paper gets enough reviewers and no reviewer is overloaded with papers, each paper p in should be assigned to l, reviewers and each reviewer in should receive no more than É, papers. An assignment is represented as binary matrix x in {0, } 8,,, where Tpr indicates that paper is assigned to reviewer r. The main objective of paper assignment is usually to maximize the predicted match quality between reviewers and papers [1] To characterize this,
set R of n,
TTii work was done when Xu was a visiting intern at Carnegic Mellon University.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Maximize Subject to similarity matrix S in R is commonly assumed [17]. Here, Sp.r represents the predicted quality of review from reviewer r for paper p and is generally computed from various sources [8] reviewer and paper subject areas, reviewer-selected bids, and textual similarity between the paper and the reviewer's 's past work [ [H12. Then, the quality of an assignment can be defined as the total similarity of all assigned paper reviewer pairs, i.e. Quality(x)
"E Sp.rSp.r. One standard approach for computing paper assignment is maximize quality I 1 [3] (which we will refer to as the maximum-quality assignment). Variants of this approach have been widely used by existing conferences, such as NeurIPS, AAAI, and ICML (
While the deterministic maximum muxiium-qualiity assignment is the most common, there are strong reasons to introduce randomness into paper assignment that is, to determine a probability distribution over feasible deterministic assignments and sample one assignment from the distribution. Specifically, randomized paper assignments are beneficial due to the following motivations:
Robustness to malicious behavior. Several computer science conferences have uncovered "collusion rings" of reviewers and authors [14 [5], in which the reviewers aim get assigned to the authors' papers in order to give them good reviews without considering their merits. By manipulating their stated expertise and interest (c.g., in the "paper bidding" process), these reviewers can cause the assignment algorithm to believe that their match quality with the targeted papers is very high. In other cases, reviewers may target assignment to a paper with the aim of giving it an unfair negative review [16 Randomization can reduce the probability that malicious reviewer achieves assignment a target paper.
Motivation 1:
Motivation 2: Evaluation of alternative assignments. Accurate reviewer eviewer-paper similarity scores are fundamental for automated paper assignment algorithms. Despite this, these scores are currently computed using various different methods by different conferences [19] 20), with obvious way to tell beforehand which method produces the best-quality reviews. However, after deploying an assignment, it is possible to examine the resulting reviews to counterfactually evaluate the review quality produced by another method of similarity computation that is not deployed. Specifically, using techniques for off-policy evaluation (2i). the randomness of the deployed paper assignment can be utilized estimate the review quality of another non-deployed assignment. The variance of the estimation depends on the overlap in assignment probability between the deployed (randomized) assignment and the non-deployed alternative assignments of interest. Such an evaluation can then inform program chairs on how similarities should be computed (or how other algorithmic choices should be made) in the future.
Motivation 3: Reviewer diversity. As each paper is evaluated by multiple reviewers, it is often desirable to assign set of reviewers with diverse perspectives or areas of expertise. However, since maximum-quality assignments compute only a holistic score to represent the expertise of each reviewer- eriper pair, they do not consider this factor. Randomization can increase diversity by spreading out assignment probability among a larger set of nigh-expertise reviewers.
Motivation 4: Reviewer anonymity. In peer review, reviewer identities are hidden from
authors so that authors cannot retaliate for negative reviews. As a result, conferences are generally reluctant to release paper assignment data since authors may be able to deduce the identities of their reviewers (even if reviewer names and other information are hidden). By sufficiently randomizing the assignment, conferences can make difficult for authors identify any reviewer on their paper with high probability from the assignment data.
Despite the significance of randomness in paper assignment, there is very limited prior work that looks into computing randomized assignments. A notable exception is (22), which proposed an algorithm for computing randomized paper assignments: Probability Limited Randomized Assignment (PLRA). Formally, it represents a randomized assignment as a matrix x in [0, 1|3h, X"., where Tp.r denotes the marginal probability that paper p is assigned to reviewer r. PLRA computes a randomized assignment via the following linear program (LP), defined for given parameter Q E [0, 1] as:
Quality(x) (x) r Fps =lp Ep
Ep.r Sp.
Vp E P, Vr E R, Vp E ER,
(PLRA)
Tp. $ Ey
< Zpr S Q
2

---

where Quality(x) for randomized assignment x is the expected total similarity of the assignment. A deterministic assignment can then be sampled, using the fact that any feasible randomized assignment x can be implemented as a distribution over feasible deterministic assignments 22 23
PLRA is primarily concerned with the first motivation for randomization: robustness malicious behavior. By limiting each entry of x to be at most Q, PLRA guarantees that any malicious target paper has at most probability Q to succeed, even if the
reviewer aiming to be assigned reviewer and paper are chosen adversarially The hyperparameter Q can be adjusted to balance the loss in quality and level of randomization. PLRA has been deployed in multiple iterations of the AAAI conference [ and is implemented at the popular conference management system OpenReview.net (24).
However, PLRA does not fully solve the problem of randomized paper assignment. In particular, PLRA is specific to one metric of randomness: the maximum assignment probability across all paper- reviewer pairs. As result, it is not clear how well PLRA aligns with motivations for randomization other than robustness malicious behavior. Moreover, PLRA does not distinguish between different solutions with the same quality and maximum assignment probability. This means that it often loses opportunities add additional randomness since it neglects to consider non-maximum assignment probabilities. One way to remedy this issue is to allow different values of Q to be set for each pair (p. r). as the original formulation of [22] However, this level of flexibility makes it significant burden for program chairs to manually choose appropriate Q values, hindering the usability of the algorithm. As a result, only the single-Q version stated above has been deployed in practice.
In this work, we address the problem of randomizing paper assignment by looking for a simple and practical method of achieving general purposse randomized paper assignments. We consider various intuitive randomness metrics that are relevant to all above motivations but not overly specific to a particular problem formulation, and aim provide a method that performs well across these metrics. In this way. we can provide a method for randomized paper assignment that conference program chairs can easily deploy without needing to precisely specify objectives hyperparameters.
More specifically, we make the following contributions in this work. (1). We define several metrics to measure the extent to which the randomization in a randomized paper assignment satisfies the stated motivations (Section 3). (2). We propose Perturbed Maximization (PM), a practical algorithm for randomized paper assignment that does not rely any specific formulation of the stated motivations (Section 4. While our algorithm can be implemented using a standard convex optimization solver, additionally propose an approximate implementation that is computationally cheaper. (3). We provide theoretical results showing that PM provably outperforms PLRA on two classes of structured similarity scores (Section 5) (4). We extensively evaluate our algorithm via experiments using two realistic datasets of similarity scores from AAMAS 2015 and ICLR 2018 (Section 6). PM simultaneously performs well on all defined randomness metries while sacrificing a small amount of quality as compared to the optimal non-randoe assignment. Additionally, our experiments show that PM achieves good performance when hyperparameters are set based only on the desired assignment quality, ensuring that it is simple for program chairs to deploy in practice.
2 Related Work
This work follows recent area of research in computer science on paper assignment algorithms for peer review. Building on the standard approach of maximun-simillrity assignment, algorithms have been proposed to handle various additional considerations in the paper assignment: the fair- ness across papers 22 the semiority of reviewers 220,, review processes with multiple phases (3), strategyproofness 25 26 and many others 8 We note here specifically two relevant lines of work.
One motivation for our randomized assignment algorithm is provide robustness to malicious reviewers, problem considered by several past works (27 28). Although our work most closely relates to the randomized paper assignment algorithm proposed in 222. other -on-randome approaches to the problem exist. Leyton- -rronn et al. [20] describe the paper assignment process used at AAAI 2021, which included several additional soft constraints intended to curb the possibility of reviewer-author collusion rings. Wu et al. (29] propose fitting a model of reviewer bidding in order to smooth out irregular bids. Boehmer et al. 30) consider computing paper assignments without short-length cycles in order to prevent quid-pro-que agreements between reviewers.
3

---

Randomization in the paper assignment process has also been used for evaluating different assignment policies. Traditionally, conferences will sometimes run randomized controlled experiments order to test policy changes, where the randomization is incorporated in the assignment of reviewers to different experimental conditions. For example, WSDM 2017 randomly separated reviewers into single- and double-blind conditions in order to evaluate the benefits of double-bling reviewing [31]; other notable experiments include NeurIPS 2014 [32 33,, ICML 2020 [34], and NeurIPS 2021 [35] In contrast, recent work by Saveski et al. [21] proposes method for evaluating alternative assignment policies by leveraging randomization in the paper assignment itself, such as the randomized paper assignments of [22]. By introducing additional randomness at low cost, algorithm provides an improved basis for the methods of [21 and potential future counterfactual policy evaluation methods.
3 Metrics for Randomness and Problem Statement
In Section [ we introduced several motivations for choosing randomized paper assignments: robust- ness to malicious behavior, evaluation of alternative assignments, reviewer diversity, and reviewer anonymity. These indicate that assignment quality is not the only objective that should be considered when choosing paper assignment. In this section, we propose several metries to characterize the extent to which the randomness in a paper assignment is practically useful.
One randomness metric considered by PLRA is maximum probability, defined as Maxprob(x) = maxp.r (xr.). PLRA controls Maxprob in order to trade off between quality and randomness, and thus achieves the greatest possible quality for fixed level of Maxprob. However, as the following example shows, this metric alone is sufficient to fully characterize the randomness of paper assignment since it ignores the structure of the assignment with non-mon mo-maaximm probability.
Subject Area A
Subject Area B
Subject Area A
Subject Area B
P1
P2
P3
P4
P5
P1
P2
P3
P4
P5
3
T3
TA
T5
F
T2
T3
Y4
T5
(a) The ideal assignment
(b) PLRA with Q
Figure 1: Example showing the limitations of PLRA. There are 2 subject areas with 5 papers and 5 reviewers. 6p = E, = 1. The similarity of paper-reviewer pair is 1 they are in the same area. The edge weights denote the assignment probability. (a) shows the ideal assignment with optimal quality. (b) shows an assignment by PLRA with Q 2. which is less randomized than (a) in subject area A.
Fig. depicts a mini-conference consisting of 2 subject areas. Subject area A contains papers and reviewers, whereas subject area B contains 2 of cach. The similarities between reviewers and papers within the same subject area are and similarities across subject areas are O. The constraints are 6p l, i.c., one-to-one assignment. Intuitively, the best randomized assignment matches papers and reviewers uniformly at random within each subject area, like Fig. la since this does not sacrifice any quality. However, PLRA fails to give out this ideal assignment regardless of the hyperparameter choice. Specifically, Q 2 1/2 is required for PLRA to get a maximum -uaalitt--qullttyy assignment, but when Q 1/2, PLRA considers Fig. la and Fig. Ib to be equivalent (in terms of objective value). In fact, infinitely many solutions with the same optimal quality are considered equivalent by PLRA, and current I.P solvers tend return Fig. Tbas as it is vertex solution when Q 1/2. In essence, PLRA is leaving "free randomness on the table," with many practical implications.
Consider the problem of mitigating malicious behavior (Motivation 1), and compare the assignments in Figs. Ia and lb Although they appear to have the same Maxprob, when we only look at subject area A, the Maxprob of Fig. la is lower than that of Fig. lb This indicates that Fig. [a is more robust to malicious behavior within subject area Therefore, Fig. is more desirable.
Moreover, as introduced in Motivation 2, randomness can also be leveraged to evaluate alternative paper assignments using observations of the review quality from deployed, randomized assignment. These techniques rely on a "positivity" assumption: paper-reviewer pairs assigned in the alternative assignment must be given non-zero probability the deployed assignment. Thus, if we spread assignment probability more uniformly among more reviewer-paper pairs, the resulting data can be

---

Maximize Subject to used to evaluate more varied strategies with tighter bounds. In this sense, the assignment in Fig. la will allow us to better estimate the quality of different paper assignments within subject area A.
The failure of PLRA on such a simple example shows that Maxprob alone is an inadequate metric. Thus, we need other metries distinguish between assignments like Fig. 1a and Fig. Tb We therefore propose, in addition to Maxprob, a set of new randomness metrics to capture the neglected low-probability structure of an assignment. Under each of these metrics, uniform assignment considered "more random" than any other assignment, thus distinguishing Fig. la from Fig. lb
(1) Average maximum probability: AvgMaxp(x) -
my Ep max, (Tpr.. With respect to the motivation of preventing malicious behavior, this randomness metric corresponds to the case when target paper is randomly chosen and the reviewer targeting assignment to that paper is adversarially chosen. By minimizing average maximum probability, we will limit the success probability of manipulation in that case.
(2) Support size: Support(x) -p.,"(Eppr > 0). Support size directly relates to the "positivity" assumption introduced above. As there may be many alternative paper assignments of interest, maximizing the support size effectively maximizes the quality of estimation across them.
(3) Entropy:
Entropy(x (x) = - In(xp.r) In information theory, entropy characterizes the uncertainty of a random variable. By maximizing entropy, we maximize the uncertainty of our assignment, corresponding to the idea of maximizing randomness. Note that strictly speaking, assignment x is not a probability distribution, so this definition is generalization.
(4) L2 norm: L2Norm(x) = v V pp.r p.r. To prevent manipulation, PLRA limits the assigned
probability of each pair to be at most a specified value Q. L2 norm relaxes this constraint to a soft one: higher probability results in larger loss. Note that a uniformly random assignment will always have the smallest L2 norm, and so minimizing L2 norm pushes the assignment towards the uniform assignment.
The combination of these metrics more comprchensively captures the impact of randomness on the motivations from Section Moreover, they do so without requiring specific problem formulation for each motivation (e.g., an assumption on the behavior of malicious reviewers, list of the alternative assignments of interest), which are impractical or infeasible to accurately specify in practice.
Problem statement. For an input instance (Ni, Tly, lp, Ey, S), we want to find an algorithm achiev- ing good trade-off between quality and randomness. Specifically, let the maximum possible quality be M. For a given lower bound of assignment quality 1r (n E [0, 1]), we want the algo- rithm produce assignment with lower Maxprob(x), A AvgMaxp(x)) L2 (x) and higher (ntropy Support(x), i.c., good Pareto-frontic of quality and randomness.
4 Perturbed Maximization
In this section, we present our proposed algorithm for randomized paper assignment. To describe it, we first present some definitions.
Definition 4.1 (Perturbation Function). function f [0. 1] [0. 1 is perturbation function (i)
f(0) = 0, (ü) f' exists, (iii) f is non-decreasing on [0, 1] and (iv) f is concave on [0, 1].
Definition 4.2 (Perturbed Quality). For an assignment x, its perturbed quality with respect to perturbation function f on instance (N2, Bl, Ep. L, S) is (Quulityy(x) = -Epr Epprrppm Sprr ((
The definition of perturbed quality incorporates the intuition from the motivating example in the previous section. As function / is concave, the marginal increase of PQuality y (x) from increasing specific entry sprr is diminishing as Fpp. grows. Consequently, the assignment of Fig. will have a higher perturbed quality than that of Fig. [b This naturally gives our new algorithm, Perturbed Maximization (PM). For a given parameter Q [0, 1] and a perturbation function f:
PQuality (x) Ep.r Spr ((xp.r)
Fp. lp
PEEP, Vr R,
(PM)
p Zp.r S Er
xprr SQ
VpEP,rER.
5

---

Note that PM is a class of algorithms induced by different perturbation functions. When the perturba- tion function is chosen to linear function. PM becomes PLRA. In the main experiments of this paper, two specific perturbation functions are considered: (1). Exponential Perturbation Function:
f()) = -aa where a E (0, +00) and (2). Quadratic Perturbation Function: f(z) = x Bax²
where 3 E [0, 1]. Respectively, we will denote PM with fz) 1 e e and f f(x)
-3x² as
PM-Exponeentill (PM-E) and 2M-Quadratic (PM-Q) in the rest of the paper.
In Section 6 we will empirically show that under our settings of hyperparameters, PM-E and PM-Q have almost identical performances on every metric we consider, which suggests that the specific form of the perturbation function has limited impact as long as it is strictly concave. Therefore, there likely no need consider many different types of perturbation functions.
To analyze PM, first notice that the concaveness of function f guarantees that the optimization program is concave. Therefore, we ascent or the ellipsoid method to solve the program in polynomial time. In most of the experiments of this paper, we will use Gurobi [36), a well-known commercial solver, solve PM. While solving PM as general concave optimization problem is conceptually convenient, doing so also incurs high time complexity as there are n, - Tr variables. To further speed up the execution of PM, propose Algorithm I network-flor soork-ffoo-bbseed approximation of PM.
standard concave optimization methods like gradient
Algorithm 1: Network-Flow Flow-Based Approximation PM
For given parameter Q E [0, I]. a perturbation function f and a precision w E N+:
(1) Construct a graph G with a source s, a sink
(2) For paper p. add a vertex Up and an edge s + up with capacity lp w and cost O.
(3) For reviewer r, add a vertex u, and an edge v, - with capacity &, w and cost
(4) For reviewer-paper pair (p, r). add [Q w| edges Up + Uy. The i-th edge has capacity and cost Sp.r [f( - f( (() Let this set of edges be Ep.-
(5) Run maximum cost maximum flow algorithm [7 on G. Define the assignment such that Ep.- [The total flow edges in Ep.,//w.
(6) Enumerate all pairs (p,r) r) in any order and increase Tp.r by min - Fp.r. En Tprr by E, p. J. If Ef p. Zpr = np Ep. return x. Otherwise, return infeasible.
At high level, Algorithm I uses piecewise linear function with pieces approximate the concave function fx) and solves the approximated objective with maximum cost maximum flow. As increase the precision w, the approximation becomes more accurate, but the running time of the algorithm also scales up. Formally, we have the following Theorem |
Theorem 1. Let N+ be the precision in Algorithm 1 and OPT be the optimal perturbed quality.
(a) Algorithum runs in O(w lp n2p n2) time.
Sp.r- Algorithm returns an assignment with perturbed quality ALG 2 OPT -PT--(12) - Sp.r
The proof of Theorem D is deferred to Appendix B.1
Consider the running time of Algorithm given Theorem [ (a). we directly model PM as an optimization problem, the number of variables will be Mp Tyy. The ttate-of-the-art algorithm for solving linear program with n variables to high accuracy has a time complexity of O* (n.2.5 log n) [8]. In contrast, for fixed w, Algorithm works in O(n²) time since é, S n2. Thus, Algorithm has a better time complexity than directly solving PM as an optimization program even if the objective is linear, For non- non-linear perturbation functions, the time complexity of Aggrithm[[rrmmaee while the complexity of solving the optimization program increases. Moreover, by Theorem (b), we can see that as w increases, the approximated perturbed quality ALG approaches OPT, formalizing the intuition that as we increase the precision w, the approximation becomes more accurate. In Section 6 we empirically evaluate the running time and the approximation accuracy of Algorithm We find with w 10, Algorithm produces decently-accuree approximations on our datasets.
the same

---

Theoretical Analysis
In this section, we provide two theorems showing that PM provably outperforms PLRA on general class of input instances. We start with the simpler one inspired by the example in Fig. | Let PLRA(Q) and PM(Q. f) be the of possible solutions of PLRA and PM respectively.
Definition 5.1 (Blockwise Dominant Matrix), A similarity matrix S E 22 X*r is blockwiss dominant E
with block identity
B and block sizes {PI....,Ps), f rw) if 20
A1,1 pixTi
A1,2 pixrs
A 1 XTx
A2,1
1ax
A2, 12xer
A2 1 12xx
S
Ak,1 1 pxxr1
A 1exx2
A 1pxxre/
where Ai, > Aigg Vi + and 1 pxr is a X matrix with all entries being 1. Moreover, define the dominance factor of as Dom(A) sup(a A a a. Vi
Remark. Like Fig. 1 blockwise dominant similarity matrix models a conference with k subject areas where the i-th subject area has pj papers and r; reviewers. The similarity between a paper and a reviewer is determined only by their subject areas, and paper has highest similarity with a reviewer in the same subject area. Note that Dom (A) > 1 as A > Aijj Vi j..
Theorem 2. For an input instance (Np. Tey Ep. ly. S), where S is blockwise dominant with block identity E 18-0 and block sizes {pi...., pa J: {r1,... (rl,...,T TR assume (i) .i..... [Tk are not all equal. (ii) P:: lg TT.. E, Vi {I.....k) and (ii) Q Q-r, 2.2, lp Vi [l....,k] Let f be a strictly concave perturbation function and (0) < Dom ()) PM with f(x) as the perturbation function (weakly) dominates PLRA in quality and all randomness metrics. Formally.
(a) Vx E PM(Q. f). Vy (L)A(Q).
Quality(x) 2 Quality(y), L2Norm(x) LyNorm(y).
Maxprob(x) < Maxprob(y), AvgMaxp(x) < AvgMaxp(y),, Entropy(x) Entropy(y),
Support(x) Support(y).
(b) Vx E PM(Q. f). By e QL)A(Q),
AvgMaxp(x) < AvgMaxp(y), L2Norm(x) < L2Norm(y), Entropy > Entropy(y))
The proof of Theorem follows the same intuition as the example in Fig. The assumptions guarantee that an assignment like Fig. Ial i.e., uniformly matching papers to reviewers within the same subject area, feasible. Details the proof are deferred Appendix B.2 At high level, Theorem
2 shows that with slight restriction on the perturbation function, PM provably performs better than PLRA on blockwise dominant similarity matrices.
Theorem 2 requires a strict restriction on S's structure. In our next theorem, we remove the restriction, stating that PM also outperforms PLRA on random similarity matrix with high probability.
Theorem 3. For an input instance (Tep Thy, Eps S). where each entry of S is i.i.d. sampled from {UI...., Uk (0 < < ... < U&) uniformly, assume (i) k < _ _. "pp. (ii) C, 2 +In(n)), (iii) 2 2.np En S nl Er and (iv) Q (1) 2 ly. Lei f be strictly concave perturbation function and f'(0) fI), Vi {2....,
........ k). With probability 1 1 e D(c) PM with f(x) as the perturbation function (weakly) dominates PLRA in quality and all randomness metrics. Formally,
(a) Vx E PM(Q. f), Vy PLRA(Q),
Quality(x) 2 Quality(y), 1.2Nor((x) < 122orm((y).
Maxprob(x) < Maxprob(y), AvgMaxp(x) < AvgMaxp(y), Support Support(y).
Entropy(x) 2 Entropy(y),
(b) Vx E PM(Q, f). By E PLRA(Q),
Support(x) > Support(y), L2Norm(x) < L2Norm(y), Entropy
> Entropy(y).
The complete proof of Theorem 3 deferred to Appendix B.3 To sketch the proof, we will first
relate PLRA and PM to two simpler auxiliary algorithms using concentration inequality and then
7

---

prove the dominance between them. The assumptions (ii) and (iii) are used to connect PM and PLRA with the auxiliary algorithms, while (i) and (iv) are for proving the dominance.
For Theorem 3 to hold on general random similarity matrices, we have made a major assumption (i), which requires that there are not too many distinct levels of similarity scores. Assumption (i) is naturally satisfied in some cases, For example, when the similarities are derived purely from reviewers' bids, the number of levels becomes the number of discrete bid levels; discrete values can also result when computing similarities from the overlap between reviewer- and author-selected subject areas. When the similarity scores are instead computed from continuous values like TPMS scores [I, assumption (i) is usually not satisfied. In Section 6 we show experiments on both discrete and continuous similarities to evaluate the effect of assumption (i).
Experiments
Datasets. In this section, we test our algorithm on two realistic datasets. The first dataset is bidding data from the AAMAS 2015 conference (39] In this dataset, np = 613, n, = 201, and the bidding data has 4 discrete levels: "yes", "maybe", "no" and "conflict". We transform these 4 levels to similarities 1, 2 and 0, as inspired by NeurlPS 2016, in which similarity scores were computed as 2 (ext + jub [9]. The transformed dataset satisfies assumption (i) in Theorem 3 as there are only 4 levels. The second dataset contains text-similarity scores recreated from the ICLR 2018 conference with np 911, f4, 2435 [26]- These scores were computed by comparing the text of each paper with the text of each reviewer's 's past work; we directly them as the similarity matrix. Assumption (i) is not valid in this dataset as it is contimuous-value
The constraints are set
as l, 3, Er 6 for ICLR 2018 was done in (26) and l, 3, b. 12 for AAMAS 2015 for feasibility. In Appendix A.3 we also test our algorithm on four additional datasets from [39].
Experiment and hyperparameter setting. We implement PLRA and two versions of PM (PM-E and PM-Q) using commercial optimization solver Gurobi 10.0 36. For each algorithm on each dataset, use principled method (Appendix (.2)) to find 8 sets of hyperparameters that produce solutions with at least f80%, 85%, 90%, 95%, 98%, 99%, 99.5%, 100%) ) of the maximum possible quality. When setting the hyperparameters, we choose a "slackness" value 5 and allow PM produce solutions with Maxprob at most ó higher than the optimal Maxprob (in exchange for better performance other metrics). For AAMAS 2015, 5 0.00 and for ICLR 2018, ō 0.02. We refer to Appendix A.2 more details. We do not consider assignments with lower than 80% of the maximum quality since such low-quality assignments are unlikely to be deployed in practice. We evaluate the produced assignments on different randomness metrics to draw Figs. to We also implemented Algorithm and tested with the set of parameters at 95% relative quality create Table [ All source code is released at https: gi thub. com VixuaaEvennu wwwpnnewwwwnueeeuuereeeeeee and all experiments are done on a server with 56 cores and 504G RAM, running Ubuntu 20.04.6.
http://ettrurbddeeeee mwt-mmiiimmmimmmmmmmmmmmmmmmmmmm in
Implementation
Gurobi
Flow (w = 10)
Algorithm
PM-Q
PM-E
PM-Q
PM-E
Wall Clock Time
86.85s
368.13
563.24s
554.07s
Total CPU Time
988.115
3212.18s
562.77s
553.59s
Quality
95%
95%
94%
94%
PQuality
606.55
305.41
603.34
303.68
AvgMaxp (4)
0.87
0.87
0.86
0.86
Entropy (t)
1589.95
1630.80
1575.86
1607.20
Table 1: Comparison of different implementations on ICLR 2018. Downarrows (L) mean the lower the better and uparrows (f) mean the higher the better. Due parallelization, Gurobi takes less wall clock time. However, the network- based approximation uses fewer computation resources (total CPU time). The approximation has relatively accurate Quality, PQuality and randomness metries.
Comparing Gurobi and Algorithm 1 Table [soows that on ICLR 2018, Gurobi takes less wall clock time than Algorithm|| due to parallelization over the server's 112 cores. However, Algorithm|] I takes less total CPU time (system user CPU time) and achieves similar performance with Gurobi, which shows that Algorithm provides decently approximated solutions using fewer computation
8

---

resources. Due to the space limit, rows in Table have been selected and only results on ICLR 2018 are present. The complete tables and analysis for both datasets can found Appendix [ A..
Comparing randomness metrics of PM and PLRA on discrete-valued datasets. As shown in Figs. 2alad D on AAMAS 2015, both versions of PM achieve exactly the same performance with PLRA on Maxprob while improving significantly on the other randomness metrics. Recall that PLRA achieves the optimal quality for given Maxprob. This demonstrates that as predicted by PM produces solutions that are more generally random while preserving the optimality in Maxprob on discrete-ve valued datasets where assumption (i) holds. In Appendix A.3
Theorem 3
we also test our
algorithm on four more datasets from 39] and observe similar results.
1.0
1.00
0.9
PLRA
0.95
Maxprop Maxprop
PM-Q
0.90
0.8
0.85
0.7
PM-E
X 0.80
0.75
0.6
0.70
0.5
0.65
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
1.00
Relative Quality
Relative Quality
(a) AAMAS 2015 Quality Maxprob (4)
(b) ICLR 2018 Quality Maxprob (L)
Figure 2: The trade-off's between quality and Maxprob on both datasets. Downarrows (L) indicate that lower is better. On AAMAS 2015 where assumption (i) of Theorem 3 holds, PM incurs no increase in Maxprob; on ICLR 2018 where it does not hold, PM causes 0.02 increase.
1.0
42.5
0.9
PLRA
40.0
AvgMax
0.7
0.8
PM-E
PM-Q
-
E 37.5
35.0
32.5
0.6
2 30.0
27.5
0.5
25.0
0.4
22.5
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
1.00
Relative Quality
Relative Quality
(a) AAMAS 2015
Quality vs AvgMaxp (4)
(b) AAMAS 2015 Quality L2Norm (L)
60000
3500
50000
3000
Support
40000
2500
2000
30000
1500
20000
1000
10000
500
0
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
1.00
Relative Quality
Relative Quality
(c) AAMAS 2015 Quality vs Support (t)
(d) AAMAS 2015 Quality vs Entropy (t)
Figure 3: The trade-offs between quality and four randomness metrics on AAMAS 2015. Downarrows
(L) indicate that lower better and uparrows (t) indicate that higher is better. The figure shows that PM significantly outperforms PLRA on all four metrics, as predicted by Theorem 3
Comparing randomness metries of PM and PLRA on continuous-valle on ICLR 2018 in Figs. and 4 show that both versions of PM sacrifice some Maxprob as compared to PLRA. The exact amount of this sacrifice is affected by the slackness described in Appendix A.2 However, the improved randomness is still significant, though to a lesser extent than on AAMAS 2015. Note that assumption (i) of Theorem does not hold on ICLR 2018. This exhibits the empirical efficacy of PM beyond the theoretical guarantees provided in Section 5
datasets. The results
3
Comparing randomness metrics of PM-E and PM-Q. In all of Figs.
we can see that no
matter what metric and dataset are used, the performances of PM-E and PM- are always similar.

---

1.00
52.5
0.95
PLRA
50.0
PM-Q
47.5
0.85
NO 45.0
0.80
PM-E
42.5
0.75
40.0
0.70
37.5
0.65
35.0
0.60
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
1.00
Relative Quality
Relative Quality
(a) ICLR 2018 Quality vs AvgMaxp (4)
(b) ICLR 2018 Quality vs L2Norm (L)
12000
3000
2500
10000
Support
Entropy
2000
8000
1500
6000
1000
4000
500
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
1.00
Relative Quality
Relative Quality
(c) ICLR 2018 Quality vs Support (1)
(d) ICLR 2018 Quality vs Entropy (t)
Figure 4: The trade-offs between quality and four randomness metries on ICLR 2018. Downarrows (4) indicate that lower is better and uparrows (f) indicate that higher is better. The figure shows that PM outperforms P on four metrics despite the fact that assumption (i) of Theorem 3 does not hold, indicating the empirical efficacy of PM beyond theoretical guarantees.
This suggests that the specific type of the perturbation function has limited impact as long as it is strictly concave. Therefore, program chairs do not need to carefully consider this choice in practice.
Additional experiments. Due to the page limit on the main paper, we are not able to present all the experiments we run in this section. We refer Appendix A for additional experimental results about the network-flow-bass approximation (Appendix A. hyperparameter tuning (Appendix A.2) and experiments more datasets (Appendix A.3
7 Conclusion
We present a general-purpose, practical algorithm for use by conference program chairs in computing randomized paper assignments. We show both theoretically and experimentally that our algorithm significantly improves over the previously deployed randomized assignment algorithm, PLRA. In conferences that currently deploy PLRA, our algorithm can be simply plugged-in in place of find a paper assignment with the same quality but with an improved level of randomization, achieving various benefits.
In practice, various aspects of paper assignment other than quality and randomness are considered by program chairs. We refer to Appendix Cifor discussions about how to optimize a specific metric with our algorithm (Appendix C.1 and how to incorporate some additional constraints from (20 (Appendix C.2 That being said, we do not consider various other aspects and constraints that may be desired by program chairs: e.g., faimess-based objectives 2 or constraints on review cycles 20
Incorporating these aspects remains an interesting direction for future work.
Broader Impacts. We expect our algorithm to have a mostly positive social impact by assisting program chairs in mitigating malicious behavior, facilitating evaluation of assignments, and increasing reviewer diversity and reviewer amonymity. While deploying a randomized assignment may negatively impact the assignment quality compared to deterministic assignment, work allows conferences to choose the level of randomization that they deem best for their goals.
Aeknowledgments and Disclosure of Funding
This work was supported by ONR grant N00014221218 and NSF grant I1S-2200410.
This work was supported in part by the Sloan Research Fellowship.
10

---

References
[1] Laurent Charlin and Richard S. Zemel. The Toronto Paper Matching System: An automated paper-reviewer assignment system. In ICML Workshop on Peer Reviewing and Publishing Models, 2013.
[2] Ivan Stelmakh, Nihar B. Shah, and Aarti Singh. PeerReview4AAll: Fair and accurate reviewer assignment in peer review. In ALT, 2019.
[3] Steven Jecmen, Hanrui Zhang, Ryan Liu, Fei Fang, Vincent Conitzer, and Nihar Shah, Near- optimal reviewer splitring in two-phase paper reviewing and conference experiment design, In HCOMP, 2022.
[4] Wenbin Tang, Jie Tang, and Chenhao Tan. Expertise matching via constraint-based optimization. In International Conference on Web Intelligence and Intelligent Agent Technology, 2010.
[5] Peter A. Flach, Sebastian Spiegler, Bruno Golénia, Simon Price, John Guiver, Ralf Herbrich, Thore Graepel, and Mohammed J. Zaki. Novel tools streamline the conference review process: Experiences from SIGKDD'09 09. SIGKDD Explorations Newsletter, 2010.
[6] Camillo J. Taylor. On the optimal assignment of conference papers to reviewers. Technical report, Department of Computer and Information Science, University of Pennsylvania, 2008.
[7] Laurent Charlin, Richard S. Zemel, and Craig Boutilier. A framework for optimizing paper matching. In UAI, 2011.
[8] Nihar Shah. Challenges, experiments, and computational solutions in peer review. Communi- cations of the ACM, 2022.
[9] David Mimno and Andrew McCallum. Expertise modeling for matching papers with reviewers. In KDD, 2007.
[10] Xiang Liu, Torsten Suel, and Nasir Memon. A robust model for paper reviewer assignment. In RecSys, 2014.
[11] Marko A. Rodriguez and Johan Bollen. An algorithm to determine peer-reviewers. In CIKM, 2008.
[12] Hong Diep Tran, Guillaume Cabanac, and Gilles Hubert. Expert suggestion for conference program committees. In RCIS, 2017.
[13] Judy Goldsmith and Robert H. Sloan. The AI conference paper assignment problem. In AAAI Workshop, 2007.
[14] T. N. Vijaykumar. Potential organized fraud in ACM/IEEE computer architecture con- ferences. http:://woaiiinnccooo/oototttttp fraudd -n-uddiii-cmmi ieee- cct.pppce..caaaaaccc.....ooooooa 2023.
2020. Accessed February
[15] Michael Littman. Collusion rings threaten the integrity of computer science research. Commu- nications of the ACM, 2021.
[16] Jef Akst. hate your paper. Many say the peer review system is broken. Here's how some journals trying to fix it. The Scientist, 2010.
[17] Edward F. Barroga. Safeguarding the integrity science communication by restraining 'rational cheating' in peer review. Journal of Korean Medical Science, 2014.
[18] Mario Paolucci and Francisco Grimaldo. Mechanism change in simulation of peer review: From junk support to elitism. Scientometrics, 2014.
[19] Nihar B Shah, Behzad Tabibian, Krikamol Muandet, Isabelle Guyon, and Ulrike Von Luxburg. Design and analysis of the nips 2016 review process. Journal of Machine Learning Research, 2018.
11

---

[20] Kevin Leyton- Brown, Yatin Nandwani, Hedayat Zarkoob, Chris Cameron, Neil Newman, Dinesh Raghu, al. Matching papers and reviewers at large conferences. arXiv preprint arXiv:2202. /2273, 2022.
[21] Martin Saveski, Steven Jecmen, Nihar Shah, and Johan Ugander. Counterfactual evaluation of peer review assignment strategies in computer science and artificial intelligence. In NeurIPS, 2023.
[22] Steven Jecmen, Hanrui Zhang, Ryan Liu, Nihar Shah, Vincent Conitzer, and Fei Fang. Mitigating manipulation in peer review via randomized reviewer assignments. In NeurlPS, 2020.
[23] Eric Budish, Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom. Implementing random assign- ments: A generalization of the Birkhoff-von Neumann theorem. In Cowles Summer Conference, 2009.
[24] OpenReview.net. OpenReview matcher. httpa:///gttaaa..omommpppeeeeeep matcher 2023. Accessed April 2023.
[25] Komal Dhull, Steven Jecmen, Pravesh Kothari, and Nihar B Shah. Strategyproofing peer assessment via partitioning: The price in terms of evaluators' expertise. In HCOMP, 2022.
[26] Yichong Xu, Han Zhao, Xiaofei Shi, Jeremy Zhang, and Nihar B Shah. On strategyproof conference peer review. In IJCAI, 2019.
[27] Steven Jecmen, Nihar B Shah, Fei Fang, and Vincent Conitzer. Tradcoff's in preventing manipulation in paper bidding for reviewer assignment. In ML Evaluation Standards Workshop at ICLR, 2022.
[28] Steven Jecmen, Minji Yoon, Vincent Conitzer, Nihar B. Shah, and Fei Fang. A dataset on malicious paper bidding in peer review. In WWW, 2023.
[29] Ruihan Wu, Chuan Guo, Felix Wu, Rahul Kidambi, Laurens Van Der Maaten, and Kilian Weinberger. Making paper reviewing robust to bid manipulation attacks. In ICML, 2021.
[30] Niclas Boehmer, Robert Bredereck, and André Nichterlein. Combating collusion rings is hard but possible. In AAAI, 2022.
[31] Andrew Tomkins, Min Zhang, and William D. Heavlin. Reviewer bias in single- versus double-blind peer review. Proceedings of the National Academy of Sciences, 2017.
[32] Neil D. Lawrence. The NIPS experiment. httpa:///mneeegprrbbbbllllco///2 16/the-nips-a expermmmmmemmntt 2014. Accessed February 1, 2023.
[33] Eric Price. The NIPS experiment. http://blog, mrtz. mmttz..orr/211////////tt---- experiment htmml html 2014. Accessed February 1, 2023.
[34] Ivan Stelmakh, Charvi Rastogi, Nihar B Shah, Aarti Singh, and Hal Daumé III. A large scale randomized controlled trial on herding in peer-review discussions. PLoS ONE, 2023.
[35] Alina Beygelzimer, Yann Dauphin, Percy Liang, and Jennifer Wortman Vaughan. The NeurIPS 2021 consistency experiment. betpss:/bblo neurips wttpccc////////ee/ htt/////ttheeettteeee 2021 Co2sisonsss eereeistteccc-epeeimmeeee 2021. Accessed February 1, 2023.
[36] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023.
[37] Jack Edmonds and Richard M Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 1972.
[38] Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 2021.
[39] Nicholas Mattei and Toby Walsh. Preflib: A library for preferences http://wwwwpreffibborg. In ADT, 2013.
12

---

A Additional Experiments
A.1 Network--Fow-Basel Approximation
In Section we presented Table which is a shortened version of the experimental results comparing Gurobi and Algorithm [
We now present the complete experimental results on both datasets in Tables 2 and B as well as the complete analysis in this section.
Implementation
Gurobi
Flow (w
10)
Algorithm
PLRA
PM-Q
PM-E
PM-Q
PM-F
Wall Clock Time
I.35s
4.06s
17.64s
20.03s
20.63s
Total CPU Time
9.91s
31.13s
79.20s
20.03s
20.61s
User CPU Time
4.94s
23.46s
66.44s
20.03s
20.61s
System CPU Time
4.97s
7.67s
12.76s
0,00s
0.00s
Quality
95%
95%
95%
95%
95%
PQuality
N/A
1232.91
312.78
1230.75
312.22
Maxprob (4)
0.80
0.80
0.80
0.80
0.80
AvgMaxp (4)
0.80
0.74
0.74
0.74
0.74
Support (1)
2501
28108
28099
5849
5853
Entropy (1)
531.40
1953.55
1953.20
1411.82
1411.12
1.2Nrr (1)
37.33
32.33
32.34
32.66
32.68
Table 2: Comparison of different implementations AAMAS 2015. Downarrows (4) mean the lower the better and uparrows (f) mean the higher the better. Due to parallelization, Gurobi takes less wall clock time, However, the network-flor flook-fflow-blr based approximation uses fewer computation resources (total CPU time). The approximation has very accurate Quality and PQuality. Approximated Support and Entropy are significantly worse than Gurobi's, but still significantly better than PLRA's.
Implementation
Gurobi
Flow (w = 10)
Algorithm
PLRA
PM-Q
PM-E
PM-Q
PM-E
Wall Clock Time
21.50s
86.85s
368. 13s
563.24s
554.07s
Total CPU Time
78.41s
988. 11s
3212.18s
562.77s
553.59s
User CPU Time
67.66s
906.72s
2957.54s
562.68s
553.42s
System CPU Time
10.75s
81.39s
254.64s
0.09s
0.13s
Quality
95%
95%
95%
94%
94%
PQuality
N/A
606.55
305.41
603.34
303.68
Maxprob (1)
0.90
0.92
0.92
0.90
0.90
AvgMaxp (1)
0.90
0.87
0.87
0.86
0.86
Support (1)
3648
7122
7480
6250
6432
Entropy (1)
595.25
1,89.95
1630.80
1575.86
1607.20
L2Norm (L)
47.83
42.49
42.45
42.21
42.18
Table Comparison of different implementations on ICLR 2018. Downarrows (L) mean the lower the better and uparrows (t) mean the higher the better. Due to parallelization, Gurobi takes less wall clock time. However, the network-flowe based approximation uses fewer computation resources (total CPU time). The approximation has relatively accurate Quality, PQuality and randomness metries.
Comparing the running time of Gurobi and Algorithm [ As shown in Tables 2 and 3 Gurobi generally runs faster than Algorithm in wall clock time. This because it well-written commercial software that is able to parallelize over multiple cores on our server. However, the sum of user and system CPU time is smaller for Algorithm which shows that Algorithm [ Juses fewer computation resources than Gurobi. Moreover, note that Gurobi takes significantly longer to solve PM-E than PM-Q, while Algorithm supports quadratic objective functions primitively. Therefore, to solve exponential objective functions, iterative approximation methods have be used. contrast, A Algorithm| T can support an arbitrary perturbation function without sacrificing running time.
[ is not affected. The reason for this Gurobi only
13

---

In the rows about Quality and PQuality Tables Saaeesaannd we can see that Algorithm I has almost the same Quality Gurobi. The PQuality of A is also close to Gurobi's. This shows that with 10, Algorithm approximates PM in solution quality well, validating Theorem
Comparing the solution qualities of Gurobi and Algorithm 1
Comparing the randomness metrics of Gurobi and Algorithm 1 As shown in Table 2 for randomness metries Maxprob, AvgMaxp, and L2Norm, the approximated solution by Algorithm has a similar or identical performance to Gurobi on AAMAS 2015. For Support and Entropy. the approximated solution is significantly worse than Gurobi's, ss but it is still significantly better than PLRA's solution. As presented in Table 33 on ICLR 2018, the performances of Algorithm | and Gurobi on all randomness metrics are relatively close. This shows that Algorithm mostly preserves PM's performance on randomness metrics. Although discrete- valued datasets like AAMAS 2015, Support and Enty can be affected, they are still better than PLRA's solution.
A.2 Hyperparameter Tuning
In this section, we will introduce the way in which we do hyperparameter tuning for PM. We start with lemma that shows the monotonicity of the solution quality of PM-Q with respect to 3.
Lemma A.1. For an input instance (M. By: pp: fr, 8), let the solution of PM with fi (I) = z - 8,x
be X1 and the solution of PM with fz(z) = 32x² be X2 where B1, B2 E [0, 1]. Then
31 < B2 Quality(x1) 2 Quality(x2).
Proof of Lemma A.1 Let SQuality(x) = Ep Σ, =2. Then
PQuality, fi (x) Quality(x) (aatttxxx))33SSaaa) 3)SQuality(x),
PQuality fa (x) = Quality(x) 335Quality(x)).
As X maximizes PQuality f. (x) and x2 maximizes PQuality (x(), we have Quality(x:) ( (uSuulltty(x)) 2 Quality(x2) 3;5Qualityxx2), Quality(x1) - (3,SQualityxxi) < Quality(x2) 3,SQuality(x2).
(1)
Subtracting (2) from and using 03 31, we have
(32 Bi (.]uulllayyyx) 2 (32 - -1))SQuality(xx) - SQuality(xi) 2 SQuality(x2).
Then, from 1 we know that Quality(x:) - Quality(X2) 2 ( (SQuallity(xx) SQuality(xe)) 2 0.
Therefore, Quality(x1) 2 Quality(xo))
With Lemma A.I for minimum requirement of quality Quality as= use binary search to find the largest 3 for PM-Q such that PM-Q with f(x) = 2 3x gives an assignment with quality
2 Quality M- Formally, consider the following Algorithm 2
Algorithm 2: Hyperparameter Tuning for PM-Q
For given minimum quality requirement Quality, As and slackness 6:
(1) Use binary search to find QPLRA, the smallest Q with which PLRA gives solution with quality Quality m-
(2) Use binary search to find $max. the largest 3 such that PM-Q with = QPLRA + and f(x = x - f2 gives solution with quality 2 Quality M-
Finalize the hyperparameters (Q,9) (min (QrLRA 1), Bmax)-
Algorithm 2 maximizes the parameter 3 while ensuring the produced assignment with the set of hyperparameters (Q,3) has quality at least Quality, xs and Maxprob at most QPERA + +8. Note that any solution with quality 2 Quality m has Maxprob 2 QPLRA Intuitively, Algorithm
14

---

trying to maximize the randomness while obtaining the minimum required quality and near-optimal Maxprob given the quality constraint.
Analogously, we use similar method for tuning the hyperparameters in PM-E.
Algorithm Hyperparameter Tuning for PM-E
For given minimum quality requirement Quality Ms and slackness 6:
(1) Use binary search find QPLRA. the smallest Q with which PLRA gives a solution with quality Quality
(2) Use binary search to find amax the largest such that PM-E with Q = QPLRA + and f(x) 1 gives solution with quality Quality M
(3) Finalize the hyperparameters as (Q, (min(Qren) (QPLRA 5, 6,1}, Omax)
Although we similarly apply binary search to PM-E as we have done to PM-Q, the monotonicity condition of Lemma A.A.Joosss does not hold in general for PM-E. For instance, consider the following Example [ If we run PM-E with different a and Q = 1, the solution quality is not monotonic with respect a. The results are shown Fig. 5
Example In this example, np Trr 3, lp
4, and
0.4
0.0 0.6
s
0.8
0.6
0.0
0.8
0.6 1.0)
1.000
0.999
Relative Quality
0.998
0.997
0.996
0.995
0.994
0.993
0.0
2.5 5.0
7.5 10.012.515.01..52 Alpha
Figure 5:
The quality of PM-E on Example with Q and different a. The figure shows that the solution quality of PM-E is not necessarily monotonic with respect to a.
Nevertheless, such examples are rare in practice. have examined thousands of examples to find Example [ In fact, the monotonicity of solution quality with respect to can still be observed empirically in the datasets we used. Therefore, for the purpose of our experiments in Section G we will still use Algorithm
3 to tune the hyperparameters of PM-E.
In Algorithms and 3] there are still two parameters be fixed, namely and Quality v- In
Section 6, Quality,, M was already specified as (80%, 85%, 90%, 95%, 98%. 99%, 99.5%, 100%) of maximum possible quality. remains to specify 8. experiments in Section 6 we used 0 for AAMAS 2015 and 0.02 for ICLR 2018. In the rest of the section, we will show experiments about the performances of PM-Q and PM-E with different values to justify our choice. practice, conference program chairs can simply choose small value for the slackness, such as & 0.02.
15

---

0.80
37
PLRA
MgMax
0.79
36
PM-Q
0.78
35
*
PM-E
0.77
34
PM-Q Elbow
0.76
S 33
x
PM-E Elbow
0.75
32-
0.74
31
0.00
0.04
0.08
0.12
0.16
0.20
0.00
0.04
0.08
0.12
0.16
0.20
Delta
Delta
(a) AAMAS 2015 vs Maxp (4)
(b) AAMAS 2015 8 vs L2Norm (L)
30000
2250
2000
25000
Support
1750
20000
1500
15000
1250
10000
1000-
5000
750
0.00
0.04
0.08
0.12
0.16
0.20
0.00
0.04
0.08
0.12
0.16
0.20
Delta
Delta
(c) AAMAS 2015 vs Support (f)
(d) AAMAS 2015 8 vs Entropy (t)
Figure 6: The performances of PM-Q and PM-E on AAMAS 2015 with different Quality m is set to 95% of the maximum possible quality. Downarrows (J) mean the lower the better and uparrows (t) mean the higher the better. The figure shows that the elbow points both algorithms in all four metrics are at 5 0. Therefore, we should set 5 = 0 for AAMAS 20155
0.90
48
0.89
PLRA
0.88
46
PM-Q
0.87
No
44
PM-E
0.86
0.85
S 42
PM-Q Elbow
0.84
PM-E Elbow
0.83
0.82
0.00
0.02
0.04
0.06
0.08
0.10
0,00
0.02
0.04
0.06
0.08
0.10
Delta
Delta
(a) ICLR 2018 vs AvgMaxp (L)
(b) ICLR 2018 8 vs L2Norm (1)
2500
12000
2250-
Support
10000
2000
1750
8000
1500
1250
6000
1000
4000
750
500
0.00
0.02
0.04
0.06
0.08
0.10
0.00
0.02
0.04
0.06
0.08
0.10
Delta
Delta
(c) ICLR 2018 vs Support (t)
(d) ICLR 2018 ō vs Entropy (f)
Figure 7: The performances PM-Q and PM-E on ICLR 2018 with different 8. Quality set to 95% of the maximum possible quality. Downarrows (J) mean the lower the better and uparrows (f) mean the higher the better. The figure shows that the elbow points of both algorithms lie the range 6 E [0.02, 0.04]. We have chosen 8 0.02 in this range.
As we increase 5, we allow PM-Q and PM-E to find more random solutions (i.e., solutions that perform better on our randomness metrics) a cost of larger Maxprob. To balance the gain and we choose that maximizes a linear combination of them. We call these elbow points. Below, we show the choices of graphically in Figs. and
loss,
7 on AAMAS 2015, the elbow points of both algorithms in all four metrics are at 5 = O. Therefore, we should set 5 = 0 for it. On ICLR 2018, the elbow points lie in the range 5 E [0.02, 0.04]. We have chosen 0.02 this range for it.
As shown in Figs. and
16

---

A.3 Experiments on More Datasets
In this subsection, we include additional experiment results on more datasets. In particular, we include Preflibl (00039-1 from [39]. mp 54, n2 = 31), Preflib2 (00039-2 from [39]. n2 = 52, ny 24), Preflib3 (00039-3 from [3) ne 176, n, 146) and AAMAS 2016 (00037-2 from [39]. Up = 442, n, = 161). All of the four datasets are bidding data consisting of 4 discrete levels: "yes", "maybe". "no" and "conflict". We transform these 4 levels to similarities 1, 2. 4
1 and O as done in
Section 6 The constraints are set as Ep = 3, e, 6 for Preflibl and Preflib3. For Preflib2 and AAMAS 2016, (x) are set as (3, 7) and (3. 12) respectively for feasibility.
We use the same experimental setup and hyperparameter setting as in Section 6 The results are shown in Fig. 8 The results of these additional datasets are similar to those on AAMAS 2015 shown in Figs. 2a and 3 In partieular, both versions of PM achieve exactly the same performance with PLRA on Maxprob while improving significantly on the other randomness metrics. This shows that the empirical observations in Section are not dataset-specific and generalize other datasets.
1.0
PLBA
1.0
0.9
0.2
1.0
1.4
0.8
IN-o
0.8
0.8
X
1N-2
3.
007
9.7
05
2.5
0.5
0.00
0.25
2.50
0.95
1.00
0.80
0.85
0.30
5,05
1.00
0.20
0.55
3.30
0,05
1.00
0.00
0.55
5.50
0.55
1.00
(a) Preflibl Quality vs Maxprob (4)
(b) Preflib2 Quality vs Maxprob (4)
(c) Preflib3 Quality vs Maxprob (4)
(d) AAMAS2016 Quality vs Maxprob (4)
1.0
208
206
05
0.30
Setative Quattyy
Reterive Quality
Reterive Quatiy
Seletivn Quaby
(c) Preffibl Quality
(f) Preftib2 Quality AvgMaxp (4)
(g) Preflib3 Quality VS AvgMaxp (1)
(h) AAMAS2016 Quality vs AvgMaxp (4)
vs AvgMaxp (4)
22
35.2
20
5-
2.233
22.3
23.5
400
0.31
2.40
1.00
6300
0.0%
030
GES
3:30 5.09
630
031
2:50 0:45
1.00
Quality
Qurliy
Quality
Qualty
(i) Preflibl Quality vs L2Norm (1)
i Preflib2 Quality vs L2Norm (U)
(k) Preflib3 Quality vs L2Norm (L)
(I) AAMAS2016 Quality vs L2Norm (1)
730
40003
Supteer
632
032
L820 920
4500
12550
DSCO-
2220012
200
202-00
1:0-
2020
1000:
0.35
1.00
0.30
0.30
030
0.30 0.55
0.20
AddttieQuulk Qualiy
Raluive Quality
Rubiive Quality
Adlable Qualit
(m) Preflibl Quality vs Support (t)
(n) Preflib2 Quality vs Support (f)
(0) Preflib3 Quality vs Support (t)
(p) AAMAS2016 Quality vs Support (t)
1800-
15:
850
650
1500
2002
8 100
450
1003
50
250-
500
0.00
0.25
5.50
0.95
1.00
0.80
0.35
0.55
1.02
0.00
0.55
0.20
0.00
1:03
0.80
0.85
3.50
0.95
1.00
Deative Quality
Ratacve Quality
Ratutive Quality
Talative Quality
(q) Preflibl Quality vs Entropy (t)
(r) Preflib2 Quality vS Entropy (t)
(s) Preflib3 Quality vs Entropy (t)
(1) AAMAS2016 Quality vs Entropy (1)
Figure& 8: The trade-offs between quality and five randomness metrics on Preffibl, Preflib2, Preffib3 and AAMAS 2016. Downarrows (L) indicate that lower is better and uparrows (1) indicate that higher is better. The figure shows that PM incurs no increase in Maxprob while significantly improves over PLRA on all other four metrics. The results are similar to those on AAMAS 2015 shown in Section 6
17

---

B Missing Proofs in Sections 4 and
B.1 Proof of Theorem
1
Theorem 1. Let N+ be the precision in Algorithm 1
and OPT be the optimal perturbed quality.
(a) Algorithm runs in Oww lp nop ny) time.
(b) Algorithm returns an assignment with perturbed quality ALG 2 OPT - Sp.r-
Proof of Theorem For (a), consider implementing the maximum cost flow using Edmonds & Karp's Algorithm B in [37]. In Edmonds & Karp's algorithm, we will compute the shortest path on the residual graph each time find augmenting path. The number of times augment is bounded by O(w Ep mp). For the shortest path part, Edmonds & Karp's 's algorithm applies node potential trick that ensures the edge weights non-negative throughout the execution, that can use Dijkstra's 's algorithm for shortest path. Although for each paper and reviewer r, Up and er connected by O(w) edges, only 2 of them need to be considered: the ones with the largest cost in both directions E - 2r- and U, + Up- Therefore, the shortest path can be computed O(n, n,)) time. Step (6) of Algorithm [ can be done in On, n,,) time by maintaining running totals for each reviewer and paper load. And thus Algorithm runs in O(w lp np n,)) time.
For (b), let x" be the optimal assignment such that PQuality, , (x*) OPT. Consider another assignment x', where dy,, = 1 w. w 1p.r-l.y Vp E P,r E R. Note that x' may not be a feasible assignment if E, "yrrr S &p for some paper p. but any feasible assignment x" where x"/,- 2 x/pr for all (p.r) will have perturbed quality at least PQuality, (xx). Then Fnry - J/p.r [0, w.. and
PQuality (x*) PQuality (x') Spr (alr((((ppp)))))))))))))))) 1( s f( w
ES...
P.r
P.T
On the other hand, x' corresponds to feasible flow for the maximum-cost flow problem in Step (5) of Algorithm
[ Therefore, ALG 2 PQuality (x'). Together with 3 we have ALG Z
OPT (()) Ep.r Sp.r-
B.2 Proof of Theorem 2
Theorem 2. For input instance (Mpp Bry, Ep, S). where S is blockwise dominant with block identity A E R Ro and block sizes {pi,..., , pk } {ri,.... ......... r assume (i) {ri,..., T& are not all equal, (ii) Pt by S.. e Vi {1,...,ki k) and (iii) Q rr; lp vi (1...., k). Let f be strictly concave perturbation function and f'( < Dom(A) PM with f(x) as the perturbation function (weakly) dominates PLRA quality and all randomness metrics. Formally.
(a) VX E PM(Q. f), Vy E (L)A(Q).
Quality(x) Quality(y),
Maxprob(x) < Maxprob(y), AvgMaxp(xx) < AvgMaxp(y),
L2Norm(x) < LyNorm(y),
Entropy(x) 2 Eutropy(y),
Support(x) 2 Support(y).
(b) Vx E PM(Q,)) By E PLRA(Q),
AvgMaxp(x) < AvgMaxp(y), 12Norm(x) < L.2Norm(y), Entropy (x) > Entropy(y))
Label the first Pi papers and ri reviewers as group 1, the next P2 papers and 12 reviewers as group 2, the next pa papers and ras reviewers as group and so on.
Proof of Theorem 2:
For convenience of language, for an assignment x, define the total Quality of paper to be Ep and the total PQuality, of paper p be Σ, (
Define x* to be the assignment such that for each paper p and reviewer " - = Ep/ri if they are in the same group i and o 0 otherwise. Note that xt is feasible, because lp/r; < Q according to assumption (iii), each row of x" sums to lp and each column x" sums S l, according to assumption (ii). Intuitively, x" is generalized version of Fig. Ta on blockwise dominant matrices.
18

---

Claim B.2.1. For feasible assignment x. Quality(x") 2 (x). The equality holds if and only if x assigns paper p to reviewer r with positive probability only when they are in the same group.
Proof of Claim B.2.1 First, Quality(x*) = Ei=1 PiT; lp/r; A,, = Ei bp A
On the other hand, recall that A,; > A1,, Vj + i. For paper p in group i, p can only be assigned to lp reviewers, so the total similarity is at most lp AA,.. Therefore, Quality(x) S Σx Po. A., Quality(x*)) ). The equality holds if and only if each paper in group i is assigned to Ep reviewers with As, similarity, i.e., lp reviewers in the same group.
As PLRA is maximizing Quality and x" is a feasible solution, we have the following corollary.
Corollary B.2.1, Vx E (LR, x assigns paper p to reviewer r with positive probability and only if they are in the same group.
Next, we consider the performance of PM. Claim B.2.2. PM(Q. f) {x*}.
Proof of Claim B.2.2 First, A. 2 Dom(A) Vj A by the definition of Dom(A).
For paper p in group i, consider the maximum total PQuality, of p. For some assignment x, suppose x assigns to some reviewer in group j # i with probability т. If we adjust x so that the probability is instead assigned to reviewers in group i, then the PQuality, will first decrease by [(T) A F (0) and then increase by at least Tf (1)) - As (0) < Dom(A))'())
T f'()),,,: (O))A.. > T of (', Dom (A) 2 0.
This shows that the adjustment increases the total PQuality, y of p. Therefore, to maximize the total PQuality, , of p. p should only be assigned reviewers in group i. Let p be assigned to the j-th reviewer in group with probability 0z (E3 a- lp), then the total PQuality, of p equals
r May)) Aii.-
Σ J=1
According to Jensen's 's inequality, only aj 7 Vj maximizes 44. This shows that, for every paper the corresponding row of x" is the unique assignment that maximizes the total PQuality, y of And thus x* is the unique solution that maximizes the overall PQuality,.
Now we are ready to proceed to prove Theorem 2 Note that Claim B.2.2 B.2.2] shows that the only possible solution of PM x". For clearer presentation, (PM) x".
For Quality, Claim B.2.1 implies (PLRA) (L)A(Q),, Quality(x(PMI) Quality
For Maxprob, compute that Maxprob(x(PMM) = max; ( (fp/r:). On the other hand, Corollary B.2. implies that (PLRA) E PLRA(Q), Maxprob(x(PLLM))
max r = Maxprob(x(PMM) (PM)).
For Support, compute that Support(x(Px0) Σ Ei=1 Par.. On the other hand, Corollary B.2.1 implies that (PLRA) E (LRA(Q), (apport(x(PLRA)) Σ Prr: = Support(>:PMM)
For the other metrics, A AvgMaxp, Entropy and L2Norm, consider paper p in group i. By Corol- lary B.2. we know that PLRA only assigns p to reviewers in group i. Let it be assigned to the j-th reviewer in group i with probability a, (E,ag a, = fz). Note that max, {ay} is minimized by
aj = lę, Vj. which is the corresponding row in (PM) for each p. Meanwhile, according to Jensen's inequality. E, az is minimized by a, = fr, Vj and Σ, a, In(1/az) is maximized by aj = fe Vj. So (PLRA) PLRA(Q), AvgMaxp(x(PMD) S AvgMaxp(x(PLRA)) L2Norm (PM)) S T.2No)((X(PLRA) and Entropy (x (PM)) 2 Entropy(x(PPRA)) Moreover, as "i.....Tk) are not all the same, for some group i, & < max S Q. For this group, aj = 4,, Vi is not the only solution. Thus, (PLRA)) E PLRA(Q), AvgMaxp(x(PMD) < AvgMaxp(x(PLRA) T.2Norm(x(PMI) < (ONNor((((PRAA)))) and Entropy (x(PM) > Entropy(x(*H) (PLRA)).
This concludes the proof of Theorem 2
19

---

B.3 Proof of Theorem 3
Theorem 3. For an input instance (np. ny (r.lp,rr.)) where each entry of is i.i.d. sampled from (Vi,..., 2k (0 V1 < .... < vp) uniformly, assume (i) S 1. Bp (i) C 2 c. In(n,)) (iii) n- Ep S R2 er and (iv) Q (n, 1) 2 Ep. Let f be strictly concave perturbation function and (0) v.-1 (1),,, vi E (2....,k) With probability 1 1 -0 PM with f(x) as the perturbation function (weakly) dominates PLRA in quality and all randomness metrics. Formally.
(a) VX E PM(Q. f). Vy PLRA(Q),
Quality(x) 2 Quality(y); Maxprob(x) Maxprob(y)) Entropy(x) 2 Entropy (y):
AvgMaxp(x) S AvgMaxp(y),
1.2Nor((x) I 1.2Norm(y).
Support (x) 2 Support(y).
(b) Vx E PM(Q. f). By (LRA(Q),
Support(x) Support(y), L2Norm(x) L2Norm(y), Entropy (x) > Entropy(y))
Proof of Theorem
To prove this statement, first consider the following 2 algorithms.
Algorithm 4: Greedy
For each paper p, let the reviewers sorted by decreasing similarity with p be (ri, 12, -2.-.... Jm. Greedily assign to the first few reviewers as follows: assign p to 11, r2, L6,/ with
probability Q, and assign to [14p/]++1 with probability Ep Q QL
Algorithm 5: Balanced Greedy
For each paper suppose Vi E 21,,,..., the set of reviewers with similarity os is Rp Initialize remaining paper requirement Cremain fg. For i from k to 1:
If Cremain 2 Q RRp, assign p each reviewer in Rp with probability Q-
Otherwise uniformly assign to each reviewer in Rp.s with probability fvemain/ /
Update Cremain to the current remaining paper requirement max (0, Eremain - Q Rp..))
Note that Balanced Greedy is almost the same algorithm Greedy, except that Balanced Greedy groups reviewers with the same similarity &; with together as Rp.s and always assigns the same probability to them, while Greedy treats each reviewer individually.
These two Greedies do not always produce feasible assignments because they both consider each paper individually and do not take the constraint that each reviewer is assigned at most & papers into account. Nevertheless, we will show that with high probability, they are feasible, and if this the case, we can relate them to PM & PLRA and prove the Theorem 3
At a high level, we will prove the Theorem 3 with the following steps.
Greedy and Balanced Greedy are feasible with probability (2(c)
When Greedy and Balanced Greedy are feasible:
Greedy produces a possible solution from PLRA.
PM does exactly the same with Balanced Greedy.
Balanced Greedy dominates Greedy with probability 1 - e9lc))
We will formalize and prove the above 3 steps below.
Claim B.3.1. Greedy and Balanced Greedy are feasible with probability 1 - e R(c).
Proof of Claim B.3.1 We use Bernstein's inequality: Suppose T1, 22, . En are i..d from distribution with mean μ., bounded support [a, b), with variance o?. Then
n +2
Pr[lů - 14 2 4] S 2exp
where f
2( + (b a)()
7
20

---

In Greedy and Balanced Greedy, the output is Rp X ny matrix of random variables, where variables from different rows (papers) are independent different papers are considered individually. These algorithms are feasible if and only if for each reviewer r. Ep Fp.r S fr- Note that as the similarities are i..dd random, the reviewers are symmetric. Using Union Bound across reviewers,
Pr[ALG is infeasible] S Pr Σ T.r by VALG E {Greedy, Balanced Greedy }.
Moreover, the papers are also symmetric. So Ep Fp.r is then a sum of np iid. random variables. Let their distribution be D. We will bound the probability using Bernstein's 's inequality. To do this, consider the properties of the distribution D. For both Greedy and Balanced Greedy,
The expectation ls of D) should be fp/m,-
Also, D is supported on [0, Q) C [0.
EEND(O] lp/ Therefore, o² E [ 122 E S
Also, by assumption (iii). 2 up Ep n lr, we then know f./ 2 2. fp/n.. So that
cr
er
Pr
Σ Uprr er Pr p
1
Pr i
Up
27p
Letting
we will use Bernstein's 's inequality on this formula.
According to Bernstein's
2np'
inequality,
np (2./2mp)² Σ Tp.r > lr < 22exp( 2(lp/n,, + (1 0)({,) O)(e,/2m,))
1 )
Pr
S 2xxp
Then, by assumption (ii), l c- In(n.), and we will VALG E (Greedy, Balanced Greedy). Pr[ALG is infeasible] < 2n, -- Her 2e In(,,) e- e((())
This concludes the proof of Claim B.3.1
For convenience of languague, for an assignment x, define the total Quality of paper to be E, Sp.r and the total PQuality, of paper p be Σ, (xx SSp..
Let (b) Balanced Greedy (Q), x(9) Greedy (Q). For paper p. both Balanced Greedy and
Greedy maximize the total Quality of p. so Quality (x (b) Quality(x(1)). Moreover, this property
of the Greedies also gives us the following Claim B.3.2
Claim B.3.2. For any feasible assignment x, Quality > Quality(x). The equality holds if and only for each paper p. x maximizes the total Quality of
And as PLRA is maximizing Quality, we further get the following Corollary B.3.1
Corollary B.3.1. xf and x(9) are feasible, then (0)xx(0) E (LRRA(Q) and VX E PLRA(Q), x maximizes the total Quality of p.
Next, we consider the performance of PM.
Claim B.3.3. For each paper (b) uniquely maximizes the total PQuality y of
Proof of Claim B.3.3:
For each paper p. recall that Vi 21. k), the set of reviewers with similarity v; to p is Ry . By the execution of Balanced Greedy, x(6) assigns p to every reviewer in the i-th set, Rp with the same probability. Let this probability be Ap,i. Then, there exists a Ap. k Q, Ap.t < Q and Ap, 1p.-11-...
E (1, k). such that Ap.e-1
Ap.1
Suppose that for an assignment x, there are both reviewer Thigh E Rp. such that Fp.riihh < Q. and another reviewer Nlw E Rp. (j < i) such that xp.riw. > O. Let min(Q - Fr-rish Fp.ro.. Consider adjusting x by decreasing pp.row by 6 and increasing pp.raigh by 8. The total PQuality of
21

---

will first decrease by at most (0)e) and then increase by at least (1),, The net increase in the total PQuality, of p will be
2 (((
0.
This shows that the adjustment increases the total PQuality, of p. so does not maximize it. Therefore, for an assignment x to maximize the total PQuality, of p. x must assign p to every reviewer in Rp.t+1...... Rp..k with probability Q. and assign p to every reviewer in Rp.t-1..... Pp,1 with probability 0. It remains to consider the assignment to group Rp.
Write the total PQuality, , of p in x as
Rpsll 5(1)xc + (Ep:))o
rE
For fixed p. the first summation is constant. To maximize the second summation, according the Jensen's 's inequality, Tp.r, Vr Rp, must be the same, which is exactly x!")
This concludes the proof of Claim B.3.3
Claim B.3.3 gives us the following Corollary B.3.2
Corollary B.3.2. x() is feasible, PM = (x(0).
Now are ready to proceed prove Theorem We first prove (
For Quality, Claim B.3.2 implies that Vx E (LRA(Q), Quality(x(0) 2 Quality(x).
For the randomness metrics, consider each paper p and again let the set of reviewers with similarity v to p be Rp Like in the proof of Claim B.3.3 3 by the execution of Balanced Greedy, x x()) assigns p to every reviewer in Rp.s with the same probability Ap, and there exists a E (1,2..... k}. such that Ap.c+1
Ap. Q, Ap. < Q and Ap.c1
Ap.1 =0
By Corollary B Vx E PLRA(Q). x must assign p to reviewers in Rp.tt1..... Rp. with probability and assign p to all reviewers in R Rp.l...., Rp,t-1 with probability O. Among all such assignments, with an argument using Jensen's inequality or simple categorical discussion, we will see that x (b) maximizes Σ, Tpr ln(1 /x.r)) Σ, [[p, 0) and minimizes max, max,-(xppr) ( Ex m2.
This shows that Theorem (a) holds.
To show Theorem 3 (b), we will first prove the following Claim B.3.4
Claim B.3.4. With probability - -S(e)
Support(x (1) > Support(x(0)) (o)), (2) < L2Norm (x(())))))))))))))))))))))))(( ())) Entropy(xx (b)) > Entropy(x(0)
Proof of Claim B.3.4 Recall in Greedy, for each paper p. the sorted reviewer list by decreasing similarity with p is T2......... }. By assumption (iv), Q (n, - 1) 2 ly. so [tp + 1 S n,
Suppose for some paper and i E (1..... kJ. Spirie,/01 = Sp.rre/ = Then, as by the (g) execution of Greedy, /p. > 0 and 2p.r
0. Let (rlett.... Fright) Fright) be the set of reviewers with similarity 2/ to p, where left $ [lp/Q1 < [4p S right. Then
(g)
Q
(j < left 1)
(b)
f0-Q(left-1
(left S م right)
p.y
right Sechtt-leftee left+I
0
(j 2 right +)
Q ( [6/Q] -
x
(0) p.y,
e -(Te//1//1
1) [= (6/0/
6 1//Q1+11
p.ts for any j < loft - and any j 2 right + 1. For left S ] S right, x are all equal, but as J.p. 101111 0, (g) are not all equal. So Support(x(()) > Support(x(0)) and by Jensen's inequality, (2) L2Norm(x(0), Entropy (x)))) (x) Entropy(x(0))
Note that x x = x (o)
(g)
22

---

Therefore, it remains to show that with probability 1 - c Q()), for some paper p. Sporte,/11 Sp.rte/./114 /01+11 For a fixed denote the event that Sp.r Sp.r1e,/004 as Esp. Recall that entries in S are i.i.d, and uniformly chosen from (V1,..., Wky. Consider fixing pp.,,..., Sp.n. 11 and let the pep 11th largest number in this set be a. Then Pr(Sp.n, a)] 2 As Spn, implies Pop. Pr[Ep = 1] 1. Therefore, according to assumption (i), k S c nps we know that
Pr[p,, E, = 1] 1
Up
2 1
1
ck 2 1 1
k
k
This concludes the proof of Claim B.3.4
Theorem (b) is implied by Claim B.3.
Corollary B.3.1
Corollary
B.3.2 and Claim B.3.4
C
Discussions
C.1 Directly Optimizing Specific Randomness Metries with PM
While PM provides one way to introduce randomness into the paper assignment, one natural alter- native approach is simply maximize one specific randomness metric, subject constraint on the minimum solution quality. In this section, we show that a slight modification to PM is general enough to capture such approaches.
Specifically, suppose we want to maximize a concave randomness metric RM [0, 1,,x" R over the set of feasible assignments Steasible {x E [0, 1 xmr) Ex Tp. cp. vp and EpHp.r S l,, Vrr subject to a minimum requirement of the solution quality Quality(x) 2 Quality maxxeSmarthie Quality(x) and r [0, 1]. The problem can be formulated as
where QualityorT
Maximize
RM(x)
Subject
Quality 2 T Quality
(5)
x E Steasible-
We then consider slight generalization of PM that allows different perturbation functions for each reviewer-paper pair. That is, we change the definition of PQuality, (the objective of PM) in Definition 4.2 to
PQuality,
ΣESp Spr fp.((xp.))
Then we have the following result:
Theorem 4. If (x) is (i) Sp.r 1 0j, (ii) Sp.r In or (iii) x Sp achieves the optimal trade-offss between Quality (x) and (i) Support(x). (ūi) (xtropy(x), or (ii)
Ax² then PM
I.2Nor?((x) respectively with different values of X E [0, 000)
In fact, the proof of Theorem 4 also shows that PM-Q can be viewed as algorithm that achieves the optimal trade-off between Quality(x) and another randomness metric (E,, Sp.re..) ). a similarity-
weighted version of squared L2 norm of x. Next, we will proceed to prove Theorem 4
Proof of Theorem 4 When [0. 1]. the maximization problem (5) always has at least one feasible solution. Let the optimal value of (5) be (T). RM* describes the optimal trade-off between Quality(x)) and RM(x). We can show the following property of RM* (T).
Lemma C.I. RM*(T)
(T) is concave and non con-increasing function of T E [0, 1].
Proof of Lemma C.I Let x1 be the optimal solution of (5) when = Ti and X2 be the optimal solution of (5) when = T2 where 0 < Ti < T2 < 1. Then, we have Quality(x,) 2 T2
Quality > Ti Quality and X2 is a feasible solution of of (5) when T Tı. Therefore, RM(x1) 2 RM(x2), i.e., (M)(T)) > RM* RM)(7). This shows that RM (r) is a non-increasing function r.
Moreover, let xe,, +x2). Then, Quality(x,.) 2 [ +72) Quality oPT and xm E Steasible-
Thus Xm is feasible solution of of (5) when = [ + T2). Since RM is concave function,
23

---

RM (T + T2)) 2 RM(x,)) 2 2
(R)((x)) + RM(x))) (RM + (T2). This shows
that RM is concave function of
Now, for 2 0, consider another optimization program as follows:
Maximize Subject to x Steasible.
Quality(x) + RM(xx
(6)
Let the solution of (6) be x. Lemma gives us the following corollary. Corollary C.I.I.
{(T, (IT,RM((T) T (0, 1]} ((Quallty(33)//uulllll RM(x))) | [0, +oo)].
Plugging in different randomness metrics RM(x) concludes the proof of Theorem
C.2 Incorporating Various Constraints in PM
In some of the surrentyy-deployee conference review systems, there various additional constraints on the assignment of papers to reviewers. We will discuss in this section how to incorporate some of these constraints in PM. Specifically, consider the following constraints from [20]
Seniority: Each paper is assigned to senior reviewer.
2) Geographic diversity: No 2 reviewers assigned to the same paper belong to the same region.
Seniority. Let the set senior reviewers be Ssenior. We can incorporate the seniority constraint in PM by modifying PM to the following optimization program.
Maximize Subject to
PQuality (x)
Σ Tpp = Ep
Yp P, Vp E P, Vr E R,
rEnnno Zp. 21
2p Tpr S Ey
Ipr SQ
Vp E P.
With slightly different sampling algorithm, can be realized by distribution of deterministic assignments that satisfies the seniority constraint (22).
show that the obtained randomized assignment
Geographic diversity. Let the set of regions be Sregion We can incorporate the geographic diversity constraint in PM by modifying PM to the following optimization program.
Maximize Subject to
PQuality (x) Ep
r Ipr
Vp E P, Vp P,g E Sregion:
r belongs to g Fpr S1
Σ p Tpr S lr
Vr E R,
Ipr SQ
Vp PpE,
The obtained assignment can also be realized by distribution of deterministic assignments that satisfies the geographic diversity constraint with a slightly different sampling algorithm (22).
Apart from the constraints mentioned above, there are also some other common constraints that cannot be easily incorporated in PM 20). We leave incorporating them for future work.
24


Reviews:
[{"review_id": "aJoeWqIBUV", "reviewer": "Reviewer_FQ98", "summary": "This work is concerned with randomness in paper matching for peer review. It provides normative motivations for the value of randomness in this process and proposes a family of generalizations of the Probability Limited Randomized Assignment (PLRA) paper matching framework of Jecmen et al. This generalization, which the authors term Perturbed Maximization, entails replacing the linear objective in the PLRA linear programming problem with a concave objective which increasingly discounts paper-reviewer matchings with higher probabilities. The authors prove comparisons between the two methods under two distributions of paper-reviewer similarity scores. Experimentally, the authors consider two choices of discounting (perturbation) functions, demonstrate that solving this convex problem is tractable in practice, and present the effect of deploying their method for two past conferences, according to multiple measures of randomness. ", "questions": "Randomness metrics:\n\tCan you remark on which metrics in Section 3 would be natural choices for any of the randomness motivations in Section 1, and whether you agree that in any cases the corresponding metrics for the induced assignment distribution would be more relevant? \t\t \t\n\tAlternatively, do you think there is good motivation for restricting your randomness metrics to ones that are linear over the fractional assignments of individual papers (as all except L2 are)?\n\tDo the authors of [22] mention or consider any metrics other than Maxprob?\n\nTheoretical results:\n\tWhat is the scalar c in the statement of Theorem 3? Is it an unspecified constant, or does the statement hold for every c?\n\tIf part (a) of Theorems 2 and 3 holds for all pairs of points in the solution set, the claimed Quality inequality seems to suggest that the solution set of PM is contained in the solution set for PLRA. This in turn raises two questions: first, given that the PM objective is different, wouldn't this suggest that these theoretical settings are in a sense too degenerate (have too many equally optimal solutions/too few nearby suboptimal ones) to distinguish between the two methods? Second, do the remaining claimed inequalities suggest that PM identifies a unique point in PLRA(Q) which simultaneously minimizes/maximizes those randomness measures within the set PLRA(Q)?\n\nOn line 333, how does Figure 4 show that PM sacrifices Maxprob relative to PLRA? ", "limitations": "The choice of perturbation function seem ad hoc, and it is not obvious why the authors decided to apply the perturbation function to the full range [0,1] instead of to the range [0,Q]. For the perturbation functions studied here this does not matter, but in general it could. There are three places in the narrative where the authors present a range of options: (i) motivations for randomness in paper matching, (ii) measures of randomness, and (ii) choices of perturbation function. It would have been interesting to see some discussion of how choices of (i) might motivate different choices of (ii), particularly with regard to motivations 2 and 4, and some discussion of how different choices of dependent rounding scheme given the fractional assignment affect these objectives. But it would have been particularly nice to see some motivation of how choices of (ii) inform choices of (iii). For instance, are there informal or heuristic arguments that would suggest that one form of perturbation function would be particularly suited to maximizing the entropy objective?\n\nThe theoretical analysis is a little unsettling. Either the theoretical similarity models considered seem inapt to the purpose of comparing the two methods, or the theoretical claims could use significantly more contextualization. \n\nCertain aspects of the experimental section could be clearer. In particular, it would be helpful to include a slightly more explicit description of the hyperparameters that are being fit, and the order in which they are being fixed. In my opinion this omission makes the presentation and interpretation of Figure 2 particularly misleading, since the form it takes and the insights offered are directly determined by the value assigned to the hyperparameter delta, which is not mentioned.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This work proposes and studies a natural generalization of the PLRA paper matching framework. The generalization and analysis are particularly suited to practical use, in the generalization can be arbitrarily incremental, and the PLRA framework has been used in practice and serves as a benchmark for the experiments.\n\nFrom a theoretical perspective, it is interesting to identify combinatorial optimization problems/applications for which randomness is a desirable property, and to study how randomness this trades off against optimality.\n\nThe experimental results seem to demonstrate that, at least for some paper matching instances, the framework could be used to generate matchings with comparable quality in a much more randomized way. ", "weaknesses": "Theoretical results: I have a difficult time understanding the settings and claims of the theoretical analysis provided, and I am suspicious of the implications of the analysis to understanding PM as compared to PLRA. The quantity c in Theorem 3 is unspecified, and the claims seem to suggest that the models permit either the same or somehow degenerate solution sets for the two algorithms. In any case, more explanation of these claims seems warranted.\n\nRandomness metrics: the motivation for the proposed randomness metrics for the distribution x in Section 3 is very thin. Some references for these being useful measures for a fractional 'matching' in this application or elsewhere would be welcome. But there seems to be a deeper mismatch between these measures and the reasons randomness is desirable outlined in Section 1. Properly, (and as observed in the discussion of entropy), x is not a distribution; instead the fractional assignment x together with a dependent rounding scheme together induce a distribution over reviewer-paper assignments.  The randomness of this distribution seems arguably more relevant to most of the randomness motivations provided in Section 1; for instance, depending on the dependent rounding scheme, a fractional assignment x with Q=0.1 could correspond to sampling one of only 10 final assignments, allowing easy reviewer de-anonymization. I think that calculating (or estimating) these randomness metrics for the assignment distribution would lead to a superior analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for spending time understanding our work and providing insightful comments. We are happy you find our contributions relevant, interesting, and practical. Below we respond to the questions and limitations raised in your review, hoping to address your concerns about our paper.\n\n**Regarding randomness metrics.**\n\nIn Section 3, two out of the four metrics are natural choices for motivations in Section 1. \n\n**(i):** Average maximum probability ($\\mathrm{AvgMaxp}$) is a natural choice for robustness to malicious behavior (Motivation 1). Depending on the model of such behavior, different metrics can fit into the motivation. The vanilla randomness metric $\\mathrm{Maxprob}(\\mathbf x)$ proposed in [22] corresponds to a model where the malicious reviewer-paper pair is a single worst-case pair chosen by Nature. However, if a particular paper $p$ is targeted, then in the worst case, the malicious reviewer targeting $p$ succeeds with probability $\\max_{r}\\lbrace x_{p,r}\\rbrace$. Our new metric $\\mathrm{AvgMaxp}(\\mathbf x)$ calculates the average of these probabilities, corresponding to the model where a random paper $p$ is targeted with a worst-case malicious reviewer. \n\n**(ii):** Support size ($\\mathrm{Support}$) is a natural choice for evaluation of alternative assignments (Motivation 2). The techniques for off-policy evaluation [21] can be utilized to estimate the review quality of another non-deployed assignment. Crucially, the precision of the estimation depends on the number of \"positivity violations'' [21] between the deployed assignment $\\mathbf x$ and the non-deployed assignment $\\mathbf y$ of interest, with positivity violation defined as an entry $(i,j)$ where $x_{i,j}=0$ but $y_{i,j}\\ne 0$. Since a large number of alternative assignments $\\mathbf y$ may be of interest, to minimize the number of positivity violations, we want to minimize the number of entries in $\\mathbf x$ set to $0$. This corresponds to maximizing $\\mathrm{Support}(\\mathbf x)$. \n\nWhile alternative metrics that operate on the full assignment distribution (as opposed to simply the fractional assignment) are possible, such metrics are only beneficial if the joint distribution of reviewer-paper assignments is of special interest. In the above two cases, the corresponding metrics for the induced assignment distribution are equivalent to the metrics for the fractional assignment that we use, and thus they are equally relevant. As such, we focus in this work on metrics that operate only on these marginal probabilities. \n\nWe are not deliberately restricting our randomness metrics linear over fractional assignments of individual papers. We choose the first two metrics because of the reasons above. The remaining two metrics (Entropy and L2 Norm) are chosen based on general principles: (i) Entropy characterizes the uncertainty of a distribution and (ii) L2 Norm places a larger penalty on entries with higher probability. These two metrics can be viewed as additional ways of characterizing the distance from a uniform random assignment, which is the most random assignment.\n\n[22] did not mention or consider any metrics other than $\\mathrm{Maxprob}$.\n\n**Regarding theoretical results.**\n\nTheorem 3 holds for every $c>0$.\n\nFor PLRA, there are indeed many equally optimal solutions in the theoretical settings. This fact does not imply that the settings are too degenerate since PLRA's optimization does allow many equally optimal solutions in many cases. Recall that in PLRA, the objective function is $\\sum_{p,r}x_{p,r}S_{p,r}$. When $S_{p_1,r_1}=S_{p_2,r_2}$, adjusting the solution by adding $c$ to $x_{p_1,r_1}$ and subtracting $c$ from $x_{p_2,r_2}$ does not affect the objective function. Therefore, when many entries in the matrix $\\mathbf S$ share the same value, one can imagine that there will be many ways to adjust an optimal solution into another optimal solution while preserving feasibility. In practice, the phenomenon of many entries in the matrix $\\mathbf S$ sharing the same value is possible (e.g., when the matrix $\\mathbf S$ is constructed from discrete reviewer bids and subject areas only). The answer to your second question is \"yes\". Among these many optimal solutions of PLRA, PM identifies a subset of solutions that simultaneously minimize/maximize those randomness measures within the set.\n\n**Regarding Line 333.**\n\nFigure 4 does not show PM sacrifices $\\mathrm{Maxprob}$ relative to PLRA. Figure 2b (which is also mentioned in Line 333) shows it instead. In Figure 2b, you can see that the yellow and green lines (showing PM’s $\\mathrm{Maxprob}$) are slightly higher than the blue line (showing PLRA’s $\\mathrm{Maxprob}$).\n\n**Regarding the choice of perturbation functions.**\n\nFor (i) motivations for randomness (ii) measures of randomness and (iii) choices of perturbation function, we clarify how (i) might motivate (ii) above. For how choices of (ii) inform choices of (iii), we do have a formal discussion in Appendix C.1 (in supplementary materials). For instance, we specify one form of perturbation function which is exactly suited to maximizing the entropy objective there (Theorem 4).\n\nIn the main paper, we choose two simpler perturbation functions to clearly convey the intuition behind PLRA, while keeping things easy to understand.\n\n**Regarding the experiments.**\n\nWe do have a formal description of a principled way to choose hyperparameters in PM, including how we pin down $\\delta$ in Appendix A.2 (in supplementary materials). In short, as we increase $\\delta$, we allow PM-Q and PM-E to find more random solutions at a cost of larger $\\mathrm{Maxprob}$. To balance the gain and loss, we choose $\\delta$ that maximizes a linear combination of them. We will add more description to the main paper in the next version. \n\nAgain, we want to thank you for these insightful comments. We hope that the response above addresses most of your concerns and we would highly appreciate it if you can re-evaluate our paper based on this response."}, {"review_id": "eZBlqXqJbL", "reviewer": "Reviewer_iL2x", "summary": "The paper presents an improvement on PLRA, an important (used in major reviewing deployments like AAAI and OpenReview) algorithm for randomizing reviewer assignments while preserving a prescribed fraction of assignment quality, by finding randomized assignments that increase additional randomization metrics of interest beyond bounding the probability a particular reviewer is assigned to a particular paper. These additional metrics help find solutions of comparable quality (as defined by PLRA) that address additional concerns such as increasing average randomness (intended to further guard against malicious behavior) and the support size (useful for better off-policy evaluation). The work is soundly evaluated theoretically and empirically.", "questions": "- The proposed approach improves on PLRA but how does it compare to [20,29,30]?\n- How much does relaxing the L2 norm to a soft constraint instead of the hard constraint used by PLRA negatively impact results?\n- How were AAMAS and ICLR 2018 chosen, and why were additional datasets not also experimented with? Would the empirical results generalize?\n- How can conference chairs prioritize certain proposed metrics over others? Is there a relative tradeoff?\n- How/why was 95% picked for Table 1, versus also providing results for other percentages 80-100%?\n", "limitations": "The limitations could include more details on the limitations of the empirical experiments such as potential lack of generality from testing on only 2 datasets.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper makes a significant contribution to reviewer assignment algorithms, an important topic relevant to the NeurIPS community. The proposed algorithm substantially improves on the previous algorithm with little to no apparent downside, and can be readily deployed. The work makes an original contribution and is presented with very high clarity.", "weaknesses": "The paper is very strong, but some minor weaknesses remain. The work relaxes the L2 norm constraint employed by PLRA to a soft constraint, but it is unclear how this relaxation might negatively harm results. The proposed algorithm appears novel in the context of reviewer assignment, but novelty in the context of related problems is less clear - it would be better to clarify the extent to which the technical contribution leverages known techniques (e.g., max flow) and how different this application is from related problems that have employed similar techniques in the past. The paper empirically tests on only 2 datasets, where it would seem easy to evaluate on additional datasets. See also my questions in the next section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for spending time understanding our work and providing insightful comments. We are very glad to see your positive review and that you recognize our work as significant, substantial, and ready to deploy. We respond to the questions and limitations raised in your review below.\n\n**Regarding the comparison to [20, 29, 30].**\n\nNone of [20, 29, 30] considered randomized assignments. Indeed, [20, 29, 30] took different approaches to computing reviewer-paper assignments under different considerations. However, the three of them were restricted to deterministic assignments, i.e., assignments $\\mathbf{x}\\in\\lbrace 0,1\\rbrace ^{n_p\\times n_r}$. Therefore, in terms of the proposed randomness metrics, these methods would perform very poorly. We then decide not to include these methods into our comparison.\n\n**Regarding the relaxation in L2 norm.**\n\nWhen we mention that the L2 norm relaxes the hard constraints used by PLRA, we intend to provide the intuition that a higher probability results in an increasingly larger loss in L2 norm. However, we do not use the L2 norm as a constraint in the optimization of PM. Instead, the L2 norm is used as a measure of randomness after PM produces a solution. We still keep the same hard constraints in PM as are used in PLRA. Therefore, the results are not negatively impacted by any relaxation in L2 norm.\n\n**Regarding the choice of datasets.**\n\nWe used to run our experiments on various more datasets. In particular, we experimented with the following 6 datasets:\n\n- Preflib1 (00039-1 from [39]): 54 papers, 31 reviewers\n- Preflib2 (00039-2 from [39]): 52 papers, 24 reviewers\n- Preflib3 (00039-3 from [39]): 176 papers, 146 reviewers\n- AAMAS2015 (00037-1 from [39]): 613 papers, 201 reviewers\n- AAMAS2016 (00037-2 from [39]): 442 papers, 161 reviewers\n- ICLR2018 (from [26]): 911 papers, 2435 reviewers\n\nAmong these 6 datasets, the first 5 are all bidding datasets, which means that for each paper-reviewer pair, there is a discrete level chosen from {\"yes\", \"maybe\", \"no\", \"conflict\"}. In contrast, ICLR2018 contains the text-similarity scores between the paper text and reviewers' past work. These scores are continuously-valued instead of discrete.\n\nOur experiments showed that on the 5 bidding datasets, the comparisons between PM and PLRA were always similar. Therefore, to optimize the presentation of our paper, we only kept the largest dataset (AAMAS2015) among these 5 datasets, together with ICLR2018. The empirical results did generalize to the other datasets we tested on and we are happy to add more experimental results for other datasets in the appendix in the next version.\n\n**Regarding trade-offs faced by conference chairs.**\n\nFrom Figures 3 and 4, we can see that essentially, the conference chairs are facing the trade-off between quality and randomness. If the conference chairs are willing to sacrifice more quality, PM will in return find an assignment with more randomness (with all randomness metrics improved simultaneously). To choose one point on this trade-off, in practice, the conference chairs could also plot it as in Figures 3 and 4, and choose a specific point on this curve based on their discretion.\n\n**Regarding Table 1.**\n\nTable 1 aims to show that the network-flow-based approximation takes less total CPU time with only minor degradation in performance. In terms of running time, the results for other percentages 80% - 100% will not be significantly different from 95%. Empirically, the degrees of degradation in performance are also similar within 80% - 100%. Therefore, we choose to only present the results of 95% since 5% is a reasonable sacrifice for robustness in real conferences. In this way, the readers will not be distracted by a large chunk of homogeneous experiment data.\n\nWe again thank you for your understanding and recognition of our work, as well as for providing your insightful comments.\n"}, {"review_id": "jYUhUQvjkO", "reviewer": "Reviewer_euo8", "summary": "In this paper, the authors propose a new algorithm to improve randomness in peer-review paper assignment without sacrificing assignment quality. The authors first identify a set of good randomness properties in paper assignment besides the max probability used in the PLRA. The authors propose a simple and practical variation to PLRA by adding a concave perturbation function. Empirical evaluation on two real-world datasets demonstrates superior performance of the proposed method to PLRA.", "questions": "N/A", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written with clear motivation and justification of the method. The identification of good randomness properties could motivate future research on random paper assignments.\n2. The proposed algorithm is very practical and easy to implement as convex optimization which can be solved efficiently with commercial software.\n3. The authors demonstrate the superiority of the proposed method both theoretically and empirically on two real-world peer-review datasets.\n", "weaknesses": "1. Though the authors provide comprehensive comparison to PLRA, it would be interesting to see comparison of the proposed method to other baselines, even the deterministic ones. Also, it would be interesting to provide “randomness” metrics from samples of assignments.\n2. The authors motivate the requirement of randomness from 4 perspectives. It would be interesting to design more direct metrics or evaluation in terms of these 4 perspectives.\n3. It would be better to include experiment and discussion on hyper-parameter sensitivity. As both PM-Q and PM-E contain the same number of parameters as in PLRA.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for spending time understanding our work and providing insightful comments. We are very glad to see your positive review and you recognize our work as superior in performance and very practical. Below we briefly respond to the weaknesses raised in your review.\n\n**Regarding comparison to other baselines.**\n\nWe would like to highlight that the deterministic maximum matching algorithm can be seen as a special case of PLRA with $Q = 1$, and thus its performance is included in all the plots.\n\nOur experiments mainly evaluate the trade-offs between quality and randomness of PM and PLRA. Similar to the deterministic maximum matching algorithm, any deterministic algorithm will always produce deterministic assignments and thus will perform poorly in all randomness metrics.\n\n**Regarding direct randomness metrics to motivations.**\n\nIn fact, two out of the four proposed metrics are direct choices for motivations in Section 1. \n\n**(i):** Average maximum probability ($\\mathrm{AvgMaxp}$) is a direct choice for robustness to malicious behavior (Motivation 1). Depending on the model of malicious behavior, different metrics can fit into the motivation. The vanilla randomness metric $\\mathrm{Maxprob}(\\mathbf x)$ proposed in [22] corresponds to a model where the malicious reviewer-paper pair is a single worst-case pair chosen by Nature. However, if a particular paper $p$ is targeted, then in the worst case, the malicious reviewer targeting $p$ succeeds with probability $\\max_{r}\\lbrace x_{p,r}\\rbrace$. Our new metric $\\mathrm{AvgMaxp}(\\mathbf x)$ calculates the average of these probabilities, corresponding to the model where a random paper $p$ is targeted with a worst-case malicious reviewer. \n\n**(ii):** Support size ($\\mathrm{Support}$) is a direct choice for evaluation of alternative assignments (Motivation 2). The techniques for off-policy evaluation discussed in [21] can be utilized to estimate the review quality of another non-deployed assignment. Crucially, the precision of the estimation depends on the number of \"positivity violations'' [21] between the deployed assignment $\\mathbf x$ and the non-deployed assignment $\\mathbf y$ of interest with positivity violation defined as an entry $(i,j)$ where $x_{i,j}=0$ but $y_{i,j}\\ne 0$. Since a large number of alternative assignments $\\mathbf y$ may be of interest, to minimize the number of positivity violations, we want to minimize the number of entries in $\\mathbf x$ set to  $0$. This corresponds to maximizing $\\mathrm{Support}(\\mathbf x)$. \n\nThat being said, we stress that sometimes, a direct randomness metric cannot be uniquely identified from a specific motivation alone. For example, as stated above, when we care about robustness to malicious behavior, the model of such behavior determines the appropriate  metric to use, and different models lead to different metrics. In practice, conference program chairs likely do not have a highly-specific model of malicious behavior in mind against which they wish to defend. As a result, we consider a “one-size-fits-all” approach in this paper, based on several general-purpose randomness metrics. \n\n**Regarding experiments on hyperparameters.**\n\nWe do have a formal description of a principled way to choose hyperparameters in PM, including experiments about what happens when we choose different sets of hyperparameters. You can find it in Appendix A.2 (in the full paper included in the supplementary materials). We will add more description to the main paper in the next version. \n\nWe again thank you for your understanding and recognition of our work, as well as for providing your insightful comments.\n"}, {"review_id": "bSyQHuwmkE", "reviewer": "Reviewer_625T", "summary": "This paper focuses on randomized paper assignments in the reviewer-paper matching problem. First, the authors state the motivation and emphasize the importance of randomness in paper assignments. Then, they point out the weakness of the existing method, PLRA, and propose additional metrics for evaluating the performance of randomized paper assignments. After that, the authors design the PM-E and PM-Q algorithms with different perturbation functions to solve the proposed problem and provide theoretical analysis to prove the effectiveness of the proposed algorithms. Finally, various experiments have been conducted, showing that PM-E and PM-Q perform well on real-world datasets. In conclusion, this paper proposes practical and universal algorithms, PM-E and PM-Q, with the aim of mitigating malicious behaviors, facilitating assignment evaluation, and increasing reviewer diversity and anonymity. However, the theoretical analysis for the correctness of the approximate algorithm is inadequate.", "questions": "1. Why is the additional metric valid? Could the authors provide some analysis or examples to briefly explain it?\n2. Figure 1 presents the ideal assignment, but it assigns more papers to each reviewer. Therefore, is it possible that in a scenario where the quality provided by PLRA is similar to PM-E and PM-Q, PLRA assigns fewer articles to each reviewer resulting in a lower workload for each reviewer?", "limitations": "This paper acknowledges the limitation that deploying a randomized assignment may have a negative impact on assignment quality compared to deterministic assignments. Additionally, the authors propose a reasonable explanation that their work allows conferences to choose the level of randomization to address this limitation.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-written and easy to understand.\n2. Related works are described in detail and the limitations of existing methods are well illustrated by a simple example.\n3. The theoretical analyses regarding how the proposed PM algorithm outperforms PLRA are sufficient.\n4. Various experiments show that the proposed algorithm has better performance than existing randomzied paper assignment methods.", "weaknesses": "1. Algorithm 1 prposes a network-flow-based approximation of PM and use experiments to show its pratical performance, but the theoretical analysis of how this algorithm approximate solves PM problem and approximation ratio is missing.\n2. The motivations listed in Introduction mainly talk about randomness in paper assignments, but randomized paper assignment problem has been proposed in PLRA.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for spending time understanding our work and providing insightful comments. We are happy to see that you find our work well-written, practical, and universal. Below we respond to the questions and weaknesses raised in your review, hoping to address your concerns about our paper.\n\n**Regarding the approximation ratio of Algorithm 1.**\n\nWe do have a theoretical guarantee for Algorithm 1 that is not included in the paper. Let the optimal perturbed quality be $\\mathrm{OPT}$. Algorithm 1 produces a solution of perturbed quality $\\mathrm{ALG}$, where $0\\leq \\mathrm{OPT}-\\mathrm{ALG}\\leq f(\\frac{1}{w})\\sum_{p,r}S_{p,r}$. For a fixed input instance and a fixed perturbation function $f$, $\\mathrm{ALG}$ approaches $\\mathrm{OPT}$ as $w\\to +\\infty$. This formalizes the intuition that as we increase the precision $w$, the approximation becomes more accurate. We are happy to add this guarantee to the appendix in the next version.\n\n**Regarding the motivations.**\n\nIndeed, the randomized paper assignment problem has been proposed in [22]. However, [22] focused on one metric of randomness: the maximum assignment probability ($\\mathrm{Maxprob}$). As a result, it is not clear how well [22] aligns with different motivations for randomization other than robustness to malicious behavior (our Motivations 2, 3, and 4 in Section 1). These additional motivations for randomization were not identified in [22]. In fact, these are important reasons why we should care about the general notion of randomness in paper assignments, rather than about optimizing a specific metric (like $\\mathrm{Maxprob}$ in [22]). In practice, conference program chairs likely have some interest in all of these motivations, and want to deploy an assignment that can satisfy all of them as much as possible. Also, even for motivation 1, the metric used in [22] only corresponds to one specific malicious behavior model and our proposed random metric broadens the scope of malicious behavior models as we explain in detail.\n\n**Regarding the additional metrics.**\n\nThe additional metrics are valid because of the following reasons:\n\n- Average maximum probability ($\\mathrm{AvgMaxp}$): $\\mathrm{AvgMaxp}$ corresponds to robustness to malicious behavior (Motivation 1 in Section 1). Depending on the model of malicious behavior, different metrics can fit into the motivation. The vanilla randomness metric $\\mathrm{Maxprob}(\\mathbf x)$ proposed in [22] corresponds to a model where the malicious reviewer-paper pair is a single worst-case pair chosen by Nature. However, if a particular paper $p$ is targeted, then in the worst case, the malicious reviewer targeting $p$ succeeds with probability $\\max_{r}\\lbrace x_{p,r}\\rbrace$. Our new metric $\\mathrm{AvgMaxp}(\\mathbf x)$ calculates the average of these probabilities, corresponding to the model where a random paper $p$ is targeted with a worst-case malicious reviewer. \n- Support size ($\\mathrm{Support}$): $\\mathrm{Support}$ corresponds to evaluation of alternative assignments (Motivation 2 in Section 1). The techniques for off-policy evaluation discussed in [21] can be utilized to estimate the review quality of another non-deployed assignment. Crucially, the precision of the estimation depends on the number of \"positivity violations'' [21] between the deployed assignment $\\mathbf x$ and the non-deployed assignment $\\mathbf y$ of interest with positivity violation defined as an entry $(i,j)$ where $x_{i,j}=0$ but $y_{i,j}\\ne 0$. Since a large number of alternative assignments $\\mathbf y$ may be of interest, to minimize the number of positivity violations, we want to minimize the number of entries in $\\mathbf x$ set to  $0$. This corresponds to maximizing $\\mathrm{Support}(\\mathbf x)$. \n- Entropy ($\\mathrm{Entropy}$): $\\mathrm{Entropy}$ corresponds to the general idea of maximizing randomness. In information theory, entropy characterizes the uncertainty of a random variable. By maximizing entropy, we maximize the uncertainty of our assignment.\n- L2 Norm ($\\mathrm{L2Norm}$): $\\mathrm{L2Norm}$ also corresponds to the general idea of maximizing randomness. Note that for a feasible assignment $\\mathrm x$, $\\sum_{p,r}x_{p,r}=n_p\\ell_p$ must hold. When the assignment is deterministic, $\\sum_{p,r}x_{p,r}^2=n_p\\ell_p$, this is the largest $\\mathrm{L2Norm}$ a feasible assignment can get. Conversely, when $x_{p,r}=\\frac{\\ell_p}{n_r},\\forall p,r$, i.e., $\\mathrm x$ is a uniformly random assignment, its $\\mathrm{L2Norm}$ becomes the smallest possible. Therefore, we can see that $\\mathrm{L2Norm}$ encourages the assignments to be more randomized.\n\n**Regarding Figure 1.**\n\nIn Figure 1, the ideal assignment (a) does not assign more papers to each reviewer than (b). First of all, for reviewers $r_4$ and $r_5$, the assignments in (a) and (b) are the same. For reviewers $r_1,r_2,r_3$, in (a), they have $\\frac{1}{3}$ probability to review paper $p_1,p_2,p_3$ each. So each of them is assigned $1$ paper in total. In (b), this is also the case. For example, $r_1$ has $\\frac{1}{2}$ probability to review $p_2$ and $p_3$ each. So $r_1$ is assigned $1$ paper in total. Therefore, we can see that each reviewer in (a) and (b) reviews the same number of papers.\n\nAgain, we want to thank you for these insightful comments. We hope that the response above addresses most of your concerns about our paper and we would highly appreciate it if you can re-evaluate our paper based on this response.\n"}]

Author rebuttal:
We firstly want to thank all the reviewers for spending the time to understand our work and provide insightful comments. 

We are happy to see that all the reviewers concurred that our proposed method “has better performance” (reviewer 625T) in randomness with “little to no apparent downside (iL2x)" and is "particularly suited to practical use" (FQ98). Also, most of the reviewers concurred that our paper is "well written" (euo8) and ”easy to understand” (625T). 

We are also glad that reviewers recognized that our “theoretical analyses regarding how the proposed PM algorithm outperforms PLRA are sufficient" (625T) and our work tackles "important topic relevant to the NeurIPS community" (iL2x).

Below we provide detailed responses to each reviewer’s questions.

Meta-review: All of the reviewers agree that the paper makes significant contributions to the well-motivated problem of assigning peer-reviewers to manuscripts. The paper builds on work by Jecmen et al, and introduces discounting functions that can controllably increase randomness in paper assignments. During the discussion phase, the authors reported additional experiment results which should be included in an appendix. The authors also clarified several points about the theory, design choices (randomness metrics, perturbation functions, experiment datasets) and Figure 1 which would substantially strengthen the paper's exposition if included in the revised manuscript.
Decision: Accept (spotlight)