How do we define ‘equal’?

Wherein I've been busy, but I have time to provide another excerpt from Cryptonomicon


GeekPress passes along a story about using game theory to divide property of divorced couples. The software is developed by John Zeleznikow and Emilia Bellucci. Sounds a lot like a scene in Neal Stephenson's Cryptonomicon; I wonder if Zeleznikow and Bellucci read it?

The Waterhouses are attempting to divide grandmother's collections among her heirs (diagrams in the original text not included):

...Randy heads straight for the Origin, as in the intersection of the X and Y axes, which is marked by a light pole with its very own multiton system of wind-deposited wakes and vortices.

"Look," says Uncle Red, "all we want to accomplish here is to make sure that your mother’s legacy, if that is the correct term for the possessions of one who is not actually dead but merely moved into a long-term care facility, is equally divided among her five offspring. Am I right?"

This is not addressed to Randy, but he nods anyway, trying to show a united front. He has been grinding his teeth for two days straight; the places where his jaw-muscles anchor to his skull have become the foci of tremendous radiating systems of surging and pulsing pain.

"I think you’d agree that an equal division is all we want," Uncle Red continues. "Correct?"

After a worrisomely long pause, Aunt Nina nods. Randy manages to glimpse her face in the rearview as she makes another dramatic lateral move, and sees there a look of almost nauseous trepidation, as if this equal-division concept might be some Jesuitical snare.

"Now, here’s the interesting part," says Uncle Red, who is the chairman of the mathematics department at Okaley College in Macomb, Illinois. "How do we define ‘equal’? This is what your brothers, and brothers-in-law, and Randy and I were debating so late into the night last night. If we were dividing up a stack of currency, it would be easy, because currency has a monetary value that is printed right on its face, and the bills are interchangeable—no one gets emotionally attached to a particular dollar bill."

"This is why we should have an objective appraiser—"

"But everyone’s going to disagree with what the appraiser says, Nina, love," says Uncle Red. "Furthermore, the appraiser will totally miss out on the emotional dimension, which evidently looms very large here, or so it would seem, based on the, uh, let’s say melodramatic character of the, uh, discussion, if discussion isn’t too dignified a term for what some might perceive as more of a, well, catfight, that you and your sisters were conducting all day yesterday."

Randy nods almost imperceptibly. He pulls up and parks next to the furniture that is again clustered around the Origin. At the edge of the parking lot, near where the Y axis (here denoting perceived emotional value) meets a retaining wall, the Shaftoes’ hot rod sits, all steamed up on the inside.

"The question reduces," Uncle Red says, "to a mathematical one: how do you divide up an inhomogeneous set of n objects among m people (or couples actually); i.e., how do you partition the set into m subsets (S1,S2, . . . ,Sm) such that the value of each subset is as close as possible to being equal?"

"It doesn’t seem that hard," Aunt Nina begins weakly. She is a professor of Qwghlmian linguistics.

"It is actually shockingly difficult," Randy says. "It is closely akin to the Knapsack Problem, which is so difficult to solve that it has been used as the basis for cryptographic systems."

"And that’s not even taking into account that each of the couples would appraise the value of each of the n objects differently!" Uncle Red shouts. By this point, Randy has shut off the car, and the windows have begun to steam up. Uncle Red pulls off a mitten and begins to draw figures in the fog on the windshield, using it like a blackboard. "For each of the m people (or couples) there exists an n-element value vector, V, where V1 is the value that that particular couple would place on item number 1 (according to some arbitrary numeration system) and V2 is the value they would place on item number 2 and so on all the way up to item number n. These m vectors, taken together, form a value matrix. Now, we can impose the condition that each vector must total up to the same amount; i.e., we can just arbitrarily specify some notional value for the entire collection of furniture and other goods and impose the condition that... where [tau] is a constant."

"But we might all have different opinions as to what the total value is, as well!" says Aunt Nina, gamely.

"That has no impact mathematically," Randy whispers.

"It is just an arbitrary scaling factor!" Uncle Red says witheringly. "This is why I ended up agreeing with your brother Tom, though I didn’t at first, that we should take a cue from the way he and the other relativistic physicists do it, and just arbitrarily set [tau] = 1. Which forces us to deal with fractional values, which I thought some of the ladies, present company excluded of course, might find confusing, but at least it emphasizes the arbitrary nature of the scaling factor and helps to eliminate that source of confusion." Uncle Tom tracks asteroids in Pasadena for the Jet Propulsion Laboratory.

"There’s the Gomer Bolstrood console," Aunt Nina exclaims, rubbing a hole in the fog on her window, and then continuing to orbitally rub away with the sleeve of her coat as if she is going to abrade an escape route through the safety glass. "Just sitting out in the snow!"

"It’s not actually precipitating," Uncle Red says, "this is just blowing snow. It is absolutely bone dry, and if you go out and look at the console or whatever you call it, you will find that the snow is not melting on it at all, because it has been sitting out in the U-Stor-It ever since your mother moved to the managed care facility and it has equilibrated to the ambient temperature which I think we can all testify is well below zero Celsius."

Randy crosses his arms over his abdomen, leans his head back, and closes his eyes. The tendons in his neck are as stiff as subzero Silly Putty and resist painfully.

"That console was in my bedroom from the time I was born until I left for college," Aunt Nina says. "By any decent standard of justice, that console is mine."

