We care about your data, and we'd like to use cookies to give you a smooth browsing experience. Please agree and read more about our privacy policy.
Quanta Homepage
  • Physics
  • Mathematics
  • Biology
  • Computer Science
  • Topics
  • Archive
All Is Not Fair in Cake-Cutting and Math
Comment
Read Later
Share
Facebook
Twitter
Copied!
Copy link
Email
Pocket
Reddit
Ycombinator
Flipboard
    • Comment
      Comments
    • Read Later
    By Erica Klarreich

    Contributing Correspondent


    October 7, 2016


    View PDF/Print Mode
    Abstractions blogalgorithmscomputer scienceeconomicsmathematicsAll topics
    Abstractions blog

    All Is Not Fair in Cake-Cutting and Math

    By Erica Klarreich

    October 7, 2016

    When divvying something up, there's more than one way to define what's fair.
    Comment
    Read Later

    Save

    Introduction

    A pair of computer scientists recently settled one of the key questions in the theory of fair division: How can you allocate cake slices among a group of people in such a way that no one envies anyone else? The new cake-cutting protocol, which takes into account information like who enjoys vanilla frosting and who prefers chocolate shavings, is guaranteed to produce an “envy-free” division after a bounded number of steps, although it may involve cutting the cake into a mind-bogglingly large number of pieces.

    Yet envy-freeness is just one of several competing notions of fairness. It’s all well and good to divide a cake in a way that won’t produce envy, but you might instead want to find an “efficient” allocation, one that can’t be improved for anyone without harming someone else. Or you might aim for “equitability,” in which everyone has the same value for the slice he ends up with. A division protocol that achieves one of these notions of fairness will not necessarily achieve the others.

    Take, for example, the “I cut, you choose” procedure for dividing a cake between two people: One person cuts the cake into two slices that she values equally, and the other person chooses his favorite slice. Neither person will envy the other, since the chooser got his favorite slice, and the cutter didn’t care which slice she got. But “I cut, you choose” flunks when it comes to equitability and efficiency.

    The cutter, after all, will get a slice that she values at exactly 50 percent of the value of the whole cake. But to the chooser, the two slices may have very different values — perhaps one is worth 75 percent and the other 25 percent. He’ll choose the one that’s worth 75 percent to him, so he values his slice more than the cutter values hers, violating equitability.

    Or suppose we have a cake that’s half chocolate and half vanilla. If Alice loves chocolate and Bob loves vanilla, efficiency would say that we should give Alice the chocolate half and Bob the vanilla half. But that efficient division is not what will emerge from “I cut, you choose.” If Alice is cutting, she’ll have to divide the cake into two pieces that each are half vanilla, half chocolate — after all, if she made an all-chocolate slice and an all-vanilla slice, she’d risk losing the entire chocolate half to Bob.

    In the case of two people, there is always some division (maybe involving multiple cuts) that is simultaneously envy-free, equitable and efficient. But when more than two people divide a cake — or a stamp collection or the family business — it is sometimes impossible to produce a division that satisfies all three notions of fairness at the same time.

    That means that before people can implement a fair division algorithm, they must decide which notion of fairness they want to strive for — and that’s something mathematics can’t decide for them. When children divide an inheritance, should the Chagall painting go to the child who’s an art lover, or should it be sold and the proceeds divided? Should parents leave more money to the child who is swimming in debt, or give each child an equal share?

    There’s no one right answer. In each case, it’s up to the individuals involved to decide if fair’s fair.

    To learn more about the new algorithm, read Erica Klarreich’s article, “How to Cut Cake Fairly and Finally Eat It Too” on QuantaMagazine.org.

    Save

    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    By Erica Klarreich

    Contributing Correspondent


    October 7, 2016


    View PDF/Print Mode
    Abstractions blogalgorithmscomputer scienceeconomicsmathematicsAll topics
    Share this article
    Facebook
    Twitter
    Copied!
    Copy link
    Email
    Pocket
    Reddit
    Ycombinator
    Flipboard

    Newsletter

    Get Quanta Magazine delivered to your inbox

    Recent newsletters
    The Quanta Newsletter

    Get highlights of the most important news delivered to your email inbox

    Recent newsletters

    Comment on this article

    Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation. Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected. Moderators are staffed during regular business hours (New York time) and can only accept comments written in English. 

    Next article

    How to Cut Cake Fairly and Finally Eat It Too
    Quanta Homepage
    Facebook
    Twitter
    Youtube
    Instagram

    • About Quanta
    • Archive
    • Contact Us
    • Terms & Conditions
    • Privacy Policy
    • Simons Foundation
    All Rights Reserved © 2023