Operations Research and the Rise of Applied Game Theory – A Nobel for Milgrom and Wilson

Today’s Nobel Prize to Paul Milgrom and Robert Wilson is the capstone of an incredibly fruitful research line which began in the 1970s in a few small departments of Operations Research. Game theory, or the mathematical study of strategic interaction, dates back to work by Zermelo, Borel and von Neumann in the early 20th century. The famed book by von Neumann and Morganstern was published in 1944, and widely reviewed as one of the most important social scientific works of the century. And yet, it would be three decades before applications of game theory revolutionized antitrust, organizational policy, political theory, trade, finance, and more. Alongside the “credibility revolution” of causal econometrics, and to a lesser extent behavioral economics, applied game theory has been the most important development in economics in the past half century. The prize to Milgrom and Wilson is likely the final one that will go for early applied game theory, joining those in 1994, 2005, 2007, 2014 and 2016 that elevated the abstractions of the 1940s to today’s rigorous interpretations of so many previously disparate economic fields.

Neither Wilson nor Milgrom were trained in pure economics departments. Wilson came out of the decision sciences program of Howard Raiffa at Harvard, and Milgrom was a student of Wilson’s at Stanford Business School. However, the link between operations research and economics is a long one, with the former field often serving as a vector for new mathematical tools before the latter field was quite ready to accept them. In the middle of the century, the mathematics of optimal control and dynamic programming – how to solve problems where today’s action affects tomorrow’s possibilities – were applied to resource allocation by Kantorovich in the Soviet Union and to market economics problems in the West by Koopmans, Samuelson, Solow, and Dorfman. Luce and Raiffa explained how the theory of games and the ideas of Bayesian decision theory apply to social scientific problems. Stan Reiter’s group first at Purdue, then later with Nancy Schwartz at Kellogg MEDS, formally brought operations researchers and economists into the same department to apply these new mathematics to economic problems.

The real breakthrough, however, was the arrival of Bayesian games and subgame perfection from Harsanyi (1968) and Selten (1965, 1975). These tools in combination allow us to study settings where players signal, make strategic moves, bluff, attempt to deter, and so on. From the perspective of an institutional designer, they allow us, alongside Myerson’s revelation principle, to follow Hayek’s ideas formally and investigate how we should organize an economic activity given the differing information and possible actions of each player. Indeed, the Wilson Doctrine argues that practical application of game theory requires attention to these informational features. There remains a more complete intellectual history to be written here, but Paul Milgrom and Al Roth’s mutual interview of the JEP provides a great sense of the intellectual milieu of the 1970s as they developed their ideas. Wilson, the Teacher, and Milgrom, the Popularizer, were at the heart of showing just how widely these new tools in game theory could be applied.

Let us begin with the Popularizer. Milgrom was born and raised in Michigan, taking part in anti-war and anti-poverty protests as a radical student in Ann Arbor in the late 1960s. The 1960s were a strange time, and so Milgrom went straight from the world of student activism to the equally radical world of…working as an actuary for an insurance company. After enrolling in the MBA program at Stanford in the mid-1970s, he was invited to pursue a PhD under his co-laureate Robert Wilson, who, as we shall see, was pursuing an incredibly lucrative combination of operations research and economics with his students. It is hard to overstate how broad Milgrom’s contributions have been, both theoretically and in practice. But we can get a good taste by looking at four: the multitasking problem and the no-trade theorem on the theoretical side, and medieval guilds and modern spectrum auctions on the applied side.

It is perhaps surprising that Milgrom’s most-cited paper was published in the JLEO, well into his career. But the famed multitasking paper is so incredibly informative. The idea is simple: you can motivate someone either with direct rewards or by changing their opportunity cost. For instance, if you want a policeman to walk the beat more often, then make their office particularly dull and full of paperwork. Workers generally have many tasks they can work on, however, which vary in their relative costs. For example, a cop can slack off, arrest people on nonsense charges, or solve murders. Making their office dull will cause them to sit at their office desk for fewer hours, but it likely won’t cause them to solve murders rather than arrest people on nonsense charges. Why not just pay for the solved murders directly? Often it is impossible to measure or observe everything you want done.

If you “reward A while hoping for B”, as Steven Kerr’s famous management paper puts it, you are likely to get a lot of A. If you pay rewards for total arrests, your cops will cite people for riding bikes with no lights. So what can be done? Milgrom and Holmstrom give a simple model where workers exert effort, do some things you can measure and some which you cannot, and you get a payoff depending on both. If a job has some things you care about which are hard to measure, you should use fewer strong incentives on the things you can measure: by paying cops for arrests, you make the opportunity cost of solving murders for the cops who like doing this higher, because now they are giving up the reward they would get from arresting the bicyclists every time they work a murder! Further, you should give workers working on hard-to-measure tasks little job flexibility. The murder cop paid on salary should need to show her face in the office, while the meter maid getting paid based on how many tickets she gives already has a good reason not to shirk while on the clock. Once you start thinking about multitasking and the interaction of incentives with opportunity costs, you start seeing perverse incentives absolutely everywhere.

Milgrom’s writings on incentives within organizations are without a doubt the literature I draw on most heavily when teaching strategic management. It is a shame that the textbook written alongside John Roberts never caught on. For a taste of their basic view of management, check out “The Firm as an Incentive System”, which formally lays out formal incentives, asset ownership, and task assignments as a system of complements which make organizations function well. The field now known as organizational economics has grown to incorporate ideas like information transmission (Garicano 2000 JPE) and the link between relational contracts and firm culture (e.g., Gibbons and Henderson 2011). Yet there remain many questions on why firms are organized the way they are which are open to an enterprising graduate student with a good theoretical background.

Multitasking has a similar feel to many of Milgrom’s great papers: they provide a framework improving our intuition about some effect in the world, rather than just showing a mathematical curiosity. The same is true of his most famous finance paper, the “no-trade theorem” developed with Nancy Stokey. The idea is ex-post obvious but ex-ante incredibly surprising. Imagine that in the market for corn, there is free exchange, and all trades anyone wants to make (to mitigate risk, for use, to try to trade on private information, etc.) have been made. A farmer one day notices a blight on his crop, and suspects this blight is widespread in the region. Therefore, the supply of corn will fall. Can he profit from this insight? Milgrom-Stokey’s answer is no!

How could this be? Even if everyone had identical prior beliefs about corn supply, conditional on getting this information, the farmer definitely has a higher posterior belief about corn price come harvest season than everyone else. However, we assumed that before the farmer saw the blight, all gains from trade had been exhausted, and that it was common knowledge that this was so. The farmer offering to buy corn at a higher price is informative that the farmer has learned something. If the former price was $5/bushel, and the farmer offers you $7, then you know that he has received private information that the corn will be worth even more than $7, hence you should not sell him any. Now, of course there is trade on information all the time; indeed, there are huge sums spent collecting information so that it can be traded on! However, Milgrom-Stokey makes clear just how clear we have to be about what is causing the “common knowledge that all gains from trade were exhausted” assumption to fail. Models with “noise” traders, or models with heterogeneous prior beliefs (a very subtle philosophical issue), have built on Milgrom-Stokey to understand everything from asset bubbles to the collapse in trade in mortgage backed securities in 2008.

When it comes to practical application, Milgrom’s work on auctions is well-known, and formed the basis of his Nobel citation. How did auctions become so “practical”? There is no question that the rise of applied auction theory, with the economist as designer, has its roots in the privatization wave of the 1990s that followed the end of the Cold War. Governments held valuable assets: water rights, resource tracts, spectrum that was proving important for new technologies like the cell phone. Who was to be given these assets, and at what price? Milgrom’s 1995 Churchill lectures formed the basis for a book, “Putting Auction Theory to Work”, which is now essential reading alongside Klemperer’s “Theory and Practice”, for theorists and practitioners alike. Where it is unique is in its focus on the practical details of running auctions.

This focus is no surprise. Milgrom’s most famous theoretical work in his 1982 Econometrica with Robert Weber on optimal auctions which are partly common-value and partly private-value. That is, consider selling a house, where some of the value is your idiosyncratic taste, and some of the value is whether the house has mold. Milgrom and Weber show a seller should reduce uncertainty as much as possible about the “common” part of the value. If the seller does not know this information or can’t credibly communicate it, then unlike in auctions which don’t have that common component, it matters a lot whether how you run the auction. For instance, with a first-price auction, you may bid low even though you like the house because you worry about winning when other bidders noticed the mold and you didn’t. In a second-price auction, the price you pay incorporates in part that information from others, hence leads to more revenue for the homeseller.

In practical auctions more broadly, complements across multiple goods being sold separately, private information about common components, the potential to collude or form bidder rings, and the regularity with which auctions are held and hence the number of expected bidders are all incredibly important to auctioneer revenue and efficient allocation of the object being sold. I omit further details of precisely what Milgrom did in the many auctions he consulted on, as the popular press will cover this aspect of his work well, but it is not out of the question to say that the social value of better allocation of things like wireless spectrum is on the order of tens of billions of dollars.

One may wonder why we care about auctions at all. Why not just assign the item to whoever we wish, and then let the free market settle things such that the person with the highest willingness-to-pay winds up with the good? It seems natural to think that how the good is allocated matters for how much revenue the government earns – selling the object is better on this count than giving it away – but it turns out that the free market will not in general allocate goods efficiently when sellers and buyers are uncertain about who is willing to pay how much for a given object.

For instance, imagine you own a car, and you think I am willing to pay somewhere between $10,000 and $20,000 to buy it from you. I think you are willing to give up the car for somewhere between $5,000 and $15,000. I know my own valuation, so let’s consider the case where I am willing to pay exactly $10,000. If you are willing to sell for $8,000, it seems reasonable that we can strike a deal. This is not the case: since all you know is that I am willing to pay somewhere between $10,000 and $20,000, you do know you can always get a $2,000 profit by selling at $10,000, but also that it’s incredibly unlikely that I will say no if you charge $10,001, or $11,000, or even more. You therefore will be hesitant to strike the deal to sell for 10 flat. This essential tension is the famed Myerson-Satterthwaite Theorem, and it occurs precisely because the buyer and seller do not know each other’s value for the object. A government auctioning off an object initially, however, can do so efficiently in a much wider set of contexts (see Maskin 2004 JEL for details). The details of auction design cannot be fixed merely by letting the market sort things out ex-post: the post-Cold War asset sales had issues not just of equity, but also efficiency. Since auctions today are used to allocate everything from the right to extract water to carbon emissions permits at the heart of global climate change policy, ensuring we get their design right is not just a minor theoretical concern!

The problem of auction design today is, partly because of Milgrom’s efforts, equally prominent in computer science. Many allocation problems are computational, with players being algorithms. This is true of electricity markets in practice, as well as the allocation of online advertisements, the design of blockchain-like mechanisms for decentralized exchange and record-keeping, and methods for preventing denial of service attacks while permitting legitimate access to internet-connected servers. Even when humans remain in the loop to some extent, we need to guarantee not just an efficient algorithm, but a practically-computable equilibrium. Leyton-Brown, Milgrom and Segal discuss this in the context of a recent spectrum auction. The problem of computability turns out to be an old one: Robert Wilson’s early work was on precisely the problem of computing equilibria. Nonetheless, given its importance in algorithmic implementation of mechanisms, it would be no surprise to see many important results in applied game theory come from computer scientists and not just economists and mathematicians in coming years. This pattern of techniques flowing from their originating field to the one where they have important new applications looks a lot like the trail of applied game theory arriving in economics by way of operations research, does it not?

That deep results in game theory can inform the real world goes beyond cases like auctions, where the economic setting is easy to understand. Consider the case of the long distance trade in the Middle Ages. The fundamental problem is that of the Yuan dynasty folk song: when “heaven is high and the emperor is far away”, what stops the distant city you arrive in from confiscatory taxation, or outright theft, of your goods? Perhaps the threat that you won’t return to trade? This is not enough – you may not return, but other traders will be told, “we had to take the goods from the last guy because he broke some rules, but of course we will treat you fairly!” It was quite common for confiscation to be targeted only at one group – the Genoans in Constantinople, the Jews in Sicily – with all other traders being treated fairly.

