But First, What is Mechanism Design and Why Should Anybody Care?

Imagine the dusty Main Street of a town in the Old West. At one end stand all the Big Guns of economics, everyone from social and economic revolutionary Karl Marx to famous free-market fast gun Friedrich von Hayek and mathematical sharpshooter Paul A. Samuelson. They are the Law in this town. And one of the laws is: You don’t just dream up new economic institutions with a piece of chalk and a blackboard: Around these parts, economic systems and mechanisms evolve and emerge from the forces of history, culture, existing institutions and changing technologies.¹

At the other end of the street stands a short, balding Stranger in a long, old overcoat. In his left hand: an over-stuffed leather suitcase, once black, now worn gray from travel. He’s been running from some of the most determined killers the world has ever known, and he aims to make his home right here, in Economics City. And he aims to design new economic institutions.

He has only one advantage: All the Big Guns facing him down have blinders on.

The Stranger draws. Not a quick draw: a slow, methodical draw. Equations on a blackboard. He draws — with a piece of chalk. As he writes, he explains what he is doing in a mild, non-confrontative, yet totally rigorous manner. He defines his terms with mathematical precision. He tells a joke. The Big Guns begin taking their blinders off.

Many, many blackboards, and many pieces of chalk later, they all go into the saloon and have a drink together.

The Stranger is Leonid “Leo” Hurwicz.²

Before Leo came to town, there were normative descriptions of ideal economic policies or systems, but they were seldom mathematical. For example, people promoted socialism because it encouraged equality and community, or they promoted capitalism because it encouraged freedom and personal self-realization. On the other hand, mathematical economists typically did research that was either exploratory (suggesting basic economic patterns or hypotheses that seemed worth investigating), descriptive (describing the workings of economic systems as they exist), analytical (analyzing and explaining causal relationships within economic systems) and/or predictive (forecasting when, where and why certain economic phenomena might be likely to manifest in the future). Alternative policies could be considered, but some overall structure had to be assumed: How else could you predict outcomes? Thus, all of these mathematical approaches took some economic framework as given and attempted to identify, describe, optimize or predict outcomes.

Mechanism design turns that on its head: It takes the outcomes as given and uses systematic, mathematical techniques to generate models of economic institutions that produce those outcomes. It is sometimes referred to as the engineering side of economics, since it attempts to produce implementable designs for economic institutions, given detailed design specs.

There are of course many instances, even going back to ancient times, of creating mechanisms to achieve desired goals. For example, John Moore³ illustrates mechanism design using the Bible story known as the Judgment of Solomon, in which King Solomon of Israel has to determine which of two women is the real mother of a baby, when one is claiming that the other stole it from her. Solomon suggests cutting the baby in two and giving each half. Only the real mother objects to this solution, revealing that the one who doesn’t protest is not the real mother. (And is a psychopath — who accepts the idea of a baby being cut in half, even if it’s not hers?) This has all the classic characteristics of a mechanism: something valuable at stake (the baby), “agents” (the women) who have private information unknown to the mechanism designer (King Solomon), a set of “environments” or states of reality in which the mechanism must work (either the real mom is woman A, or else it’s woman B), and a goal (identifying the real mother). Moore uses modern mathematical methods which were (like DNA testing) unavailable to Solomon, to analyze the efficacy and weaknesses of Solomon’s mechanism. This example suggests one of the reasons for mechanism design’s importance: its potentially broad applicability to areas beyond what we typically think of as economics.⁴

Along more typically economic lines, Moore describes a method used in ancient Greek city-states to determine who would pay for certain public rituals or other civic needs: “Someone nominated the man who was reputed to be the richest. Let us call him Spyros. Spyros would then have to pay up, or claim ‘I am not the richest, old Timon over there is richer than me.’ Then Timon was faced with a choice. Either he could pay, or he could insist that Spyros exchange all his wealth with him, after which Spyros would have to pay.”⁵

Arijit Sen and Anand V. Swamy provide another example from nineteenth century India, which they term “taxation by auction.”⁶ Used by guilds to raise funds, this mechanism required all guild members but one to close their shops on a designated day. The right to remain open was then auctioned off, with the funds from the winning bid going to the guild. The authors provide pages of mathematical analysis, showing how and why this method might be better than standard revenue-based taxation in terms of equity, efficiency and potential appeal to guild members. In particular, revenue-based taxation would be more costly to operate and more susceptible to cheating, since it would require the guild to check the revenue of each shop. With taxation by auction, the shop with the highest revenue will generally make the highest bid, since they stand to gain the most by remaining open. The mechanism incentivizes the participants to honestly reveal their revenues via their bids. The ancient Greek mechanism has similar truth-inducing qualities.

Since we have no evidence that these ancient Greek or nineteenth-century Indian mechanisms were created using any systematic, mathematical procedure, they are instances of “mechanism design” only in a broad, generic sense. Leo is credited with creating the foundations of mechanism design in a narrower, more technical sense. By defining its elements and procedures in a rigorous mathematical form, he opened the way for mechanism design to become the basic tool of modern economics that it is today.

