PaperlayerView exact revision on arXiv

Source-linked AI summary

PeerReview4All: Fair and Accurate Reviewer Assignment in Peer Review

Ivan Stelmakh, Nihar B. Shah, Aarti Singh

arXiv:1806.06237v2stat.MLcs.DScs.ITcs.LGmath.IT

TL;DR

Automated reviewer assignment must balance fairness to papers with accurate recovery of accepted papers. PeerReview4All builds assignments through incremental max-flow, and the reported experiments show it achieves a strong balance of fairness and total similarity, though it is slower than other algorithms.

  • Problem

    Automated reviewer assignment must balance review quality for disadvantaged papers with accurate selection of top papers, despite noisy reviews and subjective opinions.

    Source: §1 · pp. 1–2

  • Method

    PeerReview4All constructs candidate assignments using incremental max-flow and selects an assignment with strong fairness guarantees.

    Source: §1 · p. 2, §4.1 · p. 9

  • Results

    PeerReview4All achieved maximum or near-maximum fairness and total sum similarity in three experiments, and the authors report the best balance of those objectives despite slower runtime.

    Source: §8.3.2 · pp. 29–30

  • Takeaways & Limitations

    The reported experiments indicate that PeerReview4All can balance fairness and total sum similarity, even though it optimizes total similarity only heuristically.

    Source: §8.3.2 · p. 30

    The fully automated procedure is presented as a guideline for area chairs and a first-order estimate of the total ranking of submitted papers.

    Source: §6.2 · p. 17

Abstract

from arXiv · show

We consider the problem of automated assignment of papers to reviewers in conference peer review, with a focus on fairness and statistical accuracy. Our fairness objective is to maximize the review quality of the most disadvantaged paper, in contrast to the commonly used objective of maximizing the total quality over all papers. We design an assignment algorithm based on an incremental max-flow procedure that we prove is near-optimally fair. Our statistical accuracy objective is to ensure correct recovery of the papers that should be accepted. We provide a sharp minimax analysis of the accuracy of the peer-review process for a popular objective-score model as well as for a novel subjective-score model that we propose in the paper. Our analysis proves that our proposed assignment algorithm also leads to a near-optimal statistical accuracy. Finally, we design a novel experiment that allows for an objective comparison of various assignment algorithms, and overcomes the inherent difficulty posed by the absence of a ground truth in experiments on peer-review. The results of this experiment as well as of other experiments on synthetic and real data corroborate the theoretical guarantees of our algorithm.

1 Introduction

The paper targets fair and statistically accurate reviewer assignment, motivated by the consequences of poor reviews and the difficulty novel or interdisciplinary work faces. It proposes PeerReview4All, analyzes its guarantees, and evaluates it through experiments designed to compare assignment algorithms objectively.

1 Introduction

  • Incorrect reviews can harm publication quality, while novel, non-mainstream, and interdisciplinary papers face greater difficulty gaining acceptance.These concerns motivate the paper’s dual goals of fairness and accuracy.Source: §1 · pp. 1–2
  • PeerReview4All uses incremental max-flow to construct candidate assignments suited to different similarity structures, then selects among them.The paper’s goals are fairness to papers and statistical accuracy in recovering top papers.Source: §1 · p. 2
  • The algorithm is optimal up to a constant factor for max-min fairness and can achieve stronger guarantees, including exact optimality in some cases.It fixes the assignment for the worst-off paper, then proceeds to the next worst-off paper until all papers are assigned.Source: §1 · p. 2
  • PeerReview4All has near-optimal guarantees for identifying the top papers under an objective-score model, with minimax risk measured by incorrect accept/reject decisions.The analysis concerns a model with a true objective score for each paper.Source: §1 · p. 2
  • The paper proposes a subjective-score model and proves PeerReview4All is near-optimal for that setting as well.The model captures reviewers’ subjective opinions.Source: §1 · p. 2
  • The authors designed an MTurk experiment to compare algorithms objectively despite the absence of peer-review ground truth, alongside synthetic and conference-data evaluations.The evaluations include a reconstructed ICLR 2018 similarity matrix and results from Kobren et al. (2019).Source: §1 · pp. 2–3