The theory of repeated games can help explain what to do. It is easiest to reach efficiency when you punish not only the cheaters, but also punish those who do not themselves punish cheaters. That is, the Genoans need to punish not just the Turks by withdrawing business, but also punish the Saracens who would try to make up the trade after the Genoans pull out. The mechanism to do so is a merchant guild, a monopoly which can enforce boycotts in distant cities by taking away a given merchant’s rights in their own city. Greif, Milgrom and Weingast suggest that because merchant guilds allow cities to credibly commit to avoid confiscation, they benefit the cities themselves by increasing the amount of trade. This explains why cities encouraged the formations of guilds – one does not normally encourage your sellers to form a monopsony!

Enough on the student – let us turn to Milgrom’s advisor, Robert Wilson. Wilson was born in the tiny hamlet of Geneva, Nebraska. As discussed above, his doctoral training at Harvard was from Howard Raiffa and the decision theorists, after which he was hired at Stanford, where he has spent his career. As Milgrom is now also back at Stanford, their paths are so intertwined that the two men now quite literally live on the same street.

Wilson is most famous for his early work applying the advances of game theory in the 1970s to questions in auction design and reputation. His 3 page paper written in 1966 and published in Management Science in 1969 gives an early application of Harsanyi’s theory of Bayesian games to the “winner’s curse”. The winner’s curse means that the winner of an auction for a good with a “common value” – for instance, a tract of land that either has oil or does not – optimally bids less in a first-price auction than what they believe that good to be worth, or else loses money.

One benefit of being an operations researcher is that there is a tight link in that field between academia and industry. Wilson consulted with the Department of the Interior on oil licenses, and with private oil companies on how they bid in these auctions. What he noticed was that managers often shaded down their engineer’s best estimates of the value of an oil tract. The reason why is, as the paper shows, very straightforward. Assume we both get a signal uniformly distributed on [x-1,x+1] about the value of the tract, where x is the true value. Unconditionally, my best estimate of the value of the plot is exactly my signal. However, conditional on winning the auction, my signal was higher than my rivals. Therefore, if I knew my rival’s signal, I would have bid exactly halfway between the two. Of course, I don’t know her signal. But since my payoff is 0 if I don’t win, and my payoff is my bid minus x if I win, there is a straightforward formula, which depends on the distribution of the signals, for how much I should shade my bid. Many teachers have drawn on Bob’s famous example of the winner’s curse by auctioning off a jar of coins in class, the winner inevitably being the poor student who doesn’t realize they should have shaded their bid!

Wilson not only applied these new game theoretic tools, but also developed many of them. This is particularly true in 1982, when he published all three of his most cited papers: a resolution of the “Chain store paradox”, the idea of sequential equilibria, and the “Gang of Four” reputation paper with Kreps, Roberts, and Milgrom. To understand these, we need to understand the problem of non-credible threats.

The chain store paradox goes like this. Consider Walmart facing a sequence of potential competitors. If they stay out, Walmart earns monopoly profits in the town. If they enter, Walmart can either fight (in which case both make losses) or accept the entry (in which case they both earn duopoly profits, lower than what Walmart made as a monopolist). It seems intuitive that Walmart should fight a few early potential competitors to develop a reputation for toughness. Once they’ve done it, no one will enter. But if you think through the subgame perfect equilibrium here, the last firm who could enter knows that after they enter, Walmart is better off accepting the entry. Hence the second-to-last firm reasons that Walmart won’t benefit from establishing a reputation for deterrence, and hence won’t fight it. And likewise for the third-to-last entrant and so on up the line: Walmart never fights because it can’t “credibly” threaten to fight future entrants regardless of what it did in the past.

This seems odd. Kreps and Wilson (JET 1982) make an important contribution to reputation building by assuming there are two types of Walmart CEOs: a tough one who enjoys fighting, and a weak one with the normal payoffs above. Competitors don’t know which Walmart they are facing. If there is even a small chance the rivals think Walmart is tough, then even the weak Walmart may want to fight early rivals by “pretending” to be tougher than they are. Can this work as an equilibrium? We really need a new concept, because we both want the game to be perfect, where at any time, players play Nash equilibria from that point forward, and Bayesian, where players have beliefs about the others’ type and update those beliefs according to the hypothesized equilibrium play. Kreps and Wilson show how to do this in their Econometrica introducing sequential equilibria. The idea here is that equilibria involve strategies and beliefs at every node of the game tree, with both being consistent along the equilibrium path. Beyond having the nice property of allowing us to specifically examine the beliefs at any node, even off the equilibrium path, sequential equilibria are much simpler to compute than similar ideas like trembling hand perfection. Looking both back to Wilson’s early work on how to compute Nash equilibria, and Milgrom’s future work on practical mechanism design, is it not surprising to see the idea of practical tractability appear even back in 1982.

This type of reputation-building applies even to cooperation – or collusion, as cooperating when it is your interest to cheat and colluding when it is in your interest to undercut are the same mathematical problem. The Gang of Four paper by Kreps, Wilson, Milgrom, and Roberts shows that in finite prisoner’s dilemmas, you can get quite a bit of cooperation just with a small probability that your rival is an irrational type who always cooperates as long as you do so. Indeed, the Gang of Four show precisely how close to the end of the game players will cooperate for a given small belief that a rival is the naturally-cooperative type. Now, one may worry that allowing types in this way gives too much leeway for the modeler to justify any behavior, and indeed this is so. Nonetheless, the 1982 papers kicked off an incredibly fruitful search for justifications for reputation building – and given the role of reputation in everything from antitrust to optimal policy from central banks, a rigorous justification is incredibly important to understanding many features of the economic world.

I introduced Robert Wilson as The Teacher. This is not meant to devalue his pure research contributions, but rather to emphasize just how critical he was in developing students at the absolute forefront of applied games. Bengt Holmstrom did his PhD under Wilson in 1978, went to Kellogg MEDS after a short detour in Finland, then moved to Yale and MIT before winning the Nobel Prize. Al Roth studied with Wilson in 1974, was hired at the business school at Illinois, then Pittsburgh, then Harvard and Stanford before winning a Nobel Prize. Paul Milgrom was a 1979 student of Wilson’s, beginning also at MEDS before moving to Yale and Stanford, and winning his own Nobel Prize. This is to say nothing of his students developed later, including the great organizational theorist Bob Gibbons, or his earliest students like Armando Ortega Reichert, whose unpublished dissertation in 1969 contains important early results in auction theory and was an important influence on the limit pricing under incomplete information in Milgrom and Roberts (1982). It is one thing to write papers of Nobel quality. It is something else altogether to produce (at least!) three students who have done the same. And as any teacher is proud of their successful students, surely little is better than winning a Nobel alongside one of them!

Advertisement

The 2018 Fields Medal and its Surprising Connection to Economics!

The Fields Medal and Nevanlinna Prizes were given out today. They represent the highest honor possible for young mathematicians and theoretical computer scientists, and are granted only once every four years. The mathematics involved is often very challenging for outsiders. Indeed, the most prominent of this year’s winners, the German Peter Scholze, is best known for his work on “perfectoid spaces”, and I honestly have no idea how to begin explaining them aside from saying that they are useful in a number of problems in algebraic geometry (the lovely field mapping results in algebra – what numbers solve y=2x – and geometry – noting that those solutions to y=2x form a line). Two of this year’s prizes, however, the Fields given to Alessio Figalli and the Nevanlinna to Constantinos Daskalakis, have a very tight connection to an utterly core question in economics. Indeed, both of those men have published work in economics journals!

The problem of interest concerns how best to sell an object. If you are a monopolist hoping to sell one item to one consumer, where the consumer’s valuation of the object is only known to the consumer but commonly known to come from a distribution F, the mechanism that maximizes revenue is of course the Myerson auction from his 1981 paper in Math OR. The solution is simple: make a take it or leave it offer at a minimum price (or “reserve price”) which is a simple function of F. If you are selling one good and there are many buyers, then revenue is maximized by running a second-price auction with the exact same reserve price. In both cases, no potential buyer has any incentive to lie about their true valuation (the auction is “dominant strategy incentive compatible”). And further, seller revenue and expected payments for all players are identical to the Myerson auction in any other mechanism which allocates goods the same way in expectation, with minor caveats. This result is called “revenue equivalence”.

The Myerson paper is an absolute blockbuster. The revelation principle, the revenue equivalence theorem, and a solution to the optimal selling mechanism problem all in the same paper? I would argue it’s the most important result in economics since Arrow-Debreu-McKenzie, with the caveat that many of these ideas were “in the air” in the 1970s with the early ideas of mechanism design and Bayesian game theory. The Myerson result is also really worrying if you are concerned with general economic efficiency. Note that the reserve price means that the seller is best off sometimes not selling the good to anyone, in case all potential buyers have private values below the reserve price. But this is economically inefficient! We know that there exists an allocation mechanism which is socially efficient even when people have private information about their willingness to pay: the Vickrey-Clarke-Groves mechanism. This means that market power plus asymmetric information necessarily destroys social surplus. You may be thinking we know this already: an optimal monopoly price is classic price theory generates deadweight loss. But recall that a perfectly-price-discriminating monopolist sells to everyone whose willingness-to-pay exceeds the seller’s marginal cost of production, hence the only reason monopoly generates deadweight loss in a world with perfect information is that we constrain them to a “mechanism” called a fixed price. Myerson’s result is much worse: letting a monopolist use any mechanism, and price discriminate however they like, asymmetric information necessarily destroys surplus!

Despite this great result, there remain two enormous open problems. First, how should we sell a good when we will interact with the same buyer(s) in the future? Recall the Myerson auction involves bidders truthfully revealing their willingness to pay. Imagine that tomorrow, the seller will sell the same object. Will I reveal my willingness to pay truthfully today? Of course not! If I did, tomorrow the seller would charge the bidder with the highest willingness-to-pay exactly that amount. Ergo, today bidders will shade down their bids. This is called the “ratchet effect”, and despite a lot of progress in dynamic mechanism design, we have still not fully solved for the optimal dynamic mechanism in all cases.

The other challenging problem is one seller selling many goods, where willingness to pay for one good is related to willingness to pay for the others. Consider, for example, selling cable TV. Do you bundle the channels together? Do you offer a menu of possible bundles? This problem is often called “multidimensional screening”, because you are attempting to “screen” buyers such that those with high willingness to pay for a particular good actually pay a high price for that good. The optimal multidimensional screen is a devil of a problem. And it is here that we return to the Fields and Nevanlinna prizes, because they turn out to speak precisely to this problem!

What could possibly be the connection between high-level pure math and this particular pricing problem? The answer comes from the 18th century mathematician Gaspard Monge, founder of the Ecole Polytechnique. He asked the following question: what is the cheapest way to move mass from X to Y, such as moving apples from a bunch of distribution centers to a bunch of supermarkets. It turns out that without convexity or linearity assumptions, this problem is very hard, and it was not solved until the late 20th century. Leonid Kantorovich, the 1975 Nobel winner in economics, paved the way for this result by showing that there is a “dual” problem where instead of looking for the map from X to Y, you look for the probability that a given mass in Y comes from X. This dual turns out to be useful in that there exists an object called a “potential” which helps characterize the optimal transport problem solution in a much more tractable way than searching across any possible map.

Note the link between this problem and our optimal auction problem above, though! Instead of moving mass most cheaply from X to Y, we are looking to maximize revenue by assigning objects Y to people with willingness-to-pay drawn from X. So no surprise, the solution to the optimal transport problem when X has a particular structure and the solution to the revenue maximizing mechanism problem are tightly linked. And luckily for us economists, many of the world’s best mathematicians, including 2010 Fields winner Cedric Villani, and this year’s winner Alessio Figalli, have spent a great deal of effort working on exactly this problem. Ivar Ekeland has a nice series of notes explaining the link between the two problems in more detail.

