Difficult problems in mechanism design that are too important to get wrong

This article by Jonathan Rauch in the Atlantic about the disintegration and paralysis of American politics, got me thinking again about how important and maddeningly difficult the problem of mechanism design is.

Don’t run away! It’s simple enough to explain what mechanism design is, even if it is hard to do it well. Mechanism design is the study of how to create rules for important human interactions that will guide the outcomes of such interactions toward desirable ends, when the people interacting follow their own perceived self-interest.

For situations in which coalition-building is not to be expected, the progress mechanism designers have made over the last few decades is palpable and has achieved results. Auctions for airwaves have raised billions of dollars of revenue; kidney exchanges have saved hundreds of lives; doctors in training are better allocated to hospitals and students to colleges and graduate programs — these are just some of the examples of cases where mechanism design had a big impact.

Politics is a quintessential realm of coalition-building. But the brand of game theory that underlies the very same mechanism design approach that has achieved the great results I just mentioned fails to model coalition-building successfully. It may be that problems like fixing US politics are inherently intractable, but it seems that the US Constitution was an inspired solution that did reasonably well for a long time, even as it is beginning to fail now.

Related to the general problem of designing well-functioning democratic political systems, we have the even harder problem of getting disparate political systems to deal with the mounting disaster of planetary environmental degradation, which threatens the entire human species (and a whole lot of other species). Mechanism design theorists simply seem incapable of modeling well such a huge problem of coalition formation. Lest you think I am just criticizing others, I count myself as one of the theorists incapable of envisioning a good approach at this time.

We have evidence, in the works of Elinor Ostrom and subsequent literature inspired by Ostrom’s work, that local solutions to the problem of the commons often develop over time and such solutions, which take the form of formal and informal rules of the game (mechanisms!), often work well to solve local pollution or resource overuse problems.

The hard problem is to develop such solutions for state-wide problems (US politics is an example) and planet-wide problems (the environment), before they destroy any semblance of civilization and the livability of planet Earth. I know there are many brilliant minds working in mechanism design, much more brilliant than mine. I hope I see progress made in modeling coalition formation and its implication for mechanisms in the coming few years, before it is too late.

Art and science, and some economics, too

The pursuit of beauty and economic theory: friends or enemies?

I read this post on Aeon by Frank Wilczek this morning. I posted about it on Facebook but doing so did not make me stop thinking about it. I want to put some of these thoughts down here, as they relate to economic theory, what draws me to it, and whether the draw of beauty in the mathematics used in economic theory detracts from the theory’s value to society. First of all, I invite you to follow the link above and come back to read the rest of my thoughts.

Wilczek has published a book recently, A Beautiful Question: Finding Nature’s Deep Design (Google Play link, Amazon link). I have not read it to the end yet, but I hope I will over the winter break. His discussion in the Aeon post immediately made me think about the art of mathematics and how it motivates me (and many others) to do economic theory and guides our attempts to do it.

Empires built on math

In my early years studying for my doctorate, I thought of math as a collection of empire-building tools for empires of the mind (castles in the sky might be another apt name). Economic theory, heavily math-laden, becomes in this view a galaxy far, far away where each theorist builds an empire (or at least a few starships) to impose order on the universe. Once you have laid down your assumptions, you then have a solid foundation for building and you are the emperor of your theoretical creations, as long as you can write down your mathematical arguments correctly.

This view is not far from Asimov’s galactic empire fiction. Indeed, Asimov himself thought that some sort of social physics exists, and if we can discover its laws, we could predict the unfolding of societies over vast, even galactic, scales. For economics, this perspective explains at least some of the psychological attraction theorists feel towards their castles in the sky. This attraction is particularly prominent for me when I am working on general equilibrium theory, which most of the profession has left behind.

Ethereal but irrelevant?

Good question! Let me first tell a story about logic and the demise of the Hilbert program in mathematics. Then I will talk about the fragmentation of economic theory, this one brought about by the confrontation of the theory with empirical tests, such as they are (famously much harder in the social sciences than in physics).

Hilbert was a prominent German mathematician. His famous and eponymous program was an attempt to make all mathematics utterly rigorous by putting it on a formal basis and to prove within that framework that mathematics is consistent. (Perhaps the best way to understand “formalization” in this sense, besides the obvious which is that it should be totally understandable to a computer, is by thinking about something von Neumann said: “Young man, in mathematics you don’t understand things. You just get used to them.” —source)

Hilbert’s program came undone when Kurt Gödel came up with his stunning, deep, and worldview shattering (for mathematicians) Incompleteness Theorems. The gist of these theorems is that if you build all of mathematics on a finite list of axioms, then you cannot prove by using this list of axioms all true theorems of mathematics and you cannot prove that the mathematics you have founded on these axioms is consistent (contains no contradictions).