2 Related literature

Prior work addresses similarity computation, cumulative assignment objectives, fairness, and related coverage and diversity goals. This paper distinguishes assignment fairness from total-similarity optimization and frames the assignment-to-acceptance pipeline as a statistical problem.

Computing similarities

  • The assignment stage uses reviewer–paper similarities as input, while prior methods also study how those similarities are computed.The paper treats similarity computation as a black box; automated systems may combine bids with text-matching similarities.Source: §2 · pp. 3, 6

Cumulative goal functions

  • Earlier reviewer-assignment work often maximizes cumulative similarity, an objective that can discriminate against some papers, including non-mainstream submissions.This paper instead focuses on protecting the most disadvantaged paper.Source: §2 · pp. 3–4

Fairness

  • Prior fairness approaches include reviewer-bid objectives and an integer-programming relaxation with rounding, whose additive guarantees can be vacuous for some similarity matrices.The paper contrasts these with its multiplicative constant-factor guarantee.Source: §2 · p. 4

Fair division

  • Fair-division methods cannot be directly applied because reviewer assignment requires a fixed number of reviewers per paper and reviewer-load constraints.The paper says these constraints permit an approximation guarantee depending on λ rather than the total number of papers and reviewers.Source: §2 · p. 5

Statistical aspects

  • To the authors’ knowledge, prior conference peer-review work had not analyzed the full assignment-to-acceptance pipeline statistically; their analysis considers objective and novel subjective-score models.They report that higher assignment fairness leads to better acceptance quality.Source: §2 · p. 5

Coverage and diversity

  • Related work also pursues reviewer diversity and topic coverage, and addresses other peer-review challenges including bias, miscalibration, subjectivity, and strategic behavior.The paper notes that topic-coverage techniques can be combined with its algorithm to maintain fairness and broad coverage.Source: §2 · pp. 5–6

3 Problem setting

The problem setting formalizes reviewer assignment under reviewer and paper load constraints, with fairness and recovery of top papers as joint goals. Its fairness objective protects the paper with the lowest total reviewer similarity rather than maximizing total similarity across papers.

3.1 Preliminaries and notation

  • The setting requires assigning each paper to λ distinct reviewers while each reviewer handles at most μ papers, with nμ ≥ mλ ensuring feasibility.The statistical goal is to recover the top k papers from m submissions.Source: §3.1 · p. 6
  • The input is a reviewer–paper similarity matrix, and a feasible assignment respects reviewer and paper loads; similarity is treated as indicative of review competence.The paper assumes similarity computation is given rather than addressing how to produce it.Source: §3.1 · p. 6
  • Acceptance is modeled by estimating paper scores from reviewer evaluations and selecting the top k, with Hamming-error tolerance allowed when exact recovery is too demanding.The paper notes real program-committee decisions also use comments and discussion, beyond this simplified setup.Source: §3.1 · pp. 6–7

3.2 Fairness objective

  • The toy example shows that maximizing total similarity can leave a paper with an insufficiently expert reviewer, while an alternative assignment gives every paper similarity of at least 1/5.The example has three papers and three reviewers, with one reviewer lacking expertise in two papers.Source: §3.2 · p. 7
  • Max-min fairness maximizes the minimum sum similarity across papers; the objective can generalize through a monotonically increasing transformation of similarities, but exact optimization is NP-hard in a stated case.The paper illustrates a threshold transformation that treats reviewers as strong or weak for each paper.Source: §3.2 · p. 8
  • PeerReview4All first optimizes the worst-off paper and then proceeds through the second-worst-off and subsequent papers, fixing assignments in turn.The paper presents this as a further property beyond optimizing the minimum-quality objective.Source: §3.2 · p. 8

