I've gone out for lunch with Bob, Carol, Ted, and Alice and now it's time to settle the bill. I only had a chicken salad and a soda but Bob had a steak and a beer, Carol had the pasta special and a glass of wine, and Ted a burger and coffee, while Alice just had toast and a glass of water. No surprise, now we can't agree on how much each person should pay ...
This isn't unusual because people generally aren't very good at figuring our what's a fair split so unless everyone is cool and agrees to simply divide the bill by the number of people it becomes a real pain. Think that's bad? Try dividing assets after a death or during a divorce; figuring out what's fair often winds up usually becomes a knock 'em down and drag 'em out war of attrition.
The answer lies in what are called "fair division" or "cake cutting" algorithms which is a pretty complex topic. Wikipedia opines:
Most of what is normally called a fair division is not considered so by the theory because of the use of arbitration. This kind of situation happens quite often with mathematical theories named after real life problems. ... According to the Subjective theory of value, there cannot be an objective measure of the value of each item. Therefore, objective fairness is not possible, as different people may assign different values to each item.
Which is, of course, why when you lunch with uncool people someone usually winds up paying more than their fair share.
But for some fair division problems mathematics has the answer! And those mathematics are something called Sperner's Lemma (which is also apparently known as the KnasterKuratowskiMazurkiewicz lemma but I digress). According to Wikipedia:
Sperner's lemma states that every Sperner coloring of a triangulation of an n-dimensional simplex contains a cell colored with a complete set of colors. The initial result of this kind was proved by Emanuel Sperner, in relation with proofs of invariance of domain. Sperner colorings have been used for effective computation of fixed points and in root-finding algorithms, and are applied in fair division (cake cutting) algorithms.
I would explain the mathematics but to be honest this is not my area of expertise so I have no idea what that's all about but luckily Ariel Procaccia, an Assistant Professor in the Computer Science Department at Carnegie Mellon University, and his research assistant, Jonathan Goldman, an undergraduate student in the School of Computer Science, do and they have launched a Web service, Spliddit ...
... a not-for-profit academic endeavor. Its mission is twofold: / To provide easy access to carefully designed fair division methods, thereby making the world a bit fairer. / To communicate to the public the beauty and value of theoretical research in computer science, mathematics, and economics, from an unusual perspective.
Spliddit currently handles three specific fair division problems: Splitting rent, dividing goods, and sharing credit. Each problem type has a detailed explanation and links to educational articles as well as demos. You can also run the algorithm with your own data and your own participants which is very cleverly done so that you can coordinate the use the service between people who may be "at odds" (or even homicidal) via email.
For example, say that you, Alice, and your siblings, Bob and Claire, are bequeathed your grandparents' estate but there are no instructions on how to split it up. The items to be split have real values (for example, the diamond ring is worth $10,000 while gold ring is worth $100) as well as imputed values ("the ruby earnings would go with my dress" or "I've never liked that gold watch").
Using Spliddit each combatant, er, sibling, independently rates the value of each item to them and then the algorithm goes to work:
A participant's maximin share is the amount of value she could guarantee if she were to divide the goods into bundles herself, and then other participants were allowed to choose their bundle before her. We guarantee each participant at least two thirds of her maximin share. In practice, it is extremely likely that each participant will receive at least her full maximin share.
And:
A division of goods is envy-free if each participant believes that her bundle of goods is at least as valuable as every other participant's bundle. In other words, no participant would want to swap places with another participant. We compute an envy-free allocation if possible, but this property cannot be guaranteed.
You have to play with the demos to get a solid feel for how they work but what the service does is to allocate whatever it is as fairly as possible. Of course the algorithm is simply maximizing the mathematical fairness of the outcome so whether any of the participants actually feel fairly treated is another matter entirely.
There are lots of business situations where this kind of service could be hugely useful but the one pressing situation it still doesn't address is how much you should chip in for lunch.
Until then, I only had a salad and a soda which came to $8.27 so why are you asking me to chip in $11.50? Jeez, Alice, we did this last week ... miss, could we get separate checks? No? OK, then Bob, come on, I mean your steak must have cost twice what my meal cost so you should pay proportionally more of the tax ... oh, come on, be fair ...
