Mechanism Design and the Revelation Principle

Johannesburg, July 2nd, 2010. It’s the first world cup in Africa. Ghana is the last african team in the quarter finals. They face Uruguay. The score is still 1-1, as we enter the injury time of the extra time of the game. The tension is at its summum. The whole continent is cheering for Ghana and hoping that it becomes the first African country to ever reach a world cup semi final. An interesting free kick is given to them, close to the penalty area. That’s their last chance to score the winning goal and avoid the hazardous and unpredictable penalty kicks. The stadium is on fire…

As Ghana is just about to score, Luis Suarez decides to behave like a goalkeeper and saves his side with a handball. As a result, Luis Suarez is sent away by the referee, as Asamoah Gyan takes the penalty kick… on the post! Eventually, Ghana will lose the game at penalty kicks. In Uruguay, Luis Suarez becomes an angel that sacrificed himself and got his country to heaven. In Africa, he is a devil whose cheating brought the continent into hell. All over the world, debates have raised on the action of Luis Suarez.

I don’t want any enemies, so I guess I am not going to take side! But I will say…

Don’t blame the player, blame the game

In his situation, Luis Suarez had all incentives to stop the ball with his hands, even though it is considered ethically wrong. Therefore, the rules are bad.

That’s what the saying says… But I’ll admit that there really is a point in blaming the player (if rules aren’t changed). After the financial crisis, people have blamed the banks for being too opaque with their transactions and for giving too much bonuses to traders. It did work. This will work, as long as we make people aware of the unethical behaviors, and as long as we can prove that there has been some unethical behavior. But when we can’t prove anything…

Congratulation! You have just started to think like a mechanism designer!

A mechanism designer is a person who has to find a way to make several people interact. He is the one who chooses the rules. Mathematically speaking, he needs to define a game between several agents (didn’t sound too mathematical, did it?). In soccer, the FIFA (Fédération Internationale de Football Association) is the mechanism designer of major international football competitions.

Mechanism design is sometimes called reverse game theory, and the mechanism designer is sometimes also called the principal or the regulator. Developed in the 70s, mechanism design has already had a lot of impact, thanks to the work of Leo Hurwicz, Eric Maskin and Roger Myerson, who obtained a Nobel prize in Economics in 2007. The problem they are facing, designing mechanisms, is a very tricky problem.

He needs to take into account that people will behave as they want, not necessarily as we expect them to. They will do what’s best for them. For instance, in electricity markets, companies are expected to announce their cost functions. But they have incentives to mislead us and announce a supply function that gives higher prices, in order to increase their profits. We cannot expect them to be truthful, especially since we can hardly verify their truthfulness.

When designing mechanisms, people must be expected to behave strategically. Computer scientists probably know what I’m talking about, as they often say “Never trust user input“. In computer security, people are even called “enemies“. Hence, the FIFA (and African people) should not have expected Luis Suarez to be ethical. They can blame him. But they should blame the rules too.

The mechanism designer’s goal

I find the concept of mechanism designer’s goal to be often forgotten or incomplete in analyzes of mechanism designs. Mechanism designers are institutions or people. They have a goal to achieve. If they want to choose the right rules of their mechanisms, they first need to define their objective very well.

Maybe it’s not clear because their true goal is money! To win money, they need to make football interesting and popular, so that more people watch the games, hence increasing the prices of broadcasting agreements. Several measures have been taken in order to do that (3 points for the winning team instead of 2, rating referees, substitutions…).

Sure! Let’s get back to the electricity market. The mechanism designer of the electricity market is usually called the electricity market regulator or the Independent System Operator (ISO). It’s usually state-owned. Its goal is to create an efficient market. Basically, it means that it wants to minimize the price of electricity. That’s why he came up with a system that takes into account the cost of production by all firms and that chooses the dispatches of firms so that the prices are minimized (this is usually done with a linear program called Locational Marginal Pricing (LMP)). His goal would have been achieved, had the firms been truthful… But once again, people should be expected to behave strategically.

To give you more examples of mechanism designer’s goals, I’ll introduce other examples of mechanism design.

Examples of mechanisms

As you can imagine, mechanism designs are everywhere. Whenever an interaction between people happens, a mechanism needs to be designed.

