Coalitions in nonatomic network congestion games

This work shows that the formation of a finite number of coalitions in a nonatomic network congestion game benefits everyone. At the equilibrium of the composite game played by coalitions and individuals, the average cost to each coalition and the individuals ’ common cost are all lower than in the corresponding nonatomic game (without coalitions). The individuals ’ cost is lower than the average cost to any coalition. Similarly, the average cost to a coalition is lower than that to any larger coalition. Whenever some members of a coalition become individuals, the individuals ’ payoff is increased. In the case of a unique coalition, both the average cost to the coalition and the individuals ’ cost are decreasing with respect to the size of the coalition. In a sequence of composite games, if a finite number of coalitions are fixed, while the size of the remaining coalitions goes to zero, the equilibria of these games converge to the equilibrium of a composite game played by the same fixed coalitions and the remaining individuals. Key words: coalition, nonatomic game, atomic splittable game, composite game, network congestion game, routing game, Wardrop equilibrium, composite equilibrium