Tit-for-Tat and AI Self-Driving Cars

1169

By Lance Eliot, the AI Trends Insider

When I get to work each morning, I often see a duel between car drivers when they reach the gate that goes into the workplace parking garage. Let me describe the situation for you.

For those drivers such as me that tend to come into the parking garage from a major street that runs in front of the parking facility, we turn into a narrow alley that then leads to a gate arm. You need to then take out your pass card, wave it at the panel that will open the gate, and the gate arm then rises up (assuming you have a valid card). At this juncture, you are able to drive into the parking structure. This works just fine most of the time in the sense that once the gate arm is up, you zoom ahead into the parking structure.

But, it turns out that there is a second gate that is inside the parking structure and it allows traffic that is already in the structure to get onto the same parking floor as the gate that connects to the major street. This other gate arm is directly in front of the gate that I go through. So, what sometimes happens is that the gate opens from the street side, and there is a car inside the structure that at that same moment opens the gate that is just a few feet in front of the street side gate. Now, you have two cars facing each other, both wanting to go into the parking structure, but only one can do so at a time (because of the thin neck of the parking structure where the two gates are setup).

Imagine a duel in the old west days. Two gunslingers, both with loaded guns, eyeing each other. One waits for the other since either one might suddenly spring forth with their gun. Who will pull their gun out first? The same thing happens when both gates open at the same time. One car driver eyes the other car driver. Is the other car driver going to go first, or should I go first, that’s what’s in the mind of each driver.

Now, there are some car drivers that seem to not care that the other car driver might suddenly go forward, and as a result, these careless or heartless drivers just move forward and take what they seem to think is their birthright to always go first. This often seems to work out, admittedly. I’ve never seen two cars that crashed into each other. That being said, there are situations where both of the car drivers at each of the gates seems to believe they each have a birthright to make the first move. And, in those instances, the two cars have gotten pretty close to hitting each other. Typically, in this instance, they get within inches, one opts to stop, and the other driver zips ahead.

There are also the nervous nellies, or maybe they should more properly be known as courteous drivers, for whom when the gates open, each of those type of car driver looks to the other driver to go ahead and make the first move. These car drivers are willing to give the other driver the right of way. This is pretty nice, except admittedly sometimes it means that both cars are sitting there, waiting for the other, and because they are so giving that they are apparently willing to sit there forever (it seems), and meanwhile the car drivers behind them get really ticked off. You see, the gate arms are up, and yet nobody is moving, which can anger other drivers. If you are someone that is nearly late for work, and you see that nobody is moving, and yet the gate arms are up, you would be quite upset that you are being held back and that no one is moving ahead.

I’ve spoken with many of these drivers of each kind. The ones that are the birthright believers would say that it isn’t necessarily that they think they have a right of way, but instead they insist that their method is the most efficient. By not waiting around, they are moving the lines forward. Their belief is that all drivers should always be moving ahead as soon as the gate arm opens. If this means that you might also make contact with another car, that’s fine, since it is the modest cost for keeping the line moving efficiently.  These car drivers also think that the ones that wait once the gate opens are idiots, they are stupid because they are holding up the line and making things be inefficient.

The ones that are willing to wait for the other driver believe that this is the right way to do things. They believe it minimizes the potential for crashing into other cars. It is polite. It is civilized. The other car drivers that insist on the right of way are piggish. Those piggish drivers don’t care about other people and are ego-centric. They are the ones that ruin the world for everyone else.

Which is right and which is wrong?

You tell me. I’m not sure we can definitely call either one always right or always wrong. Certainly, the ones that increase the risk of cars hitting each other are endangering the lives of others, and so we could likely ascribe they are wrong for taking that first move.  I suppose though that those drivers would say that you might have drivers coming into the line that might hit the other cars ahead of them, since once the gate arm opens it suggests everyone should be moving forward, and so maybe there is that risk that needs to be compared to the risk of two cars hitting each other once the gates are open and the two cars are facing off.

It’s a conundrum, for sure.

The Prisoner’s Dilemma

