Formulate the solution of a zero sum game with a payoff matrix A as an optimization problem.

106 Views Asked by At

let $x\in$ ${\Bbb R}^n$ be the strategy of the first player and let $y\in$ ${\Bbb R}^n$ be the strategy of the second player. That is, $x_i$ represents the probability of the first player taking the action i.The first player aims to maximize the payoff, while the second player aims to minimize the payoff. The payoff matrix is $A\in$ ${\Bbb R}^{nxn}$.
The solution to a zero-sum game can be formulated as the following non-smooth optimization problem. Let f(x) be the payoff for a strategy of the first player, defined as:
$f(x)=min_yx^TAy$ $\space$ s.t. $\space 1^Ty=1,y>= 0$
The first player needs to optimize for the best strategy as:
$max_xf(x)\space\space s.t.\space\space 1^Tx=1,x>=0$
Reformulate this optimization problem to a smooth (linear) constrained optimization problem. That mean there should be only one maximization or minimization. Also all the constraints and the objective should be linear.