Sum of us: Strategyproof selection from the selectors

Noga Alon, Felix Fischer, Ariel Procaccia, Moshe Tennenholtz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

38 Scopus citations

Abstract

We consider the special case of approval voting when the set of agents and the set of alternatives coincide. This captures situations in which the members of an organization want to elect a president or a committee from their ranks, as well as a variety of problems in networked environments, for example in internet search, social networks like Twitter, or reputation systems like Epinions. More precisely, we look at a setting where each member of a set of n agents approves or disapproves of any other member of the set and we want to select a subset of k agents, for a given value of k, in a strategyproof and approximately efficient way. Here, strategyproofness means that no agent can improve its own chances of being selected by changing the set of other agents it approves. A mechanism is said to provide an approximation ratio of α for some α ≥ 1 if the ratio between the sum of approval scores of any set of size k and that of the set selected by the mechanism is always at most α. We show that for k ∈ {1, 2,..., n - 1}, no deterministic strategyproof mechanism can provide a finite approximation ratio. We then present a randomized strategyproof mechanism that provides an approximation ratio that is bounded from above by four for any value of k, and approaches one as k grows.

Original languageEnglish (US)
Title of host publicationTARK XIII
Subtitle of host publicationTheoretical Aspects of Rationality and Knowledge - Proceedings of the 13th Conference, TARK 2011
Pages101-110
Number of pages10
DOIs
StatePublished - Aug 16 2011
Externally publishedYes
Event13th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2011 - Groningen, Netherlands
Duration: Jul 12 2011Jul 14 2011

Publication series

NameACM International Conference Proceeding Series

Other

Other13th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2011
CountryNetherlands
CityGroningen
Period7/12/117/14/11

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Keywords

  • approval voting
  • approximate mechanism design without money
  • social choice

Fingerprint Dive into the research topics of 'Sum of us: Strategyproof selection from the selectors'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Fischer, F., Procaccia, A., & Tennenholtz, M. (2011). Sum of us: Strategyproof selection from the selectors. In TARK XIII: Theoretical Aspects of Rationality and Knowledge - Proceedings of the 13th Conference, TARK 2011 (pp. 101-110). (ACM International Conference Proceeding Series). https://doi.org/10.1145/2000378.2000390