Nobel 2012, Roth and Shapley

There will be many posts summarizing the modern market design aspect of Roth and Shapley, today’s winners of the Econ Nobel. So here let me briefly discuss certain theoretical aspects of their work, and particularly my read of the history here as it relates to game theory more generally. I also want to point out that the importance of the matching literature goes way beyond the handful of applied problems (school choice, etc.) of which most people are familiar.

Pure noncooperative game theory is insufficient for many real-world problems, because we think that single-person deviations are not the only deviations worth examining. Consider marriage, as in Gale and Shapley’s famous 1962 paper. Let men and women be matched arbitrarily. Do we find such a set of marriages reasonable, meaning an “equilibrium” in some sense? Assuming that every agent prefers being married (to anyone) to being unmarried, then any set of marriages is a Nash equilibrium. But we find it reasonable to think that two agents, a man and a woman, can commit to jointly deviate, breaking their marriage and forming a new one. Gale and Shapley prove that there always exists a match that is “pairwise stable” meaning that no pair of men and women wish to deviate in this way.

Now, if you know your game theory, you may be thinking that such deviations sound like a subset of cooperative games. After all, cooperative (or coalitional) games involve checking for deviations by groups of agents, who may or may not be able to arbitrarily distribute their joint utility among their coalition. Aspects of such cooperation are left unmodeled in their noncooperative sense. It turns out (and I believe this is a result due to Mr. Roth, though I’m not sure) that pairwise stable matches are equivalent to the (weak) core of the same cooperative game in one-to-one or many-to-one matching problems. That means both that checking deviations by one potential set of marrying partners is equivalent to checking deviations by any sized group of marrying partners. But more importantly, this link between the core and pairwise stability allows us to utilize many results in cooperative game theory, known since the 1950s and 60s, to answer questions about matching markets.

Indeed, the link between cooperative games and matching, and between cooperative and noncooperative games, allows for a very nice mathematical extension of many well-known general problems: the tools of matching are not restricted solely to school choice and medical residents, but indeed can answer important questions about search in labor markets, about financial intermediation, etc. But to do so requires reframing matching as simply mechanism design problems with heterogeneous agents and indivisibility. Ricky Vohra, of Kellogg and the Leisure of the Theory Class blog, has made a start at giving tools for such a program in his recent textbook; perhaps this post can serve as a siren call across the internet for Vohra and his colleagues to discuss some examples on this point on their blog. The basic point is that mechanism design problems can often be reformulated as linear programs with a particular set of constraints (say, integer solutions, or “fairness” requirements, etc.). The most important set of constraints, surely, are incomplete information which allows for strategic lying, as Roth discovered when he began working on “strategic” matching theory in the 1980s.

My reading of much of the recent matching literature, and there are obviously exceptions of which Roth and Shapley are both obviously included as well as younger researchers like Kojima, is that many applied practitioners do not understand how tightly linked matching is to classic results in mechanism design and cooperative games. I have seen multiple examples, published in top journals, of awkward proofs related to matching which seem to completely ignore this historical link. In general, economists are very well trained in noncooperative game theory, but less so in the other two “branches”, cooperative and evolutionary games. Fixing that imbalance is worthwhile.

As for extensions, I offer you a free paper idea, which I would be glad to discuss at further length. “Repeated” matching has been less often studied. Consider school choice. Students arrive every period to match, but schools remain in the game every period. In theory, I can promise the schools better matches in the future in exchange for not deviating today. The use of such dynamic but consistent promises is vastly underexplored.

Finally, who is left for future Nobels in the areas of particular interest to this blog, micro theory and innovation? In innovation, the obvious names are Rosenberg, Nelson and Winter; Nelson and Winter’s evolutionary econ book is one of the most cited texts in the history of our field, and that group will hopefully win soon as they are all rather old. Shapley’s UCLA colleagues Alchian and Demsetz are pioneers of agency theory. I can’t imagine that Milgrom and Holmstrom will be left off the next micro theory prize given their many seminal papers (along with Myerson, they made the “new” game theory of the 70s and 80s possible!), and a joint prize with either Bob Wilson or Roy Radner would be well deserved. An econ history prize related to the Industrial Revolution would have to include Joel Mokyr. There are of course many more that could win, but these five or six prizes seem the most realistically next in line.

“The Future of Taypayer-Funded Research,” Committee for Economic Development (2012)

