Mitigating Manipulation in Peer Review via Randomized Reviewer Assignments

Introduction

Peer review, the evaluation of work by others working in the same field as the producer of the work or with similar competencies, is a critical component of scientific research. It is regarded favorably by a significant majority of researchers and is seen as being essential to both improving the quality of published research and validating the legitimacy of research publications . Due to the wide adoption of peer review in the publication process in academia, the peer-review process can be very high-stakes for authors, and the integrity of the process can significantly influence the careers of the authors (especially due to the prominence of a “rich get richer” effect in academia ).

However, there are several challenges that arise in peer review relating to the integrity of the review process. In this work, we address three such challenges for peer review in academic conferences where a number of papers need to be assigned to reviewers at the same time.

In order to achieve a good reviewer assignment, peer review systems must solicit some information about their reviewers’ knowledge and interests. This inherently presents opportunities for manipulation, since reviewers can lie about their interests and expertise. For example, reviewers often are expected to bid on the papers they are interested in reviewing before an assignment algorithm is run to determine the paper assignment. This system can be manipulated, and in fact this is known to have happened in at least one ACM conference :

“Another SIG community has had a collusion problem where the investigators found that a group of PC members and authors colluded to bid and push for each other’s papers violating the usual conflict-of-interest rules.”

The problem of manipulation is not limited to the bidding system, as practically anything used to determine paper assignments (e.g., self-reported area of expertise, list of papers the reviewer has published) can potentially be manipulated; in more extreme cases, authors have been known to entirely falsify reviewer identities to get a desired reviewer assignment . In some cases, unethical authors may enter into deals with potential reviewers for their paper, where the reviewer agrees to attempt to get assigned to the author’s paper and give it a favorable review in exchange for some outside reward (e.g., as part of a quid-pro-quo arrangement for the reviewer’s own paper in another publication venue). To preserve the integrity of the reviewing process and maintain community trust, the paper assignment algorithm should guarantee the mitigation of these kinds of arrangements.

In “torpedo reviewing,” unethical reviewers attempt to get assigned to papers they dislike with the intent of giving them an overly negative review and blocking the paper from publication. This can have wide-reaching consequences :

“If a research direction is controversial in the sense that just 2-or-3 out of hundreds of reviewers object to it, those 2 or 3 people can bid for the paper, give it terrible reviews, and prevent publication. Repeated indefinitely, this gives the power to kill off new lines of research to the 2 or 3 most close-minded members of a community, potentially substantially retarding progress for the community as a whole.”

One special case of torpedo reviewing has been called “rational cheating,” referring to reviewers negatively reviewing papers that compete with their own authored work . The high-stakes atmosphere of academic publishing can exacerbate this problem :

“The cutthroat attitude that pervades the system results in ludicrous rejections for personal reasons—if the reviewer feels that the paper threatens his or her own research or contradicts his or her beliefs, for example.”

A paper assignment algorithm should guarantee to authors that their papers are unlikely to have been torpedo-reviewed.

For transparency and research purposes, conferences may wish to release the paper-reviewer similarities and the paper assignment algorithm used after the conference. However, if the assignment algorithm is deterministic, this would allow for authors to fully determine who reviewed their paper, breaking the anonymity of the reviewing process. Even when reviewer and paper names are removed, identities can still be discovered (as in the case of the Netflix Prize dataset ). Consequently, a rigorous guarantee of anonymity is needed in order to release the data.

Although these challenges may seem disparate, we address all of them under a common umbrella framework. Our contributions are as follows:

Conceptual: We formulate problems concerning the three aforementioned issues in peer review, and propose a framework to address them through the use of randomized paper assignments (Section 3).

Theoretical: We design computationally efficient, randomized assignment algorithms that optimally assign reviewers to papers subject to given restrictions on the probability of assigning any particular reviewer-paper pair (Section 4). We further consider the more complex case of preventing suspicious pairs of reviewers from being assigned to the same paper (Section 5). We show that finding the optimal assignment subject to arbitrary constraints on the probabilities of reviewer-reviewer-paper assignments is NP-hard. In the practical special case where the program chairs want to prevent pairs of reviewers within the same subset of some partition of the reviewer set (for example, reviewers at the same academic institution or with the same geographical area of residence) from being assigned to the same paper, we present an algorithm that finds the optimal randomized assignment with this guarantee.

Empirical: We test our algorithms on datasets from past conferences and show their practical effectiveness (Section 6). As a representative example, on data reconstructed from ICLR 2018, our algorithms can limit the chance of any reviewer-paper assignment to $50\%$ while achieving $90.8\%$ of the optimal total similarity. Our algorithms can continue to achieve this similarity while also preventing reviewers with close associations from being assigned to the same paper. We further demonstrate, using the ICLR 2018 dataset, that our algorithm successfully prevents manipulation of the assignment by a simulated malicious reviewer.

All of the code for our algorithms and our empirical results is freely available online.https://github.com/theryanl/mitigating_manipulation_via_randomized_reviewer_assignment/

Related Literature

Many paper assignment algorithms for conference peer review have been proposed in past work. The widely-used Toronto Paper Matching System (TPMS) computes a similarity score for each reviewer-paper pair based on analysis of the reviewers’ past work and bids, and then aims to maximize the total similarity of the resulting assignment. The framework of “compute similarities and maximize total similarity” (and similar variants) encompasses many paper assignment algorithms, where similarities can be computed in various ways from automated and manual analysis and reviewer bids . We treat the bidding process and computation of similarities as given, and focus primarily on adjusting the optimization problem to address the three aforementioned challenges. Some work has considered other optimization objectives such as fairness . We also consider a similar fairness objective in a variant of our algorithm. On a related front, there are also a number of recent works which deal with various other aspects of peer review.

Much prior work has studied the issue of preventing or mitigating strategic behavior in peer review. This work usually focuses on the incentives reviewers have to give poor reviews to other papers in the hopes of increasing their own paper’s chances of acceptance . Unlike the issues we deal with in this paper, these works consider only reviewers’ incentives to get their own paper accepted and not other possible incentives. We instead consider arbitrary incentives for a reviewer to give an untruthful review, such as a personal dislike for a research area or misincentives brought about by author-reviewer collusion. Instead of aiming to remove reviewer incentives to write untruthful reviews, our work focuses on mitigating the effectiveness of manipulating the reviewer assignment process.

A concurrent work considers a different set of problems in releasing data in peer review while preserving reviewer anonymity. The data to be released here are some function of the scores and the reviewer-assignment, whereas we look to release the similarities and the assignment code. Moreover, the approach and techniques in are markedly different—they consider post-processing the data for release using techniques such as differential privacy, whereas we consider randomizing the assignment for plausible deniability.

Outside of peer review, there is a line of prior work focused on detecting and mitigating manipulation in online reviews (such as those on Yelp or Amazon). These works typically make assumptions that are not applicable or require data that is not available in our setting. Several of these works analyze the graph of user reviews in order to detect fraudulent reviewers . For example, detects fraud from the review graph by assuming that products are trying to maximize the number of positive reviews they get, whereas in our setting it is important to mitigate the effectiveness of just a single author-paper collusion since the number of reviews per paper is fixed and small. Additionally, some of these works are based on estimating the “true quality” of each item from the review graph, which is not possible in peer review since paper evaluations are subjective. Another direction of prior work uses machine learning to detect malicious behavior. Some research detects fraud from reviewer statistics such as rating variance or number of ratings, but in the peer review setting, there is so little data for each reviewer that such features would be highly noisy or completely uninformative. Other works attempt to detect malicious reviews from the review text, but in our setting, malicious reviews may not differ stylistically from genuine reviews. Finally, some work in recommender systems focuses on making product recommendations resistant to malicious reviews ; however, in peer review, the paper acceptance process must be done by hand since it must take into account reviewer opinions, arguments, and the reviewer discussion.

