PeerNomination: Relaxing Exactness for Increased Accuracy in Peer Selection

Nicholas Mattei, Paolo Turrini, Stanislav ZhydkovIJCAI 2020 · DOI

TL;DR

This paper introduces PEERNOMINATION, a novel algorithm for impartial peer selection that relaxes the strict requirement of selecting exactly k individuals. By allowing for a probabilistic acceptance of candidates, PEERNOMINATION achieves higher accuracy than existing methods, particularly in scenarios with noisy or incomplete reviews, while maintaining strategyproofness.

What Problem Does This Paper Address?

Peer selection, the process of agents choosing a subset of themselves for an award or prize, is crucial in various domains, from academic peer review to online course grading. The challenge lies in designing mechanisms that are impartial (no agent can manipulate the outcome to their advantage) and accurate (the selected subset truly reflects quality). Existing methods often struggle with either impartiality or accuracy, especially when dealing with self-interested agents and imperfect information (e.g., biased or incomplete reviews). A notable issue in peer review is the inconsistency of judgments, as highlighted by the NIPS experiment where independent committees agreed on less than half of accepted papers. This paper aims to improve the accuracy of peer selection by introducing a novel algorithm that is robust to these imperfections.

Methods

The core of this paper is the PEERNOMINATION algorithm. Unlike many prior methods that require explicit partitioning of agents or complete rankings, PEERNOMINATION operates on an m-regular assignment where each agent reviews and is reviewed by m others. The algorithm selects an agent if they are nominated by a majority of their reviewers. Crucially, it relaxes the "exactness" requirement by introducing a probabilistic acceptance for candidates who fall on the boundary of the nomination quota. This is achieved by a slack parameter ($\epsilon$) that fine-tunes the nomination quota.

Key features of PEERNOMINATION:

  • Impartiality (Strategyproofness): Agents cannot influence their own selection chances by misrepresenting their preferences. This is a direct consequence of agents being considered independently.
  • Relaxed Exactness: The algorithm does not guarantee exactly k selected agents but aims for it in expectation. This flexibility is key to its improved accuracy.
  • No Explicit Partitioning: It avoids the need to divide agents into predefined groups, making it more flexible.
  • Probabilistic Nomination: Candidates are nominated with a certain probability if they fall within a fractional part of the nomination quota.

The paper also provides a theoretical analysis of the expected size and accuracy of the accepting set, and connects peer selection to classification metrics like recall and precision.

Datasets

Not discussed in the paper. The experiments use simulated data generated according to a Mallows model with varying parameters for noise and assignment.

Key Insights and Ideas

  • Relaxing Exactness Boosts Accuracy: The most significant insight is that by moving away from the strict requirement of selecting exactly k individuals, PEERNOMINATION can achieve better accuracy. This is because it allows the algorithm to be more flexible in its selection, especially when dealing with noisy reviews.
  • Impartiality is Achievable with Independence: The strategyproofness of PEERNOMINATION arises naturally from the independent consideration of each agent for selection, simplifying the design compared to mechanisms requiring complex incentive structures.
  • Connection to Classification: Viewing peer selection as a classification problem (selected = positive class) allows for the application of standard metrics like ROC and Precision-Recall curves, providing a richer understanding of the algorithm's performance trade-offs.
  • The Role of Reviewer Information (m): The number of reviewers (m) plays a critical role. Higher m reduces uncertainty and narrows the range of agents with uncertain acceptance probabilities, leading to more predictable outcomes.

Key Results

  • PEERNOMINATION outperforms existing algorithms like Exact Dollar Partition (EDP) and Credible Subset in terms of accuracy across various settings, except in very low-information scenarios (e.g., m=5).
  • The algorithm's performance approaches that of the theoretical optimal (Borda count) as m increases.
  • The slack parameter $\epsilon$ effectively controls the expected size of the accepting set, allowing it to be close to the target k. For instance, $\epsilon = 0.13$ yielded an expected size very close to 30 when n=130 and k=30.
  • The paper demonstrates that PEERNOMINATION is monotonic: better reviews do not decrease an agent's chances of selection.

Limitations and Future Work

  • Noise Sensitivity: While PEERNOMINATION is robust to noise, extremely high levels of noise (approaching random ordering) can affect the size of the accepting set.
  • m-Regular Assignment: The current algorithm assumes an m-regular assignment. Future work could explore relaxing this requirement.
  • Discarded Information: The algorithm primarily uses nomination information and discards the full ranking details provided by reviewers. Future extensions could leverage this richer information.
  • Agent Behavior Models: Further research is needed to test the algorithm's performance under different models of agent behavior and noise.
  • Extending Nominations: The paper suggests extending the mechanism to allow reviewers to declare nominees and a single fractional nominee, rather than a full ranking.

Summary updated

BibTeX
@inproceedings{mattei2020peernomination,
  author = {Nicholas Mattei and Paolo Turrini and Stanislav Zhydkov},
  title = {{PeerNomination: Relaxing Exactness for Increased Accuracy in Peer Selection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/55},
}
Figure