Reply #41: Dolls, Candy and Mechanism Design Theory

[xchrom]

http://www.elpais.com/articulo/sociedad/Dolls/Candy/and/Mechanism/Design/Theory/elpepusoc/20111205elpepusoc_15/Tes

Decision makers - including individuals, companies, governments, etc. - are often faced with the problem of allocating a number of indivisible objects among a set of agents. Examples include negotiations for the final disposal of nuclear waste, where the indivisible object is the facility selected for final disposal, the allocation of a limited number of frequency bands mobile telephone use, or, to take a more everyday example, how a father should allocate different dolls between his children.

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.