|
Game theory - A Tutorial |
|
Static: Routing Game |
|
Drives can choose one of two routes, as shown in the left part of the figure. A total rate of 1 gets split into a fraction x taking the top route and 1 - x the bottom one. The delay on each link is indicated in blue. |
|
If x < 1/2, the delay along the top route is 1 + x, which is less than the delay 2 - x along the bottom route. By symmetry, selfish drivers choose the fastest route so that the equilibrium must correspond to x = 1/2 and a delay equal to 1.5 along each route. Now assume that one adds a link with zero delay as shown in the right-hand side of the figure. Selfish drivers, choosing the fastest path, all take the vertical shortcut when they get to it. That is, y = x. The delay for the fraction x of the drivers that set out along the top route is then x + 0 + 1 while the delay for the other drivers, using the bottom route, is 1 + 1 = 2. Accordingly, all the drivers prefer the top route, so that x = 1. Consequently, all the drivers face a delay equal to 2 (indeed, 1 + x = 2 when x = 1). Paradoxically, adding a link increases the delay of all the drivers. (Braess’ Paradox). Note that, in the network on the right, the value of x = 1/2 results in a delay equal to 1.5 for all the drivers, instead of a delay of 2 when the drivers are selfish. One says that the price of anarchy—the price for being selfish— is equal to 4/3, the increase in average price per user. [5]. |
