CE322 游戏算法理论

CE322 Algorithmic Game Theory
Reassessment 2022/23
Lecturer: Maria Kyropoulou
Answer all (four) questions below.
You need to submit
– one report with your answers to all questions. This should be a .pdf file named according to
‘CE322 RegNumber Report.pdf’, where RegNumber should be replaced by your registration
number. Always conclude the answer of each task with a clearly highlighted part that contains
the final answer (after presenting the analysis). For example, if the task asks you to find Nash
equilibria, you should always conclude with something like “I have identified the following
equilibrium: Player A has chosen strategy ..., Player B has chosen strategy ..., etc.”
– all MATLAB (.m) files that you created in the context of this assignment, named according
to ‘CE322 RegNumber TaskX.m’, where RegNumber should be replaced by your registration
number and X should be replaced by the Task number.
You can include clear pictures of clearly handwritten equations/analysis etc. (emphasis on the
‘clear’ and ‘clearly handwritten’ ! If we can’t immediately tell what’s written there, no marks will
be awarded). However, all explanations in words should be electronically written as should be
the conclusion of your answer (see above). Also, 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.
Question 1 [20%]
Consider the following normal form game G:
A B
X 4, -4 7, -7
Y 8, -8 6, -6
a. [6% ] Is there a pure Nash equilibrium in G? Justify your answer.
b. [14% ] Compute a mixed equilibrium using the indifference conditions of the players. Present both the
equilibrium and the analysis clearly. No coding is required.
Question 2 [25%]
Ten commuters must decide simultaneously in the morning to use route A or route B to go from home
(same place for all) to work (ditto). If a of them use route A, each of them will travel for 10a + 40
minutes; if b of them use route B, each of them will travel for 10b minutes. Everyone wishes to minimize
his/her commuting time. Your tasks:
1
a. [12% ] Describe the pure Nash equilibrium (or Nash equilibria) of this ten-person game. Compute
the corresponding profile of commuting times. Explicitly list all equilibrium conditions that are
satisfied.
b. [6% ] What is the traffic pattern (strategies) minimizing the total travel time of all commuters (the
sum of their travel times)? Describe the corresponding profile of commuting times (individual
payoffs/cost).
c. [7% ] What does this mean about the Price of Anarchy of this game (assuming that the objective
function is the total travel time)?
No coding is required.
Question 3 [25%]
Consider the following normal form game G. Your task is to find the correlated equilibrium that max-
imizes 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 in-
put 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 6,6 0,8 0,0
Y 8,0 2,2 0,0
Z 0,0 0,0 1,1
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 = 2 and advertiser 2 has a private
value-per-click v2 = 1.
The payoff of advertiser i, (i is either 1 or 2), who is assigned to the top slot is (vi ? pi), where pi
is the price charged per-click to i. The payoff of advertiser j (j is either 1 or 2 but different than
i) who is assigned at the bottom slot is 0.5 · (vj ? pj) where pj is the price charged per-click to j.
pi and pj are defined by the auction rule, as follows.
Consider the following auction rule (first-price auction):
- Advertisers are asked to declare their value per click (this doesn’t mean that their declarations are
truthful!). Advertisers are then ranked according to their declarations and the advertiser with the
highest declaration is assigned to the slot with the highest CTR (top slot), the advertiser with the
second highest declaration 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 of any advertiser is equal to
their own bid.
a. [6% ] Compute the optimal/highest social welfare (sum of individual values) in I.
b. [9% ] Let b1 and b2 denote the bids placed by advertiser 1 and 2, respectively, and assume b2 > b1.
Formulate the conditions that need to be satisfied at equilibrium. The conditions should contain
only variables v1, v2, b1 and b2.
c. [15% ] Write a function that takes as input the bid of advertiser 1 and calculates the best response, i.e.
the strategy/bid of advertiser 2 that results in the highest possible utility for advertiser 2.
You can (or not) follow a brute-force approach, i.e. consider all possible declarations/bids for adver-
tiser 2, calculate the associated utility and keep the bid that maximizes that utility. Copy and paste
your MATLAB code in your report.