Inheritance

"Who wouldn't be?" Ecco responded with a grin. "My excuse is that I have a professional interest in Mr. Gorman. You see, his three heirs, Alice, Brad, and Carla, are due here any minute. It seems they have a private matter to discuss... No, no, don't leave. Nothing is private from you, my dear Professor. Nor from Liane for that matter."

Eleven year-old Liane was lying on the couch reading Carl Sagan's book Contact. I was going to ask her about it, when the doorbell rang.

"Am I the first to arrive?" the young man asked. He was wearing an ascot, black leather driving gloves, and reflective sunglasses.

"Yes, Brad," Ecco said. "Please have a seat."

"My sisters are always late," he said with a tone of self satisfaction. Just then, the doorbell rang.

The young woman who walked in wore haute couture from pillbox hat to heels.

"Carla, Carla Gorman is my name," she said. "You are Dr. Ecco, I presume. I do apologize for being late, but the helicopter could find no place close to land."

She nodded to her brother, sat down, glanced quickly around the apartment, and, apparently finding nothing of interest, opened the latest issue of Avenue.

A few minutes later, the doorbell rang again. This young woman wore jeans, no makeup, and a plastic earring on her left ear.

"My name is Alice Gorman," she said as she shook hands with Ecco. "I'm the black sheep of the family." She said this last sentence with good humor and proceeded to kiss her brother and sister with an affection that they more or less returned.

Brad cleared his throat and began, "We have a set of 30 family heirlooms. We don't know how to distribute them. We can each jump up and down and say how much we value each one, but Carla wants everything for herself, Alice wants everything to give away, and I want the result to be fair."

"You just want a new Ferrari," Carla said, rolling her eyes.

"Does each of you have an equal right to the heirlooms?" Ecco asked.

"Yes, we are coequal inheritors," Brad replied. "There are no others."

"I suggest a private auction then," Ecco said.

Carla, apparently experienced from her many visits to Christie's, glanced up in interest. "How do you mean?"

Reader: Before reading on, can you think of a fair auction strategy?

Ecco went on, "One thing you can do is to give each person a budget of 1000 currency units (which I'll call "CUs" from now on). Each person can then bid for the 30 objects and pay in CUs. At the end, the CUs are worthless, so each heir might as well use them all. During the bidding, however, if heir X wins the bid for an object o, then only heir X pays CUs; the others keep the CUs they would have used for o had they bought it."

"That's a nice idea," said Alice. "What do you say, dear siblings, shall we give it a try? I have a list of the objects numbered from 1 to 30. Each of us should put a CU amount next to each object in such a way that the total CU amount on all objects is 1000."

Brad and Carla apparently found no objection to this, so they created the following table.

Ecco looked over the table carefully. "Great," he said. "It's good to see that you value the objects so differently. Now, here are the rules.

"We imagine that a computer program simulates an auction for each object. For each auction, the program compares the bids and assigns the objects to the highest bidder at a price that is one more than that of the second highest bidder. If there is a tie, then the person who precedes in alphabetical order wins. Any of your CUs that are left over after a bid are assigned equally to the remaining objects you are bidding on, with any remainder going to the next object.

"Here is an example in which each person has a total of just 66 CUs and there are three objects:

"Object 1 is the subject of the first bid. Carla gets it for 26 CUs. Why? Because Brad would have bid 25, but no higher, so Carla would have won at 26. This yields the following table. Notice that the 23 that Alice would have bid for object 1 are split between objects 2 and 3. Similarly for the 25 that Brad would have bid for object 1 and for the 3 that Carla saved by paying 26 instead of 29.

"Brad wins the second bid and pays 24 (one more than Alice). This gives:

"Naturally, Alice wins the last bid and pays 43. Now, all CUs disappear. Who got the better end of the deal?

"Carla received an object that she valued originally at 29, Brad at 15, and Alice at 32. This gives a total value of 29+15+ 32 or 76. The maximum deviation in happiness falls between Brad and Alice at 17.

