Computer Science with Applications 1 & 2

Basic Game Theory II: Reducing games

Due: Monday, Oct 18th at 10pm

In Part 1, you computed Nash equilibria for pure strategy games. In this part of the assignment, you will learn the concepts of dominated strategies and apply iterative elimination of dominated strategies.

Our solution is roughly 100 lines of code. We encourage you to work in pairs on this assignment.

Introduction

In certain games, some strategies are clearly superior to others.

Take for example the case of Hungry Bob and the Free Lunch. Bob knows that some RSO is providing free lunch today, and it is going to be either pizza or Chinese food. Bob, being a man of fine taste, prefers Chinese food. But since Bob is a student, he would much rather have free pizza than nothing at all. We can model his situation as a game:

It is clear that Bob is always better off going for the lunch since he always gets a better payoff regardless of whatever the lunch might be. In this case, we say that the 'Don't' strategy is strictly dominated by the 'Go!' strategy.

More formally, we say that Player 1's strategy A is strictly dominated by strategy B when:

For any strategy Player 2 picks, the payoff Player 1 gets is strictly higher if he plays B instead of A.

Note that to determine whether one row is strictly dominated by another row, we only look at the payoffs for Player 1. Similarly, to determine whether one column is strictly dominated by another column, we only consider the payoffs for Player 2 .

One can see that if a strategy is strictly dominated, it can never be part of a pure strategy Nash Equilibrium since the player is always better off picking the strategy that dominates it. As a result, by iteratively removing all strictly dominated strategies, we can end up with a game that is easier to analyze.

Iterative Elimination of Strictly Dominated Strategies

We will now demonstrate two (less trivial) examples of using iterative removal of strictly dominated strategies to simplify games. Our first example is our favorite game, Prisoner's Dilemma:

We begin by considering Player 1's options. If Player 2 were to choose to be 'Silent', Player 1 would be better off by 1 if he chose to 'Betray'. Similarly, if Player 2 were to choose to 'Betray', Player 1 would be better off by 1 choosing to Betray. In this case, we say that the strategy 'Betray' strictly dominates 'Silent'. We can now strike out 'Silent' from Player 1's choices.

We are now left with a simpler 1 by 2 game. The same argument holds for Player 2's strategies, which leaves us with only one choice:

This brings us to an important concept:

Whenever iterative elimination leaves us with only 1 cell (C1,C2), it has to be a pure strategy Nash Equilibrium! To see why, we know that given C2, Player 1 prefers the payoff in C1 compared to any other strategy (hence they were eliminated). Ditto for C1 and Player Two.
At the same time, since each of the eliminated strategies cannot contain a Nash Equilibrium, this strategy is the only Nash Equilibrium in the game.

For the second example, we'll tackle a slightly more tricky 3 by 3 game. Remember that after each step, we only need to consider the cells that have not been eliminated.

Starting here:

'C' is dominated by 'D'

Notice at this point that 'U' does not dominate 'D', nor does 'D' dominate 'U'.

'M' is dominated by 'R'

In our reduced game, 'D' is dominated by 'U', because we only need to compare the 'U' payoff against the 'D' payoffs for 'L' and the 'U' payoff against the 'D' payoff for 'R'.

And finally, R is dominated by L

and we're left with one cell!

The examples we provide here give us particularly nice results with iterative elimination. Some games cannot be simplified to the same extent. The following game can only be reduced to a 2x2 game:

Getting started

We have seeded your PhoenixForge account with a directory named hw2b. To check it out, run svn update from with your cs121 directory. The directory hw2b contains:

ReduceGame.java -- skeleton code for part 2
Pair.java -- simple pair class.
TableUtil.java -- utility functions for reading a table from a file, printing a table, and copying valid parts of a table
data -- a directory containing test files and their matching solutions
README.txt -- describes the contents of the directory

The file ReduceGame.java contains skeleton code for this part of the assignment. We have set up its main function to load a table of pairs, print the original game, call your function that reduces games, and print the resulting reduced game.

Your task (40 points)

Your task is to implement the function:

public static Pair[][] reduceGame(Pair[][] gameData)

which takes in a Pair[][] (representing a game) and returns a Pair[][] representing the game with strictly dominated strategies iteratively eliminated. To help you get started, we will describe one possible organization of the program. There are other equally valid ways to organize the computation.

Your program will make repeated passes over the game data. Each pass will make (1) a sweep over the rows to identify and then remove rows that are strictly dominated by other rows and (2) a sweep over the columns to identify and then remove columns that are strictly dominated by other columns. Because removing a row (column) can reveal new strictly dominated columns (rows), this process will continue until a full pass is made without reducing the number of rows or columns in the game.

We recommend writing the following four auxiliary functions to simplify your task:

/* Given a game and two rows numbers r1 and r2, 
 * returns true: if payoffs for Player 1 in row r1 are strictly dominated by the 
 *   corresponding payoffs for Player 1 in row r2.
 * returns false: otherwise
 *
 * Note: a row never strictly dominates itself.
 */
public static boolean isRowSD(Pair[][] game, int r1, int r2)


/* Given a game and two column numbers c1 and c2, 
 * returns true: if the payoffs for Player 2 in column c1 are strictly dominated by the 
 *   corresponding payoffs for Player 2 in column c2.
 * returns false: otherwise.
 *
 * Note: a column never strictly dominates itself.
 */
public static boolean isColSD(Pair[][] game, boolean int c1, int c2)

/* Given a game, completes one sweep over the rows to identify rows are
 * NOT strictly dominated by other rows and returns a game that includes only
 * those rows.
 */
public static Pair[][] rowSweep(Pair[][] game)

/* Given a game, complete one sweep over the columns to identify columns that are
 * NOT strictly dominated by other columns and returns a game that includes
 * only those columns.
 */
public static Pair[][] colSweep(Pair[][] game)

Note: You do not need to use recursion for any of these functions.

We have added two functions to TableUtil to make your lives easier:

/* copyValidRows: takes a game and a boolean vector that specifies
 * which rows are valid  (row i is valid, if valid[i] is true) and
 * returns a new matrix that contains only the rows from the game that
 * are marked as valid 
 *
 * Note: if all the rows are valid, copyValidRows simply 
 * returns the original game.
 */ 
public static Pair[][] copyValidRows(Pair[][] game, boolean[] valid);

/* copyValidCols: takes a game and a boolean vector that specifies
 * which columns are valid and returns a new matrix that contains only
 * the columns from the game that are marked as valid.
 *
 * Note: if all the columns are valid, copyValidCols simply 
 * returns the original game.
 */ 
public static Pair[][] copyValidCols(Pair[][] game,  boolean[] valid);

To call one of these functions from within ReduceGame.java, prepend its name with TableUtil. as is done in the calls to TableUtil.loadPair and TableUtil.printBoolean in ReduceGame's main function.

Debugging advice

We strongly recommend that you write and test your auxiliary functions before putting them together in reduceGame. You can test a function adding code to main to call it with sample arguments and print the expected and actual results. We will give partial credit for auxiliary functions that are implemented correctly and have been tested (simply comment out your test cases). We will not give partial credit for functions that do not work and show no sign of having been tested.

When debugging my solution, I printed out the state of the table after making a sweep over the rows and again after making a sweep of the columns as a way to get a better idea of what was happening in smaller steps.

Submission

Check your code into PhoenixForge. We strongly recommend that you check your code into PhoenixForge at regular intervals!