Prehistoric Algorithms, Part 2 - Fair Division
On the surprisingly difficult field of cake cutting.
Part 1 is here, but you don’t need to read these in order. I’m trying to figure out what the earliest algorithms might have been. What could prehistoric humans have invented to solve their problems?
For this one, I’m going to start with the story of how it was rediscovered during World War II. Because it’s a pretty amazing story.
It is easy to leave the home of reality and get lost in the woods of mathematics, but only a few know how to return.
In Nazi-occupied Poland, the hardest math problem was finding someone to teach you math. The Soviets had purged all the intellectuals they deemed undesirable, and then the Nazis had murdered all the ones they didn’t like. Mathematicians tend to be pretty weird, and there weren’t many weird academics left.
(This might seem like a trivial issue, under the circumstances. It wasn’t, for some people. I would’ve been one of them. Math can be an addiction. I’ve never been a mathematician, but I’m not sure I’ve ever gone a week without learning some math, since about age 7 when my babysitter introduced me to solving algebraic equations with two variables. It soothes me when I’m anxious, and under those circumstances, if I were somehow alive, I’d be a bit on edge.)
But for those in the know1, there was one way to get a top-quality math lesson in exchange for, say, chopping some firewood. You needed to find your way to a farm on the outskirts of the village Stróże. The farm was owned by an old politician and activist, Jan Cieluch, who’d recently been released from prison. There, you’d meet one of his farmhands—a retired park ranger named Grzegorz Krochmalny. That’s your math teacher.
If you knew to come here, you probably knew he wasn’t actually a retired park ranger, and the name on his identity papers was not actually his. If you didn’t, there would’ve been some clues. He never drank, and rarely went to church. He didn’t make eye contact—in fact, he’d usually turn his whole head to the side while talking to you. He’d compulsively correct your grammar and your manners—if you introduced yourself by your last name, rather than your first, you would not be getting your class that day. He seemed almost as at home teaching the humanities as teaching math.
And of course, you’d discover he wasn’t only a great teacher—he was also a great mathematician, one the rest of the world thought was dead.
Mathematics is a bridge between spirit and matter.
Hugo Steinhaus was born in 1887. His childhood home, as well as the family store and the rest of his neighborhood, had been converted from a monastery decades earlier. You could barely tell. His family was Jewish, and you could barely tell. They had secular jobs and upper-class manners, spoke Polish, and didn’t all believe in God. Young Steinhaus would gawk at people celebrating Purim the same as he would gawk at a traditional peasant wedding or a dancing bear. Older, he won a bar bet with an anti-Semite who claimed to always be able to spot a Jew.
But he could tell. A formative memory for Steinhaus was seeing an army unit deployed to defend his neighborhood from a pogrom.
Steinhaus took longer to realize that he was a mathematician. At nine, he enrolled in the county school in the old town hall.2 The school had an intense curriculum, but at age nine it focused mainly on Latin, German, and beatings. There were other classes too, although as a Jew he wasn’t allowed in the religion class taught by father Wiśnewski. If he hadn’t cleared out by the time Wiśnewski showed up, he’d be flogged with a cane in front of the class. In his memoir, Steinhaus notes in passing that Wiśnewski eventually turned out to be a pedophile and was transferred away.
Literature was fascinating but disreputable. History was difficult because he couldn’t see any way to learn it other than memorization, which he wasn’t very good at. Sociology was incomprehensible—why was Durkheim so interested in the marriage customs of Polynesians, but not at all in their methods of warfare? Latin and German were all well and good, but he was more interested in learning English, part of his “contingency plans.” Military engineering was attractive at first, but his pacifist grandfather talked him out of his early hero-worship of the troops who had protected him from anti-Semites. (He did serve as a young man, which is how he met his wife).
That left mathematics, but for math he was dependent on textbooks, and the few he could scrounge weren’t very good. One was organized alphabetically by the last name of the author of that chapter; Steinhaus didn’t notice, tried to read it linearly, and was baffled. When he happened to meet someone who knew math, he learned that you could study it in the “exact philosophy” department at Lwów University, so there he went.
Math wasn’t only gratifying in itself. It was also a way in to all those other subjects that had stymied him before. He learned the history of mathematics, the way different cultures approached it differently, its applications to engineering, the way it approached the mystical and the divine.
His main focus, for a time, was probability and statistics, which enabled him to kibbitz in a wide variety of practical fields, including cancer research. He never bought the idea that there was a distinction between “pure” and “applied” mathematics. Math was math. Ideally you found applications for it, but doing so didn’t transform the math itself.
He also dabbled in engineering. One of his more immediately useful projects was the invention of what he called an “introvisor,” an ahead-of-its-time tool that used x-rays, lights, and a mirror to create a labeled visualization of the inside of a surgical patient, or whatever else you wanted to inspect. A CT scan, but without the C for computerized. He was motivated by meeting a 12-year-old with a needle stuck in her knee, which nobody could remove because they didn’t know exactly where it was. It was used, successfully, for that type of surgery, and later also by locksmiths, but never caught on.
The world is a ball chained to the leg of humanity.
Despite a rising tide of Polish anti-Semitism, Steinhaus eventually established himself in Lwów University as faculty. There, he became one of the founding fathers of the modern Polish mathematics community, as well as multiple branches of mathematics. He may have been the first to publish papers on game theory, a few years before John von Neumann kicked it off properly. He became known as well for his witty epigrams, some of which show up as the section headers of this article.
Meanwhile, Hitler and Stalin were secretly negotiating about who got to conquer which parts of Poland. Steinhaus was lucky, relatively speaking, to be in the Soviet slice of the cake. He stayed, because someone had told him that Bolsheviks revered academics. But Soviet culture, with its blatant disregard for the truth, disgusted him. He was never comfortable in the new regime, under posters of Stalin and his “crocodile smile.” Much later, he wrote:
Quite soon I perceived that we were dealing with liars and people of little—say a quarter of the average—intelligence whom the liars had turned into zombies. They made invariably empty promises, big fibs like trump cards to be dealt at every opportunity: “You had a pension equivalent to a thousand rubles; now you will get two thousand.”
Still, quietly, his Lwów School of Mathematics survived, meeting in the local Scottish Café, which had marble tabletops you could write on in pencil. Or sometimes, when Steinhaus had his way, in the more upscale tea shop down the street.
Then Hitler broke the truce.
You can’t predict the future. It’s hard enough to predict the present.
Murdering the academic community in Lwów, Jewish and not, was one of the top priorities for the Gestapo, passed down from the highest levels. They started killing the day they conquered the city, locating more in the next few days with the aid of Ukrainian collaborators. Lwów’s professors, especially its mathematicians and medical scientists, had become an emblem of Polish pride, and the Nazis hoped that wiping them out would break the spirit of the resistance.
Professor Jakub Karol Parnas, a celebrated Jewish biochemist and devout Communist, fled deeper into the USSR just in time to escape the massacre. He wrote in a Soviet news journal that
As soon as the Germans entered the city they organized a pogrom against the intelligentsia.
We know definitely of the murder of Kazimierz Bartel, professor of geometry; Tadeusz Boy-Zelenski, writer and literary scholar; Victor Reiss, ophthalmologist; Juljan Kleiner, philologist and literary scholar; Hugo Steinhaus, mathematician; Stanislaw Pilat, chemist; and Pawel Stern, biochemist. There are also reports that Adam Gruo and Stanislaw Dobrzaniecki, outstanding surgeons, were murdered.
That list was incomplete, but mostly accurate. Parnas himself had made mostly good decisions on how to survive. But at age 65, he was still living in the USSR when Stalin decreed his own pogrom against the intelligentsia, known as the Night of the Murdered Poets (you can tell, just from the name, that they didn’t get them all). Parnas died in a prison cell.
It’s rude to speak ill of the absent, let alone the nonexistent. So atheists are in an awkward position.
Steinhaus and his wife, Stefania, were able to sneak out of Lwów just in time. The Gestapo were guarding the front door of their house, so they went into their back yard. Stefania picked a rose from their garden, and they climbed over the fence into the neighbor’s yard. From there, the two simply strolled out of town looking like a middle-aged couple on a casual date.
Their survival now depended on a clear vision of the inner workings of the occupation bureaucracy. Underestimating their efficiency and organization could be fatal—if you were caught in a lie, you were done for. But overestimating it was even worse, he wrote later. Jews had to tell some lies, forge some documents, break some curfews, to avoid the concentration camps. Very few of them were able to spot the flaws in the machine, the places where the Gestapo’s seeming omniscience was a bluff.
But the Nazis were pretty stupid, Steinhaus thought. They didn’t even have good etiquette skills! They’d use the familiar “du” instead of “Sie” when addressing him, which was clearly incorrect. With that kind of inattention to detail, how were they supposed to be able to spot forged identity papers?
He, and most of his close family, separately and slowly made their way to Jan Cieluch’s farm, adapting their stolen identities to reflect their actual relationships to each other. They rarely felt safe, what with the constant trickle of news gradually making it clear that there was a full-scale Final Solution being implemented. But they weren’t caught. The village government proved adept at subtly sabotaging Gestapo investigations. Steinhaus avoided any academics who might recognize him, and wrote letters to friends under fake names. He helped with the harvest, getting “a great deal of satisfaction” from raking hay. Occasionally, he was able to apply his mathematical ability—creating a precisely proportioned map of the farm, for example, without the use of traditional surveying equipment. He gave lessons to the neighbors in exchange for flour rations and other foodstuffs. (This was doubly illegal—private schools were banned.)
“Thus life would have been tolerable,” he wrote, “if not for the constant dread hanging over us…”
People want to discover new things because we can’t stand how clichéd we are ourselves.
It was here, in letters exchanged with his former students Bronislaw Knaster and the great Stefan Banach, that he first formulated the problem of how to cut a cake.
Suppose two men are splitting a cake. If one cuts it in half, he could choose where to cut to give himself a “better” half—more frosting, say, or more strawberries. That’s not fair. The classic solution is to have one man cut the cake and the other choose which half. This gives the cutter an incentive to divide it exactly evenly.
But what if there are three people? Or more? Steinhaus suspected that it was impossible to come up with a general solution that worked as well as the one for two people, but he wasn’t sure.
Knaster and Banach were also Jewish, but were staying out of the camps by working as lice feeders for the parasitologist Rudolf Weigl, who was studying typhus. The Nazis spared this part of Lwów medical research because their soldiers kept getting typhus. Weigl found a clever, if horrifying, way of keeping the remaining Lwów intellectuals alive—right as the Nazis moved in, he hired them to be bitten by typhus-infected lice, so that the lice would survive long enough to be useful for research. The Nazis generally exempted people in this situation from the concentration camps—they were providing a useful service, and suffering and dying at an acceptable level.
Banach, short on blood but with little to do, ended up solving Steinhaus’s impossible problem by inventing the last diminisher protocol. In this version, the cake cutter first marks out the slice he plans to cut for himself. If anyone thinks the slice is too big, he can propose a smaller slice—but now that’s the slice assigned to him, not the original cake cutter. Once nobody thinks the slice is too big, the last person to shrink it gets that slice. The rest repeat the process. Banach and Knauser sent Steinhaus a theorem proving this was optimal.
They didn’t dare publish it until after the war. They did, however, get a different theorem published, anonymously, one that nobody would suspect had been written by Jews: a proof that it’s always possible to cut a ham sandwich in half with one cut, no matter how sloppily it was made.
Discoveries are flashes. One can find the philosopher's stone and forget where it lies.
I think the last diminisher was a reinvention of a prehistoric algorithm. Prehistoric cultures probably didn’t have the concept of a mathematical proof, but they could have tested it and noticed how well it worked. They might even have noticed, and corrected, a flaw in the protocol that mathematicians spotted later. People perceive the cake differently. If somebody got his fair portion, but thinks that the rest are dividing up their portions unfairly, he might end up envying one of the others, even if nobody else feels cheated. So people need to be allowed to return their portion to the pot and re-enter the process.
The protocol can be explained in a paragraph. We know it can be invented by people in highly stressful situations. And it would have been useful.
Four people work together to kill a large animal. Who gets which bits? Different people may have different preferences—someone wants the hide as part of their share, someone only wants as much meat as possible, someone really doesn’t want to have to eat liver again. If anyone feels like they’ve been cheated, violence could ensue or the band could break up at the height of their success.
Somehow or other, our ancestors must have solved that problem, probably many times in many places. Unlike some other algorithms, they wouldn’t have needed to make tools or wall markings to implement it, so we’re unlikely to ever find evidence. But they must have had a solution, because they survived. They didn’t spend their entire lives in a brutal war of all against all; they planted the seeds of civilization.
World War II is that story in miniature—even in the midst of its horrors, people were not just surviving, but innovating. Enriching the peaceful future. Weigl’s theories about typhus turned out to be correct. He invented a typhus vaccine, and used it to protect his lice-feeders. Including himself—he was always his own first test subject. Weigl is considered one of the Righteous Among The Nations, a non-Jew who saved Jewish lives. Knauser’s and Banach’s, among many others.
In 1969, a young mathematician named Wojbor A. Woyczynski was reading in a university library in Wrocław. The director of the library approached him and made an introduction to a professor who wanted to meet him. The 82-year-old man was immediately recognizable to any Polish nerd with a radio or television set. He started out with a compliment, as is only polite. “Professor Urbanik, your advisor, told me that you did something useful recently. May I invite you to our home for tea and cookies?” Thirty years after his supposed death, Hugo Steinhaus was still looking for ways to share.
Postscript: Cake Cutting Today
Cake-cutting is still a lively field in mathematics, with plenty of variants chosen to be mathematically interesting or tuned to different real-world problems—choosing work shifts, dividing an inheritance, allocating funding for public goods, and gerrymandering are just a few. We still tend to use Steinhaus’s metaphor of the cake no matter what’s actually being modeled.
When I was telling my spouse (happy birthday, by the way!) about cake cutting, she immediately assumed that the problem was about finding the socially-optimal distribution—in particular, how do you make sure each person gets enough to survive, when they can lie about how many calories they need? This turns out to be a (sorry) cutting-edge question.
In the general case, Aumann, Dombb, and Hassidim (2012) have proven that even if everybody is honest, finding the socially-optimal way to slice the cake is NP-hard, meaning roughly that finding an efficient algorithm for it would also solve a host of other problems and is probably impossible. For the specific case of step-function utility (e.g. you value all slices below a certain threshold at 0, because you’ll starve, and you’d lie about where that threshold was if lying got you more cake), Menon and Larson (2017) show, if I understand correctly, that it is provably impossible to prevent cheating.
The best answer I can come up with is probabilistic. Everyone self-reports their threshold value, but the higher your threshold, the more likely people are to get angry and kick you out. Or you systemize that. With a uniform cake, for example, you could slice it in place, then toss three berries onto it from a distance, and if all three land on the same slice, the person who cut that slice for himself doesn’t get any cake. This kind of solution doesn’t guarantee a good outcome, but it’s often where our instincts take us.
Anyway, I’m off to eat some birthday cake. Thanks, as always, for reading.
By the end of the occupation, the Polish resistance was not only covertly routing students to teachers, but trying to enforce educational standards in the underground schools. It was that important to keep the torch lit.
This had once contained monastic cells, so it was only natural that the top floor was made into a school and the bottom one a prison. The combination was unpleasant…mainly for the prisoners, who were often mentally ill and tormented by schoolchildren who diligently studied how to trigger them.
This epigram doesn’t appear in the standard list of “Hugonotki.” It’s adapted from the memoir Beech Boat, by Janina Kościałkowska, whose mother was friends with Steinhaus.
It was a kind of snobbery not to delight in Worochta, everything had already been said about it, everything painted in watercolours, gouache, oils, and even embroideries. Worochta was like a well-known model become over-famous.
…
Then my mother said with that half-serious smile of hers which was her charm: “ ‘Because the purpose of beauty is to delight…’ The poet Norwid was right. At least in this instance. And the most banal views are precisely the ones that are the most beautiful. Such a shame…”Professor Steinhaus laughed. “Of course it’s a shame. Man would like to be a discoverer, it’s hard for him to bear the fact that he is himself a banality.”
“Well, professor, you can’t know anything about that. You belong to the very few people who are the least banal of all.”