One way or another, people mostly get along. You walk into a restaurant and eat, with the understanding that you will pay. You work with the expectation of being compensated at the end of the week. Reputation, tradition, and contracts make most transactions run smoothly. In other cases, prepayments and security deposits reduce risk.
What about cases when these mechanisms are not reliable? A playground exchange has each party grip the object to be received, and both sides release the object to be given at the same time. But a bully with a good grip can cheat and end up with both toys. Is it possible to come up with strategies that allow adversarial parties to make reliable transactions without depending on third parties?
Fair Division
A well-known tactic solves the problem of dividing a cake evenly between two people. Alice cuts the cake such that she is satisfied with either slice. Bob then chooses which piece he wants. (1) Can three people divide a cake such that they are all satisfied? Can a solution be extended to more people?
Adversarial Trade
Two people who don't trust each other want to exchange some goods, and no escrow service is available. One solution: Alice leaves her item on one end of a long table. Bob leaves his item on the other end. Both parties proceed clockwise around the table to collect the other's item. (2) Is there a solution for three or more people?
Promise to Pay
At the end of a taxi ride, the fare asks the cabby to wait while he runs an errand. He tears a banknote down the middle and gives half to the cabby. It's now worthless to the fare, so the cabby is encouraged to wait. But the fare has nothing to lose by abandoning the taxi if he changes his mind. (3) Is there a better way to promise payment?
Remote Coin Flip
Heads-or-tails is a fair way to pick a winner between two people. But what if they are not in the same place? (4) If one party is only available by phone, can the flip be fair? What if they are not present at the time of the flip but will come later? More generally, (5) can you pick a winner among three or more people together using only fair coins or dice?
Who Makes More?
Two employees want to know who makes more, but don't want to reveal their salaries. Alice enters her salary on a calculator with the display covered. Bob then subtracts his salary, and divides the result by the absolute value of the result. The display is revealed, and a 1 indicates that Alice makes more; a -1 indicates that Bob makes more. (6) Can this be extended to three or more employees? They should all learn their rank, but no one (except those at the top and bottom) should have any knowledge of which employees rank above or below them.
Some of these questions can be approached with logic, and others require a more pragmatic approach. My high school science teacher, Mr. Hutchinson, solved the Promise to Pay problem by requiring a shoe to be held in escrow when he loaned out a pencil. Each item is more valuable to the owner than the borrower, making the eventual return more likely. Pawn shops operate somewhat differently on similar principles. For those looking for more pure logic, the Commitment scheme article is a good place to start.
Subscribe to:
Post Comments (Atom)
9 comments:
(1) For three people, how about this:
--Alice cuts the cake into 6 slices however she chooses.
--Bob then divides these slices into groups of two, in any way he chooses.
--Then Chuckles distributes the three groups among the eaters however he chooses.
This is vulnerable to Alice and Chuckles conspiring to screw Bob over: e.g., Alice cuts 5 slices that are each 2/11 the size of the cake, and one slice that is 1/11. Then Bob has no choice but to group them like {{2/11, 2/11}, {2/11, 2/11}, {2/11, 1/11}}, and then Chuckles can give Bob the group with the small slice.
So it's not a perfect scheme.
Even without conspiracy, Bob can object to Alice's slicings, saying that he is unable to group them such that he will be satisfied with any two.
How about this? Making some helpful assumptions about ideal cake and molecular gastronomy, we can try the procedure below.
Alice cuts a slice that she would be happy with, and each of the others states if they would be satisfied with this slice or not. There are three cases.
1) Neither Bob nor Cthulhu would accept the slice. Alice takes it, then Bob and Cthulhu use the usual way to divide the remainder between two people.
2) Only Bob would accept the slice. Then Bob cuts a little bit of the slice off, such that he would still accept the slice, and returns the part he cut off to the remainder of the cake. The slice then goes back to Alice. If she would accept it, then she slices off some more such that she will still accept the remainder. The two go back and forth until one refuses to accept the slice, then the other takes it. The remainder of the cake, reassembled, is then divided in the usual way between the remaining two people.
3) Both Bob and Cthulhu would accept the first slice. Then instead of passing back and forth, the slice is passed around the circle until one person refuses the slice, and the procedure is continued as in the previous case.
We still have to deal with "ties" -- cases in which someone would accept the slice as presented but not if it were any smaller. In that case they pass, and the slice continues. If two or more people pass, then the slice is accepted by the first person who passed it.
Seems like this might work for more than three people as well.
(3) Promise to Pay might work if the fare leaves half a banknote and a smaller amount, intact, as a deposit. When returning to the taxi, he gives the second half of the torn banknote and gets his deposit back.
(4) Telephonic coin flip almost works if the flipper states the result and the caller-in calls the flip at the same time. But it's hard to synchronize perfectly, so the caller has to use a code. When the flipper sees the result and says "go," the caller says a word. A word with an even number of letters stands for heads, odd stands for tails. Immediately after the caller calls, the flipper states the result, and can then count letters to see who won. The coin, in fact, is optional.
(1) I'm pretty sure Steve's pie auction scheme would work. The only problem would be that two of the people would probably end up with pie mush instead of pie slices with all of the cutting going on.
Looking at the problem, I'm going to add another constraint: The people dividing the pie are pirates. Aka, they value two things in life:
1)Getting as much pie as possible
2)Causing pain, suffering and bloodshed.
Of course, what causes more pain and suffering then giving someone as small a slice of pie as possible? That in turn will also lead to bloodshed, (as a fight breaks out). That being said, a pirate will put getting as much pie as possible as their highest priority, because let's be honest, this is some good pie we are talking about.
Pirate 1: Arrrthur
Pirate 2: Charrrles
Pirate 3: Alice
My first thought was to have Arrrthur, then Charrrles cut slices off the pie. Then Alice would pick a slice, then Charrrles, then Arrrthur. This way Arrrthur would cut a 1/3 slice since he is guaranteed to get the smallest slice there is, (aka it's in Arrthurs best interest that all the slices are equal). Then Charrrles would also cut a 1/3 slice since he can't do better than the slice Arrthur cut, (aka Alice will take the bigger of two slices that Charrles cuts). The problem is that Charrrles could cut a very small piece. He would then end up taking Arrrthur's 1/3 size piece after Alice takes the big one, and Arrthur is left with a tiny sliver of pie and bloodshed ensues.
My actual solution will be in the next post.
A better, but more boring since there's no bloodshed, solution would be to change the order in which the pie slices are selected.
Step 1)Arrthur cuts a slice
Step 2)Charrrles cuts a slice
Step 3)Alice picks a slice
Step 4)Arrthur picks a slice
Step 5)Charrles picks a slice
What makes this work is that pirates are vindictive SoB's, and they love bloodshed. Let's say Arrthur cuts a very small slice knowing that Charrles will be forced to take it, (since he picks last). Seeing this Charrles decides to punish Arrthur by cutting a slice equally as small so Arrthur will be forced to take that one. In this case Alice makes out like a Bandit with almost the entire pie, but Arrthur and Charrles don't notice this since they are too busy trying to keelhaul each other.
Since Arrthur loves pie more than bloodshed though, and he knows Charrles will retaliate if he cuts a small slice, that option is out. Also it is not in Arrthur's best interest to cut a large slice since Alice will take that, leaving him and Charrrles less than 2/3rds of the pie between them. Therefore thanks to the wonders of mutually assured destruction, Arrthur will cut a fair, (1/3), slice of the pie. Likewise, since Charrles will always get the smallest slice, he will also cut a (1/3) slice of the pie. Therefore everyone gets an equal share and bloodshed is avoided.
The main problem is if Arrthur and Alice decide to team up against Charrrles. This is unlikely though since Arrthur would have to trust Alice, (while also inviting the wrath of Charrles), so that would probably only happen if Arrthur was really gullible.
I don't know if you could extend this to more than 3 pirates though.
Matt's tactic seems to work fine, given that the piratical pie eaters are expert slicers, perfect judges of slice size, and seek most of all to maximize their own consumption. It will work for any number of pirates in a simple manner: have one person do all the slicing and also receive the last slice after everyone else chooses in any order.
Wikipedia has a substantial article covering fair division and mentioning the Talmud, envy-freeness, the Potsdam Conference, moving knives, the Econometric Society, and the tragedy of the anticommons. Good old Wikipedia.
Post a Comment