Some of you might recognize this problem as one that has been affectionately called the Prisoner’s Dilemma.

In the case of the prisoner’s dilemma, you are to pretend that there are two people that have been arrested and are being held by the police in separate rooms. The two have no means to communicate with each other.  They were each potentially involved in the same crime. A prosecutor is willing to offer them each a deal.

The deal is that if one of them betrays the other and says that the other one did the crime, the one that does the betraying will be set free if the other one has remained silent (and in that case the other one will get 3 years in jail). But, if the other one has also tried to betray the one that is doing the betraying, they will both get 2 years in jail. If neither of them betrays the other, they will each get 1 year in jail.

So, if you were one of those prisoners, what would you do?

Would you betray the other one, doing so in hopes that the other one remains silent and so you can then go free? Of course, if the other one also betrays you, you both are going to jail for 2 years. Even worse, if you have remained silent and the other one betrays you, you’ll go to jail for 3 years. You could pin your hopes on the other one remaining silent and you opt to remain silent, figuring in that case you both only get 1 year each.

Another conundrum, for sure!

If you were to create a so-called payoff matrix, you would put on one axis the choices for you, and on the other axis the choices for the other person. You would have a 2×2 matrix, consisting of you remaining silent, you betraying the other, on one axis, and the other axis would have the other person remaining silent, or betraying you.

There is the viewpoint that by remaining silent you are trying to cooperate with the other person, while if you betray the other person then you are essentially defecting from cooperating. If you defect and the other person tries to cooperate, you get the payoff temptation labeled as T. If you cooperate and the other person cooperates, you get the payoff reward labeled as R. If you defect and the other person defects then you get the payoff punishment labeled as P. If you cooperate and the other person defects, you get the payoff “sucker bet” labeled as S.

In the game as I’ve described it:  T > R > P > S

I mention this because there are numerous variations of the dilemma in terms of the amount of payoff involved for each of the four choices, and it makes a difference in that unless the above is true, namely T > R, R > P, P > S, then the logic about what choice you should logically make is changed.

Anyway, what would you do? In theory, you are better off with betraying the other prisoner. This would be a proper thing to do in a rational self-interested way, since it offers the greatest option for the least of the penalties that you might get.

Now, you might try to fight the problem by saying that it depends on the nature of the other person. You might think that certainly you would already know the other fellow prisoner and so you would already have an inkling of how the other person is going to vote. If you knew that the other person was the type to remain silent, then you would indeed want to remain silent. If you knew that the other person was the type to fink on others, you’d presumably want to betray them.

But, we are going to say that you don’t know the other person and do not know what choice they are likely or unlikely to make.  Going back to the car drivers at the open gates, the car driver looking at the other car driver does not know that other person and does not know if they are the type of person that will zoom ahead or will be willing to wait. It’s the same kind of situation. Complete strangers that do not know what the other one will do.

Humans Tend Toward Cooperative Behavior

You might feel better about the world if I were to tell you that humans in these kinds of games have tended toward cooperative behavior and would more than not be willing to assume that the other person will act cooperatively too. I hope that boosts your feelings about humanity. Well, keep in mind that those that aren’t the cooperative types are now thinking that you are sheep and they like the idea that there are lots of sheep in the world. Sorry.

You might somewhat object to this prisoner’s dilemma since it only is a one-time deal. You might wonder what would someone do if the same dilemma happened over and over.  There is indeed the iterative prisoner’s dilemma, in which you play the game once, then after the outcome is known, you play it again, and so on. This makes for a quite different situation. You now can see what your other prisoner is doing over time, and opt to respond based on what the other person does.

When the number of times that the play is iterated is known to the players, the proper rational thing to do is for each to betray. In that sense, it is just like the single-shot game play. On the other hand, if the number of iterations is unknown, it is a toss-up as to whether to cooperate or to defect.

For the multiple plays, there are various strategies you can use. One is the “nice person” strategy of starting as a cooperative person and only switching if the other does a betray. The extreme of the nice person strategy is to always cooperate no matter what, but usually the other person will realize this and will then switch to betray for the rest of the game.