It’s one month after SOPA/PIPA. Congress is currently considering two bills. The Federal Research Public Access Act would require federal funders to insist on open-access publication of funded research papers after an embargo period. The NIH currently has such a policy, with a one year embargo. As of now, the FRPAA has essentially no chance of passing. On the other hand, the Fair Copyright in Research Works Act would reverse the current NIH policy and ban any other federal funders from setting similar access mandates. It has heavy Congressional support. How should you think of this as an economist? (A quick side note for economists: the world we live in, where working papers are universally available on author’s personal websites, is almost unheard of in other fields. Only about 20% of academic papers published last year were available online in ungated versions. This is about 100% in economics and high energy physics and a few other fields, and close to 0% otherwise.)

I did some consulting in the fall for a Kaufmann-funded CED report released yesterday called The Future of Taxpayer-Funded Research. There is a simple necessary condition that any government policy concerning new goods should not violate: call it The First Law of Zero Marginal Product Goods. The First Law says that if some policy increases consumption of something with zero marginal cost (an idea, an academic paper, a song, an e-book, etc.), a minimum, necessary condition to restrict that policy is that the variety of affected new goods must decrease. So if music piracy increases the number of songs consumed (and the number of songs illegally downloaded in any period of time is currently much higher than worldwide sales during that period), a minimum economic justification for a government crackdown on piracy is that the number of new songs created has decreased (in this case, they have not). Applying The First Law to open access mandates, a minimum economic justification for opposing such mandates is that either open access has no benefits, or that open access will make peer reviewed journals economically infeasible. To keep this post from becoming a mess of links, I leave out citations, but you can find all of the numbers below in the main report.

On the first point, open access has a ton of benefits even when most universities subscribe to nearly all the important journals. It “speeds up” the rate at which knowledge diffuses, which is important because science is cumulative. It helps solve access difficulties for private sector researchers and clinicians, who generally do not have subscriptions due to the cost; this website is proof that non-academics have interest in reading academic work, as I regularly receive email from private sector workers or the simply curious. Most importantly, even the minor access difficulties caused by the current gated system, such as having to go to a publisher website, having to click “Accept terms & conditions”, etc., versus just reading a pdf, matter. Look at the work by Fiona Murray and Scott Stern and Heidi Williams and others, much of which has been covered on this website: minor restrictions on ease can cause major deviations to efficiency in a world where results are cumulative. Such effects are only going to become more important as we move into a world where computer programs search and synthesize and translate research results.

The second point, whether open access makes peer review infeasible, is more important. The answer is that open access appears to have no such effects. Over time, we have seen many funders and universities, from MIT to the Wellcome Trust, impose open access mandates on their researchers. This has, to my knowledge, not led to the shutdown of even a single prominent journal. Not one. Profits in science publishing remain really, really high, as you’d expect in an industry with a lot of market power due to lock-in. Cross-sectionally, there is a ton of heterogeneity in norms: every high energy physicist and mathematician puts their work on arXiv, and every economist backs up their work online, yet none of this has led to the demise of peer reviewed journals and their dissemination function in those fields. Even within fields, radically different policies have proven sustainable. The New England Journal of Medicine makes all articles freely accessible after 6 months. The PLoS journals are totally open access, charging only a publication fee of $1350 upon acceptance. Other journals keep their entire archive gated. All are financially sustainable models, though of course they may differ in terms of how much profit the journal can extract.

One more point, and it’s an important one. Though the American Economics Association has not taken a position on these bills – as far as I know, the AEA does very little lobbying at all, keeping its membership fee low, for which I’m glad! – many other scholarly societies have taken a position. And I think many of their members would be surprised that their own associations oppose public access, something which I think can safely be said to be supported by nearly all of their members. Here is a full list of responses to the recent White House RFI on public access mandates. The American Anthropological Association opposes public access. The American Sociological Association and the American Psychological Association both strongly oppose public access. These groups all claim first that there is no access problem to begin with – simply untrue for the reasons above, all of which are expanded on in the CED paper – and that open access is incompatible with social science publishing, where articles are long and even rejected articles regularly receive many comments from peer review. But we know from the cross section that this isn’t true. Many learned societies publish open access journals, even in the social sciences, and many of them don’t charge any publication fee at all. The two main societies in economics, thankfully, both publish OA journals: the AEA’s Journal of Economic Perspectives, and the Econometric Society’s TE and QE. And even non-OA economics journals essentially face an open access mandate with a 0-month embargo, since everyone puts their working papers online. Econ is not unique in the social sciences: the Royal Society’s Philosophical Transactions, for instance, is open access. If you’re a member of the APA, ASA or AAA, you ought voice your displeasure!

http://www.ced.org/images/content/issues/innovation-technology/DCCReport_Final_2_9-12.pdf (Final published version of CED report – freely available online, of course!)

A Note on Openness

