Zero-sum Bimatrix Game (ZSBG)

Input

Two $m \times n$ matrices $A$ and $B$ that have integer entries, and a designated natural number $k$, $1 \leq k \leq m$.

Problem

Is row $k$ of matrix $A$ deleted in the reduced game? In a bimatrix game the reduced game is unique up to row and column permutations (Knuth, Papadimitriou, and Tsitsiklis [1]); thus, the elimination order will not affect the answer to this question.

Definitions

The game involves two players. Simultaneously, player one chooses a row $i$ and player two chooses a column $j$. The result of these choices is that player one (two) receives $a_{ij}$ (respectively, $b_{ij}$) points. A strategy $i$ of player one dominates a strategy $i’$ of player one if $a_{ij} \geq a_{i’j}$ for $j = 1, \ldots, n$. A strategy $j$ of player two dominates a strategy $j’$ of player two if $b_{ij} \geq b_{ij’}$ for $i = 1, \ldots, m$. It is easy to see that all dominated strategies can be removed from both one and two’s matrix without affecting the outcome of the game. A reduced game is one in which all dominated strategies have been eliminated. The game is zero-sum if $A + B = \mathcal{O}$, where $\mathcal{O}$ denotes the $m \times n$ matrix with all $0$ entries.

Status

$\P$-complete (Knuth, Papadimitriou, and Tsitsiklis [1]).

Remarks

In [1] they give a polynomial time algorithm for the general problem, that is, the game is not required to be a zero-sum game. The reduction proving completeness is from a variant of MCVP.