Abstract
This paper addresses the "PC chair’s nightmare": assigning hundreds of conference papers to referees in a way that is both efficient and fair. By moving beyond simple "maximum happiness" models to a "leximin" approach—which prioritizes the satisfaction of the least-happy referees—the authors provide algorithms that significantly outperform the default assignment logic used by popular tools like EasyChair. Evaluation on real-world data from the ESA 2008 conference demonstrates that our approach significantly improves fairness without compromising overall assignment quality.
Introduction
In the world of academic publishing, Program Committee (PC) chairs must assign submitted papers to referees for review. Referees "bid" on papers, ranking them by interest (e.g., High, Medium, Low). The goal is to find an assignment that respects two hard constraints: Coverage (every paper gets exactly $k$ reviews) and Load Balance (every referee gets roughly the same number of papers).
Most existing software, like EasyChair, uses a "maximum weight" objective. While this maximizes the total satisfaction across the committee, it often results in extreme unfairness. One referee might get all their top-choice papers, while another is stuck with dozens of papers they have zero interest in. This paper seeks to model and solve for Fairness, ensuring that no single referee is unfairly burdened with a "bad" set of papers if a better distribution is mathematically possible.
Methodology
The authors model the problem as an edge-labeled bipartite graph between referees and papers. They explore two primary fairness criteria: the Leximin Principle, which aims to maximize the satisfaction of the "worst-off" referee, and Rank-Maximal Matchings, which prioritizes giving as many people as possible their top-rank choices.
Exact Solutions for Two Preference Levels
For cases with only two preference levels ($\Delta = 2$), the authors provide an exact polynomial-time algorithm. They reduce the problem to a maximum-cost perfect matching in a specially constructed graph using a "round decomposition" technique. This can be visualized as a staircase pattern that divides the assignment space into regions corresponding to different paper ranks.
Approximation for Multiple Preference Levels
When the number of preference levels increases ($\Delta \ge 3$), the problem becomes NP-hard. To solve this, the authors develop approximation algorithms based on Linear Programming (LP) rounding. They use a novel rounding scheme involving "laminar families" and max-flow computations to turn fractional solutions into valid, integral assignments with minimal loss in satisfaction. This is achieved through a graph reduction that models the leximin objective as a maximum-cost matching problem.
Key Insights and Results
The authors evaluated their algorithms using a real-world dataset from the 16th European Symposium on Algorithms (ESA) 2008, featuring 202 papers and 14 referees with three preference levels (High, Medium, and Low interest).
- The "Max-Weight" Trap: Maximizing total weight is socially "efficient" but individually "cruel." If two referees want the same paper, a max-weight algorithm doesn't care who gets it, even if one referee already has many "High Interest" papers and the other has zero.
- Improved Fairness: In the EasyChair assignment, some referees received as few as 8 "High Interest" papers while others got over 50. The Leximin assignment tightened this gap significantly, ensuring the "worst-off" referees were much better served.
- Satisfying Bids: The Leximin and Rank-Maximal assignments completely satisfied the bids of the referees who were most restricted (those who only bid on a few papers), whereas the max-weight approach often ignored them.
- Global Quality: Surprisingly, achieving fairness didn't require a massive sacrifice in total satisfaction. The Leximin assignment used roughly the same total number of high-rank edges as the max-weight version; it just distributed them more equitably.
Conclusion
Fairness in referee assignment is both mathematically formalizable and computationally tractable through approximation. By shifting focus from aggregate satisfaction to the leximin principle, PC chairs can ensure a more motivated and fairly treated committee. While the current work focuses primarily on referee satisfaction, future developments could integrate these algorithms into mainstream tools like EasyChair to provide a more balanced experience for both reviewers and authors.
Summary updated