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