PaperlayerView exact revision on arXiv

Source-linked AI summary

Paper Matching with Local Fairness Constraints

Ari Kobren, Barna Saha, Andrew McCallum

arXiv:1905.11924v1cs.DScs.DL

TL;DR

Paper matching must balance reviewer workloads while ensuring each paper’s reviewer group has sufficient expertise. The paper formulates these local fairness goals and presents FairIR and FairFlow; experiments report stronger objective scores for FairIR than fairness-focused state-of-the-art methods, while FairFlow is faster and often close to FairIR.

  • Problem

    Paper matching can leave papers without sufficient collective reviewer expertise and produce highly skewed reviewer workloads.

    Source: §1 · p. 2

  • Method

    The paper formulates local fairness constraints alongside the global objective and reviewer-load bounds, then proposes FairIR, which relaxes and rounds the formulation, and the min-cost-flow heuristic FairFlow.

    Source: §1 · p. 2, §7 · p. 15

  • Results

    FairIR has higher objective scores, more balanced reviewer allocations, and competitive treatment of the most disadvantaged paper versus state-of-the-art fairness-focused approaches; FairFlow is over 2x faster than FairIR and often has fairness and objective scores close to it.

    Source: §1 · p. 3

  • Takeaways & Limitations

    FairFlow’s speed targets program chairs’ need to efficiently construct new matchings after adjusting affinities or assignment constraints.

    Source: §1 · p. 3, §4 · p. 7

    The local fairness formulation is NP-Hard, and constraining minimum assignment affinity can often make assignment problems infeasible.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

Automatically matching reviewers to papers is a crucial step of the peer review process for venues receiving thousands of submissions. Unfortunately, common paper matching algorithms often construct matchings suffering from two critical problems: (1) the group of reviewers assigned to a paper do not collectively possess sufficient expertise, and (2) reviewer workloads are highly skewed. In this paper, we propose a novel local fairness formulation of paper matching that directly addresses both of these issues. Since optimizing our formulation is not always tractable, we introduce two new algorithms, FairIR and FairFlow, for computing fair matchings that approximately optimize the new formulation. FairIR solves a relaxation of the local fairness formulation and then employs a rounding technique to construct a valid matching that provably maximizes the objective and only compromises on fairness with respect to reviewer loads and papers by a small constant. In contrast, FairFlow is not provably guaranteed to produce fair matchings, however it can be 2x as efficient as FairIR and an order of magnitude faster than matching algorithms that directly optimize for fairness. Empirically, we demonstrate that both FairIR and FairFlow improve fairness over standard matching algorithms on real conference data. Moreover, in comparison to state-of-the-art matching algorithms that optimize for fairness only, FairIR achieves higher objective scores, FairFlow achieves competitive fairness, and both are capable of more evenly allocating reviewers.

1 Introduction

Reviewer matching must balance expertise across each paper’s assigned team with fair reviewer workloads, despite scarce experts and tight review timelines. The paper introduces a local fairness formulation and two algorithms, with different guarantees and efficiency trade-offs.

1 Introduction

  • A 2014 NeurIPS experiment found that duplicate reviewer groups disagreed on acceptance 25.9% of the time; re-reviewing submissions would reject about 57% of originally accepted papers.Peer review also faces scarce experts, large submission volumes, and tight conference timelines.Source: §1 · pp. 1–2
  • Maximizing total reviewer-paper affinity can leave a paper with reviewers lacking sufficient topical expertise because experts may be concentrated elsewhere.Experts are scarce, and typical load restrictions make assigning only experts to every submission impossible.Source: §1 · p. 2
  • Earlier fairness approaches can make assignments infeasible with affinity thresholds or ignore overall affinity and lower reviewer-load bounds when optimizing the worst-off paper.Highly uneven reviewer loads may lead reviewers to decline assignments or submit reviews late.Source: §1 · p. 2
  • Local fairness constraints require each paper’s reviewer group to possess sufficient expertise, while reviewer-load bounds balance assignments across reviewers.The formulation jointly optimizes the global objective and includes both upper and lower load bounds.Source: §1 · p. 2
  • FAIRIR relaxes the NP-hard formulation and rounds its solution, maximizing the global objective while allowing only small violations of fairness and load constraints.Experiments report that FAIRIR never violates reviewer-load constraints.Source: §1 · p. 2
  • FAIRIR achieves higher objective scores and more balanced reviewer allocations than fairness-focused state-of-the-art methods, while FAIRFLOW often approaches FAIRIR’s fairness and objective scores in a fraction of the time.FAIRFLOW is more than 2x faster than FAIRIR; both methods allocate reviewers more evenly.Source: §1 · p. 3

2 Reviewer Assignment Problem

The reviewer assignment problem matches papers and reviewers using affinity scores, subject to limits on reviewer workloads and required paper coverage. The standard formulation maximizes total affinity, and lower load bounds can be added to spread assignments more evenly.