4 Reviewer assignment algorithm

PeerReview4All builds reviewer assignments through incremental max-flow and repeatedly fixes the most disadvantaged papers. Its examples show how it adapts to different similarity structures.

4.1 Algorithm

  • The algorithm tries each κ from 1 to λ, combines κ strong reviewers with λ−κ additional reviewers, then fixes the most disadvantaged papers and repeats for the rest.This iterative procedure aims to avoid bottlenecks from irrelevant papers with low average similarities.Source: §4.1 · pp. 9–10
  • The subroutine adds reviewer–paper edges in decreasing similarity order until a full max-flow assigns κ reviewers to each paper, maximizing the lowest assigned similarity.The flow respects reviewer and paper load constraints; integer capacities ensure an integer flow that can be found in polynomial time.Source: §4.1 · p. 9
  • Different max-flows may yield different assignments; any satisfies the worst-case fairness objective, while a max-cost choice can also favor high average quality.The paper also notes that its approximation and statistical guarantees hold for any max-flow assignment.Source: §4.1 · pp. 9–10

4.2 Example

  • In the ideal scenario where every paper has λ strong reviewers, PeerReview4All finds an assignment close to optimal.When some critical papers have only η strong reviewers, trying κ=η can still yield fairness at least ηζ and an assignment close to optimal.Source: §4.2 · p. 12
  • The examples illustrate that PeerReview4All adapts to the similarity matrix’s structure to guarantee fairness.The contrasted scenarios represent papers with enough strong reviewers and critical papers with fewer than λ strong reviewers.Source: §4.2 · p. 12

5 Approximation guarantees

The paper establishes max-min fairness guarantees for PeerReview4All, extends them to successive worst-off papers, and compares the guarantees with prior algorithms.

5.1 Max-min fairness

  • At λ=1, PeerReview4All finds the exact solution; with the typical λ=3, it guarantees a constant-factor approximation.The paper notes that the fraction in its bound is read as 1 when it takes the forms 0/0 or ∞/∞.Source: §5.1 · p. 13

5.2 Beyond worst case

  • After fixing the assignment for the worst-off papers, PeerReview4All repeats the procedure to find a fair assignment for the remaining papers.For each iteration, the fairness of the papers fixed is close to the best possible given assignments fixed in earlier iterations.Source: §5.2 · pp. 14–15

5.3 Comparison to past literature

  • Unlike ILPR, PeerReview4All guarantees a non-trivial worst-case multiplicative approximation of 1/λ; ILPR’s guarantee can be vacuous when optimal fairness is small.For λ=1, PeerReview4All recovers the optimally fair assignment and the classical result of Garfinkel (1971).Source: §5.3 · pp. 15–16

6 Objective-score model

The objective-score analysis models noisy paper scores and studies how reviewer assignments and estimators affect recovery of the top k papers. PeerReview4All is shown to be minimax near-optimal for exact and approximate recovery, adapting to similarity structure.

6.1 Model setup

  • The objective-score model assumes each paper has an unknown true quality and reviewer scores are noisy estimates, with noise variance depending on reviewer-paper similarity.The analysis assumes the variance function is known; reviewer-specific bias is omitted for simplicity.Source: §6.1 · p. 16

6.2 Estimator

  • The estimators rank papers by estimated true scores; the mean estimator is model-agnostic, while the MLE has minimum variance among linear unbiased estimators.The mean estimator has previously been predictive of acceptance decisions in grant-review and homework-grading settings.Source: §6.2 · pp. 16–17

6.3 Analysis

  • The analysis covers both MLE and mean estimators, considering exact top-k recovery and recovery under a Hamming-error tolerance.The paper analyzes minimax risk in terms of incorrect accept/reject decisions.Source: §6.3 · p. 17