In a 2017 Econometrica, this year’s Nevanlinna winner Daskalakis and his coauthors Alan Deckelbaum and Christos Tzamos, show precisely how to use strong duality in the optimal transport problem to solve the general optimal mechanism problem when selling multiple goods. The paper is very challenging, requiring some knowledge of measure theory, duality theory, and convex analysis. That said, the conditions they give to check an optimal solution, and the method to find the optimal solution, involve a reasonably straightforward series of inequalities. In particular, the optimal mechanism involves dividing the hypercube of potential types into (perhaps infinite) regions who get assigned the same prices and goods (for example, “you get good A and good B together with probability p at price X”, or “if you are unwilling to pay p1 for A, p2 for B, or p for both together, you get nothing”).

This optimal mechanism has some unusual properties. Remember that the Myerson auction for one buyer is “simple”: make a take it or leave it offer at the reserve price. You may think that if you are selling many items to one buyer, you would likewise choose a reserve price for the whole bundle, particularly when the number of goods with independently distributed values becomes large. For instance, if there are 1000 cable channels, and a buyer has value distributed uniformly between 0 and 10 cents for each channel, then by a limit theorem type argument it’s clear that the willingness to pay for the whole bundle is quite close to 50 bucks. So you may think, just price at a bit lower than 50. However, Daskalakis et al show that when there are sufficiently many goods with i.i.d. uniformly-distributed values, it is never optimal to just set a price for the whole bundle! It is also possible to show that the best mechanism often involves randomization, where buyers who report that they are willing to pay X for item a and Y for item b will only get the items with probability less than 1 at specified price. This is quite contrary to my intuition, which is that in most mechanism problems, we can restrict focus to deterministic assignment. It was well-known that multidimensional screening has weird properties; for example, Hart and Reny show that an increase in buyer valuations can cause seller revenue from the optimal mechanism to fall. The techniques Daskalakis and coauthors develop allow us to state exactly what we ought do in these situations previously unknown in the literature, such as when we know we need mechanisms more complicated than “sell the whole bundle at price p”.

The history of economics has been a long series of taking tools from the frontier of mathematics, from the physics-based analogues of the “marginalists” in the 1870s, to the fixed point theorems of the early game theorists, the linear programming tricks used to analyze competitive equilibrium in the 1950s, and the tropical geometry recently introduced to auction theory by Elizabeth Baldwin and Paul Klemperer. We are now making progress on pricing issues that have stumped some of the great theoretical minds in the history of the field. Multidimensional screening is an incredibly broad topic: how ought we regulate a monopoly with private fixed and marginal costs, how ought we tax agents who have private costs of effort and opportunities, how ought a firm choose wages and benefits, and so on. Knowing the optimum is essential when it comes to understanding when we can use simple, nearly-correct mechanisms. Just in the context of pricing, using related tricks to Daskalakis, Gabriel Carroll showed in a recent Econometrica that bundling should be avoided when the principal has limited knowledge about the correlation structure of types, and my old grad school friend Nima Haghpanah has shown, in a paper with Jason Hartline, that firms should only offer high-quality and low-quality versions of their products if consumers’ values for the high-quality good and their relative value for the low versus high quality good are positively correlated. Neither of these results are trivial to prove. Nonetheless, a hearty cheers to our friends in pure mathematics who continue to provide us with the tools we need to answer questions at the very core of economic life!

Kenneth Arrow Part II: The Theory of General Equilibrium

The first post in this series discussed Ken Arrow’s work in the broad sense, with particular focus on social choice. In this post, we will dive into his most famous accomplishment, the theory of general equilibrium (1954, Econometrica). I beg the reader to offer some sympathy for the approximations and simplifications that will appear below: the history of general equilibrium is, by this point, well-trodden ground for historians of thought, and the interpretation of history and theory in this area is quite contentious.

My read of the literature on GE following Arrow is as follows. First, the theory of general equilibrium is an incredible proof that markets can, in theory and in certain cases, work as efficiently as an all-powerful planner. That said, the three other hopes of general equilibrium theory since the days of Walras are, in fact, disproven by the work of Arrow and its followers. Market forces will not necessarily lead us toward these socially optimal equilibrium prices. Walrasian demand does not have empirical content derived from basic ordinal utility maximization. We cannot rigorously perform comparative statics on general equilibrium economic statistics without assumptions that go beyond simple utility maximization. From my read of Walras and the early general equilibrium theorists, all three of those results would be a real shock.

Let’s start at the beginning. There is an idea going back to Adam Smith and the invisible hand, an idea that individual action will, via the price system, lead to an increase or even maximization of economic welfare (an an aside, Smith’s own use of “invisible hand” trope is overstated, as William Grampp among others has convincingly argued). The kind of people who denigrate modern economics – the neo-Marxists, the back-of-the-room scribblers, the wannabe-contrarian-dilletantes – see Arrow’s work, and the idea of using general equilibrium theory to “prove that markets work”, as a barbarism. We know, and have known well before Arrow, that externalities exist. We know, and have known well before Arrow, that the distribution of income depends on the distribution of endowments. What Arrow was interested in was examining not only whether the invisible hand argument “is true, but whether it could be true”. That is, if we are to claim markets are uniquely powerful at organizing economic activity, we ought formally show that the market could work in such a manner, and understand the precise conditions under which it won’t generate these claimed benefits. How ought we do this? Prove the precise conditions under which there exists a price vector where markets clear, show the outcome satisfies some welfare criterion that is desirable, and note exactly why each of the conditions are necessary for such an outcome.

The question is, how difficult is it to prove these prices exist? The term “general equilibrium” has had many meanings in economics. Today, it is often used to mean “as opposed to partial equilibrium”, meaning that we consider economic effects allowing all agents to adjust to a change in the environment. For instance, a small random trial of guaranteed incomes has, as its primary effect, an impact on the incomes of the recipients; the general equilibrium effects of making such a policy widespread on the labor market will be difficult to discern. In the 19th and early 20th century, however, the term was much more concerned with the idea of the economy as a self-regulating system. Arrow put it very nicely in an encyclopedia chapter he wrote in 1966: general equilibrium is both “the simple notion of determinateness, that the relations which describe the economic system must form a system sufficiently complete to determine the values of its variables and…the more specific notion that each relation represents a balance of forces.”

If you were a classical, a Smith or a Marx or a Ricardo, the problem of what price will obtain in a market is simple to solve: ignore demand. Prices are implied by costs and a zero profit condition, essentially free entry. And we more or less think like this now in some markets. With free entry and every firm producing at the identical minimum efficient scale, price is entirely determined by the supply side, and only quantity is determined by demand. With one factor, labor where the Malthusian condition plays the role of free entry, or labor and land in the Ricardian system, this classical model of value is well-defined. How to handle capital and differentiated labor is a problem to be assumed away, or handled informally; Samuelson has many papers where he is incensed by Marx’s handling of capital as embodied labor.

The French mathematical economist Leon Walras finally cracked the nut by introducing demand and price-taking. There are household who produce and consume. Equilibrium involves supply and demand equating in each market, hence price is where margins along the supply and demand curves equate. Walras famously (and informally) proposed a method by which prices might actually reach equilibrium: the tatonnement. An auctioneer calls out a price vector: in some markets there is excess demand and in some excess supply. Prices are then adjusted one at a time. Of course each price change will affect excess demand and supply in other markets, but you might imagine things can “converge” if you adjust prices just right. Not bad for the 1870s – there is a reason Schumpeter calls this the “Magna Carta” of economic theory in his History of Economic Analysis. But Walras was mistaken on two counts: first, knowing whether there even exists an equilibrium that clears every market simultaneously is, it turns out, equivalent to a problem in Poincare’s analysis situs beyond the reach of mathematics in the 19th century, and second, the conditions under which tatonnement actually converges are a devilish problem.

The equilibrium existence problem is easy to understand. Take the simplest case, with all j goods made up of the linear combination of k factors. Demand equals supply just says that Aq=e, where q is the quantity of each good produced, e is the endowment of each factor, and A is the input-output matrix whereby product j is made up of some combination of factors k. Also, zero profit in every market will imply Ap(k)=p(j), where p(k) are the factor prices and p(j) the good prices. It was pointed out that even in this simple system where everything is linear, it is not at all trivial to ensure that prices and quantities are not negative. It would not be until Abraham Wald in the mid-1930s – later Arrow’s professor at Columbia and a fellow Romanian, links that are surely not a coincidence! – that formal conditions were shown giving existence of general equilibrium in a simple system like this one, though Wald’s proof greatly simplified by the general problem by imposing implausible restrictions on aggregate demand.

Mathematicians like Wald, trained in the Vienna tradition, were aghast at the state of mathematical reasoning in economics at the time. Oskar Morgenstern absolutely hammered the great economist John Hicks in a 1941 review of Hicks’ Value and Capital, particularly over the crazy assertion (similar to Walras!) that the number of unknowns and equations being identical in a general equilibrium system sufficed for a solution to exist (if this isn’t clear to you in a nonlinear system, a trivial example with two equations and two unknowns is here). Von Neumann apparently said (p. 85) to Oskar, in reference to Hicks and those of his school, “if those books are unearthed a hundred years hence, people will not believe they were written in our time. Rather they will think they are about contemporary with Newton, so primitive is the mathematics.” And Hicks was quite technically advanced compared to his contemporary economists, bringing the Keynesian macroeconomics and the microeconomics of indifference curves and demand analysis together masterfully. Arrow and Hahn even credit their initial interest in the problems of general equilibrium to the serendipity of coming across Hicks’ book.

Mathematics had advanced since Walras, however, and those trained at the mathematical frontier finally had the tools to tackle Walras’ problem seriously. Let D(p) be a vector of demand for all goods given price p, and e be initial endowments of each good. Then we simply need D(p)=e or D(p)-e=0 in each market. To make things a bit harder, we can introduce intermediate and factor goods with some form of production function, but the basic problem is the same: find whether there exists a vector p such that a nonlinear equation is equal to zero. This is the mathematics of fixed points, and Brouwer had, in 1912, given a nice theorem: every continuous function from a compact convex subset to itself has a fixed point. Von Neumann used this in the 1930s to prove a similar result to Wald. A mathematician named Shizuo Kakutani, inspired by von Neumann, extended the Brouwer result to set-valued mappings called correspondences, and John Nash in 1950 used that result to show, in a trivial proof, the existence of mixed equilibria in noncooperative games. The math had arrived: we had the tools to formally state when non-trivial non-linear demand and supply systems had a fixed point, and hence a price that cleared all markets. We further had techniques for handling “corner solutions” where demand for a given good was zero at some price, surely a common outcome in the world: the idea of the linear program and complementary slackness, and its origin in convex set theory as applied to the dual, provided just the mathematics Arrow and his contemporaries would need.

So here we stood in the early 1950s. The mathematical conditions necessary to prove that a set-valued function has an equilibrium have been worked out. Hicks, in Value and Capital, has given Arrow the idea that relating the future to today is simple: just put a date on every commodity and enlarge the commodity space. Indeed, adding state-contingency is easy: put an index for state in addition to date on every commodity. So we need not only zero excess demand in apples, or in apples delivered in May 1955, but in apples delivered in May 1955 if Eisenhower loses his reelection bid. Complex, it seems, but no matter: the conditions for the existence of a fixed point will be the same in this enlarged commodity space.

With these tools in mind, Arrow and Debreu can begin their proof. They first define a generalization of an n-person game where the feasible set of actions for each player depends on the actions of every other player; think of the feasible set as “what can I afford given the prices that will result for the commodities I am endowed with?” The set of actions is an n-tuple where n is the number of date and state indexed commodities a player could buy. Debreu showed in 1952 PNAS that these generalized games have an equilibrium as long as each payoff function varies continuously with other player’s actions, the feasible set of choices convex and varies continuously in other player’s actions, and the set of actions which improve a player’s payoff are convex for every action profile. Arrow and Debreu then show that the usual implications on individual demand are sufficient to aggregate up to the conditions Debreu’s earlier paper requires. This method is much, much different from what is done by McKenzie or other early general equilibrium theorists: excess demand is never taken as a primitive. This allows the Arrow-Debreu proof to provide substantial economic intuition as Duffie and Sonnenschein point out in a 1989 JEL. For instance, showing that the Arrow-Debreu equilibrium exists even with taxation is trivial using their method but much less so in methods that begin with excess demand functions.

