HW5

(1) Please show ALL of your work!!!!

*****************************************************************************************************************************

1) Graphical games: Consider the road game we discussed in class and the following road game with four players (labeled as player 1, player 2, player 3, and player 4).

(a) Formulate this instance as a graphical game (i.e., please define the graph, neighborhoods, actions, and utilities). You can specify the actions (e.g., two actions for each player) and the utilities of the players. (10 points)

2) Action-graph games: Consider the coffee shop game we discussed in class and the following coffee shop game with four actions (labeled as action 1, action 2, action 3, and action 4).

(a) Formulate this instance as an action-graph game (i.e., please define the graph, neighborhoods, and utilities). You can specify the number of players (e.g., 4 players) and the utilities of the players. (10 points)

3) Complexity: Specify the complexity of determining the existence of a pure-strategy Nash equilibrium and computing a mixed-strategy Nash equilibrium in the following games.

(a) Normal-form games. (10 points)

(b) Graphical games. (10 points)

4) Congestion games: Consider a network routing game where each agent has to route a unit flow on a directed graph from one node to another. Each edge has a delay that depends on the total flow on the edge. Each agent wants to minimize cost, which is the total delay on the edges on its selected route. See Figure below. There are four players, with start and end nodes as indicated. Each edge j is annotated with a cost function, either cj(x) = 0 or cj(x) = x.

(a) Formulate this as a congestion game. (10 points)

(b) Show that there is always a pure-strategy Nash equilibrium (via the potential function argument). (10 points)

(d) Demonstrate the usage of myopic best-response. (10 points)

Page updated

Google Sites

Report abuse