Incentive-Compatible Classification

Yakov Babichenko, Oren Dean, Moshe Tennenholtz

Abstract

In peer-review systems like eBay or academic conferences, agents often have a selfish incentive to give others poor reviews to boost their own relative standing. This paper explores the mathematical limits of "Incentive-Compatible" (IC) classification—systems where no agent can improve their own status by lying about others—and proves that while perfect classification is impossible, we can still achieve meaningful results if the number of reviews per person is limited.

The Strategic Reviewer Problem

The authors tackle the "strategic reviewer" problem in social and economic networks. Imagine a group of sellers on a platform where only the top 10% get a "Top Rated" badge. If a seller is allowed to rate their competitors, they have a dominant strategy to give everyone else a one-star review, regardless of actual quality, just to increase their own chances of being in that top 10%.

This behavior breaks the integrity of the classification system. The challenge is to design a mechanism that is Incentive-Compatible (IC): a rule where an agent’s own classification is entirely independent of the reviews they provide. The paper asks: How closely can an IC mechanism's output resemble the "ideal" classification (the one we would get if everyone were honest)?

Methodology

The researchers model the problem using a directed, weighted network where nodes are agents and edges represent reviews (weighted from -1 to 1). They define the $\alpha$-classification problem, where the goal is to identify the top $\alpha$ fraction of "worthy" agents based on their average incoming scores.

Key methodological contributions include:

  • Defining Coincidence: They introduce a metric to measure the "quality" of a mechanism by comparing its selected set to the ideal set of worthy agents.
  • The Partitioning Approach: For scenarios where agents give a limited number of reviews ($\Delta$), they propose a mechanism that partitions agents into three groups: "absolutely worthy," "absolutely unworthy," and "borderline." By ignoring an agent's own reviews when determining their category, they maintain IC status.
  • Probabilistic Extensions: To prove upper bounds (impossibility results), the authors extend their model to include probabilistic mechanisms, where agents are assigned a probability of being worthy.

Key Insights and Results

The "Price" of Honesty

The paper proves there is a fundamental gap between what is achievable and what is ideal. For any $\alpha < 1$, there is no "perfect" IC classification mechanism. You must sacrifice some accuracy to ensure the system cannot be gamed. The quality of any IC mechanism is capped at $\frac{1}{2}(1 + \alpha)$.

The Impact of Influence ($\Delta$)

The most critical parameter is $\Delta$, the maximum number of reviews a single agent can issue. If $\Delta$ is large (meaning one person can tank the scores of many others), the system becomes impossible to manage effectively. In the worst case (unbounded $\Delta$), the best IC mechanism is "trivial"---it either picks everyone or ignores the reviews entirely.

Visualizing the feasible quality range (a) and the impact of large influence (b).

Selectivity and Classification

The smaller the fraction $\alpha$ (i.e., the more "prestigious" or selective the classification), the harder it is to design a good IC mechanism. As the system becomes more "picky," the quality of the best possible mechanism decays toward zero. Unlike previous work that focused on selecting exactly $k$ agents, this paper focuses on classifying agents. This is a harder problem because the mechanism doesn't know the exact size of the "worthy" set in advance and must try to avoid "false positives" (unworthy agents) just as much as "false negatives."

Limitations and Future Work

While this theoretical work establishes critical bounds, it currently focuses on binary classification. Real-world systems often require more granular rankings or continuous scores. Future work could explore highly asymmetric or data-driven priors, or alternative quality measures that weight misclassification errors differently (e.g., misclassifying a "worthy" agent as "unworthy" might be worse than the reverse).

Summary updated

Abstract

We investigate the possibility of an incentive-compatible (IC, a.k.a. strategy-proof) mechanism for the classification of agents in a network according to their reviews of each other. In the α-classification problem we are interested in selecting the top α fraction of users. We give upper bounds (impossibilities) and lower bounds (mechanisms) on the worst-case coincidence between the classification of an IC mechanism and the ideal α-classification.We prove bounds which depend on α and on the maximal number of reviews given by a single agent, Δ. Our results show that it is harder to find a good mechanism when α is smaller and Δ is larger. In particular, if Δ is unbounded, then the best mechanism is trivial (that is, it does not take into account the reviews). On the other hand, when Δ is sublinear in the number of agents, we give a simple, natural mechanism, with a coincidence ratio of α.
BibTeX
@inproceedings{babichenko2020incentive,
  author = {Yakov Babichenko and Oren Dean and Moshe Tennenholtz},
  title = {{Incentive-Compatible Classification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i05.6191},
}
Figure