public class TwoPersonZeroSumGame extends Object
TwoPersonZeroSumGame
class represents a data type for
computing optimal row and column strategies to two-person zero-sum games.
This implementation solves an m-by-n two-person zero-sum game by reducing it to a linear programming problem. Assuming the payoff matrix A is strictly positive, the optimal row and column player strategies x* and y* are obtained by solving the following primal and dual pair of linear programs, scaling the results to be probability distributions.
(P) max y^T 1 (D) min 1^T x s.t A^T y ≤ 1 s.t A x ≥ 1 y ≤ 0 x ≥ 0
If the payoff matrix A has any negative entries, we add the same constant to every entry so that every entry is positive. This increases the value of the game by that constant, but does not change solutions to the two-person zero-sum game.
This implementation is not suitable for large inputs, as it calls a bare-bones linear programming solver that is neither fast nor robust with respect to floating-point roundoff error.
For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
TwoPersonZeroSumGame(double[][] payoff)
Determines an optimal solution to the two-sum zero-sum game
with the specified payoff matrix.
|
Modifier and Type | Method and Description |
---|---|
double[] |
column()
Returns the optimal column strategy of this two-person zero-sum game.
|
static void |
main(String[] args)
Unit tests the
ZeroSumGameToLP data type. |
double[] |
row()
Returns the optimal row strategy of this two-person zero-sum game.
|
double |
value()
Returns the optimal value of this two-person zero-sum game.
|
public TwoPersonZeroSumGame(double[][] payoff)
payoff
- the m-by-n payoff matrixpublic double value()
public double[] row()
public double[] column()
public static void main(String[] args)
ZeroSumGameToLP
data type.args
- the command-line arguments