This is already quite an accomplishment: Arrow and Debreu have shown that there exists a price vector that clears all markets simultaneously. The nature of their proof, as later theorists will point out, relies less on convexity on preferences and production sets as on the fact that every agent is “small” relative to the market (convexity is used to get continuity in the Debreu game, and you can get this equally well by making all consumers infinitesimal and then randomizing allocations to smooth things out; see Duffie and Sonnenschein above for an example). At this point, it’s the mid-1950s, heyday of the Neoclassical synthesis: surely we want to be able to answer questions like, when there is a negative demand shock, how will the economy best reach a Pareto-optimal equilibrium again? How do different speeds of adjustment due to sticky prices or other frictions affect the rate at which optimal is regained? Those types of question implicitly assume that the equilibrium is unique (at least locally) so that we actually can “return” to where we were before the shock. And of course we know some of the assumptions needed for the Arrow-Debreu proof are unrealistic – e.g., no fixed costs in production – but we would at least like to work out how to manipulate the economy in the “simple” case before figuring out how to deal with those issues.

Here is where things didn’t work out as hoped. Uzawa (RESTUD, 1960) proved that not only could Brouwer’s theorem be used to prove the existence of general equilibrum, but that the opposite was true as well: the existence of general equilibrium was logically equivalent to Brouwer. A result like this certainly makes one worry about how much one could say about prices in general equilibrium. The 1970s brought us the Sonnenschein-Mantel-Debreu “Anything Goes” theorem: aggregate excess demand functions do not inherit all the properties of individual excess demand functions because of wealth effects (when relative prices change, the value of one’s endowment changes as well). For any aggregate excess demand function satisfying a couple minor restrictions, there exists an economy with individual preferences generating that function; in particular, fewer restrictions than are placed on individual excess demand as derived from individual preference maximization. This tells us, importantly, that there is no generic reason for equilibria to be unique in an economy.

Multiplicity of equilibria is a problem: if the goal of GE was to be able to take underlying primitives like tastes and technology, calculate “the” prices that clear the market, then examine how those prices change (“comparative statics”), we essentially lose the ability to do all but local comparative statics since large changes in the environment may cause the economy to jump to a different equilibrium (luckily, Debreu (1970, Econometrica) at least generically gives us a finite number of equilibria, so we may at least be able to say something about local comparative statics for very small shocks). Indeed, these analyses are tough without an equilibrium selection mechanism, which we don’t really have even now. Some would say this is no big deal: of course the same technology and tastes can generate many equilibria, just as cars may wind up all driving on either the left or the right in equilibrium. And true, all of the Arrow-Debreu equilibria are Pareto optimal. But it is still far afield from what might have been hoped for in the 1930s when this quest for a modern GE theory began.

Worse yet is stability, as Arrow and his collaborators (1958, Ecta; 1959, Ecta) would help discover. Even if we have a unique equilibrium, Herbert Scarf (IER, 1960) showed, via many simple examples, how Walrasian tatonnement can lead to cycles which never converge. Despite a great deal of the intellectual effort in the 1960s and 1970s, we do not have a good model of price adjustment even now. I should think we are unlikely to ever have such a theory: as many theorists have pointed out, if we are in a period of price adjustment and not in an equilibrium, then the zero profit condition ought not apply, ergo why should there be “one” price rather than ten or a hundred or a thousand?

The problem of multiplicity and instability for comparative static analysis ought be clear, but it should also be noted how problematic they are for welfare analysis. Consider the Second Welfare Theorem: under the Arrow-Debreu system, for every Pareto optimal allocation, there exists an initial endowment of resources such that that allocation is an equilibrium. This is literally the main justification for the benefits of the market: if we reallocate endowments, free exchange can get us to any Pareto optimal point, ergo can get us to any reasonable socially optimal point no matter what social welfare function you happen to hold. How valid is this justification? Call x* the allocation that maximizes some social welfare function. Let e* be an initial endowment for which x* is an equilibrium outcome – such an endowment must exist via Arrow-Debreu’s proof. Does endowing agents with e* guarantee we reach that social welfare maximum? No: x* may not be unique. Even if it unique, will we reach it? No: if it is not a stable equilibrium, it is only by dint of luck that our price adjustment process will ever reach it.

So let’s sum up. In the 1870s, Walras showed us that demand and supply, with agents as price takers, can generate supremely useful insights into the economy. Since demand matters, changes in demand in one market will affect other markets as well. If the price of apples rises, demand for pears will rise, as will their price, whose secondary effect should be accounted for in the market for apples. By the 1930s we have the beginnings of a nice model of individual choice based on constrained preference maximization. Taking prices as given, individual demands have well-defined forms, and excess demand in the economy can be computed by a simple summing up. So we now want to know: is there in fact a price that clears the market? Yes, Arrow and Debreu show, there is, and we needn’t assume anything strange about individual demand to generate this. These equilibrium prices always give Pareto optimal allocations, as had long been known, but there also always exist endowments such that every Pareto optimal allocation is an equilibria. It is a beautiful and important result, and a triumph for the intuition of the invisible hand it its most formal sense.

Alas, it is there we reach a dead end. Individual preferences alone do not suffice to tell us what equilibria we are at, nor that any equilibria will be stable, nor that any equilibria will be reached by an economically sensible adjustment process. To say anything meaningful about aggregate economic outcomes, or about comparative statics after modest shocks, or about how technological changes change price, we need to make assumptions that go beyond individual rationality and profit maximization. This is, it seems to me, a shock for the economists of the middle of the century, and still a shock for many today. I do not think this means “general equilibrium is dead” or that the mathematical exploration in the field was a waste. We learned a great deal about precisely when markets could even in principle achieve the first best, and that education was critical for the work Arrow would later do on health care, innovation, and the environment, which I will discuss in the next two posts. And we needn’t throw out general equilibrium analysis because of uniqueness or stability problems, any more than we would throw out game theoretic analysis because of the same problems. But it does mean that individual rationality as the sole paradigm of economic analysis is dead: it is mathematically proven that postulates of individual rationality will not allow us to say anything of consequence about economic aggregates or game theoretic outcomes in the frequent scenarios where we do not have a unique equilibria with a well-defined way to get there (via learning in games, or a tatonnament process in GE, or something of a similar nature). Arrow himself (1986, J. Business) accepts this: “In the aggregate, the hypothesis of rational behavior has in general no implications.” This is an opportunity for economists, not a burden, and we still await the next Arrow who can guide us on how to proceed.

Some notes on the literature: For those interested in the theoretical development of general equilibrium, I recommend General Equilibrium Analysis by Roy Weintraub, a reformed theorist who now works in the history of thought. Wade Hands has a nice review of the neoclassical synthesis and the ways in which Keynesianism and GE analysis were interrelated. On the battle for McKenzie to be credited alongside Arrow and Debreu, and the potentially scandalous way Debreu may have secretly been responsible for the Arrow and Debreu paper being published first, see the fine book Finding Equilibrium by Weintraub and Duppe; both Debreu and McKenzie have particularly wild histories. Till Duppe, a scholar of Debreu, also has a nice paper in the JHET on precisely how Arrow and Debreu came to work together, and what the contribution of each to their famous ’54 paper was.

Nobel Prize 2016 Part I: Bengt Holmstrom

The Nobel Prize in Economics has been announced, and what a deserving prize it is: Bengt Holmstrom and Oliver Hart have won for the theory of contracts. The name of this research weblog is “A Fine Theorem”, and it would be hard to find two economists whose work is more likely to elicit such a description! Both are incredibly deserving; more than five years ago on this site, I discussed how crazy it was that Holmstrom had yet to win!. The only shock is the combination: a more natural prize would have been Holmstrom with Paul Milgrom and Robert Wilson for modern applied mechanism design, and Oliver Hart with John Moore and Sandy Grossman for the theory of the firm. The contributions of Holmstrom and Hart are so vast that I’m splitting this post into two, so as to properly cover the incredible intellectual accomplishments of these two economists.

The Finnish economist Bengt Holmstrom did his PhD in operations research at Stanford, advised by Robert Wilson, and began his career at my alma mater, the tiny department of Managerial Economics and Decision Sciences at Northwestern’s Kellogg School. To say MEDS struck gold with their hires in this era is an extreme understatement: in 1978 and 1979 alone, they hired Holmstrom and his classmate Paul Milgrom (another Wilson student from Stanford), hired Nancy Stokey promoted Nobel laureate Roger Myerson to Associate Professor, and tenured an adviser of mine, Mark Satterthwaite. And this list doesn’t even include other faculty in the late 1970s and early 1980s like eminent contract theorist John Roberts, behavioralist Colin Camerer, mechanism designer John Ledyard or game theorist Ehud Kalai. This group was essentially put together by two senior economists at Kellogg, Nancy Schwartz and Stanley Reiter, who had the incredible foresight to realize both that applied game theory was finally showing promise of tackling first-order economic questions in a rigorous way, and that the folks with the proper mathematical background to tackle these questions were largely going unhired since they often did their graduate work in operations or mathematics departments rather than traditional economics departments. This market inefficiency, as it were, allowed Nancy and Stan to hire essentially every young scholar in what would become the field of mechanism design, and to develop a graduate program which combined operations, economics, and mathematics in a manner unlike any other place in the world.

From that fantastic group, Holmstrom’s contribution lies most centrally in the area of formal contract design. Imagine that you want someone – an employee, a child, a subordinate division, an aid contractor, or more generally an agent – to perform a task. How should you induce them to do this? If the task is “simple”, meaning the agent’s effort and knowledge about how to perform the task most efficiently is known and observable, you can simply pay a wage, cutting off payment if effort is not being exerted. When only the outcome of work can be observed, if there is no uncertainty in how effort is transformed into outcomes, knowing the outcome is equivalent to knowing effort, and hence optimal effort can be achieved via a bonus payment made on the basis of outcomes. All straightforward so far. The trickier situations, which Holmstrom and his coauthors analyzed at great length, are when neither effort nor outcomes are directly observable.

Consider paying a surgeon. You want to reward the doctor for competent, safe work. However, it is very difficult to observe perfectly what the surgeon is doing at all times, and basing pay on outcomes has a number of problems. First, the patient outcome depends on the effort of not just one surgeon, but on others in the operating room and prep table: team incentives must be provided. Second, the doctor has many ways to shift the balance of effort between reducing costs to the hospital, increasing patient comfort, increasing the quality of the medical outcome, and mentoring young assistant surgeons, so paying on the basis of one or two tasks may distort effort away from other harder-to-measure tasks: there is a multitasking problem. Third, the number of medical mistakes, or the cost of surgery, that a hospital ought expect from a competent surgeon depends on changes in training and technology that are hard to know, and hence a contract may want to adjust payments for its surgeons on the performance of surgeons elsewhere: contracts ought take advantage of relevant information when it is informative about the task being incentivized. Fourth, since surgeons will dislike risk in their salary, the fact that some negative patient outcomes are just bad luck means that you will need to pay the surgeon very high bonuses to overcome their risk aversion: when outcome measures involve uncertainty, optimal contracts will weigh “high-powered” bonuses against “low-powered” insurance against risk. Fifth, the surgeon can be incentivized either by payments today or by keeping their job tomorrow, and worse, these career concerns may cause the surgeon to waste the hospital’s money on tasks which matter to the surgeon’s career beyond the hospital.

Holmstrom wrote the canonical paper on each of these topics. His 1979 paper in the Bell Journal of Economics shows that any information which reduces the uncertainty about what an agent actually did should feature in a contract, since by reducing uncertainty, you reduce the risk premium needed to incentivize the agent to accept the contract. It might seem strange that contracts in many cases do not satisfy this “informativeness principle”. For instance, CEO bonuses are often not indexed to the performance of firms in the same industry. If oil prices rise, essentially all oil firms will be very profitable, and this is true whether or not a particular CEO is a good one. Bertrand and Mullainathan argue that this is because many firms with diverse shareholders are poorly governed!