"Notice, however, that the object each heir receives can change if we change the order of the auction. For example, if the program processes the objects in the order 2, 1, 3, then the distribution of objects proceeds as follows:

"and Alice wins object 3. So, Alice has finished in the same way, but Brad and Carla have swapped positions and Brad is in fact happier with this order. Alice has received goods she values at 32, Brad at 25, and Carla at 17. This gives a total value of 74 and a maximum discrepancy of 15. So, this solution is more equitable, but yields a lower value.

"That is, there are two possible optimality criteria: maximize total value or maximize fairness so the difference between the happiest and the saddest is minimized.

"We seek an order that achieves as high a value as possible and another order that is as equitable as possible. If the objects are auctioned off in the order of their object order, then the total value is 1670 and the deviation (from happiest to saddest person) is 139.

Here is the list of the results of the first 10 bids:

Liane was writing something down on paper. "But there are more than 200 trillion billion possible orderings," she said.

"I see that Sagan has had a certain influence," Ecco said. "Nevertheless, we must find a very good order."

Ecco and Liane were able to find one ordering that achieved a total value of 1801 with a deviation of 64 and another solution achieving 1780 with a deviation of just 1. Can you find as good or better orderings? Better would mean either a total value greater than 1801 or a deviation of 1 or 0 with a total value greater than 1780.

After some debate, Alice persuaded her siblings to choose the ordering that gave the small deviation. They agreed after she gave each a week on her yacht to make up for the fact that she was the one who won 594 with that ordering, whereas they each won only 593.

Last Month's Solution

1. If duplicates are not allowed, then an "imbalance" strategy can put 52 monopoles into 4 rooms. Such a strategy consists of putting a monopole into the room that already has the most monopoles. Here is the distribution:

• Room A: 1 2 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52
• Room B: 3 5 6 12 14 21 23 30 32 41 50

• Room C: 8 9 11 15 18 44 47 51

• Room D: 17 20 24 26 27 29 33 35 36 38 39 42 45 48

2. Ecco and Liane concluded that 8 rooms would be necessary if every spare monopole with value V had to go into a different room from the original monopole of value V. Just double the number of rooms shown above.

3. If spares may go in the same room, then 5 rooms are enough. In fact, they could handle 58 monopoles if we put every spare in the same room. Ecco chose a strategy in which every spare always went in the same room as the original. Here we show the solution for only 52:

• Room A: 1 1 6 6 10 10 17 17 22 22 26 26 31 31 38 38 40 40 45 45 49 49
• Room B: 2 2 7 7 12 12 16 16 20 20 29 29 33 33 37 37 42 42 47 47 50 50

• Room C: 3 3 8 8 13 13 18 18 23 23 27 27 32 32 39 39 43 43 48 48

• Room D: 4 4 9 9 14 14 19 19 24 24 30 30 35 35 36 36 46 46 51 51 52 52

• Room E: 5 5 11 11 15 15 21 21 25 25 28 28 34 34 41 41 44 44

4. If duplicates are allowed but spares must be in different rooms from the originals, then a balance strategy works:

• Room A: 1 5 10 14 18 22 29 31 38 42 46 54 57
• Room B: 1 6 10 15 19 24 27 31 36 44 47 49 56

• Room C: 2 6 11 15 20 24 28 32 36 41 45 49 54 59

• Room D: 2 7 11 16 20 25 29 34 38 42 46 51 55

• Room E: 3 7 12 16 21 25 30 34 39 43 48 52 56

• Room F: 3 8 12 17 21 26 30 35 39 44 48 53 57

• Room G: 4 8 13 18 23 28 33 35 40 45 50 52 59

• Room H: 4 9 14 17 22 27 32 37 40 43 50 53 58

• Room I: 5 9 13 19 23 26 33 37 41 47 51 55 58

Reader Notes on "Flats and Steeps"

So far, there is no web version of the "Articulated Flats and Steeps" game. I guess people must still be working on closed forms solutions. Christopher Creutzig reports a Prolog program that suggests that Flats has a winning strategy on the 4×4 board. I will report on other progress in the coming months.

DDJ