You might find of interest that these prisoner dilemma games have been played in numerous tournaments. One of the most winning strategies was done in four lines of programming code and became known as tit-for-tat. Whatever the other person did, the program did the same thing on the next move.  The only problem here is that often the game then goes into a death spiral of both players always defecting. As such, there is a variant that is tit-for-tat with some forgiveness, which will detect if a certain number of continuous betrayals has occurred and will then switch to cooperate in hopes that the other side will do so too.

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

At the Cybernetic Self-Driving Car Institute, we are developing AI for self-driving cars and there will be instances when a self-driving car will need to make these kinds of prisoner dilemma decisions, such as the case of the open gates and deciding who goes first.

You’ve likely heard about the famous example of the self-driving car that came to a four-way stop sign and waited for the other cars to go ahead, which it did because the other cars were driven by humans and those humans realized that if they rolled through the stop sign they could intimidate the self-driving car. The AI of the self-driving car had been developed to avoid potentially leading to a crash and so it sat at the stop sign waiting for the other cars to give it a turn to go.

If we had only self-driving cars on the roadways, presumably they would have each neatly stopped at the stop sign, and then would have abided by the usual rule of the first one there goes, or that the one to the right goes, or something like that. There would not have been a stand-off.  They might even be able to communicate with each other via a local V2V (vehicle to vehicle communication system).

But, we are going to have a mixture of both human driven cars and AI driven self-driving cars for many years, if not even forever, and so the AI of the self-driving car cannot assume that the other cars are being driven by AI. The AI needs to know how to deal with human drivers.

Suppose your self-driving car is on the freeway and a car in the next lane signals that it wants into the lane of the self-driving car. Should it let the other car in? If the AI does this, it could be that pushy human drivers realize that the AI is a sucker, and the next thing you know all the other cars around the self-driving car are trying to also cut into the lane. At some point, the AI needs to know when to allow someone else in and when not to do so.

If the AI is playing the always cooperate mode, it will be just like the prisoner’s dilemma that others will do the betray always to the AI because they know that the AI will cave in. Don’t think we want that.

In fact, there might be some owners of self-driving cars that will insist they want their self-driving car AI to be the betraying type. Just as they themselves are perhaps that egocentric person, they might want that their self-driving car has the same kind of dominant approach to driving. You might be thinking that we don’t need to let such car owners have their way, and that maybe the auto makers should make all self-driving cars be the cooperating type. Or, maybe we should have federal and state regulations that say an AI cannot be the betraying type and so this will force all AI to be the same way.  Again, this is highly questionable and raises the same points made earlier about the mix of human drivers and AI drivers.

I realize you might find it shocking to think that the AI would be potentially a pushy driver and insist on getting its way. Imagine a human driver that encounters such a self-centered self-driving car. Will the human driver have road rage against the AI self-driving car? No darned machine is going to take cuts in front of me, you can just hear the human driver screaming in anger. Fortunately, we are unlikely to get any road rage from the AI when the human cuts it off while driving, though, if we train the AI by the way that humans drive, it could very well have a hidden and embedded road rage within its deep learning neural network.

The ability to discern what to do in the prisoner’s dilemma circumstances is a needed skill for the AI of any self-driving car that is seeking to be a Level 5 (a Level 5 is a true self-driving car that can do whatever a human driver can do). Besides providing that type of AI skill, the other aspect is whether to allow the self-driving car owner or human occupant to modify what it is. For example, the voice command system of the AI in the self-driving car could interact with the owner or occupant and find out which dominant strategy to use, allowing the human owner or occupant to select whatever they prefer in the situation. If you are late for work, maybe you go with the betray, while if you are on leisurely drive and in no rush then maybe you choose the cooperative. Or, maybe the AI needs to ascertain the type of person you are, and take on your personality. It’s a tough driving world out there and the tit-for-tat is just one of many ways to for your AI to make its way through the world.

Copyright 2018 Dr. Lance Eliot

This content is originally posted on AI Trends.