I Will Have Order! Optimizing Orders for Fair Reviewer Assignment

We study mechanisms that allocate reviewers to papers in a fair and efficient manner. We model reviewer assignment as an instance of a fair allocation problem, presenting an extension of the classic round-robin mechanism, called Reviewer Round Robin (RRR). Round-robin mechanisms are a standard tool to ensure envy-free up to one item (EF1) allocations. However, fairness often comes at the cost of decreased efficiency. To overcome this challenge, we carefully select an approximately optimal round-robin order. Applying a relaxation of submodularity, γ-weak submodularity, we show that greedily inserting papers into an order yields a (1+γ²)-approximation to the maximum welfare attainable by our round-robin mechanism under any order. Our Greedy Reviewer Round Robin (GRRR) approach outputs highly efficient EF1 allocations for three real conference datasets, offering comparable performance to state-of-the-art paper assignment methods in fairness, efficiency, and runtime, while providing the only EF1 guarantee.

我们研究以公平且高效的方式将评审人员分配给论文的机制。我们将评审人员分配建模为一个公平分配问题的实例，提出了经典循环赛机制的一种扩展，称为评审人员循环赛（RRR）。循环赛机制是确保无嫉妒至多一项（EF1）分配的标准工具。然而，公平往往以效率降低为代价。为了克服这一挑战，我们精心选择一个近似最优的循环赛顺序。通过应用次模性的一种松弛形式，γ - 弱次模性，我们表明将论文贪婪地插入一个顺序中，对于我们的循环赛机制在任何顺序下可达到的最大福利，能产生一个（1 + γ²） - 近似值。我们的贪婪评审人员循环赛（GRRR）方法为三个真实的会议数据集输出了高效的EF1分配，在公平性、效率和运行时间方面提供了与最先进的论文分配方法相当的性能，同时提供了唯一的EF1保证。