Additively-Separable Sum Linear Programming Games

Abstract

We introduce the class of additively-separable linear-programming games. Such games are two-person/two-player games, where one player’s “strategy set” is a “closed convex polytope” and the other player’s “set of pure strategies” is a non-empty finite set. The objective of the first player is to maximize a real-valued linear payoff function on the closed convex polytope, where the payoff consists partly on a transfer from the second player and depends on the strategies chosen by both players and the rest is independent of the strategy chosen by the second player while being linearly dependent on the strategy chosen by the first player. We allow the second player to choose randomized or mixed strategies and the objective of the second player is to maximize expected pay-off. The expected payoff of the second player is a linear function of the mixed strategy chosen by the second player which is not influenced by the strategy chosen by the first player minus what the second player transfers to the first player. Our main result says that under the assumption that the closed convex polytope is non-empty and bounded, the set of all equilibria of an additively-separable linear programming game is “equivalent” to the solution set of two different “primal-dual pairs” of linear programming problems. Further, the optimal value of the second primal-dual pair of linear programming problems defines the value of the additively-separable linear programming game.