CE322 Algorithmic Game Theory
Assignment 2022/23
Answer all (four) questions below.
The filename of each submitted file (report and matlab files) should contain your registration
number. For example, CE322 RegNumber Report.pdf, CE322 RegNumber Task3.m.
Make sure that your code is easy to follow by adequately commenting on your code and/or briefly
describing in the report the steps you take.
Your assignment will be assessed on the quality of the files you submit –correctness, work quality
and quality of presentation– and how clearly you explain what you have done. Aim for precise and
concise answers and explanations.
Explicit marking criteria have been uploaded in a separate document on moodle.
Question 1 [25%]
Four colleagues, A, B,C, and D, want to decide how to commute to work. The company they work for
offers a shuttle service, for a total cost of 12 pounds, that would be evenly split among the people who
chose to use it. For example, if two people use the shuttle service, each of them would pay 6 pounds.
Each person also has the option to drive with their own car to work. The cost for using their own car is
fixed but different for each person: A’s cost for driving is 2; B’s cost for driving is 3, C’s cost for driving
is 5; D’s cost for driving is 11. Your tasks:
a. [6% ] Give a formal definition of the game described above. Who are the players, what are their
strategies and how are their utilities defined for each state (strategy combination).
b. [9% ] Are there any strictly dominated strategies in this game? If so, reduce the game as much as
possible by eliminating them.
c. [5% ] Identify all pure Nash equilibria of the game and their social cost (sum of costs).
d. [5% ] What is the price of stability of the game?
Question 2 [20%]
Consider the following zero sum game G:
A B C D
X 1 1 2 5
Y 0 3 4 4
Z -3 2 2 4
Your tasks:
a. [4% ] Reduce the game as much as possible by removing any possible strictly dominated strategies.
b. [4% ] Is there a pure Nash equilibrium in the remaining game? Justify your answer.
c. [12% ] Compute a mixed Nash equilibrium using the indifference conditions of the players. Present both
the equilibrium and the analysis clearly. No coding is required.
1
Question 3 [25%]
Consider the following general normal form game G. Your task is to find the correlated equilibrium
that maximizes the sum of players’ utilities, using Linear Programming in MATLAB. In your report,
you need to present the equilibrium that you have computed, the linear program that you are solving
(which should include the equilibrium conditions that are satisfied), and a screenshot of your MATLAB
input AND output. Use the following ordering of variables when constructing your MATLAB input:
pXA, pXB , pXC , pY A, pY B , pY C , pZA, pZB , pZC .
A B C
X 0,7 2,5 7,0
Y 5,2 0,0 5,2
Z 7,0 2,5 0,7
Question 4 [30%]
Consider the following sponsored search auction instance I:
2 slots. The top slot has a known click-through rate (CTR) ctr1 = 1 and the bottom slot has a
known click-through rate ctr3 = 0.5.
2 advertisers. Advertiser 1 has a private value-per-click v1 = 1 and advertiser 2 has a private
value-per-click v2 = 0.5.
The utility of the advertiser (let’s call them i, i = 1, 2) is:
– (vi p), if i is assigned to the top slot, where p is the price charged per-click in the top slot.
– 0.5 · vi, if i is assigned to the bottom slot (price 0 is charged per-click in the bottom slot).
Under the Generalized Second-Price (GSP) auction rule:
- Advertisers are asked to place bids in the auction (players are supposed to declare their value per
click, but the bids aren’t always truthful!). Advertisers are then ranked according to their bids
and the advertiser with the highest bid is assigned to the slot with the highest CTR (top slot),
the other advertiser is assigned to the slot with the lowest CTR (bottom slot). In case of a tie,
advertiser 1 is allocated to the top slot. The per-click payment p at the top slot is set to be equal
to the bid of the advertiser assigned to the bottom slot.
a. [4% ] Compute the optimal/highest social welfare (sum of individual values) in I.
b. [6% ] Let b1 and b2 denote the bids placed by advertiser 1 and 2, respectively, and assume b1 > b2.
Formulate the conditions that need to be satisfied at equilibrium. The conditions should contain
only variables v1, v2, b1 and b2.
c. [8% ] Write a function in MATLAB that takes as input the bids of the two players and outputs their
utilities.
d. [12% ] Assume the following strategy sets (the allowed strategies each player can make) S1 = {0, 0.5, 1}
and S2 = {0, 0.5}. Write MATLAB code that computes all Nash equilibria in I, and outputs the
equilibrium strategies and the associated social welfare. Your code can call the function of part c.
You can (or not) follow a brute-force approach, i.e. consider all possible combinations of bids and
for each of them check if it is an equilibrium. Copy and paste your MATLAB code in your report,
and explicitly mention where in your MATLAB code you guarantee that the equilibrium conditions are
satisfied. If your code successfully computes one or more equilibria, present them in the report alongside
their social welfare.