Each question counts for 50 points, for a total of 100 points for AN-
SWERING *** TWO *** QUESTIONS ONLY. (DO NOT SUBMIT AN-
SWERS FOR MORE THAN TWO QUESTIONS. ONLY TWO WILL BE
MARKED.)
1. (a) (25 points) Consider 2-player strategic form game, G, specied
by the following \bimatrix”:
2664
(7; 4) (9; 5) (2; 3) (2; 6)
(4; 1) (9; 2) (2; 1) (3; 6)
(8; 7) (6; 7) (5; 8) (2; 7)
(3; 3) (7; 4) (4; 6) (2; 4)
3775
As usual, player 1 is the row player, and player 2 is the column
player. If the content of the bimatrix at row i and column j is
the pair (a; b), then u1(i; j) = a and u2(i; j) = b.
Compute all of the Nash equilibria (NEs) of this game G, together
with the expected payo to each player in each NE. Explain why
any prole x that you claim is an NE of G, is indeed an NE of G,
and furthermore, explain why there are no other (pure or mixed)
NEs of G, other than the prole(s) you claim are NE(s) of G.
(b) (25 points) Consider a nite game, G, with pure strategy sets
S1; : : : ; Sn for the n players, and with a payo function ui(s)
for each player i 2 f1; : : : ; ng that assigns a payo to each pure
strategy prole s = (s1; : : : ; sn) 2 S = S1  S2  : : :  Sn.
Now consider a dierent n-player game, G0, which has exactly the
same strategy sets S1; : : : ; Sn, as G, but where the payo function

u0i(s) for each player i diers from ui(s) as follows:
u0i(s) = ui(s) + gi(s􀀀i)
where, for each player i, gi : S􀀀i ! R is a function (any function)
that depends only on the other players’ pure strategies and not
on player i’s own pure strategy.
Prove that G and G0 have exactly the same set of Nash equi-
libria. In other words, prove that a mixed strategy prole x =
(x1; : : : ; xn) is a NE for G if and only if x is a NE for G0.
(Note, however, that the same NE may yield entirely dierent
payos to the dierent players in G and in G0.)

2. (a) (20 points) Consider the 2-player zero-sum game given by the
following payo matrix for player 1 (the row player):
266664
5 6 4 7 3
6 4 5 3 8
7 2 5 4 6
4 7 3 5 7
3 5 8 6 3
377775
Compute both the minimax value for this game, as well as a min-
imax prole (NE), i.e. a pair of minmaximizer and maxminimizer
strategies for players 1 and 2, respectively.
(You can, for example, use the linear programming solver package
linprog in MATLAB, available on DICE machines, to do this.
To run MATLAB, type \matlab” at the shell command prompt.
For guidance on using the linprog package, see:
http://uk.mathworks.com/help/optim/ug/linprog.html.)
(b) (30 points) Recall from Lecture 7 on LP duality, the symmetric 2-
player zero-sum game, G, for which the (skew-symmetric) payo
matrix (in block form) for player 1 is:
B =24
0 A 􀀀b
􀀀AT 0 c
bT 􀀀cT 0
35
Suppose that there exist vectors x0 2 Rn and y0 2 Rm, such
that Ax0 < b, x0  0, AT y0 > c and y0  0. (Note the two
strict inequalities.) Prove that for the game G, every minmaxi-
mizer strategy w = (y; x; z) for player 1 (and hence also every
maxminimizer strategy for player 2, since the game is symmetric)
has the property that z > 0, i.e., the last pure strategy is played
with positive probability. (Recall that this was one of the missing
steps in our sketch proof in the lecture that the minimax theorem
implies the LP duality theorem.)
(Hint: Let w = (y; x; z) be a maxminimizer strategy for player
2 in the game G. Note that the value of any symmetric 2-player
zero-sum game must be equal to zero. This implies, by the min-
imax theorem, that Bw  0. Suppose, for contradiction, that
z = 0. What does this imply about Ax , AT y, and bT y􀀀cT x?
Then if y 6= 0, show that this implies (y)T (Ax0 􀀀 b) < 0. In
turn, show that it also implies (x)T (AT y0 􀀀 c) > 0. Use these
and related facts to conclude a contradiction.)

3. Consider the following simple 2-player zero-sum games, where the pay-
o table for Player 1 (the row player) is given by:
A =  1 􀀀1
􀀀1 1 
We can view this as a game where each player chooses \heads” (H) or
\tails” (T), where the rst strategy for each player is denoted H and
the second strategy is denoted T.
(a) (10 points) First, what is the unique Nash equilibrium, or equiva-
lently the unique minimax prole of mixed strategies for the two
players, in this game? And what is the minimax value of that
game?
(b) (40 points) Now, suppose that the two players play the same game
you have chosen in part (a), against each other, over and over
again, for ever, and suppose that both of them use the following
method in order to update their own strategy after each round of
the game.
i. At the beginning, in the rst round, each player chooses ei-
ther of the pure strategies, H or T, arbitrarily, and plays
that.
ii. After each round, each player i accumulates statistics on how
its opponent has played until now, meaning how many Heads
and how many Tails have been played by the opponent, over
all rounds of the game played thusfar. Suppose these num-
bers are N Heads and M Tails.
Then player i uses these statistics to \guess” its opponents
\statistical mixed strategy” as follows. It assumes that its op-
ponent will next play a mixed strategy , which plays Heads
with probability N=(N+M) and plays Tails with probability
M=(N +M).
Under the assumption that its opponent is playing the \sta-
tistical mixed strategy” , in the next round player i plays a
pure strategy (H or T) that is a pure best response to .
If both H and T are a best response at any round, then
player i can use any tie breaking rule it wish in order to
determine the pure strategy it plays in the next round.
iii. They repeat playing like this forever.

Prove that, regardless how the two players start playing the game
in the rst round, the \statistical mixed strategies” of both play-
ers in this method of repeatedly playing the game will, in the long
run, as the number of rounds goes to innity, converge to their
mixed strategies in the unique Nash equilibrium of the game.
You are allowed to show that this holds using any specic tie
breaking rule that you want. Please specify the precise tie break-
ing rule you have used. (It turns out that it holds true for any
tie breaking rule. But some tie breaking rules make the proof a
lot easier than others.)

4. (a) (40 points) One variant of the Farkas Lemma says the following:
Farkas Lemma A linear system of inequalities Ax  b has a
solution x if and only if there is no vector y satisfying y  0 and
yTA = 0 (i.e., 0 in every coordinate) and such that yT b < 0.
Prove this Farkas Lemma with the aid of Fourier-Motzkin elim-
ination. (Hint: One direction of the \if and only if” is easy.
For the other direction, use induction on the number of columns
of A, using the fact that Fourier-Motzkin elimination \works”.
Note basically that each round of Fourier-Motzkin elimination
can \eliminate one variable” by pre-multiplying a given system
of linear inequalities by a non-negative matrix.)
(b) (10 points) Recall that in the Strong Duality Theorem one possi-
ble case (case 4, in the theorem as stated on our lecture slides)
is that both the primal LP and its dual LP are infeasible. Give
an example of a primal LP and its dual LP, for which both are
infeasible (and argue why they are both infeasible).

You may use any programming l anguage you l ike (Python, C++, C, Java… ) . All programming must be
done individually f rom rst principles. You are only permitted to use existing t ools f or simple l inear algebra
such as matrix multiplication/inversion. Do NOT use any toolkit that performs machine learning
functions and do NOT collaborate with your classmates. Cite any resources that were used.
In t his project you will practice the basics of Machine Learning Classication by creating a K-NN clas-sier
for two datasets. You will also practice good practices f or how to describe, evaluate, and write up a report on
the classier performance.
It i s expected that your project report may require 2 pages per dataset i f you are good about making
interesting gures and making them not too l arge, or 3 pages i f your gures are big.
Datasets: The project will explore two datasets, the famous MNIST dataset of very small pictures of
handwritten numbers, and a dataset that explores the prevelance of diabetes in a native american tribe
named the Pima. You can access the datasets here:
1. https://www.kaggle.com/uciml/pima-indians-diabetes-database
2. https://www.kaggle.com/c/digit-recognizer/data
Programming Task: For each dataset, you must create a K-NN classier that uses the training data to
build a classier, and evaluate and report on the classier performance.
(30 points) Dataset details: Describe the data and some simple visualizations (for images, a few exam-
ples from each category; for other data, perhaps some scatter plots or histograms that show a big picture of
the data). Describe your training/test split for K-NN and justify your choices.
(15 points) Algorithm Description: K-NN is a very clear algorithm, so here describe any data pre-
processing, feature scaling, distance metrics, or otherwise that you did.
(45 points) Algorithm Results: Show the accuracy of your algorithm|in the case of the Pima Dataset,
show accuracy with tables showing false positive, false negative, true positive and true negatives. For the
Pima Dataset, use three dierent distance metrics and compare the results.
In the case of the MNIST digits show the complete confusion matrix. Choose a single digit to measure
accuracy and show how that number varies as a function of K.
(10 points) Runtime: Describe the run-time of your algorithm and also share the actual “wall-clock”
time that it took to compute your results.