edu.princeton.cs.algs4

## Class TwoPersonZeroSumGame

• Object
• edu.princeton.cs.algs4.TwoPersonZeroSumGame

• ```public class TwoPersonZeroSumGame
extends Object```
The `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.

Author:
Robert Sedgewick, Kevin Wayne
• ### Constructor Summary

Constructors
Constructor and Description
`TwoPersonZeroSumGame(double[][] payoff)`
Determines an optimal solution to the two-sum zero-sum game with the specified payoff matrix.
• ### Method Summary

All Methods
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.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### TwoPersonZeroSumGame

`public TwoPersonZeroSumGame(double[][] payoff)`
Determines an optimal solution to the two-sum zero-sum game with the specified payoff matrix.
Parameters:
`payoff` - the m-by-n payoff matrix
• ### Method Detail

• #### value

`public double value()`
Returns the optimal value of this two-person zero-sum game.
Returns:
the optimal value of this two-person zero-sum game
• #### row

`public double[] row()`
Returns the optimal row strategy of this two-person zero-sum game.
Returns:
the optimal row strategy x of this two-person zero-sum game
• #### column

`public double[] column()`
Returns the optimal column strategy of this two-person zero-sum game.
Returns:
the optimal column strategy y of this two-person zero-sum game
• #### main

`public static void main(String[] args)`
Unit tests the `ZeroSumGameToLP` data type.
Parameters:
`args` - the command-line arguments