Schneier on Security
A blog covering security and security technology.
« Password Advice |
| An Ethical Code for Intelligence Officers »
August 11, 2009
There are several ways two people can divide a piece of cake in half. One way is to find someone impartial to do it for them. This works, but it requires another person. Another way is for one person to divide the piece, and the other person to complain (to the police, a judge, or his parents) if he doesn't think it’s fair. This also works, but still requires another person -- at least to resolve disputes. A third way is for one person to do the dividing, and for the other person to choose the half he wants.
That third way, known by kids, pot smokers, and everyone else who needs to divide something up quickly and fairly, is called cut-and-choose. People use it because it’s a self-enforcing protocol: a protocol designed so that neither party can cheat.
Self-enforcing protocols are useful because they don't require trusted third parties. Modern systems for transferring money -- checks, credit cards, PayPal -- require trusted intermediaries like banks and credit card companies to facilitate the transfer. Even cash transfers require a trusted government to issue currency, and they take a cut in the form of seigniorage. Modern contract protocols require a legal system to resolve disputes. Modern commerce wasn't possible until those systems were in place and generally trusted, and complex business contracts still aren't possible in areas where there is no fair judicial system. Barter is a self-enforcing protocol: nobody needs to facilitate the transaction or resolve disputes. It just works.
Self-enforcing protocols are safer than other types because participants don't gain an advantage from cheating. Modern voting systems are rife with the potential for cheating, but an open show of hands in a room -- one that everyone in the room can count for himself -- is self-enforcing. On the other hand, there’s no secret ballot, late voters are potentially subjected to coercion, and it doesn't scale well to large elections. But there are mathematical election protocols that have self-enforcing properties, and some cryptographers have suggested their use in elections.
Here’s a self-enforcing protocol for determining property tax: the homeowner decides the value of the property and calculates the resultant tax, and the government can either accept the tax or buy the home for that price. Sounds unrealistic, but the Greek government implemented exactly that system for the taxation of antiquities. It was the easiest way to motivate people to accurately report the value of antiquities.
A VAT, or value-added tax, is a self-enforcing alternative to sales tax. Sales tax is collected on the entire value of the thing at the point of retail sale; both the customer and the storeowner want to cheat the government. But VAT is collected at every step between raw materials and that final customer; it’s the difference between the price of the materials sold and the materials bought. Buyers wants official receipts with as high a purchase price as possible, so each buyer along the chain keeps each seller honest. Yes, there’s still an incentive to cheat on the final sale to the customer, but the amount of tax collected at that point is much lower.
Of course, self-enforcing protocols aren't perfect. For example, someone in a cut-and-choose can punch the other guy and run away with the entire piece of cake. But perfection isn't the goal here; the goal is to reduce cheating by taking away potential avenues of cheating. Self-enforcing protocols improve security not by implementing countermeasures that prevent cheating, but by leveraging economic incentives so that the parties don't want to cheat.
One more self-enforcing protocol. Imagine a pirate ship that encounters a storm. The pirates are all worried about their gold, so they put their personal bags of gold in the safe. During the storm, the safe cracks open, and all the gold mixes up and spills out on the floor. How do the pirates determine who owns what? They each announce to the group how much gold they had. If the total of all the announcements matches what’s in the pile, it’s divided as people announced. If it’s different, then the captain keeps it all. I can think of all kinds of ways this can go wrong -- the captain and one pirate can collude to throw off the total, for example -- but it is self-enforcing against individual misreporting.
This essay originally appeared on ThreatPost.
EDITED TO ADD (8/12): Shotgun clauses are an example of a self-enforcing protocol.
Posted on August 11, 2009 at 6:15 AM
• 68 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
Although cut-and-choose prevents cheating, it's not "fair" - the cutter will always end up with slightly less than the chooser. The cutter can try and minimize this unfairness, but they will always be slightly worse off than the chooser.
In a one-off situation this normally does not matter, but when the same protocol is repeated the unfairness can mount up. I was the oldest child so I always had to cut, so my brother always got a slightly bigger piece of cake than me. Over the years the small inequality mounts up...
When a self-enforcing protocol is repeatedly used it may need to be modified for fairness. So, for example, cut and choose becomes flip a coin, cut and choose.
I first read of cut-and-choose in Primo Levi's book 'Moments of Reprieve' - it was the method used by people who had partnerships in the camps in WW2.
It was partnerships and the methods that enabled some people to survive...
So not just for kids and people doing pot!
I don't fully agree on the VAT. First of all the full amount is due on every step in the chain - you have to claim back what you paid when you bought the goods and pay yourself the full VAT amount. The difference is indeed a small increase, reflecting the VAT on "your" added value. But first you pay out and claim back full amounts.
Then there's one big flaw which you ignored: Not paying the VAT in the final step incentivates everybody. The customer as he has a lower price, the seller as he has less hassle. Or can make a bargain.
Different countries have found different ways to enforce VAT, so you better take the receipt when you buy some ice cream in italy - or the financial police can accuse you (and the shop owner) of VAT fraud (no joking, locals will advise you to *keep* the proof).
Sorry I was not clear enough: The customer has to pay the *full* amount of the VAT, so not paying the VAT means a discount of up to 20%. That's where your line of arguing does not work out :-)
yeah, "pirate's gold" example shows clearly that - for example - one rogue pirate (more twisted then others) can intentionally cheat and strip follow pirates from their gold... real world episodes are proof validating such option. protocol is weak, and is based on very unpractical assumptions.
VAT is indeed a lousy example, with a great deal of extra overhead and windows of opportunity to exploit the gap between collection and refund ("carousel fraud", for example) - a simple £1,000 purchase might involve transferring the VAT on £10,000 or more in a dozen separate transactions, each of which then needs to be audited, recorded and enforced, with potential for error or fraud at each step. More self-defeating than self-enforcing, with the number of extra vulnerabilities it introduces! (The alternative, exempt business-to-business transactions, then simply audit retailers to ensure they aren't falsly declaring retail transactions as b-b - trivial, and a vulnerability which exists in VAT as well. Indeed, VAT already works in exactly that way within the EU, because the VAT mechanism simply doesn't scale internationally.)
Cut-and-choose also works in dividing assets in a divorce: Each puts a price on the items they want, then the other chooses either to accept the money and lose that item, or pay that price and take the item.
what happens when both want the same item? or if I bid high on an item the other absolutely wants (the grandmother's mirror?)
I wish I had a dime for every time I heard the word 'seigniorage'.
What if the "Greek government" simply wants to buy my site but I do not want to sell? Does not seem fair to me...
Cut and choose also needs a homogenous object. If an omnivore and a vegan are sharing a pizza which is half mushroom and half sausage, the omnivore should cut perpendicular to the toppings so the vegan will forfeit his claim (or half his claim).
One thing all self-enforcing protocols will have is transparency. In the voting example, you could have everyone face away from each other and ring a bell instead of raising a hand. Some of the privacy is returned, but then you have to make sure someone does not have more than one bell. Is there a way to have a self-enforcing protocol with anonymity?
"Here’s a self-enforcing protocol for determining property tax: the homeowner decides the value of the property and calculates the resultant tax, and the government can either accept the tax or buy the home for that price".
It sounds clever, but it doesn't allow for the fact that "a house is not a home". I know what my house is worth, but I don't want to sell it. You could offer me $50K above the market value and I still wouldn't be remotely interested. Because of all the hassle, and because I like being where I am. So the upshot of this rule would be that everyone who feels the same as I do would be forced to pay property taxes that are way, way too high - just to be sure the government won't exercise its option and put them on the street.
If the govt wants to buy it and you don't want to sell? Here in the U.S. it's called "eminent domain", and the govt entity (sometimes in collusion with a judge) sets the value that you are to be paid.
In the Greek system, at least, you're guaranteed to be paid what you value the property at.
Cut and chose is only self enforcing on one assumption which may be false (for a whole variety of reasons).
If the person doing the cutting actually want's a smaller portion then the protocol fails in their favour.
All self enforcing protocols fail for this reason.
The problem is you do not know when it is going to work or not or why the other person wishes to lose.
For instance you have the case of the pot smokers. In some juresdictions the amount you carry can result in a different punishment if caught.
If you assume it's 1 once and there are three people who club together to get 3 ounces at a "bulk discount rate" the person doing the dividing might have reason to think the supplier or one of the co-buyers is possibly an agent.
It is in their interest to make sure one piece is definatly less than 1 ounce whilst the other two are more than an ounce. If there is a bust then the cutter has the smaller part and gets the smaller sentance.
Tom, I assume that is why this is only applied in Greece to antiquities and not property in general. Although, why would the government go and buy up lots of properties at market value or above as there would be no marketability to them. In a properly designed system (with minimal fraud by elected officials, govt employees, etc), unless they could purchase the property for enough under market value to make the resale make up for the tax "underreporting" and cost of acquisition and reselling, there would be no incentive to take your home. Unless they wanted to put a highway through it -- in which case they would just use eminent domain and take your home anyway.
Think of the business opportunity for doing land valuations for tax purposes, selling insurance based on the accuracy (that your home won't get bought) ... Property Appraisers would be salivating at the prospect ...
I'm sure, Clive, when you get done dividing your three little baggies that if you offered the cutter a "bonus bud" from your bag for his efforts he wouldn't turn it down -- and if he does then be suspicious.
Actually, if you choose and pick the larger one, but the cutter actually wanted the smaller (of whatever we're dividing), why is this bad? It sounds like even better because everyone gets what they wanted! This isn't supposed to be a competition to see if we can screw the other person.
Also, the cutter should be incentivised to make the segments as close as humanly possible to equal. Isn't that the purpose (and the human nature) of this exercise? Now, of course if you spit on the larger one while dividing the cake with your brother or sister ...
Re not wanting to sell an item. When you factor in transaction costs, there's no way the government would pay over market, in fact they'd only exercise the option to buy if your self-valuation is lower than market less transaction costs...ok there may be some very small subset of cases like buying an antiquity that has some symbolic / political value, but that doesn't invalidate the usefulness of the protocol in 99.999999% of cases.
Dividing a cake != cutting it in half. there's no such thing as a bigger half.
1. Pirates usually operated on a shares basis, so they would just take their shares back from the total in the safe.
2. Alan Porter: Ha! Well I wish I had a mil for every time I heard the word "arbitrage".
@Clive Robinson: «If the person doing the cutting actually want's a smaller portion then the protocol fails in their favour.»
Nope. If you have the bigger portion, you also have the smaller portion. You just have to throw away what you don't want.
(The assumption being, obviously, that the cake is homogeneous, but you will kindly agree to stop splitting hair at this point. Thank you.)
"I wish I had a dime for every time I heard the word 'seigniorage'."
Change "heard" to "read", and I'd be up to twenty cents now.
I would really like to read more on the actual protocols.
Another self-enforcing protocol is seen with horse racing. As I understand it, any horse that's raced is implicitly for sale for a value determined within the class of race and can be claimed by any other competitor. This prevents world class race horses from competing and consistently winning the easy money against lesser horses.
How about a self-enforcing protocol for pay and benefits? Instead of a 'minimum wage', have a maximum wage: the maximum wage being a multiple of the compensation for the lowest paid person in a company (I have the multiple as around 10 log(n) where n is the number of employees). If you want to pay yourself more (as the head of a company), just hire more people, or increase the pay of the lowest paid employee. It does more good for a small company to hire more people (you get a faster increase in pay by increasing the multiplier), but large companies do better to increase benefits.
There would need to be some wrangling about the exact size of the multiplier, what 'compansation' means in this context, and how it would be enforced, but that's the basic idea - comments?
Jo, Ben&Jerry's had just that sort of wage compensation plan for quite some time, with a 7x multiplier.
"For example, someone in a cut-and-choose can punch the other guy and run away with the entire piece of cake."
Depends on who's doing the punching. The guy with the knife or the guy without the knife.
Barter isn't necessarily self-enforcing either, particularly for one-time transactions. If one party defrauds the other--spoiled eggs, a sick animal, fake gold or diamonds, etc.--then the defrauded party must either go after the defrauder for damages, or appeal to a third party. Only when reputation is at stake is barter necessarily self-policing.
I love the concept, but of course in the IT industry everything is outsourced so a majority of your labor is not paid by the company. You would end up with Large corporations that only have management and are even more incentivized to outsource their lower paid employees. The less you pay the lower rung the more you can pay your management.
Tack, that's called a "claiming race." It's used in auto racing as well. The 24 hours of Lemons (http://www.24hoursoflemons.com/) series works like that--they keep the cars even by capping the vehicle price at $500 (not counting safety equipment), and entering a race gives the judges an option to buy your car for $500.
@martin, cut and choose is "fair" in the game-theory sense, it's just not guaranteed to have a perfectly equitable equilibrium strategy.
That said, I'm pretty sure (refutations welcome) that the problem you're describing is "provably present" for any game in which the payoff matrix includes non-discrete (i.e. further-divisible) payoffs.
Part of this is just the difficulty with any kind of game in which defining the payoff matrix (the "rules" of the game that define who wins, how much, under what circumstances) is part of the game itself. If payoffs are predefined and immutable, then rational strategy can be deduced or induced, and compared with confidence, at least in theory if not in practice. If payoffs are undefined but discrete, there's the extra step of negotiating what the payoff matrix should look like, but it's still just a sort of meta-game, still accessible to either deductive or inductive certainty, with various outcomes of the payoff matrix as the payoffs. Mmmm, meta. :)
The homogeneity-of-the-cake issue is critical, as is the desire for both parties to maximize or minimize their share. The benefit of cut-and-choose (and friends) is that they allow equilibrium strategies in games where the payoff matrices can only be approximated, even if calculated to an arbitrary precision. They can't iterate to a perfect static equilibrium the way some games can -- the best they can do is to be "fair." But "fair" is something they can definitely be. In cut-and-choose you just have to make sure the cut and the choice change hands across iterations.
Self-enforcing protocols are useful under other circumstances as well, but I think that where there's no "correct" payoff matrix, some sort of self-enforcing protocol is the only way for an equilibrium to emerge.
"but you will kindly agree to stop splitting hair at this point. Thank you"
As a person who is older than Bruce I could say,
"Hair what hair" ;)
@ B. Real,
"Now, of course if you spit on the larger one while dividing the cake with your brother or sister ..."
Hmm I'm not sure you had a brother or sister as mine would have gone "Mom he spat on the cake". At which point I would have wound up doing time in my room not eating cake.
The way you do it is to "sneeze all over the cake" then nobody (except you) want's any of it, and when the "Mom" shout goes up you can say you "couldn't help it".
The trick as they say, is not in "skining the cat" but "getting the cat to jump out of it's skin".
Seriously though these self enforcing protocols normaly assume that everybody has the same objective and more often than you'd think the objectives of a player are not what is expected.
If you like a player decides to lose out to gain a bigger advantage. I used to see this when I'd carry golf clubs as a young teenager. You would see some bloke play a realy good game at the weekend but during the week you could tell if it was a person that they wanted something from as they would have a wager on the game with their guest and then lose by just a little.
There are a whole load of "sucker" or "come on" games and this is what people do frequently.
Have you ever noticed in an office if a girl has made the mistake of mentioning she's on a diet her (so called) friends conspire so she gets left with the big slice of cake...
> The cutter will always end up with slightly less than the chooser.
This assumes that the chooser has access to measuring devices of greater precision than those accessible to the cutter, or that the cutter is incapable of cutting with a degree of precision that matches his or her measuring ability... which is rarely the case.
In theory, this is a dilemma. In practice, this is a non-issue.
One of the real reasons self-enforcing protocols are so effective is that you rarely need to audit the process, thus bypassing the overhead of audit. In fact, I'd argue that:
> But perfection isn't the goal here; the goal is to reduce
> cheating by taking away potential avenues of cheating.
... the goal is not to reduce cheating by taking away potential avenues of cheating, but instead to reduce the necessity for *checking* for cheating, making the overall transaction cheaper.
It's a fine distinction, but it eliminates the side discussion B. Real and Clive are having -> you're not trying to prevent someone from gaming the system, you're trying to prevent the overhead of using audit to prevent someone from gaming the system. Now your countermeasures towards other types of gaming the system can be more clearly defined, inside that context.
Casey hit on the importance of homogeneity of the contested *item*, but what's more important, I think, is that the *parties* must be absolutely equal: equal in their knowledge, equal in their goals. In Casey's example dividing a meat/veggie pizza, the problem isn't the pizza, it's the fact that the omnivore and the herbivore have different desires.
People have complained about the "property tax" scheme, the Greek antiquities scheme, and someone mentioned "shotgun clauses" and "claiming races". All of these put the parties in the role of becoming either a possible buyer or a seller of something without knowing whether or which way the purchase will go. That works fine if both parties are ambivalent about having cash vs property, but if there are unequal external factors to consider (sentimental attachment, closing costs and moving expenses, limited capital, etc.) the system fails.
In short, these systems work great if people are equal. Often, they're not.
Oh, one final note: self-enforcing protocols also require that the object of value be either divisible or financially liquid. For instance, it doesn't work on babies: http://en.wikipedia.org/wiki/Judgment_of_Solomon
"Self-enforcing protocols are useful because they don't require trusted third parties."
This reminds me of the American old-West.
Two men in a dispute reportedly would seek a woman to hear and decide their issues, as women were seen as more thoughtful and impartial than any man.
When no woman could be found primitive competitions were invented.
I also am reminded of a great tradition of philosophers on this topic who are suspiciously absent. As you constructed your argument for social process you could have mentioned at least Hobbes who wrote many fine points against any system of nonlegal controls. Perhaps that is why the article looks more to me like a mathematician's study of computational probabilities, and why you regularly admit it will fail when faced with actual human behavior.
"Cut and chose" is not a protocol, at least not as described.
But I'll play:
I cut the slice of cake with one slice slightly larger, but there's a secret poison pill in that slice. The other gal gets the larger piece, but I get her good-looking husband and all of her possessions.
The rules for the LeMons series are a fun read, and they add several strong disincentives to bringing a ringer. My personal favorite is the "People's Curse" On the second day, a poll is taken. If your car is chosen (for whatever reason), you are pulled in and your car is crushed...
@Sheila: "cut and choose" doesn't say the non-cutter gets the larger slice, it says they get to choose. So given your example, she may choose the smaller piece and you are left with the "poison pill".
Another thought is you might get her "good-looking husband and possessions", but you might find he beats and abuses you and the possessions come with her debt.
As they say -- "Be careful what you ask for, you might get it".
I was first introduced to 'cut and choose' in college. The version we used (it was usually for pizza, with a not-quite-homogeneous spread of pepperoni) was slightly different, giving both parties a better opportunity to be happy with the result. Cutter positions the knife and asks, "If I cut here, which piece will you choose?" Chooser indicates a choice. Cutter repeats with other knife placements until satisfied that the one of the proposed cuts will be satisfactory. I don't recall if the chooser was constrained to make the same choice after the actual cut, though.
@Tack: "Claiming" races are a fraction of the all the horse races. Most are straight handicap races with a total purse divided amonst the top finishers and no right to claim attached.
@ Pat Cahalan,
"you're not trying to prevent someone from gaming the system, you're trying to prevent the overhead of using audit to prevent someone from gaming the system."
Your observation is right on the button.
@ Davi Ottenheimer
"Perhaps that is why the article looks more to me like a mathematician's study of computational probabilities, and why you regularly admit it will fail when faced with actual human behavior."
Which is also partly my point.
The problem with the "cut-n-chose" system is there is not one "null hypothosis" but many for each participant and that means it is "an incompleate system" as far as logic is concerned.
"In short, these systems work great if people are equal. Often, they're not.
Oh, one final note: self-enforcing protocols also require that the object of value be either divisible or financially liquid."
Your 99.9% of the way there, the "cake" can also be tradable between the parties in an "equitable" maner as they see fit (for instance after we rob a house - you get the paintings and I get the jewlery as we both find that acceptable).
@ Sheila, Mitch Wright,
"Humans don't you just love em" 8)
"Known by ... pot smokers..." -- we just won't say *which* (long haired hippy freak) pot smokers, will we ;-)
The idea is to take turns being the cutter and chooser. In an equal number of rounds, this shouldn't unfairly disadvantage either party.
However, some halves may be more desirable than others. More icing, more edges, more flowers, more nuts, etc. Size isn't everything. With the article-mentioned "pot smokers", weight isn't the only quality of attractiveness. Back in my college days, I saw a cut that was very uneven in the weight category, but was a fair cut because the choice was a lighter weight of tops versus a greater weight of shake/stems.
I proposed a management level multiplier of 1.5. You couldn't earn more than 50% more than the Median/Max/Avg salary than the level below you. To prevent worthless 'stacking', you had to manage at least 4 people to qualify as a manager.
Around 7:09 of this Top Gear video, you will see James May rally race in Finland where any driver may buy your car after the race for a pre-set price (to keep people from pouring money into their racing vehicles).
Note: if you are a race fan, watch from the beginning to see Mika Hakkinen teach James to drive.
Sidenote: it is possible to create 'cut and choose' algorithm for three parties (algorithm by Hugo Steinhaus, if I remember correctly), but generalization to n parties leads to many fragments and many cuts (but is possible).
One of the problems with cut-and-choose is that the cutting action (whatever it is) can destroy some of the value of the original intact item. When you cut a cake, for instance, you end up not with two pieces, but with two pieces and some crumbs that fell off. With more cuts, you have more of a problem; the average size of a piece tends to get smaller and more crumb-like, and the "equal" shares are more likely to be composed of slivers and crumbs.
All the multi-party cut-and-choose variants I've seen have this problem - you can assure that everyone gets a their choice of several piles of crumbs and slivers, but you can't assure anyone a presentable slice.
How about a voting system where, at each election period, a totally random and unique number is assigned to voters.
Each voter knows what their unique number is, but no-one elses.
The unique number and the vote is recorded in a simple database which is released to the public during / after counting. Perhaps split up by state / electorate etc.
The individual votes can be verified by voters (Add in avenues for dispute, etc) and the data as a whole can be analysed by the general public while maintaining anonymity.
@Nick: and how do you know a voter crying wolf is telling the truth? What can be done when an individual or group claims their votes were changed? How does the voter prove he was assigned a particular random number? -- a token that can't be easily counterfeited?
...and what happens when someone stuffs thousands of fake votes into the system? Nobody complains because their votes were counted correctly.
@Boris: That is why I wrote about special case of three-party cut-and-choose, which like two-party one can be done with minimal number of cuts and minimal number of crumbs.
Re: property tax as a self-enforcing protocol: Some have already mentioned the liquidity argument and the "house is not a home" problem. On the flip side of that equation, it opens the possibility of increased government domain.... also it forces you to do well when the government is doing well, or else. In a capitalist economy, I think such a system would ultimately eat itself. Plus, rental home investors would set their tax prices at some acceptable profit level above what is owed on their mortgage, and house prices would suffer in the long term, as would the renters living in those homes. It's self-enforcing, but it is not self-balancing.
It's intriguing as an instant analogy for explanatory purposes, but it would be utterly impractical in the real world.
a better solution to the pirate story: if all the amounts are incorrect, the pirate will throw all the gold overboard. there would be even less temptation to cheat, as long as the captain is capable of enforcing that...
Bruce - there is NO SUCH THING as a self-enforcing protocol because they are all tied to the Network Transport Protocol they are layered on. What you can do is produce end-to-end application layer reports but they are also suspect because of cool flaws in IP like the BGP4 routing flaw.
So... if you want real evidence you need to look to third parties. Sorry but that's the way it is.
Todd Glassey CISM CIFI
Any interesting books on this topic?
@jbl: '"Claiming" races are a fraction of the all the horse races. Most are straight handicap races with a total purse divided amonst the top finishers and no right to claim attached.'
Assuming that by "fraction" you mean something less than 70%, in what mythical land of horse-racing is this? Dubai? (wait, actually that statement is probably true for Dubai...) I can only speak for North America and the bit of Australia that shows up late at night on TVG, but I read a lot of condition books, and it is certainly the case that most horse races are claimers. That is probably for the competitive reasons cited above.
It doesn't always work in a straightforward fashion, however. Weekend before last, our filly ran 2nd by a nose in a $10k Nx2 claiming race; its time would have handily won the higher-paying allowance race at that distance at that track that weekend. That is to say, both our horse and the winning horse were entered in the wrong race. We'll look to rectify that this weekend or the next.
Of course there are even more security wrinkles to the "horses for courses" game. Some owners would be tempted to arrange for their horse to run second repeatedly, in every maiden race they enter, all season long. If you know your horse can't handle open competition, this might be the way to make the most money. However, this would require the collusion of other parties whose interests do not perfectly align with those of the owner. You might find some trainers who would go along with the scheme, especially if you had many horses in their stable. However, the stewards are watching every race very closely for the slightest indication of jockey malfeasance, and no jock would risk getting set down for a year just so some cheapskate owner could nickel-and-dime the maidens.
Cut-and-choose works even in instances of bad faith. Hasn't anyone here seen The Princess Bride?
"You can't have chosen the cup in front of me, because..."
>Cut and choose also needs a homogenous object. If an omnivore and a vegan are >sharing a pizza which is half mushroom and half sausage, the omnivore should cut >perpendicular to the toppings so the vegan will forfeit his claim (or half his claim).
This is almost completely wrong. Assuming that the omnivore likes sausage as much as mushroom, he should cut a piece which is 1/2+epsilon of the mushroom section, and another piece which contains all of the sausage and 1/2-epsilon of the mushroom. He then gets all of the sausage and nearly half of the mushroom.
If he uses your method, the vegan will take his half of the pizza, eat the mushroom bit and throw away the sausage piece (or feed it to his dog).
Similarly, if the vegan cuts he will leave all of the sausage to the omnivore and take as much of the mushroom as he can get away with.
It is not a *problem* that the omnivore and the herbivore have different desires, it just means that an efficient division (or even a fair division) is going to result in the omnivore getting more pizza.
"You divide, I choose" is not self-enforcing for fairness. If the divider has sufficient information (and preferences differ), he does much better.
For instance: I like chocolate and vanilla ice cream equally. My brother like chocolate only. We have equal amounts of both. If I divide, he gets 60% of the chocolate and no vanilla; I get 70% of the total ice cream. If he divides, I get all the vanilla and a tiny amount of chocolate.
Shotgun clauses aren't necessarily self-enforcing, either. You and I start a company. After a few years, I offer you a price less than your half is worth. You don't have the cash to buy me out at that price. I win.
As a child, I used my knowledge of geometry and optical illusions to my advantage when cutting. I'd cut a crazy Pac-Man shape designed to make the smaller piece seem bigger. At some point a "one straight cut" rule was added.
There is another more serious problem with the cut-and-choose technique, and with any self-enforcing protocols that are similar: the cutter always loses.
Measuring is more accurate than cutting, partly because of mechanical inaccuracy, but also because measuring is repeatable whereas cutting is an irreversible one-time operation. Thus, even the best cutter will fail to cut the cake perfectly in half, and so the chooser has the advantage and can take a larger portion. (In addition, cutting tends to be more expensive in effort, cost, resources, etc. than measuring, which adds to the burden of the cutter.)
If this is a single transaction (a single cake), then unfairness is inherent in the system; although it may be minimized, not eliminated, by randomly selecting cutter vs. chooser or by a skilled cutter. Only if this situation involves many transactions (many cakes) can the unfairness be mitigated by alternating or randomizing roles.
In the case of a cake divided with a sharp knife by a skilled baker, a difference of a crumb or two might not matter, but in many cases the difference can be substantial.
So Cutter will divide the cake so that it doesn't matter which piece they get. After the cut, Cutter thinks both pieces are equally desirable.
And Chooser gets to allocate the pieces. Chooser will select the piece for themself that is better (or at least no worse) than the other piece.
So each person gets the guarantee that their piece is no worse (in their own opinion) than the other piece.
But that doesn't mean that there isn't another way to cut the cake and allocate the pieces that would make both Cutter and Chooser happier.
And you still have to work out who is going to cut and who will choose...
Having personal cake valuations, rather than a global cake valuation, makes an optimal division much harder.
No pirate charter I have found on wikipedia gives the captain more than a double share, many only a share and a half. More than a single share went to a few individuals like quartermaster, doctor and carpenter. Everybody else got a single share, whether a topsman, galley staff or gun crew.
I'm pretty sure this is some kind of self enforcing protocol based on having to band together in order to get the booty required to buy supplies to take more booty. A pirate ship requires topsmen to sail, and a gun crew to fight.
They were forced to band together against a common enemy (at least after taking their first prize) as the penalty for piracy was usually painfully lethal.
Compare this to the pay structure on naval vessels of the era, which did a similar job, and you see a much more uneven distribution. It was probably similar on privateers, as the charter granting legitimacy to the piratical activity of these vessels was awarded to a specific captain.
In both privateers and naval vessels an external entity is involved, which the captains authority derived from, whereas on pirate ships the captain had to satisfy the greed of his crew to gain authority.
@ John Faben
> This is almost completely wrong. Assuming that the omnivore likes
> sausage as much as mushroom, he should cut a piece which is 1/2+epsilon
> of the mushroom section, and another piece which contains all of the
> sausage and 1/2-epsilon of the mushroom. He then gets all of the
> sausage and nearly half of the mushroom.
> If he uses your method, the vegan will take his half of the pizza, eat the
> mushroom bit and throw away the sausage piece (or feed it to his dog).
If he uses *your* method, the vegan will take his half of the pizza, eat the mushroom bit and throw away the sausage piece.
Thus *both* parties get 1/2 +/- epsilon of the mushroom section and the protocol has worked! :)
A lot of the comments here talk about the cake as if the chooser is committed to the benefit of both parties. They are not. Economists and psychologists have shown that people will work so that the unfair person is punished for unfair actions. In the experiments they give person X $10 and tell them to split it between themselves and person Y. Person Y then has the choice to accept the split that person X decides or reject it, in which case neither party gets anything. Now, the personal beneficiary theory says that if Y is offered $1 and person X takes $9, then Y should take $1, cos it's $1 more than Y had, and for no work. But people don't operate that way and will reject the offer because it is not fair. Some will be tempted to accept the 40% of a $4/$6 split, but most people will reject it to punish the decider for being greedy.
In the example Bruce gives, we are talking purely about one incident, but life is a continuous set of interactions and exchanges, and the punishing nature of people shows that you might get away with being clever and greedy once or twice, but you will not win in the long term.
The problem of voting comes along then, and the issue is that we are assuming that both parties like and want a part of the cake. If I don't want part of that cake, then spoiling my vote is my vote. After all, a vegan (mentioned so often in the comments above) does not care which part of the cream cake you want, cos they want neither, and they want a different choice. Options are never binary, though they are often formulated this way.
Just a comment to the first commenter who posted that the cutter always got slightly less--
I was thinking the opposite. With a little psychological edge (like a big brother might have), you COULD manipulate your sibling by cutting a piece a little smaller but making it more attractive--That piece with the flower looks awful good!
In bridge, a party might cheat and revoke (not follow a suit when able). Because the cards played are public, unlike cards in hands, any cheat will eventually be discovered by opponents. In a sense, this is self-enforcing.
Schneier.com is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc.