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 pure-strategy equilibria of the game is a subset of the set of solutions of the integer linear programming problem and another very closely related integer programming problem whose solutions yield the set of pure strategy equilibria of the simple coordination game. These two integer linear programming problems depend only on the location of the positive pay-offs, and not on their magnitude. If one examines the objective function of the two integer linear programming problems, then one will find implicit in them both “altruism” as well as “antagonism”. The integer linear programs are far from obvious and the second one-in particular- surreptitiously incorporates in it “multiplicative” or “interdependent” non-linear features, that would not be possible unless we required some additional variables to be either ‘0’ or ‘1’.