The simplicity of contracts in the real world may have more prosaic explanations. Jointly with Paul Milgrom, the famous “multitasking” paper published in JLEO in 1991 notes that contracts shift incentives across different tasks in addition to serving as risk-sharing mechanisms and as methods for inducing effort. Since bonuses on task A will cause agents to shift effort away from hard-to-measure task B, it may be optimal to avoid strong incentives at all (just pay teachers a salary rather than a bonus based only on test performance) or to split job tasks (pay bonuses to teacher A who is told to focus only on math test scores, and pay salary to teacher B who is meant to serve as a mentor). That outcomes are generated by teams also motivates simpler contracts. Holmstrom’s 1982 article on incentives in teams, published in the Bell Journal, points out that if both my effort and yours is required to produce a good outcome, then the marginal product of our efforts are both equal to the entire value of what is produced, hence there is not enough output to pay each of us our marginal product. What can be done? Alchian and Demsetz had noticed this problem in 1972, arguing that firms exist to monitor the effort of individuals working in teams. With perfect knowledge of who does what, you can simply pay the workers a wage sufficient to make the optimal effort, then collect the residual as profit. Holmstrom notes that the monitoring isn’t the important bit: rather, even shareholder controlled firms where shareholders do no monitoring at all are useful. The reason is that shareholders can be residual claimants for profit, and hence there is no need to fully distribute profit to members of the team. Free-riding can therefore be eliminated by simply paying team members a wage of X if the team outcome is optimal, and 0 otherwise. Even a slight bit of shirking by a single agent drops their payment precipitously (which is impossible if all profits generated by the team are shared by the team), so the agents will not shirk. Of course, when there is uncertainty about how team effort transforms into outcomes, this harsh penalty will not work, and hence incentive problems may require team sizes to be smaller than that which is first-best efficient. A third justification for simple contracts is career concerns: agents work hard today to try to signal to the market that they are high quality, and do so even if they are paid a fixed wage. This argument had been made less formally by Fama, but Holmstrom (in a 1982 working paper finally published in 1999 in RESTUD) showed that this concern about the market only completely mitigates moral hazard if outcomes within a firm were fully observable to the market, or the future is not discounted at all, or there is no uncertainty about agent’s abilities. Indeed, career concerns can make effort provision worse; for example, agents may take actions to signal quality to the market which are negative for their current firm! A final explanation for simple contracts comes from Holmstrom’s 1987 paper with Milgrom in Econometrica. They argue that simple “linear” contracts, with a wage and a bonus based linearly on output, are more “robust” methods of solving moral hazard because they are less susceptible to manipulation by agents when the environment is not perfectly known. Michael Powell, a student of Holmstrom’s now at Northwestern, has a great set of PhD notes providing details of these models.

These ideas are reasonably intuitive, but the way Holmstrom answered them is not. Think about how an economist before the 1970s, like Adam Smith in his famous discussion of the inefficiency of sharecropping, might have dealt with these problems. These economists had few tools to deal with asymmetric information, so although economists like George Stigler analyzed the economic value of information, the question of how to elicit information useful to a contract could not be discussed in any systematic way. These economists would have been burdened by the fact that the number of contracts one could write are infinite, so beyond saying that under a contract of type X does not equate marginal cost to marginal revenue, the question of which “second-best” contract is optimal is extraordinarily difficult to answer in the absence of beautiful tricks like the revelation principle partially developed by Holmstrom himself. To develop those tricks, a theory of how individuals would respond to changes in their joint incentives over time was needed; the ideas of Bayesian equilibria and subgame perfection, developed by Harsanyi and Selten, were unknown before the 1960s. The accretion of tools developed by pure theory finally permitted, in the late 1970s and early 1980s, an absolute explosion of developments of great use to understanding the economic world. Consider, for example, the many results in antitrust provided by Nobel winner Jean Tirole, discussed here two years ago.

Holmstrom’s work has provided me with a great deal of understanding of why innovation management looks the way it does. For instance, why would a risk neutral firm not work enough on high-variance moonshot-type R&D projects, a question Holmstrom asks in his 1989 JEBO Agency Costs and Innovation? Four reasons. First, in Holmstrom and Milgrom’s 1987 linear contracts paper, optimal risk sharing leads to more distortion by agents the riskier the project being incentivized, so firms may choose lower expected value projects even if they themselves are risk neutral. Second, firms build reputation in capital markets just as workers do with career concerns, and high variance output projects are more costly in terms of the future value of that reputation when the interest rate on capital is lower (e.g., when firms are large and old). Third, when R&D workers can potentially pursue many different projects, multitasking suggests that workers should be given small and very specific tasks so as to lessen the potential for bonus payments to shift worker effort across projects. Smaller firms with fewer resources may naturally have limits on the types of research a worker could pursue, which surprisingly makes it easier to provide strong incentives for research effort on the remaining possible projects. Fourth, multitasking suggests agent’s tasks should be limited, and that high variance tasks should be assigned to the same agent, which provides a role for decentralizing research into large firms providing incremental, safe research, and small firms performing high-variance research. That many aspects of firm organization depend on the swirl of conflicting incentives the firm and the market provide is a topic Holmstrom has also discussed at length, especially in his beautiful paper “The Firm as an Incentive System”; I shall reserve discussion of that paper for a subsequent post on Oliver Hart.

Two final light notes on Holmstrom. First, he is the source of one of my favorite stories about Paul Samuelson, the greatest economic theorist of all time. Samuelson was known for having a steel trap of a mind. At a light trivia session during a house party for young faculty at MIT, Holmstrom snuck in a question, as a joke, asking for the name of the third President of independent Finland. Samuelson not only knew the name, but apparently was also able to digress on the man’s accomplishments! Second, I mentioned at the beginning of this post the illustrious roster of theorists who once sat at MEDS. Business school students are often very hesitant to deal with formal models, partially because they lack a technical background but also because there is a trend of “dumbing down” in business education whereby many schools (of course, not including my current department at The University of Toronto Rotman!) are more worried about student satisfaction than student learning. With perhaps Stanford GSB as an exception, it is inconceivable that any school today, Northwestern included, would gather such an incredible collection of minds working on abstract topics whose applicability to tangible business questions might lie years in the future. Indeed, I could name a number of so-called “top” business schools who have nobody on their faculty who has made any contribution of note to theory! There is a great opportunity for a Nancy Schwartz or Stan Reiter of today to build a business school whose students will have the ultimate reputation for rigorous analysis of social scientific questions.

Reinhard Selten and the making of modern game theory

Reinhard Selten, it is no exaggeration, is a founding father of two massive branches of modern economics: experiments and industrial organization. He passed away last week after a long and idiosyncratic life. Game theory as developed by the three co-Nobel laureates Selten, Nash, and Harsanyi is so embedded in economic reasoning today that, to a great extent, it has replaced price theory as the core organizing principle of our field. That this would happen was not always so clear, however.

Take a look at some canonical papers before 1980. Arrow’s Possibility Theorem simply assumed true preferences can be elicited; not until Gibbard and Satterthwaite do we answer the question of whether there is even a social choice rule that can elicit those preferences truthfully! Rothschild and Stiglitz’s celebrated 1976 essay on imperfect information in insurance markets defines equilibria in terms of a individual rationality, best responses in the Cournot sense, and free entry. How odd this seems today – surely the natural equilibrium in an insurance market depends on beliefs about the knowledge held by others, and beliefs about those beliefs! Analyses of bargaining before Rubinstein’s 1982 breakthrough nearly always rely on axioms of psychology rather than strategic reasoning. Discussions of predatory pricing until the 1970s, at the very earliest, relied on arguments that we now find unacceptably loose in their treatment of beliefs.

What happened? Why didn’t modern game-theoretic treatment of strategic situations – principally those involve more than one agent but less than an infinite number, although even situations of perfect competition now often are motivated game theoretically – arrive soon after the proofs of von Neumann, Morganstern, and Nash? Why wasn’t the Nash program, of finding justification in self-interested noncooperative reasoning for cooperative or axiom-driven behavior, immediately taken up? The problem was that the core concept of the Nash equilibrium simply permits too great a multiplicity of outcomes, some of which feel natural and others of which are less so. As such, a long search, driven essentially by a small community of mathematicians and economists, attempted to find the “right” refinements of Nash. And a small community it was: I recall Drew Fudenberg telling a story about a harrowing bus ride at an early game theory conference, where a fellow rider mentioned offhand that should they crash, the vast majority of game theorists in the world would be wiped out in one go!

Selten’s most renowned contribution came in the idea of perfection. The concept of subgame perfection was first proposed in a German-language journal in 1965 (making it one of the rare modern economic classics inaccessible to English speakers in the original, alongside Maurice Allais’ 1953 French-language paper in Econometrica which introduces the Allais paradox). Selten’s background up to 1965 is quite unusual. A young man during World War II, raised Protestant but with one Jewish parent, Selten fled Germany to work on farms, and only finished high school at 20 and college at 26. His two interests were mathematics, for which he worked on the then-unusual extensive form game for his doctoral degree, and experimentation, inspired by the small team of young professors at Frankfurt trying to pin down behavior in oligopoly through small lab studies.

In the 1965 paper, on demand inertia (paper is gated), Selten wrote a small game theoretic model to accompany the experiment, but realized there were many equilibria. The term “subgame perfect” was not introduced until 1974, also by Selten, but the idea itself is clear in the ’65 paper. He proposed that attention should focus on equilibria where, after every action, each player continues to act rationally from that point forward; that is, he proposed that in every “subgame”, or every game that could conceivably occur after some actions have been taken, equilibrium actions must remain an equilibrium. Consider predatory pricing: a firm considers lowering price below cost today to deter entry. It is a Nash equilibrium for entrants to believe the price would continue to stay low should they enter, and hence to not enter. But it is not subgame perfect: the entrant should reason that after entering, it is not worthwhile for the incumbent to continue to lose money once the entry has already occurred.

Complicated strings of deductions which rule out some actions based on faraway subgames can seem paradoxical, of course, and did even to Selten. In his famous Chain Store paradox, he considers a firm with stores in many locations choosing whether to price aggressively to deter entry, with one potential entrant in each town choosing one at a time whether to enter. Entrants prefer to enter if pricing is not aggressive, but prefer to remain out otherwise; incumbents prefer to price nonaggressively either if entry occurs or not. Reasoning backward, in the final town we have the simple one-shot predatory pricing case analyzed above, where we saw that entry is the only subgame perfect equilibria. Therefore, the entrant in the second-to-last town knows that the incumbent will not fight entry aggressively in the final town, hence there is no benefit to doing so in the second-to-last town, hence entry occurs again. Reasoning similarly, entry occurs everywhere. But if the incumbent could commit in advance to pricing aggressively in, say, the first 10 towns, it would deter entry in those towns and hence its profits would improve. Such commitment may not possible, but what if the incumbent’s reasoning ability is limited, and it doesn’t completely understand why aggressive pricing in early stages won’t deter the entrant in the 16th town? And what if entrants reason that the incumbent’s reasoning ability is not perfectly rational? Then aggressive pricing to deter entry can occur.

That behavior may not be perfectly rational but rather bounded had been an idea of Selten’s since he read Herbert Simon as a young professor, but in his Nobel Prize biography, he argues that progress on a suitable general theory of bounded rationality has been hard to come by. The closest Selten comes to formalizing the idea is in his paper on trembling hand perfection in 1974, inspired by conversations with John Harsanyi. The problem with subgame perfection had been noted: if an opponent takes an action off the equilibrium path, it is “irrational”, so why should rationality of the opponent be assumed in the subgame that follows? Harsanyi assumes that tiny mistakes can happen, putting even rational players into subgames. Taking the limit as mistakes become infinitesimally rare produces the idea of trembling-hand perfection. The idea of trembles implicitly introduces the idea that players have beliefs at various information sets about what has happened in the game. Kreps and Wilson’s sequential equilibrium recasts trembles as beliefs under uncertainty, and showed that a slight modification of the trembling hand leads to an easier decision-theoretic interpretation of trembles, an easier computation of equilibria, and an outcome that is nearly identical to Selten’s original idea. Sequential equilibria, of course, goes on to become to workhorse solution concept in dynamic economics, a concept which underscores essentially all of modern industrial organization.

