Network Congestion Simulation
Configuring the network
- Click in the open space to add a state
- Drag between states to add a transition
- Ctrl-drag a state to move graph layout
- Click a state or a transition to select it
- click the play button to run a Best Response Dynamics simulation
-
When a state is selected:
- Delete removes the state
- S select as source state for current player. will be shown as S<player> next to state.
selecting a source state will restart selected player strategy - T select as target state for current player. will be shown as T<player> next to state
- P select as next state for strategy of current player. path will be colored with player color
-
When a transition is selected:
- L(eft), R(ight), B(oth) change transition direction
- Delete removes the transition
- Ctrl edit transition cost
What is a Network Congestion Game?
Network Congestion Games are a type of strategic games where each player chooses a subset from a set of resources,
and the cost of each resource dependes on the number of players who chose it.
Each player's selection is called his strategy, and the set of all strategies for all players is called a profile.
Congestion games belong to a special class of potential games considered in game theory.
Potential games always have a Nash Equilibrium (NE) - a profile for which no player has an incentive to switch his strategy.
Our simultation visualizes the Best Response Dynamics (BRD) algorithm, which finds the NE in any congestion game you define.
Example for a congestion game
Consider the example above: players A,B and C have to go from point S to T using road segments SX, XY,...etc.
Numbers on edges denote the cost for a single user for using the corresponding road segment, where the actual
cost is a function of the actual number of players using that road segment(i.e. a descrete delay function).
For example: if segment SX is used by a 1,2, or 3 users, the cost on that segment would be 2,3, or 5, respectively.
The total cost of each player is the sum of all segments he uses. Note that the players are therefore engaged in a
game which can be represented in a strategic form(as a cost matrix).
References
If you're curious to learn more, here are a few useful resources: