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”. Continue reading