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 a class of “mixed integer linear programming problems”, such that the set of pure-strategy equilibria of the game is a “projection” of subset of the set of solutions of any mixed integer linear programming problem in the class and another very closely related class of mixed integer linear programming problem whose solutions for each problem in the class yield the set of pure-strategy equilibria of the simple coordination game. These two types of mixed integer linear programming problems depend only on the location of the positive pay-offs, and not on their magnitude. The mixed integer linear programs are far from obvious and the second one-in particular- 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’.