Main Game Theory: A Very Short Introduction
Game Theory: A Very Short IntroductionKen Binmore
Games are everywhere: Drivers maneuvering in heavy traffic are playing a driving game. Bargain hunters bidding on eBay are playing an auctioning game. The supermarket's price for corn flakes is decided by playing an economic game. This Very Short Introduction offers a succinct tour of the fascinating world of game theory, a ground-breaking field that analyzes how to play games in a rational way. Ken Binmore, a renowned game theorist, explains the theory in a way that is both entertaining and non-mathematical yet also deeply insightful, revealing how game theory can shed light on everything from social gatherings, to ethical decision-making, to successful card-playing strategies, to calculating the sex ratio among bees. With mini-biographies of many fascinating, and occasionally eccentric, founders of the subject--including John Nash, subject of the movie A Beautiful Mind--this book offers a concise overview of a cutting-edge field that has seen spectacular successes in evolutionary biology and economics, and is beginning to revolutionize other disciplines from psychology to political science.
You may be interested in
Most frequently terms
Game Theory: A Very Short Introduction VERY SHORT INTRODUCTIONS are for anyone wanting a stimulating and accessible way in to a new subject. They are written by experts, and have been published in more than 25 languages worldwide. The series began in 1995, and now represents a wide variety of topics in history, philosophy, religion, science, and the humanities. Over the next few years it will grow to a library of around 200 volumes – a Very Short Introduction to everything from ancient Egypt and Indian philosophy to conceptual art and cosmology. Very Short Introductions available now: AFRICAN HISTORY THE HISTORY OF AMERICAN POLITICAL ASTRONOMY MichaelHoskin ATHEISM Julian Baggini PARTIES AND ELECTIONS L. Sandy Maisel THE AMERICAN AUGUSTINE Henry Chadwick BARTHES Jonathan Culler BESTSELLERS John Sutherland PRESIDENCY Charles O. Jones ANARCHISM Colin Ward ANCIENT EGYPT Ian Shaw THE BIBLE John Riches THE BRAIN Michael O’Shea BRITISH POLITICS John Parker and Richard Rathbone ANCIENT PHILOSOPHY Julia Annas ANCIENT WARFARE Harry Sidebottom ANGLICANISM Mark Chapman THE ANGLO-SAXON AGE Anthony Wright BUDDHA Michael Carrithers BUDDHISM Damien Keown BUDDHIST ETHICS Damien Keown CAPITALISM James Fulcher ANIMAL RIGHTS DavidDeGrazia Antisemitism Steven Beller THE CELTS Barry Cunliffe CHAOS Leonard Smith CHOICE THEORY ARCHAEOLOGY Paul Bahn ARCHITECTURE CHRISTIAN ART John Blair Andrew Ballantyne ARISTOTLE Jonathan Barnes ART HISTORY Dana Arnold ART THEORY Cynthia Freeland Michael Allingham Beth Williamson CHRISTIANITY Linda Woodhead CLASSICS Mary Beard and John Henderson CLASSICAL MYTHOLOGY Helen Morales CLAUSEWITZ Michael Howard THE COLD WAR Robert McMahon CONSCIOUSNESS Susan Blackmore CONTEMPORARY ART Julian Stallabrass CONTINENTAL PHILOSOPHY THE ELEMENTS Philip Ball EMOTION Dylan Evans EMPIRE Stephen Howe ENGELS Terrell Carver ETHICS Simon Blackburn THE EUROPEAN UNION John Pinder EVOLUTION Brian and Deborah Charlesworth COSMOLOGY Peter Coles EXISTENTIALISM Thomas Flynn FASCISM Kevin Passmore FEMINISM Margaret Walters THE CRUSADES THE FIRST WORLD WAR Simon Critchley Christopher Tyerman CRYPTOGRAPHY Fred Piper and Sean Murphy DADA AND SURREALISM David Hopkins DARWIN Jonathan Howard THE DEAD SEA SCROLLS Timothy Lim Michael Howard FOSSILS Keith Thomson FOUCAULT Gary Gutting THE FRENCH REVOLUTION William Doyle FREE WILL Thomas Pink FREUD Anthony Storr FUNDAMENTALISM DEMOCRACY Bernard Crick DESCARTES Tom Sorell GALILEO Stillman Drake DESIGN John Heskett DINOSAURS David Norman DOCUMENTARY FILM Game theory Ken Binmore GANDHI Bhikhu Parekh GEOPOLITICS Klaus Dodds Patricia Aufderheide Malise Ruthven GLOBAL CATASTROPHES DREAMING J. Allan Hobson DRUGS Leslie Iversen GLOBALIZATION THE EARTH Martin Redfern ECONOMICS Partha Dasgupta GLOBAL WARMING EGYPTIAN MYTH Geraldine Pinch EIGHTEENTH-CENTURY BRITAIN Paul Langford Bill McGuire Manfred Steger Mark Maslin THE GREAT DEPRESSION AND THE NEW DEAL Eric Rauchway HABERMAS James Gordon Finlayson HEGEL Peter Singer MACHIAVELLI Quentin Skinner THE MARQUIS DE SADE John Phillips HEIDEGGER Michael Inwood HIEROGLYPHS Penelope Wilson HINDUISM Kim Knott MARX Peter Singer MATHEMATICS HISTORY John H. Arnold HOBBES Richard Tuck HUMAN EVOLUTION MEDICAL ETHICS Tony Hope MEDIEVAL BRITAIN Bernard Wood HUMAN RIGHTS Andrew Clapham HUME A. J. Ayer IDEOLOGY Michael Freeden INDIAN PHILOSOPHY Timothy Gowers John Gillingham and Ralph A. Grifﬁths MODERN ART David Cottington MODERN IRELAND Senia Pašeta MOLECULES Philip Ball INTELLIGENCE Ian J. Deary MUSIC Nicholas Cook MYTH Robert A. Segal NATIONALISM Steven Grosby INTERNATIONAL MIGRATION Khalid Koser INTERNATIONAL THE NEW TESTAMENT AS LITERATURE Kyle Keefer NEWTON Robert Iliffe RELATIONS Paul Wilkinson ISLAM Malise Ruthven JOURNALISM Ian Hargreaves NIETZSCHE Michael Tanner NINETEENTH-CENTURY BRITAIN Christopher Harvie JUDAISM Norman Solomon JUNG Anthony Stevens KABBALAH Joseph Dan NORTHERN IRELAND KAFKA Ritchie Robertson KANT Roger Scruton KIERKEGAARD Patrick Gardiner PARTICLE PHYSICS Frank Close PAUL E. P. Sanders PHILOSOPHY Edward Craig THE KORAN Michael Cook LINGUISTICS Peter Matthews PHILOSOPHY OF LAW LITERARY THEORY PHILOSOPHY OF SCIENCE Sue Hamilton Jonathan Culler and H. C. G. Matthew Marc Mulholland Raymond Wacks Samir Okasha LOCKE John Dunn PHOTOGRAPHY Steve Edwards LOGIC Graham Priest PLATO Julia Annas POLITICS Kenneth Minogue POLITICAL PHILOSOPHY David Miller POSTCOLONIALISM Robert Young POSTMODERNISM Christopher Butler POSTSTRUCTURALISM Catherine Belsey PREHISTORY Chris Gosden PRESOCRATIC PHILOSOPHY Catherine Osborne PSYCHOLOGY Gillian Butler and Freda McManus PSYCHIATRY Tom Burns QUANTUM THEORY John Polkinghorne RACISM Ali Rattansi THE RENAISSANCE Jerry Brotton RENAISSANCE ART Geraldine A. Johnson ROMAN BRITAIN Peter Salway THE ROMAN EMPIRE Christopher Kelly ROUSSEAU Robert Wokler RUSSELL A. C. Grayling RUSSIAN LITERATURE Catriona Kelly THE RUSSIAN REVOLUTION S. A. Smith SCHIZOPHRENIA Chris Frith and Eve Johnstone SCHOPENHAUER Christopher Janaway SHAKESPEARE Germaine Greer SIKHISM Eleanor Nesbitt SOCIAL AND CULTURAL ANTHROPOLOGY John Monaghan and Peter Just SOCIALISM Michael Newman SOCIOLOGY Steve Bruce SOCRATES C. C. W. Taylor THE SPANISH CIVIL WAR Helen Graham SPINOZA Roger Scruton STUART BRITAIN John Morrill TERRORISM Charles Townshend THEOLOGY David F. Ford THE HISTORY OF TIME Leofranc Holford–Strevens TRAGEDY Adrian Poole THE TUDORS John Guy TWENTIETH-CENTURY BRITAIN Kenneth O. Morgan THE VIKINGS Julian Richards WITTGENSTEIN A. C. Grayling WORLD MUSIC Philip Bohlman THE WORLD TRADE ORGANIZATION Amrita Narlikar Available soon: Expressionism Katerina Reed–Tsocha Galaxies John Gribbin Geography John Matthews and David Herbert Memory Jonathan Foster Modern China Rana Mitter Nuclear Weapons Joseph M. Siracusa German Literature HIV/AIDS Alan Whiteside Quakerism Pink Dandelion Science and Religion Thomas Dixon The Meaning of Life Sexuality Nicholas Boyle Terry Eagleton Véronique Mottier For more information visit our web site www.oup.co.uk/general/vsi/ Ken Binmore Game Theory A Very Short Introduction 1 1 Great Clarendon Street, Oxford ox2 6dp Oxford University Press is a department of the University of Oxford. It furthers the University’s objective of excellence in research, scholarship, and education by publishing worldwide in Oxford New York Auckland Cape Town Dar es Salaam Hong Kong Karachi Kuala Lumpur Madrid Melbourne Mexico City Nairobi New Delhi Shanghai Taipei Toronto With ofﬁces in Argentina Austria Brazil Chile Czech Republic France Greece Guatemala Hungary Italy Japan Poland Portugal Singapore South Korea Switzerland Thailand Turkey Ukraine Vietnam Oxford is a registered trade mark of Oxford University Press in the UK and in certain other countries Published in the United States by Oxford University Press Inc., New York c Ken Binmore 2007 The moral rights of the author have been asserted Database right Oxford University Press (maker) First Published as a Very Short Introduction 2007 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission in writing of Oxford University Press, or as expressly permitted by law, or under terms agreed with the appropriate reprographics rights organization. Enquiries concerning reproduction outside the scope of the above should be sent to the Rights Department, Oxford University Press, at the address above You must not circulate this book in any other binding or cover and you must impose the same condition on any acquirer British Library Cataloguing in Publication Data Data available Library of Congress Cataloging in Publication Data Data available ISBN 978–0–19–921846–2 10 9 8 7 6 5 4 3 2 1 Typeset by SPI Publisher Services, Pondicherry, India Printed in Great Britain on acid-free paper by Ashford Colour Press Ltd, Gosport, Hampshire To Peter and Nina This page intentionally left blank Contents List of illustrations xiii 1 The name of the game 1 2 Chance 22 3 Time 36 4 Conventions 57 5 Reciprocity 71 6 Information 88 7 Auctions 102 8 Evolutionary biology 117 9 Bargaining and coalitions 140 10 Puzzles and paradoxes 158 References and further reading 175 Index 181 This page intentionally left blank List of illustrations 1 Matching Pennies 4 12 Cosy Kidnap 46 2 Payoff tables 5 13 Ultimatum Minigame 49 3 Numerical payoffs 10 14 Evolutionary adjustment in the Ultimatum Minigame 50 4 Games with mixed motivations 11 5 James Dean 12 c 2004 TopFoto 6 John Nash 13 c Robert P. Matthews/Princeton University/Getty Images 7 Two versions of the Prisoner’s Dilemma 18 8 Rolling dice 24 c iStockphoto 9 Learning to play an equilibrium 28 10 Two board games 39 11 Kidnap 44 15 Simpliﬁed Chain Store paradox 53 16 David Hume 61 c Hulton Archive/Getty Images 17 Schelling’s Solitaire 63 18 Stag Hunt Game 69 19 Reciprocal grooming by chimps 74 c Peter Arnold Inc./Alamy 20 The folk theorem 77 21 Information sets for Matching Pennies 89 22 Full house 90 c iStockphoto 23 Maximin play in Von Neumann’s Poker model 91 31 Vampire bat 135 24 Von Neumann’s model 93 32 Hawk-Dove-Retaliator Game 137 c Michael and Patricia Fogden/Corbis 25 Payoff table for Von Neumann’s Poker model 94 33 The Nash bargaining solution 144 26 Incomplete information in Chicken 96 34 Transparent disposition fallacy 163 27 The Judgement of Solomon 105 35 Two attempts to satisfy Newcomb’s requirements 165 28 Going, Going, Gone! 108 c Hiu Yin Leung/Fotolia 29 Replicator dynamics in the Hawk-Dove Game 126 30 Relatives play the Prisoner’s Dilemma 131 36 Three midwestern ladies 168 Library of Congress, Prints and Photographs Division, FSA-OW1 Collection (reproduction no. LC-USF33-012381-M5 DLC) 37 Monty Hall Game 173 The publisher and the author apologize for any errors or omissions in the above list. If contacted they will be pleased to rectify these at the earliest opportunity. Chapter 1 The name of the game What is game theory about? When my wife was away for the day at a pleasant little conference in Tuscany, three young women invited me to share their table for lunch. As I sat down, one of them said in a sultry voice, ‘Teach us how to play the game of love’, but it turned out that all they wanted was advice on how to manage Italian boyfriends. I still think they were wrong to reject my strategic recommendations, but they were right on the nail in taking for granted that courting is one of the many different kinds of game we play in real life. Drivers manoeuvring in heavy trafﬁc are playing a driving game. Bargain-hunters bidding on eBay are playing an auctioning game. A ﬁrm and a union negotiating next year’s wage are playing a bargaining game. When opposing candidates choose their platform in an election, they are playing a political game. The owner of a grocery store deciding today’s price for corn ﬂakes is playing an economic game. In brief, a game is being played whenever human beings interact. Antony and Cleopatra played the courting game on a grand scale. Bill Gates made himself immensely rich by playing the computer software game. Adolf Hitler and Josef Stalin played a game that killed off a substantial fraction of the world’s population. Kruschev 1 and Kennedy played a game during the Cuban missile crisis that might have wiped us out altogether. Game Theory With such a wide ﬁeld of application, game theory would be a universal panacea if it could always predict how people will play the many games of which social life largely consists. But game theory isn’t able to solve all of the world’s problems, because it only works when people play games rationally. So it can’t predict the behaviour of love-sick teenagers like Romeo or Juliet, or madmen like Hitler or Stalin. However, people don’t always behave irrationally, and so it isn’t a waste of time to study what happens when people put on their thinking caps. Most of us at least try to spend our money sensibly – and we don’t do too badly much of the time or economic theory wouldn’t work at all. Even when people haven’t thought everything out in advance, it doesn’t follow that they are necessarily behaving irrationally. Game theory has had some notable successes in explaining the behaviour of spiders and ﬁsh, neither of which can be said to think at all. Such mindless animals end up behaving as though they were rational, because rivals whose genes programmed them to behave irrationally are now extinct. Similarly, companies aren’t always run by great intellects, but the market is often just as ruthless as Nature in eliminating the unﬁt from the scene. Does game theory work? In spite of its theoretical successes, practical men of business used to dismiss game theory as just one more ineffectual branch of social science, but they changed their minds more or less overnight after the American government decided to auction off the right to use various radio frequencies for use with cellular telephones. With no established experts to get in the way, the advice of game theorists proved decisive in determining the design of the rules of the auctioning games that were used. The result was that the 2 American taxpayer made a proﬁt of $20 billion – more than twice the orthodox prediction. Even more was made in a later British telecom auction for which I was responsible. We made a total of $35 billion in just one auction. In consequence, Newsweek magazine described me as the ruthless, Poker-playing economist who destroyed the telecom industry! Toy games Each new big-money telecom auction needs to be tailored to the circumstances in which it is going to be run. One can’t just take a design off the shelf, as the American government found when it hired Sotheby’s to auction off a bunch of satellite transponders. But nor can one capture all the complicated ins and outs of a new telecom market in a mathematical model. Designing a telecom auction is therefore as much an art as a science. One extrapolates from simple models chosen to mimic what seem to be the essential strategic features of a problem. I try to do the same in this book, which therefore contains no algebra and a minimum of technical jargon. It looks only at toy games, leaving aside all the bells and whistles with which they are complicated in real life. However, most people ﬁnd that even toy games give them plenty to think about. 3 The name of the game As it turned out, the telecom industry wasn’t destroyed. Nor is it at all ruthless to make the fat cats of the telecom industry pay for their licences what they think they are worth – especially when the money is spent on hospitals for those who can’t afford private medical care. As for Poker, it is at least 20 years since I played for more than nickels and dimes. The only thing that Newsweek got right is that game theory really does work when applied by people who know what they are doing. It works not just in economics, but also in evolutionary biology and political science. In my recent book Natural Justice, I even outrage orthodox moral philosophers by using game theory when talking about ethics. 1. Alice and Bob’s decision problem in Matching Pennies Conﬂict and cooperation Game Theory Most of the games in this book have only two players, called Alice and Bob. The ﬁrst game they will play is Matching Pennies. Sherlock Holmes and the evil Professor Moriarty played Matching Pennies on the way to their ﬁnal confrontation at the Reichenbach Falls. Holmes had to decide at which station to get off a train. Moriarty had to decide at which station to lie in wait. A real-life counterpart is played by dishonest accountants and their auditors. The former decide when to cheat and the latter decide when to inspect the books. In our toy version, Alice and Bob each show a coin. Alice wins if both coins show the same face. Bob wins if they show different faces. Alice and Bob therefore each have two strategies, heads and tails. Figure 1 shows who wins and loses for all possible strategy combinations. These outcomes are the players’ payoffs in the game. The thumbs-up and thumbs-down icons have been used to emphasize that payoffs needn’t be measured in money. Figure 2 shows how all the information in Figure 1 can be assembled into a payoff table, with Alice’s payoff in the southwest corner of each cell, and Bob’s in the northeast corner. It also shows a two-player version of the very different Driving Game that we 4 2. Payoff tables. Alice chooses a row and Bob chooses a column Von Neumann The ﬁrst result in game theory was John Von Neumann’s minimax theorem, which applies only to games like Matching Pennies in which the players are modelled as implacable enemies. One sometimes still reads dismissive commentaries on game theory in which Von Neumann is caricatured as the archetypal cold warrior – the original for Dr Strangelove in the well known movie. We are then told that only a crazed military strategist would think of applying game theory in real life, because only a madman or a cyborg would make the mistake of supposing that the world is a game of pure conﬂict. Von Neumann was an all-round genius. Inventing game theory was just a sideline for him. It is true that he was a hawk in the Cold War, but far from being a mad cyborg, he was a genial soul, who liked to party and have a good time. Just like you and me, he preferred cooperation to conﬂict, but he also understood that the 5 The name of the game play every morning when we get into our cars to drive to work. Alice and Bob again have two pure strategies, left and right, but now the players’ payoffs are totally aligned instead of being diametrically opposed. When journalists talk about a win-win situation, they have something like the Driving Game in mind. way to achieve cooperation isn’t to pretend that people can’t sometimes proﬁt by causing trouble. Cooperation and conﬂict are two sides of the same coin, neither of which can be understood properly without taking account of the other. To consider a game of pure conﬂict like Matching Pennies isn’t to claim that all human interaction is competitive. Nor is one claiming that all human interaction is cooperative when one looks at a game of pure coordination like the Driving Game. One is simply distinguishing two different aspects of human behaviour so that they can be studied one at a time. Game Theory Revealed preference To cope with cooperation and conﬂict together, we need a better way of describing the motivation of the players than simply saying that they like winning and dislike losing. For this purpose, economists have invented the idea of utility, which allows each player to assign a numerical value to each possible outcome of a game. In business, the bottom line is commonly proﬁt, but economists know that human beings often have more complex aims than simply making as much money as they can. So we can’t identify utility with money. A naive response is to substitute happiness for money. But what is happiness? How do we measure it? It is unfortunate that the word ‘utility’ is linked historically with Victorian utilitarians like Jeremy Bentham and John Stuart Mill, because modern economists don’t follow them in identifying utility with how much pleasure or how little pain a person may feel. The modern theory abandons any attempt to explain how people behave in terms of what is going on inside their heads. On the contrary, it makes a virtue of making no psychological assumptions at all. 6 We don’t try to explain why Alice or Bob behave as they do. Instead of an explanatory theory, we have to be content with a descriptive theory, which can do no more than say that Alice or Bob will be acting inconsistently if they did such-and-such in the past, but now plan to do so-and-so in the future. In game theory, the object is to observe the decisions that Alice and Bob make (or would make) when they aren’t interacting with each other or anyone else, and to deduce how they will behave when interacting in a game. With some mild assumptions, acting consistently can be shown to be the same as behaving as though seeking to maximize the value of something. Whatever this abstract something may be in a particular context, economists call it utility. It needn’t correlate with money, but it sadly often does. Taking risks In acting consistently, Alice may not be aware that she is behaving as though maximizing something we choose to call her utility. But if we want to predict her behaviour, we need to be able to measure her utility on a utility scale, much as temperature is measured on a thermometer. Just as the units on a thermometer are called degrees, we can then say that a util is a unit on Alice’s utility scale. The orthodoxy in economics used to be that such cardinal utility scales are intrinsically nonsensical, but Von Neumann fortunately 7 The name of the game We therefore don’t argue that some preferences are more rational than others. We follow the great philosopher David Hume in regarding reason as the ‘slave of the passions’. As he extravagantly remarked, there would be nothing irrational about his preferring the destruction of the entire universe to scratching his ﬁnger. However, we go even further down this road by regarding reason purely as an instrument for avoiding inconsistent behaviour. Any consistent behaviour therefore counts as rational. didn’t know this when Oskar Morgenstern turned up at his house one day complaining that they didn’t have a proper basis for the numerical payoffs in the book on game theory they were writing together. So Von Neumann invented a theory on the spot that measures how much Alice wants something by the size of the risk she is willing to take to get it. We can then ﬁgure out what choice she will make in risky situations by ﬁnding the option that will give her the highest utility on average. Game Theory It is easy to use Von Neumann’s theory to ﬁnd how much utility to assign to anything Alice may need to evaluate. For example, how many utils should Alice assign to getting a date with Bob? We ﬁrst need to decide what utility scale to use. For this purpose, pick two outcomes that are respectively better and worse than any other outcome Alice is likely to encounter. These outcomes will correspond to the boiling and freezing points of water used to calibrate a Celsius thermometer, in that the utility scale to be constructed will assign 0 utils to the worst outcome, and 100 utils to the best outcome. Next consider a bunch of (free) lottery tickets in which the only prizes are either the best outcome or the worst outcome. When we offer Alice lottery tickets with higher and higher probabilities of getting the best outcome as an alternative to a date with Bob, she will eventually switch from saying no to saying yes. If the probability of the best outcome on the lottery ticket that makes her switch is 75%, then Von Neumann’s theory says that a date with Bob is worth 75 utils to her. Each extra percentage point added to her indifference probability therefore corresponds to one extra util. When some people evaluate sums of money using this method, they always assign the same number of utils to each extra dollar. We call such people risk neutral. Those who assign fewer utils to each extra dollar than the one that went before are called risk averse. 8 Insurance Alice is thinking of accepting an offer from Bob to insure her Beverley Hills mansion against ﬁre. If she refuses his offer, she faces a lottery in which she ends up with her house plus the insurance premium if her house doesn’t burn down, and with only the premium if it does. This has to be compared with her ending up for sure with the value of the house less the premium if she accepts Bob’s offer. Notice that economists regard the degree of risk aversion that a person reveals as a matter of personal preference. Just as Alice may or may not prefer chocolate ice-cream to vanilla, so she may or may not prefer to spend $1,000 on insuring her house. Some philosophers – notably John Rawls – insist that it is rational to be risk averse when defending whatever alternative to maximizing average utility they prefer, but such appeals miss the point that the players’ attitudes to taking risks have already been taken into account when using Von Neumann’s method to assign utilities to each outcome. Economists make a different mistake when they attribute risk aversion to a dislike of the act of gambling. Von Neumann’s theory only makes sense when the players are entirely neutral to the actual act of gambling. Like a Presbyterian minister insuring his house, they don’t gamble because they enjoy gambling – they gamble only when they judge that the odds are in their favour. 9 The name of the game If it is rational for Bob to make the offer and for Alice to accept, he must think that the lottery is better than breaking even for sure, and she must have the opposing preference. The existence of the insurance industry therefore conﬁrms not only that it can be rational to gamble – provided that the risks you take are calculated risks – but that rational people can have different attitudes to taking risks. In the insurance industry, the insurers are close to being risk neutral and the insurees are risk averse to varying degrees. 3. Numerical payoffs Game Theory Life isn’t a zero-sum game As with measuring temperature, we are free to choose the zero and the unit on Alice’s utility scale however we like. We could, for example, have assigned 32 utils to the worst outcome, and 212 utils to the best outcome. The number of utils a date with Bob is worth on this new scale is found in the same way that one converts degrees Celsius into degrees Fahrenheit. So the date with Bob that was worth 75 utils on the old scale would be worth 167 utils on the new scale. In the toy games we have considered so far, Alice and Bob have only the outcomes WIN and LOSE to evaluate. We are free to assign these two outcomes any number of utils we like, as long as we assign more utils to winning than to losing. If we assign plus one util to winning and minus one util to losing, we get the payoff tables of Figure 3. The payoffs in each cell of Matching Pennies in Figure 3 always add up to zero. We can always ﬁx things to make this true in a game of pure conﬂict. Such games are therefore said to be zero sum. When gurus tell us that life isn’t a zero-sum game, they therefore aren’t saying anything about the total sum of happiness in the world. They are just reminding us that the games we play in real life are seldom games of pure conﬂict. 10 4. Games with mixed motivations Nash equilibrium I prefer to illustrate Chicken with a more humdrum story in which Alice and Bob are two middle-aged drivers approaching each other in a street too narrow for them to pass safely without someone slowing down. The strategies in Figure 4 are therefore taken to be slow and speed. The new setting downplays the competitive element of the original story. Chicken differs from zero-sum games like Matching Pennies because the players also have a joint interest in avoiding a mutual disaster. The stereotypes embedded in the Battle of the Sexes pre-date the female liberation movement. Alice and Bob are a newly married couple honeymooning in New York. At breakfast, they discuss whether to go to a boxing match or the ballet in the evening, but 11 The name of the game The old movie Rebel without a Cause still occasionally gets a showing because it stars the unforgettable James Dean as a sexy teenage rebel. The game of Chicken was invented to commemorate a scene in which he and another boy drive cars towards a cliff edge to see who will chicken out ﬁrst. Bertrand Russell famously used the episode as a metaphor for the Cold War. Game Theory 5. James Dean fail to make a decision. They later get separated in the crowds and now each has to decide independently where to go in the evening. The story that accompanies the Battle of the Sexes emphasizes the cooperative features of their problem, but there is also a conﬂictual element absent from the Driving Game, because each player prefers that they coordinate on a different outcome. Alice prefers the ballet and Bob the boxing match. John Nash Everybody has heard of John Nash now that his life has been featured in the movie A Beautiful Mind. As the movie documents, the highs and lows of his life are out of the range of experience of most human beings. He was still an undergraduate when he initiated the modern theory of rational bargaining. His graduate thesis formulated the concept of a Nash equilibrium, which is now regarded as the basic building block of the theory of games. He went on to solve major problems in pure mathematics, using methods of such originality that his reputation as a mathematical genius of the ﬁrst rank became ﬁrmly established. But he fell prey 12 The name of the game 6. John Nash to a schizophrenic illness that wrecked his career and ﬁnally left him to languish in obscurity for more than 40 years as an object of occasional mockery on the Princeton campus. His recovery in time to be awarded a Nobel Prize in 1994 seems almost miraculous in retrospect. But as Nash comments, without his ‘madness’, he would perhaps only have been another of the faceless multitudes who have lived and died on this planet without leaving any trace of their existence behind. 13 However, one doesn’t need to be a wayward genius to understand the idea of a Nash equilibrium. We have seen that the payoffs in a game are chosen to make it tautological that rational players will seek to maximize their average payoff. This would be easy if players knew what strategies their opponents were going to choose. For example, if Alice knew that Bob were going to choose ball in the Battle of the Sexes, she would maximize her payoff by choosing ball as well. That is to say, ball is Alice’s best reply to Bob’s choice of ball, a fact indicated in Figure 4 by circling Alice’s payoff in the cell that results if both players choose ball. Game Theory A Nash equilibrium is just a pair of strategies whose use results in a cell in which both payoffs are circled. More generally, a Nash equilibrium occurs when all the players are simultaneously making a best reply to the strategy choices of the others. Both (box, box) and (ball, ball) are therefore Nash equilibria in the Battle of the Sexes. Similarly, (slow, speed) and (speed, slow) are Nash equilibria in Chicken. Why should we care about Nash equilibria? There are two major reasons. The ﬁrst supposes that ideally rational players reason their way to a solution of a game. The second supposes that people ﬁnd their way to a solution by some evolutionary process of trial and error. Much of the predictive power of game theory arises from the possibility of passing back and forth between these alternative interpretations. We seldom know much about the details of evolutionary processes, but we can sometimes leap ahead to predict where they will eventually end up by asking what rational players would do in the situation under study. Rational interpretation Suppose that somebody even cleverer than Nash or Von Neumann had written a book that lists all possible games along with an authoritative recommendation on how each game should be 14 played by rational players. Such a great book of game theory would necessarily have to pick a Nash equilibrium as the solution of each game. Otherwise it would be rational for at least one player to deviate from the book’s advice, which would then fail to be authoritative. Suppose, for example, that the book recommended that teenage boys playing Chicken should both choose slow as their mothers would wish. If the book were authoritative, each player would then know that the other was going to play slow. But a rational player in Chicken who knows that his opponent is going to choose slow will necessarily choose speed, thereby refuting the book’s claim to be authoritative. Various Latin tags are available to those who are unhappy with such circular arguments. When ﬁrst accused of committing the fallacy of circulus in probando when talking about equilibria, I had to go and look it up. It turns out that I was lucky not to have been accused of the even more discreditable petitio principii. But all arguments must obviously either be circular or reduce to an inﬁnite regression if one never stops asking why. Dictionary deﬁnitions are the most familiar example. In games, we can either forever contemplate the inﬁnite regression that begins: Alice thinks that Bob thinks that Alice thinks that Bob thinks . . . or else take refuge in the circularity built into the idea of a Nash equilibrium. This short circuits the inﬁnite regression by observing that any other strategy proﬁle will eventually be destabilized when the players start thinking about what the other 15 The name of the game Notice that the reasoning in this defence of Nash equilibria is circular. Why does Alice play this way? Because Bob plays that way. Why does Bob play that way? Because Alice plays this way. players are thinking. Or to say the same thing another way, if the players’ beliefs about each other’s plans are to be consistent, then they must be in equilibrium. Game Theory Evolutionary interpretation The rational interpretation of Nash equilibrium had such a grip on early game theorists that the evolutionary interpretation was almost entirely neglected. The editors of the journal in which Nash published his paper on equilibria even threw out his remarks on this subject as being without interest! But game theory would never be able to predict the behaviour of ordinary people if the evolutionary interpretation were invalid. For example, the famous mathematician Emile Borel thought about game theory before Von Neumann but came to the conclusion that the minimax theorem was probably false. So what hope would there be for the rest of us, if even someone as clever as Borel couldn’t reason his way to a solution of the simplest class of games! There are many possible evolutionary interpretations of Nash equilibria, which differ in the adjustment process by means of which players may ﬁnd their way to an equilibrium. In the simpler adjustment processes, the payoffs in a game are identiﬁed with how ﬁt the players are. Processes that favour ﬁtter strategies at the expense of their less successful brethren can then only stop working when we get to a Nash equilibrium, because only then will all the surviving strategies be as ﬁt as it is possible to be in the circumstances. We therefore don’t need our players to be mathematical whizzes for Nash equilibria to be relevant. They often predict the behaviour of animals quite well. Nor is the evolutionary signiﬁcance of Nash equilibria conﬁned to biology. They have a predictive role whenever an adjustment process tends to eliminate strategies that generate low payoffs. For example, stockbrokers who do less well than their competitors go bust. The rules-of-thumb that stockbrokers use are therefore 16 subject to the same kind of evolutionary pressures as the genes of ﬁsh or insects. It therefore makes sense to look at Nash equilibria in the games played by stockbrokers, even though we all know that some stockbrokers wouldn’t be able to ﬁnd their way around a goldﬁsh bowl, let alone a game theory book. Prisoner’s Dilemma The most famous toy game of all is the Prisoner’s Dilemma. In the traditional story used to motivate the game, Alice and Bob are gangsters in the Chicago of the 1920s. The District Attorney knows that they are guilty of a major crime, but is unable to convict either unless one of them confesses. He orders their arrest, and separately offers each the following deal: If you fail to confess but your accomplice confesses, then you will be convicted and sentenced to the maximum term in jail. If you both confess, then you will both be convicted, but the maximum sentence will not be imposed. If neither confesses, you will both be framed on a tax evasion charge for which a conviction is certain. The story becomes more poignant if Alice and Bob have agreed to keep their mouths shut if ever put into such a situation. Holding out then corresponds to cooperating and confessing to defecting, as in the table on the left of Figure 7. The payoffs in the table correspond to notional years in jail (on the assumption that one util always corresponds to one extra year of freedom). A less baroque story assumes that Alice and Bob each have access to a pot of money. Both are independently allowed either to give their opponent $2 from the pot, or to put $1 from the pot in their own pocket. On the assumption that Alice and Bob care only about money, we are led to the payoff table on the right of Figure 7 in which utils have been identiﬁed with dollars. In this case, the altruistic strategy of giving $2 has been assigned the label dove, 17 The name of the game If you confess and your accomplice fails to confess, then you go free. 7. Two versions of the Prisoner’s Dilemma: in the version on the right, dove represents giving and hawk represents taking Game Theory and the selﬁsh strategy of taking $1 has been assigned the label hawk. Circling best replies reveals that the only Nash equilibrium in the give-or-take version of the Prisoner’s Dilemma is for both Alice and Bob to play hawk, although each would get more if they both played dove. The gangster version is strategically identical. In the unique Nash equilibrium, each will defect, with the result that they will both spend a long time in jail, although each would get a much lighter sentence if they both cooperated. Paradox of rationality? A whole generation of scholars swallowed the line that the Prisoner’s Dilemma embodies the essence of the problem of human cooperation. They therefore set themselves the hopeless task of giving reasons why game theory’s resolution of this supposed ‘paradox of rationality’ is mistaken (See Fallacies of the Prisoner’s Dilemma, Chapter 10). But game theorists think it just plain wrong that the Prisoner’s Dilemma captures what matters about human cooperation. On the contrary, it represents a situation in which the dice are as loaded against the emergence of cooperation as they could possibly be. 18 If the great game of life played by the human species were adequately modelled by the Prisoner’s Dilemma, we wouldn’t have evolved as social animals! We therefore see no more need to solve an invented paradox of rationality than to explain why people drown when thrown into Lake Michigan with their feet encased in concrete. No paradox of rationality exists. Rational players don’t cooperate in the Prisoner’s Dilemma because the conditions necessary for rational cooperation are absent. Domination The idea that it is necessarily irrational to do things that would be bad if everybody did them is very pervasive. Your mother was probably as fond of this argument as mine. The following knock-down refutation in the case of the Prisoner’s Dilemma is therefore worth repeating. So as not to beg any questions, we begin by asking where the payoffs that represent the players’ preferences in the Prisoner’s Dilemma come from. The theory of revealed preference tells us to ﬁnd the answer by observing the choices that Alice and Bob make (or would make) when solving one-person decision problems. Writing a larger payoff for Alice in the bottom-left cell of the payoff table of the Prisoner’s Dilemma than in the top-left cell 19 The name of the game Fortunately the paradox-of-rationality phase in the history of game theory is just about over. Insofar as they are remembered, the many fallacies that were invented in hopeless attempts to show that it is rational to cooperate in the Prisoner’s Dilemma are now mostly quoted as entertaining examples of what psychologists call magical reasoning, in which logic is twisted to secure some desired outcome. My favourite example is Immanuel Kant’s claim that rationality demands obeying his categorical imperative. In the Prisoner’s Dilemma, rational players would then all choose dove, because this is the strategy that would be best if everybody chose it. therefore means that Alice would choose hawk in the one-person decision problem that she would face if she knew in advance that Bob had chosen dove. Similarly, writing a larger payoff in the bottom-right cell means that Alice would choose hawk when faced with the one-person decision problem in which she knew in advance that Bob had chosen hawk. Game Theory The very deﬁnition of the game therefore says that hawk is Alice’s best reply when she knows that Bob’s choice is dove, and also when she knows his choice is hawk. So she doesn’t need to know anything about Bob’s actual choice to know her best reply to it. It is rational for her to play hawk whatever strategy he is planning to choose. In this unusual circumstance, we say that hawk dominates Alice’s alternative strategies. Objections? Two objections to the preceding analysis are common. The ﬁrst denies that Alice would choose to defect in the gangster version of the Prisoner’s Dilemma if she knew that Bob had chosen to cooperate. Various reasons are offered that depend on what one believes about conditions in Al Capone’s Chicago, but such objections miss the point. If Alice wouldn’t defect if she knew that Bob had chosen to cooperate, then she wouldn’t be playing the Prisoner’s Dilemma. Here and elsewhere, it is important not to take the stories used to motivate games too seriously. It is the payoff tables of Figure 7 that deﬁne the Prisoner’s Dilemma – not the silly stories that accompany them. The second objection always puzzles me. It is said that appealing to the theory of revealed preference reduces the claim that it is rational to defect in the Prisoner’s Dilemma to a tautology. Since tautologies have no substantive content, the claim can therefore be ignored! But who would say the same of 2 + 2 = 4? 20 Experiments An alternative response is to argue that it doesn’t matter what is rational in the Prisoner’s Dilemma, because laboratory experiments show that real people actually play dove. The payoffs in such experiments aren’t usually determined using the theory of revealed preference. They are nearly always just money, but the results can nevertheless be very instructive. Inexperienced subjects do indeed cooperate a little more than half the time on average, but the evidence is overwhelming in games like the Prisoner’s Dilemma that the rate of defection increases steadily as the subjects gain experience, until only about 10% of subjects are still cooperating after ten trials or so. 21 The name of the game Computer simulations are also mentioned which supposedly show that evolution will eventually generate cooperation in the Prisoner’s Dilemma, but such critics have usually confused the Prisoner’s Dilemma with its indeﬁnitely repeated cousin in which cooperation is indeed a Nash equilibrium (See Tit-for-tat, Chapter 5). Chapter 2 Chance Conan Doyle’s analysis of his version of Matching Pennies in The Final Problem doesn’t reﬂect much credit on his hero’s supposed intellectual mastery. Edgar Allan Poe does better in the Purloined Letter, in which the villain has stolen a letter, and the problem is where to look for it. Poe argues that the way to win is to extend chains of reasoning of the form ‘He thinks that I think that he thinks that I think . . . ’ one step further than your opponent. In defence of this proposition, he invents a boy who consistently wins at Matching Pennies by imitating his opponent’s facial expression, thereby supposedly learning what he must be thinking. It is admittedly amazing how many Poker players give their hands away by being unable to control their body language, but Alice and Bob can’t both use Poe’s trick successfully even if neither ever learns to keep a Poker face. Game theory escapes the apparent inﬁnite regression with which Alice and Bob are faced by appealing to the idea of a Nash equilibrium. But we are still left with a problem, because the trick of circling best replies doesn’t work for Matching Pennies. After circling all the payoffs in Figure 3 that are best replies, we end up with two Nash equilibria in the Driving Game, but none at all in Matching Pennies. 22 This fact may seem mysterious to those who remember that John Nash won his Nobel Prize partly for showing that all ﬁnite games have at least one equilibrium. The answer to the mystery is that we need to look beyond the pure strategies we have considered up to now, and consider mixed strategies as well. Does randomizing make sense? A mixed strategy requires that players randomize their choice of pure strategy. It is natural to object that only crazy people make serious decisions at random, but mixed strategies are used all the time without anyone realizing it. His answer shows that he understood perfectly well why game theory sometimes recommends the use of mixed strategies. What he didn’t want to face up to is that his company’s method for setting prices was essentially a randomizing device. Nobody cut any cards. Nobody rattled a dice box. But from the point of view of a rival trying to predict what his company would charge for two weeks in the Bahamas, they might as well have done so. Mixed Nash equilibria The use of mixed strategies isn’t at all surprising in Matching Pennies, where the whole point is to keep the opponent guessing. As every child knows, the solution is to randomize between heads 23 Chance My favourite example arose when I was advising a package holiday company on a regulatory matter. Game theory predicts that such a company will use a mixed strategy in the pricing game it has to play when the demand for vacations proves to be unexpectedly low. However, when I asked a senior executive whether his company actively randomized their prices last year, he reacted with horror at such an outlandish suggestion. So why were his prices for similar vacations so very different? His answer was instructive: ‘You have to keep the opposition guessing.’ 8. Rolling dice Game Theory and tails. If both players use this mixed strategy, the result is a Nash equilibrium. Each player wins half the time, which is the best that both can do given the strategy choice of the other. Similarly, it is a Nash equilibrium in the Driving Game if both players choose left and right with equal probability, which therefore has three Nash equilibria, two pure and one mixed. The same is also true in both Chicken and the Battle of the Sexes, but the mixed Nash equilibrium in the Battle of the Sexes requires more of the players than that they simply make each of their pure strategies equally likely. In the Battle of the Sexes, Bob likes boxing twice as much as ballet, and so Alice must play box half as often as ball to ensure that he gets the same payoff on average from his two pure strategies. Since Bob doesn’t then care which of his pure strategies gets played, all of his strategies are then equally good – including the mixed strategy which makes ball half as likely as box. But the use of this mixed strategy makes Alice indifferent between her two pure strategies. So all of her strategies are then equally good – including the mixed strategy which makes box twice as likely as ball. This completion of the circuit shows that we have found a mixed Nash equilibrium in which Alice and Bob each play their more favoured strategy two-thirds of the time. 24 Making the other guy indifferent Rational players never randomize between two pure strategies unless they are indifferent between them. If one strategy were better, the inferior strategy would never get played at all. What might make you indifferent between two strategies? In the Battle of the Sexes, the reason is that you believe your opponent is going to play a mixed strategy that equalizes the average payoff you get from each of your strategies. This feature of a mixed Nash equilibrium sometimes leads to results that look paradoxical at ﬁrst sight. If nobody else is planning to help, you do best by offering to help yourself. If everybody else is planning to help, you maximize your payoff by doing nothing. So the only possible Nash equilibrium in which everybody independently uses the same strategy is necessarily mixed. In such a mixed Nash equilibrium, there must be precisely one chance in ten that nobody else offers help, because this is the frequency that makes you indifferent between helping and not helping. The actual probability that help is offered in equilibrium is somewhat higher, because there is some chance that you will offer to help yourself. However, the probability that any single player offers help in equilibrium has got to get smaller as the population gets larger because the probability that nobody else helps has to stay equal to 1/10. So the bigger the population, the lower the chances that anyone will help. With only two players, each helps with probability 9/10 and the cry for help is ignored only one time in a hundred. With a million players, each helps with such a tiny 25 Chance The Good Samaritan Game is played by a whole population of identical players, all of whom want someone to respond to a cry for help. Each player gets ten utils if someone helps, and nothing if nobody helps. The snag is that helping is a nuisance, and so all the players who offer help must subtract one util from their payoffs. probability that nobody at all answers the cry for help about one time in ten. Game Theory The consequences can be chilling, as a notorious case in New York illustrates. A woman was assaulted at length after dark, and ﬁnally murdered in the street. Many people heard her cries for help but nobody even phoned the police. Should we follow the newspapers and deduce that city life makes monsters of us all? Perhaps it does, but the Good Samaritan Game suggests that even small-town folk might behave in the same way if put in the same situation. Voting has a similar character. To take an extreme case, suppose that Alice and Bob are the only candidates for the presidency. It is common knowledge that Bob is a hopeless case; only his mother thinks he would be the better president. She is sure to vote, but why should anyone else bother? As in the Good Samaritan Game, adding more voters makes things worse. In equilibrium, Bob will get elected with some irreducible probability even if there are a million voters. Such voting games are only toys. Real people seldom think rational thoughts about whether or not to vote. Even if they did, they might feel that going to the polling booth is a pleasure rather than a pain. But the model nevertheless shows that the pundits who denounce the large minority of people who fail to vote in presidential elections as irrational are talking through their hats. If we want more people to vote, we need to move to a more decentralized system in which every vote really does count enough to outweigh the lack of enthusiasm for voting which so many people obviously feel. If we can’t persuade such folk that they like to vote and we don’t want to change our political system, we will just have to put up with their staying at home on election night. Simply repeating the slogan that ‘every vote counts’ isn’t ever going to work, because it isn’t true. 26 Getting to equilibrium How do people ﬁnd their way to a Nash equilibrium? This question is particularly pressing in the case of mixed equilibria. Why should Alice adjust her behaviour to make Bob indifferent between some of his strategies? Sports studies show that athletes sometimes behave in quite close accord with game theory predictions. Taking penalty kicks in soccer is one example. Where should the ball be aimed? Which way should the goalkeeper jump? Tennis is another example. Should I smash or should I lob? It seems unlikely that coaches read any game theory books, so how come they know the correct frequency with which to choose each option? Presumably they learn by trial and error. Alice and Bob are robots who play the same game repeatedly. At each repetition, Alice is programmed to play her best reply to a mixed strategy in which each of Bob’s pure strategies is played with the same frequency he has played it in the past. Bob has the same program, so neither he nor Alice are fully rational, because they could both sometimes improve their payoffs if they were programmed more cleverly. Game theorists say that they are only boundedly rational. As time passes, the frequencies with which the robots have played their second pure strategy evolve as shown in Figure 9 (which has been simpliﬁed by passing from discrete to continuous time). For example, Alice’s best reply in Matching Pennies is tails whenever the current frequency with which Bob has played tails exceeds one half. So her frequency for tails will increase until his frequency for 27 Chance Nobody understands all the different ways in which real people learn new ways of doing things, but we have some toy models that capture some of what must be going on. Even the following naive model does surprisingly well. 9. Learning to play an equilibrium Game Theory tails falls below one half, after which it will abruptly begin to decrease. Following the arrows in Figure 9 always leads to a Nash equilibrium. No matter how we initialize the robots, someone counting how often they play each of their pure strategies will therefore eventually ﬁnd it hard to distinguish one of our boundedly rational robots from a perfectly rational player. In the case of Matching Pennies, which is closest to tennis or soccer, the frequencies with which heads or tails are played always converge on their equilibrium values of 1/2. In laboratory experiments with human subjects, the general pattern is much the same, although the frequencies don’t evolve in such a regular manner and they begin to drift when they get near enough to a mixed equilibrium, because the players are then nearly indifferent between the available strategies. The situation in Chicken is more complicated. Each pure equilibrium has a basin of attraction. If we initialize our robots so that they begin in the basin of attraction of a particular equilibrium, they will eventually converge on that equilibrium. The basin of attraction for (slow, speed) lies above the diagonal in 28 Figure 9. The basin of attraction for (speed, slow) lies below the diagonal. The basin of attraction for the mixed equilibrium is just the diagonal itself. It is easy to construct games in which the behaviour of robots like Alice and Bob would cycle forever without ever settling down on an equilibrium, but human beings are capable of learning in more sophisticated ways than Alice or Bob. In particular, we commonly enjoy a great deal of feedback from all kinds of sources when learning how to behave when faced with a new game. Evolutionary game theory is the study of such dynamic models. Its application to evolutionary biology is so important that it gets a chapter all to itself (Chapter 8). Minimax theorem When a youthful John Nash called at Von Neumann’s ofﬁce to tell him of his proof that all ﬁnite games have at least one equilibrium when mixed strategies are allowed, Von Neumann was dismissive. Why didn’t he welcome Nash’s contribution? It is true that the method Nash used to prove his theorem wasn’t anything new for Von Neumann, who had pioneered the method himself. It is also true that Nash’s approach was probably not very tactful, since he famously called on Albert Einstein around the same time to tell him how to do physics. But Von Neumann had 29 Chance For example, rookie stockbrokers learn the ropes from their more experienced colleagues. Young scientists peruse the history of Nobel laureates in the hope of ﬁnding the secret of their success. Novelists tediously recycle the plots of the latest best-seller. Shoppers tell each other where the best bargains are to be found. Toy models of such social or imitative learning converge more quickly and reliably on Nash equilibria than models in which single individuals learn by trial and error. nothing to fear from a brash young graduate student muscling in on his domain. I think there was a more fundamental reason for Von Neumann’s lack of interest. Game Theory Von Neumann never seems to have thought much about the evolutionary interpretation of game theory. He believed that the purpose of studying a game should be to identify an unambiguous rational solution. The idea of a Nash equilibrium doesn’t meet this requirement, because most games have many Nash equilibria, and there is often no purely rational reason for selecting one equilibrium rather than another. As Von Neumann later remarked, the best-reply criterion only tells us that some strategy proﬁles can’t be the rational solution to a game, but we want to know which strategy proﬁles can be regarded as solutions. Minimax and maximin Von Neumann presumably restricted his attention to two-person, zero-sum games because they are one of the few classes of games in which his ideal of a unique rational solution can be realized. It is unfortunate that his proof of this fact should be called the minimax theorem, because the rational solution of a two-person, zero-sum game is actually for each player to apply the maximin principle. This tells you to work out the worst payoff you could get on average from each of your mixed strategies, and then to choose whichever strategy would maximize your payoff if this worst-case scenario were always realized. For example, the worst thing that could happen to Alice in Matching Pennies is that Bob will guess her choice of mixed strategy. If this mixed strategy requires her to play heads more than half the time, then he will play tails all the time. She will then lose more than half the time and so her payoff will be negative. If Alice’s mixed strategy requires her to play tails more than half the time, then Bob will play heads all the time. She will again lose more than half the time and so her payoff will again be negative. 30 Alice’s maximin strategy is therefore to play heads and tails equally often, which guarantees her a payoff of exactly zero. Only a paranoic would ﬁnd the maximin principle attractive in general, since it assumes that the universe has singled you out to be its personal enemy. However, if Alice is playing Bob in a zero-sum game, he is the relevant universe and so the universe is indeed her personal enemy in this special case. Why maximin? Ironically, Von Neumann’s minimax theorem follows immediately from Nash’s proof that all ﬁnite games have at least one Nash equilibrium. Alice can’t be sure of getting more than Alice’s value because Bob might always play column, to which her best reply is row. On the other hand, Alice can be sure of getting at least Alice’s value by playing row because the best that Bob can do is to reply with column, and the best that Bob can do for himself in a zero-sum game is the same as the worst he can do to Alice. So Alice’s value is Alice’s maximin payoff, and row is one of her maximin strategies. By the same reasoning, Bob’s value is his maximin payoff and column is one of his maximin strategies. Since if Alice’s value and Bob’s value sum to zero, it follows that so do their maximin payoffs. Neither player can therefore get more than his or her 31 Chance To see this, begin by locating a Nash equilibrium in a two-person, zero-sum game. Call Alice’s equilibrium strategy row and Bob’s equilibrium strategy column. The equilibrium payoffs will be called Alice’s value and Bob’s value. For example, in Matching Pennies both row and column are the mixed strategy in which heads and tails are played with equal probability; Alice’s value and Bob’s value are the zero payoff that each player gets on average if they play this way. maximin payoff unless the other gets less. So one can’t improve on the maximin principle when playing a two-person, zero-sum game against a rational opponent. Von Neumann’s proof of this fact is called the minimax theorem, because saying that Alice and Bob’s maximin payoffs sum to zero is equivalent to saying that Alice’s maximin payoff equals her minimax payoff. But one mustn’t make the common mistake of thinking that Von Neumann therefore recommended using the minimax principle. Nobody would want to work out the best payoff you could get on average from each of your mixed strategies, and then choose whichever strategy would minimize your payoff if this best-case scenario were always realized! Game Theory Finding maximin strategies In retrospect, it is a pity that mathematicians took an immediate interest in the minimax theorem. The study of pursuit-evasion games in which a pilot seeks to evade a heat-seeking missile is certainly an interesting exercise in control theory, but such work naturally reinforces the prejudices of critics who are ﬁxated on the idea that game theorists are mad cyborgs. Nor is the popularity of game theory likely to be enhanced by the abstruse ﬁnding that the minimax theorem can only be true in certain inﬁnite games if we are willing to deny the Axiom of Choice. Game theory would have found a more ready acceptance in its early years if enthusiasts hadn’t made it all seem so difﬁcult. Rock-Scissors-Paper Every child knows this game. Alice and Bob simultaneously make a hand signal that represents one of their three pure strategies: rock, scissors, paper. The winner is determined by the rules: rock scissors paper blunts cuts wraps 32 scissors paper rock . If both players make the same signal, the result is a draw, which both players regard as being equivalent to a lottery in which they win or lose with equal probability, so that the game is zero-sum. It is obvious that the rational solution is for each player to use each of their three pure strategies equally often. They each then guarantee their maximin payoff of zero. The chief interest of the game is that one has to work very hard to ﬁnd an evolutionary process that converges on this solution. O’Neill’s Card Game Barry O’Neill used this game in the ﬁrst laboratory experiment that found positive support for the maximin principle. Previous experiments had been discouraging. The eminent psychologist William Estes was particularly scathing when reporting on his test of Von Neumann’s theory: ‘Game theory will be no substitute for an empirically grounded behavioral theory when we want to predict what people will actually do in competitive situations.’ But in the experiment on which Estes based his dismissive remarks, there were only two subjects, who are described as being well practised in the reinforcement learning experiments that Estes was using to defend the (now discredited) theory of ‘probability matching’. Neither subject knew that they were playing a game with another person. Even if they had known they were playing a game, the minimax theory would have been irrelevant to their plight, since they weren’t told in advance what 33 Chance For example, the best-reply dynamics of Figure 9 end up cycling in a manner that periodically nearly eliminates each strategy in turn. One might dismiss this outcome as a curiosity if it weren’t for the fact that the population mix of three varieties of Central American salamanders who play a game like Rock-Scissors-Paper also end up in a similar cycle, so that one variety always seems on the edge of extinction. the payoffs of the game were. They were therefore playing with incomplete information – a situation to which Von Neumann’s minimax theory doesn’t apply. In designing an experiment without such errors, O’Neill wanted to control for the possibility that subjects might have different attitudes to taking risks. For example, Rock-Scissors-Paper wouldn’t be zero-sum if Alice and Bob didn’t both think a draw is equivalent to winning or losing with equal probability. So O’Neill experimented on a game with only winning or losing, but which still has enough structure to make the solution unobvious. Game Theory Alice and Bob each have the ace and the picture cards from one of the suits in a deck of playing cards. They simultaneously show a card. Alice wins if both show an ace, or if there is a mismatch of picture cards. Otherwise Bob wins. Alice’s maximin strategy is found by asking which of her mixed strategies makes Bob indifferent between all his pure strategies. The answer is that Alice should play each picture card equally often and her ace twice as often. Bob should do the same, with the result that Alice will win two-ﬁfths of the time and Bob will win three-ﬁfths of the time. Duel The game of Duel is the nearest we are going to get to a military application. Alice and Bob walk towards each other armed with pistols loaded with just one bullet. The probability of either hitting the other increases the nearer the two approach. The payoff to each player is the probability of surviving. How close should Alice get to Bob before ﬁring? This is literally a question of life and death because, if she ﬁres and misses, Bob will be able to advance to point-blank range with fatal consequences 34 for Alice. Since someone dies in each possible outcome of the game, the payoffs therefore always sum to one. One conclusion is obvious. It can’t be a Nash equilibrium for one player to plan to ﬁre sooner than the other, because it would be a better reply for the player who is planning to ﬁre ﬁrst to wait a tiny bit longer. But how close will they be when they simultaneously open ﬁre? 35 Chance The minimax theorem gives the answer right away. Duel is unit-sum rather than zero-sum, but the minimax theorem still applies (provided the payoffs still sum to one when the players ﬁre simultaneously). The only difference is that the players’ maximin payoffs now add up to one instead of zero. So if Alice is always twice as likely to hit Bob as he is to hit her, they will both ﬁre at whatever distance makes Alice hit Bob two-thirds of the time and Bob hit Alice one-third of the time. Chapter 3 Time Games with perfect information People sometimes think it frivolous to talk about human social problems as though they were mere parlour games. The advantage is that nearly everybody is able to think dispassionately about the strategic issues that arise in games like Chess or Poker, without automatically rejecting a conclusion if it turns out to be unwelcome. But logic is the same wherever it is applied. Parlour games At ﬁrst sight, it doesn’t look like Chess and Poker can be represented by payoff tables, because time enters the picture. It not only matters who does what – it matters when they do it. Some of the difference is illusory. In the general case, a pure strategy is a plan of action that tells a player what to do under all possible contingencies that might arise in a game. The players can then be envisaged as choosing a strategy once and for all at the beginning of the game, and then delegating the play of the game to a robot. The resulting strategic form of Chess will then look just like Chicken or the Battle of the Sexes, except that its payoff table will be zero sum and have immensely more rows and columns. 36 Von Neumann argued that the ﬁrst thing one should do in any game is to reduce it to its strategic form, which he called its normal form for this reason. However, the case of Chess makes it clear that this isn’t always a very practical proposal, since it has more pure strategies than the estimated number of electrons in the known universe! Even when the strategic form isn’t hopelessly unwieldy, it is often a lot easier to work things out by sticking with the extensive form of the game. In Poker, the ﬁrst move is made by a ﬁctional player called Chance who shufﬂes and deals hands to the real players. What the players know about this move is extremely important in Poker, since the game would be devoid of interest if everybody knew what everybody else had been dealt. However, such games of imperfect information will be left until the next chapter. All the games in this chapter will be games of perfect information, in which nothing that has happened in the game so far is hidden from players when they make a move. Nor shall we consider games of perfect information like Duel that have chance moves. Chess is therefore the archetypal example for this chapter. Backward induction Backward induction is a contentious topic, but everybody agrees that we would always be able to use it to ﬁnd the players’ maximin 37 Time Game theorists use the analogy of a tree when describing a game in extensive form. Each move corresponds to a point called a node where the tree branches. The root of the tree corresponds to the ﬁrst move of the game. The branches at each node correspond to the choices that can be made at that move. The leaves of the tree correspond to the ﬁnal outcomes of the game, and so we must say who gets what payoff at each leaf. We must also say which player moves at each node, and what that player knows about what has happened so far in the game when making the move. values in a ﬁnite game of perfect information – if we had a large enough computer and sufﬁcient time. Given a large enough lever and a place on which to stand, Archimedes was similarly correct when he said he would be able to move the world. Applying backward induction to Chess illustrates both its theoretical virtues and its practical drawbacks. Game Theory Chess Label each leaf of the game tree for Chess with WIN, LOSE, or DRAW, depending on the outcome for White. Now pick any penultimate node (where each choice leads immediately to a leaf of the tree). Find the best choice for the player who moves at this node. Label the penultimate node with the label of the leaf to which this choice leads. Finally, throw away all of the tree that follows the penultimate node, which now becomes a leaf of a smaller tree in which the players’ maximin values are unchanged. Now do the same again and again, until all that is left is a label attached to the root of the original tree. This label is White’s maximin outcome. No matter how big and fast the computers we eventually build, they will never be able to complete this program for Chess, because it would take too long. So we will probably never know the solution of Chess. But at least we have established that, unlike Bigfoot or the Loch Ness Monster, there really is a solution for Chess. If White’s maximin outcome is WIN, then she has a pure strategy that guarantees her a victory against any defence by Black. If White’s maximin outcome is LOSE, Black has a pure strategy that guarantees him a victory against any defence by White. However, most experts guess that White’s maximin outcome is DRAW, which implies that both White and Black have pure strategies that guarantee a draw against any defence. 38 10. Two board games Hex Piet Hein invented this game in 1942. It was reinvented by Nash in 1948. People say that he had the idea while contemplating the hexagonal tiling in the men’s room of the Princeton mathematics department. There were indeed hexagonal tiles there, but Nash tells me that he doesn’t recall ﬁnding them at all inspiring. Hex is played between Black and White on a board of hexagons arranged in a parallelogram, as in Figure 10. At the beginning of the game, each player’s territory consists of two opposite sides of the board. The players take turns in moving, with White going ﬁrst. A move consists of placing one of your counters on a vacant hexagon. The winner is the ﬁrst to link their two sides of the board, so Black was the winner in the game just concluded in Figure 10. As in Chess, we can theoretically work out the players’ maximin payoffs using backward induction, but the method isn’t practical 39 Time If these experts are right, then the strategic form of Chess has a row in which all the outcomes are WIN or DRAW and a column in which all the payoffs are LOSE or DRAW as in Figure 10. Without the backward induction argument, I am not sure that this fact would seem at all obvious. when the board is large. But we nevertheless know that White’s maximin payoff is WIN. That is to say, the ﬁrst player to move has a strategy that guarantees victory against any defence by the second player. How do we know this? Game Theory Note ﬁrst that Hex can’t end in a draw. To see this, think of the Black counters as water and the White counters as land. When all the hexagons are occupied, water will then either ﬂow between the two lakes originally belonging to Black, or else the channel between them will be dammed. Black wins in the ﬁrst case, and White in the second. So either Black or White has a winning strategy. Nash invented a strategy-stealing argument to show that the winner must be White. The argument is by contradiction. If Black were to play a winning strategy, White could steal it using the following rules: 1. Put your ﬁrst counter anywhere. 2. At later moves, ﬁrst pretend that the last counter you played isn’t on the board. Next pretend that all the remaining White counters are Black and all the Black counters are White. 3. Now make the move that Black would make in this position when using his winning strategy. If you already have a counter in this position, just move anywhere. This strategy guarantees you a win, because you are simply doing what supposedly guarantees Black a win – but one move earlier. The presence on the board of an extra White counter may result in your winning sooner than Black would have done, but I guess you won’t complain about that! Since both players can’t be winners, our assumption that Black has a winning strategy must be wrong. The winner is therefore White – although knowing this fact won’t help her much when 40 playing Hex on a large board, since ﬁnding White’s winning strategy is an unsolved problem in the general case. Notice that the strategy-stealing argument doesn’t tell us anything at all about White’s actual winning strategy. She certainly can’t guarantee winning after putting her ﬁrst counter just anywhere. If she puts her ﬁrst counter in an acute corner of the board, you will probably be able to see why Black then has a winning strategy in the rest of the game. Deleting dominated strategies Every time you throw out a bunch of choices at a node while carrying out a backward induction, you are discarding an equivalent bunch of pure strategies. From the point of view of the strategic form of the game you have reached at that stage, any strategy you discard is dominated by a strategy which is exactly the same except that it calls for a best choice to be made at the node in question. If we exclude the case when two strategies always yield the same payoff, one strategy is dominated by another if it never yields a better payoff, no matter what strategies the other players may use. Thus hawk dominates dove in the Prisoner’s Dilemma (but not in the Stag Hunt Game of Figure 18). 41 Time It may also be fun to test your reasoning skills on a version of Hex with which Princeton mathematicians supposedly used to tease their visitors. An extra line of hexagons is added to the board so that White’s two sides of the board become more distant than Black’s. In the new game, not only is it Black who has a winning strategy, but we can write his winning strategy down. However, when visitors played as White against a computer, the board was shown in perspective on the screen to disguise its asymmetry. The visitors therefore thought they were playing regular Hex, but to their frustration and dismay, somehow the computer always won! We can therefore mimic backward induction in a game by successively deleting dominated strategies in its strategic form. We can sometimes reduce a strategic form to just one outcome by this method even when not mimicking backward induction. The result will always be a maximin outcome in a two-person, zero-sum game. But what about games in general? Game Theory Any Nash equilibrium of a game you get by eliminating dominated strategies from a larger game must also be a Nash equilibrium of the larger game. The reason is that adding a dominated strategy to your options in a game can’t make any of your current best replies into something worse. You may sometimes lose Nash equilibria as you delete dominated strategies (unless all the dominations are strict), but you can never eliminate all Nash equilibria of the original game. Guessing games If Alice trades on the stock market, she is hoping that the shares she buys will rise in value. Since their future value depends on what other people believe about them, investors like Alice are really investing on the basis of their beliefs about other people’s beliefs. If Bob plans to exploit investors like Alice, he will need to take account of his beliefs about what she believes about what other people believe. If we want to exploit Bob, we will need to ask what we believe about what Bob believes about what Alice believes about what other people believe. John Maynard Keynes famously used the beauty contests run by newspapers of his time to illustrate how these chains of beliefs about beliefs get longer and longer the more one thinks about the problem. The aim in these contests was to chose the girl chosen by most other people. Game theorists prefer a simpler Guessing Game in which the winners are the players who choose a number that is closest to two-thirds of the average of all the numbers chosen. 42 If the players are restricted to whole numbers between 1 and 10 inclusive, it is a dominated strategy to choose a number above 7, because the average can be at most 10, and 23 × 10 = 6 23 . You therefore always improve your chances of winning by playing 7 instead of 8, 9, or 10. But if everybody knows that, nobody will ever play a dominated strategy, then we are in a game in which the players choose a number between 1 and 7 inclusive. The average in this game can be at most 7, and 23 × 7 = 4 23 . So it is a dominated strategy to choose a number above 5. It will be obvious where this argument is going. If it is common knowledge that no player will ever use a dominated strategy, then all the players must choose the number 1. Common knowledge I once watched a quiz show called The Price is Right in which three contestants guess the value of an antique. Whoever gets closest to the actual value is the winner. If the last contestant thinks the value is more than both the other two guesses, he should obviously raise the higher guess by no more than one dollar. Since this isn’t what happens, we would be foolish to try to apply game theory to quiz shows on the assumption that it is common knowledge that the contestants are rational. It is therefore fortunate that the evolutionary interpretation of game theory doesn’t require such strong assumptions. 43 Time Something is common knowledge if everybody knows it, everybody knows that everybody knows it, everybody knows that everybody knows that everybody knows it; and so on. If nothing is said to the contrary in a rational analysis of a game, it is always implicitly being assumed that both the game and the rationality of the players are common knowledge. Otherwise we wouldn’t be entitled to use the idea of a Nash equilibrium to break into inﬁnite regressions of the form: ‘Alice thinks that Bob thinks that Alice thinks that Bob thinks . . . ’ 11. Kidnap Game Theory Subgame perfection Daniel Ellsberg is best known for blowing the whistle on the Nixon administration’s conduct of the war in Vietnam when he leaked the Pentagon Papers to the New York Times in 1971. In an earlier incarnation, he proposed the game of Kidnap. Kidnap Alice has kidnapped Bob. The ransom has been paid, and the question now is whether she should release him or murder him. Alice would prefer to release Bob if she could be sure that he wouldn’t reveal her identity. Bob has promised to stay silent, but can she trust his promise? Figure 11 shows a game tree for Kidnap together with a corresponding payoff table. Circling best replies reveals that there is only one Nash equilibrium, in which Alice murders Bob because she predicts that he will tell if released. Deleting dominated strategies leads us to the same Nash equilibrium. Bob’s strategy tell is always at least as good as silent. So we begin by deleting silent. In the game that remains, Alice’s strategy murder is always at least as good as release (because Bob can only play tell in the reduced game). So we are left with only the Nash equilibrium (murder, tell). 44 Deleting dominated strategies in this way corresponds to using backward induction in the game tree. First thicken the branch in the game tree that represents Bob’s best choice of tell. Now forget that Bob’s inferior choice is there at all, and thicken the branch that represents Alice’s best choice of murder in the game that remains. We can now see the equilibrium path that will be followed when Alice and Bob play the Nash equilibrium (murder, tell). In this case, a single thickened branch links the root of the tree to a leaf; in a bigger game, the equilibrium path will be a whole sequence of thickened branches that link the root to a leaf. Counterfactuals Politicians like to pretend that hypothetical questions make no sense. As George Bush Senior said in 1992 when replying to a perfectly reasonable question about unemployment beneﬁt: ‘If a frog had wings, he wouldn’t hit his tail on the ground.’ But the game of Kidnap shows why hypothetical questions are the life blood of game theory – just as they ought to be the life blood of politics. Rational players stick to their equilibrium strategies because of what they predict would happen if they were to deviate. The subjunctives in this sentence appear because we are talking about a counterfactual event – an event that isn’t going to happen. Far from being irrelevant to anything real, such counterfactual events always arise when a rational decision is made. Why doesn’t Alice ever step in front of a car when crossing the road? Because she 45 Time In games of perfect information like Kidnap, backward induction always leads to strategies that are not only a Nash equilibrium in the whole game, but also in all its subgames – whether they lie on the equilibrium path or not. Reinhard Selten shared a Nobel Prize with John Nash partly for introducing this class of equilibria. He ﬁrst called them perfect, but later changed his mind about what perfection should mean. So now we call them subgame perfect. predicts that if she did, she would be run over. Why does Alice murder Bob in Kidnap? Because she believes that he would tell on her if she didn’t. What would happen in subgames that won’t be reached therefore matters. It is because of what would happen if they were reached that they aren’t reached! Changing the game? Game Theory Psychologists advise kidnap victims to try and build up a human relationship with their captors. If Bob could thereby persuade Alice that he cared sufﬁciently for her that his payoffs for remaining silent or telling were reversed, then we would be playing a different game that one might call Cosy Kidnap. As Figure 12 shows, Cosy Kidnap has two Nash equilibria in pure strategies: (murder, tell) and (release, silent). The equilibrium (murder, tell) isn’t subgame perfect any more, because it calls for Bob to make the inferior choice of tell in the subgame that is unreached in equilibrium because Alice actually chooses murder, but which would be reached if Alice were to choose release instead. However, the new equilibrium (release, silent) is subgame perfect. It is therefore this equilibrium that will be played, provided that Alice is rational and knows that Bob is rational. If the payoffs are 12. Cosy Kidnap 46 chosen according to the theory of revealed preference, then it is tautological that Bob would play silent rather than tell if Alice were to play release. Alice will therefore play release because she knows it will yield a higher payoff than murder. The moral is that rationality sometimes tells us more than simply that Alice and Bob must play a Nash equilibrium. Ultimatum Game The Ultimatum Game is a primitive bargaining game in which a notional philanthropist has donated a sum of money for Alice and Bob to share if they can agree on how to divide it. The rules specify that Alice ﬁrst makes a proposal to Bob on how to divide the money. He may accept or refuse. If he accepts, Alice’s proposal is adopted. If he refuses, the game ends with both players getting nothing. It is easy to apply backward induction to the game on the assumption that both players care only about getting as much money as possible. If Alice offers Bob a positive amount, he will say yes, because anything is better than nothing. The most that Alice will therefore offer is a penny. In a subgame-perfect equilibrium, Alice therefore scoops the pot. However, laboratory experiments show that real people usually play fair. The most likely proposal is a ﬁfty-ﬁfty split. Proposals for 47 Time Reinhard Selten has a mischievous sense of humour, and it may be that he takes a delight in the controversy he created with his notion of a subgame-perfect equilibrium. He certainly added fuel to the ﬁre when he proposed to his student Werner Güth that he run a laboratory experiment on the subject. The experiment was to see whether real people would play the subgame-perfect equilibrium in the Ultimatum Game. Selten predicted that they wouldn’t – and he was right. an unfair split like seventy-thirty are refused more than half the time, even though the responder then gets nothing at all. This is the most replicated result in experimental economics. I have replicated it myself several times. It doesn’t go away when the stakes are increased. It holds up even in countries where the dollar payoffs are a substantial fraction of the subjects’ annual income. The result isn’t entirely universal, but one has to follow anthropologists into remote parts of the world to ﬁnd exceptions. Game Theory A new school of behavioural economists uses this result as a stick with which to beat their traditional rivals. They say that the data disprove the ‘selﬁshness axiom’ of orthodox economics. Their challenge is therefore to the hypothesis that people care only about money rather than to the logic of backward induction. Actually, it isn’t axiomatic in economics that people are relentlessly selﬁsh. The orthodoxy is represented by the theory of revealed preference. Everybody agrees that money isn’t everything. Even Milton Friedman used to be kind to animals and give money to charity. But it is also true that there are an enormous number of experiments showing that most subjects do eventually end up behaving as though they were primarily interested in maximizing their dollar payoffs in all but a few laboratory games. The Prisoner’s Dilemma is the norm rather than an exception. So what is different about the Ultimatum Game? I think that the answer lies in the fact that the rational and the evolutionary interpretations of an equilibrium diverge when applied to subgame-perfect equilibria. The Ultimatum Minigame In this simpiﬁed version of the Ultimatum Game, the philanthropist donates $4. Alice can make a fair or an unfair proposal to Bob. The fair offer is to split the money ﬁfty-ﬁfty. Bob automatically accepts the fair offer, but has the option of accepting 48 13. Ultimatum Minigame. Apart from the labels of the available actions and some inconsequential changes in the payoffs, the game is the same as Cosy Kidnap The subgame-perfect equilibrium is (unfair, yes). Like Cosy Kidnap, the game also has another Nash equilibrium: (fair, no). In fact, it has lots of Nash equilibria in which Alice chooses fair because Bob is planning to use a mixed strategy in which he says no to the unfair offer with a sufﬁciently high probability. The reason that we need to worry about Nash equilibria that aren’t subgame perfect is that we haven’t any reason to suppose that an evolutionary process will necessarily converge on the subgame-perfect equilibrium. If the subjects are learning by trial and error which equilibrium to play, they might therefore learn to play any of the Nash equilibria of the Ultimatum Minigame. Figure 14 shows two different evolutionary processes in the Ultimatum Minigame. One is the best-reply dynamics we encountered earlier; the other is the more complicated replicator dynamics, which is usually regarded as a superior toy model of an adjustment process (see Evalutionary Stability, Chapter 8). 49 Time or refusing the unfair offer, which assigns $3 to Alice and only $1 to Bob. Figure 13 shows the game tree and payoff table for the Ultimatum Minigame. Its analysis is the same as in Cosy Kidnap, although here the logic of the argument is controversial because critics don’t like where it leads. Game Theory 14. Evolutionary adjustment in the Ultimatum Minigame. The subgame-perfect equilibrium is S. The other Nash equilibria lie in the set N. The latter all require the use of the weakly dominated strategy no, but N still has a large basin of attraction in the case of the replicator dynamics The best-reply dynamics converge on the subgame-perfect equilibrium, but this isn’t necessarily true of the replicator dynamics. The set of Nash equilibria in which Alice plays fair has a large basin of attraction in Figure 14. Evolution doesn’t care that Bob’s choice of no is weakly dominated in all of these equilibria. It is true that yes is always better than no provided that Alice sometimes plays unfair, but the evolutionary pressure against unfair can be so strong that it disappears altogether. Once it has gone, no can survive, because Bob is then indifferent between yes and no. Fair conventions We now have an explanation of the experimental data in the Ultimatum Game that doesn’t require assigning different preferences to the subjects than they reveal when playing the Prisoner’s Dilemma in the laboratory. In real life, Bob would be stupid to knuckle under when made an unfair offer, because he can’t afford to acquire a reputation for 50 being a soft touch. We therefore operate a convention in which Alice is often refused if she makes an unfair offer. Subjects bring this convention into the laboratory without realizing either that it coordinates behaviour on an equilibrium in the game of life, or that the game they are asked to play in the laboratory is very different from the real-life games for which the convention is adapted. Game theorists are happy for behavioural economists to make the case against selﬁshness. How else are we to explain why Milton Friedman contributed to charity? But they make two errors when they say: ‘Game theory predicts the subgame-perfect equilibrium in the Ultimatum Game.’ The ﬁrst is that game theory assumes that players necessarily maximize money. The second is that rational and evolutionary game theory always predict the same thing. Reﬁnements Evolution doesn’t always select subgame-perfect equilibria, but it remains rational for Alice to solve the Ultimatum Minigame by backward induction when the payoffs are determined by the theory of revealed preference. The standard assumption that Alice 51 Time When subjects start by playing fair in the Prisoner’s Dilemma, evolutionary pressures immediately start modifying their behaviour, because the only Nash equilibrium in the Prisoner’s Dilemma precludes any cooperation. The Ultimatum Game differs from the Prisoner’s Dilemma in having many Nash equilibria. Any split whatever of the available money corresponds to a Nash equilibrium, for the same reason that the same is true in the Ultimatum Minigame. When Alice and Bob begin by playing fair in the Ultimatum Game, there are no obvious evolutionary pressures urging them towards the subgame-perfect equilibrium. We therefore don’t need to invent some reason why they don’t move much from where they started. knows that Bob is rational is essential for this purpose, because Alice needs to be sure that Bob’s behaviour will be consistent with the payoffs assigned to him. Does our standard assumption that the rationality of the players is common knowledge imply that a subgame-perfect equilibrium path will be followed in any ﬁnite game of perfect information? Bob Aumann says yes, and one might think that he should know, since he won his Nobel Prize partly for making common knowledge into an operational tool. But examples like Selten’s Chain Store paradox continue to keep the question open. Game Theory Chain Store paradox The Ultimatum Minigame can be reinterpreted as a game in which Alice is threatening to open a store in a town where Bob already runs a similar store. We just need to relabel Alice’s strategies as out and in, and Bob’s as acquiesce and ﬁght. Fighting consists of initiating a price war, which is bad for both players. Selten’s paradox arises when Bob runs a chain of stores in a hundred towns and Alice is replaced by a hundred possible rivals threatening to set up a rival store in each town. Just as in the Ultimatum Minigame, backward induction in the 100th game says that the 100th rival will enter the market, and Bob will acquiesce. What happens in the 100th game is therefore determined independently of what happens in previous games, and so exactly the same argument applies in the 99th game. Continuing in this way, we end up with the conclusion that the rival will always enter and Bob will always acquiesce. But wouldn’t Bob do better to ﬁght the ﬁrst few entrants so as to discourage entry in the remaining towns? The game tree of Figure 15 is a simpliﬁcation in which there are only two towns and the rival is always Alice. If she enters the ﬁrst town, Bob can acquiesce or ﬁght. If she later enters the second 52 15. A simpliﬁed Chain Store paradox. Apart from the labels of the available actions, the subgame rooted at Alice’s second move is identical to the Ultimatum Minigame The thickened lines in Figure 15 show the result of applying backward induction. If the great book of game theory recommended following the subgame-perfect equilibrium path, it would therefore be right for Alice to enter both towns and for Bob to acquiesce each time. But will Alice and Bob follow the book’s advice? To explore this question, put yourself in Bob’s position at his ﬁrst move. Alice has just entered the ﬁrst town as recommended by the book, but what would she do if her second move were reached? The answer depends on what she predicts Bob would do if his second move were reached. If Alice knew that Bob were rational, then she would predict that he would acquiesce. She should then enter, and so Bob should acquiesce at his ﬁrst move, as required by backward induction. But Alice wouldn’t know that Bob is rational at her 53 Time town, he can again acquiesce or ﬁght. If Alice stays out of the ﬁrst town, we simplify by assuming that she necessarily stays out of the second town. Similarly, if Bob acquiesces in the ﬁrst town, Alice necessarily enters the second town, and Bob again acquiesces. second move, because a rational Bob wouldn’t have fought at his ﬁrst move if the great book of game theory were right about what is rational! Game Theory Alice began the game believing Bob to be rational, but if he plays in a manner that is inconsistent with his preferences by ﬁghting in the ﬁrst town, her belief will be refuted. And who knows what she might believe after such a counterfactual event? Selten’s original version of the paradox has 100 stores, because the common-sense answer after Bob has fought in 50 towns is that he is likely to ﬁght in the 51st as well. But then the backward induction argument collapses. The paradox doesn’t cast doubt on backward induction as a way of ﬁnding the maximin payoffs in two-person, zero-sum games. Nor does it create a problem for the rationality of backward induction in games like Kidnap or the Ultimatum Game. The players’ initial belief that everyone is rational would still be refuted if someone were to diverge from the equilibrium path, but this fact causes no problem in these short games. But how are we to respond to the paradox in longer games? Typos Subgame-perfect equilibria are said to be a reﬁnement of the Nash equilibrium concept. They are safe to use whenever the circumstances make it sensible for the players to continue behaving as though it is common knowledge that they are all rational even though one or more irrational moves have been made. A whole bestiary of even more reﬁned reﬁnements has been created for use in games of imperfect information. These are based on various different ideas about what beliefs would make sense in the counterfactual event that a rational player were to play irrationally. If George Bush Senior were to read the literature, it would make his head swim! Fortunately, this phase in the history of game theory is effectively over – although applied economists 54 continue to appeal to whichever reﬁnement in the bestiary comes closest to conﬁrming their own prejudices. My own take on these issues is that we should follow Reinhard Selten’s common-sense approach, which eliminates the need to interpret counterfactuals at all. He recommends that we build enough chance moves into the rules of our games to remove the possibility that players will ﬁnd themselves trying to explain the inexplicable. In the simplest such models, the players are assumed to make occasional mistakes. Their hands tremble as they reach for the rational button and they press an irrational button by mistake. If these mistakes are independent transient errors – like typos – that have no implications for mistakes that might be made in the future, then the Nash equilibria of the game with mistakes converge on subgame-perfect equilibria of the game without mistakes as we allow the frequency of mistakes to get very small. Thinkos The reason that other game theorists were unwilling to endorse Selten’s new deﬁnition can perhaps be traced to doubts about the generality of his trembling-hand story. If we want a rational analysis of a game to be relevant to the behaviour of real people trying to cope intelligently with complex problems, we have to face up to the fact that their mistakes are much more likely to be ‘thinkos’ than ‘typos’. For example, nobody would think it reasonable to explain why the owner of a chain of stores initiated a price war in 50 successive towns by saying that he always meant to instruct his managers to 55 Time Selten tried to downgrade subgame-perfect equilibria because he decided that the limits of Nash equilibria in trembling-hand games are what really deserve to be called perfect. But the rest of the world only concedes that such equilibria are trembling-hand perfect. acquiesce in the entry of a rival, but somehow always sent the wrong message by mistake. The only plausible explanation is that he has a policy of ﬁghting entry, and hence is likely to ﬁght in the 51st town whether this is foolish or not. Game Theory When chance moves are introduced that allow for such thinkos to occur, the Nash equilibria of the game with mistakes needn’t converge on a subgame-perfect equilibrium of the game without mistakes. So Nash equilibria of the game without mistakes can’t routinely be thrown away as irrelevant to a rational analysis. But nor do we want to scrap backward induction. All Nash equilibria of the game with mistakes are automatically subgame-perfect because the mistakes ensure that every subgame is always reached with positive probability. Backward induction is therefore a useful tool when locating these equilibria. A moral? The lesson I draw from the reﬁnement controversy is that game theorists went astray by forgetting that their discipline has no substantive content. Just as it isn’t our business to say what people ought to like, so it isn’t our business to say what they ought to believe. We can only say that if they believe this, then they would be inconsistent not to believe that. If we can’t analyse a game on such consistency principles alone, then more information about the players and their environment needs to be added to the game until we can. 56 Chapter 4 Conventions There is no problem about which Nash equilibrium should be regarded as the rational solution of a two-person, zero-sum game, because any pair of maximin strategies is always a Nash equilibrium in which the players get their maximin payoffs. But things can be very different in games that aren’t zero sum. For example, in the Battle of the Sexes, the maximin payoff for both players is two-thirds. This happens to be the same as the payoffs they both get in the game’s mixed equilibrium, but their maximin strategies aren’t equilibrium strategies. Moreover, Alice and Bob’s payoffs in both pure equilibria of the game are much bigger than their maximin payoffs. So what should they do? The Driving Game makes it obvious that there isn’t any point in looking for a strictly rational answer. Any argument that might be offered in favour of everyone driving on the left would be an equally good argument for everyone driving on the right. People sometimes say that the rational solution must therefore be the mixed equilibrium in which everyone decides whether to drive on the left or right at random, but this proposal seldom garners much support! To solve the Driving Game, we need a commonly accepted convention as to whether we should drive on the left or the right. 57 The fact that such a convention may be entirely arbitrary is reﬂected in the fact that some countries have adopted the convention of driving on the left and others of driving on the right. Game Theory Focal points Societies sometimes choose conventions deliberately, as when Sweden switched from driving on the left to driving on the right in the early hours of 1 September 1967. However, one should perhaps think of