帮写COMP3477 Algorithmic Game theory 2023-24代做留学生SQL 程序

Summative Assignment

Module code and title	COMP3477 Algorithmic Game theory
Academic year	2023-24
Coursework title	AGT Assignment
Coursework credits	5 credits
% of module’s final mark	50%

Submission date*	Tuesday, April 23, 2024 14:00
Estimated hours of work	10 hours
Submission method	Ultra

Additional coursework files	AGTassignment-23-24.tex (optional template for writing the answers to individual exercises)
Required submission items and formats	One file per student, SOLUTIONSXXXXXX.pdf, where XXXXXX is the student’s CIS username.

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 ifshe 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 payoffs. [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]

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 payoff from the other player (who looses one unit of payoff).

(a) Write down a game tree representing this game in extensive form. and find all solutions (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 ∈ 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]

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:

(a1) Is this function a potential of the load balancing game considered, and if so, what type of potential is it? Justify your answer(s). [5 marks]

(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),

.  m identical tasks w1  = 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(OPT) in the special case where m = 2. [2 marks]

(b2)  Calculate the ratio cost(A)/cost(OPT) in the special case where m = 3. [3 marks]

(b3)  Discuss what the ratio cost(A)/cost(OPT) is for arbitrary m. What does this imply about the Price of Anarchy on identical machines for mixed Nash equilibria? [10 marks]

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.

(a) What are the prices of the sellers’ items (1st  item, 2nd  item,  . . . , kth  item) when the market clears? [2 marks]

(b) Which buyer gets the 1st item and at what price?	[2 marks]
(c) Justify your answers to (a) and (b).	[7 marks]

(d) Which kind of auction does the construction of market-clearing prices procedure implement in this case? [4 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 payoffs for a player i ∈ 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 form Si  = {(xi , Ki )  :  xi  ∈ A ,  Ki  ⊂ N}. What is the meaning of the set Ki? [5 marks]

(b)  Consider the strategy profile s = ((x1 , K1 ), . . . , (xn , Kn )) and let ∆(s) be the set of players who are not violating the law in s, that is ∆(s) = {i | i ∈ N ,  xi  = nv}.  Also let K(s) be the set of players that are being informed on by at least one neighbour in s, that is K(s) =" Ki. Determine a necessary and sufficient condition for s to be a Pure Nash Equilibrium of this game. Justify your answer. [10 marks]