Coming as it did in 1930, this devastating development seems to be a symptom of the fragmentation of European culture, which was soon to produce a horrible war. But what does it have to do with economic theory? Well, it tells us that the theoretical castles are indeed based on air, not stone foundations.

What’s worse, that’s not all that ails theoretical empire-building in economics. While there are plenty of valid criticisms to aim at empirical research in economics, its basic import is that grand, unified economic theories perform badly. This has led to the growth of “behavioral economics”. (Once again, let me point out how silly this name is: isn’t all economics behavioral? — I prefer psychological economics). However mainstream this field has become, it does have a shattering impact on beautiful theory-building that aims at wide applicability.

We contain multitudes and that can be beautiful too!

Well, it was good enough for Walt Whitman. How about we apply it to the entire society, whose functioning is the domain of study of economic theory, broadly conceived? Does the fragmentation I just talked about make further theory development ugly?

Many social scientists have written on this issue. To me, it seems that a fragmented field of theories can still be an object of beauty in the mind of the theorist. Think of it as a kaleidoscope (a word that literally means “a device for showing beauty”). This is how I attempt to keep my motivation up when I am struggling with long, messy arguments trying to prove something in complicated mathematical models of society that invariably leave my head spinning after only a couple of hours of effort.

Another good thing to say about the fragmented collection of models that constitutes modern economic theory is that it has produced some quite literally life-saving innovations (kidney exchanges, which came from a deeply mathematical field of economic theory called mechanism design theory). A good and easily readable account is Al Roth’s recent book Who Gets What — and Why.

Some others to read on related matters

In conclusion, here are some thoughtful works to read carefully that I constantly feel guilty for not having time to read carefully enough.

Daniel Little has a website portal and a blog about what it means to do social theory, even more widely construed than the widest view of economics.

Dani Rodrik has a recently published book in which he “argues that economics can be a powerful tool that improves the world―but only when economists abandon universal theories and focus on getting the context right”, as the book description on Amazon states. Another book I have started — so I really should wrap this post up now and get back to reading, even without having convinced myself that this gigantic post is as well written as possible! Of course it’s not. But I move on anyway. Ars Longa, Vita Brevis. Or, in the original language of Hippocrates, taken from the last link:

Ὁ βίος βραχύς, ἡ δὲ τέχνη μακρή, ὁ δὲ καιρὸς ὀξύς, ἡ δὲ πεῖρα σφαλερή, ἡ δὲ κρίσις χαλεπή. In English: Life is short, and art long, opportunity fleeting, experience perilous, and decision difficult.

RIP Ronald Coase (1910–2013)

I am late to the commemoration of Ronald Coase’s contribution to economics, on the occasion of his death yesterday at the age of 102 years. You will find a large number of online posts about this with a simple search. The New York Times publishes its obituary here. The Economist points to its article published two years ago on the occasion of Coase’s 100th birthday.

After reading a number of other posts on Coase’s legacy, I decided to offer here this fantastic piece by Kevin Bryan. I heartily recommend a careful reading of it and the links it offers. In the Toolbox for Economic Design there are several cautions against taking the “Coase Theorem” seriously. After studying Bryan’s post and the links he offers in it (especially that to McCloskey’s article), you will have a better idea why this nomenclature (Stigler’s baby, Coase proclaimed no theorems) is wrong and misleading, while Coase’s contributions to institutional economics, stemming from his 1960 article The Problem of Social Cost, are important.

Let us also not forget Coase’s 1937 (!) article The Nature of the Firm, an early and fundamental contribution to the way economists ought to view the limits of the efficacy of markets.

What a little honesty can do for implementation theory

Moving beyond consequentialism

The vast majority of the implementation literature follows mainstream economic theory by assuming that agents care about outcomes (consequentialism). Of course this is not true; most people care in some measure about how outcomes are achieved, too. They care about the process that brings the outcomes. They are not proud of themselves if they lie in pursuit of wealth or power. (At least I hope this is still true of most people, even if they are graduates of economics programs.)

It seems worthwhile to inject a little caring-about-process into implementation theory to capture such considerations. A few authors have attempted this recently and found out that a truly minimal injection of caring about process has larger results than one would expect.

An aside that promises a future post

A great example of a paper that goes well beyond a minimal injection of process-caring is Pride and Prejudice: The Human Side of Incentive Theory, by Tore Ellingsen and Magnus Johannesson, American Economic Review 2008, 98:3, 990–1008. Since this study limits itself to the principal-agent model and it modifies the outcome-orientation of standard theory drastically, I will discuss it in a separate post. Here I want to discuss a group of related papers that take the smallest possible departure from outcome-orientation in the context of implementation theory.

Four papers on honesty in implementation

Matsushima’s papers

Hitoshi Matsushima comes first with two papers on this topic. In Role of honesty in full implementation, Journal of Economic Theory 2008, 139, 353–359, he introduces a model of an agent who chooses strategies in order to achieve the best payoff as in standard theory, except when faced with a choice between an honest strategy and a dishonest one, such that they each reach outcomes that have the same payoff. In such a situation, the agent plays the honest strategy, defined as the strategy that goes along with the mechanism designer’s—the planner’s—intention.

