Obscure how-to

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.