Impossibility Result for “Survivor”

Consider a set of n agents and a directed graph where an edge (i,j) means that agent i supports or trusts agent j. We wish to choose a subset C of size k of trustworthy agents. Each agent’s first priority is to be included in C. We want to find a function from directed graphs of trust, to k-subsets C 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 C of trustworthy players.

Axiom 2: A player cannot prevent not being selected to C 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 k, 1\le k\le n-1 there is no mechanism for choosing the k-subset C of trustworthy agents that satisfies Axioms 1, 2.  

A special case of the theorem, when k=n-1, can be described in terms of the TV reality game “survivor”. Continue reading