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 (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).

For example,

   
min
    0 1 2
max
0
1
2
3
 -7   -11   -7 
-7 -90 -7
-9 -10 -9
-7 -12 -7

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 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).

Your main method should do the following:

  1. Accept two numbers from the command line (or the BlueJ dialog box): the number of rows and the number of columns. Check to make sure the numbers are "reasonable."
  2. Create an instance of SaddlePoint, using these two numbers.
  3. Call the 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).

-7 -11 -7
-7 -90 -7
-9 -10 -9
-7 -12 -7
-11
-90
-10
-12
-7 -10 -7
 

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.