|CIT 591 Assignment 3: Saddle
Fall 2003, David Matuszek
Purpose of this assignment:
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 (two-dimensional 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).
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.)
In this assignment you only need one class; call it
This class should have (at least) three instance variables: A two-dimensional
array of integers (call it
game), and two one-dimensional arrays of
integers. These arrays should be declared but not defined (that
is, don't initialize the array variables in the declarations).
main method should do the following:
SaddlePoint, using these two numbers.
run()method (see below) of the newly created
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
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;
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
print() method, which you can call from either
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.
Your program is due before midnight, Thursday October 2. Zip up all files
.class, and any extra files produced by BlueJ,
.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