6.3.1 Exact top k recovery

  • For exact recovery, the minimax bounds are sharp up to a factor tied to PeerReview4All’s assignment approximation and a constant pre-factor.The approximation factor can be better than 1/λ for some similarity matrices.Source: §6.3.1 · p. 18
  • Across similarity-matrix classes, PeerReview4All adapts its assignments and can be simultaneously minimax near-optimal for exact top-k recovery.For the classes Sκ(v), the upper bound has no approximation factor; the results also extend to a generalized sub-Gaussian reviewer model.Source: §6.3.1 · p. 19

6.3.2 Approximate recovery under Hamming error

  • For approximate recovery, the analysis also establishes adaptive guarantees for the similarity-matrix classes Sκ(v).The adaptive result extends to Hamming error, with the same class of matrices used for the exact-recovery adaptive result.Source: §6.3.2 · p. 20
  • PeerReview4All produces assignments that are minimax near-optimal for both exact and Hamming-error-tolerant recovery of the top k papers.For approximate recovery, the bounds differ by an assignment approximation factor and a pre-factor depending on constants ν1 and ν2.Source: §6.3.2 · p. 20

7 Subjective-score model

The subjective-score model treats reviewers’ opinions as distinct from review noise and analyzes whether assignments support recovery of the top papers by mean full-competence subjective scores. The analysis finds PeerReview4All near-optimal for both exact and approximate recovery under the stated model classes.

7.1 Model

  • The model separates each reviewer’s subjective opinion from noise, defining the opinion as the score under full expertise and modeling real reviews as noisy.Higher reviewer-paper similarity makes the observed score a better representation of that reviewer’s subjective score.Source: §7.1 · p. 21

7.2 Analysis

  • Its target is recovery of the top k papers by their mean full-competence subjective scores, using the mean-score estimator.The analysis studies guarantees for this estimator under the subjective-score model.Source: §7.1 · p. 21, §7.2 · p. 21, §7.2.1 · pp. 21–22

7.2.1 Exact top k recovery

  • For exact top-k recovery, PeerReview4All has strong guarantees, with a converse result supporting near-optimality under the subjective-score setting.Theorem 4 states the result for specified separation and similarity conditions.Source: §7.2.1 · p. 22

7.2.2 Approximate recovery under Hamming error

  • With Hamming error tolerance t, PeerReview4All is minimax-optimal up to a constant pre-factor and approximation factor for subjective scores in Fk,t(A,δ).The analysis extends the score class to allow a nonzero error tolerance.Source: §7.2.2 · pp. 22–23

8 Experiments

The experiments compare PeerReview4All with other assignment algorithms on fairness, total similarity, and directly measured acceptance accuracy across synthetic and conference-based similarity matrices. An Amazon Mechanical Turk experiment enables direct accuracy evaluation, including cases where fairness-focused assignments may incur more errors when they neglect other questions.

8.1.1 Fairness

  • Across five synthetic cases, PeerReview4All matched or exceeded TPMS in fairness, while its total similarity was close to or higher than ILPR’s and Hard’s.The simulations included cases with non-mainstream papers, weak reviewers, unusually strong reviewers, an adverse instance, and sparse similarities. In C1, PeerReview4All, ILPR, and Hard assigned the four best possible reviewers to non-mainstream papers; in C2 and C3, ILPR failed to find a fair assignment. In C4, PeerReview4All found an assignment with approximation ratio 1/3, and in C5 all algorithms recovered fair assignments, though Hard had low total similarity.Source: Table 2 · p. 24, §8.1.1 · pp. 24–25

8.1.2 Statistical accuracy

  • In the first four synthetic cases, PeerReview4All significantly outperformed TPMS in fairness and fraction of incorrectly accepted papers.The reported accuracy relationship holds provided average sum similarity does not decrease dramatically. In C4, PeerReview4All performed well on accuracy despite suboptimal fairness; in C5, Hard had lower accuracy because it did not optimize for the second worst-off paper, unlike PeerReview4All and ILPR.Source: Figure 1 · p. 25, §8.1.2 · p. 26, Figure 2 · p. 26

8.2.2 Evaluation

  • On the approximate ICLR’18 matrix, PeerReview4All had significantly higher fairness than TPMS, with cumulative similarity only marginally below the optimal value.The matrix constructed by Xu et al. (2019b) contained 2,435 reviewers and 911 papers. Hard was excluded because computing its optimally fair assignment was infeasible, and ILPR was excluded because its implementation was computationally inefficient and source code unavailable.Source: §8.2 · p. 26, Table 3 · p. 27, §8.2.2 · p. 27
  • On the ICLR’18 comparison, later PeerReview4All iterations improved the second worst-off paper, balancing quality toward worst-off papers at the expense of the most benefiting papers.The fairness guarantees were achieved after one iteration, while subsequent iterations continued improving the assignment for papers beyond the worst-off one.Source: §8.2.2 · pp. 27–28, Figure 3 · p. 28

8.3.1 Brief discussion of the algorithms by Kobren et al.

  • FairIr optimizes total similarity with additive fairness violations bounded by the maximum matrix entry, whereas FairFlow is a lower-complexity heuristic without theoretical guarantees.Kobren et al. (2019) formulate total-similarity optimization subject to a per-paper fairness threshold. PeerReview4All prioritizes fairness but can use a max-cost heuristic to improve total similarity; comparisons exclude cases enforcing a lower bound on reviewer load, which PeerReview4All does not support.Source: §8.3.1 · pp. 28–29

8.3.2 Summary of the experiments

  • In Kobren et al. (2019)’s MIDL and CVPR experiments, PeerReview4All was significantly slower than the other algorithms, but its first iteration ran in under three hours on the largest instance of more than 5,000 papers.On large instances, only one iteration was computed in a reasonable time; the paper notes that one iteration suffices for PeerReview4All’s fairness guarantees.Source: Table 4 · p. 29, §8.3.2 · p. 29
  • Across three experiments, PeerReview4All achieved maximum or near-maximum fairness and total similarity, while other algorithms substantially lagged on at least one objective in two experiments.It was considerably, but not prohibitively, slower than other algorithms and optimized total similarity only heuristically.Source: §8.3.2 · p. 30

8.4 Experiment on Amazon Mechanical Turk

  • The Mechanical Turk experiment enabled direct accuracy evaluation despite conference-review data lacking ground-truth rankings and reviews for alternative assignments.The experiment used crowdsourcing workers as reviewers and general-knowledge questions as papers.Source: §8.4 · p. 30

8.4.1 Design of experiment

  • The study recruited 80 workers to answer 60 country-flag questions, with three participants’ incomplete responses discarded.The 60 flags comprised 10 countries from each of six geographic regions.Source: §8.4.1 · pp. 30–31

8.4.2 Evaluation

  • Across 1,000 iterations, the researchers estimated worker-question similarities from regional gold-standard answers and compared five assignments using majority votes on unresolved questions.Each region’s 10 questions were split into 8 randomly chosen gold-standard and 2 unresolved questions; 40 workers were sampled, each question assigned to 3 workers, and each worker given at most 2 questions. Ties counted as mistakes.Source: §8.4.2 · p. 31
  • All non-trivial algorithms significantly outperformed random assignment, while ATPMS incurred about 8% increased error compared with APR4A.Results were measured as the fraction of incorrectly estimated answers across the five assignments.Source: §8.4.2 · p. 31, Table 5 · p. 32
  • AHARD incurred more errors than APR4A and AILPR because it prioritized the most disadvantaged question without considering the remaining questions.APR4A slightly outperformed AILPR on error despite slightly lower average fairness, while maintaining high conventional sum similarity alongside near-optimal fairness.Source: §8.4.2 · p. 31
  • The flag-identification task had relatively homogeneous similarities, whereas greater heterogeneity in conference peer review is expected to amplify PeerReview4All’s improvements over TPMS and ILPR.The passage attributes the difference to non-mainstream papers and very strong and very weak reviewers in peer review.Source: §8.4.2 · p. 31