Randomized assignments have been used to address the problem of fair division of indivisible goods such as jobs or courses , as well as in the context of Stackelberg security games . The paper uses randomization to address the issue of miscalibration in ratings, such as those given to papers in peer review. To the best of our knowledge, the use of randomized reviewer-paper assignments to address the issues of malicious reviewers or reviewer de-anonymization in peer review has not been studied previously. Work on randomized assignments often references the well-known Birkhoff-von Neumann theorem or a generalization in order to demonstrate how to implement a randomized assignment as a lottery over deterministic assignments. The paper proposes a broad generalization of the Birkhoff-von Neumann theorem that we use in our work.

Background and Problem Statements

Now, suppose there exists a reviewer who wishes to get assigned to a specific paper for some malicious reason and manipulates their similarities in order to do so. When the assignment algorithm is deterministic, as in previous work , a malicious reviewer who knows the algorithm may be able to effectively manipulate it in order to get assigned to the desired paper. To address this issue, we aim to provide a guarantee that regardless of the reviewer bids and similarities, this reviewer-paper pair has only a limited probability of being assigned.

Consider now the challenge of preserving anonymity in releasing conference data. If a conference releases its similarity matrix and its deterministic assignment algorithm, then anyone could reconstruct the full paper assignment. Interestingly, this problem can be solved in the same way as the malicious reviewer problems described above. If the assignment algorithm provides a guarantee that each reviewer-paper pair has only a limited probability of being assigned, then no reviewer’s identity can be discovered with certainty.

With this motivation, we now consider $M$ as stochastic and aim to find a randomized assignment, a probability distribution over deterministic assignments. This naturally leads to the following problem formulation.

To prevent dishonest reviews of papers, program chairs may want to do more than just control the probability of individual paper-reviewer pairs. For example, suppose that we have three reviewers assigned per paper (a very common arrangement in computer science conferences). We might not be particularly concerned about preventing any single reviewer from being assigned to some paper, since even if that reviewer dishonestly reviews the paper, there are likely two other honest reviewers who can overrule the dishonest one. However, it would be much worse if we have two reviewers dishonestly reviewing the same paper, since they could likely overrule the sole honest reviewer.

A second issue is that there may be dependencies within certain pairs of reviewers that cannot be accurately represented by constraints on individual reviewer-paper pairs. For example, we may have two reviewers $a$ and $b$ who are close collaborators, each of which we are not individually very concerned about assigning to paper $p$. However, we may believe that in the case where reviewer $a$ has entered into a quid-pro-quo deal to dishonestly review paper $p$, reviewer $b$ is likely to also be involved in the same deal. Therefore, one may want to strictly limit the probability that both reviewers $a$ and $b$ are assigned to paper $p$, regardless of the limits on the probability that either reviewer individually is assigned to paper $p$.

With this motivation, we define the following generalization of the Pairwise-Constrained Problem.

The randomized assignments that solve these problems can be used to address all three challenges we identified earlier:

Untruthful favorable reviews: By guaranteeing a limit on the probability that any malicious reviewer or any malicious pairs of reviewers can be assigned to the paper they want, we mitigate the effectiveness of any unethical deals between reviewers and authors by capping the probability that such a deal can be upheld. This guarantee holds regardless of how extreme a reviewers’ manipulation of the assignment is and without any assumptions on reviewers’ exact incentives. The entries of $Q$ can be set by the program chairs based on their assessment of the risk of allowing the corresponding reviewer-paper pair; for example, an entry can be set low if the reviewer and author have collaborated in the past. The entries of $T$ can be set similarly based on known associations between reviewers.

Torpedo reviewing: By limiting the probability that any reviewer or pair of reviewers can be assigned to a paper they wish to torpedo, we make it much more difficult for a small group of reviewers to shut down a new research direction or to take out competing papers.

Reviewer de-anonymization in releasing assignment data: To allow for the release of similarities and the assignment algorithm after a conference, all of the entries in $Q$ can simply be set to some reasonable constant value. Even if reviewer and paper names are fully identified through analysis of the similarities, only the distribution over assignments can be recovered and not the specific assignment that was actually used. This guarantees that for each paper, no reviewer’s identity can be identified with high confidence, since every reviewer has only a limited chance to be assigned to that paper.

In Sections 4 and 5, we consider the Pairwise-Constrained Problem and Triplet-Constrained Problem respectively. We also consider several related problems in the appendices.

We address an alternate version of the Pairwise-Constrained Problem in Appendix B which uses the probabilities with which any reviewer may intend to untruthfully review any paper, along with other problems using these probabilities.

Randomized Assignment with Reviewer-Paper Constraints

In this section we present our main algorithm to solve the Pairwise-Constrained Problem (Definition 1), thereby addressing the challenges identified earlier. Before delving into the details of the algorithm, the following theorem states our main result.

There exists an algorithm which returns an optimal solution to the Pairwise-Constrained Problem in $poly(n,d)$ time.

We describe the algorithm, thereby proving this result, in the next two subsections. Our algorithm that realizes this result has two parts. In the first part, we find an optimal “fractional assignment matrix,” which gives the marginal probabilities of individual reviewer-paper assignments. The second part of the algorithm then samples an assignment, respecting the marginal probabilities specified by this fractional assignment.

$\mathcal{LP}1$ has $O(dn)$ variables and $O(dn)$ constraints. Using techniques from , $\mathcal{LP}1$ can be solved in $O((dn)^{2.055})$ time.

2 Implementing the Probabilities

$\mathcal{LP}1$ only finds the optimal marginal assignment probabilities $F$ (where $F$ now refers to a solution to $\mathcal{LP}1$). It remains to show whether and how these marginal probabilities can be implemented as a randomization over deterministic paper assignments. The paper provides a method for sampling a deterministic assignment from a fractional assignment matrix, which completes our algorithm once applied to the optimal solution of $\mathcal{LP}$1. Here we propose a simpler version of the sampling algorithm. Pseudocode for the algorithm is presented as Algorithm 1; we describe the algorithm in detail below. In Appendix C, we present a supplementary algorithm to compute the full distribution over deterministic assignments, which does not. Knowing the full distribution may be useful in order to compute other properties of the randomized assignment not calculable from $F$ directly.

The algorithm then proceeds in an iterative manner, modifying the flow function $f$ on each iteration. On each iteration, we first check if there exists a “fractional edge,” an edge with non-integral flow. If no such edge exists, our current assignment is integral and so we can stop iterating. If there does exist a fractional edge, we then find an arbitrary cycle of fractional edges, ignoring direction (Line 6); this can be done by starting at any fractional edge and walking along fractional edges until a previously-visited vertex is returned to. On finding a cycle, we randomly modify the flow on each of the edges in the cycle in order to guarantee that at least one of the flows becomes integral. In what follows, we first prove that such a cycle of fractional edges can always be found. We then show how to modify the flows in order to guarantee the implementation of the marginal assignment probabilities.

We now show that a directionless cycle of fractional edges must exist whenever one fractional edge exists. Initially, by the properties of $F$, the total flow on each edge going into vertex $t$ is integral; further, the algorithm only ever changes the flow on edges with non-integral flow. Therefore, the total flow going into $t$ is always integral. By flow conservation, the total flow leaving $s$ is also always integral. So, if there is a fractional edge adjacent to $s$, there must also be another fractional edge adjacent to $s$. As already stated, there are no fractional edges adjacent to $t$. Finally, for each vertex $v\in V\setminus\{s,t\}$, by flow conservation, there can never be only one fractional edge adjacent to $v$. Therefore, every vertex that is adjacent to a fractional edge must also be adjacent to another fractional edge. This proves that a directionless cycle of fractional edges must exist if one fractional edge exists.

We now show how to modify the flow on the edges in this cycle. We can keep pushing flow in some direction on this cycle (pushing negative flow if the edge is directed backwards) until some edge is at capacity or has flow. Call this amount of additional flow $\alpha$, and the resulting flow $f_{1}$. We can do the same thing in the other direction on the cycle, calling the additional flow $\beta$ and the resulting flow $f_{2}$. Both $f_{1}$ and $f_{2}$ must have at least one more integral edge than $f$, since some edge is at capacity. Further, both $f_{1}$ and $f_{2}$ obey the flow conservation and capacity constraints. Defining $\gamma\leftarrow\frac{\beta}{\alpha+\beta}$, we set $f\leftarrow f_{1}$ with probability $\gamma$ and $f\leftarrow f_{2}$ with probability $1-\gamma$ (Lines 23-24).

Once all edges are integral (after the final iteration), we construct the sampled deterministic assignment $M$ from the flow on the reviewer-paper edges (Line 26). Since $f$ obeys the capacity constraints on all edges, $M$ obeys the load constraints and so is in fact an assignment. Since on each iteration the initial flow $f$ satisfies $f(e)=\gamma f_{1}(e)+\left(1-\gamma\right)f_{2}(e),\forall e\in E$, the expected final flow on each edge is always equal to the current flow on that edge. Since the expectation of a Bernoulli random variable is exactly the probability it equals one, each final reviewer-paper assignment $M_{rp}$ has been chosen with the desired marginal probabilities $F_{rp}$.

Each iteration of this algorithm takes $O(d+n)$ time to find a cycle in the $O(d+n)$ vertices (if a list of fractional edges adjacent to each vertex is maintained), and it can take $O(dn)$ iterations to terminate since one edge becomes integral every iteration. Therefore, the sampling algorithm is overall $O(dn(d+n))$.

The time complexity of our full algorithm, including both $\mathcal{LP}1$ and the sampling algorithm, is dominated by the complexity of solving the LP. Since standard paper assignment algorithms such as TPMS can be implemented by solving an LP of the same size, our algorithm is comparable in complexity. If a conference currently does solve an LP to find their assignment, whatever LP solver a conference currently uses for their paper assignment algorithm could be used in our algorithm as well.

Randomized Assignment with Constraints on Pairs of Reviewers

We now turn to the problem of controlling the probabilities that certain pairs of reviewers are assigned to the same paper, defined in Section 3 as the Triplet-Constrained Problem (Definition 2). In the following subsections, we first show that the problem of finding an optimal randomized assignment given arbitrary constraints on the maximum probabilities of each reviewer-reviewer-paper grouping is NP-hard. We then show that, for the practical special case of restrictions on reviewers from the same subset of a partition of $\mathcal{R}$ (such as the same primary academic institution or geographical area of residence), an optimal randomized assignment can be found efficiently.

As described in Section 3, solving the Triplet-Constrained Problem would allow the program chairs of a conference maximum flexibility in how they control the probabilities of the assignments of pairs of reviewers. Unfortunately, as the following theorem shows, this problem cannot be efficiently solved.

The Triplet-Constrained Problem is NP-hard, by reduction from 3-Dimensional Matching.

3-Dimensional Matching is an NP-complete decision problem that takes as input three sets $X,Y,Z$ of size $s$ as well as a collection of tuples in $X\times Y\times Z$; the goal is to find a choice of $s$ tuples out of the collection such that no elements of any set are repeated . Our reduction maps sets $X\cup Y$ to $\mathcal{R}$ and $Z$ to $\mathcal{P}$, and constructs $T\in\{0,1\}^{n\times n\times d}$ to allow only the assignments where the corresponding tuples are allowable in the 3-Dimensional Matching instance. The full proof is stated in Appendix D.

Theorem 2 implies a more fundamental result about the feasible region of implementable reviewer-reviewer-paper probability tensors, that is, the tensors $G\in^{n\times n\times d}$ where entry $G_{ijp}$ represents the marginal probability that both reviewers $i$ and $j$ are assigned to paper $p$ under some randomized assignment. We can represent any deterministic assignment by a $3$-dimensional tensor $M\in\{0,1\}^{n\times n\times d}$ where $M_{ijp}=1$ if and only if both reviewers $i$ and $j$ are assigned to paper $p$. Just as in the earlier case of fractional assignment matrices, the set of implementable probability tensors is a polytope with deterministic assignment tensors at the vertices (since any implementable probability tensor is a convex combination of deterministic assignment tensors). For fractional reviewer-paper assignment matrices, this polytope was defined by a small number ($O(dn)$) of linear inequalities, despite the fact that it has a large number of vertices (factorial in $d$ and $n$). However, this is no longer the case for reviewer-reviewer-paper probabilities.

The polytope of implementable reviewer-reviewer-paper probabilities is not expressible in a polynomial (in $n$ and $d$) number of linear inequality constraints (assuming $P\neq NP$).

The proof of this result is also stated in Appendix D.

2 Constraints on Disjoint Reviewer Sets

Since the most general problem of arbitrary constraints on reviewer-reviewer-paper triples is NP-hard, we must restrict ourselves to tractable special cases of interest. One such special case arises when the program chairs of a conference can partition the reviewers in such a way that they wish to prevent any two reviewers within the same subset from being assigned to the same paper. For example, reviewers can be partitioned by their primary academic institution. Since reviewers at the same institution are likely closely associated, program chairs may believe that placing them together as co-reviewers is more risky than would be implied by our concern about either reviewer individually. In this case, there may not even be any concern about the reviewers’ motivations; the concern may simply be that the reviewers’ opinions would not be sufficiently independent. Other partitions of interest could be the reviewer’s geographical area of residence or research sub-field, as each of these defines a “community” of reviewers that may be more closely associated. This special case corresponds to instances of the Triplet-Constrained Problem where $T_{abp}=0$ if reviewers $a$ and $b$ are in the same subset, and $T_{abp}=1$ otherwise.

We formally define this problem as follows:

For this special case of the Triplet-Constrained Problem, we show that the problem is efficiently solvable, as stated in the following theorem.

There exists an algorithm which returns an optimal solution to the Partition-Constrained Problem in poly(n, d) time.

We present the algorithm that realizes this result in the following subsections, thus proving the theorem. The algorithm has two parts: it first finds a fractional assignment matrix $F$ meeting certain requirements, and then samples an assignment while respecting the marginal assignment probabilities given by $F$ and additionally never assigning two reviewers from the same subset to the same paper. For ease of exposition, we first present the sampling algorithm, and then present an LP which finds the optimal fractional assignment matrix meeting the necessary requirements.

The sampling algorithm we present in this section takes as input a fractional assignment matrix $F$ and samples an assignment while respecting the marginal assignment probabilities given by $F$. The sampling algorithm is based on the following lemma:

Consider any fractional assignment matrix $F$ and any partition of $\mathcal{R}$ into subsets $I_{1},\dots,I_{m}$.

There exists a sampling algorithm that implements the marginal assignment probabilities given by $F$ and runs in $O(dn(d+n))$ time such that, for all papers $p\in\mathcal{P}$ and subsets $I\in\{I_{1},\dots,I_{m}\}$ where $\sum_{r\in I}F_{rp}\leq 1$, the algorithm never samples an assignment assigning two reviewers from subset $I$ to paper $p$.

For any sampling algorithm that implements the marginal assignment probabilities given by $F$, for all papers $p\in\mathcal{P}$ and subsets $I\in\{I_{1},\dots,I_{m}\}$ where $\sum_{r\in I}F_{rp}>1$, the expected number of pairs of reviewers from subset $I$ assigned to paper $p$ is strictly positive.

The sampling algorithm which realizes Lemma 1 has an additional helpful property, which holds simultaneously for all papers and subsets. We state the property in the following corollary and make use of it later:

For any fractional assignment matrix $F$, the sampling algorithm that realizes Lemma 1 minimizes the expected number of pairs of reviewers from subset $I$ assigned to paper $p$ simultaneously for all papers $p\in\mathcal{P}$ and subsets $I\in\{I_{1},\dots,I_{m}\}$ among all sampling algorithms implementing the marginal assignment probabilities given by $F$.

We present the sampling algorithm that realizes these results here, and prove the guarantees stated in Lemma 1 and Corollary 2 in Appendix E. This algorithm is a modification of the sampling algorithm from Theorem 1 presented earlier as Algorithm 1.

