HW5

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

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

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

(c) Identify two (pure-strategy) Nash equilibria of the game. Show why they are equilibria. (10 points)

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

2) Interdependent Security (IDS) Games: Create your own instance of IDS games with 3 players. 

(a) Formulate this instance as an IDS game. (10 points) 

(b) Apply the algorithm presented in class to compute a (pure-strategy) Nash equilibria in your instance. (10 points)

(c) Summarize the experimental section of IDS game paper. (10 points)