That Harsanyi, inventor of the Bayesian game, is credited by Selten for inspiring the trembling hand paper is no surprise. The two had met at a conference in Jerusalem in the mid-1960s, and they’d worked together both on applied projects for the US military, and on pure theory research while Selten visiting Berkeley. A classic 1972 paper of theirs on Nash bargaining with incomplete information (article is gated) begins the field of cooperative games with incomplete information. And this was no minor field: Roger Myerson, in his paper introducing mechanism design under incomplete information – the famous Bayesian revelation principle paper – shows that there exists a unique Selten-Harsanyi bargaining solution under incomplete information which is incentive compatible.

Myerson’s example is amazing. Consider building a bridge which costs $100. Two people will use the bridge. One values the bridge at $90. The other values the bridge at $90 with probability .9, and $30 with probability p=.1, where that valuation is the private knowledge of the second person. Note that in either case, the bridge is worth building. But who should pay? If you propose a 50/50 split, the bridge will simply not be built 10% of the time. If you propose an 80/20 split, where even in their worst case situation each person gets a surplus value of ten dollars, the outcome is unfair to player one 90% of the time (where “unfair” will mean, violates certain principles of fairness that Nash, and later Selten and Harsanyi, set out axiomatically). What of the 53/47 split that gives each party, on average, the same split? Again, this is not “interim incentive compatible”, in that player two will refuse to pay in the case he is the type that values the bridge only at $30. Myerson shows mathematically that both players will agree once they know their private valuations to the following deal, and that the deal satisfies the Selten-Nash fairness axioms: when player 2 claims to value at $90, the payment split is 49.5/50.5 and the bridge is always built, but when player 2 claims to value at $30, the entire cost is paid by player 1 but the bridge is built with only probability .439. Under this split, there are correct incentives for player 2 to always reveal his true willingness to pay. The mechanism means that there is a 5.61 percent chance the bridge isn’t built, but the split of surplus from the bridge nonetheless does better than any other split which satisfies all of Harsanyi and Selten’s fairness axioms.

Selten’s later work is, it appears to me, more scattered. His attempt with Harsanyi to formalize “the” equilibrium refinement, in a 1988 book, was a valiant but in the end misguided attempt. His papers on theoretical biology, inspired by his interest in long walks among the wildflowers, are rather tangential to his economics. And what of his experimental work? To understand Selten’s thinking, read this fascinating dialogue with himself that Selten gave as a Schwartz Lecture at Northwestern MEDS. In this dialogue, he imagines a debate between a Bayesian economist, experimentalist, and an evolutionary biologist. The economist argues that “theory without theorems” is doomed to fail, that Bayesianism is normatively “correct”, and the Bayesian reasoning can easily be extended to include costs of reasoning or reasoning mistakes. The experimentalist argues that ad hoc assumptions are better than incorrect ones: just as human anatomy is complex and cannot be reduced to a few axioms, neither can social behavior. The biologist argues that learning a la Nelson and Winter is descriptively accurate as far as how humans behave, whereas high level reasoning is not. The “chairman”, perhaps representing Selten himself, sums up the argument as saying that experiments which simply contradict Bayesianism are a waste of time, but that human social behavior surely depends on bounded rationality and hence empirical work ought be devoted to constructing a foundation for such a theory (shall we call this the “Selten program”?). And yet, this essay was from 1990, and we seem no closer to having such a theory, nor does it seem to me that behavioral research has fundamentally contradicted most of our core empirical understanding derived from theories with pure rationality. Selten’s program, it seems, remains not only incomplete, but perhaps not even first order; the same cannot be said of his theoretical constructs, as without perfection a great part of modern economics simply could not exist.

Douglass North, An Economist’s Historian

Sad news today arrives, as we hear that Douglass North has passed away, living only just longer than his two great compatriots in Cliometrics (Robert Fogel) and New Institutional Economics (Ronald Coase). There will be many lovely pieces today, I’m sure, on North’s qualitative and empirical exploration of the rise of institutions as solutions to agency and transaction cost problems, a series of ideas that continues to be enormously influential. No economist today denies the importance of institutions. If economics is the study of the aggregation of rational choice under constraints, as it is sometimes thought to be, then North focused our mind on the origin of the constraints rather the choice or its aggregation. Why do states develop? Why do guilds, and trade laws, and merchant organizations, and courts, appear, and when? How does organizational persistence negatively affect the economy over time, a question pursued at great length by Daron Acemoglu and his coauthors? All important questions, and it is not clear that there are better answers than the ones North provided.

But North was not, first and foremost, a historian. His PhD is in economics, and even late in life he continued to apply the very most cutting edge economic tools to his studies of institutions. I want to discuss today a beautiful piece of his, “The Role of Institutions in the Revival of Trade”, written jointly with Barry Weingast and Paul Milgrom in 1990. This is one of the fundamental papers in “Analytic Narratives”, as it would later be called, a school which applied formal economic theory to historical questions; I have previously discussed here a series of papers by Avner Greif and his coauthors which are the canonical examples.

Here is the essential idea. In the late middle ages, long distance trade, particularly at “Fairs” held in specific places at specific times, arose again in Western Europe. Agency problems must have been severe: how do you keep people from cheating you, from stealing, from selling defective goods, or from reneging on granted credit? A harmonized body of rules, the Merchant Law, appeared across many parts of Western Europe, with local courts granting judgments on the basis of this Law. In the absence of nation-states, someone with a negative judgment could simply leave the local city where the verdict was given. The threat of not being able to sell in the future may have been sufficient to keep merchants fair, but if the threat of future lost business was the only credible punishment, then why were laws and courts needed at all? Surely merchants could simply let it be known that Johann or Giuseppe is a cheat, and that one shouldn’t deal with them? There is a puzzle here, then: it appears that the set of punishments the Merchant Law could give are identical to the set of “punishments” one receives for having a bad reputation, so why then did anybody bother with courts and formal rules? In terms of modern theory, if relational contracts and formal contracts can offer identical punishments for deviating from cooperation, and formal contracts are costly, then why doesn’t everyone simply rely on relational contracts?

Milgrom, North and Weingast consider a simple repeated Prisoner’s Dilemma. Two agents with a sufficiently high discount rate can sustain cooperation in a Prisoner’s Dilemma using tit-for-tat: if you cheat me today, I cheat you tomorrow. Of course, the Folk Theorem tells us that cooperation can be sustained using potentially more complex punishment strategies in infinitely repeated games with any number of players, although a fundamental idea in the repeated games literature is that it may be necessary to punish people who do not themselves punish when they are meant to do so. In a repeated prisoner’s dilemma with an arbitrary number of players who randomly match each period, cooperation can be sustained in a simple way: you cheat anyone you match with if they cheated their previous trading partner and their previous trading partner did not themselves cheat their partner two rounds ago, and otherwise cooperate.

The trick, though, is that you need to know the two-periods-back history of your current trading partner and their last trading partner. Particularly with long-distance trade, you might frequently encounter traders you don’t know even indirectly. Imagine that every period you trade with someone you have never met before, and who you will never meet again (the “Townsend turnpike”, with two infinite lines of traders moving in opposite directions), and imagine that you do not know the trading history of anyone you match with. In this incomplete information game, there is no punishment for cheating: you cheat the person you match with today, and no one you meet with tomorrow will ever directly or indirectly learn about this. Hence cooperation is not sustained.

What we need, then, is an institution that first collects a sufficient statistic for the honesty of traders you might deal with, that incentivizes merchants to bother to check this sufficient statistic and punish people who have cheated, and that encourages people to report if they have been cheated even if this reporting is personally costly. That is, “institutions must be designed both to keep the traders adequately informed of their responsibilities and to motivate them to do their duties.”

Consider an institution LM. When you are matched with a trading partner, you can query LM at cost Q to find out if there are any “unpaid judgments” against your trading partner, and this query is common knowledge to you and your partner. You and your partner then play a trading game which is a Prisoner’s Dilemma. After trading, and only if you paid the query cost Q, when you have been cheated you can pay another cost C to take your trading partner to trial. If your partner cheated you in the Prisoner’s Dilemma and you took them to trial, you win a judgment penalty of J which the cheater can either voluntarily pay you at cost c(J) or which the cheater can ignore. If the cheater doesn’t pay a judgment, LM lists them as having “unpaid judgments”.

Milgrom, North and Weingast show that, under certain conditions, the following is an equilibrium where everyone always cooperates: if you have no unpaid judgments, you always query LM. If no one queries LM, or if there are unpaid judgments against your trading partner, you defect in the Prisoner’s Dilemma, else you cooperate. If both parties queried LM and only one defects in the Prisoner’s Dilemma, the other trader pays cost C and takes the cheater to the LM for judgment. The conditions needed for this to be an equilibrium are that penalties for cheating are high enough, but not so high that cheaters prefer to retire to the countryside rather than pay them, and that the cost of querying LM is not too high. Note how the LM equilibrium encourages anyone to pay the personal cost of checking their trading partner’s history: if you don’t check, then you can’t go to LM for judgment if you are cheated, hence you will definitely be cheated. The LM also encourages people to pay the personal cost of putting a cheater on trial, because that is the only way to get a judgment decision, and that judgment is actually paid in equilibrium. Relying on reputation in the absence of an institution may not work if communicating reputation of someone who cheated you is personally costly: if you need to print up posters that Giuseppe cheated you, but can otherwise get no money back from Giuseppe, you are simply “throwing good money after bad” and won’t bother. The LM institution provides you an incentive to narc on the cheats.

Note also that in equilibrium, the only cost of the system is the cost of querying, since no one cheats. That is, in the sense of transactions costs, the Law Merchant may be a very low-cost institution: it generates cooperation even though only one piece of information, the existence of unpaid judgments, needs to be aggregated and communicated, and it generates cooperation among a large set of traders that never personally interact by using a single centralized “record-keeper”. Any system that induces cooperation must, at a minimum, inform a player whether their partner has cheated in the past. The Law Merchant system does this with no other costs in equilibrium, since in equilibrium, no one cheats, no one goes for judgment, and no resources are destroyed paying fines.

That historical institutions develop largely to limit transactions costs is a major theme in North’s work, and this paper is a beautiful, highly formal, explication of that broad Coasean idea. Our motivating puzzle – why use formal institutions when reputation provides precisely the same potential for punishment? – can be answered simply by noting that reputation requires information, and the cost-minimizing incentive-compatible way to aggregate and share that information may require an institution. The Law Merchant arises not because we need a way to punish offenders, since in the absence of the nation-state the Law Merchant offers no method for involuntary punishment beyond those that exist in its absence; and yet, in its role reducing costs in the aggregation of information, the Law proves indispensable. What a beautiful example of how theory can clarify our observations!

“The Role of Institutions in the Revival of Trade” appeared in Economics and Politics 1.2, March 1990, and extensions of these ideas to long distance trade with many centers are considered in the papers by Avner Greif and his coauthors linked at the beginning of this post. A broad philosophical defense of the importance of transaction costs to economic history is North’s 1984 essay in the Journal of Institutional and Theoretical Economics. Two other titans of economics have also recently passed away, I’m afraid. Herbert Scarf, the mathematician whose work is of fundamental importance to modern market design, was eulogized by Ricky Vohra and Al Roth. Nate Rosenberg, who with Zvi Griliches was the most important thinker on the economics of invention, was memorialized by Joshua Gans and Joel West.

The Economics of John Nash

I’m in the midst of a four week string of conferences and travel, and terribly backed up with posts on some great new papers, but I can’t let the tragic passing today of John Nash go by without comment. When nonacademics ask what I do, I often say that I work in a branch of applied math called game theory; if you say you are economist, the man on the street expects you to know when unemployment will go down, or which stocks they should buy, or whether monetary expansion will lead to inflation, questions which the applied theorist has little ability to answer in a satisfying way. But then, if you mention game theory, without question the most common way your interlocutor knows the field is via Russell Crowe’s John Nash character in A Beautiful Mind, so surely, and rightfully, no game theorist has greater popular name recognition.