2 Reviewer Assignment Problem

  • Reviewer-paper affinities may reflect expertise, bids, area-chair recommendations, or subject-area matches; this paper focuses on matching given those scores, not developing affinity models.Prior affinity modeling approaches include latent semantic indexing, collaborative filtering, and information retrieval [3] [4].Source: §2 · p. 3
  • Load constraints bound papers per reviewer, while coverage constraints specify the number of reviews each paper must receive.Typically, papers receive the same number of reviews.Source: §2 · p. 3
  • The standard RAP maximizes the sum of assigned reviewer-paper affinities subject to reviewer-load upper bounds and paper-coverage requirements.The assignment variables indicate whether a reviewer is assigned to a paper; the formulation can be solved optimally in polynomial time.Source: §2 · p. 4
  • Adding lower bounds on reviewer loads spreads work more evenly, and the resulting formulations are used in conference systems including TPMS, OpenReview, CMT, and HotCRP [26].The paper calls these formulations the TPMS RAP.Source: §2 · p. 4

3 Fair Paper Matching

The section replaces global affinity-only matching with per-paper fairness constraints, then presents FAIRIR as a relaxation-and-rounding method for the resulting hard problem. Its guarantee preserves the global objective while bounding fairness and reviewer-load violations.

3 Fair Paper Matching

  • Equal global objective scores can conceal inequity: Figure 1a gives P3 and P4 lower paper scores by assigning only low-affinity reviewers.The example contrasts two matchings with equivalent objective scores but different paper scores.Source: §3 · p. 4, Figure 1 · p. 5

3.1 Local Fairness Constraints

  • The local fairness formulation adds a minimum paper-score threshold T to the matching problem; it is NP-hard, while minimum-affinity thresholds can make assignments infeasible.The threshold constrains each paper’s score.Source: §3.1 · p. 5

3.2 FAIRIR

  • FAIRIR repeatedly solves a relaxed linear program, fixes integral assignments, and drops a paper fairness or reviewer-load constraint when specified fractional-assignment conditions are met.It drops a paper’s fairness constraint when at most three reviewers are fractionally assigned, or a reviewer’s load constraints when at most two papers are fractionally assigned.Source: §3.2 · pp. 5–6
  • For feasible instances, FAIRIR returns an integer matching that maximizes the global objective, with local-fairness violations at most Amax and load violations at most 1.The theorem requires a feasible instance.Source: §3.2 · p. 6
  • FAIRIR’s relaxed program can establish whether an integer solution will be returned; selecting the highest feasible T by binary search requires repeated program solves.Dropping constraints during iterations can improve scalability without sacrificing the theoretical guarantees.Source: §3.2 · pp. 6–7

4 Faster Flow-based Matching

The section frames reviewer matching as an interactive task requiring fast rematching after program-chair edits, and presents a min-cost-flow heuristic for approximately solving local fairness.

4 Faster Flow-based Matching

  • Interactive matching requires efficient recomputation after program chairs change affinities or impose reviewer-paper constraints; FairFlow is proposed as a faster heuristic without FairIR’s guarantees.The section notes that FairIR’s sequence of linear programs may be too slow for large instances, while FairFlow empirically produces high-quality matches on real data.Source: §4 · p. 7

4.1 Paper Matching as Min-cost Flow

  • The min-cost-flow graph sends coverage-sized flow through reviewer-paper assignment edges, with capacities encoding reviewer and paper limits and costs encoding affinities.An optimal flow corresponds to an optimal TPMS RAP assignment.Source: §4.1 · p. 8

4.2 Locally Fair Flows

  • FAIRFLOW repeats three phases: compute a valid assignment and partition papers, drop a low-affinity reviewer from each paper in P−, then refine assignments to reduce papers scoring below T−Amax.The paper groups assignments by paper score relative to T and T−Amax.Source: §4.2 · pp. 8–9
  • The refinement flow can reassign reviewers between paper groups, and Fact 2 states that it adds no new papers to P−.If refinement leaves papers over capacity, the original flow network repairs the assignment; iterations stop when P− is empty or unchanged for two iterations.Source: §4.2 · p. 9
  • Reviewer load lower bounds are incorporated by first assigning each reviewer Li papers, then routing remaining coverage within residual capacities.The initial and residual flow plans together form a valid assignment, after which the remaining phases proceed normally.Source: §4.2 · p. 10

5 Experiments

Experiments compare four matching algorithms on three conference datasets, including settings with and without reviewer-load lower bounds. Across the reported matching statistics, FAIRFLOW is the fastest fair algorithm, FAIRIR achieves the highest objective score, and FAIRFLOW is competitive with or outperforms PR4A on fairness for the most disadvantaged paper.

5 Experiments

  • Across MIDL, CVPR, and CVPR2018, FAIRFLOW is always the fastest fair algorithm, FAIRIR always achieves the highest objective score, and FAIRFLOW is competitive with or outperforms PR4A on most-disadvantaged-paper fairness.The reported matching statistics cover paper scores (PS) and reviewer assignments (RA).Source: Table 1 · p. 12

5.1 Medical Imaging and Deep Learning

  • With lower bounds on MIDL reviewer loads, FAIRIR has higher minimum and maximum paper scores and a higher objective score than the other algorithms, while running 40% slower than FAIRFLOW.Without lower bounds, the algorithms produce similar profiles, except PR4A and FAIRFLOW have the lowest maximum paper scores and lower objective scores.Source: §5.1 · pp. 11–12, Figure 3 · p. 11

