Consider a set of 
Axiom 1: If exactly one player is trusted by some other player then this player will be selected to the set
Axiom 2: A player cannot prevent not being selected to
Axiom 2 is referred to as “strategy proofness“.
Impossibility theorem (Alon, Fischer, Procaccia and Tennenholtz): For any 
A special case of the theorem, when 
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 
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.
Combinatorics and more 
Isn’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.
Axiom 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.
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?
Dear Kevin, you are right, the example does not work.
The 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.
Right, 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
Noga 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
Pingback: TYI38 Lior Kalai: Monty Hall Meets Survivor | Combinatorics and more