Caditz/Newman

Traffic modeling is fundamentally a problem in Game Theory

It has become commonplace to simulate traffic flow as a fluid dynamics problem, treating vehicles as particles in a collective flow. Steady-state macroscopic quantities such as flow density and speed, as well as collective phenomena such as congestion waves, can be modeled in simple situations such as on a stretch of highway. In such cases, flows can be modeled using a continuity equation, accounting for upstream sources and downstream sinks.

The application of modeling and simulation to road networks is more difficult. One issue is that on a road network, vehicles cannot reasonably be treated as particles in a flow. In reality, drivers have choices among alternative routes. Given sufficient information about traffic conditions, drivers can make rational choices which they believe will optimize their routes, arriving at their destination sooner, in a shorter distance, or along their preferred roadways. For this reason, the analysis of traffic flow on a network is fundamentally a problem in Game Theory.

Imagine two drivers, Mary and Fred, operating on the same road network. Mary can choose either Route A or Route B to arrive at her destination. Likewise, Fred can choose either Route C or Route D. These routes may interfere in such a way that if Mary chooses Route A and Fred chooses Route C, both are delayed. For example, say there is a single lane bridge with a limited capacity of a single vehicle. A similar situation holds for Route B and Route D. We can describe the situation using the matrix shown below. Driving times are given in the body of the matrix in minutes, where the numbers before the '/' represent Fred's driving time and the numbers after the '/' represent Mary's driving time. For example, if Mary chooses Route B and Fred chooses Route C, Mary will arrive at her destination in 20 minutes and Fred in 25 minutes.

Now let's consider the information available to Mary and Fred. Say that Fred is not aware that Mary is on the road. He will likely choose his fastest route, Route D, thinking it will take only 20 minutes. This is his best case scenario. However, when he unexpectedly encounters Mary, he is delayed by 10 minutes, his worst case scenario. On the other hand, if Fred knows that Mary was on the road, he may make another choice, even if he does not know which route Mary will take. But what choice would be his best? It turns out that this problem does not have a single best solution. The best choice for both players is a so-called mixed strategy where each driver chooses one of their routes with some probability.

But what if some central mediator could choose (and enforce) each driver's route? We could then be assured of minimal interference between drivers using the network. Such a scenario could be possible in the case of connected autonomous vehicles! If both Fred and Mary make their origins and destinations known to a central controller, then the central controller could choose the best route combination optimizing, say, aggregate driving time.

The routing problem with hundreds or even thousands of drivers is an example of a multiplayer game. When origins, destinations, real-time positions of each vehicle are known by all players, we say that it is a game of perfect information. When the routing preferences - e.g., fastest route, shortest route, etc. - of all players are known, then we say it is a game of complete information. CAVs allow the routing games to be cast as multiplayer games of perfect and complete information. Such games are solvable, in principle in extended form by backwards induction on a game tree.