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.

Ori Gurel-GurevichIsn’t Axiom 1 already impossible if you want to have k strictly small then n?

If the trust relation is a 1-1 function, you have to choose the entire subset.

Ariel ProcacciaAxiom 1 states that there exists *exactly* one player that is trusted by someone. If the trust relation is a 1-1 function then all the players are trusted (in particular more than one player assuming n>1), and then the axiom does not impose any constraints.

Kevin C.Am I missing something about the last example?

Say that every player but the rightmost player chooses to recommend nobody for elimination, and the rightmost player recommends everybody but himself. Then since nobody has recommended anyone to his right, the rightmost player is one of the eliminated players. But he’s the only one who wasn’t recommended by someone for elimination. Why doesn’t this violate axiom 1?

Gil KalaiPost authorDear Kevin, you are right, the example does not work.

Ariel ProcacciaThe example given in the paper (Appendix B) is a method for selecting one or two players that satisfies the more general Axioms 1 and 2 formulated by Gil: look at the leftmost player x that has an edge (x,y) directed to the right (i.e., x trusts y), and select player y (or the rightmost player if there is no such edge), then do the same from right to left. This gives an amusing contrast to the k=1,2 cases of the theorem as Gil presented it. Under the “projection” to “Survivor” the method would be directly mapped to a method that eliminates either n-1 or n-2 players, so I guess the example is not necessarily meaningful in this context.

GilRight, I suppose that it is not clear if an example satisfying the axioms where one or two players are eliminated (or perhaps a larger range of numbers of players) can be found or not. Also if we stick to survivor’s rule and insist that every player will propose one other player to eliminate we can wonder which rules satisfy the axioms. (“Dictatorship” does work in this case.)

Pingback: Math World | Impossibility Result for “Survivor” « Combinatorics and more

Gil KalaiPost authorNoga told me that for the original survivor rules there are a few variations on the dictatorship examples that also work: For example the rule can be this: if player 1 decide to eliminate player 2 or 4 then we follow his reccomendation, if player 1 recommend to eliminate player 3 then player’s 4 reccomendation is taken unless it is player 1 in which case player 3 is eliminated.

It may be the case that there is no strategy-prood method where every player can be eliminated. This translates into a natural nice covering problem.

Pingback: Carnival of Mathematics #56 « Reasonable Deviations

Pingback: Survivor problem « Theory Sublime