Fun_People Archive
28 Apr
A mathematical approach to division

Content-Type: text/plain
Mime-Version: 1.0 (NeXT Mail 3.3 v118.2)
From: Peter Langston <psl>
Date: Sun, 28 Apr 96 23:08:34 -0700
To: Fun_People
Subject: A mathematical approach to division

[or "How to divide $800,000"  -psl]

Forwarded-by: mbkomor@remarque.berkeley.edu (m.b.komor)
Forwarded-by: brand@reasoning.com (Russell Brand)

A mathematical approach to division

Published: April 27, 1996

BY K.C. COLE
Los Angeles Times

Mathematics now may be used to solve a problem that has tormented people
since the dawn of humanity: how to divide things fairly.

Mathematician Alan Taylor and political scientist Steven Brams say they have
devised a system based on "preference points" that can split just about
anything -- from the spoils of war to a child's birthday cake -- into
"envy-free pieces."

Not only do all parties get what they think is fair, they say, each thinks
it got the better of the other guys.

Taylor and Brams' work is only a small part of a rapidly surfacing trend.
Mathematics is invading political science in attempts to find rational
approaches to complex, often highly emotional questions.

The California Institute of Technology, for example, recently received an
$800,000 grant from the National Science Foundation to apply mathematics to
finding fair ways to divide society's scarce resources. It's the biggest
grant the foundation has given in the social sciences.

Among the questions Caltech is tackling: how to spread the cost of cleaning
up Los Angeles' polluted skies.

"Philosophers have argued about fairness for thousands of years," said
John Ledyard, who heads Caltech's social sciences division. "What's
different now is we have a formal mathematical structure. That takes it out
of ideological debate. There's science here."

One of the earliest notions of fairness is the Biblical story of King
Solomon, who had to decide which of two women claiming the same baby was
the mother. He ordered the child cut in half, which prompted the mother to
give up her claim to save her infant's life.

Solomon's story illustrates the idea that fair division means more than
cutting things into equal pieces. It involves the value the parties -- and
society -- place on what is to be divided.

Finding out how much people really value things often is difficult. Most
people try to take whatever they can get rather than honestly state their
choices.

Trying to encode the wisdom of Solomon into equations hasn't been easy, but
scientists are making progress.

Having their cake

Mathematicians do most of their research on fairness on a simple but
versatile model called the cake-cutting problem.

Suppose two people want to share a small cake. The fairest way to divide it
is to let one person cut the cake and let the other choose a piece first.

The cutter reveals her true preferences in the way she cuts the cake. For
example, if she values icing, she might cut one piece smaller but with more
icing, hoping her friend will go for the bigger slice.

Either way, both people can feel they are winners; one gets a bigger piece
and the other gets more icing.

Perception is as important as mathematics in making the solution work. In
this example, each person gets a role in choosing a slice.

The cake-cutting model works well for two. In more complicated situations,
more players often are involved.

In 1992, in response to a challenge posed in the Sciences magazine, Brams
came up with a solution that worked for three players. The first divides
the cake into three; the second is allowed to trim one piece he thinks is
bigger than the others. The third player gets to choose first. In the end,
everyone has a say, and everyone gets to choose a piece. Ergo, Brams says,
the solution is envy-free.

But when he tried to expand his system to four people, it didn't work. So
he called his friend Taylor, a mathematician at Union College in
Schenectady, N.Y. Taylor, who had never worked on fair division, thinks that
freshness helped him come up with a radical approach.

Essentially, his new method involved cutting a cake into an extra piece --
four for three players, and so forth. This allowed everyone to take a role
in both trimming and choosing.

Taylor's breakthrough won kudos in the mathematics community, because it
showed how to divide anything into any possible number of "envy-free"
pieces.

And now, divorce

In practice, though, the method is too unwieldy to use in everyday life,
because eventually the number of extra pieces required increases much faster
than the number of players. Besides, there are things one can't divide or
trim, such as the family dog in a divorce.

So this past year, Brams and Taylor turned their attention to a more
workable method. Instead of viewing the goods to be divided as a cake, in
the new system -- called Adjusted Winner -- each player gets 100 points to
distribute based on value preferences.

In a divorce, one spouse might assign 90 points to retaining custody of the
children; the other spouse might care more about the house and put 70 points
there.

In the first step of this process, each person wins whatever he placed more
points on. In this case, the spouse with 70 getting, say, a life insurance
policy rated 30 points; then the other spouse might get the family computer,
worth 10. The rest is split according to a mathematical formula that Taylor
and Brams guarantee is envy-free.

"The big problem we can help solve is divorce," said Brams, who teaches
at New York University. He also sees immediate applications in issues
ranging from labor disputes to the federal budget.

© 1996 Peter Langston