In detail, an agent has standard, expected-utility, preferences on the alternatives and furthermore suffers a psychological cost, a disutility, from dishonesty. The agent starts life endowed with a signal and is required to make many announcements regarding her signal in the mechanism. Her cost of dishonesty is an increasing function of the proportion of dishonest announcements she makes in the playing of the mechanism game. Apart from this, the model is standard.

Matsushima proves that if a social choice function is Bayesian-incentive compatible (with the dishonesty cost removed from the agents’ utility functions), then it is implementable in iteratively undominated strategies. Further, the mechanism that achieves this implementation is detail-free, meaning that the planner does not need to know details of the agents’ utility functions or prior belief distributions to design the mechanism. In addition, while the mechanism does involve fines that are to be imposed when certain strategies are played, these fines are small. All in all, this is a very impressive result. However, it is not clear in my mind how the planner would know that the social choice function to be implemented is incentive-compatible without the knowledge of the details on utility functions and priors that are not needed for the design of the implementing mechanism.

An answer to this concern is given in the second Matsushima paper I want to discuss, Behavioral aspects of implementation theory, Economics Letters, 100, 2008, 161–164. In this paper any social choice function is implementable in iterative dominance as long as there is aversion to telling lies among the agents. Remarkably, if this aversion is absent, the mechanism of this paper has a large multiplicity of Nash equilibria, a multiplicity that disappears the moment even a slight white-lie aversion comes in and we turn to iteratively undominated equilibrium. The mechanism is entirely detail-free, not even depending on the form of the social choice function.

Both papers use mechanisms with lotteries among alternatives as outcomes. While this allows the designer to sidestep any issues that the discreteness of the set of alternatives raises, it also is subject to the standard criticisms of mechanisms that use lotteries. This criticism points out that such mechanisms depend heavily on the assumption that agents are expected-utility maximizers, and it assumes a very high level of trust in the mechanism operator by the agents.

One last remark on the Matsushima papers: they study social choice functions. Let us now consider two papers that look at social choice correspondences, not functions, and Nash equilibrium as the implementing equilibrium notion, rather than iterative undomination.

Papers on Nash implementation

Dutta and Sen 2009

Bhaskar Dutta and Arunava Sen released a working paper (PDF) entitled Nash Implementation with Partially Honest Individuals on November 9, 2009. They found that even minimal dishonesty aversion, as already described in this post, expands the class of social choice correspondences that are implementable in Nash equilibrium dramatically when there are three or more agents: any social choice correspondence that satisfies No Veto Power is Nash implementable when there exists at least one partially honest individual! This result is spectacular and it stands in stark contrast to Maskin’s classic results that Maskin Monotonicity is a necessary condition for a social choice correspondence to be Nash implementable, and Maskin Monotonicity with No Veto Power are together sufficient. The planner here only needs to know that there is one partially honest agent, not who this agent is.

The paper has additional results for the case of two agents, when it is known that one of them is partially honest and for the case where there is a positive probability that a certain agent would be partially honest. But I think the clearest advance is the extension of Nash implementability so much beyond the walls of the Monotonicity jail.

Lombardi and Yoshihara 2011

The last paper I discuss here is the one that brought Dutta and Sen to my attention (I knew about the Matshushima papers already). It is Partially-honest Nash implementation: Characterization results, by Michele Lombardi and Naoki Yoshihara, February 13, 2011, available in the Munich Personal RePec Archive. This paper gives necessary conditions for Nash implementation with partially honest agents. It also studies the implications of the presence of partially honest individuals for strategy space reduction. The surprise here is that the equivalence between Nash implementation via Maskin’s “canonical” mechanism (which is very demanding in terms of information transmission) and Nash implementation with more information-economical mechanisms (such as Saijo’s strategy-reduction one) breaks down in the presence of partially honest individuals.

This paper is the longest of the four and contains lengthy proofs. It gives the impression of the authors coming into this area and sweeping a lot of cobwebs away from the corners that the seminal works in the nascent partial-honesty implementation area (the previous three papers) did not clean up as they were more concerned with laying foundations.

Musings

I find this trend in implementation theory very refreshing. While it is still at a highly abstract level, it has already set secure foundations for further study. I am eager to see what else can be done with the general idea of adding a degree of honesty to economic agents involved in a mechanism. There are such people around still, even among those super-cynical types with economics degrees! Yet I can see that applied fields like auction theory might resist the trend. Especially for auctions involving corporations, the assumption that the agent, who now is a representative of a corporation, is partially honest, is less appealing than when the agent is an individual playing for herself. But this trend should be fruitful in applications to problems of externalities and public goods, two applied fields that come readily to mind as well-suited for it.