Evènement pour le groupe Algorithmique Distribuée

Date 2011-04-18  14:00-15:00
TitreChoosing the best among peers  
RésuméA group of n peers (e.g., computer scientists) has to choose the best (most competent) among them. Each member of the group may vote for one other member (self-voting is not allowed), or abstain. While opinions may be subjective, resulting in various voting graphs (directed graphs in which an arc (u,v) means that u votes for v), 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., random) 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 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. This is joint work with Jurek Czyzowicz and Andrzej Pelc. 
Lieus. 178 
OrateurLeszek Gasieniec 
UrlUniversity of Liverpool 

Aucun document lié à cet événement.

Retour à l'index