The Price of Anarchy in the Congestion Game with Flow Constraints
摘要
This paper considers the congestion game with flow constraints. While the total number of players in the congestion game is usually specified and the flow of players assigned to each of the alternatives is, generally speaking, unlimited, in the formulation considered in this paper, the flow of players can be limited for each of the available alternatives and in total. The paper provides a general formulation of the congestion game with flow constraints and studies its solution space. We estimate the price of anarchy for different numbers of players, which helps us determine when the game’s equilibrium assignment is close to the social optimum and when it deviates. Finally, we consider examples of practical problems and cases that can be modeled and described using the corresponding game.