Equivalence Theorem for Simple Coordination Games

Abstract

In this note, we consider simple coordination games, with each player having the same number of pure strategies to choose from. We model the problem as a “pie-division” problem. Let ‘n’ denote the number of strategies available to each of the two players. One player called the “row player” chooses one of the rows of a square matrix of size ‘n’. The other player called the “column player” chooses of the columns of a square matrix of size ‘n’. There is a permutation (one-to-one function from a non-empty finite domain to itself) on the set of first ‘n’ positive integers, such that if the row player chooses a row and the column player chooses the column assigned by the permutation to itself, then each get a positive pay-off. Otherwise, they get nothing. We call such two-person games, “simple coordination games”. We show, that for each simple coordination game, there are two “linear programming problems”, such that the set of pure-strategy equilibria of the game is in “one-to-one correspondence” with the set of solutions of each of the two linear programming problems. We provide a second characterization of pure-strategy equilibrium in terms of solutions to ‘n’ pairs of linear programming problems. We subsequently address the problem of coordination between the two players and show that a way to solve this problem is the “leader-follower” method. where one of the players is pre-committed to its best pure strategy and the other chooses its best response to the pre-committed strategy. Such a solution arises by solving one of two quadratic programming problems. 

AMS Classifications: 90C05, 90C20, 91A05, 91A10, 91A35, 91B06

JEL Classifications: C61, C72, D81