Due: Monday, May 13th at 6pm.

You must work alone on this assignment.

Introduction

Game theory, as its name suggests, is a tool for analyzing games. Here the word 'game' takes on a more general meaning than one would normally expect. A game here is simply a collection of:

• A finite number of players
• A set of strategies that each player can take
• A payoff function for each player based on the strategy that the player takes

This general framework fits our conventional notion of games, such as competitive sports, chess and gambling. We can also model many of the following real-world events as games:

• Auctions
• Competition between firms (strategies - how each firm positions itself; payoff - profits)
• Any form of election is a game amongst potential candidates. The way each candidate markets himself or herself is a strategy (i.e. appealing to working class voters, young voters, or special interests) and the payoff is the result of the election.

As a result, game theory has found applications in numerous fields such as economics, computer science, and evolutionary biology.

Basic Terminology

Given the players, strategies, and payoffs, one can represent the game in normal (or strategic) form, which tells us the associated payoff for every possible combination of strategies. We call each combination of strategies played by the players a strategy profile and we use a matrix to represent the payoff associated with each strategy profile. For example, this matrix:

should be interpreted to mean:

• given the profile (A, A), both Players 1 and 2 gain 2 each.
• given the profile (A, B), Player 1 gains nothing, Player 2 gains 1.
• given the profile (B, A), Player 1 gains 1, Player 2 gains nothing.
• given the profile (B, B), both Players 1 and 2 gain 1 each.

We can classify games as pure, in which players make their choices deterministically, or as mixed, in which players are allowed to randomize their strategies.

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

Please note: you do not need to understand Nash Equilibria to do this assignment.

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 a classic game known as 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:

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 strategy profiles that have not been eliminated.

Starting here:

Choice C is dominated by Choice D.

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

Choice M is dominated by Choice R.

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

And finally, Choice R is dominated by Choice L.

and we're left with one strategy profile!

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, for example, can only be reduced to a 2x2 game:

Getting started

To work on your VM, you will need to do the following (once):

sudo apt-get install clang

If you get a "command not found" error every time you try to use clang, close and reopen your terminal window to ensure this command has taken effect.

If you will be working on a CSIL machine, the clang compiler is already installed. On a personal Mac being used without a VM, typing clang will offer to install it if it is not already present.

Please register for pa2 using chisubmit and do a git pull upstream master in your repository to get the distribution files

The pa2 directory contains:

• reduce_game.c: a file with skeleton code,
• test_reduce.c: a file with test code for the function reduce,
• game.c, game.h: the files for the data structure for representing games,
• double_table.c, double_table.h: the files for utility functions for working with tables of doubles,
• util.c, util.h: the files for a set of utility functions,
• data: a directory containing test games,
• Makefile: a file that describes how to build and run the application, and
• README.txt: a file that describes the contents of the directory

The file reduce_game.c contains skeleton code for the assignment. It is the only file you will modify. The file test_reduce.c contains test code for the reduce function. The file game.c contains a data structure for representing games. The remaining .c and .h files are libraries that are used by game.c. You need not read or understand all the code in these files to complete this assignment.

make is a utility that allows you to describe and run a set of commands. The file Makefile describes the commands that are to be run. We will describe how to use make to compile and test your code later when we discuss testing.

Please add your name to the top of reduce_game.c before you start this assignment.

Representing games

We have provided a data structure representing games. The header file game.h contains the structure definition struct game_s and the definition for game_t, a type for pointers to games. It also contains prototypes for the following functions:

• game_t mk_game(char *filename): load a game from the specified file,
• void free_game(game_t g): free the game,
• void print_game(game_t g): print the contents of the game to the screen,
• void remove_row_game(game_t g, int row_num): remove the specified row from the game , and
• void remove_col_game(game_t g, int col_num): remove the specified column from the game.

When a row (column) is removed from the game, the remaining rows (columns) are shifted forward by 1 to fill the gap. For example, if we remove row 2 from a game, the original row 3 becomes the new row 2, etc.

Your task

Your task is to implement the function:

void reduce(game_t g)

in reduce_game.c, which should take a game_t and reduce it using iterative elimination.

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

As always, writing auxiliary functions and testing them as you go will make the task of completing this assignment much easier. It is OK if you end up with auxiliary functions that are very similar except that one works on rows and the other works on columns.

Note: you will lose style points if your code has loops that are more than doubly-nested within a single function. To be clear: you will likely need more than this amount of nesting -- all you need to do is have appropriate helper functions so that all the loops are not within the same function.

Test cases

We have provided code to test your implementation of reduce in the file test_reduce.c. As usual, our test cases vary the types of input and the expected output to exercise different parts of your code. You can compile test_reduce.c using the command:

make test_reduce

You can run the subsequent executable in one of two ways: you can run all the tests or a specific test (0 through 6). For example, the first line below runs all of the tests and the second runs only test 3:

./test_reduce data

./test_reduce data 3

You can also run the command make run_test_reduce to run all the test cases.

The directory data contains a collection of test games. Each game is represented by a directory that contains a subdirectory original that contains files with the original payoffs for player 1 and player 2 and a subdirectory reduced that contains files with the payoffs for player 1 and player 2 in the reduced game. There are seven test cases. The first game can be reduced by one row.

The second game can be reduced by multiple rows during one pass over the game.

The third game can be reduced by one column.

The fourth game can be reduced by multiple columns in one pass over the game.

The fifth game cannot be reduced further.

The sixth game can be reduced by one row and one column during one pass over the game.

And finally, the seventh game, which contains the second example seen above, requires multiple passes over the game to produce the reduced game.