Optimal strategies for node selection games on oriented graphs: Skew matrices and symmetric games

Abstract In the node selection game Γ D each of the two players simultaneously selects a node from the oriented graph D . If there is an arc between the selected nodes, then there is a payoff from the “dominated” player to the “dominating” player. We investigate the set of optimal strategies for the players in the node selection game Γ D . We point out that a classical theorem from game theory relates the dimension of the polytope of optimal strategies for Γ D to the nullity of certain skew submatrix of the payoff matrix for Γ D . We show that if D is bipartite (with at least two nodes in each partite set), then an optimal strategy for the node selection game Γ D is never unique. Our work also implies that if D is a tournament, then there is a unique optimal strategy for each player, a result obtained by Fisher and Ryan [Optimal strategies for a generalized “scissors, paper, and stone” game, Amer. Math. Monthly 99 (1992) 935–942] and independently by Laffond, Laslier, and Le Breton [The bipartisan set of a tournament game, Games Econom. Behav. 5 (1993) 182–201].