 |
We consider a nonatomic congestion game on a connected graph, with several classes of players. Each player wants to go from its origin vertex to its destination vertex at the minimum cost and all players of a given class share the same characteristics: cost functions on each arc, and origin-destination pair. In the transportation terminology, each class models a distinct mode of transportation, such as cars, trucks, or motorbikes for example.
A strategy profile is a mapping determining for each player a route from its origin to its destination. A strategy profile is a (pure) Nash equilibrium if no player would benefit by changing its route.
This game enters in the category of nonatomic congestion games with player-specific cost functions, see Milchtaich (Congestion games with player-specific payoff functions, Games Econom. Behavior, 13:111-124, 1996). The problem of finding a Nash equilibrium for such a game is called the Multiclass Network Equilibrium Problem.
Under some mild conditions, it is known that a Nash equilibrium exists, but the computation of an equilibrium in the multiclass case is an open problem for general functions. We consider the specific case where the cost functions are affine and stricly increasing. In this case, we write the Multiclass Network Equilibrium Problem as a linear complementarity problem. Our contribution is twofold:
- We prove the existence of a polynomial algorithm solving the problem when the graph consists in parallel arcs. The main idea of the algorithm relies on properties of hyperplane arrangements.
- We build a pivoting algorithm, adapted from Lemke (Bimatrix equilibrium points and equilibrium programming, Management Science, 11:681-689, 1965), solving the problem for general graphs. To our knowledge, it is the first algorithm solving this problem. We prove its efficiency through computational experiments. Moreover, this algorithm provides the first constructive proof of the existence of an equilibrium for this problem.
