### 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 language | English (US) |
---|---|

Title of host publication | TARK XIII |

Subtitle of host publication | Theoretical Aspects of Rationality and Knowledge - Proceedings of the 13th Conference, TARK 2011 |

Pages | 101-110 |

Number of pages | 10 |

DOIs | |

State | Published - Aug 16 2011 |

Externally published | Yes |

Event | 13th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2011 - Groningen, Netherlands Duration: Jul 12 2011 → Jul 14 2011 |

### Publication series

Name | ACM International Conference Proceeding Series |
---|

### Other

Other | 13th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2011 |
---|---|

Country | Netherlands |

City | Groningen |

Period | 7/12/11 → 7/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

*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