The essential procedural characteristic of modern mechanism design is that desired outcomes are the starting point, while the end point is identification of mechanisms that achieve those outcomes. Leo first presented this idea in published form (without using the term “mechanism design”) in 1960: “In a broader perspective, these findings suggest the possibility of a more systematic study of resource allocation mechanisms. In such a study, unlike in the more traditional approach, the mechanism becomes the unknown of the problem, rather than a datum.”⁷ Leo expanded on these ideas in 1972,⁸ while focusing less on resource allocation (flows of money, goods, capital and labor) and more on communication (information transfer and processing). This view of the economy as message transfer, innovative at the time, now has many adherents.⁹

So what exactly is a mechanism? My dad, apparently foreseeing that I might some day try to read the first few pages of Designing Economic Mechanisms, included a plain English definition on the very first page:

A mechanism is a mathematical structure that models institutions through which economic activity is guided and coordinated. There are many such institutions; markets are the most familiar ones. Lawmakers, administrators and officers of private companies create institutions in order to achieve desired goals. They seek to do so in ways that economize on the resources needed to operate the institutions, and that provide incentives that induce the required behavior.¹⁰

Mechanism design, then, consists of “systematic procedures for designing mechanisms that achieve specified performance, and economize on the resources required to operate the mechanism …”

The introduction to Designing Economic Mechanisms also has a couple of drawings illustrating mechanism design. Not charts or diagrams or graphs. Actual sketches of physical things (boxes in this case) such as might be drawn by a typical fifth-grader to explain something to a typical hippie-techie-bum-folksinger. True, these boxes are decorated with mysterious Greek symbols, and the caption for the first drawing contains the words “nondeterministic algorithm.” But, as it turns out, no harm was intended. (Check the drawings out in Appendix G.)¹¹

The first box represents a mechanism. It has an input slot and an output slot. Two things go into the input slot: 1) where the mechanism has to work (the “prevailing environment” chosen out of a set of possible environments) and 2) who the mechanism has to work for (a particular group of “agents” chosen out of one or more possible groups). The box is programmed with a “goal function” defining exactly how success is defined for this particular mechanism.

The output is simply a yes-no answer to the question, “Did we get a desired result as defined by the goal function?” Note that it’s “a” desired result, not “the” desired result. That’s why it’s a nondeterministic algorithm: With a given input, you don’t always get the same output. But you may be able to design a nondeterministic mechanism so that you always get a “good” output (however the goal function defines “good”).

For instance, say you have three people and a mechanism that, when asked for a piece of fruit, hands out either a banana, an orange, or an apple – but you can’t predict who’s going to get what. As long as you (the mechanism designer) are happy no matter what each of the three gets (hopefully because they themselves are happy), you’ve got yourself a successful mechanism.

The prevailing environment, by the way, includes the preferences of the agents (e.g. the fact that they’re all happy with any of the three types of fruit), but also any other economic factors that the mechanism designer can’t control, such as perhaps the number of available oranges, apples and bananas, possibilities for consuming said fruit or putting it back in the hopper, possibilities for growing or importing more fruit, etc.

That’s the mechanism box.

The second box might be called a “mechanism factory.” It also has inputs and outputs. The output – no surprise – is a mechanism, or possibly a bunch of mechanisms.

Once again, the inputs define who the mechanism has to work for (the “agents”) and where it has to work (the “environments”), but this time we may have multiple groups, each in a different environment, which could include different preferences. For example, perhaps we have: three people in Arizona who happen to like tacos, burritos and nachos; three people in California who would prefer oranges, bananas and apples; and three people in Idaho, who like latkes, french fries and tater tots. The correspondence between the state and the preferred foods is embodied in the goal function. The mechanism factory needs to turn out one or more mechanisms that pass the goal function’s test by providing the right foods for each group.

This second box, in real life, would typically be an algorithm, that is, a set of mathematical instructions for producing the mechanism(s).

A defining feature of mechanism design is its mathematical specificity. It requires you to explicitly define, in mathematical terms, what you are talking about. In discussing things in less mathematical terms, my father would occasionally use a phrase equivalent to “whatever that may mean” – highlighting the fact that a discussion was taking place without ever really defining what was being discussed. For instance:

Let me make it clear at this point that I do not intend to argue the advantages or disadvantages of whatever may be meant by “central planning” or “industrial policy.” Rather, my purpose is to instill some skepticism with respect to oversimplified arguments sometimes used in this area.¹²

Of course he wasn’t opposed to thinking about the fundamentals of economic systems: His work was guided by thinking about fundamental concepts such as feasibility, efficiency, equilibrium and incentive-compatibility. For example, given informational decentralization (the fact that pertinent information is dispersed among economic agents, who don’t have to share it and can even deliberately mislead others about it), a mechanism may only be feasible (i.e. operable) if agents actually can and do share information honestly and are then able to process the information they receive. This means that the mechanism has to motivate agents to share information honestly (which makes the mechanism incentive-compatible)¹³ and allow the agents to transfer and process information efficiently (which makes the mechanism informationally efficient). Even then, if a solution is so unstable that it is unlikely to last for any significant period of time (i.e. the solution does not represent a point of equilibrium), then it may not be much of a solution after all.

