Dolls, Candy and Mechanism Design Theory

Although the first two examples concern multi-million dollar industries, the basic challenge is the same in all three: how to find a fair principle by which indivisible objects can be allocated among a number of agents given that they each hold private information about their valuation of the objects, and given that they can each act in self-interest? The answer to this question is found in the research area of mechanism design theory, whose founders L. Hurwicz, Maskin E. and R. Meyerson were awarded the 2007 Nobel Prize in Economics.

Let us return to the father's problem. Say that he has bought one light- and one dark-haired doll to give to his daughters Molly and Allis. He has also bought a bag of candy. Both Molly and Allis want the dark-haired doll. Who should it be given to? The natural solution is to give the child that is assigned the light-haired doll a larger share of the candy bag in compensation for not receiving their preferred choice. But how big should this share be? A first traditional solution is that the father makes a unanimous decision - as would be the case in a centrally managed economy. A second traditional solution is to let the children solve the problem themselves through negotiation - as in a market economy. One problem with the first principle is that the children's valuation of the dolls in relation to the candy is unknown to the father, which makes it difficult for him to find a solution that satisfies both of the children. The problem with the second principle is that the children may act in self-interest: there are incentives to lie about the true valuation to achieve a better bargain. The basic idea of mechanism design theory is simple: decisions are taken by those who have the most information - as in a market economy - but the rules of the game are determined by a central planner - as in a centrally managed economy.

Pioneering research performed over the past few decades has provided a solution to the above type of allocation problems. The basic idea, described using the above example, is that the central planner (the father) designs two consumption bundles containing an indivisible object (a doll) and a divisible good (the share of the candy bag). The central planner also specifies a maximum limit of the divisible goods than can be included in each bundle. Say, for instance, that the candy bag contains 100 pieces of candy and the bundle with the dark-haired doll can contain at most 30 pieces of candy. Then the agents (Molly and Allis) report how they value the indivisible objects in terms of the divisible goods to the central planner. Say that Molly reports that the dark-haired doll is worth 200 pieces of candy and that the light-haired doll is worth 140 pieces of candy, while Allis values the dark-haired doll at 180 pieces and the light-haired one at 130 pieces. The central planner takes these assessments and then decides the share of the divisible goods in each bundle so that each agent can be assigned a bundle that maximizes the sum of the valuation of the doll and the share of the candy. The central planner also maximizes the payment of the divisible good. In the above example, the unique solution is that Molly would be assigned the dark-haired doll plus 20 pieces of candy, while Allis would be assigned the light-haired doll and 70 pieces of candy. Note that Allis is indifferent between the two bundles (both have the value 200 pieces of candy) and that Molly strictly prefers the bundle designed for her. In this sense the solution is free from envy and can therefore be regarded as fair.

The fundamental advantage with the above allocation mechanism is that it is impossible for any of the agents to gain by reporting incorrect valuations. For example, if Allis falsely reports that her valuation of the dark-haired doll is 220 pieces of candy, the solution is that Molly is assigned the light-haired doll plus 70 pieces of candy, while Allis would get the dark-haried doll plus 10 pieces. But Allis' true valuation of this bundle is only 190 pieces of candy (180 + 10) which is less than the value 200 she received by telling the truth! Because the problems associated with selfishness and private information are solved, the allocation rule is very attractive. Note, however, that the cost of truth-telling is that some pieces of candy not necessarily are allocated between the agents -in this example, only 90 pieces are allocated.

We might ask why the remaining pieces of candy cannot simply be divided equally between Molly and Allis. Although this seems to be a reasonable idea, a well-known result in the mechanism design literature states that such a modification in general creates incentives for at least one of the agents to report non-truthfully. Hence, there is a fundamental conflict between truth-telling and allocation of all pieces of candy. In this case, this means that the father has to choose between getting an envy-free allocation - which always will be the case when the agent tells the truth - or an allocation where all candy is distributed between his daughters - it is in general impossible to achieve both these objectives.

The father's problem is clearly irrelevant in a larger perspective. What makes mechanism design theory important is that self-interest and private information is present in most industries, organizations, agencies, etc., and this complicates everyday life allocation problems. The theory can therefore be an important key in order to solve many hard allocation problems in the future.