Some Anomalies of Farsighted Strategic Behavior
We investigate the loss in optimality due to the presence of selfish players in sequential games, a relevant subclass of extensive form games with perfect information recently introduced in Paes Leme et al. (Proceedings of innovations in theoretical computer science (ITCS), ACM, New York, pp. 6067, 2012). In such a setting, the notion of subgame perfect equilibrium is preferred to that of Nash equilibrium since it better captures the farsighted rationality of the players who can anticipate future strategic opportunities. We prove that the sequential price of anarchy, that is the worst-case ratio between the social performance at a subgame perfect equilibrium and that of the best possible solution, is exactly 3 in cut and consensus games. Moreover, we improve the known ?(n) lower bound for unrelated scheduling to \(2^{\varOmega(\sqrt{n})}\) and refine the corresponding upper bound to 2 n , where n is the number of players. Finally, we determine essentially tight bounds for fair cost sharing games by proving that the sequential price of anarchy is between n+1?H n and n. A surprising lower bound of (n+1)/2 is also determined for the singleton case.
sequential price of anarchy cost sharing games subgame perfect equilibria cut games scheduling games