by Filip Palda
Future Nobellist Reinhard Selten thought the compressed, or “normal form” Nash representation of these games hid the possibility that the Nash equilibria which seemed not-credible to all players could be eliminated. He said that the only credible equilibria were those in which each “subgame” was itself a Nash equilibrium. A subgame was a strategy chosen for the last stage of the game, or the two last stages, or the three last stages, and so, on. Basically a subgame perfect strategy had the feature that if you lopped off earlier plays and forgot about what had preceded, then your ensuing strategy would remain unchanged. It was strikingly similar to Richard Bellman’s “principle of optimality” in the totally unrelated field of dynamic optimization. If you strung together the sequence of such “subgame equilibria” you would have found the only credible strategy over the whole game. To even begin to grasp what all this means we desperately need an example.
Formally the example is known as the incumbent-challenger game but I like to think of it as the Fanucci-Corleone showdown. It takes place in New York around 1915 when an aspiring gangster by the name of Guido Corleone starts committing robberies on the Brooklyn “turf” of the older Don Fanucci. There are two stages to this game. In the first stage Corleone decides either to stay off Fanucci’s turf or continue robbing there. In the second stage Fanucci either fights or does not fight. If Corleone stays out and Fanucci does not fight, then Fanucci gives him a small weekly bribe of $100 while himself pocketing $500. In the other branching of this game Corleone decides to enter the turf. If Fanucci fights both die, and if Fanucci allows him to compete for criminal earnings, both get $200 a week. There are two possible Nash equilibria in this game, only one of which is subgame perfect.
Remember that a strategy is a complete specification of what a player plans to do given every contingency. One strategy leading to a Nash equilibrium is for Fanucci to fight if Corleone enters. If Corleone thinks this is Fanucci’s strategy then he will simply choose to accept the $100 bribe because the alternative is to die. It is a Nash equilibrium because neither player sees an advantage in deviating from this strategy. If Corleone deviates by fighting he gets killed along with Fanucci. If Fanucci deviates and does not plan to fight, his earnings go down to $200. Yet this is not a subgame perfect equilibrium because one of the subgames in it is not a Nash equilibrium. If we consider the final stage in isolation, no matter what Corleone has chosen in the first stage, it never makes sense for Fanucci to fight. If he does he dies. If he does not then at least he gets $200.
The other Nash equilibrium is for Corleone to enter and Fanucci not to fight. In this case both get $200. Neither wishes to deviate because then all get killed. This game has a Nash equilibrium in each subgame. It would never make sense in the subgame of the final stage for Fanucci to fight. And if Corleone knows this, his optimal strategy in the first stage is to enter the market. So the larger subgame including both stages is also a Nash equilibrium.
The number of parents tormented by the logic of playing this sort of game with their children over the aeons is hard to quantify. A firm strategy of abandoning your child at roadside will, if credible, calm any backseat agitations by the most inveterate of young miscreants. Yet children are aware that the final stage of this game is not a credible equilibrium and intuitively solve the game according to Selten’s logic.
As you can surmise, subgame perfection was around long before economists “discovered” it. What Selten contributed however was to prove under very general conditions that for games with some finite span, by picking their way backwards through all the payoffs each player would rule out non-credible choices by other players. By this method of backward induction players could exclude “some cases of intuitively unreasonable equilibrium points for extensive games” (Selten, 1975, 33). Put more precisely “every finite extensive game with perfect recall has at least one perfect equilibrium point.” Economists later called this “sub-game perfect equilibrium”. By producing a method for how people would play sequential games Selten showed how to winnow out non-credible Nash equilibria. No reliance on some mystical focal point a la Schelling was required.
Much of the subsequent work in game theory has emulated Selten’s program of finding “refinements” to Nash equilibrium which allow the researcher to rule out non-credible behavior arising from the predictions of a model.
Yet what they mean by refinement is really a restriction. The more “refined” an equilibrium concept becomes the less general it is, and in some cases is the sign of the researcher’s effort to impose equilibrium on what he or she perceives as an inefficient and inappropriate outcome to the game. So for “refinement” think “ruling out”.
What Selten was ruling out was in fact the enormous efforts people go to in making their threats credible. If Corleone had thought Fanucci “crazy” enough to fight even though it deviated from the Nash equilibrium, Corleone’s best strategy would have been to not enter Fanucci’s turf and Fanucci would have benefitted from a better Nash equilibrium than he did by backing down. As he matured into a Don, Corleone would become very interested in whether his opponents were “men of stomach”, meaning that they might well play strategies that Selten would rule out as being non-credible. These men of stomach ended up getting their way in most conflicts because of their fearsome reputations, but sometimes they met a similar opponent and the result was a very inferior Nash equilibrium for both.
An excess of stomach is thus a way to attain equilibria outside the Selten framework but also can be the path to occasional disaster. On a clear and calm day in 1976 the British Navy frigate HMS Mermaid and the minesweeper HMS Fittleton, both functioning without impairment, crashed into each other while on a standard exercise in the North Sea. The sea is a big place and crashes between big ships on clear days might seem unlikely. In fact they are not. In 1899 the first class warship HMS Collingwood drove straight into the side of cruiser HMS Curacoa. Examples abound. Sea captains are unusually tough specimens, used to getting their way, mainly because they have to in order to be effective. Was there some excess of toughness, needed to garner the credibility to attain higher Nash equilibria that led in these instances to tragically inferior Nash equilibria? Such questions define a broad swath of human interactions, ranging from relations between neighbors to relations between nations. Selten’s work gave us at least some basis for thinking about the outcomes of these treacherous interactions.
The Harsanyi Renaissance
SELTEN WAS CONCERNED about multiple equilibria, but another problem plagued the Nash agenda. Everybody in the game had all the information about their opponents and their opponents about them. Von Neumann–Nash games were games of perfect information in a very specific sense. Even though you did not know how the game would pan out, you knew what your opponent’s payoffs and motivations were and thus what their strategies would be. In other words, you had the complete background picture. You might not be able to predict the outcome due to mixing but you would know how the game would be played.
But what if on the train ride from Victoria station to Canterbury, Holmes believed it possible that Moriarty might fall asleep between Canterbury and Dover, but that only Moriarty knew for sure how tired he really was? This was an added wrinkle. Fatigue could come on for reasons that had nothing to do with any strategizing by the players. The risk of fatigue multiplied the possibilities Holmes had to consider. Only Moriarty knew the real answer. One could even imagine a sprite, or an unpredictable Greek deity, or as Harsanyi called it more prosaically “Nature” being a third player in this game. Nature revealed only part of her hand to any one player, and only that player would know how nature’s quirks had influenced the potency of his or her strategy. From the point of view of the opponent without inside knowledge, nature split the effect of one strategy into as many different effects as nature had faces. Only the affected player knew the truth and the others had to guess the truth by forming an impression of the average potency of the other’s strategy. This average was more technically ca
lled an expectation.
John Harsanyi invented this sort of reasoning in the 1960s. He called his solution a “Bayesian equilibrium” in honour of an 18th century British cleric who showed how to include prior beliefs about your environment into measures of probability, though this is not really what his equilibrium concept was about. In Harsanyi’s equilibrium each player’s strategy maximizes his average or “expected” payoff, given his or her equilibrium beliefs about the probable influence that nature will have on the effect of whatever strategies others will choose.
Bayesian equilibrium is the key tool for taking account of the hidden information people have about how nature has touched them, or more technically about what “types” they have become. Using this tool Harsanyi was able to create an equilibrium concept that is really nothing other than a souped-up version of Nash equilibrium, and as such, along with Nash equilibrium, has the property of being self-fulfilling, at least in an average sense. As game theorists D’Asprémont and Gérard-Varet put it in 1995, in Bayesian equilibrium, “the players’ ‘conjectures’ about their mutual behavior are confirmed by the decisions taken by each on the basis of their private information.” This mutually confirming state is the analogue of the Nash equilibrium, so looking at things this way guaranteed at least one Nash equilibrium.
“And so what?” you might rightly ask, as did some economists fatigued by the endless and seemingly pointless theorizing of game theory. Yes, the theorems were interesting, and the field seemed full of promise just as did the newly created field of genetic engineering. But despite big promises, game theory seemed just as incapable as genetic engineer of “delivering”. Great visions abounded. But applications seemed as scarce as sightings of a yeti. It was important at this stage not to blink. For indeed the yeti was about, lurking just within reach of those in the intellectual hunt for relevance in game theory.
Fusion of game theory and information economics
WE HAVE SEEN so far that game theory took off in a blast of theorizing on the existence of equilibria in mixed strategies. In the 1940s and 50s von Neumann and Nash were the pilots at the helm of this mental rocket. Then came a period of consolidation in the 1960s by Reinhard Selten, who sought a theoretical means of ruling out equilibria that game theorists found not credible in games played over stages. Another consolidator was John Harsanyi who showed how to solve games with asymmetric information. Harsanyi’s work was the most important innovation in game theory since Nash, but this did not become evident until the 1970s. Then, from left field as it were, arose a new generation of young economists bent on questioning the hallowed presumptions of the theory of markets and perfect competition. Their approach had nothing to do with game theory. They were concerned with good old-fashioned equilibrium and welfare economics. They brought attention to two problems that plagued markets: lying and cheating.
You would think economists would have noticed the nuisance these darker sides of human nature posed for markets, but for some reason economic minds were otherwise occupied during the first seventy years of the 20th century. The new kids on the economic block were more street-wise than their predecessors. They were concerned about showing how lying and cheating, or more technically, “adverse selection” and “moral hazard”, harmed commercial markets and threatened the integrity of social organizations such as businesses, and even governments.
You can see that when you start talking about deception, notions of strategic interaction calling for game theoretic reasoning are not far away. What then exactly was the relation between information and game theorists? The answer was fairly simple. Information theory fixated on the consequences of deception. Game theory focused on the degree to which people would try to deceive each other in the quest for some prize. One studied the consequences, the other the processes leading to bad behavior. Despite these varying objectives both information theorists and game theorists soon realized they were dealing with asymmetric information. Information theorists understood the consequences of asymmetric information for market efficiency. Game theorists understood how much asymmetric information would emerge from market interactions. This mutual recognition of common ground led to the next stage of developments in game theory.
In the first part of this next stage information theorists learned how to use the techniques of Bayesian games to understand particular problems of adverse selection and moral hazard that were bothering them. This was the era of “signalling”, as discovered by Nobellist Michael Spence in 1973, which will be discussed at greater length later on.
Second, and more remarkably, game theorists used their knowledge of Bayesian solutions to transform games of lying and cheating into games where everyone was honest and obedient (which, as you might quickly grasp, is no game at all). Put differently, they created a sort of “reverse game theory” in which government manipulated the rules and rewards of games to neuter all strategic comportment. It was as if someone had invented the jet engine and then a team of engineers figured out how to dampen the sound by attaching speakers that sent waves of sound to perfectly counter the engine’s roar. Roger Myerson, David Kreps, Bengt Holmstrom, Thomas Mroz, Jonathan Ostroy, Sherwin Rosen, Theodore Groves, and about a dozen others who in greater or lesser degree came up at around the same time with the idea that games with Bayes equilibria could be hemmed about by incentives which made people tell the truth. There is no other precedent in economics for such a simultaneous eruption of discovery. The convergence of this intellectual pullulation, known as the “revelation principle”, is only now starting to be appreciated.
Ex ludis probitas et oboedentia
BEFORE GETTING INTO how information and game theory merged we need to learn a few terms from information economics and appreciate why some researchers bothered to invent them. Then we need to see how Spence’s informational model of signalling led to the fusion of game theory and information economics. We want to grasp how this fusion led to the neutralization of games through inverse game theory. In other words, we want to understand how by setting the rewards and rules of games to act as incentives for behavior, we can make people behave honestly and obediently. A Latin scholar would describe this situation as one of ex ludis probitas et oboedientia. Through games, honesty and obedience. What other science can boast such a motto?
Information economics is about lying and cheating. Lying is called adverse selection. Adverse selection arises when people misrepresent themselves in order to gain access to some group in a way that profits them at the expense of everyone else in the group. Academic plagiarism is a manifestation of the quest of some to obtain real credentials based on false achievement so that they might insinuate themselves into businesses, churches, or academia. Once ensconced, they draw a weekly check while riding upon the superior efforts and abilities of their fellow workers. Resentment and ultimately the demise of the institution which they populate may result.
At its heart, adverse selection is a problem of honesty. Dishonesty can bring down insurance companies. Some people want to hide the fact that they are high-risk types because they would have to pay higher premiums than low-risk types. An insurance company that fails to devise and enforce a contract that separates people into different risk categories may go bankrupt through a subtle process of in-migration of high-risk types to its policies and out-migration of low-risk types. To see this, consider that when high-risk clients sneak into a low-risk insurance pool by pretending to be low-risk, suddenly claims on the pool increase. Then premiums must rise to ensure the solvency of the pool. The premiums are still lower than what high-risk types would pay in their own pool, but higher now for low-risk types than what they would have paid without the added risk burden of helping to prop up high-risk clients. These premiums may drive some low-risk types to seek companies that better control adverse selection, leading to higher premiums for the people still remaining in the pool which chases out further low-risk types until all that are left are high-risk people in the market for insurance.
The separatin
g equilibrium problem plagues used car markets where lemons and sound vehicles are difficult to distinguish before purchase. Without a market mechanism, such as credible inspection certificates and 30-day guaranteed return policies, a separating equilibrium may not emerge. Instead, some people with sound vehicles will prefer to take them off the market because the presence of lemons depresses prices. As this process continues, soon most of what is left in the market are lemons. Of course there will always be gems to be found, but these are the exception rather than the rule in markets plagued by adverse selection, or “lemonitis”.
Adverse selection also afflicts social organizations where team effort determines some collectively sought-after result. Think of managers at a government health ministry. They work together to help the ministry provide efficient health services to citizens, but pointing to and then rewarding the output of any single manager is difficult, if not absurd, despite “performance management plans” that may be implemented.
The difficulty of measuring individual contributions exposes the ministry to the influx of managers who overstate their abilities and qualifications. When too many such managers are hired, the burden on good managers rises. They may leave and the ministry may fall into disrepute. To protect itself from such adverse selection, the ministry may invest hundreds of thousands of dollars to find a qualified manager.
The fundamental problem in all of these examples is that of finding a separating equilibrium based on the credible communication of information. In other words, how do we guarantee honesty so that our organizations do not topple under the burden of carrying light-weights? The problem may go beyond the honesty of applicants to include the honesty of employers who may accept bribes to let in under-qualified candidates. One of the reasons Napoleon’s armies clobbered the armies of continental Europe and Britain was that during La Revolution, the French instituted a system of officer selection based on merit. In Britain and on the continent, aspiring officers could and sometimes had to buy their commissions. The dishonesty here lay not with the applicant, but with the army, which by admitting inferior officers betrayed the trust of the people.