While the NBER continues its rather ridiculous policy of gating access to NBER Working Papers – they are nearly all available freely after a quick search on Google Scholar, so why not just make the link in my NBER New Papers emails go to a pdf I can read? – Yale’s wonderful Cowles Foundation has taken a great step in the opposite direction and made a huge number of their classic papers and monographs freely available online. A few of the books you might be particularly interested in if you like the regular content on this site are Marschak and Radner’s legendary work on team incentives and the internal organization of firms, and Debreu’s Theory of Value (which still might be suitable as a textbook on general equilibrium analysis).

The full collection of Cowles’ work online can be found here.

“How to Count to One Thousand,” J. Sobel (1992)

You have a stack of money, supposedly containing one thousand coins. You want to make sure that count is accurate. However, with probability p, you will make a mistake at every step of the counting, and will know you’ve made the mistake (“five hundred and twelve, five hundred and thirteen, five hundred and….wait, how many was I at?). What is the optimal way to count the coins? And what does this have to do with economics?

The optimal way to count to one thousand turns out to be precisely what intuition tells you. Count a stack of coins, perhaps forty of them, set that stack aside, count another forty, set that aside, and so on, then count at the end to make sure you have twenty-five stacks. If your probability of making a mistake is very high, you may wish only to count ten coins at a time, set them aside, then count ten stacks of ten, setting those superstacks aside, then counting at the end to make sure you have ten stacks of one hundred. The higher the number of coins, and the higher your probability of making a mistake, the more “levels” you will need to build. Proving this is a rather straightforward dynamic programming exercise.

Imagine you’ve hired workers to perform these tasks. If tasks cannot be subdivided, the fastest workers should be assigned to count the first layer of stacks (since they will be repeating the task most often after mistakes are made) and the most accurate are assigned to do the later counts (since they “destroy more value” when a mistake is made, as in Kremer’s O-Ring paper). The counting process will suffer from decreasing returns to scale – the more coins to count, the more value is destroyed on average by a mistake. With optimal subdivision, the number of extra counts needed to make sure the number of stacks is accurate grows slower than the number of coins to be counted, and the optimal stack size is independent of the total number of coins, so counting technology has almost-constant returns to scale.

The basic idea here tells us something about the boundary and optimal organization of a firm, but in a very stylized way. If workers only imperfectly know when mistakes are made, the problem is more difficult, and is not solved by Sobel. If workers definitely do not know when a mistake is made, there still can be gains to subdividing. Sobel mentions a parable about prisoners told by Rubinstein. There are two prisoners who want to coordinate an escape 89 days from now. Both prisoners can see the sun out their window. The odds of one of the two mistaking the day count after that long is quite high, causing a lack of coordination. If both prisoners can also see the moon, though, they need only count three full moons plus five days.

http://www.jstor.org/stable/pdfplus/2234847.pdf?acceptTC=true (JSTOR gated version – I couldn’t find an ungated copy. Prof. Sobel, hire one of your students to put all of your old papers up on your website!)

“Secrets,” D. Ellsberg (2002)

Generally, the public won’t know even the most famous economists – mention Paul Samuelson to your non-economist friends and watch the blank stares – but a select few manage to enter the zeitgeist through something other than their research. Friedman had a weekly column and a TV series, Krugman is regularly in the New York Times, and Greenspan, Summers and Romer, among many others, are famous for their governmental work. These folks at least have their fame attributable to their economics, if not their economic research. The real rare trick is being both a famous economist and famous in another way. I can think of two.

First is Paul Douglas, of the Cobb-Douglas production function. Douglas was a Chicago economist who went on to become a long-time U.S. Senator. MLK Jr. called Douglas “the greatest of all Senators” for his work on civil rights. In ’52, with Truman’s popularity at a nadir, Douglas was considered a prohibitive favorite for the Democratic nomination would he have run. I think modern-day economists would very much like Douglas’ policies: he was a fiscally conservative, socially liberal reformist who supported Socialists, Democrats and Republicans at various times, generally preferring the least-corrupt technocrat.

The other famous-for-non-economics-economist, of course, is Daniel Ellsberg. Ellsberg is known to us for the Ellsberg Paradox, which in many ways is more important than the work of Tversky and Kahneman for encouraging non-expected utility derivations by decision theorists. Ellsberg would have been a massive star had he stayed in econ: he got his PhD in just a couple years, published his undergrad thesis (“the Theory of the Reluctant Duelist”) in the AER, his PhD thesis in the QJE, and was elected to the Harvard Society of Fellows, joining Samuelson and Tobin in that still-elite group.