"Well, that brings me to the breakthrough that Randy and Tom and Geoff and I finally came up with at about two A.M., namely that the perceived economic value of each item, as complicated as that is in and of itself, viz the Knapsack Problem, is only one dimension of the issues that have got us all on such a jagged emotional edge. The other dimension—and here I really do mean dimension in a Euclidean geometry sense—is the emotional value of each item. That is, in theory we could come up with a division of the set of all pieces of furniture that would give you, Nina, an equal share. But such a division might leave you, love, just deeply, deeply unsatisfied because you didn’t get that console, which, though it’s obviously not as valuable as say the grand piano, has much greater emotional value to you."

"I don’t think it’s out of the question that I would commit physical violence in order to defend my rightful ownership of that console," Aunt Nina says, suddenly reverting to a kind of dead-voiced frigid calm.

"But that’s not necessary, Nina, because we have created this whole setup here just so that you can give your feelings the full expression they deserve!"

"Okay. What do I do?" Aunt Nina says, bolting from the car. Randy and Uncle Red hastily gather up their gloves and mittens and hats and follow her out. She is now hovering over the console, watching the dust of ice swirl across the dark but limpid, virtually glowing surface of the console in the turbulent wake of her body, forming little Mandelbrotian epi-epi-epi-vortices.

"As Geoff and Anne did before us, and the others will do afterwards, we are going to move each of these items to a specific position, as in (x, y) coordinates, in the parking lots. The x axis runs this way," Uncle Red says, facing the Waterhouse House and holding his arms out in a cruciform attitude, "and the y axis this way." He toddles around ninety degrees so that one of his hands is now pointing at the Shaftoes’ Impala. "Perceived financial value is measured by x. The farther in that direction it is, the more valuable you think it is. You might even assign something a negative x value if you think it has negative value—e.g., that overstuffed chair over there—which might cost more to re-upholster than it is actually worth. Likewise, the y axis measures perceived emotional value. Now, we have established that the console has extreme emotional value to you and so I think that we can just go right ahead and move it down the line over to where the Impala is located."

"Can something have negative emotional value?" Aunt Nina says, sourly and probably rhetorically.

"If you hate it so much that just owning it would cancel out the emotional benefits of having something like the console, then yes," Uncle Red says.

Randy hoists the console onto his shoulder and begins to walk in a positive y direction....Back at the Origin, he can hear Red and Nina going at it. "I have a problem with this," Nina says. "What’s to prevent her from just putting every thing down at the extreme y axis—claiming that everything is terribly emotionally important to her?" Her in this case can only mean Aunt Rachel, the wife of Tom. Rachel is a multiethnic East Coast urbanite who is not blessed or afflicted with the obligatory Waterhousian diffidence and so has always been regarded as a sort of living incarnation of rapacity, a sucking maw of need. The worst-case scenario here is that Rachel somehow goes home with everything—the grand piano, the silver, the china, the Gomer Bolstrood dining room set. Hence the need for elaborate rules and rituals, and a booty division system that is mathematically provable as fair.

"That’s where [tau sub e] and [tau sub $] enter into it," Uncle Red says soothingly.

"All of our choices will be mathematically scaled so that they add up to the same total values on both the emotional and financial scales. So if someone clumped everything together in the extreme corner, then, after scaling, it’d be as if they never expressed any preferences at all."

"That’s good, Randy!" shouts Uncle Red from the Origin, "now we need to give it some x!" Meaning that the console is not devoid of economic value either. Randy does a right-face and begins to walk into the (+x, +y) quadrant, counting the yellow lines. "Give it about four parking spaces! That’s good!" Randy plonks the console down, then pulls a pad of graph paper out of his coat, whips back the first sheet, which contains the (x,y) scatterplot of Uncle Geoff and Auntie Anne, and notes down the coordinates of the console. Sound carries in the Palouse, and from the Origin he can hear Aunt Nina saying to Uncle Red, "How much of our [tau sub e] have we just spent on that console?"

"If we leave everything else down here at y equals zero, a hundred percent after scaling," Uncle Red says. "Otherwise it depends on how we distribute these things in the y dimension." Which is of course the correct answer, albeit totally useless....

Randy rejoins his aunt at the Origin. Uncle Red has been explaining to her, somewhat condescendingly, that they must pay careful attention to the distribution of items on the economic scale, and for his troubles he has been sent on a long, lonely walk down the +x axis carrying the complete silver tea service. "Why couldn’t we just have stayed inside and worked this all out on paper?" Aunt Nina asks.

"It was felt that there was value in physically moving this stuff around, giving people a direct physical analog of the value-assertions that they were making," Randy says. "Also that it would be useful to appraise this stuff literally in the cold light of day." As opposed to ten or twelve emotionally fraught people clambering around a packed-to-the-ceiling U-Stor-It locker with flashlights, sniping at each other from behind the armoires.

"Once we’ve all made our choices, then what? You sit down and figure it out on a spreadsheet, or something?"

"It is much too computationally intensive to be solved that way. Probably a genetic algorithm is called for—certainly there won’t be a mathematically exact solution. My father knows a researcher in Geneva who has done work on problems isomorphic to this one, and sent him e-mail last night. With any luck we will be able to ftp some suitable software and get it running on the Tera."

"The Terror?"

"Tera. As in Teraflops."

"That does me no good at all. When you say ‘as in’ you are supposed to give me something more familiar to relate it to."

"It is one of the ten fastest computers on the planet.