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 share of the pie. Otherwise, they get nothing. We call such two-person games, “simple coordination games”. We show, that for each simple coordination game, there is an “integer linear programming problem”, such that the set of solutions of the integer linear programming problem agrees with the set of pure-strategy equilibria of the game. If one examines the objective function of the integer linear programming problem, then one will find implicit in it both “altruism” as well as “antagonism”. The integer linear programs are far from obvious and surreptitiously incorporate in them “multiplicative” or “interdependent” non-linear features, that would not be possible unless we required some of the variables to be either ‘0’ or ‘1’.