Game Theory Taken Seriously For Advancing Self-Driving Cars

Dr. Lance Eliot, AI Insider

Image for post
Image for post

When you get onto the freeway, you are essentially entering into the matrix. For those of you familiar with the movie of the same name, you’ll realize that I am suggesting that you are entering into a kind of simulated world as your car proceeds up the freeway onramp and into the flow of traffic. Whether you know it or not, you are indeed opting into playing a game, though one much more serious than an amusement park bumper cars arena.

On the freeway, you are playing a game of life-and-death.

It might seem like you are merely driving to work or trying to get to the ballgame, but the reality is that for every moment you are on the freeway you are at risk of your life. Your car can go awry, say it suddenly loses a tire, and you swerve across the lanes, possibly ramming into other cars or going off a freeway embankment. Or, you might be driving perfectly well, and all of a sudden, a truck ahead of you unexpectedly slams on its breaks and you crash into the truck.

Leveraging Game Theory

If you are willing to concede that we can think of freeway driving as a game, you then might be also willing to accept the idea that we can potentially use game theory to help understand and model driving behavior.

With game theory, we can consider the freeway driving and the traffic to be something that can be mathematically modeled. This mathematical model can take into account conflict.

A car cuts off another car. One car is desperately trying to get ahead of another car. And so on. The mathematical model can also take into account cooperation. As you enter onto the freeway, perhaps other cars let you in by purposely slowing down and making an open space for you. Or, you are in the fast lane and want to get over to the slow lane, so you turn on your blinker and other cars let you make your way from one lane to the next. There is at times cooperative behavior on the freeway, and likewise at times there is behavior involving conflict.

If this topic generally interests you, there’s key work by John Glen Wardrop that produced what is considered the core principles of equilibrium in traffic assignment. Traffic assignment is the formal name given to modeling traffic situations. He developed mathematical models that showcase how we seek to minimize our cost of travel, and that we potentially can reach various points of equilibrium in doing so. At times, traffic suffers and can be modeled as doing so due to the “price of anarchy,” which is based on presumably selfish oriented behavior.

For those of you that are into computer science, you likely are familiar with the work of John von Neumann. Of his many contributions to the field of computing and mathematics, he’s also known for his work involving zero-sum games. Indeed, he made use of Brouwer’s fixed-point theorem in topology, and had observed that when you dissolve sugar in a cup of coffee that there’s always a point without motion. We’ll come back to this later on in this exploration of game theory and freeway traffic.

Let’s first define what a zero-sum game consists of.

In a zero-sum game, the choices by the players will not decrease and nor increase the amount of available resources, and thus they are competing against a bounded set of resources. Each player wants their piece of the pie, and in so doing are keeping that piece away from the other player. The pie is not going to expand or contract, it stays the same size. Meanwhile, the players are fighting over the slices and when someone else takes a slice it means there’s one less for the other players to have. A non-zero sum game allows for the pie to be increased and thus one player doesn’t necessarily benefit at the expense of the other players.

When you are on the freeway, you at times experience a zero-sum game, while at other times it is a non-zero sum game. Suppose you come upon a bunch of stopped traffic up ahead of you. You realize that there’s an accident and it has led to the traffic halting. You are going to get stuck behind the traffic and be late to work. Looking around, you see that there’s a freeway offramp that you could use to get off the freeway and take side streets to get around the snarl.

It turns out that the freeway traffic is slowly moving forward up toward the blockage, and meanwhile other cars are also realizing that maybe they should try to get to the offramp. You are in the fast lane, which is the furthest lane from the exit ramp. The cars in the other closer lanes are all vying to make the exit. They don’t care about you. They care about themselves making the exit. If they were to let you into their lane, it would increase your chances of getting to the offramp, but simultaneously decrease their chances. This is due to the aspect that the traffic is slowly moving forward and will gradually push past the offramp. There’s a short time window involved and it’s a dog eat dog situation. Zero-sum game.

But suppose instead the situation involved all the cars that were behind the snarl to share with each other to get to the offramp. Politely and with civility, the cars each allowed other cars around them to make the offramp. Furthermore, there was an emergency lane that the cars opted to use, which otherwise wasn’t supposed to be used, and opened up more available resources to allow the traffic to flow over to the exit. Non-zero sum game (of sorts).

Game theory attempts to use applied mathematics to model the behavior of humans and animals, and in so doing explain how games are played. This can be done in a purely descriptive manner, meaning that game theory will only describe what is going on about a game. This can also be done in a prescriptive manner, meaning that game theory can advise about what should be done when playing a game.

Applying Game Theory To Autonomous Cars

What does this have to do with AI self-driving driverless autonomous cars?

At the Cybernetic AI Self-Driving Car Institute, we are using game theory to aid in modeling the traffic that will occur with the advent of AI self-driving cars.

There are some that believe in a nirvana world whereby all cars on the roadways will be exclusively AI self-driving cars. This provides a grand opportunity to essentially control all cars and do so in a macroscopic manner. Presumably, either by government efforts or by other means, we could setup some master system that would direct the traffic on our roads. Imagine that when you got onto the freeway, all of the cars on the freeway were under the control of a master traffic flow system. Each car was to obey strictly to the master traffic flow system. It alone would determine which lane each car would be in, what the speed of the car would be, when it will change lanes, etc.