As with many of the “whiz kids” of the Kennedy and Johnson era, he consulted for the US government, both at RAND and as an assistant to the Undersecretary of Defense. Government was filled with theorists at the time – Ellsberg recounts meetings with Schelling and various cabinet members where game theoretic analyses were discussed. None of this made Ellsberg famous, however: he entered popular culture when he leaked the “Pentagon Papers” early in the Nixon presidency. These documents were a top secret, internal government report on presidential decisionmaking in Vietnam going back to Eisenhower, and showed a continuous pattern of deceit and overconfidence by presidents and their advisors.

Ellsberg’s description of why he leaked the data, and the consequences thereof, are interesting in and of themselves. But what interests me in this book – from the perspective of economic theory – is what the Pentagon Papers tell us about secrecy within organizations. Governments and firms regularly make decisions, as an entity, where optimal decisionmaking depends on correctly aggregating information held by various employees and contractors. Standard mechanism design is actually very bad at dealing with desires for secrecy within this context. That is, imagine that I want to aggregate information but I don’t want to tell my contractors what I’m going to use it for. A paper I’m working on currently says this goal is basically hopeless. A more complicated structure is one where a firm has multiple levels (in a hierarchy, let’s say), and the bosses want some group of low-level employees to take an action, but don’t want anyone outside the branch of the organizational tree containing those employees to know that such an action was requested. How can the boss send the signal to the low-level employees without those employees thinking their immediate boss is undermining the CEO? Indeed, something like this problem is described in Ellsberg’s book: Nixon and Kissinger were having low-level soldiers fake flight reports so that it would appear that American plans were not bombing Laos. The Secretary of Defense, Laird, did not support this policy, so Nixon and Kissinger wanted to keep this secret from him. The jig was up when some soldier on the ground contacted the Pentagon because he thought that his immediate supervisors were bombing Laos against the wishes of Nixon!

In general, secrecy concerns make mechanism problems harder because they can undermine the use of the revelation principle – we want the information transmitted without revealing our type. More on this to come. Also, if you can think of any other economists who are most famous for their non-economic work, like Douglas and Ellsberg, please post in the comments.

(No link – Secrets is a book and I don’t see it online. Amazon has a copy for just over 6 bucks right now, though).

“Understanding PPPs and PPP-based National Accounts,” A. Deaton & A. Heston (2010)

Every economist knows what PPP adjustments are: we adjust consumption/GDP/whatever comparisons to account for differences in the price of nontradables and to remove the effect of economically insignificant swings in market exchange rates. But how exactly is this done? Is the data reliable? What precautions should be taken? Anyone who has seen how economic data is created – I’ve worked briefly at the Fed and at the Dept of Commerce – is rightfully worried: even simple statistics in a developed country like the US are often surprisingly inaccurate. In the new AEJ:Macro, Deaton and Huston explain what procedures were used in the recent 2005 International Comparison Project, which gathers the prices used in World Bank and PWT data; you may remember that China’s GDP was nearly halved as a result of this data.

First, we don’t even have “a” definition of PPP. GEKS (usually EKS, though Deaton and Huston think Gini should be credited for the idea as well) PPP ensures transitivity of bilateral price levels, and in a limited sense allows welfare comparisons if we assume identical preferences across any two countries, but do not allow GDP to be disaggregated into PPP-adjusted consumption, investment, etc. GK PPP does allow such aggregation, but in so doing overstates the value of nontraded goods in poor countries, therefore overstating living standards in poor countries; further, GK has no link to welfare theory.

Once an index has been selected, the data themselves are problematic. How do we account for different consumption bundles in different regions (the authors use Ethiopian teff and Thai rice as a bilateral problem)? First compute PPP within regions with similar product availability, then use a “ring” of countries with good data availability to link the regions. Even if price data is good, is the underlying GDP calculation in poor countries any good? Probably not. How do we account for services? This is generally problematic, though some “quality adjustments”, such as adjusting education for internationally comparable test scores is being done as of 2005. Are prices nationally representative, or are only urban areas samples? Prices are not representative in many countries, particularly China, where only 11 cities were sampled. How do we adjust for quality? Each good is very specifically described in terms of packaging and content, though this specificity leads to problems of data availability.

The number of problems are huge. Should we worry? In some sense, when claims like “variable x is important for growth based on this regression using PPP data, and y is not,” obviously the above data problems can be very important. But I think the “smell test” generally works: I travel heavily and generally find that when countries “feel richer”, they tend to be so under PPP income per capita comparisons, so there must be some value in the exercise. On the other hand, these types of data problems are a major reason I see my future work as lying in theory rather than empirics!

http://www.princeton.edu/~deaton/downloads/deaton_heston_complete_nov10.pdf (Final WP – published in AEJ: Macro 2.4)