The best-known example of mechanism design is the auction problem. Consider a seller with a good for sale, and a set of potential buyers. Each buyer has a valuation of the good, but they all have incentives to hide it. As a matter of fact, otherwise, the seller would simply set the price at the highest valuation. Because the seller does not know the buyers’ valuations, he has to design an auction. He’s the mechanism designer. His goal is to sell the good at the highest possible price, while the buyers’ goals are to buy the good at the smallest possible price without overpaying. Quite often, the seller’s choice of mechanism is the classical english auction (the highest bidder is the buyer and the price is his bid).

Any market is a mechanism, and the institution that organizes a market is its mechanism designer. The Kyoto protocol regulates the energy market globally. In some regions, an Independent System Operator (ISO) regulates the electricity market. The World Wide Web Consortium (W3C) defines some standards of the web. All those organisms control mechanisms that they need to design so that no one produces to much greenhouse gas, no one owns to much market power and no one can hack the Internet.

When I was an undergrad student at the Ecole Polytechnique in France, we had to register to courses with numerous clausus. As these courses are not that important, it was decided that registration would be a “first come first served” system on the internet. That overloaded the servers and only lucky people could get the courses they wanted. This example is a particular case of the more general concept of assignment problems. In a lot of them, fairness is the mechanism designer’s objective.

There are plenty of other mechanism design problems, but I’ll only mention one more: politics. In particular, which system should we choose to govern a country? Today, most develop countries praise democracy. And a lot of them use the “First Past The Post” system or one of its variant to elect their leader. The following video explains in a wonderful way why this is a bad system (check out other videos from CPGGrey too, they’re awesome!). Briefly said, it gives the wrong incentives, and leads to a result which is not be the one we should hope for.

As said in the video, democracy inevitably leads to 2-party systems. One consequence of that is that democracy is unavoidably ruled by the median person, which means that the strong opinions of minorities are simply ignored. Is that right? Let’s suppose that the animal kingdom wants to decide whether they should be punished for attacking another healthy animal. If the king really wants to make it democratically, he’ll decide to have a referendum to decide. As most of animals are predators and fear that they may one day not have enough food when only attacking unhealthy animals, they will make the law go through. Yet, this law is horrible for herbivores who now have to fear any predator, even when they are healthy.

In reality, democracy seems to unavoidably create minority tensions, as minorities’ strong opinions don’t matter enough. This leads to political instability. Also, on technical matters like Germany deciding to remove Greece for the European Union with hardly foreseeable economical fallouts, it seems awkward to me that a median person will decide, while only a fist of people have an actual understanding of the problem. In some cases, from my humble point of view, making experts take decisions may be a better solution than democracy. Nevertheless, what I really wanted to do here is to point out mathematically the weaknesses of democracy as a mechanism design.

Well, the main result of mathematics in mechanism design is the one I am going to present right now…

The revelation principle

The revelation principle is a nice trick developed by mathematicians to give incentives to players to behave truthfully. It can be applied to any existing game, and players will all have incentives to behave truthfully. How awesome is this?

Buckle up, this is going to get a little technical! Let’s consider an existing mechanism. Basically, each person has an optimal strategy that depends on what he wants (yes each person has his own objective too!) and his constraints. Being truthful means revealing his objective and his constraints, which he has no incentive to do. Now, the revelation principle consists in asking each person to reveal his objectives and his constraints, as the mechanism designer guarantees them that he will play his optimal strategy for him. The player no longer has any action on the existing game. His only move is to tell the mechanism designer his objective and his constraints.

No. That’s the beauty of it. If he lies about his objective and his constraints, we will play the optimal strategy of a person whose objective and constraints are the lie. Therefore, it may be another strategy. Anyways, it will definitely not be strictly better than his optimal strategy, which is the optimal strategy we would have played, had he told us the truth. That’s why he has incentives to be truthful.

Well, first it is not well-known (invented by Gibbard in 1973). Second, it forces us to play the person’s optimal strategy, which could be ethically wrong. But mainly, because for it to be applied, we need to evaluate each person’s optimal strategy. But, as each person’s optimal strategy depends on the other persons’ strategies, you can imagine how complicated this can get. This is a typical game theory problem. It gets even more complicated considering that each person does not know what the others want. This is known as a bayesian game. In my PhD research, we have developed a great new tool to solve this problem. You can read this article of mine to know more about the problem.