9 Proofs

The proofs establish fairness and statistical guarantees using comparisons with optimal assignments, variance bounds, hypothesis testing, score-separation arguments, and Fano reductions. They also adapt these arguments to corollaries and subjective-score models.

9.1 Proof of Theorem 1

  • Theorem 1’s proof combines a lower bound for PeerReview4All with an upper bound for the optimal assignment to obtain result (7).The lower-bound argument uses a maximum flow to ensure assigned reviewer–paper pairs meet a similarity threshold; the proof then takes a maximum over κ and combines the bounds.Source: §9.1 · p. 32

9.2 Proof of Corollary 1

  • Corollary 1’s proof reapplies Theorem 1’s argument to the remaining papers, updated similarity matrix, and reviewer-specific load limits.At each iteration, the fairness of the worst-off papers is lower-bounded by the largest fairness among the candidate assignments, yielding bound (8).Source: §9.2 · p. 33

9.3.1 Proof of upper bound

  • Theorem 2’s upper-bound proof links f = 1 − h to minimizing maximum variance for the mean estimator and f = h−1 to doing so for the MLE.In each case, the algorithm also maximizes fairness with respect to the corresponding transformation function.Source: §9.3.1 · p. 34

9.3.2 Proof of lower bound

  • For Theorem 2’s lower bound, the proof applies Fano’s inequality to m−k+1 instances sharing a similarity matrix but differing in their top-k sets.The stated result applies for m > 6 and a sufficiently small constant c.Source: §9.3.2 · pp. 35–37

9.3.3 Proof of Lemma 1

  • Lemma 1’s proof bounds error for the mean and MLE estimators; the mean-estimator argument uses Hoeffding’s inequality and a union bound across top-k and other papers.The MLE case proceeds similarly to the averaging-estimator proof.Source: §9.3.3 · p. 37

9.4.1 Proof of upper bound

  • Corollary 2’s upper-bound proof applies Lemma 1 after deriving an upper bound on the variance for the PeerReview4All assignment.It completes the argument by applying the same chain of bounds used in Theorem 2’s proof.Source: §9.4.1 · p. 38

9.4.2 Proof of lower bound

  • For Corollary 2’s lower bound, the proof uses Fano’s inequality and constructs a similarity matrix where each paper has exactly κ reviewers with similarity v.Every feasible assignment gives each paper at most κ reviewers with nonzero similarity.Source: §9.4.2 · p. 38
  • The lower-bound argument for this earlier instance family applies Fano’s inequality uniformly over feasible assignments when m > 6 and the universal constant is sufficiently small.Unlike the proof of Theorem 2, the score distribution here depends on the chosen assignment.Source: §9.4.2 · pp. 38–39

9.5.1 Proof of upper bound

  • A pairwise score-separation bound and union bound establish the Theorem 3 upper bound, ensuring the stated high-probability recovery guarantee.The proof compares papers among the top k − t and bottom m − k − t, then uses the resulting separation to control errors among accepted papers.Source: §9.5.1 · pp. 39–40

9.5.2 Proof of lower bound

  • Theorem 3’s lower bound constructs well-separated top-k sets and applies Fano’s inequality, using a coding-theoretic lemma attributed to Levenshtein (1971).The construction makes recovery of the sampled problem instance necessary for recovery of its top-k set, and the Fano argument yields a contradiction.Source: §9.5 · p. 39, §9.5.2 · pp. 40–41

9.6.1 Proof of upper bound

  • For Corollary 3, the upper-bound proof reuses Theorem 3(a)’s argument with APR4A and the maximum-likelihood estimator substituted for the earlier assignment-estimator pair.The lower-bound proof reuses Theorem 3’s instance family, bounds divergence for assignment-dependent score distributions, and applies Fano’s inequality.Source: §9.6.1 · pp. 41–42, §9.6.2 · p. 42

