Problem in game theory related to traffic networks

Question

I have learnt game theory for a short period of time and I am not familiar with multi-player non-zero sum games. Here is a problem from my book which I am stuck:

In this road network below each of $n$ players wishes to choose a route from $A$ to $D$. Each player experiences a delay that is the sum of the delays on the links of his route.

As shown in the diagram, there is a delay of $1 + \frac{x}{100}$ on link $AB$ when $x$ players use that link, and a delay of $1+\frac{y}{100}$ on $CD$ when $y$ players use that link. The delays on links $AC$, $BD$ and $BC$ are $2$, $2$ and $\frac{1}{4}$.

Suppose that in equilibrium, $n_1$, $n_2$ and $n_3$ players travel on routes $ABD$, $ACD$ and $ABCD$ respectively. Show that

$1.$ When $n=100$, there is an equilibrium at $n_1 = n_2 = 25, n_3=50$.

$2.$ It would be possible for the players to follow routes that make them all better off, but that this is not a Nash equilibrium.

$3.$ There exists an equilibrium which all players use the same strategy.

Can someone please help me? I have no idea how to even model this problem!

Answer 1

1) To show there is a Nash equilibrium, we show that no player can unilaterally deviate and improve his situation. When $n_{1} = n_{2} = 25$ and $n_{3} = 50$, the edges $(a, b), (c, d)$ have weight $1.75$. So suppose an ABD player chooses ACD instead. Then that player is adding $1$ to the edge $(c, d)$, increasing his cost of using that route. By symmetry, an ACD player will similarly not switch to ABD. If an ABD or ACD player chooses ABCD instead, then his cost becomes 3.76, where as staying yields a cost of 3.75. So no ACD and ABD players will deviate.

Now suppose an ABCD player deviates to either ACD or ABCD. On the ABCD route, this player contributes $\frac{1}{100}$ to the cost of the $(a, b)$ and $(c, d)$ edges. So whichever edge he uses, he still incurs that marginal cost. The $\frac{1}{4}$ from the $(b, c)$ edge lost, but then the $(a, c)$ and $(b, d)$ edges have a cost of $2 > 1.75$. So the total cost of switching is $1.75 + 2 = 1.75 + .25 + 1.75$, and so there is no incentive to switch. Thus, $n_{1} = n_{2} = 25$ and $n_{3} = 50$ is a Nash equilibrium.

2) Consider $n_{1} = n_{2} = 50$. What happens if a player from either class deviates to ABCD? Then the cost becomes $1.5 + 0.25 + 1.51 < 1.5 + 2$ for the deviating player. And so such a strategy is not a Nash equilibrium.

3) So a strategy is different than a route. A strategy can have choice in it. So if $x < 75$, purse $(a, b)$. Otherwise, pursue $(a, c)$. Now for the players at $b$, we consider the choice of finishing ABD or ABCD. In the Nash Equilibrium, we want individuals to be indifferent to the options. So if $50$ people travel along $(b, c)$, then $75$ people travel along $(c, d)$. And so $n_{1} = n_{2} = 25$, $n_{3} = 50$. This gives ABD a cost of 3.75, ACD a cost of 3.75, and ABCD a cost of 3.75. An ABD player won't deviate to ABC or ABCD, as that will drive the $(c, d)$ cost up by 0.01 and the total cost to 3.75. By similar argument, an ACD player won't deviate to ABCD or ABD. An ABCD player is indifferent to ACD, as $w(a, b) + w(b, c) = w(a, c)$ and $w(b, c) + w(c, d) = w(b, d)$. So there is no incentive for anyone to deviate.

Answer 2

A cheap answer for part 3 is to note that there is a general theorem that says that every finite symmetric normalform game has a symmetric Nash equilibrium (which may involve mixed strategies). This is a finite normalform game. Therefore the theorem applies. I don't have a reference for the theorem. But it is well-known. One may prove it using the standard argument, via Kakutani's fixed point theorem, but mapping each mixed strategy $\sigma$ of a single player into the set of all pure or mixed strategies that are best responses of a player if all other players choose the mixed strategy $\sigma$. This correspondence has a fixed point whenever the underlying game is finite and symmetric because it satisfies the assumptions of Kakutani's fixed point theorem: the domain and range is a convex set, the correspondence of best responses has a closed graph and is convex valued.

A calculation shows that in this game the following is a symmetric mixed strategy equilibrium: Players choose each of routes $ABD$ and $ACD$ with probability $\frac{25}{99}$ and they choose route $ABCD$ with probability $\frac{49}{99}$.The expected traveling time along route $ABD$ is then: $1+\frac{74+1}{100}+2=3.75$. (In the sum, the fraction in the middle has in the numerator the expected number of drivers other than myself taking route AB, which is $\frac{25}{99}\cdot 99+\frac{49}{99}\cdot 99$, plus 1, because I myself, if I take that route, am 1 additional driver.) The same applies to route $ACD$. For route $ABCD$ a similar calculation of the expected traveling times yields: $1+\frac{74+1}{100}+\frac{1}{4}+1+\frac{74+1}{100}=3.75$. So, drivers are indifferent between all routes, and we have a symmetric mixed strategy Nash equilibrium.

The symmetric mixed strategy Nash equilibrium is very similar to the asymmetric pure strategy Nash equilibrium.