We first provide some high-level intuition about the modifications to Algorithm 1. For any fractional assignment matrix $F$, for any subset $I$ and paper $p$, the expected number of reviewers from subset $I$ assigned to paper $p$ is $\sum_{r\in I}F_{rp}$. This is equal to the initial load from subset $I$ on paper $p$ in Algorithm 1 (that is, the sum of the flow on all edges from reviewers in subset $I$ to paper $p$). Note that at Algorithm 1’s conclusion, when all edges are integral, the load from subset $I$ on paper $p$ is equal to the number of reviewers from subset $I$ assigned to paper $p$. Therefore, if the fractional assignment $F$ is such that the initial expected number of reviewers from subset $I$ assigned to paper $p$ is no greater than $1$ (as stated in part (i) of Lemma 1), we want to keep the load from subset $I$ on paper $p$ close to its initial value so that the final number of reviewers from subset $I$ assigned to paper $p$ is also no greater than $1$. With this reasoning, we modify Algorithm 1 so that in each iteration, it ensures that the total load on each paper from each subset is unchanged if originally integral and is never moved past the closest integer in either direction if originally fractional.

The algorithm realizing Lemma 1 and Corollary 2 is obtained by changing three lines in Algorithm 1, as follows:

Line 6 is replaced with the subroutine in Algorithm 2.

Line 9 is changed to: $\alpha\leftarrow\min\left(\min_{e\in A}f(e),\min_{e\in B}h(e)-f(e),\min_{t\in D_{1}}t-\lfloor t\rfloor,\min_{t\in D_{2}}\lceil t\rceil-t\right)$.

Line 16 is changed to: $\beta\leftarrow\min\left(\min_{e\in A}h(e)-f(e),\min_{e\in B}f(e),\min_{t\in D_{1}}\lceil t\rceil-t,\min_{t\in D_{2}}t-\lfloor t\rfloor\right)$.

The primary modification we make to Algorithm 1 is replacing Line 6 with the subroutine in Algorithm 2. In each iteration, when we look for an undirected cycle of fractional edges in the graph, we now choose the cycle carefully rather than arbitrarily. We find a cycle by starting from an arbitrary fractional edge in the graph and walk along adjacent fractional edges (ignoring direction) until we repeat a previously-visited vertex. As we do this, whenever we take a fractional edge from a reviewer in subset $I$ into paper $p$, there are two cases.

Case 1: If there exists a different fractional edge from paper $p$ to subset $I$ (Line 8 in Algorithm 2), we take this edge next. Note that if the total load from subset $I$ on paper $p$ is integral, such an edge must exist.

Case 2: Otherwise (Line 12 in Algorithm 2), we must take a fractional edge from paper $p$ to some other subset $J$. In this case, the total load from subset $I$ on paper $p$ must not be integral. We choose the subset $J$ so that the total load from subset $J$ on paper $p$ is also not integral. Such a subset must exist since the total load on paper $p$ is always integral. We keep track of both the total load from $I$ and from $J$ on $p$, for every occurrence of this case along the cycle (Lines 14 and 15 in Algorithm 2).

In Case 1, no matter how much flow is pushed on the cycle, the total load from subset $I$ on paper $p$ will be preserved exactly. However, due to Case 2, we must modify the choice of how much flow to push on the cycle to ensure that the loads are preserved as desired. Specifically, we only push flow in a given direction on the cycle until the total load for either subset $I$ or $J$ on paper $p$ is integral, for any $I,J,p$ found in Case 2. The total loads from each subset on each paper found in Case 2 are saved in either set $D_{1}$ or set $D_{2}$ depending on the direction of the corresponding edges in the cycle, and each subset-paper pair with an edge corresponding to an element of $D_{1}$ or $D_{2}$ has only that one edge in the cycle. If the total (fractional) load from subset $I$ on paper $p$ is $t$, then only $\lceil t\rceil-t$ additional flow can be added to any edge from subset $I$ to paper $p$ before the load becomes integral; similarly, only $t-\lfloor t\rfloor$ flow can be removed from any edge before the load becomes integral. This leads to the stated changes to Lines 9 and 16 in Algorithm 1.

Therefore, on each iteration, we push flow until either the flow on some edge is integral (as in the original algorithm), or until the total load on some paper from some subset is integral. This implies that the algorithm still terminates in a finite number of iterations. In addition, by the end of the algorithm, the total load on each paper from each subset is preserved exactly if originally integral and rounded in either direction if originally fractional, as desired.

The time complexity of this modified algorithm is identical to that of the original algorithm from Theorem 1, since finding a cycle takes the same amount of time (if a fractional adjacency list for each subset is used) and only a maximum of $O(n)$ extra iterations are performed (if an subset’s total load becomes integral rather than an edge’s flow). Therefore, the algorithm is overall $O(dn(d+n))$.

2.2 Finding the Optimal Partition-Constrained Fractional Assignment

Lemma 1 provides necessary and sufficient conditions for the fractional assignment matrices for which it is possible to prevent all pairs of same-subset reviewers from being assigned to the same paper. Therefore, to find an optimal fractional assignment with this property, we just need to add $md$ constraints to $\mathcal{LP}1$. We call this new LP $\mathcal{LP}2$:

The solution to $\mathcal{LP}2$ when paired with the sampling algorithm from Section 5.2.1 never assigns two reviewers from the same subset to the same paper. Furthermore, since any fractional assignment $F$ not obeying Constraint (7) will have a strictly positive probability of assigning two reviewers from the same subset to the same paper, $\mathcal{LP}2$ finds the optimal fractional assignment with this guarantee. This completes the algorithm for the Partition-Constrained Problem.

Additionally, Corollary 2 shows that the sampling algorithm from Section 5.2.1 is optimal in the expected number of same-subset reviewer pairs, for any fractional assignment. If the guarantee of entirely preventing same-subset reviewer pairs is not strictly required, Constraint (7) in $\mathcal{LP}2$ can be loosened (constraining the subset loads to a higher value) without removing it entirely. For the resulting fractional assignment $F$, the sampling algorithm from Section 5.2.1 still minimizes the expected number of pairs of reviewers from any subset on any paper, as compared to any other sampling algorithm implementing $F$. Since the subset loads are still constrained, the expected number of same-subset reviewer pairs will be lower than in the solution to the Pairwise-Constrained Problem (at the cost of some expected sum-similarity). We examine this tradeoff experimentally in Section 6.

Experiments

We run all experiments on a computer with $8$ cores and $16$ GB of RAM, running Ubuntu 18.04 and using Gurobi 9.0.2 to solve the LPs. Our algorithm for the Pairwise-Constrained Problem takes an average of $41$ seconds to complete on ICLR; our algorithm for the Partition-Constrained Problem takes an average of $45$ seconds. As expected, the running time is dominated by the time taken to solve the LP.

We first study our algorithm for the Pairwise-Constrained Problem, as described in Section 4. In this setting, program chairs must make a tradeoff between the quality of the output assignments and guarding against malicious reviewers or reviewer de-anonymization by setting the values of the maximum-probability matrix $Q$. We investigate this tradeoff on real datasets. All results in this section are averaged over $10$ trials with error bars plotted representing the standard error of the mean, although they are sometimes not visible since the variance is very low.

In Figure 1(a), we set all entries of the maximum-probability-matrix $Q$ equal to the same constant value $q_{0}$ (varied on the x-axis), and observe how the sum-similarity value of the assignment computed via our algorithm from Section 4 changes as $q_{0}$ increases from $0.1$ to $1$ with an interval of $0.1$. We report the sum-similarity as a percentage of the unconstrained optimal solution’s objective. This unconstrained optimal solution maximizes sum-similarity through a deterministic assignment as is popularly done today , and does not address the aforementioned challenges. We see that our algorithm trades off the maximum probability of an assignment gracefully against the sum-similarity on all datasets. For instance, with $q_{0}=0.5$, our algorithm achieves $90.8\%$ of the optimal objective value on the ICLR dataset. In practice, this would allow the program chairs of a conference to limit the chance that any malicious reviewer is assigned to their desired paper to $50\%$ without suffering a significant loss of assignment quality. When $q_{0}$ is too small, a feasible assignment may not exist in some datasets (e.g., $q_{0}=0.1$ for PrefLib2).

