Uneasy Alliances II: Why Two-Face Loses by Flipping a Coin

Earlier we began a discussion of Harvey Dent and James Gordon's alliance to clean up the streets of Gotham. We concluded that cooperation did make sense in the scenario portrayed by the film The Dark Knight. The cooperation game, or the Stag Hunt game, produced two pure strategy Nash Equilibria -- both players would cooperate or both players would work on their own.

Now, suppose that we take the same situation but introduce randomization. That is, suppose Harvey decides he wants to randomize his actions so that Gordon could not predict what he would do. Note that this is extremely unlikely; people usually intentionally randomize when they are working against another player. But for the sake of argument, suppose that it applies here.

The idea of assigning a certain probability towards an action is known as a mixed strategy. In this game, we can actually find a third, mixed-strategy equilibrium in addition to the two pure strategy ones we had found in the previous post.

So, here is the matrix from last time:

Harvey Dent -->> James Gordon ↓	Cooperate	Don’t Cooperate
Cooperate	(4,4)	(1,3)
Don’t Cooperate	(3,1)	(3,3)

Suppose that Harvey assigns a probability, p, to cooperating and (1-p) to not cooperating. Then we could perform an expected utility calculation to deduce Gordon's optimal strategy.

Recall that Expected Utility (EU) of a given action is equal to the sum of the utility values (U) or outcomes weighted by the probabilities (p) of receiving each. Therefore:

EU = p * U(Cooperate) + (1-p) * U(Don't Cooperate)

Then the expected utility if Gordon cooperates is:
EU(Gordon Cooperates) = p * 4 + (1-p) * 1
=4p + 1 - p
=3p + 1

The expected utility if Gordon does not cooperate is:
EU(Gordon Does Not Cooperate) = p * 3 + (1-p) * 3
= 3p + 3 - 3p
= 3

We know that Gordon will choose whichever action gives yields the greatest expected utility. So setting the two equations equal to each other, we have:

EU(Gordon Cooperates) = EU(Gordon Does Not Cooperate)
3p + 1 = 3
3p = 2
p = 2/3

Therefore, Gordon will cooperate only if the probability that Harvey cooperates is greater than 2/3. Otherwise, he will not cooperate. We can perform the exact same analysis by assigning a probability, q, to Gordon's actions and calculating expected utilities for Harvey. It will yield the same answer, namely that q = 2/3.

So p = q = 2/3 and we have a new, mixed strategy equilibrium where each player chooses to cooperate 2/3 of the time and does not cooperate 1/3 of the time. If Harvey decides to randomize this way, then Gordon cannot benefit by deviating from this strategy alone.

This result is interesting for several reasons. First, each player's expected payoff under mixed strategies is 3. Therefore, the mixed strategy equilibrium outcome is no better than either of the pure strategy ones. Therefore, Dent and Gordon would be just as well off choosing not to cooperate with each other 100% of the time. They would each be strictly better off choosing to cooperate 100% of the time.

Second, I had mentioned before that we were supposing Harvey intentionally randomized his actions, but the truth is that this mixed strategy exists whether he wants to or not. The reason is that these mixed strategies can be interpreted to reflect one individual's beliefs about the other's actions. In other words, Harvey choosing cooperate 2/3 of the time and choosing to work on his own 1/3 of the time can be seen as Gordon's views on what Harvey will do given his uncertainty in the matter. If he believes Harvey will cooperate 2/3 of the time, then he will cooperate 2/3 of the time.

Now suppose that Harvey decides to flip a coin instead. And what's more, suppose that Gordon knows that Harvey will flip a coin. What will Gordon do? And will this be an equilibrium?

If Harvey flips a coin to decide, this means that he will cooperate 50% of the time and work on his own 50% of the time. So, Gordon's expected payoff will be:

EU(Gordon Cooperates) = (1/2 * 4) + (1/2 * 1) = 2.5
EU (Gordon Does Not Cooperate) = (1/2 * 3) + (1/2 * 3) = 3

Therefore, Gordon will derive a larger expected utility from not cooperating and will choose to work on his own all of the time.

This, however, is not an equilibrium. We already know that if Gordon chooses to work alone 100% of the time, then Harvey would be strictly better off by also choosing not to cooperate 100% of the time. By sticking to the coin strategy, Harvey is actually losing some utility.

Of course, there are certain situations where flipping a coin could work. Suppose that Two-Face and the Penguin are facing off against each other by driving their cars towards one another in a bizarre game of chicken. Each can choose to go left or go right. The only thing is that they have to make their decisions at the same time, so nobody gains any utility by turning first. All we know is that each wants to live. So, if they both turn left, they each receive a utility of 10 for being alive. If they each turn right, they will also receive a utility of 10. If one turns left and the other turns right, both will die in the car crash and receive a utility 0f 0. The matrix then looks like this:

Two Face -->> Penguin ↓	Left	Right
Left	(10,10)	(0,0)
Right	(0,0)	(10,10)

Here if we perform the same utility calculations as above, assigning a probability of p to Two-Face turning left, we will arrive at p=1/2. Therefore, if Two-Face chooses to flip a coin intentionally, the Penguin should do the same and this would be a mixed-strategy Nash equilibrium.

Now, this sort of situation does not happen often. And this is why Two-Face's gimmick of flipping a coin to make every decision is usually a costly one. First of all, he gives away his strategy, making it easy for his opponents to predict their best actions. Second, it is not always the case that choosing one action 50% of the time and another 50% of the time is a mixed-strategy equilibrium, as we saw above. If Two-Face continues to adhere strictly to this strategy, he will be losing in the long-run.

And this is why Batman will always win. He knows his economics.

share on: del.icio.us digg reditt su

Dent and Gordon's Uneasy Alliance: A Game Theoretic Analysis

Watching the film, The Dark Knight, got me thinking more about trust and cooperation. In fact, trust seems to be a big theme in the movie (as it was in Batman Begins). For example, though we know that future Batman and future Commissioner Gordon form a close bond predicated on absolute trust and respect for one another, the relationship was more uneasy at the dawn of Batman's career. Gordon knew that in order to aid a masked vigilante, he had to bend the rules of the law and risk his career. Batman knew that in order to gain help from the inside, he needed to accept someone into his operation who could at any moment turn on him and compromise his mission. In Frank Miller Batman: Year One, we are actually given access into Gordon's mind as he struggles with the implications of partnering with Batman.

There are other examples of cooperation and trust that are presented in the Christopher Nolan films as well. Batman's gradual but cautious partnership with Harvey Dent, Lucius Fox's faith in Bruce's use of company technology, even mob loyalties towards one another. And the movie certainly does pose a few interesting questions. Namely, "Are these partnerships a good idea" and "What are the potential consequences of such relationships?" We also are allowed to see the short-term effects of some of these, particularly Batman's relationship with Gordon. SPOILER ALERT. Towards the end of the film, we in fact see their ties severed and the good that they had accomplished slowly wither away.

But let's take it a step back and think about a specific example in game theoretic terms to see whether cooperation makes sense. Earlier, we had considered the case of villains betraying each other after neutralizing Batman's threat, which we likened to the famous example of the Prisoner's Dilemma. Now, we consider a different scenario--one in which cooperation, rather than defecting, might be an optimal choice for each party involved.

Let's take the example of Gordon and Harvey Dent in the Dark Knight. Recall the scene in which Gordon meets with Dent at the DA's office following an unsuccessful trial in which the latter attempted to convict Boss Maroni for his connections to the mob. In this scene, Dent proclaimed that despite all of his best efforts, he was at best only able to put some mobsters away and was ultimately incapable of rooting out their money laundering schemes and halting the transfer of illegal money. Conversely, Gordon, with Batman's help, was able to craft a scheme to seize the mob's finances from five notable banks. However, he needed Dent to issue warrants to back the search and seizures on the banks. Without Dent's help, Gordon and Batman could only continue stopping pockets of crime here and there.

It is clear that the benefits of cooperation in this case would be a significant reduction in mob power and influence. However, both Gordon and Dent have some reservations about partnership. Gordon was skeptical about allowing a third party to meet Batman, fearing both that it would make the operation too large and that it would increase the chances of either sensitive information being leaked or the operation being compromised. Dent feared that he could not trust Gordon's Major Crimes Unit after having investigated several of its members in Internal Affairs.

Though they had met and ultimately agreed to cooperate, let us suppose that their mistrust was considerable enough to cause serious doubts. That is, neither Gordon nor Dent were 100% certain of the actions of the other player. What would their optimal choices be in this situation?

We need to assign some utilities here. Let's say if both players cooperate then each would receive a utility of 4 for the success of having rooted out the mob's finances. If neither chooses to cooperate, but rather continue with their separate means of crime-fighting, then each would receive a utility of 3. They would continue catching mobsters and putting some in jail, but of course this would not be as beneficial to either as "hitting them where it hurts: their wallets." Suppose that Gordon decides to cooperate, setting up the scheme to seize assets from the five banks and involve Batman, but Dent backs down at the last minute. In this scenario, Dent would still receive a utility of 3 for catching criminals on his own, but Gordon's utility would be reduced, say, to a utility of 1 for having planned the operation and expending all the resources of his unit. Conversely, if Dent decides to cooperate and drafts up the warrants, but Gordon decides not to include him after all, then Gordon would receive the utility of 3, while Dent would receive the utility of 1 for having wasted the effort.

This scenario is similar to the popular game known as the Stag Hunt. In it, two hunters decide whether to cooperate to catch a stag (from which they each derive greater utility) or go separately and each catch a hare. The following normal-form matrix represents these utilities.

Harvey Dent -->> James Gordon ↓	Cooperate	Don’t Cooperate
Cooperate	(4,4)	(1,3)
Don’t Cooperate	(3,1)	(3,3)

Let's find the pure strategy Nash Equilibria of this game. Suppose that Dent decides to cooperate. Then it would be in Gordon's best interest to cooperate as well, for he would receive a utility of 4 instead of a utility of 3. However, if Dent decides not to cooperate, Gordon would be better off by also not cooperating, for he would only receive a utility of 1 for cooperating, rather than a utility of 3 for going on his own.

Similarly, if Gordon decides to cooperate, Dent should choose to cooperate as well, as he would also receive a utility of 4 as opposed to 3. Should Gordon choose not to cooperate, Dent would also be best served by not cooperating, as he would receive a utility of 3 rather than 1.

Notice that the results of this game are quite different than that of the Prisoner's Dilemma. Namely, this game actually has two pure strategy Nash equilibria (strategies in which neither player can benefit by deviating alone). Either both players will cooperate or both players will work alone. Recall that in the Prisoner's Dilemma (Batman villains betraying each other), there was only one pure strategy Nash Equilibrium: both villains betray each other. Although both players would benefit by cooperating, it did not make sense for either player to do so individually. Rather, each should have always chosen to betray each other. In this case, however, Gordon and Dent choosing to work together could make sense.

Note that there is a difference between the two Nash Equilibria in this game. If both players cooperate, this is known as a payoff dominant equilibrium. This means that it is Pareto superior to all other outcomes in the game, i.e. should players choose to cooperate, each would receive more benefits than any other outcome. However, the other equilibrium, in which both players work on their own, is risk dominant. This means that as players become more uncertain of the actions of the other player, they would be more likely to choose the strategy that leads to this outcome. The reason is that choosing not to cooperate guarantees a utility of 3, whereas an individual choosing to cooperate bears the risk of receiving a utility of 1.

In fact, one major implication of this game (aside from the fact that there are situations in which cooperation makes sense) is that an individual's view of another one's actions matter. Suppose Gordon knew the probability that Dent would cooperate. How would this affect his actions? This is where mixed strategies and randomization come into play. As it turns out that this "Stag Hunt" game contains one mixed strategy Nash equilibrium. We shall consider these mixed strategies in an upcoming post.

share on: del.icio.us digg reditt su

Destroyer Likes Supervillain Team Ups

Here, Destroyer tells the menacing Scar that he made a blunder by summoning multiple villains to cooperate. The reasoning is having all of them in one place would make it easier for him to kill them all. Turns out, he was right. Scar's ego forced him to neutralize the other villains just so he would experience the glory of defeating Destroyer himself. Of course, this ultimately led to his demise...

share on: del.icio.us digg reditt su

Should Batman Villains Betray Each Other? (Analysis using the Prisoner's Dilemma)

(This is the second part of a post that will include some very light and simple algebra and game theoretic concepts. Not to worry--it is pretty crude and easy to follow along with. Also, please note that the assumptions made are rudimentary and based off of my own view of Batman and his villains. I welcome everyone to debate them with me).


We've discussed the decision of whether or not Batman villains should cooperate. Now consider another fun issue: lets suppose some of them do, in fact, work together and somehow manage to capture the Batman. There is now another decision that has to be made by each: whether or not to betray the partner.

Let's talk about Two-Face this time. As discussed in the previous post, the benefits of betrayal are obvious. Two-Face could claim full credit for killing Batman, could win the respect of the Gotham underworld, could elicit fear from the elite, and could potentially acquire some wealth and technology from the Batcave that he would not have to share with, say, Mr. Freeze (I can't think of a conceivable reason for that pair to team up, but I haven't used Mr. Freeze anywhere yet).

This situation is a nice example of the Prisoner's Dilemma. So, let's do a really quick summation of this two-player (Two-Face, Mr. Freeze), two-choice (Cooperate, Betray) game in Batman terms to show that it would actually make sense for the two of them to continue to cooperate, even though neither will. We must again assign some utilities for each player. I have done so, as the following normal-form game matrix represents:

Mr. Freeze -->> Two-Face ↓	Cooperate	Betray
Cooperate	(5,5)	(0,10)
Betray	(10,0)	(3,3)

In this matrix, Two-Face is the player on the left and Mr. Freeze is the player on the top. Each has the choice of either cooperating after capturing Batman or of betraying the other. In each cell, the numbers represent the utilities awarded to the respective players given their choice of action.

If both villains cooperate with one another, they each enjoy a utility of 5 from killing Batman and ruling Gotham (5,5). If Two-Face cooperates but Mr. Freeze betrays, then we will assume that Freeze will eliminate Two-Face, thereby winning all of his utility. In this case, Two-Face would get 0 utility and Mr. Freeze would get a utility of 10 (0,10). If Two-Face betrays but Mr. Freeze cooperates, then the opposite happens: Two-Face gets a utility of 10 and Freeze gets 0 (10,0). If they both betray each other, I'm going to assume that they'll either kill each other (in which case they'd both get 0) or they'll both walk away alive, but each would get less utility than they would have if they had cooperated (obviously they'd prefer not to engage in a near-death battle with one another, so they would lose something). Lets award each a utility of 3 in this situation (3,3).

If this is the scenario, each player would rationally want to betray the other. To see this, we must note that Two-Face and Mr. Freeze are hopelessly self-interested. They only care about their own utilities and not that of the other player. Now assume Mr. Freeze decides to cooperate. So we are restricted to the "cooperate" column of the table above. Looking at Two-Face's utilities in that column, it is clearly a better decision for him to betray, as he would be receiving a utility of 10 as opposed to 5. Let's say Mr. Freeze decides to betray, so we are now in the "betray" column. The best decision for Two-Face is still to betray, as he would receive a utility of 3 instead of 0. Hence regardless of what Mr. Freeze does, Two-Face would still want to betray him. The same is true for Mr. Freeze given Two-Face's actions.

Both players will choose to betray each other and (3,3) is the Nash equilibrium outcome. This means that neither Two-Face nor Mr. Freeze can benefit by deviating from his course of action alone. The dilemma, however, is that there exists an outcome in which both players are strictly better off. If both choose to cooperate, then each receive a utility of 5, which is greater than 3. Thus the outcome (5,5) is the Pareto Optimal point. It is the outcome of the game in which one player deviating would necessarily mean that somebody else is worse off.

So, what we have is a scenario in which Two-Face and Mr. Freeze teamed up and were successful (for some reason). Now it would benefit both of them to continue working together, but neither of them will actually do so. Hence they'll walk away with less than what they could have. As the Prisoner's Dilemma demonstrates, Nash Equilibria are not necessarily Pareto Optima. It's sort of funny to think about, actually. Batman can still claim a small victory even in his death.

share on: del.icio.us digg reditt su