9.7 Proof of Theorem 4

  • Theorem 4’s upper-bound proof repeats the averaging-estimator argument from Theorem 2 for the ranking induced by each feasible assignment.For the lower bound, a constructed parameter choice makes the induced ranking independent of assignment, transferring Theorem 2(b)’s bound to the subjective-score model.Source: §9.7.1 · p. 43, §9.7.2 · p. 43

9.8 Proof of Theorem 5

  • For the upper bound, the goal mimics the averaging-estimator upper-bound goal from Theorem 3; for the lower bound, Section 9.7.2’s argument directly transfers Theorem 3’s bound to the subjective-score model.Source: §9.8.1 · p. 43, §9.8.2 · p. 43

10 Discussion

The discussion presents PeerReview4All as an approach to fairness and accuracy in conference review and outlines open questions about its guarantees, statistical model, and similarity inputs.

10 Discussion

  • PeerReview4All is designed to address fairness and accuracy concerns in conference review, including difficulties faced by non-mainstream and interdisciplinary research.The authors say its guarantees hold promise for deployment in conference peer review.Source: §10 · p. 43
  • Whether a polynomial-time algorithm can improve on the paper’s 1/λ worst-case approximation guarantee remains open, as does improving PeerReview4All’s computational efficiency.The authors suggest implementing Subroutine 1 with algorithms specialized for layered graphs rather than general max-flow algorithms.Source: §10 · pp. 43–44
  • The statistical analysis characterizes a simplified paper-acceptance procedure, while reviewer confidence and inter-reviewer discussions are factors that could be added to the model.Source: §10 · p. 44
  • Improving reviewer-paper similarity assessment is another open problem, including the possibility of jointly addressing assessment and assignment using feedback from earlier conference iterations.Source: §10 · p. 44

Appendix

The appendix provides supplementary materials and additional discussion.

Appendix

  • The appendix provides supplementary materials and additional discussion.Source: Appendix · p. 48

A Discussion of approximation results

The approximation-results discussion assumes f(s) = s and uses c to denote a matrix whose entries are all c.

A Discussion of approximation results

A.1 Example for ILPR algorithm.

The ILPR example shows how rounding can destroy fairness even when its fractional assignment is optimally fair. For the stated parameter choices, PeerReview4All exactly recovers the fair assignment in the simulations.

A.1 Example for ILPR algorithm.

  • The example groups papers and reviewers into three matching groups, with n_r = m_r, n_3 > λ, and ε < e_s.Here e_s = n_1/(n_1+n_2).Source: §A.1 · p. 48
  • ILPR’s fractional optimum gives each paper in the first two groups total similarity λe_s, while third-group papers attain at most λe_s.The passage states that deviations from this fractional assignment strictly decrease fairness.Source: §A.1 · p. 48
  • For the constructed similarity matrices, ILPR’s rounding can produce zero fairness although a feasible assignment has fairness at least e_s − ε.The fractional assignment is most fair, but rounding restricts each paper to reviewers receiving a nonzero fraction in that assignment.Source: §A.1 · pp. 48–49
  • For λ ∈ {1, 2, 3, 4} and the stated simulation parameters, PeerReview4All exactly recovers the fair assignment and outperforms ILPR.Table 6 reports fairness for algorithms on this class of similarity matrices.Source: §A.1 · p. 49, Table 6 · p. 49

A.2 Sub-optimality of TPMS

This example shows that optimizing the objective in (2) can be highly suboptimal under the fairness criterion in (4). It contrasts TPMS’s assignment with the assignments produced by PeerReview4All and AHARD.