Now Nash’s contributions to economics are very small, though enormously influential. He was a pure mathematician who took only one course in economics in his studies; more on this fortuitous course shortly. The contributions are simple to state: Nash founded the theory of non-cooperative games, and he instigated an important, though ultimately unsuccessful, literature on bargaining. Nash essentially only has two short papers on each topic, each of which is easy to follow for a modern reader, so I will generally discuss some background on the work rather than the well-known results directly.

First, non-cooperative games. Robert Leonard has a very interesting intellectual history of the early days of game theory, the formal study of strategic interaction, which begins well before Nash. Many like to cite von Neumann’s “Zur Theorie der Gesellschaftsspiele” (“A Theory of Parlor Games”), from whence we have the minimax theorem, but Emile Borel in the early 1920’s, and Ernst Zermelo with his eponymous theorem a decade earlier, surely form relevant prehistory as well. These earlier attempts, including von Neumann’s book with Morganstern, did not allow general investigation of what we now call noncooperative games, or strategic situations where players do not attempt to collude. The most famous situation of this type is the Prisoner’s Dilemma, a simple example, yet a shocking one: competing agents, be they individuals, firms or countries, may (in a sense) rationally find themselves taking actions which both parties think is worse than some alternative. Given the U.S. government interest in how a joint nuclear world with the Soviets would play out, analyzing situations of that type was not simply a “Gesellschaftsspiele” in the late 1940s; Nash himself was funded by the Atomic Energy Commission, and RAND, site of a huge amount of important early game theory research, was linked to the military.

Nash’s insight was, in retrospect, very simple. Consider a soccer penalty kick, where the only options are to kick left and right for the shooter, and to simultaneously dive left or right for the goalie. Now at first glance, it seems like there can be no equilibrium: if the shooter will kick left, then the goalie will jump to that side, in which case the shooter would prefer to shoot right, in which case the goalie would prefer to switch as well, and so on. In real life, then, what do we expect to happen? Well, surely we expect that the shooter will sometimes shoot left and sometimes right, and likewise the goalie will mix which way she dives. That is, instead of two strategies for each player, we have a continuum of mixed strategies, where a mixed strategy is simply a probability distribution over the strategies “Left, Right”. This idea of mixed strategies “convexifies” the strategy space so that we can use fixed point strategies to guarantee that an equilibrium exists in every finite-strategy noncooperative game under expected utility (Kakutani’s Fixed Point in the initial one-page paper in PNAS which Nash wrote his very first year of graduate school, and Brouwer’s Fixed Point in the Annals of Math article which more rigorously lays out Nash’s noncooperative theory). Because of Nash, we are able to analyze essentially whatever nonstrategic situation we want under what seems to be a reasonable solution concept (I optimize given my beliefs about what others will do, and my beliefs are in the end correct). More importantly, the fixed point theorems Nash used to generate his equilibria are now so broadly applied that no respectable economist should now get a PhD without understanding how they work.

(A quick aside: it is quite interesting to me that game theory, as opposed to Walrasian/Marshallian economics, does not derive from physics or other natural sciences, but rather from a program at the intersection of formal logic and mathematics, primarily in Germany, primarily in the early 20th century. I still have a mind to write a proper paper on this intellectual history at some point, but there is a very real sense in which economics post-Samuelson, von Neumann and Nash forms a rather continuous methodology with earlier social science in the sense of qualitative deduction, whereas it is our sister social sciences which, for a variety of reasons, go on writing papers without the powerful tools of modern logic and the mathematics which followed Hilbert. When Nash makes claims about the existence of equilibria due to Brouwer, the mathematics is merely the structure holding up and extending ideas concerning the interaction of agents in noncooperative systems that would have been totally familiar to earlier generations of economists who simply didn’t have access to tools like the fixed point theorems, in the same way that Samuelson and Houthakker’s ideas on utility are no great break from earlier work aside from their explicit incorporation of deduction on the basis of relational logic, a tool unknown to economists in the 19th century. That is, I claim the mathematization of economics in the mid 20th century represents no major methodological break, nor an attempt to ape the natural sciences. Back to Nash’s work in the direct sense.)

Nash only applies his theory to one game: a simplified version of poker due to his advisor called Kuhn Poker. It turned out that the noncooperative solution was not immediately applicable, at least to the types of applied situations where it is now commonplace, without a handful of modifications. In my read of the intellectual history, noncooperative games was a bit of a failure outside the realm of pure math in its first 25 years because we still needed Harsanyi’s purification theorem and Bayesian equilibria to understand what exactly was going on with mixed strategies, Reinhard Selten’s idea of subgame perfection to reasonably analyze games with multiple stages, and the idea of mechanism design of Gibbard, Vickers, Myerson, Maskin, and Satterthwaite (among others) to make it possible to discuss how institutions affect outcomes which are determined in equilibrium. It is not simply economists that Nash influenced; among many others, his work directly leads to the evolutionary games of Maynard Smith and Price in biology and linguistics, the upper and lower values of his 1953 results have been used to prove other mathematical results and to discuss what is meant as truth in philosophy, and Nash is widespread in the analysis of voting behavior in political science and international relations.

The bargaining solution is a trickier legacy. Recall Nash’s sole economics course, which he took as an undergraduate. In that course, he wrote a term paper, eventually to appear in Econometrica, where he attempted to axiomatize what will happen when two parties bargain over some outcome. The idea is simple. Whatever the bargaining outcome is, we want it to satisfy a handful of reasonable assumptions. First, since ordinal utility is invariant to affine transformations of a utility function, the bargaining outcome should not be affected by these types of transformations: only ordinal preferences should matter. Second, the outcome should be Pareto optimal: the players would have to mighty spiteful to throw away part of the pie rather than give it to at least one of them. Third, given their utility functions players should be treated symmetrically. Fourth (and a bit controversially, as we will see), Nash insisted on Independence of Irrelevant Alternatives, meaning that if f(T) is the set of “fair bargains” when T is the set of all potential bargains, then if the potential set of bargains is smaller yet still contains f(T), say S strictly contained by T where f(T) is in S, then f(T) must remain the barganing outcome. It turns out that under these assumptions, there is a unique outcome which maximizes (u(x)-u(d))*(v(x)-v(d)), where u and v are each player’s utility functions, x is the vector of payoffs under the eventual bargain, and d the “status-quo” payoff if no bargain is made. This is natural in many cases. For instance, if two identical agents are splitting a dollar, then 50-50 is the only Nash outcome. Uniqueness is not at all obvious: recall the Edgeworth box and you will see that individual rationality and Pareto optimality alone leave many potential equilibria. Nash’s result is elegant and surprising, and it is no surprise that Nash’s grad school recommendation letter famously was only one sentence long: “This man is a genius.”

One problem with Nash bargaining, however. Nash was famously bipolar in real life, but there is an analogous bipolar feel to the idea of Nash equilibrium and the idea of Nash bargaining: where exactly are threats in Nash’s bargain theory? That is, Nash bargaining as an idea completely follows from the cooperative theory of von Neumann and Morganstern. Consider two identical agents splitting a dollar once more. Imagine that one of the agents already has 30 cents, so that only 70 of the cents are actually in the middle of the table. The Nash solution is that the person who starts with the thirty cents eventually winds up with 65 cents, and the other person with 35. But play this out in your head.

Player 1: “I, already having the 30 cents, should get half of what remains. It is only fair, and if you don’t give me 65 I will walk away from this table and we will each get nothing more.”

Player 2: “What does that have to do with it? The fair outcome is 50 cents each, which leaves you with more than your originally thirty, so you can take your threat and go jump off a bridge.”

That is, 50/50 might be a reasonable solution here, right? This might make even more sense if we take a more concrete example: bargaining over wages. Imagine the prevailing wage for CEOs in your industry is $250,000. Two identical CEOs will generate $500,000 in value for the firm if hired. CEO Candidate One has no other job offer. CEO Candidate Two has an offer from a job with similar prestige and benefits, paying $175,000. Surely we can’t believe that the second CEO will wind up with higher pay, right? It is a completely noncredible threat to take the $175,000 offer, hence it shouldn’t affect the bargaining outcome. A pet peeve of mine is that many applied economists are still using Nash bargaining – often in the context of the labor market! – despite this well-known problem.

Nash was quite aware of this, as can be seen by his 1953 Econometrica, where he attempts to give a noncooperative bargaining game that reaches the earlier axiomatic outcome. Indeed, this paper inspired an enormous research agenda called the Nash Program devoted to finding noncooperative games which generate well-known or reasonable-sounding cooperative solution outcomes. In some sense, the idea of “implementation” in mechanism design, where we investigate whether there exists a game which can generate socially or coalitionally preferred outcomes noncooperatively, can be thought of as a successful modern branch of the Nash program. Nash’s ’53 noncooperative game simply involves adding a bit of noise into the set of possible outcomes. Consider splitting a dollar again. Let a third party tell each player to name how many cents they want. If the joint requests are feasible, then the dollar is split (with any remainder thrown away), else each player gets nothing. Clearly every split of the dollar on the Pareto frontier is a Nash equilibrium, as is each player requesting the full dollar and getting nothing. However, if there is a tiny bit of noise about whether there is exactly one dollar, or .99 cents, or 1.01 cents, etc., when deciding whether to ask for more money, I will have to weigh the higher payoff if the joint demand is feasible against the payoff zero if my increased demand makes the split impossible and hence neither of us earn anything. In a rough sense, Nash shows that as the distribution of noise becomes degenerate around the true bargaining frontier, players will demand exactly their Nash bargaining outcome. Of course it is interesting that there exists some bargaining game that generates the Nash solution, and the idea that we should study noncooperative games which implement cooperate solution concepts is without a doubt seminal, but this particular game seems very strange to me, as I don’t understand what the source of the noise is, why it becomes degenerate, etc.

On the shoulders of Nash, however, bargaining progressed a huge amount. Three papers in particular are worth your time, although hopefully you have seen these before: Kalai and Smorodinsky 1975 who retaining the axiomatic approach but drop IIA, Rubinstein’s famous 1982 Econometrica on noncooperative bargaining with alternative offers, and Binmore, Rubinstein and Wolinsky on implementation of bargaining solutions which deals with the idea of threats as I did above.

You can read all four Nash papers in the original literally during your lunch hour; this seems to me a worthy way to tip your cap toward a man who literally helped make modern economics possible.

“The Power of Communication,” D. Rahman (2014)

(Before getting to Rahman’s paper, a quick note on today’s Clark Medal, which went to Roland Fryer, an economist at Harvard who is best known for his work on the economics of education. Fryer is no question a superstar, and is unusual in leaving academia temporarily while still quite young to work for the city of New York on improving their education policy. His work is a bit outside my interests, so I will leave more competent commentary to better informed writers.

The one caveat I have, however, is the same one I gave last year: the AEA is making a huge mistake in essentially changing this prize from “Best Economist Under 40” to “Best Applied Microeconomist Under 40”. Of the past seven winners, the only one who isn’t obviously an applied microeconomist is Levin, and yet even he describes himself as “an applied economist with interests in industrial organization, market design and the economics of technology.” It’s not that Saez, Duflo, Levin, Finkelstein, Chetty, Gentzkow and Fryer are doing bad work – their research is all of very high quality and by no means “cute-onomics” – but simply that the type of research they do is a very small subset of what economists work on. This style of work is particularly associated with the two Cambridge schools, and it’s no surprise that all of the past seven winners either did their PhD or postdoc in Cambridge. Where are the macroeconomists, when Europe is facing unemployment rates upwards of 30% in some regions? Where are the finance and monetary folks, when we just suffered the worst global recession since the 1930s? Where are the growth economists, when we have just seen 20 years of incredible economic growth in the third world? Where are the historians? Where are the theorists, microeconomic and econometric, on whose backs the applied work winning the prizes are built? Something needs to change.)

