Consider a set of agents and a directed graph where an edge means that agent supports or trusts agent . We wish to choose a subset of size of trustworthy agents. Each agent’s first priority is to be included in . We want to find a function from directed graphs of trust, to k-subsets of the vertices. We require two axioms
Axiom 1: If exactly one player is trusted by some other player then this player will be selected to the set of trustworthy players.
Axiom 2: A player cannot prevent not being selected to by misreporting his truthful judgement of his fellow players (even if he knows the way other players are going to vote).
Axiom 2 is referred to as “strategy proofness“.
Impossibility theorem (Alon, Fischer, Procaccia and Tennenholtz): For any , there is no mechanism for choosing the -subset of trustworthy agents that satisfies Axioms 1, 2.
A special case of the theorem, when , can be described in terms of the TV reality game “survivor”. Each of players in the game “survivor” can recommend a subset of his fellow players to be eliminated from the game. Unlike the TV game we allow a player to recommend eliminating more than one other player. One player must be eliminated in the tribal council based on the votes. The theorem asserts that there is no way to design a method to decide which player should be eliminated which satisfies:
Axiom 1: If exactly one player is not recommended to be eliminated by somebody, then this player will not be eliminated.
Axiom 2: A player cannot prevent his own elimination by misreporting his truthful judgement of his fellow players (even if he knows the way other players are going to vote)
Another way to describe this result is that for any reasonable scheme to choose the eliminated player lies are inherent in the game.
Proof: If everybody recommends to eliminate all other players, some player, say player 0 is eliminated. Consider only the scenarios where player 0 recommends to eliminate everybody and every other player recommends either everybody or everybody except player ’0′. By Axiom 1 player 0 is eliminated only in one of these scenarios. (When nobody recommend him.) If any other player is being eliminated in some other scenario, then the same player must be eliminated when player changes his vote. (By Axiom 2) Therefore, every player other than 0 is being eliminated in an even number of these scenarios. This is impossible since the total number of scenarios we consider is even. Walla.
A similar result holds if we insist to eliminate two players in each round. Here is a method from the paper which satisfies Axioms 1 and 2, where we eliminate one or two players.
We put the players in line and look at the first from the left player v who recommends eliminating a player w to his right, and we eliminate player w. If no player recommends a player to his right to be eliminated then the right most player is eliminated. We also look at the first from the right player x who recommends eliminating a player y to his left, and we eliminate player y. If no player recommends a player to his left to be eliminated then the left most player is eliminated. (Note that it may be the case that w=y.)
(Update: the method does not quite work as Kevin remarked; and it is not quite the example from the paper..)
A related post in algorithmic game theory.