By TOMMY ANDERSSON of LUND UNIVERSITY
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.
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.
Tommy Andersson
Lund University
www.atomiumculture.eu
