首页 >
> 详细

CE322 Algorithmic Game Theory

Assignment 2021/22

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 zero sum game G:

A B C D

X 2 0 1 4

Y 1 2 5 3

Z 4 1 3 2

Your tasks:

a. [4% ] Reduce the game as much as possible by removing any possible dominated strategies.

b. [4% ] Is there a pure Nash equilibrium in the remaining game? Justify your answer.

c. [12% ] Compute a mixed equilibrium using the indifference conditions of the players. Present both the

equilibrium and the analysis clearly. No coding is required.

1

Question 2 [25%]

Consider the following 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 10,5 0,6 0,0

Y 7,7 0,0 6,0

Z 0,0 7,7 5,10

Question 3 [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:

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)?

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 payoff of the advertiser (let’s call them i, i = 1, 2) who is assigned to the top slot is (vi − p),

where p is the price charged per-click in the top slot. The payoff of i in the bottom slot is 0.5 · vi

(price 0 is charged per-click in the bottom slot).

Under the Generalized Second-Price (GSP) auction rule:

- 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 p at the top slot j, is set to be

equal to the declaration of the advertiser assigned to the bottom slot.

a. [7% ] Compute the optimal/highest social welfare (sum of individual values) in I.

b. [23% ] Assume the following strategy sets (the allowed strategies/reports 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 social welfare achieved in each of them.

You can (or not) follow a brute-force approach, i.e. consider all possible combinations of declarations

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 (even if your code doesn’t run or doesn’t compute an equilibrium). If your code successfully

computes one or more equilibria, present them in the report alongside their social welfare. Marks will

be awarded for partially-correct approaches.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- 代写 Lab 2: Threads 2022-05-10
- 辅导assessment 1. Present Your Client ... 2022-05-10
- 5Cce2sas辅导、Python，Java程序辅导 2022-05-10
- 代写brae Webb编程 2022-05-09
- 辅导csci 3110 Assignment 1 2022-05-09
- Mth2222 Assignment 2代写 2022-05-09
- Cse3bdc Assignment 2022辅导 2022-05-08
- 辅导cis 468、辅导java，Python编程 2022-05-08
- Comp Sci 4094/4194/7094 Assignment 3 D... 2022-05-07
- Cs 178: Machine Learning & Data Mining... 2022-05-07
- Data7703 Assignment 4 2022-05-07
- 讲解assignment 2: Databases 2022-04-25
- 辅导ait681 Static Analysis 2022-04-25
- Cse121 & Cse121l 编程辅导、辅导c++程序语言 2022-04-25
- 辅导iti1120 Bject-Oriented Programming 2022-04-25
- Cmt304语言辅导、辅导c++，Python编程 2022-04-25
- 辅导comp/Engn4528 Computer Vision 2022-04-24
- 辅导fin 2200 Bloomberg Investment Proj... 2022-04-24
- 辅导bism 7255 Uml Assignment 2022-04-23
- 讲解comp202 Programming Assignment 2022-04-23