There is a fourth important reason why we don’t often use the revelation principle. As a mechanism designer applies it, he may run into agency problems, as he complicates the mechanism. As a matter of fact, he may lose the trust of agents, hence jeopardizing his own goals. This is particularly the case when moral hazard or conflicts of interest may arise. Therefore, in order to apply the revelation principle, it is crucial that the mechanism designer declares his goal clearly and that the players trust him. When publishing this article, I had not seen that problem. I thank my readers for having pointed it out.

In some cases, those optimal strategies are easy to evaluate, and the revelation principle can therefore be applied. This is the case of the english auction! What’s the optimal strategy? Bid slightly more than the second highest bidder if we are the highest bidder. We can tell buyers: “Tell us how much you are willing to pay, and if you have the highest valuation, I’ll bid for you slightly more than the second highest bidder“. This is known as the Vickrey auction (designed in 1961, and got his author, William Vickrey, a Nobel price). It is equivalent to saying that the good will be sold to the highest bidder at the price of the second-highest bid.

In several cases, yes it is! In particular, that’s how Google AdWords works (you know, the sponsored links with a yellow background). Each company that wants to put an add on google tells google how much he is willing to pay to appear when people write this or that word. Then google takes into account the companies’ bids and uses the Vickrey auction to choose the buyer and the price. Well, it’s actually a little more complicated than that but the revelation principle is applied here!

Unfortunately, no. Not at all. As said earlier, we must not forget about the mechanism designer’s goal. Although it does make the mechanism truthful, the revelation principle does not affect the issue of the game. Let’s see what happens in our initial example: Suarez’s handball. What he wants, especially at such a moment of the game, is to prevent a goal at all cost. His optimal strategy is to do the handball. Right? Then if we apply the revelation principle, the only thing he has to do is tell us what he wants. He’s going to be truthful. But we have to play his optimal strategy for him. Which means that we do the handball for him. The consequences are exactly the same: he gets a red card and Ghana gets a penalty kick instead of scoring a goal.

Here is another example of how the revelation principle can be applied in sports. During the 2012 Olympic Games in London, 8 women badminton players have been disqualified for “not giving their best to win“. The International Olympic Committee has chosen a sanction (highly questionable as it wasn’t applied to all players in all sports). Now, let’s see what would have happened if they applied the revelation principle: the 8 women badminton players’ best strategies were to lose their games, so applying the revelation principle would correspond to the International Olympic Committee to consider these games as lost for the 8 players, without having them played. As you can imagine, this is not a good solution, but that’s not what the revelation principle. Applying it simply implies that the 8 players would not have had to lose on purpose. Jason Hartline, professor at Northwestern University, discusses the matter in more details, and underlines that, as opposed to current rules, previous rules were incentive-compatible.

Once again, the revelation principle does not affect the issue! It creates another mechanism in which people have incentives to be truthful. But if, in the initial mechanism, strategic behaviors lead to a bad issue, then, after having applied the revelation principle, the issue is still bad.

We can think of mechanism optimization. This is a concept we have come up with in my PhD research. The idea is to parameterize a mechanism to try to fix the bad issue. Then, we search for the parameters that will optimize the issue. In order to do that, we need more mathematical tools, including the return function. To know more about that, you’ll have to wait for my next article…

Let’s sum up

When you are the man in charge of making people interact, you are a mechanism designer. There is something that must come out of these interactions. This is your goal. You need to define it well and never lose track of it. Then, when designing the system of interaction, you have to think of the incentives this will create. How will people react to the rules I choose? And more importantly, given their reactions, what will actually be the aftermath? Will it be the one I had hoped for? If that’s the case and if the optimal strategies are not being truthful, you can then apply the revelation principle, and make people aware that you are applying it. Then your mechanism will be truthful and have a great issue.

In particular, you may want to avoid with rules that so many players violate, that you end up informally allow it, despite every one knowing that most players are in violations of the rules… Like for racewalking, as explained by MinutePhysics:

I’ll finish this article with a last example of mechanism design. Science4All.org is a mechanism and I am its designer. My goal is to make the website very popular and very well-known. The way I see it, there are two sorts of people that are going to use the websites: the readers and the authors. I am giving incentives to the readers to come to Science4All.org by assuring the quality of the articles. And I am giving incentives to the authors to write because they are highlighted in the article pages (and I also give plenty of other reasons to contribute in section “about”). I am hoping that these incentives are good enough so that my website keeps growing!