Enough bellyaching. Let’s take a look at Rahman’s clever paper, which might be thought as “when mediators are bad for society”; I’ll give you another paper shortly about “when mediators are good”. Rahman’s question is simple: can firms maintain collusion without observing what other firms produce? You might think this would be tricky if the realized price only imperfectly reflects total production. Let the market price p be a function of total industry production q plus an epsilon term. Optimally, we would jointly produce the monopoly quantity and split the rents. However, the epsilon term means that simply observing the market price doesn’t tell my firm whether the other firm cheated and produced too much.

What can be done? Green and Porter (1984), along with Abreu, Pearce and Stacchetti two years later, answered that collusion can be sustained: just let the equilibrium involve a price war if the market price drops below a threshold. Sannikov and Skrzypacz provided an important corollary, however: if prices can be monitored continuously, then collusion unravels. Essentially, if actions to increase production can be taken continuously, the price wars required to prevent cheating must be so frequent that join profit from sometimes colluding and sometimes fighting price wars is worse than joint profit than from just playing static Cournot.

Rahman’s trick saves collusion even when, as is surely realistic, cheaters can act in continuous time. Here is how it works. Let there be a mediator – an industry organization or similar – who can talk privately to each firm. Colluding firms alternate who is producing at any given time, with the one producing firm selling the monopoly level of output. The firms who are not supposed to produce at time t obviously have an incentive to cheat and produce a little bit anyway. Once in a while, however, the mediator tells the firm who is meant to produce in time t to produce a very large amount. If the price turns out high, the mediator gives the firm that was meant to produce a very large amount less time in the future to act as the monopolist, whereas if the price turns out low, the mediator gives that firm more monopolist time in the future. The latter condition is required to incentivize the producing firm to actually ramp up production when told to do so. Either a capacity constraint, or a condition on the demand function, is required to keep the producing firm from increasing production too much.

Note that if a nonproducing firm cheats and produce during periods you were meant to be producing 0, and the mediator happens to secretly ask the temporary monopolist firm to produce a large amount, you are just increasing the probability that the other firm gets to act as the monopolist in the future while you just get to produce zero. Even better, since the mediator only occasionally asks the producing firm to overproduce, and other firms don’t know when this time might be, the nonproducing firms are always wary of cheating. That is, the mediator’s ability to make private recommendations permits more scope for collusion than firms who only options are to punish based on continuously-changing public prices, because there are only rare yet unknown times when cheating could be detected. What’s worse for policymakers, the equilibrium here which involves occasional overproduction shows that such overproduction is being used to help maintain collusion, not to deviate from it; add overproduction to Green-Porter price wars as phenomena which look like collusion breaking down but are instead collusion being maintained.

Final working paper (RePEc IDEAS). Final version published in AER 2014. If you don’t care about proof details, the paper is actually a very quick read. Perhaps no surprise, but the results in this paper are very much related to those in Rahman’s excellent “Who will Monitor the Monitor?” which was discussed on this site four years ago.

“Epistemic Game Theory,” E. Dekel & M. Siniscalchi (2014)

Here is a handbook chapter that is long overdue. The theory of epistemic games concerns a fairly novel justification for solution concepts under strategic uncertainty – that is, situations where what I want to do depends on other people do, and vice versa. We generally analyze these as games, and have a bunch of equilibrium (Nash, subgame perfection, etc.) and nonequilibrium (Nash bargain, rationalizability, etc.) solution concepts. So which should you use? I can think of four classes of justification for a game solution. First, the solution might be stable: if you told each player what to do, no one person (or sometimes group) would want to deviate. Maskin mentions this justification is particularly worthy when it comes to mechanism design. Second, the solution might be the outcome of a dynamic selection process, such as evolution or a particular learning rule. Third, the solution may be justified by certain axiomatic first principles; Shapley value is a good example in this class. The fourth class, however, is the one we most often teach students: a solution concept is good because it is justified by individual behavior assumptions. Nash, for example, is often thought to be justified by “rationality plus correct beliefs”. Backward induction is similarly justified by “common knowledge of rationality at all states.”

Those are informal arguments, however. The epistemic games (or sometimes, “interactive epistemology”) program seeks to formally analyze assumptions about the knowledge and rationality of players and what it implies for behavior. There remain many results we don’t know (for instance, I asked around and could only come up with one paper on the epistemics of coalitional games), but the results proven so far are actually fascinating. Let me give you three: rationality and common belief in rationality implies rationalizable strategies are played, the requirements for Nash are different depending on how players there are, and backward induction is surprisingly difficult to justify on epistemic grounds.

First, rationalizability. Take a game and remove any strictly dominated strategy for each player. Now in the reduced game, remove anything that is strictly dominated. Continue doing this until nothing is left to remove. The remaining strategies for each player are “rationalizable”. If players can hold any belief they want about what potential “types” opponents may be – where a given (Harsanyi) type specifies what an opponent will do – then as long as we are all rational, we all believe the opponents are rational, we all believe the opponents all believe that we all are rational, ad infinitum, the only possible outcomes to the game are the rationalizable ones. Proving this is actually quite complex: if we take as primitive the “hierarchy of beliefs” of each player (what do I believe my opponents will do, what do I believe they believe I will do, and so on), then we need to show that any hierarchy of beliefs can be written down in a type structure, then we need to be careful about how we define “rational” and “common belief” on a type structure, but all of this can be done. Note that many rationalizable strategies are not Nash equilibria.

So what further assumptions do we need to justify Nash? Recall the naive explanation: “rationality plus correct beliefs”. Nash takes us from rationalizability, where play is based on conjectures about opponent’s play, to an equilibrium, where play is based on correct conjectures. But which beliefs need to be correct? With two players and no uncertainty, the result is actually fairly straightforward: if our first order beliefs are (f,g), we mutually believe our first order beliefs are (f,g), and we mutually believe we are rational, then beliefs (f,g) represent a Nash equilibrium. You should notice three things here. First, we only need mutual belief (I know X, and you know I know X), not common belief, in rationality and in our first order beliefs. Second, the result is that our first-order beliefs are that a Nash equilibrium strategy will be played by all players; the result is about beliefs, not actual play. Third, with more than two players, we are clearly going to need assumptions about how my beliefs about our mutual opponent are related to your beliefs; that is, Nash will require more, epistemically, than “basic strategic reasoning”. Knowing these conditions can be quite useful. For instance, Terri Kneeland at UCL has investigated experimentally the extent to which each of the required epistemic conditions are satisfied, which helps us to understand situations in which Nash is harder to justify.

Finally, how about backward induction? Consider a centipede game. The backward induction rationale is that if we reached the final stage, the final player would defect, hence if we are in the second-to-last stage I should see that coming and defect before her, hence if we are in the third-to-last stage she will see that coming and defect before me, and so on. Imagine that, however, player 1 does not defect in the first stage. What am I to infer? Was this a mistake or am I perhaps facing an irrational opponent? Backward induction requires that I never make such an inference, and hence I defect in stage 2.

Here is a better justification for defection in the centipede game, though. If player 1 doesn’t defect in the first stage, then I “try my best” to retain a belief in his rationality. That is, if it is possible for him to have some belief about my actions in the second stage which rationally justified his first stage action, then I must believe that he holds those beliefs. For example, he may believe that I believe he will continue again in the third stage, hence that I will continue in the second stage, hence he will continue in the first stage then plan to defect in the third stage. Given his beliefs about me, his actions in the first stage were rational. But if that plan to defect in stage three were his justification, then I should defect in stage two. He realizes I will make these inferences, hence he will defect in stage 1. That is, the backward induction outcome is justified by forward induction. Now, it can be proven that rationality and common “strong belief in rationality” as loosely explained above, along with a suitably rich type structure for all players, generates a backward induction outcome. But the epistemic justification is completely based on the equivalence between forward and backward induction under those assumptions, not on any epistemic justification for backward induction reasoning per se. I think that’s a fantastic result.

Final version, prepared for the new Handbook of Game Theory. I don’t see a version on RePEc IDEAS.

“The Tragedy of the Commons in a Violent World,” P. Sekeris (2014)

The prisoner’s dilemma is one of the great insights in the history of the social sciences. Why would people ever take actions that make everyone worse off? Because we all realize that if everyone took the socially optimal action, we would each be better off individually by cheating and doing something else. Even if we interact many times, that incentive to cheat will remain in our final interaction, hence cooperation will unravel all the way back to the present. In the absence of some ability to commit or contract, then, it is no surprise we see things like oligopolies who sell more than the quantity which maximizes industry profit, or countries who exhaust common fisheries faster than they would if the fishery were wholly within national waters, and so on.

But there is a wrinkle: the dreaded folk theorem. As is well known, if we play frequently enough, and the probability that any given game is the last is low enough, then any feasible outcome which is better than what players can guarantee themselves regardless of other player’s action can be sustained as an equilibrium; this, of course, includes the socially optimal outcome. And the punishment strategies necessary to get to that social optimum are often fairly straightforward. Consider oligopoly: if your firm produces more than half the monopoly output, then I produce the Cournot duopoly quantity in the next period. If you think I will produce Cournot, your best response is also to produce Cournot, and we will do so forever. Therefore, if we are setting prices frequently enough, the benefit to you of cheating today is not enough to overcome the lower profits you will earn in every future period, and hence we are able to collude at the monopoly level of output.

Folk theorems are really robust. What if we only observe some random public signal of what each of us did in the last period? The folk theorem holds. What if we only privately observe some random signal of what the other people did last period? No problem, the folk theorem holds. There are many more generalizations. Any applied theorist has surely run into the folk theorem problem – how do I let players use “reasonable” strategies in a repeated game but disallow crazy strategies which might permit tacit collusion?

This is Sekeris’ problem in the present paper. Consider two nations sharing a common pool of resources like fish. We know from Hotelling how to solve the optimal resource extraction problem if there is only one nation. With more than one nation, each party has an incentive to overfish today because they don’t take sufficient account of the fact that their fishing today lowers the amount of fish left for the opponent tomorrow, but the folk theorem tells us that we can still sustain cooperation if we interact frequently enough. Indeed, Ostrom won the Nobel a few years ago for showing how such punishments operate in many real world situations. But, but! – why then do we see fisheries and other common pool resources overdepleted so often?

There are a few ways to get around the folk theorem. First, it may just be that players do not interact forever, at least probabalistically; some firms may last longer than others, for instance. Second, it may be that firms cannot change their strategies frequently enough, so that you will not be punished so harshly if you deviate from the cooperative optimum. Third, Mallesh Pai and coauthors show in a recent paper that with a large number of players and sufficient differential obfuscation of signals, it becomes too difficult to “catch cheaters” and hence the stage game equilibrium is retained. Sekeris proposes an alternative to all of these: allow players to take actions which change the form of the stage game in the future. In particular, he allows players to fight for control of a bigger share of the common pool if they wish. Fighting requires expending resources from the pool building arms, and the fight itself also diminishes the size of the pool by destroying resources.

As the remaining resource pool gets smaller and smaller, then each player is willing to waste fewer resources arming themselves in a fight over that smaller pool. This means that if conflict does break out, fewer resources will be destroyed in the “low intensity” fight. Because fighting is less costly when the pool is small, as the pool is depleted through cooperative extraction, eventually the players will fight over what remains. Since players will have asymmetric access to the pool following the outcome of the fight, there are fewer ways for the “smaller” player to harm the bigger one after the fight, and hence less ability to use threats of such harm to maintain folk-theorem cooperation before the fight. Therefore, the cooperative equilibrium partially unravels and players do not fully cooperate even at the start of the game when the common pool is big.

That’s a nice methodological trick, but also somewhat reasonable in the context of common resource pool management. If you don’t overfish today, it must be because you fear I will punish you by overfishing myself tomorrow. If you know I will enact such punishment, then you will just invade me tomorrow (perhaps metaphorically via trade agreements or similar) before I can enact such punishment. This possibility limits the type of credible threats that can be made off the equilibrium path.

Final working paper (RePEc IDEAS. Paper published in Fall 2014 RAND.