We next test our algorithm for the Partition-Constrained Problem discussed in Section 5.2. In this algorithm, program chairs can navigate an additional tradeoff between the number of same-subset reviewers assigned to the same paper and the assignment quality; we investigate this tradeoff here. On ICLR, we fix $q_{0}=0.5$ and randomly assign reviewers to subsets of size $15$, using this as our partition of $\mathcal{R}$ (since the dataset does not include any reviewer information). Each subset represents a group of reviewers with close associations, such as reviewers from the same institution. Our algorithm is able to achieve $100\%$ of the optimal objective for the Pairwise-Constrained Problem with $q_{0}=0.5$ while preventing any pairs of reviewers from the same subset from being assigned to the same paper.

Since our algorithm achieves the full possible objective in this setting, we now run experiments with a considerably more restrictive partition constraint. In Figure 1(b), we show an extreme case where we randomly assign reviewers to $3$ subsets of equal size (sizes $811$, $11$, $8$ and $48$ on ICLR and the PrefLib datasets, respectively, with the remainder assigned to a dummy fourth subset), again fixing $q_{0}=0.5$. We then gradually loosen the constraints on the expected number of same-subset reviewers assigned to the same paper by increasing the constant in Constraint (7) from $1$ to $2$ in increments of $0.1$, shown on the x-axis. We plot the sum-similarity objective of the resulting assignment, expressed as a percentage of the optimal non-partition-constrained solution’s objective (i.e., the solution to the Pairwise-Constrained Problem with $q_{0}=0.5$). Even in this extremely constrained case with only a few subsets, we still achieve $99.1\%$ of the non-partition-constrained objective while entirely preventing same-subset reviewer pairs on ICLR.

In Appendix F, we present results for additional experiments on synthetic similarities, where we find results qualitatively similar to those presented here. We also run experiments for a fairness objective, which we present in Appendix A.

2 Effectiveness at Preventing Manipulation

We now describe experiments evaluating the effectiveness of our algorithm at preventing manipulation on the ICLR dataset against a simulated reviewer bidding model. We assume that there is one malicious reviewer who is attempting to maximize their chances of being assigned to a target paper solely through bidding (and not through other means). Since the ICLR similarities are reconstructed purely from the text similarity with each reviewers’ past work and do not contain any bidding, we supplement them with synthetic bids. Specifically, each reviewer $r$ chooses a bid $b_{rp}\in\{-1,0,1\}$ for each paper $p$, indicating “not interested,” “neutral,” or “interested” respectively. Based on the similarity function used in the NeurIPS 2016 conference , we compute the final similarity between reviewer $r$ and paper $p$ as $S^{\prime}_{rp}=\gamma^{b_{rp}}S_{rp}$, where $S_{rp}$ is the text similarity from the ICLR dataset and $\gamma$ is a fixed scale parameter.

In our experiment, the malicious reviewer bids $1$ on their target paper and $-1$ on all other papers. The other (honest) reviewers bid according to a simple randomized model constructed to match characteristics of the bidding observed in NeurIPS 2016 . We divide the reviewers uniformly at random into three groups. The first group contains $20\%$ of the reviewers, who all bid on all papers. The second group contains $50\%$ of the reviewers, who bid non-zero on a low number of papers. These reviewers consider each paper within the $10\%$ of papers that have highest text similarity with them, and independently choose to bid non-zero on each one with probability $0.016$. If a paper is selected to bid non-zero, the bid is chosen from $\{-1,1\}$ with uniform probability. The third group contains $30\%$ of the reviewers, who bid non-zero on a high number of papers. They follow the same bidding procedure as the second group, but bid with probability $0.24$.

The results of this experiment are shown in Figure 2. We choose a target paper uniformly at random, and choose the malicious reviewer to be the reviewer with the $x$th highest text similarity with that paper (varying $x$ on the x-axis). Note that the x-axis is on a log-scale. We then have all reviewers bid in the manner described above, and compute the assignment with either the standard deterministic assignment algorithm described in Section 3 or our randomized assignment algorithm for the Pairwise-Constrained Problem, setting all entries of $Q$ to $0.5$. We then observe the probability that the malicious reviewer is assigned to the target paper (that is, the probability with which the manipulation is successful), which is in $\{0,1\}$ for the deterministic algorithm but can be non-integral for our algorithm. For each point on the x-axis, we average results over $50$ choices of target paper, giving an overall success rate for the manipulation under a uniform choice of papers (reported on the y-axis, with error bars plotted representing the standard error of the mean). For comparison, we also plot the case where only the honest reviewers bid and the malicious reviewer does not bid.

There are three key takeaways from this experiment. First, we see that when a reviewer does not bid, their assignment probability is low for any reviewer not ranked in the top 4 for that paper in terms of the text similarity. Second, when the malicious reviewer does bid, the manipulation has a high success rate under the standard assignment algorithm. For example, the $8$th ranked reviewer for any paper is never assigned if they do not bid, but with bids they can manipulate in order to guarantee their assignment. Moreover, even the $100$th ranked reviewer has a has a decent probability (above $0.25$) of getting assigned the target paper if the reviewer bids maliciously. This indicates that manipulation from reviewers is quite powerful in standard assignment algorithms, potentially compromising the integrity of the assignment. Third, our algorithm always limits the probability of successful manipulation to the desired level of $0.5$, reflecting the theoretical guarantees presented earlier in the paper. For malicious reviewers who have low text similarity with the target paper (e.g., reviewers from a different subject area), our algorithm occasionally gives the manipulation a marginally higher probability to succeed as compared to the standard assignment algorithm since the set of possible reviewers for each paper is larger. However, manipulation from these low-similarity reviewers is unlikely to succeed in the first place (with probability below the desired limit of $0.5$), and it is envisaged to be easier for program chairs to manually spot unusual bids from reviewers outside of a paper’s subject area.

Discussion

We have presented here a framework and a set of algorithms for addressing three challenges of practical importance to the peer review process: untruthful favorable reviews, torpedo reviewing, and reviewer de-anonymization on the release of assignment data. By design, our algorithms are quite flexible to the needs of the program chairs, depending on which challenges they are most concerned with addressing. Our empirical evaluations demonstrate some of the tradeoffs that can be made between total similarity and maximum probability of each paper-reviewer pair or between total similarity and number of reviewers from the same subset on the same paper. The exact parameters of the algorithm can be set based on how the program chairs weigh the relative importance of each of these factors. Note that an empirical evaluation of exactly how much our algorithm reduces manipulation in a real conference is not possible, since the ground truth of which reviewers were manipulating their assignments is not known.

This work leads to a number of open problems of interest. First, since the general Triplet-Constrained Problem is NP-hard, we considered one special structure—the Partition-Constrained Problem—of practical relevance. A direction for future research is to find additional special cases under which optimizing over constraints on the probabilities of reviewer-pair-to-paper assignments is feasible. For example, there may be a known network of reviewers where program chairs wish to prevent connected reviewers from being assigned to the same paper. A second problem of interest is to develop methods to detect potentially malicious reviewer-paper pairs before papers are assigned (e.g., based on the bids). Finally, this work does not address the problem of reviewers colluding with each other to give dishonest favorable reviews after being assigned to each others’ papers; we leave this issue for future work.

Acknowledgments

The research of Steven Jecmen and Nihar Shah was supported in part by NSF CAREER 1942124. The research of Steven Jecmen and Fei Fang was supported in part by NSF Award IIS-1850477. The research of Hanrui Zhang and Vincent Conitzer was supported in part by NSF Award IIS-1814056.

References

Appendix A Stochastic Fairness Objective

An alternate objective to the sum-similarity objective has been studied in past work , aiming to improve the fairness of the assignment with respect to the papers. Rather than maximizing the sum-similarity across all papers, this objective maximizes the minimum total similarity assigned to any paper:

Due to the minimum in the objective, this problem is NP-hard ; the paper presents an algorithm to find an approximate solution.

Fortunately, this problem is solvable efficiently, as the following theorem states.

There exists an algorithm which returns an optimal solution to the Fair Pairwise-Constrained Problem in poly(n, d) time.

We now present our algorithm for solving the Fair Pairwise-Constrained Problem, thereby proving the theorem. It proceeds in a similar manner as the algorithm for the Pairwise-Constrained Problem presented in Section 4.

The algorithm first finds an optimal fractional assignment matrix, since the stochastic fairness objective depends only on the marginal probabilities in the fractional assignment matrix. The optimal fractional assignment is found by the following LP, which we call $\mathcal{LP}3$:

For any $F$, the optimal value of $x$ is always $\min_{p\in\mathcal{P}}\sum_{r\in\mathcal{R}}S_{rp}F_{rp}$, the stochastic fairness of $F$. For a fixed $x$, the feasible region of $F$ in $\mathcal{LP}3$ is exactly the space of fractional assignment matrices with stochastic fairness no less than $x$. Therefore, $\mathcal{LP}3$ will find an optimal fractional assignment matrix for the stochastic fairness objective.

Once an optimal fractional assignment matrix has been found, it only remains to sample a deterministic assignment from it. This is done with the sampling algorithm described in Section 4.2, just as in the Pairwise-Constrained Problem.

We now present some empirical results for this algorithm on the four conference datasets described in Section 6. We set all entries of $Q$ equal to the same constant value $q_{0}$ (varied on the x-axis), and observe how the stochastic fairness objective of the assignment changes as $q_{0}$ increases from $0.1$ to $1$ with an interval of $0.1$. Since the expectation is inside a minimum in the objective, the objective cannot be estimated without bias by averaging together the stochastic fairness of sampled deterministic assignments. Due to this difficulty, we plot the exact objective of our randomized assignment (i.e., the optimal objective value of $\mathcal{LP}3$) rather than averaging over multiple samples, and report the objective as a percentage of the unconstrained optimal solution’s objective (that is, the algorithm’s solution when $q_{0}=1$). As Figure 3 shows, our algorithm finds a randomized assignment achieving $92.7\%$ of the optimal fairness objective on the ICLR dataset when $q_{0}=0.5$.

Appendix B Bad-Assignment Probability Problem Variants

An input to both the Pairwise-Constrained Problem (Definition 1) and the Partition-Constrained Problem (Definition 3) is the matrix $Q$, where $Q_{rp}$ denotes the maximum probability with which reviewer $r$ should be assigned to paper $p$. In practice, program chairs can set the values in this matrix based on their own beliefs about each reviewer-paper pair. However, it may be difficult for program chairs to translate their beliefs about the risk of assigning any reviewer-paper pair into appropriate values for $Q$. In this appendix, we define alternate versions of these problems that allow the program chairs to codify their beliefs in a different way.

Define the assignment of reviewer $r$ to paper $p$ as “bad” if reviewer $r$ intends to untruthfully review paper $p$ (either because they intend to give a dishonest favorable review or because they intend to torpedo-review). Further define a matrix $W\in^{n\times d}$ of bad-assignment probabilities, where $W_{rp}$ represents the probability that the assignment of reviewer $r$ to paper $p$ would be a bad assignment; we assume that the events of each reviewer-paper assignment being bad are all independent of each other. The “true value” of $W$ may not be known, but it can be set based on the program chairs’ beliefs about the reviewers and authors or potentially estimated based on some data from prior conferences. The problem variants we present in the following subsections make use of these bad-assignment probabilities.

We first consider the problem of limiting the probabilities of bad reviewer-paper assignments. We then consider the problem of limiting the probabilities that bad pairs of reviewers are assigned to the same paper.

We define an alternate version of the Pairwise-Constrained Problem using the bad-assignment probabilities:

We now show how to solve the Bad-Assignment Probability Pairwise-Constrained Problem, by translating it to the original Pairwise-Constrained Problem. Suppose that we have access to the matrix $F$ of marginal assignment probabilities that occur under some randomized assignment. The randomized assignment obeys our constraints if and only if $F_{rp}W_{rp}\leq\lambda,\forall r\in\mathcal{R},p\in\mathcal{P}$. This observation leads to the following method of solving the Bad-Assignment Probability Pairwise-Constrained Problem:

Transform the given instance of the Bad-Assignment Probability Pairwise-Constrained Problem into an instance of the Pairwise-Constrained Problem by constructing a matrix of maximum probabilities $Q$ where

Solve the Pairwise-Constrained Problem using the algorithm from Theorem 1, described in Section 4.

B.2 Handling Bad Pairs of Reviewers

Here, we first present an alternative version of the Partition-Constrained Problem and show how to solve it. We then present a different approach to handling the issue of bad reviewer pairs.

In the same way as done above for the Pairwise-Constrained Problem, we define an alternate version of the Partition-Constrained Problem:

Just as for the Bad-Assignment Probability Pairwise-Constrained Problem, we solve this problem by first transforming an instance of this problem into an equivalent instance of the Partition-Constrained Problem, done by constructing a matrix of maximum probabilities $Q$ where $Q_{rp}=\min\left(\lambda/W_{rp},1\right),\forall r\in\mathcal{R},p\in\mathcal{P}$. We then solve this instance using the algorithm in Section 5.2.

B.2.2 Constraints on the Expected Number of Bad Reviewers

The Bad-Assignment Probability Partition-Constrained Problem requires a partition of the reviewer set and prevents pairs of reviewers from being assigned to the same paper if they are in the same subset of this partition. Alternatively, one may want to prevent pairs of reviewers from being assigned to the same paper based on whether $W$ indicates that they are both likely to be bad assignments on this paper, rather than based on some partition of the reviewer set. In this way, we now present an alternative approach to handling the issue of bad reviewer pairs, which does not require a partition of the reviewer set. Rather than explicitly constraining the probabilities of certain same-subset reviewer-reviewer-paper triples as in the Bad-Assignment Partition-Constrained Problem, we limit the expected number of bad reviewers on each paper.

We now present the algorithm that optimally solves this problem. The following LP, $\mathcal{LP}4$, finds a fractional assignment with expected number of bad reviewers on each paper no greater than $\mu$:

Constraints (15-17) define the space of fractional assignment matrices, Constraint (18) ensures that the probability of each bad assignment occurring is limited at $\lambda$, and Constraint (19) ensures that the expected number of bad reviewer-paper assignments for each paper is at most $\mu$. Therefore, $\mathcal{LP}4$ finds the optimal fractional assignment for the Bad-Assignment Probability Expectation-Constrained Problem. This fractional assignment can then be sampled from using the sampling algorithm in Section 4.2.

The above approach to controlling bad reviewer pairs is not directly comparable to the approach taken earlier when solving the Bad-Assignment Probability Partition-Constrained Problem. The Bad-Assignment Probability Expectation-Constrained Problem indirectly restricts pairs of reviewers from being assigned to the same paper based on whether $W$ indicates that they are both likely to be bad assignments on that paper, instead of based on a partition of the reviewer set. This could be advantageous if the sets of likely-bad reviewers for each paper (as given by the probabilities in $W$) are not expressed well by any partition of the reviewer set. However, handling suspicious reviewer pairs through constraining the expected number of bad reviewers per paper is weaker than directly constraining the probabilities of certain reviewer-reviewer-paper triples (as in the Bad-Assignment Probability Partition-Constrained Problem). First, it provides a guarantee only in expectation, and does not guarantee anything about the probabilities of the events we wish to avoid (that is, bad reviewer pairs being assigned to a paper). In addition, we here are assuming that the event of paper $p$ and reviewer $r$ being a bad assignment is independent of this event for all other reviewer-paper pairs; so, this method cannot address the issue of associations between reviewers, such as their presence at the same academic institution.

Appendix C Decomposition Algorithm for the Pairwise-Constrained Problem

In Section 4, we provided the sampling algorithm that realizes Theorem 1, thus solving the Pairwise-Constrained Problem (Definition 1). We here provide a decomposition algorithm to compute a full distribution over deterministic assignments for a given fractional assignment matrix (which the prior work does not). For simplicity, we assume here that all reviewer loads are met with equality (that is, $\sum_{p\in\mathcal{P}}F_{rp}=k$ for all $r\in\mathcal{R}$); the extension to the case when reviewer loads are met with inequality is simple.

We first define certain concepts necessary for the algorithm. We then present a subroutine of the algorithm and prove its correctness. We then present the overall algorithm and prove its correctness. Finally, we analyze the time complexity of the algorithm.

