Algorithmic Game Theory Summative Assignment: Nash equilibria and Auction
Algorithmic Game Theory Summative Assignment
2024
IMPORTANT: You should submit a single PDF file named SOLUTIONSXXXXXX.pdf, where XXXXXX is your CIS username in lowercase letters.
Solve exercises 1 - 5.
Your answers should be either written using Latex (you may use the settings of the Latex template file AGTassignment-23-24.tex provided) and compiled into pdf (only the pdf should be handed in), or hand- written and scanned (in which case you should hand in the scanned pdf).
Note 1: Make sure your answers are clear and detailed. Marks will be deducted if your
answers are not clear or explanations are missing.
Note 2: In the case where you return a scanned copy of your handwritten notes, please
make sure your writing is legible and neat. Marks will be deducted if your answers are not
neatly written.
Note 3: Please remember that you should not share your work or make it available where others can find it as this can facilitate plagiarism and you can be penalised. This requirement applies until the assessment process is completed which does not happen until the exam board meets in June 2024.
Exercise 1. A crime is observed by a group of n people. Each person would like the police to be informed, but prefers that someone else make the phone call. Suppose each person attaches the value v to the police being informed and bears the cost c if she makes the call, where v > c > 0. Suppose also that each person attaches the value 0 to the police not being informed.
-
(a) Formulate the above game as a strategic game.
Clearly define the players, actions and payo↵s. [5 marks] -
(b) Does the game have any pure Nash equilibria and, if so, what are they? Justify your answer and show all your working. [5 marks]
-
(c) The game is symmetric, so it must have a symmetric Nash equilibrium. Find said equilibrium.
Show all your working.
[10 marks]
1
Exercise 2. Two players, Player 1 and Player 2, take turns removing 1 or 2 cards from a stack of 6 cards, i.e., each of them, every time their turn comes, pick 1 or 2 cards to remove. Player 1 starts the game. Whoever picks the last card wins 1 unit of payo↵ from the other player (who looses one unit of payo↵ ).
-
(a) Writedownagametreerepresentingthisgameinextensiveformandfindallsolutions(subgame perfect equilibria) using backward induction.
Clearly describe your steps in detail. Who wins? [7 marks] -
(b) Generalise your answer for the case where there are n cards in the stack, n 2 N, and each of the two players picks 1 or 2 cards to remove every time their turn comes. Who wins? Justify
your answer and show all your working.
[18 marks]
2
Exercise 3.
(a) Consider the selfish load balancing scenario of m equispeed machines (all speeds equal to 1)
and n selfish users (user i = 1,...,n) with integer weights w1,w2,...,wn. User i has to choose
a single specific machine to allocate her weight, wi.
The cost of user i, provided that she chooses to allocate her load wi to machine j, is exactly
the sum of all loads that are allocated to machine j.
For any particular allocation A of weights to machines as described above, let lj(A) be the (total) load of machine j. Consider the function:
Xm
l j2 ( A )
potential is it? Justify your answer(s). [5 marks]
F ( A ) =
(a1) Is this function a potential of the load balancing game considered, and if so, what type of
(a2) Based on (a1), give the pseudocode of a program that uses F to compute a pure Nash equilibrium of the game. [5 marks]
(b) Consider the following instance of the load balancing game where the number of tasks is equal to the number of machines, and in particular we have:
• m identical machines M1, M2, . . . , Mm (all of speed 1),
• midenticaltasksw1 =w2 =···=wm =1.
Consider also the mixed strategy profile A where each of the tasks is assigned to all machines
equiprobably (i.e., with probability 1/m).
-
(b1) Calculate the ratio cost(A)/cost(OP T ) in the special case where m = 2. [2 marks]
-
(b2) Calculate the ratio cost(A)/cost(OP T ) in the special case where m = 3. [3 marks]
-
(b3) Discuss what the ratio cost(A)/cost(OP T ) is for arbitrary m. What does this imply about the Price of Anarchy on identical machines for mixed Nash equilibria? [10 marks]
3
j=1
Exercise 4. We consider a (matching) market of k sellers and k buyers, where k is an integer, k > 0.
Each seller sells an item and the prices of the items are initially all zero. Buyer i has valuation k i + 1 for the first item and valuation 0 for every other item, as shown in the following diagram.
Buyers
x1 x2 .
xk
-
(a) What are the prices of the sellers’ items (1st item, 2nd item, . . . , kth item) when the market
clears?
-
(b) Which buyer gets the 1st item and at what price?
-
(c) Justify your answers to (a) and (b).
-
(d) Which kind of auction does the construction of market-clearing prices procedure implement in
this case?
[4 marks]
Valuations (for items 1 to k) k, 0, ..., 0 k1, 0, ..., 0
.
1, 0, ..., 0
4
[2 marks] [2 marks] [7 marks]
Exercise 5.
A set N of |N| = n neighbours decide simultaneously and independently from each other, on one hand whether to build an extension to their home without getting proper planning permission, and on the other hand which of their neighbours to notify the local authority’s planning department about. The possible payo↵s for a player i 2 N are:
a if i built an extension without proper permission and none of the neighbours informed on him; b if i did not build an extension without proper permission; and
c if i built an extension without proper permission and at least one of the neighbours informed on him.
We assume that a > b > c.
-
(a) Let A = {v,nv}, where ‘v’ stands for ‘violating the law (by building an extension without proper permission)’ and ‘nv’ stands for ‘not violating the law (by not building an extension without proper permission)’. Clearly explain why the set of pure strategies of player i is of the formSi={(xi,Ki) : xi2A,Ki⇢N}.WhatisthemeaningofthesetKi? [5marks]
-
(b) Consider the strategy profile s = ((x1, K1), . . . , (xn, Kn)) and let (s) be the set of players who arenotviolatingthelawins,thatis(s)={i|i2N , xi =nv}. AlsoletK(s)bSetheset of players that are being informed on by at least one neighbour in s, that is K(s) = ni=1 Ki. Determine a necessary and sucient condition for s to be a Pure Nash Equilibrium of this
game. Justify your answer.
[10 marks]
5
