Who Should Get the Biggest Slice? The Algorithm for Fairness
A Chapati Puzzle with No Easy Answer
Two farmers, Ram and Shyam, were resting under a tree. Ram had brought three flat, round chapatis to eat. Shyam had five. A hungry traveler rode up on a tired horse. The men kindly invited him to share their meal. They stacked all eight chapatis like pancakes, cut the stack into three equal portions, and each ate until nothing was left.
The grateful traveler turned out to be a nobleman. Before leaving, he handed the farmers eight gold coins as payment for the bread he had eaten. Then he rode off.
Ram and Shyam stared at the coins. How should they split them? Ram said, “There are eight coins and two of us, so four each.” Shyam protested: “But I put in five chapatis and you put in three. That doesn’t seem fair.” They couldn’t agree, so they went to see Maulvi, a wise elder.
After a long silence, Maulvi proposed a surprising division: seven coins for Shyam, and just one coin for Ram. Both men were stunned — but after Maulvi explained his reasoning, they saw that his answer was also fair.
Ram’s logic was about equal sharing between friends. Shyam’s logic was about paying each farmer the market price for his chapatis. Maulvi’s logic was about what the traveler actually consumed — one third of each person’s original stack. Since the traveler ate much more from Shyam’s pile, Shyam should be paid more.
Three people. Three perfectly reasonable ways to be fair. So which one is right?
That puzzle is not just about chapatis. It’s about something much bigger: how we design social procedures — step-by-step recipes that groups of people follow to make decisions, share things, or solve problems. And, as strange as it sounds, these recipes can be studied the same way we study computer algorithms.
What’s an Algorithm Got to Do with Sharing?
An algorithm is a set of exact instructions that always leads to the same result if you follow the steps correctly. You probably know one: Euclid’s recipe for the greatest common divisor. If I give you the numbers 20 and 12, the algorithm says: keep subtracting the smaller from the larger until both numbers are equal — that final number is your answer. It sounds like a math trick, but it’s also a guarantee. If you follow the recipe faithfully, the outcome is mathematically correct.
Social procedures can work the same way. If we follow a clear set of rules for dividing a cake, matching roommates, or taking turns to speak, the result should be orderly and hopefully fair. But fair is the hard part. An algorithm can be logically flawless, yet still feel wrong if it doesn’t match what we care about.
The oldest example is called Divide and Choose, or “I cut, you choose.” One person divides a cake into two slices she believes are equal. The other person picks first. If the cutter doesn’t know what the chooser likes, the cutter’s safest move is to make the slices truly equal — otherwise she risks getting the smaller piece. Both walk away satisfied, because each feels she got at least half.
But what happens if the cutter does know the chooser’s taste? Suppose she knows you hate raisins and love chocolate frosting. She can slice so that one piece has all the raisins and the other all the frosting — and she makes the raisin piece slightly larger in her own eyes, while it’s practically worthless to you. You pick the frosting piece and feel happy, but she gets more total cake by her own measure. The algorithm itself didn’t change. What changed was the knowledge each person had about the other.
This shows a deep idea: even a simple procedure can feel fairer or trickier depending on what information is public and what is hidden. When everyone knows each other’s preferences, the cutter can be sneaky. When they don’t, the cutter is forced to be honest.
Cutting Cake for a Whole Party
Divide and Choose works for two. But what if three, four, or ten people need to split a single cake, and everyone wants to feel they got at least their fair share? A cake here isn’t just a dessert — it’s a heterogeneous good, like a piece of land or a set of chores. The cake might have cherries on one side, chocolate on another, and someone might hate cherries. So equal size doesn’t mean equal value to everyone.
Mathematicians invented a method called the Banach-Knaster algorithm. Here’s the gist: the first person cuts a slice she thinks is a fair ( 1/n ) share. Everybody else inspects it. If no one objects, she takes it. If someone does object, that person trims a bit off and puts the trimmings back with the rest of the cake. Then that person asks, “Is this trimmed piece now small enough that I’d accept it?” The process repeats — people trim and trim — until someone finally accepts the piece and leaves the game. The remaining players continue with a smaller cake and one fewer person. It’s slow, but it can be proved to always deliver a simply fair division: each player ends up with a piece they honestly believe is at least ( 1/n ) of the whole.
Notice that “simply fair” doesn’t mean nobody feels envious. A division is envy-free only if no one thinks anyone else got a larger piece by their own valuation. Divide and Choose is envy-free for two, because there’s only one other piece. With more people, achieving both fairness and envy-freeness at once is surprisingly hard. Researchers still puzzle over recipes that guarantee both.
Matching Without Hard Feelings: The Stable Marriage Problem
Not every social puzzle is about slicing things. Some are about pairing people up. Imagine a classroom where all the students must pair up for a big project. Everyone writes down their ranked list of whom they’d most like to work with. The teacher wants an assignment where no two students would secretly prefer to ditch their partners and work together instead. That’s called a stable matching.
In the 1960s, mathematicians David Gale (1921–2008) and Lloyd Shapley (1923–2016) proved that a stable matching always exists, no matter what the preference lists look like. They also gave a step-by-step algorithm to find one. The Gale-Shapley algorithm works like this:
- Each person on one side (say, the boys) proposes to their top choice who hasn’t already rejected them.
- Each person on the receiving side (the girls) always keeps the best proposal they have so far, and rejects any less-preferred ones. The rejected proposer goes back to the pool and tries again in the next round.
- The rounds continue until no one is left proposing.
Here’s a tiny example. Suppose three boys (a, b, c) and three girls (d, e, f) have these preferences (most preferred first):
(a: e, d, f)
(b: f, e, d)
(c: d, f, e)
(d: a, b, c)
(e: c, d, a)
(f: a, c, b)
The algorithm might produce the pairs ((a,e), (b,f), (c,d)). Notice girl (d) ends up with boy (c), her very last choice. Yet the matching is stable. Boy (c) is delighted, and although (d) would rather be with (a) or (b), those boys are happily paired with their own top choices — they have no reason to switch. No two people would rather run away together.
There’s a catch: the algorithm strongly favours the group that does the proposing. If the boys propose, they get their best possible stable partners, while the girls get their worst. If the girls propose instead, the tables turn. Just like in Divide and Choose, the design of the procedure loads the dice — even though it is completely predictable and repeatable.
The Gale-Shapley algorithm isn’t just for imaginary classrooms. Real-world versions match medical students to hospitals and assign students to schools. When you don’t see the machinery, it’s easy to assume the result is simply fair. But “fair” might depend on who got to do the asking.
The Talking Stick and the Lost Token
Some procedures manage not goods or matches but conversation. Many Indigenous traditions use a talking stick: a decorated stick that passes around a circle. Only the person holding it may speak; everyone else listens. Without a stick, a group of equals might talk over each other, and the loudest voice wins. The talking stick is a social algorithm that guarantees everyone’s voice can be heard exactly once before any decision is made.
Computers need the same thing. In a token ring network, computers are connected in a circle like beads on a necklace. A small piece of data called a token travels around the ring. Only the computer holding the token can send a message. If the token gets lost — maybe due to a glitch — the computers must cooperatively create a new one without accidentally creating two. That’s the leader election problem, and computers solve it with a simple algorithm: each machine sends its own ID number around the ring, and the largest number eventually survives to become the leader. No planning, no boss — the algorithm handles it.
This marriage of social custom and computer science reveals something deep: the logic of fair group behaviour is often the same logic that runs the internet.
Why Knowing What Others Know Matters
All these algorithms rely on knowledge. Sometimes we need to create common knowledge: the kind of knowledge where not only does everyone know something, but everyone knows that everyone knows it, and so on forever. A public announcement in a classroom creates common knowledge instantly. But in a world with imperfect communication, common knowledge can be impossible to guarantee.
The computer scientists Joseph Halpern and Yoram Moses illustrated this with the Two Generals Problem. Imagine two generals on opposite hills, planning a joint attack on a city below. If only one army attacks, it will be destroyed. The valley between them is full of enemy patrols, so any messenger might get captured. General A sends a message: “Attack at dawn.” But how does A know the message arrived? General B could send an acknowledgement, but how does B know that arrived? No matter how many confirmations fly back and forth, there’s always a shred of doubt. They can never be absolutely certain of coordination, even if all messages succeed.
This shows that communication channels shape what kinds of social procedures are possible. Laws must be published openly so citizens can be presumed to know them. Advertisements during big events, like the Super Bowl, are so expensive partly because they create common knowledge: everyone watching knows that everyone else saw the same brand. Without common knowledge, some forms of cooperation remain out of reach.
Why Does an Ancient Algorithm Matter to You?
Next time you and your friends split a pizza, decide who gets the last slice, or pick teams without a teacher, you’re designing and running a social procedure. You might use “I cut, you choose” without even knowing its name. You might negotiate, flip a coin, or argue until someone gives in. Each method is a tiny algorithm, and each carries hidden assumptions about what fairness means.
The insight of the social software perspective is that we can study these everyday recipes with the same tools we use to design apps and networks. We can ask: Is the result always stable? Does it favour the person who acts first? What does it require everyone to know? And the biggest question of all — the one Maulvi faced with those eight gold coins — is: whose idea of fairness are we baking into the rules?
There’s no single right algorithm for living together. But knowing how the recipes work lets you see the choices hidden inside them — and maybe invent a better one next time.
Think about it
- Suppose three friends share a birthday cake with very different toppings (chocolate, sprinkles, fruit slices). Design a cut-and-choose rule that you think would leave everyone happy — then try to imagine how someone could feel it was unfair. What does your rule assume about fairness?
- If an algorithm for pairing up project partners always gives the students who ask first their best possible matches, is that still fair? Why or why not?
- Can you think of a situation where it might be better not to have common knowledge about something in your classroom or family?
