CIT 591 Assignment 3: Saddle
Points Fall 2003, David Matuszek 
Purpose of this assignment:
Background:
There is a branch of mathematics called Game Theory, which is concerned with analyzing "games." These aren't ordinary games like chess, but a mathematical idealization that uses matrices (twodimensional arrays). Game theory has a surprisingly large number of applications in war, business, and other competitive situations.
Here's the typical situation. There are two players, max and min. Max has to choose among a set of alternatives (rows), and min has to simultaneously choose among a different set of alternatives (columns). The value located at this particular row and column is the amount that min loses to max. Thus, max prefers larger numbers and min prefers smaller numbers (hence their names).
For example,
min  
0  1  2  
max 


In this example, if max chooses row 3 and min chooses row 1, the payoff from min to max is 12; that is, max loses 12 and min gains 12. Game theory is all about determining how players should make their choices.
A saddle point in a numerical array is a number that is larger than or equal to every number in its column, and smaller than or equal to every number in its row.One simple result is that if the game has a saddle point, then players should always choose the row/column containing that saddle point. (It is possible for a game to have more than one saddle point, but in this case they will all be numerically equal.)
Your assignment:
In this assignment you only need one class; call it SaddlePoint
.
This class should have (at least) three instance variables: A twodimensional
array of integers (call it game
), and two onedimensional arrays of
integers. These arrays should be declared but not defined (that
is, don't initialize the array variables in the declarations).
Your main
method should do the following:
SaddlePoint
, using these two numbers.
run()
method (see below) of the newly created
SaddlePoint
object. The SaddlePoint
class should have a constructor (named
SaddlePoint
, of course) that takes two parameters, the number of
rows and the number of columns, and defines the game
array.
It should also fill in this array with random integers in the range 10 to +10.
(Our example uses a larger range.)
import java.util.*; // Must be at the top of the file, before the class
...
Random random = new Random();
int randomNumber = random.nextInt(21)  10;
The run()
method should do the rest of the work. You can (and
should) define additional methods for run
to use. In particular,
you should print the game
array, and for this you should have a
separate print()
method, which you can call from either
main
or run
.
Here's how you find a saddle point (if one exists):
Find the minimum in each row, and find the maximum in each column, and put these in separate arrays. Hint: you will need two loops for each array, one to loop over the rows [columns], and an inside loop to find the minimum [maximum] value in each row [column]. Print out these two arrays, each on a single line (don't try to do anything fancy with the output).

 

Finally, find and print the minimum value of the column maxima
(10
), and the maximum value of the row minima (also
10
). If these are equal, print that you have a saddle point, and
print the row and column number in which it occurs. If these two numbers are
unequal, print a message saying that there is no saddle point.
Due date:
Your program is due before midnight, Thursday October 2. Zip up all files
(.java
, .class
, and any extra files produced by BlueJ,
such as .pkg
and .pkh
files), and submit via Blackboard. Please turn in one
program for your pair, that is, you and your partner should not both turn in a
copy.