In this scenario, it is assumed that there would never be traffic snarls again. Somehow the master traffic flow system would prevent traffic snarls from occurring. All traffic would magically flow along at maximum speeds and we could increase the speed limit to say 120 miles per hour. Pretty exciting!

But, this is something that seems less based on mathematics and more so based on a hunch and a dream.

It’s also somewhat hard to believe that humans are going to be willing to give up the control of their cars to a master traffic flow system. I realize you might immediately point out that if people are willing to secede control of the driving task to an AI-based self-driving car, it’s a simple next step to then secede that their particular AI self-driving car must obey some master traffic control system. We’ll have to wait and see whether people will want their AI self-driving car to be an individualized driver, or whether they’ll be accepting that their individualized driver will become a robot Borg of the larger collective.

Anyway, even if all of this is interesting to postulate, it still omits the real-world aspect that we are not going to have all and only AI self-driving cars for a very long time. In the United States alone, there are 200+ million conventional cars. Those conventional cars are not going to disappear overnight and be replaced with AI self-driving cars. It’s just not economically feasible. As such, we’re going to have a mixture of AI self-driving cars and conventional cars for quite some time.

Predicting A Point Of Equilibrium

Returning to the aspect about using game theory, we can at least try to do traffic simulations and attempt to see what might happen as more and more cars become AI self-driving cars, especially those that are at the vaunted Level 5.

These simulations use various payoff matrices to gauge what will happen as an AI self-driving car drives alongside human driven cars. A symmetric payoff is one that depends upon the strategy being deployed and not the AI or person deploying it, while an asymmetric payoff is dependent. We also include varying degrees of cooperative behavior versus non-cooperative behavior.

John Nash made some crucial contributions to game theory and ultimately was awarded the Nobel Prize in Economic Science for it. His mathematical formulation suggested that when there are two or more players in a game, at some point there will be an equilibrium state such that no player can do any better than they are already doing. The sad thing is that we cannot yet predict per se when that equilibrium point is going to be reached — well, let’s say it is very hard to do. This is still an open research problem and if you can solve it, good for you, and it might get you your very own Nobel Prize too.

Why would we want to be able to predict that point of equilibrium?

Because we could then potentially guide the players toward it.

On the freeway, imagine that you have a hundred cars all moving along. Some are not doing so well and are behind in terms of trying to get to work on time. Others are doing really well and ahead of schedule and will get to work with plenty of time to spare. All else being equal, if we had a master traffic flow system, suppose it could reposition and guide the cars so that they would all be at their best possible state.

But if we aren’t able to figure out that best possible state, there’s no means to therefore guide everyone toward it. We instead have to use a hit-and-miss approach (not literally hit, just metaphorically). In more formal terms, Nash stated that for a game of a finite number of moves, there exists a means by which the player can randomly choose their moves such that they will ultimately reach a collective point of equilibrium, and that at that point no player can further improve their situation.

You might say that everyone has reached the happiest point to which they can arrive, given the status of everyone else involved too. When I earlier said it was hard to calculate the point of equilibrium, I was suggesting that it can be found but that it is computationally expensive to do so. Some of you might be familiar with classes of mathematical problems that are considered computable in polynomial time (P), and others that are NP (non-deterministic polynomial time). We aren’t sure yet whether the calculation of Nash’s point of equilibrium is P or NP. Right now, it seems hard to calculate, that we can say for sure.

By the way, for those of you looking for a Nobel Prize, please let us know if P = NP.

Conclusion

Game theory will increasingly become important to designing and shaping traffic flow on our roads, particularly once we begin to see the advent of true Level 5 AI self-driving cars. The effort to mathematically model conflict and cooperation in our traffic will involve not only the intelligent rational human decision makers, along with their irrational behavior, but also the potential intelligent rational (and maybe irrational) behavior of the AI of the self-driving cars.

Getting a handle on the traffic aspects will allow AI developers to better shape the AI of the self-driving cars and will aid regulators and the public at large in experiencing what hopefully will be better traffic conditions than with human-only drivers. I don’t think we want to end-up with AI self-driving cars that drive like those crazy human drivers that seem to not realize they are involved in a game of life-and-death. It’s deadly out there and we need to make sure that the AI self-driving cars know how to best play that that serious and somber game.

For free podcast of this story, visit: http://ai-selfdriving-cars.libsyn.com/website

The podcasts are also available on Spotify, iTunes, iHeartRadio, etc.

More info about AI self-driving cars, see: www.ai-selfdriving-cars.guru

To follow Lance Eliot on Twitter: @LanceEliot

For his Forbes.com blog, see: https://forbes.com/sites/lanceeliot/

For his Medium blog, see: https://medium.com/@lance.eliot

For Dr. Eliot’s books, see: https://www.amazon.com/author/lanceeliot

Copyright © 2019 Dr. Lance B. Eliot

Written by

Dr. Lance B. Eliot is a renowned global expert on AI, Stanford Fellow at Stanford University, was a professor at USC, headed an AI Lab, top exec at a major VC.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store