We define here three concepts used in the algorithm and its proof.

The solution $F$ is integral if $F_{rp}\in\{0,1\}$ for all $p\in\mathcal{P}$ and $r\in\mathcal{R}$.

The following procedure, a subroutine of the overall algorithm, takes an instance $(\mathcal{P},\mathcal{R},h)$ and a solution to that instance $F$ as input, and outputs an integral solution $F_{0}$ to $(\mathcal{P},\mathcal{R},h)$ with weight $\alpha_{0}$ and a fractional solution $F^{\prime}$ to $(\mathcal{P},\mathcal{R},h)$ with strictly fewer fractional entries than $F$. Moreover, $F$, $F_{0}$, $\alpha_{0}$, and $F^{\prime}$ satisfy $F=\alpha_{0}F_{0}+(1-\alpha_{0})F^{\prime}$.

Let $E\subseteq\mathcal{R}\times\mathcal{P}$ be $E=\{(r,p)\mid F_{rp}\in(0,1)\}$, and let $M_{0}\subseteq\mathcal{R}\times\mathcal{P}$ be $M_{0}=\{(r,p)\mid F_{rp}=1\}$. With this, define capacity function $h^{\prime}$ as, for any $p\in\mathcal{P}$,

Find a maximum matching $M\subseteq E$ on $E$ subject to capacity constraints $h^{\prime}$.

Set $\alpha_{0}=\min(\{F_{rp}\mid(r,p)\in M\}\cup\{1-F_{rp}\mid(r,p)\in E\setminus(M\cup M_{0})\})$.

We prove the correctness of this subroutine in Lemma 3. Before we do, we restate a result from prior work that we use in the proof, using our own notation.

Now, the following lemma proves the correctness of the subroutine.

The decomposition subroutine finds $F_{0}$, $\alpha_{0}$, and $F^{\prime}$, such that (i) $F_{0}$ is an integral solution to $(\mathcal{P},\mathcal{R},h)$, (ii) $F^{\prime}$ is a fractional solution to $(\mathcal{P},\mathcal{R},h)$, (iii) $F^{\prime}$ has strictly fewer fractional entries than $F$, and (iv) $F=\alpha_{0}F_{0}+(1-\alpha_{0})F^{\prime}$.

We first consider (i). The key step is to show that the maximum matching $M$ found in step 2 is a perfect matching with respect to $h^{\prime}$, or equivalently, to show there is a perfect matching on $E$ with respect to $h^{\prime}$. Consider the capacitated matching instance $(\mathcal{P},\mathcal{R},h^{\prime})$, and the solution $F^{\prime\prime}$ where

$F^{\prime\prime}$ is a solution to $(\mathcal{P},\mathcal{R},h^{\prime})$ by the construction of $h^{\prime}$. By Lemma 2, $F^{\prime\prime}$ is a convex combination of integral solutions to $(\mathcal{P},\mathcal{R},h^{\prime})$. For some $z$, let $\{F_{1},\dots,F_{z}\}$ and $\alpha$ be such a decomposition of $F^{\prime\prime}$, where each $F_{i}$ is an integral solution to $(\mathcal{R},\mathcal{P},h^{\prime})$ and $\alpha_{i}$ is its associated weight. For each $i\in[z]$, let $M_{i}\subseteq\mathcal{R}\times\mathcal{P}$ be the set of $(r,p)$ pairs where $(F_{i})_{rp}=1$. Since $F_{i}$ is a solution to $(\mathcal{R},\mathcal{P},h^{\prime})$, $M_{i}$ is a perfect matching with respect to $h^{\prime}$. By the definition of $F^{\prime\prime}$, $(r,p)\in E$ if and only if $F^{\prime\prime}_{rp}>0$. Now since $F^{\prime\prime}=\sum_{i=1}^{z}\alpha_{i}F_{i}$, $E=\bigcup_{i=1}^{z}M_{i}$. Since each $M_{i}$ is a perfect matching with respect to $h^{\prime}$, $E$ contains a perfect matching with respect to $h^{\prime}$ and so the maximum matching $M$ found is in fact a perfect matching with respect to $h^{\prime}$. Therefore, $M\cup M_{0}$ is a perfect matching with respect to $h$ by the definition of $h^{\prime}$. Therefore, $F_{0}$ is an integral solution to $(\mathcal{P},\mathcal{R},h)$.

For (ii), by the construction of $F^{\prime}$, all capacity constraints hold with equality. We only need to show that $F^{\prime}_{rp}\in$ for any $(r,p)$. Consider any $(r,p)$. There are $3$ cases. If $(r,p)\in M_{0}$, then $F^{\prime}_{rp}=1$. If $(r,p)\not\in M\cup M_{0}$, then the choice of $\alpha_{0}$ ensures that

If $(r,p)\in M$, the choice of $\alpha_{0}$ ensures that

As a result, $F^{\prime}$ is a solution to $(\mathcal{P},\mathcal{R},h)$.

For (iii), the choice of $\alpha_{0}$ ensures that at least one of the inequalities above achieves equality. That is, there exists $(r,p)$ where $F_{rp}\in(0,1)$ such that $F^{\prime}_{rp}\in\{0,1\}$.

Finally, (iv) holds by the construction of $F_{0}$ and $F^{\prime}$. ∎

Using the above subroutine, the overall algorithm proceeds in the following recursive way. It takes as input a capacitated matching instance $(\mathcal{P},\mathcal{R},h)$ and a solution to that instance $F$. It outputs integral solutions $\{F_{1},\dots,F_{z}\}$ to $(\mathcal{P},\mathcal{R},h)$ and $\alpha$ lying on the $z$-dimensional simplex, such that $F=\sum_{i=1}^{z}\alpha_{i}F_{i}$.

If $F$ is integral, return solution $\{F\}$ and weight $1$.

Otherwise, decompose $F$ into $F_{0}$ (with weight $\alpha_{0}$) and $F^{\prime}$ using the above subroutine.

Recursively call this algorithm with $(\mathcal{P},\mathcal{R},h)$ and $F^{\prime}$ as input, decomposing $F^{\prime}$ into solutions $\{F_{1},\dots,F_{z}\}$ with weights $\alpha$.

Define $\beta=(1-\alpha_{0})\alpha$. Return the solutions $\{F_{0},F_{1},\dots,F_{z}\}$ with weights $(\alpha_{0},\beta_{1},\dots,\beta_{z})$.

We now prove the correctness of this algorithm.

The decomposition algorithm correctly outputs integral solutions $\{F_{1},\dots,F_{z}\}$ to $(\mathcal{P},\mathcal{R},h)$ and $\alpha$ lying on the $z$-dimensional simplex, such that $F=\sum_{i=1}^{z}\alpha_{i}F_{i}$.

We prove this statement by induction. If the algorithm returns in step 1, the theorem’s statement holds. Now, assume that the theorem’s statement holds for the decomposition returned by the recursive call to the algorithm in step 3, so that the following all hold: $\{F_{1},\dots,F_{z}\}$ are integral solutions to $(\mathcal{P},\mathcal{R},h)$, $\alpha$ lies on the $z$-dimensional simplex, and $F^{\prime}=\sum_{i=1}^{z}\alpha_{i}F_{i}$. By Lemma 3, $F_{0}$ is an integral solution to $(\mathcal{P},\mathcal{R},h)$, so the $z+1$ solutions returned in step 4 are integral solutions to $(\mathcal{P},\mathcal{R},h)$. Since $\alpha_{0}\in$, $\beta\in^{z}$, and $\alpha_{0}+\sum_{i=1}^{z}\beta_{z}=1$, the weights returned in step 4 lie on the $z+1$ dimensional simplex. Finally, by Lemma 3,

Therefore, the theorem’s statement holds for the output of the algorithm in step 4. By induction, this proves the desired statement. ∎

Since $F^{\prime}$ has at least one fewer fractional entry than $F$, the recursive procedure has depth $O(dn)$ and therefore makes $O(dn)$ calls to the decomposition subroutine. In each call, the bottleneck is finding a maximum matching on $E$ subject to capacities $h$. This can be solved as a max-flow problem on a graph with $O(d+n)$ vertices and $O(dn)$ edges . Using Dinic’s algorithm , the computation of each matching takes $O(dn(d+n)^{2})$ time, giving an overall time complexity of $O(d^{2}n^{2}(d+n)^{2})$.

