FROM COIN TOSSING TO ROCK-PAPER-SCISSORS AND BEYOND: A LOG-EXP GAP THEOREM FOR SELECTING A LEADER

A class of games for finding a leader among a group of candidates is studied in detail. This class covers games based on coin-tossing and rock-paper-scissors as special cases and its complexity exhibits similar stochastic behaviors: either of logarithmic mean and bounded variance or of exponential mean and exponential variance. Many applications are also discussed.