TY - GEN

T1 - Sum of us

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

AU - Alon, Noga

AU - Fischer, Felix

AU - Procaccia, Ariel

AU - Tennenholtz, Moshe

PY - 2011

Y1 - 2011

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

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

KW - approval voting

KW - approximate mechanism design without money

KW - social choice

UR - http://www.scopus.com/inward/record.url?scp=80051573389&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80051573389&partnerID=8YFLogxK

U2 - 10.1145/2000378.2000390

DO - 10.1145/2000378.2000390

M3 - Conference contribution

AN - SCOPUS:80051573389

SN - 9781450307079

T3 - ACM International Conference Proceeding Series

SP - 101

EP - 110

BT - TARK XIII

Y2 - 12 July 2011 through 14 July 2011

ER -