by Filip Palda
This is why the solution of such two-person conflicts is called a “saddle-point”. At this point neither Moriarty nor Holmes have any incentive to deviate from their strategies given their expectations of what the other’s strategy will be. To do so would be to expose oneself to a greater downside risk than at the saddlepoint. Each in a way has insulated himself from the other by seeking refuge in strategy that utterly minimizes the downside the other can impose on him. Not only is this strategy an equilibrium, but it is also a self-fulfilling equilibrium in an average, or expected sense. Each man’ strategy settles at a point where the outcome he expects from his strategy is consistent with what the outcome is expected to be in a statistical sense.
If the payoffs were somewhat less symmetric than in this example, with the greatest possible loss to Holmes in pure strategies being from getting off at Dover, then you might find Holmes’ minimax probability of getting off at Canterbury as being perhaps 60% and that of Moriarty as being 40%, but this really just an aside that need not derail us as it were from the point of this exposition. The point being that equilibrium in this game emerges from payoffs and preferences, the view each of Holmes and Moriarty have of how the other plays the game, and the possibilities for randomizing your play.
Having just scaled one of the greatest intellectual tours-de-force of the social sciences a breather is called for in which we gaze over the landscape we have traversed. In the death chase there is a clear set of rewards and losses, players that have well-defined preferences, and an equilibrium concept. In the death chase this type of interaction will lead to strategies such that each player has the same expected payoff no matter the station of egress. The word “expectation” here is used in a mathematical sense. Getting off at a station has two possible payoffs. The expected value of these payoffs is the sum of each multiplied by its probability. Having the same expected payoff no matter what others plan is the consequence of strategies geared toward avoiding the worst possible outcomes in an average sense.
The minimax theorem
JOHN VON NEUMANN proved in 1928 that games such as the death chase have an equilibrium in mixed strategies and showed how to calculate the probabilities each player uses to determine his or her move. More generally, he proved that any two-player game in which the payoffs were of a zero-sum or constant-sum nature, and in which players had minimax preferences, had an equilibrium of the sort that no player had any incentive to change his or her strategy given his or her expectations of the other player’s strategies. This is the fundamental theorem of game theory and arguably one of the great intellectual accomplishments of the social sciences.
While this reasoning dazzled game theorists, it rested on an unusual view of how people interact. In von Neumann’s world, people play games as if they understand his theory and bow to it. One of the most difficult and subtle parts of von Neumann’s analysis is that even though players decide their strategies before the game starts, without knowing what the others will do, knowing the rules of the game and others’ preferences in effect allows each player to divine the mixed strategies of others. There is no direct interaction between the players, and they do not have the chance to learn from experience because the game is one-shot. If that were not strange enough, a one-shot game can have many different stages at which players move simultaneously, not in reaction to what the others do, but in reaction to what the others were anticipated to do before the game even started. Even with many stages each player could write down his or her strategy for every contingency, mail this in to the referee, and wait to hear whether he or she had won or lost.
The equilibrium from this one-shot game represents a set of strategies for which it is not profitable for any player to change his or her planned game given the anticipated strategies of the others. So knowledge of what others might do arises out of people knowing not only how the game is played, but how equilibrium emerges. More technically, knowledge of other people’s strategies is “endogenous” to the model. The endogeneity of expectations about other people’s behavior means that equilibrium is on average self-fulfilling. If it were not, people would change their strategies to exploit what they believe are incorrect views held by others. As Myerson explains, “… by his emphasis on max-min values, von Neumann was implicitly assuming that any strategy choice for a player or coalition should be evaluated against the other players’ rational response, as if the others could plan their response after observing this strategy choice” (1999, 1072). This non-stop rumination about other peoples’ strategies is what leads everyone to converge to mixed strategies such that their anticipations of the game’s outcome are in line with what that outcome will be on average.
The self-fulfilling nature of equilibrium remains one of the most troubling aspects of game theory. Equally troubling is von Neumann’s proof that at least one equilibrium mixed strategy exists for every two-person zero-sum game with minimax preferences (mixed strategies involve people throwing dice to decide their moves). It was also possible that multiple equilibria might exist and that researchers could not tell which one people would choose. Von Neumann bought the certainty of equilibrium at the price of admitting randomness in the strategies of the players. The only path to a certain strategy, or strategies in his model was to admit an uncertain outcome. It became curiouser and curiouser.
The Nash Supremacy
WHEN VON NEUMANN was developing game theory the field was moving too quickly for people to be worried about subtleties such as multiple equilibria. Early researchers, those from the dark ages of game theory, wanted to prove there always would be an equilibrium to games of the most varied sort. What the games were saying about real-life problems was of less interest to them than proving that solutions to such games existed. Mathematical reasoning reigned. Economics was relegated to a corner in the sense that integrating game theory into current economic models was a subject of intense neglect.
Von Neumann was only able to prove that at least one mixed equilibrium would exist for zero-sum, two person non-cooperative games. Remarkable as his analysis was, it did not really cover much ground. A few years later John Nash proved that minimax preferences and zero-sum rewards were not needed to prove the existence of equilibrium. There was always an equilibrium mixed strategy for any game, be it non-zero-sum or games in which the outcome could favor both players, or so called “non-constant-sum non-cooperative games”, and for any preferences.
His result was held to be revolutionary, but in fact it followed from a very simple, very clever restatement of the von Neumann problem. The key to Nash’s ability to prove existence far more generally than von Neumann lay in his definition of equilibrium. According to Nash (1951, 287) “an equilibrium point is an n-tuple such that each player’s mixed strategy maximizes his payoff if the strategies of the others are held fixed. Thus each player’s strategy is optimal against those of the others.” This is the most important two line passage written in the social sciences. It has been paraphrased and reparaphrased much as the theme song from Casablanca. What it boils down to is that if everyone believes that his or her actions cannot be changed to improve his or her wellbeing given the actions of all others, then we have Nash equilibrium.
Just putting the problem in this framework allowed Nash to employ a high-powered mathematical tool called Kakutani’s fixed point theorem in his 1950 paper, and a variant upon it in his 1951 paper called Brouwer’s fixed point theorem to prove that there had to exist at least one set of mixed strategies that mapped back into themselves for non zero-sum games, namely, a set of strategies that did not call for a shift in strategies that could improve payoffs.
The fixed point theorem was a natural way of proving this because it showed how a continuous mapping of a surface into itself always has a fixed point. In nature, wind is a continuous transformation of the atmosphere from one part of the earth’s surface back to another part of that surface. Wind shifts molecules of air in a flowing manner from some position on the earth back into another position. This is the meaning of a contin
uous mapping of a surface onto itself. The fixed point property of such a transformation explains the fact that the wind cannot be blowing in different directions all over the earth. There has to be at least one point of calm on the globe from which the wind starts to take direction.
By adopting mixed strategies, people transform a limited set of options based on coarse pure strategies (an aggressive advertising campaign; a friendly campaign) into an infinity of options based on subtle gradations of probability (a campaign that could be aggressive or friendly with an infinite number of different probabilities). This is what produces a continuous mapping of strategies into other strategies, and this extravagant widening of options is ultimately where an equilibrium, or a fixed point, is to be found.
Hunting for stag
DESPITE THE ELEGANCE of the Nash proof it is not really clear that he added anything conceptually to von Neumann’s formulation of the basic game equilibrium concept. What we were left with was an unusual way of looking at how people interact and an unintuitive master proof guaranteeing that if they did as theorists said they should a mixed equilibrium would be guaranteed to exist. It was not a guide to finding equilibria, but merely an assurance they would exist. And it suffered from the von Neumann assumption that people would play the game according to the analysts notion of how it should be played. What might happen if Holmes had not read Nash’s memo and had simply fallen asleep on the train? This was never considered in the theory.
The result of this first round in the development of game theory was a mix of enthusiasm and reticence. Mathematicians respected the Nash-von Neumann results. Economists did not understand the maths and were distressed by the tendency of Nash equilibria to proliferate. For instead of pulling a single rabbit out of a Nash equilibrium hat, game theorists sometimes pulled a rabbit, a guinea pig, and a rat—so-called multiple equilibria. Game theory can be either a miserly or a promiscuous generator of equilibria. That is undesirable from the practitioner’s point of view because it means the theory either can determine nothing or determines so many possibilities as to be useless as a guide to what the outcome of a game will be.
The parable of the stag hunt, first described by Jean-Jacques Rousseau, shows what is troubling about multiple Nash equilibria. Two hunters, Brimoche and Rompenil, wait quietly behind a bush for a stag to show up. Both must cooperate and pounce together or the stag escapes. Yet after a long wait, with still no stag in sight but one suspected to be lurking in the distance, both at the same time observe the chance to each catch one of two rabbits. Each can individually catch a less nutritionally satisfying rabbit, but if only one hunter does so while the other maintains his watch, the stag in the distance is alerted by the commotion and escapes. The one who waited then gets neither rabbit nor stag.
Here we have a classic simultaneous game in which the rewards are not zero-sum but allow some scope for concerted action based on mutual interest. From Brimoche’s perspective, waiting to catch the stag if he expects Rompenil to go for the rabbit is not a Nash strategy because he ends up with an empty belly, whereas he could increase his payoff by also catching a rabbit.
The same reasoning is true for Brimoche. So that leaves two possible Nash equilibria in pure, that is, non-random, strategies. If Brimoche expects Rompenil to focus on the stag, then his Nash strategy is also to focus on the stag. He cannot improve his outcome by deviating from this strategy. If Brimoche expects Rompenil to hunt rabbit, then he too must hunt rabbit, and again this is a Nash strategy because deviating from it will worsen his condition by landing him with an empty belly.
There is actually a third, randomized Nash equilibrium which we do not really need to illustrate to make the point. And this point is that the cast-iron logic of Nash equilibrium makes many people want to scream in frustration at being the mental captives of so fine a theory. We want to shout at these hunters from our ivory tower and tell them to cooperate. Doing so allows them to bag the biggest game. It is even a Nash equilibrium! But what can we say when the hunters call back that chasing rabbit is also a Nash equilibrium and they are stuck in it? We must draw the curtains and remain mute. For by itself the Nash equilibrium concept is not able to say which pure equilibrium will be observed. It can only say that both are viable because each is a situation in which deviating from the strategy lowers one’s payoffs given what one expects the other to do.
The Schelling Point
THE INABILITY OF the Nash equilibrium concept to rule out equilibria that were clearly inferior to all parties suggested that Nash equilibrium was a necessary but not sufficient condition for how games would play out. What was this sufficient condition? Among the first to propose an answer was Thomas Schelling, who in 1960 published a highly readable, non-mathematical treatise entitled The Strategy of Conflict. He suggested that when there are two or more Nash equilibria possible, and one is clearly better than the others for all involved, then people should place their hope in a “focal point” that allows them to coordinate their behavior in a way that guides them to the superior solution. The problem in the stag hunt game was one of expectations. If you had a dim expectation of your fellow man or woman, and he or she had the same of you, then you could all settle into an inferior equilibrium. But if you both believed in the village elder’s sermon about the duty to be cooperative and helpful, then you could coordinate your actions around this belief to achieve a superior result. Focal points in the stag hunt throw some light on why societies in which the two main groups of citizens are deeply divided can, through some leap of faith, or belief in a wise man or woman, move almost overnight from an inferior Nash equilibrium to a superior one. Nelson Mandela’s transformation of South Africa from apartheid to democracy in 1992 comes to mind.
This kind of reasoning has an immediate and intuitive appeal. How many of us have not sensed upon driving from the small town to the big city that we have left behind a certain culture of driving and entered a different culture? Traffic situations resemble games in which simultaneous choices have to be conditioned on our expectations of what others will do. In the small town, a Schelling focal point may attract people to cooperative solutions, while in the large city the focal point may be one of disregard for others. The same person, transplanted from one setting to the other, will have to rationally change his or her behavior in response to the closest focal point. The function of the focal point in each case is that it gives people some means of coordinating their behavior based purely on expectations and not upon any communication or commitment mechanism such as a contract.
If we consider society as a collection of people in need of some efficient way of coordinating their actions, then the challenge becomes that of moving to ever more efficient focal points. These thoughts can be applied to a comparison of the US and Europe. As trivial as it may sound, the US is united by focal points such as baseball, hotdogs, and American English. Europe, which is of similar size, had focal points of such variety and number that in the 20th century it gained the dubious honour of being the most ultra-violent, racist, genocidal society in history. The recent calm that has befallen that continent is perhaps due to post-war efforts to create broad focal points such as a common market, a common currency, a common soccer league, and the Eurovision song contest. Whether these attempts at homogenization are successful, or a return is made to older, less appealing focal points is a question haunting the policies of France and Germany, the main architects of Europe’s present stability.
So how do you move from a bad focal point to a good one? In Myerson’s view “pathological social expectations can be changed only by someone who is perceived as an authority or leader and who can identify a better Nash equilibrium for them” (2009, 1114). The challenge here is that everyone has to accept that the leader is properly identifying the Nash equilibria. If we go with Schelling’s way of solving the problem of multiple Nash equilibria, we are reaching into an old philosophical bag of tricks. Plato had explained the need for wise men who could perceive the fundamental forms of reality ly
ing below the surface appearance of things. The ordinary flock of mortals would then rally around these super-sensory paragons. Myerson’s essay in honour of Schelling expounds on this point and even suggests that oracles interpreting divine messages can act as focal points (2009, 1116). I kid thee not.
Subgame perfection
SCHELLING’S CRACKER-BARREL SOLUTION to multiple Nash equilibria failed to impress John Harsanyi and Reinhard Selten, who eventually shared the first Nobel Prize for game theory with Nash in 1994. They may have been troubled, if not appalled, by the fix Schelling was proposing for perceived deficiencies in the Nash program. Instead of assuming some focal point for all their theoretical problems, they wanted to probe Nash’s austere generalizations to see if, by thinking inside the box Nash had built, a technique for eliminating bad equilibria might not be found. They wanted to work within the frontiers of the theory and not assume the deus ex machina of a focal point. Schelling was then, and still remains, an outsider to the game theory purists who insist that equilibrium solutions to games must follow from the theory and not be imposed upon it from without.
Part of the problem giving rise to multiple Nash equilibria was that some games had to be played over stages. There is a first move, a second move, and so on. Von Neumann, and later Nash, showed that we could compress all such moves into a “strategy” that could be determined even before the game had started to be played. This made extended games look like one-shot games. In a strict technical sense, they were, because under the von Neumann-Nash approach, no player learned anything new about the other player at intermediate stages. Knowing the way the game was played, the incentives, and how equilibrium worked, each player could figure out all the possibilities beforehand, send in their moves by mail to an arbiter and pay the fine or collect the reward at the end. In such multi-stage games you might find absurd Nash equilibria similar to those we discussed in the one-stage stag hunt game.
