HW6

Submit a single .pdf (or handcopy) for the written problems to me via email/on canvas (or in person) by the date of the deadline (11:59 pm)

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