Game Theory

Game Theory Parables for Game Designers

The Emergence of Modern Game Theory

Game Theory, as an official academic discipline, arguably began in 1944 with the publication of “Theory of Games and Economic Behaviour” by John von Neumann and Oskar Morgenstern.  Like many disciplines, though, its roots trace much deeper, and it is only after sufficient development that these roots become apparent.

The theory developed in von Neumann and Morgenstern’s massive text has a reputation for being very militaristic — think Dr. Strangelove.  Game Theory was, and sometimes still is, seen as a tool for analyzing conflict situations, and the tone of that analysis often appears cold, calculating, and impersonal.  This is because a lot of Game Theory was done in service of the Cold War, with the omnipresent threat of mutually assured destruction being a common topic in Game Theory discussions.

Why did a mathematical theory get so entangled with this Cold War mentality?  It certainly didn’t help that von Neumann was also involved in the Manhattan Project, but the theory itself focused on a kind of game that is conflict-oriented.

A Zero Sum Game is a game where one player’s loss is identical to the players’ gain: if player one gains 10 points, player two loses 10 points.  Hence, the sum of both outcomes is zero: players are fighting over a common set of points, where no new points are created or destroyed.  Area control games are common examples of this, where one players’ territorial gains are the other players’ losses.

von Neumann and Morgenstern investigated the question of how players should act when involved in a zero sum game.  Remember that, as a game, the outcome is determined by the strategically independent choices of both players, so each player has to think about what their opponent will do in order to decide what they will do.

A conservative player may think about the worst possible outcomes that they could get from each of their strategies, and then choose the strategy that gives the highest of the worst possible outcomes.  This is called the Maximin strategy as it seeks to MAXImize the MINimum outcome that the player can receive.  Maximin is motivated by loss aversion, and is appealing because it provides a guaranteed minimum outcome.  Depending on what the other player does, a maximin player can never do worse than this outcome, and they may even do better.

A punitive player may instead seek to punish the other player, to inflict the maximum penalty that they can, knowing that the other players’ losses are their gains.  This motivates the Minimax strategy where a player looks at the best possible outcomes that the other player could get from each of their strategies, and then chooses the strategy that MINImizes the MAXimum payoff for that player.  In other words, a minimax player looks to see the best possible outcomes for the other player, and then chooses the strategy that gives them the lowest of the best possible outcomes.

What von Neumann and Morgenstern proved is that, when playing a Zero Sum Game, the Maximin and the Minimax strategies lead to the exact same outcome for the game.  If a player is trying to stem their losses (playing Maximin) they are also, at the same time, trying to cap the other players’ gains (playing Minimax).  This is because, in a zero sum game, the losses of one player are the gains of the other.  The same is true for the other player, who knows that their opponent is trying to Minimax them, so they want to counter by playing their Maximin strategy, which in turn is the same as Minimaxing their opponent.  

The end result, and this is a pretty big result in the history of Game Theory, is that the Maximin and the Minimax strategies lead to the same outcome, and that this outcome is unique for that game.  In other words, there is a unique value such that players playing their Maximin/Minimax strategies can do no better than this value by unilaterally changing their strategy.  This value, assuming it is non-zero, will be positive/gains for one player, and negative/losses for the other.

von Neumann and Morganstern showed that, in every two-player zero-sum game of pure conflict, there is a unique value for the game such that neither player can do better by unilaterally deviating from their Maximin/Minimax strategy.  This is the outcome of the game that rational players will arrive at, so in a very strong sense it can be called the solution to the game.

Mathematicians love it when there are unique solutions for mathematical problems.  This, coupled with the Cold War zeitgeist that emerged just after this book was written, shaped the thinking about game theory for years to come.  Major research efforts were devoted to this sort of question: how can one side of a conflict maximize their gains (= the other side’s losses) while minimizing their own losses (= the other side’s gains).  The focus was on finding maximally efficient strategies that sought only to get the best outcome possible, and to inflict as much harm as possible to the other side.  This spectre of thought loomed large over Game Theory, and even today it helps to explain why some people have such negative reactions to Game Theory’s analysis of the Prisoner’s Dilemma.  The cold, calculating attitude of the Cold War game theorists is sometimes taken to be the reason why mutual cooperation is not the solution of the Prisoner’s Dilemma.

A few short years after the publication of Theory of Games and Economic Behaviour, the mathematician John Nash published, in 1951, a two-page paper that presented the concept of a Nash Equilibrium.  For any game, a Nash Equilibrium is a pair of strategies (one for each player) such that neither player can increase their payoff by unilaterally changing their strategy.  Nash proved that each and every two-player game has at least one Nash Equilibrium.

In a zero-sum game, the unique solution found through maximin/minimax is a Nash Equilibrium, since neither player can do better by changing their strategy.  So far, Nash’s work is in line with the results of von Neumann & Morgenstern.

Two lines of thought diverge when non-zero-sum games are involved, though.  In the Action Selection game from earlier, there are two different Nash Equilibrium: mutual Develop, and mutual Export.  These Equilibrium points have very different values as well, unlike a zero-sum game.