A Useful Link

As in probably clear from my comments here, I think philosophy, and in particular epistemology, is an area that is both incredibly important for social scientists and also a source of woeful ignorance, in general, for social scientists. Given that the study of causal relations is a huge part of economics, it blows my mind how many economists are unfamiliar with really, really basic philosophical arguments like preemption or the link between causality and counterfactuals.

Luckily, the Internet continues to pay dividends in its role as an information diffuser with Philosophy TV. This week’s episode is a conversation by two well-known philosophers, Ned Hall and L.A. Paul, on what contemporary philosophy thinks about causality. Well worth a watch, along with many others on the site. And with that, a promise from me to severely limit posts here that do not directly comment on economic research – I’m a good Ricardian and therefore believe in specialization!

Note: Nobel Predictions

I’m sure that many of you, like myself, were psyched last week for your annual Fantasy Econ Nobel Draft: it’s the new fantasy football, right? A group of friends from the Fed, past and present, like to wager on Monday’s prize every year. I’ve got Hansen, Milgrom, Rogoff and Sid Winter on my team, with many a beer at stake. If you wanted my sentimental “who deserves it most” picks, noting that I have abysmal knowledge of the legends in econometrics and broad swaths of macro, I would say that Milgrom, Nordhaus, Tirole and Peter Diamond strike me as the most deserving.

On a related note, the 1988 winner Maurice Allais passed away. You know him from the Allais paradox in utility theory. Two notes on him: First, if you’ve ever seen the Allais paradox cited, you must notice that the particularly erudite 1950s economist must have been bilingual at least, since Allais’ paper (aside from an extended abstract) is published in French in Econometrica. I could not find English translations of many of his other papers.

Second, (and I would love to be corrected on this point!), there is a good case that Allais is among the “least deserving” laureates. Look at citation count, for instance: he has essentially only one well-cited paper, and surely citation is at least a rough measure of influence. His other interesting work strikes me as less developed than his followers (particularly Debreu); for instance, Allais’ proof of the welfare theorems demands much more in the way of assumptions about, say, differentiability, then similar proofs by his contemporaries. I don’t really see how Allais was more influential than other theorists of his era like Abba Lerner.

“Why are Certain Properties of Binary Relations Relatively More Common in Natural Language?”, A. Rubinstein (1996)

Everyone agrees that Rubinstein is a genius, right? In this old Econometrica of his, he applies game theory to a question of language: why do certain binary relations appear frequently – “A is to the right of B” – but others do not – “A lies clockwise from B”? Assume that languages are limited to a low number of binary relations, and that some sort of evolutionary process leads languages to tend toward the most “optimal” one.

Recall that a linear ordering is a complete, asymmetric and transitive binary relation. “To the right of” is one such linear ordering. Let the world contain a finite number of objects. A binary relation allows us to indicate – meaning to create a truth statement in predicate logic for which A is the only element in a given set making the statement true – any element of any subset of the grand set iff the relation is a binary ordering. In particular, there is a logical statement defining the “maximal element” of any set ordered in a linear ordering, and a second-maximal, and a third-maximal, etc. For this reason, we can say that linear orderings are the binary relation which is best among all possible binary relations in a language for “indicativeness”.

Rubinstein similarly proves other properties we might like a relation in a language are satisfied by linear orderings (although transitivity is not required for all of these): when a language has only one binary relation, a linear ordering is the most “precise” and a linear ordering allows a set of relations to be described with a minimal number of examples. The second property, roughly, is that if {A,B,C,D} are related by a linear ordering, and you know aRb, cRd, bRd and aRc, then you know every other possible relation among that set.

As usual, Rubinstein makes no claims that languages do in fact “naturally” find properties that are optimal: certainly English spelling is an obvious counterexample. His point is merely that language is nothing if not a coordination game, that the equilibria of a coordination games gives payoffs based on the properties of its solution, and that therefore economic and mathematic tools can be applied even to the study of language.

http://arielrubinstein.tau.ac.il/el/EL.pdf (Although this paper originally appeared in Econometrica, the ideas therein were expanded in chapter 1 of Rubinstein’s book on Economics and Language, which I have linked to.)

Note

I am quite literally trapped in the mountains of Central Asia – the Amu Darya has flooded out the roads in both directions. This being the case, posting will be (very) light until the 24th, though I still hope to briefly discuss a few papers from the new Econometrica. While I wait for the waters to recede, I’ll be up in the solitude of the Pamirs. As you know, economics, especially the micro theory that is the focus of this blog, is the only social science where the best work can be done without any social interaction at all!

(Now was that last line serious, or tongue-in-cheek? I leave it for you to decide…)