A.2 Sub-optimality of TPMS

  • Optimizing objective (2) can be highly suboptimal with respect to criterion (4), even when f is the identity function.The example uses similarities described by a block matrix and contrasts the resulting assignments.Source: §A.2 · p. 49
  • TPMS assigns the first λ reviewers to the first λ papers and the remaining reviewers to the remaining papers.The assignment within each group is arbitrary.Source: §A.2 · p. 49
  • Table 7’s similarity example yields a 1/λ approximation factor for PeerReview4All; PeerReview4All and AHARD instead assign reviewers across the two paper groups.The cited passages describe the cross-group assignment but do not report its fairness value here.Source: §A.2 · p. 49, Table 7 · p. 50

A.3 Example of 1/λ approximation factor for APR4A

A four-paper, four-reviewer example demonstrates PeerReview4All’s 1/λ approximation factor. Its achieved fairness approaches one-half of the optimum when λ = 2.

A.3 Example of 1/λ approximation factor for APR4A

  • The instance has m = n = 4 and λ = μ = 2, with similarities given in Table 7.The section evaluates the algorithm’s fairness using its intermediate assignments in Table 8.Source: §A.3 · p. 50
  • With λ = 2, PeerReview4All’s approximation factor is arbitrarily close to 1/2 = 1/λ in the example.The optimal max-min fairness is 0.6; the algorithm’s candidate assignments have fairness 0.3 + ε and 0.2.Source: §A.3 · p. 50

B Computational aspects

PeerReview4All’s max-flow implementation can be optimized, and its guarantees permit early stopping. The computational comparison with ILPR depends on whether that algorithm is also stopped early.

B Computational aspects

  • The algorithm’s computational complexity can be improved without losing its approximation or statistical guarantees.The passage mentions alternative max-flow methods and binary search as possible optimizations.Source: B Computational aspects · p. 51
  • Binary search can reduce PeerReview4All’s max-flow iterations to O(λm log mn), while the passage also describes a slightly optimized version as asymptotically better than full ILPR.Full ILPR requires O(m^2) linear-programming solutions; the optimized PeerReview4All version is described as requiring O(λm log mn) such solutions.Source: B Computational aspects · p. 51
  • After its first iteration, PeerReview4All retains the max-min approximation and statistical guarantees, but not the guarantee for optimizing papers beyond the worst-off paper.Stopping after a constant number of iterations makes its complexity comparable to TPMS; early termination of ILPR also brings the algorithms to a similar footing.Source: B Computational aspects · p. 51

C Topic coverage

Multidisciplinary papers motivate topic coverage: reviewers should be similar to a paper and represent its related research fields. PeerReview4All incorporates coverage into max-flow tie-breaking while preserving its established guarantees.

C Topic coverage

  • Topic coverage means assigning multidisciplinary papers reviewers who both match the paper and represent its related research areas.The section motivates this with papers spanning fields such as particle physics, computer science, and statistics.Source: C Topic coverage · p. 51
  • Long et al. (2013) measure coverage by the total number of distinct paper topics covered across assignments, while allowing at most λ reviewers per paper.Their coverage objective is to be maximized subject to paper and reviewer load constraints; this differs from assigning exactly λ reviewers as in PeerReview4All.Source: C Topic coverage · pp. 51–52
  • The greedy coverage algorithm can prioritize global coverage at the expense of some papers and may assign fewer than λ reviewers, or none, to a paper.It has a constant-factor approximation guarantee for the coverage objective, but not a guarantee that every paper receives λ reviewers.Source: C Topic coverage · p. 52
  • PeerReview4All uses Long et al. (2013)'s greedy coverage heuristic to choose feasible pairs in max-flow tie-breaking, while ensuring each paper receives its requested number of reviewers.The heuristic encourages topic coverage, although the greedy algorithm's approximation guarantee for coverage no longer holds.Source: C Topic coverage · p. 52
  • The combined procedure avoids sacrificing papers for global coverage by restricting feasible pairs to reviewers with high similarity to each paper.It modifies only max-flow tie-breaking, so the guarantees established for PeerReview4All continue to hold.Source: C Topic coverage · p. 52
Loading 1806.06237v2…