Class TwoPersonZeroSumGame
 Object

 edu.princeton.cs.algs4.TwoPersonZeroSumGame

public class TwoPersonZeroSumGame extends Object
TheTwoPersonZeroSumGame
class represents a data type for computing optimal row and column strategies to twoperson zerosum games.This implementation solves an mbyn twoperson zerosum 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 twoperson zerosum game.
This implementation is not suitable for large inputs, as it calls a barebones linear programming solver that is neither fast nor robust with respect to floatingpoint 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 Description TwoPersonZeroSumGame(double[][] payoff)
Determines an optimal solution to the twosum zerosum game with the specified payoff matrix.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description double[]
column()
Returns the optimal column strategy of this twoperson zerosum game.static void
main(String[] args)
Unit tests theZeroSumGameToLP
data type.double[]
row()
Returns the optimal row strategy of this twoperson zerosum game.double
value()
Returns the optimal value of this twoperson zerosum game.



Method Detail

value
public double value()
Returns the optimal value of this twoperson zerosum game. Returns:
 the optimal value of this twoperson zerosum game

row
public double[] row()
Returns the optimal row strategy of this twoperson zerosum game. Returns:
 the optimal row strategy x of this twoperson zerosum game

column
public double[] column()
Returns the optimal column strategy of this twoperson zerosum game. Returns:
 the optimal column strategy y of this twoperson zerosum game

main
public static void main(String[] args)
Unit tests theZeroSumGameToLP
data type. Parameters:
args
 the commandline arguments