5.2 CVPR

  • On CVPR, FAIRFLOW achieves the highest fairness when lower bounds on reviewing loads are applied, at the expense of a relatively low objective score; FAIRIR’s profile has low-score outliers but many comparatively high scores in quintiles 3–5.FAIRFLOW is 2x faster than FAIRIR when lower bounds are excluded and 100s (15%) faster when they are included.Source: §5.2 · pp. 12–13

5.3 CVPR2018

  • On CVPR2018, PR4A and FAIRIR are the most fair algorithms, while FAIRFLOW remains the most efficient fair algorithm.The experiments use synthetic reviewer-load lower bounds because the dataset has none; the binary search for a suitable threshold did not terminate within five hours.Source: §5.3 · p. 13

6 Related Work

Related work addresses fair assignments through maximin objectives, alternative fairness constraints, and different models of reviewer-paper affinity. The paper contrasts those approaches with its local-fairness formulation and discusses scalability and representation choices.

6 Related Work

  • PR4A maximizes the minimum paper score through repeated maximum-flow problems and has a bounded multiplicative guarantee, while experiments find FAIRFLOW faster with similar solution quality on real conference data.Another rounding approach has an additive constant-factor guarantee but requires a new linear program for each reviewer in each iteration, which is unlikely to scale to large problems.Source: §6 · pp. 13–14
  • Prior fairness approaches include reviewer-load penalties, minimum-affinity objectives, threshold requirements, and global objectives without local constraints.The approaches differ in how they balance reviewer equity, paper scores, and local assignment requirements.Source: §6 · p. 14
  • Reviewer-paper affinity has been modeled with topic vectors, latent semantic indexing, author personas, imputed bids, and coauthorship or citation information; this work uses real-valued affinity scores.Topic-vector methods range from binary representations to real-valued vectors and use ILPs, constraint optimization, or greedy algorithms.Source: §6 · pp. 14–15

7 Conclusion

The conclusion presents local fairness as an NP-hard reviewer-assignment formulation and describes two algorithms for addressing it. Experiments on three conference datasets support FAIRIR’s joint optimization strengths and FAIRFLOW’s efficiency and fairness in practice.

7 Conclusion

  • FAIRIR relaxes the formulation and rounds its solution, with fairness violations bounded by the maximum reviewer-paper affinity and load violations bounded by 1.FAIRFLOW instead solves a sequence of min-cost-flow problems; it lacks theoretical guarantees but constructs highly fair matchings.Source: §7 · p. 15
  • Across three recent-conference datasets, FAIRIR best jointly optimizes the global matching while satisfying fairness constraints, and FAIRFLOW is the most efficient fair-matching algorithm.The paper states that anonymized data is included in its code repository or available upon request.Source: §7 · p. 15

A FAIRIR Guarantees

FAIRIR returns an integer solution that maximizes the global objective, while limiting violations of local fairness and reviewer-load constraints. Its iterative relaxation and rounding procedure terminates, with the proof bounding fairness violations by Amax and load violations by 1.

A FAIRIR Guarantees

  • FAIRIR maximizes the global objective while violating each local fairness constraint by at most Amax and each load constraint by at most 1.These guarantees hold for a feasible instance of the local fairness formulation.Source: A FAIRIR Guarantees · p. 18
  • Reviewer-load constraints are violated by at most 1 when FAIRIR drops them for reviewers fractionally assigned to at most two papers.The proof considers reviewers assigned fractionally to one or two papers and bounds the resulting load deviation.Source: A FAIRIR Guarantees · p. 18
  • Local fairness constraints are violated by at most Amax when FAIRIR drops a paper’s constraint after it has at most three fractionally assigned reviewers.For papers with two fractional reviewers, the proof bounds the paper-score change and fairness violation by Amax; it also treats the three-reviewer case.Source: A FAIRIR Guarantees · pp. 18–19
  • FAIRIR terminates, and its global objective value never decreases as constraints are relaxed and integral variables are fixed.When local fairness constraints are absent, the underlying constraint matrix is totally unimodular and FAIRIR returns an integral solution.Source: A FAIRIR Guarantees · pp. 19–20
  • FAIRIR makes progress by dropping constraints or rounding variables; a basic-feasible-solution count rules out the fractional assignment pattern that could stall it.The stalled pattern would require every reviewer to be fractionally assigned to at least three papers and every paper to at least four reviewers, contradicting the active-constraint bound.Source: A FAIRIR Guarantees · pp. 19–20

B Proof of Fact 2

The flow proof preserves papers’ status relative to the threshold T, allowing their scores to decrease only to T − Amax.

B Proof of Fact 2

  • Papers above T can fall by at most Amax when a reviewer is unassigned, while papers at or below T are unassigned only when the resulting score remains at least T − Amax.Thus, papers in P+ or P0 remain in one of those sets after the step.Source: B Proof of Fact 2 · p. 20
Loading 1905.11924v1…