TY - JOUR
T1 - Choosing the best among peers
AU - Czyzowicz, Jurek
AU - Gasieniec, Leszek
AU - Pelc, Andrzej
N1 - Funding Information:
The first author was partially supported by NSERC discovery grant. The second author’s work was done during his visit at the Université du Québec en Outaouais. The third author was partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.
PY - 2012/7/6
Y1 - 2012/7/6
N2 - A group of n peers, e.g., computer scientists, has to choose the best, i.e., the most competent among them. Each member of the group may vote for one other member, or abstain. Self-voting is not allowed. A voting graph is a directed graph in which an arc (u,v) means that u votes for v. While opinions may be subjective, resulting in various voting graphs, it is natural to assume that more competent peers are also, in general, more competent in evaluating competence of others. We capture this by proposing a voting system in which each member is assigned a positive integer value satisfying the following strict support monotonicity property: the value of x is larger than the value of y if and only if the sum of values of members voting for x is larger than the sum of values of members voting for y. Then we choose the member with the highest value, or if there are several such members, another election mechanism, e.g., using randomness, chooses one of them. We show that for every voting graph there is a value function satisfying the strict support monotonicity property and that such a function can be computed in linear time. However, it turns out that this method of choosing the best among peers is vulnerable to vote manipulation: even one voter of very low value may change his/her vote so as to get the highest value. This is due to the possibility of loops (directed cycles) in the voting graph. Hence we slightly modify voting graphs by erasing all arcs that belong to some cycle. This modification results in a pruned voting graph which is always a rooted forest. We show that for all pruned voting graphs there are value functions giving a guarantee against manipulation. More precisely, we show a value function guaranteeing that no coalition of k members all of whose values are lower than those of (1-1(k+1))n other members can manipulate their votes so that one of them gets the largest value. In particular, no single member from the lower half of the group is able to manipulate his/her vote to become elected. We also show that no better guarantee can be given for any value function satisfying the strict support monotonicity property.
AB - A group of n peers, e.g., computer scientists, has to choose the best, i.e., the most competent among them. Each member of the group may vote for one other member, or abstain. Self-voting is not allowed. A voting graph is a directed graph in which an arc (u,v) means that u votes for v. While opinions may be subjective, resulting in various voting graphs, it is natural to assume that more competent peers are also, in general, more competent in evaluating competence of others. We capture this by proposing a voting system in which each member is assigned a positive integer value satisfying the following strict support monotonicity property: the value of x is larger than the value of y if and only if the sum of values of members voting for x is larger than the sum of values of members voting for y. Then we choose the member with the highest value, or if there are several such members, another election mechanism, e.g., using randomness, chooses one of them. We show that for every voting graph there is a value function satisfying the strict support monotonicity property and that such a function can be computed in linear time. However, it turns out that this method of choosing the best among peers is vulnerable to vote manipulation: even one voter of very low value may change his/her vote so as to get the highest value. This is due to the possibility of loops (directed cycles) in the voting graph. Hence we slightly modify voting graphs by erasing all arcs that belong to some cycle. This modification results in a pruned voting graph which is always a rooted forest. We show that for all pruned voting graphs there are value functions giving a guarantee against manipulation. More precisely, we show a value function guaranteeing that no coalition of k members all of whose values are lower than those of (1-1(k+1))n other members can manipulate their votes so that one of them gets the largest value. In particular, no single member from the lower half of the group is able to manipulate his/her vote to become elected. We also show that no better guarantee can be given for any value function satisfying the strict support monotonicity property.
KW - Directed graph
KW - Ranking
KW - Value function
KW - Vote manipulation
KW - Voting system
KW - Weighted voting
UR - http://www.scopus.com/inward/record.url?scp=84861529426&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84861529426&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2012.04.005
DO - 10.1016/j.tcs.2012.04.005
M3 - Article
AN - SCOPUS:84861529426
SN - 0304-3975
VL - 440-441
SP - 52
EP - 59
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -