# Algorithmic Game Theory and Applications

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 di erent 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 di ers 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 di erent
payo s to the di erent 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).

# Machine Learning

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 di erent 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.

# C++ Program Design

Raven Elevators Inc. (REI), a manufacturer of elevators, has hired you to build them a simulator for their line of elevator control systems. You happily accept the task, eager to impress your new employer with your development skills. REI asked you to implement it in Qt C++, but before doing the implementation REI requested that you first deliver use cases, design documentation, traceability matrix, and C++ class interfaces.
Learning objectives:
 Verifying consistency between use cases and design
 Building a requirements traceability matrix
 Designing for variability in elevator allocation strategy
Deliverables:
 Use cases (can borrow from A1 & grading feedback)
 Design documentation – structure and behavior:
o UML Class diagram
o Sequence diagrams for these scenarios: 1 Basic use cases and 5 safety features
o Activity or state diagram (where relevant)
o Textual explanation of your design decisions including use of design patterns, if any.  C++ header files (interfaces and significant variables)  Traceability matrix
Your design should include passenger and sensor actors driving the elevator controller responses that are displayed through a simple GUI.
Your design should accommodate for variability in elevator allocation strategy (handle 2 or more allocation strategies).

Elevator system specification (same as Assignment 1)
<Paragraph 1> A building is serviced by M elevators (also called cars). On each of the N floors is a pair of buttons marked “up” and “down. When a button is pressed it illuminates, and remains illuminated, until an elevator arrives to transport the customers who, at this floor, have requested an elevator going in a certain direction. When the elevator arrives, it rings a bell, opens its doors (the elevator and floor doors) for a fixed time (10 seconds) allowing people to exit or board, rings the bell again, closes its doors and proceeds to another floor. Once on-board passengers select one or more destination floors using a panel of buttons; there is one button for every floor. The elevator has a display which shows passengers the current floor of the elevator. There is also a pair of buttons on the elevator control panel marked “open door” and “close door”. These buttons can be used by a passenger to override the default timing of the doors. The door will remain open beyond its default period if the “open door” button is held depressed; the doors can be closed prematurely by pressing the “door close” button. Inside the elevator there is also a help button linked to building safety service.
<Paragraph 2> Each elevator has a sensor that notifies it when it arrives at a floor. The elevator control system should ensure that the group of elevators services all (floor and on-board) requests expeditiously.
<Paragraph 3> Each elevator has a display and an audio system. The display shows the current floor number and warning messages that are synced with audio warnings.
Safety features:
<Paragraph 4> Help: The control system receives a “Help” alarm signal from an elevator indicating that the “Help” button has been pressed. In that case, the passenger is connected to building safety service through a voice connection. If there is no response from building safety within 5 seconds or if there is no response from a passenger a 911 emergency call is placed.
<Paragraph 5> Door obstacles: If the light sensor is interrupted when the door is closing, the control system stops the door from closing and opens it. If this occurs repeatedly over a short period of time, a warning is sounded over the audio system and a text message is displayed.
<Paragraph 6> Fire: The control system receives a “Fire” alarm signal from the building and commands all elevators to move to a safe floor. Similarly, a “Fire” alarm signal from the elevator itself will cause that elevator to go to a safe floor. In both cases an audio and text message are presented to passengers informing them of an emergency and asking them to disembark once the safe floor is reached.
<Paragraph 7> Overload: The control system receives an “Overload” alarm signal from an elevator if the sensors indicate that the passenger or cargo load exceeds the carrying capacity. In that case, the elevator does not move and an audio and a text messages are presented to passengers asking for the load to be reduced before attempting to move again.
<Paragraph 8 > Power out: The control system receives a “Power Out” alarm signal. In that case, an audio and a text messages are presented to passengers informing them of the power outage. Each elevator is then moved to a safe floor and passengers are asked to disembark via audio and text messages. The battery backup power is sufficient to do all of this.