Appendix D Proofs of Theorem 2 and Corollary 1

An instance of 3-Dimensional Matching consists of three sets $X,Y,Z$ of size $s$, and a collection of tuples in $X\times Y\times Z$. It asks whether there exists a selection of $s$ tuples that includes each element of $X,Y,$ and $Z$ at most once. This problem is known to be NP-complete .

We now show that a 3-Dimensional Matching instance is a yes instance (that is, the answer to it is “yes”) if and only if the corresponding Arbitrary-Constraint Feasibility instance is a yes instance, thus proving that solving Arbitrary-Constraint Feasibility in polynomial time would allow us to solve 3-Dimensional Matching in polynomial time. If there exists a feasible reviewer-paper assignment in the corresponding Arbitrary-Constraint Feasibility instance, then we would answer yes for the original 3-Dimensional Matching instance; otherwise, if there does not exist a feasible reviewer-paper assignment, then we would answer no for the original 3-Dimensional Matching instance.

If the 3-Dimensional Matching instance is a yes (that is, there exists a valid selection of $s$ tuples), then consider the paper assignment that assigns the corresponding reviewers and paper within each triple in the matching. Each paper has exactly $2$ reviewers and each reviewer has exactly $1$ paper, so this is a deterministic assignment. Since it includes only the triples in the matching instance, it obeys the probability constraints of $T$, so the Arbitrary-Constraint Feasibility instance is a yes.

If the 3-Dimensional Matching instance is a no, then all choices of $s$ tuples include some element of $X,Y$, or $Z$ twice. If some element of $Z$ is chosen twice, then there must exist another element of $Z$ that is not included in any tuple. Therefore, any assignment of reviewer pairs to papers must either (a) include some reviewer-pair-to-paper assignment disallowed by $T$ (i.e., an assignment not in the collection of tuples), (b) make less than $s$ assignments of pairs to papers (and thus not assign to some paper), or (c) assign a reviewer twice or not assign some paper. So, no deterministic reviewer-paper assignment can meet the constraints of $T$. Now consider any randomized assignment, and select an arbitrary deterministic assignment in support of the randomized assignment. This deterministic assignment does not meet the constraints of $T$, so it must assign some reviewer $r$ to some paper $p$ that $T$ requires to have probability . Therefore, since this deterministic assignment is in support, the randomized assignment assigns reviewer $r$ to paper $p$ with non-zero probability, thereby violating the constraints of $T$. Therefore, no randomized assignment can meet the constraints of $T$. Therefore, the Arbitrary-Constraint Feasibility instance is a no. This proves that Arbitrary-Constraint Feasibility is NP-hard.

Since even telling if the feasible region of randomized assignments is non-empty is NP-hard, optimizing any objective over this region is also NP-hard. Therefore, the Triplet-Constrained Problem is NP-hard.

Suppose that the polytope of implementable reviewer-reviewer-paper probabilities could be expressed in a polynomial number of linear inequality constraints (with the reviewer-reviewer-paper probabilities as variables). An LP could then be constructed with these inequalities as well as the inequalities given by a tensor $T$ of maximum reviewer-reviewer-paper probabilities. Solving this LP with any linear objective would then find a feasible point, solving Arbitrary-Constraint Feasibility. Since LPs can be solved in time polynomial in the number of variables and constraints, this is a contradiction unless $P\neq NP$.

Appendix E Proof of Lemma 1 and Corollary 2

In Section 5.2.1, we described the sampling algorithm that realizes Lemma 1 and Corollary 2. Here, we present proofs of these results.

We first prove part (i) of the lemma. Consider any subset $I$ and any paper $p$, and recall that in Section 5.2.1 we showed that the algorithm presented there has the property that the total load on each paper from each subset is preserved exactly if originally integral and rounded in either direction if originally fractional. If the total load from subset $I$ on paper $p$ is less than or equal to $1$ originally (i.e., $\sum_{r\in I}F_{rp}\leq 1$), then this algorithm will only ever sample assignments with either or $1$ reviewers, so it never samples a integral assignment that assigns two reviewers from subset $I$ to paper $p$.

Let $f$ be the probability mass function of $X$ under the distribution of $X$ produced by our sampling algorithm, so that $f(i)=P[X=i]$ for $i\in\{0,\dots,|I|\}$. Let $f^{\prime}$ be the probability mass function of $X$ under any different distribution produced by some sampling algorithm, so that $\exists i\in\{0,\dots,|I|\}$ such that $f^{\prime}(i)\neq f(i)$. Since both $f$ and $f^{\prime}$ are produced by sampling algorithms, they must respect the marginal assignment probabilities given by $F$.

Under any other distribution of $X$ giving the probability mass function $f^{\prime}$,

Note that because $f^{\prime}(i)\neq f(i)$ for some $i$, there exists some $j\not\in\{\lceil\mu\rceil,\lfloor\mu\rfloor\}$ such that $f^{\prime}(j)>0$. Further, $(i-{\lceil\mu\rceil})^{2}\geq({\lceil\mu\rceil}-i)$ for all integers $i$ and $(i-{\lceil\mu\rceil})^{2}>({\lceil\mu\rceil}-i)$ for all integers $i\not\in\{\lceil\mu\rceil,\lfloor\mu\rfloor\}$. Therefore,

Appendix F Synthetic Simulations

We now present experimental results on synthetic simulations. All results are averaged over $10$ trials with error bars plotted representing the standard error of the mean, although error bars are sometimes not visible since the variance is low. All experiments were run on a computer with $8$ cores and $16$ GB of RAM, running Ubuntu 18.04 and solving the LPs with Gurobi 9.0.2 .

In Figure 4(a), we examine the performance of our algorithm for the Pairwise-Constrained Problem. For each simulation, we set all entries of $Q$ to a constant $q_{0}$ and observe the sum-similarity as we vary $q_{0}$ (on the x-axis). The objective value is reported here as a percentage of the optimal unconstrained solution’s objective, as was done in Section 6. For the community models, the group size makes a large difference as to what an acceptable value of $q_{0}$ is. For example, with group size $6$ and $q_{0}=0.5$, our algorithm will always assign all good reviewers to all papers; however, for any lower value of $q_{0}$ it can no longer do this and so the objective deteriorates rapidly. Note that since our algorithm is optimal, this deterioration is due to the problem being overconstrained for low values of $q_{0}$ and not due to an issue with the algorithm. For the uniform random simulation, our algorithm performs very well, since there are likely many reviewers with high similarity for each paper.

We also examine the performance of our algorithm for the Partition-Constrained Problem in Figure 4(b). For each simulation, we fix $q_{0}=0.5$ and gradually loosen Constraint (7) in $\mathcal{LP}2$ by increasing the constant from $1$ to $3$ in increments of $0.2$, shown on the x-axis. We plot the sum-similarity objective of the resulting assignment, reported as a percentage of the optimal non-partition-constrained solution’s objective (that is, the solution to the Pairwise-Constrained Problem with $q_{0}=0.5$). For the community model simulations, we assign all reviewers in each group to the same subset of the partition. Since all of the reviewers who can review each paper well are in the same subset, this presents a highly constrained problem (which our algorithm is solving optimally). As expected, our algorithm trades off the number of same-subset reviewer pairs assigned to the same paper and the sum-similarity objective rather poorly (as would any other algorithm). Since $q_{0}=0.5$, there is no difference between the cases with group size $6$ or greater. For the uniform random simulation, we assign random subsets of size $100$. Since there are likely many reviewers with high similarity for each paper in different subsets, our algorithm again performs very well.

In Figure 4(c), we show the runtime of our algorithm for the Pairwise-Constrained Problem on the various simulations, fixing $q_{0}=0.5$ and varying $n=d$ on the x-axis. The runtime of our algorithm is similar across the different simulations. Our algorithm solves the uniform random simulation case with $n=d=5000$ in just over $10$ minutes.