mkse150  Homework 2


Do these exercises from the E&K textbook: 6.11.2, 6.11.5, 8.4.2, 9.8.2, and 9.8.5. Two programming problems follow below. The paper problems should be handed in during class on Feb 21; the program should be submitted via turnin by midnight the same day.

Programming Background

In this assignment you will be working with formal models of games and

Your job is to implement these three algorithms by editing the files, and

Setting up the Project

Download this eclipse project and Import it into Eclipse.
In the Package Explorer, open hw2/src/DefaultPackage.
Highlight and run it. You should get dozens of lines, ending with this:
game now has 5 rows and 6 columns
Eeyore now has these actions:  roll shrug pout grump sit
Tigger now has these actions:  jump bounce run chomp growl spring
finding equilibria
found 0 equilibria
This means that you have succeeded to compile and run the provided code.

Getting Oriented

Open the file in the editor and look it over. It has one loop, which successively opens several data files to create as many different example games. For each one, it calls findEquilibria(), and reduce(). Examine each of the games by viewing the .data files shown in your Project Explorer.

Open the file Inside the class, you will see these three member fields:

	public String gameName;				// a human-readable label for this game.
	public Player castor, pollux; 		// the two players.
The Player called castor will be the one that is described first in the game data file; the second one is called pollux. It might be tempting to call these the row player and the column player, but that is not the way the Player object views the situation.

The Game object is something that gets instantiated and initialized by the Driver. Apart from the constructor, it has these other items:

	public Vector<IndexPair> findEquilibria() {...}
	private boolean findAndRemove(Player player, Player partner) {...}
	public void reduce() {...}
	public class IndexPair {...}

Open the file Inside the class, you will see these four member fields:

		public String name;
		public Vector<String> actions;
		public Vector<Vector<Float>> pay;
		public float[] bests;
The name and the Actions vector are just for human consumption. The bests array is mentioned below.

The pay structure is the central feature of this class; it will hold the normal form representation of all the payoffs for one player. It is a Vector of Vectors, but conceptually it is a matrix where the first index specifies the player's action and the second one specifies the partner's action. Note that this matrix is not represented like ones drawn on the classroom blackboard or in the textbook. A game that has 5 actions of "the row player" and 3 actions for "the column player" would be drawn on the board as a 5 x 3 matrix where every entry is a pair. In our software, however, the same concept would be represented as two Player objects, one of which has a 5 x 3 pay structure, and the other of which has a 3 x 5 pay structure. Both Players view the game as if they were the "row player", and hence the code for one will automatically work for the other as well.

Player objects get instantiated and initialized when Game calls its constructor. There are several other support methods:

		public Player(Scanner sc) 
		public int size() { return actions.size(); }
		public void clearMatrix(int numPartnerActions) 
		public void findBestPayoffs() 
		int findDominatedStrategy() 					TODO: finish this!
		void deleteRow(int index) 
		void deleteCol(int index) 
You will be finishing the findDominatedStrategy method, and will not need to edit or even refer to the other ones, except you might want to use size, which tells you how many actions a player has.

Finding Pure Equilibria

Your first job is to finish writing findEquilibria. It has a data structure inside it
	Vector<IndexPair> equilibs= new Vector<IndexPair>();
which is what will be returned from the method. You will append data to this by using an instruction of this form:
	equilibs.add(new IndexPair(castorIndex,polluxIndex));
Your job is simply to find the pairs of numbers that go in there; they are the indices of the actions that the two players take.

The bests arrays are just provided as a storage device to help with the coding of findEquilibria in case you want to use them. They record the best possible payoff that a player could have in response to each one of his partner's choices. Ignore these arrays until you have worked out an algorithm to find equilibria; depending on the way you solve this, you might see that bests will come in handy. The call to set these things up is already present in the code.

Finding Weakly-Dominated Strategies

Your second job is to finish writing findDominatedStrategy which is to identify any single weakly-dominated strategy. That is you want to find any action i which, in relation to some other action j, never pays better than j and sometimes pays worse than j. (See sections 6.3 and 6.10.B in the textbook.)
For this, the data object you need is one player's payoff matrix, pay, which is actually a Vector of Vectors.
The method is in the Player class. (The code you write here will work for either player, because of the symmetry in the way they are set up.)

Removing All Dominated Strategies

Your last job is to finish writing reduce, which should remove all dominated strategies from the game.
This is just a matter of calling findAndRemove a few times. Note that removing a strategy from one player may cause some strategy of the other player to become dominated. The Hundred Acre Wood game should get reduced way down to this:
Eeyore now has these actions:  grump
Tigger now has these actions:  bounce
finding Equilibria
found 1 equilibria:  (grump,bounce)

Finishing up

Use turnin to turn in both these files: and