it's game theory question please do itself don't do from internet otherwise I will report it Exercise

it's game theory question please do itself don't do from internet otherwise I will report it

 

Transcribed Image Text:

Exercise 3: Consider the following game. We have a set N = {1,...,n) of n players, and E a set of resources (e.g., edges of a graph). Each player i, with 1 i n, chooses a strategy A S. C 2 (for example, a path in a graph) from a subset of possible strategies S. Let A = (A1,...,An) be a solution. In solution A, the cost for player i is c(A) = ZeeAi ne(A), where ne(A) is the number of players using resource e in A. Each player seeks to minimize their cost. The global objective function is SUM(A) = EN C.(A). The price of anarchy is defined as PA = maxA Nash equilibrium SUM(A)/OPT, where OPT = min, SUM(P) is the value of an optimal solution. In the following, A = (A1,...,An) is an arbitrary Nash equilibrium and P = (P1,...,Pn) is an optimal solution. 1. Show that SUM(A) = ZEE ne(A). 2. Show that c(A) eepi (ne(A) + 1). S 3. Show that SUM(A) (1/3) SUM(A) + (5/3) SUM(P). Hint: For any pair of positive integers a and , we have (a + 1) (1/3)a + (5/3). 4. What can be concluded about PA? Exercise 3: Consider the following game. We have a set N = {1,...,n) of n players, and E a set of resources (e.g., edges of a graph). Each player i, with 1 i n, chooses a strategy A S. C 2 (for example, a path in a graph) from a subset of possible strategies S. Let A = (A1,...,An) be a solution. In solution A, the cost for player i is c(A) = ZeeAi ne(A), where ne(A) is the number of players using resource e in A. Each player seeks to minimize their cost. The global objective function is SUM(A) = EN C.(A). The price of anarchy is defined as PA = maxA Nash equilibrium SUM(A)/OPT, where OPT = min, SUM(P) is the value of an optimal solution. In the following, A = (A1,...,An) is an arbitrary Nash equilibrium and P = (P1,...,Pn) is an optimal solution. 1. Show that SUM(A) = ZEE ne(A). 2. Show that c(A) eepi (ne(A) + 1). S 3. Show that SUM(A) (1/3) SUM(A) + (5/3) SUM(P). Hint: For any pair of positive integers a and , we have (a + 1) (1/3)a + (5/3). 4. What can be concluded about PA?