Consider the following congestion network with three nodes. As shown, an edge has the cost function...

Transcribed Image Text:

Consider the following congestion network with three nodes. As shown, an edge has the cost function c(x) = on that edge is x, except for the edges vu and wu where c(x) = 0. The table on the right shows four users i 0; and destinations d¡. In this network, each user has two possible routes from her origin to her destination = x 0 X x И 0 x W user i 1 2 3 4 Oi u u V W di V W W x if the flow (number of users) 1, 2, 3, 4 with different origins V (a) Develop an algorithm, say Best-response dynamics, and implmenent it to find two equilibria of this congestion game, one with low cost and one with high cost. (do explain how the algorithm works and why) [5 marks] (b) Explain why the equilibrium property holds in each case. [2 marks] (c) Compare the costs of the two equilibria. Discuss which of them is socially optimal and Price of Anarchy. [3 marks] Consider the following congestion network with three nodes. As shown, an edge has the cost function c(x) = on that edge is x, except for the edges vu and wu where c(x) = 0. The table on the right shows four users i 0; and destinations d¡. In this network, each user has two possible routes from her origin to her destination = x 0 X x И 0 x W user i 1 2 3 4 Oi u u V W di V W W x if the flow (number of users) 1, 2, 3, 4 with different origins V (a) Develop an algorithm, say Best-response dynamics, and implmenent it to find two equilibria of this congestion game, one with low cost and one with high cost. (do explain how the algorithm works and why) [5 marks] (b) Explain why the equilibrium property holds in each case. [2 marks] (c) Compare the costs of the two equilibria. Discuss which of them is socially optimal and Price of Anarchy. [3 marks]

Answer rating: 100% (QA)

a Bestresponse dynamics is an iterative approach where each player in this case user sequentially chooses their best strategy given the strategies chosen by other players The algorithm will reach an e... View the full answer