But such foundational ideas were just a starting point. His ultimate goal was to embody whatever understanding or intuition he had in a mathematical form that permitted no ambiguity, to reason from basic premises to logical conclusions and produce logically consistent systems of postulates and theorems. This has sometimes been characterized as an “abstract” approach. In its own hyper-mathematical way, it is actually a highly tangible and concrete one, not allowing for any fuzziness or doubt as to exactly what it is you’re talking about.

Of course, mechanism design probably wouldn’t be as important as it is if it weren’t down-to-earth and concrete in another way, namely, that it has actually helped solve some important practical problems. In fact, perhaps one of the reasons it took the good folks at the Royal Swedish Academy of Coolness so long to recognize this particular field of endeavor is that applications emerged over a long period of time.

For instance, one area where mechanism design has been applied successfully is in the design of auctions. A commonly-cited example is the Vickrey auction, or “second-price” auction, first described academically by William Vickrey, a professor at Columbia University, in 1961.¹⁴ In this type of auction, the highest bidder gets the item, but only pays the second-highest bid. The advantage is that bidders have no incentive to submit bids below the actual value they place on the item, because lowering your bid can only reduce your chances of winning, not the amount you pay if you do win. It is also not smart to bid more than the item is worth to you, since you could then end up paying more than it’s worth. This is an example of an incentive-compatible mechanism, one that rewards those who honestly reveal their private information.

Vickrey’s clever idea was “largely ignored for a decade.”¹⁵ Then in the 70’s, the Vickrey-Clarke-Groves (VCG) auction was devised, which has similar truth-inducing characteristics for multiple bidders competing for multiple items, and is more generally applicable in other ways as well. Even that has been used more as a “lovely and elegant reference point” than as a blueprint for actual auctions.¹⁶ Among other possible drawbacks, VCG requires bidders to bid on every possible combination of goods.¹⁷ By the 1980’s, one could reasonably have concluded that the auction design branch of the mechanism design tree had matured, bearing some interesting, even inspiring, but perhaps not terribly edible fruits.

But the best was yet to come. Precipitated, in part at least, by the worst. In 1991, it was discovered that some major cheating had been going on in auctions for U.S. government securities: No single bidder was supposed to be able to bid on more than 35% of the total supply, but the Salomon Brothers investment bank had tried to corner the market by bidding on amounts at times exceeding the total supply. Salomon was fined $190 million and required to set aside another $100 million for restitution to injured parties. The firm’s reputation was seriously hurt by the scandal, and it ended up getting acquired by Travelers Group. This raised awareness among those who followed such things that the good old sealed-bid, pay-what-you-offer auction had some shortcomings.

So in 1994, when the FCC started auctioning off communication spectrum (rather than assigning it by previously preferred means such as lottery or comparative hearings sometimes referred to as “beauty contests”), they consulted experts on how to devise an auction mechanism that would be transparent, fair, foolproof, and allocate the spectrum to the companies that valued it most. A very public test of the concept and potential of mechanism design, it was a huge success.

About this same time, the public Internet began its explosive expansion, and a need emerged to find ways to route traffic across networks owned by many different entities, serving all kinds of different customers, in a way that was both globally efficient and individually incentive-compatible. This is a classic mechanism design problem, and it was recognized that some of the same ideas that worked for auctions could be applied here: essentially, nodes and links would “auction off” their services and capacity, and traffic would “bid” on it, using least-cost routing algorithms to make decisions.

Because it does not presuppose any particular institutions, mechanism has potentially broad applicability in economics, sociology and political science: Considering to its potential, it may still be in its youth, if not its infancy.

The slow pace of development in mechanism design had an unfortunate consequence for Leo: By the time important applications were emerging, it seemed that awareness of his foundational contributions might have been fading. In fact, famously, when he got the early-morning call telling him he had won the Nobel Prize, he hung up, thinking it was a “stupid joke.” (Well, actually, he had my mom hang up. She had answered the call, because he was hard of hearing.)

“There were times when other people said I was on the short list,” he commented, “but as time passed and nothing happened, I didn’t expect the recognition would come because people who were familiar with my work were slowly dying off.”¹⁸

So on that chilly Minneapolis¹⁹ morning, December 10, 2007, in the Ted Mann Theater at the University of Minnesota, when my father slowly rose from his chair on the stage, slightly hunched over, leaning on his cane, and Jonas Hafström, Swedish Ambassador to the U.S., presented the red leather box containing the gold medal with the embossed profile of Alfred Nobel, those who hadn’t forgotten knew that Leo was harvesting the fruit of a tree he had planted half a century earlier.

Even the most aware, however, may not have known much about the soil that nurtured that tree: Leo’s Polish-Jewish background. That’s the focus of the next chapter.

I may have left out one or two technical details in this discussion of mechanism design. If you’re interested in going a little deeper, I recommend the short section from the introduction to Designing Economic Mechanisms by my father and his partner-in-design Stan Reiter, reprinted as Appendix G, with the generous permission of Cambridge University Press. Eric Maskin’s²⁰ and Roger Myerson’s²¹ Nobel lectures are also great introductory material.

===============

Footnotes