Summary
This work is concerned with randomness in paper matching for peer review. It provides normative motivations for the value of randomness in this process and proposes a family of generalizations of the Probability Limited Randomized Assignment (PLRA) paper matching framework of Jecmen et al. This generalization, which the authors term Perturbed Maximization, entails replacing the linear objective in the PLRA linear programming problem with a concave objective which increasingly discounts paper-reviewer matchings with higher probabilities. The authors prove comparisons between the two methods under two distributions of paper-reviewer similarity scores. Experimentally, the authors consider two choices of discounting (perturbation) functions, demonstrate that solving this convex problem is tractable in practice, and present the effect of deploying their method for two past conferences, according to multiple measures of randomness.
Strengths
This work proposes and studies a natural generalization of the PLRA paper matching framework. The generalization and analysis are particularly suited to practical use, in the generalization can be arbitrarily incremental, and the PLRA framework has been used in practice and serves as a benchmark for the experiments.
From a theoretical perspective, it is interesting to identify combinatorial optimization problems/applications for which randomness is a desirable property, and to study how randomness this trades off against optimality.
The experimental results seem to demonstrate that, at least for some paper matching instances, the framework could be used to generate matchings with comparable quality in a much more randomized way.
Weaknesses
Theoretical results: I have a difficult time understanding the settings and claims of the theoretical analysis provided, and I am suspicious of the implications of the analysis to understanding PM as compared to PLRA. The quantity c in Theorem 3 is unspecified, and the claims seem to suggest that the models permit either the same or somehow degenerate solution sets for the two algorithms. In any case, more explanation of these claims seems warranted.
Randomness metrics: the motivation for the proposed randomness metrics for the distribution x in Section 3 is very thin. Some references for these being useful measures for a fractional 'matching' in this application or elsewhere would be welcome. But there seems to be a deeper mismatch between these measures and the reasons randomness is desirable outlined in Section 1. Properly, (and as observed in the discussion of entropy), x is not a distribution; instead the fractional assignment x together with a dependent rounding scheme together induce a distribution over reviewer-paper assignments. The randomness of this distribution seems arguably more relevant to most of the randomness motivations provided in Section 1; for instance, depending on the dependent rounding scheme, a fractional assignment x with Q=0.1 could correspond to sampling one of only 10 final assignments, allowing easy reviewer de-anonymization. I think that calculating (or estimating) these randomness metrics for the assignment distribution would lead to a superior analysis.
Questions
Randomness metrics:
Can you remark on which metrics in Section 3 would be natural choices for any of the randomness motivations in Section 1, and whether you agree that in any cases the corresponding metrics for the induced assignment distribution would be more relevant?
Alternatively, do you think there is good motivation for restricting your randomness metrics to ones that are linear over the fractional assignments of individual papers (as all except L2 are)?
Do the authors of [22] mention or consider any metrics other than Maxprob?
Theoretical results:
What is the scalar c in the statement of Theorem 3? Is it an unspecified constant, or does the statement hold for every c?
If part (a) of Theorems 2 and 3 holds for all pairs of points in the solution set, the claimed Quality inequality seems to suggest that the solution set of PM is contained in the solution set for PLRA. This in turn raises two questions: first, given that the PM objective is different, wouldn't this suggest that these theoretical settings are in a sense too degenerate (have too many equally optimal solutions/too few nearby suboptimal ones) to distinguish between the two methods? Second, do the remaining claimed inequalities suggest that PM identifies a unique point in PLRA(Q) which simultaneously minimizes/maximizes those randomness measures within the set PLRA(Q)?
On line 333, how does Figure 4 show that PM sacrifices Maxprob relative to PLRA?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
The choice of perturbation function seem ad hoc, and it is not obvious why the authors decided to apply the perturbation function to the full range [0,1] instead of to the range [0,Q]. For the perturbation functions studied here this does not matter, but in general it could. There are three places in the narrative where the authors present a range of options: (i) motivations for randomness in paper matching, (ii) measures of randomness, and (ii) choices of perturbation function. It would have been interesting to see some discussion of how choices of (i) might motivate different choices of (ii), particularly with regard to motivations 2 and 4, and some discussion of how different choices of dependent rounding scheme given the fractional assignment affect these objectives. But it would have been particularly nice to see some motivation of how choices of (ii) inform choices of (iii). For instance, are there informal or heuristic arguments that would suggest that one form of perturbation function would be particularly suited to maximizing the entropy objective?
The theoretical analysis is a little unsettling. Either the theoretical similarity models considered seem inapt to the purpose of comparing the two methods, or the theoretical claims could use significantly more contextualization.
Certain aspects of the experimental section could be clearer. In particular, it would be helpful to include a slightly more explicit description of the hyperparameters that are being fit, and the order in which they are being fixed. In my opinion this omission makes the presentation and interpretation of Figure 2 particularly misleading, since the form it takes and the insights offered are directly determined by the value assigned to the hyperparameter delta, which is not mentioned.