# 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