Incentive-Compatible Classification

Yakov Babichenko, Oren Dean, Moshe Tennenholtz

AAAI 2020 pp. 7055-7062

doi:10.1609/AAAI.V34I05.6191 /aaai/2020/babichenko2020aaai-incentive/

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

PDF AAAI Semantic Scholar

Cite

Text

Babichenko et al. "Incentive-Compatible Classification." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I05.6191

Markdown

[Babichenko et al. "Incentive-Compatible Classification." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/babichenko2020aaai-incentive/) doi:10.1609/AAAI.V34I05.6191

BibTeX

@inproceedings{babichenko2020aaai-incentive,
  title     = {{Incentive-Compatible Classification}},
  author    = {Babichenko, Yakov and Dean, Oren and Tennenholtz, Moshe},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2020},
  pages     = {7055-7062},
  doi       = {10.1609/AAAI.V34I05.6191},
  url       = {https://mlanthology.org/aaai/2020/babichenko2020aaai-incentive/}
}