Incentive-Compatible Classification

Authors

  • Yakov Babichenko Technion - Israel Institute of Technology
  • Oren Dean Technion - Israel Institute of Technology
  • Moshe Tennenholtz Technion - Israel Institute of Technology

DOI:

https://doi.org/10.1609/aaai.v34i05.6191

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 α.

Downloads

Published

2020-04-03

How to Cite

Babichenko, Y., Dean, O., & Tennenholtz, M. (2020). Incentive-Compatible Classification. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05), 7055-7062. https://doi.org/10.1609/aaai.v34i05.6191

Issue

Section

AAAI Technical Track: Multiagent Systems