Some theorists reacted to this by rejecting Nash Equlibrium as a solution: “how can a game have multiple, different solutions?”  This line of thought assumed that every game must have a  single, rational solution: a set of instructions to tell each player what to do to get the very best outcome of the game they can.  Thinking this way means rejecting the concept of a Nash Equilibrium, and/or rejecting the whole class of non-zero-sum games because they don’t conform to these rational expectations.  

Another line of thought sees real value in analyzing non-zero-sum games like this Action Selection game, or the Stag Hunt, or even the Prisoner’s Dilemma, because those are the types of situations that people encounter in real social interactions.  The existence of multiple, unequal solutions (or even facts like the impossibility of cooperation in the Prisoner’s Dilemma) are not bugs of the theory, but features.  They reveal genuinely interested aspects of social interactions, and their study can be far more fruitful than the straightforward min-maxing found in the study of two-player, zero-sum games of pure conflict.

Under this expanded definition, Game Theory began to study these more interesting social interactions, games that are of interest to economists, philosophers, scientists, and yes, even game designers, because of the unique situations they represent.  With the concept of a Nash Equilibrium in hand, Game Theorists saw that many other thinkers across many other disciplines had actually been doing this sort of Game Theory all along — they just didn’t have a name for it.

In 1838, the mathematician Antoine Augustin Cournot wrote Researches on the Mathematical Principles of the Theory of Wealth, one of the first texts to apply mathematics to economics.  In it, he considered the situation of two companies that supplied spring water to a market.  How much should each company supply, given that they want to maximize their own profits, but also that the price of the good is determined by the supply from the other company as well.  Through mathematical analysis, Cournot was able to show that there is a unique equilibrium point where each company is maximizing their profits given the behaviour of the other.  In his words:

“The state of equilibrium … is therefore stable; i.e. if either one of the producers, misled as to his true interest, leaves it temporarily, he will be brought back to it”

This is the same idea behind a Nash Equilibrium, appearing in this special case over 100 years before it was to be formally defined.

In 1651, the philosopher Thomas Hobbes wrote Leviathan, a massive treatise in political philosophy.  Amongst many other topics, Hobbes considers the problem of social cooperation: how can people come to trust each other enough to work together on a larger project?  There is always the incentive for one player, after having received the benefits of another’s work, to abandon their end of the bargain and essentially get the others’ labour for free.  But the other players know this as well — they know that others cannot be trusted, so they do not offer to cooperate in the first place.  Without cooperation, humans are left in a world where life will be “solitary, poor, nasty, brutish and short.” 

Hobbes has essentially outlined the problem of the social contract, of how people can agree to mutually cooperate despite the ever-present temptation of defection.  This has the structure of the Stag Hunt, where players always have a risk-dominant option: remain in the status quo and be guaranteed a certain outcome (no matter how nasty that outcome happens to be).  Working together with others is risky, as the others may not reciprocate; and a player who commits cooperate while no one else does suffers great losses.  Hobbes’ proposed solution to this is tyranny, the creation of an all powerful government who can inflict unavoidable penalties on anyone who breaks their promises.

David Hume, it should be noted, faced the same problem of social cooperation.  Instead of arguing in favour of a tyrant, Hume thought that cooperation could arise through reciprocity.  In his Treatise on Human Nature (1739) he writes:

“Hence I learn to do a service to another, without bearing him any real kindness; because I foresee, that he will return my service, in expectation of another of the same kind, and in order to maintain the same correspondence of good offices with me and others”

This idea, sometimes known as “The Shadow of the Future,” or as Reciprocal Altruism, underlines a very different approach to social contract theory, one that is also supported by Game Theory.

In Shakespeare’s Henry V (written circa 1599), there is a scene in the Battle of Agincourt where King Henry decides to slaughter his French prisoners in front of the enemy.  This is, from a modern Game Theoretic point of view, a clever bit of strategy.  Henry’s troops see that all of the prisoners have been killed, and they see that the French see that all of the prisoners have been killed.  These troops know, then, the fate that awaits them if they are captured, and are therefore inspired to fight as bravely as they possibly can.

A similar situation happened in Cortés’ conquest of the Aztec empire in 1519.  When preparing to attack Veracruz, Cortés noted that his forces were greatly outnumbered by the Aztecs and was afraid of the possibility that they would retreat from this losing cause.  To prevent this, Cortés burned the ships on which his invaders arrived, thus trapping his army on the Mexican coastline.  With the option of retreat removed for them, his troops had no choice but to fight as best as they possibly can to avoid defeat.  The Aztecs, in turn, saw that Cortés had destroyed his fleet.  They realized that his troops were left with only one option, so they had to decide whether or not to fight this highly motivated force of Spanish troops.  They retreated to the surrounding hills, and Cortés easily took Veracruz.  

This example demonstrates a somewhat counterintuitive result of Game Theory, that sometimes it is in a players’ interest to limit their options.

These examples, from Cournot, Hobbes, Shakespeare and Cortés, show that Game Theoretic reasoning has been around for a long time before the discipline was formalized.  Nash’s definition of Equilibrium allowed for the strategic insights in these examples to be brought to light and studied analytically, showing the rationality of the reasoning involved.

Sam HillierComment