One approach is to split the land evenly. But even this method can get complicated if we add some realistic assumptions. Today’s puzzle illustrates why splitting land can be a mind-boggling exercise.

The problem

“Your father owns a rectangular field, from which the city has appropriated a smaller rectangular patch. He wants to split the remainder between you and your brother so that each of you two gets equal area.

How does he do this?”

And let’s add one more restriction: how can he split the land using a single straight line?

(Source: Janko Gravner, UC Davis, Advanced problem solving, Problem set 1)

Example shapes

Here are a few shapes to get you started in brainstorming. The big rectangle is the original land and the shaded grey area is the land appropriated (i.e. removed) by the city. How can you divide the remaining land equally using  a single line?

The solution is a general algorithm that should cover all of these cases:

Corner

Side

Middle, parallel

Middle, skewed

Hints

As a bit of history, this puzzle is sometimes used as an interview brain teaser or technical question when testing job seekers on their problem solving ability.

It is sometimes stated in the following terms: how can you split in half a rectangular piece of cake, with a small rectangular piece removed, using a single cut from a knife?

Can you figure out an answer?

The difficulty in this puzzle is the smaller rectangular piece can be in any place and in any orientation. Notice the removed piece does not have to be in a corner, on a side, or even be parallel to the sides. The removed piece can be angled and skewed and placed anywhere.

And while you’re brainstorming, remember the solution has to come from a single straight line division.

Solution:

Normally I have included answers in the post. At a reader request to avoid spoilers, I have moved the solution to the comment section

Alternately you can read another solution writeup here.

The video is about an experiment where children are asked to share a pile of chocolate coins. The twist to is they had to follow the rules of the ultimatum game.

Specifically, here is how the game worked. One child got to offer a split of the chocolate (“9 pieces for me, 1 for you”). Then, the other child could either accept the split and take the candy. Or, she could reject the split and both would go home empty-handed.

What should happen? Game theory predicts the proposer has the advantage. In theory, the second player–the one hearing the proposal–should be favorable to most offers. The reason is that rejecting an proposal leads to a zero payout. It is better to get something rather than nothing, so the second player is likely to accept most offers even if she ends up with little. Consequently, the proposer can make almost any offer and will make one that gives him most of the chocolate. In effect, the proposer can make an ultimatum which the second player will find hard to refuse.

Of course, the game does not always works so smoothly in practice. How do the children play this game? Watch this entertaining video on youtube to find out:

Link to youtube video: the ultimatum game

*I am in the dark about the show. I would be very grateful to anyone that can identify the source of this show/experiment.

My video transcription

Narrator: In this experiment, seven and eight year olds are sharing a stash of ten chocolate coins. One child decides on how they are split, and they can offer as many or as few coins as they like.

Children in experiment: [offer various splits from one to three coins]

Narrator: At first they keep more for themselves. But there is a catch. It is the other child who gets to decide if the split is fair. If not, they can refuse the offer. And then, both children have to go away empty-handed. Will they get away with it?

Children in experiment: [almost all reject small offers]

Child 1: What do you mean [you reject]? That means you don’t get any chocolate!

Child 2: I don’t care. It’s already too little.

Narrator: Almost all of the children reject the smaller share, preferring to have nothing at all. It may seem strange, but it is not. By going without themselves, they are punishing their partner who loses even more chocolate. And they are not going to forget that in a hurry. Look what happens when the experiment is repeated.

Children in experiment: [most offer nearly even split]

Narrator: Now, with a fairer split, what will the response be?

Children in experiment: [most accept nearly even split]

Narrator: The children are happy to accept. It is not difficult to see why we have evolved this way. If we react instinctively against people who cheat, they will think twice before trying it again. And it has left us all with a taste of fairness.

This video raises many interesting questions. Here are a few thoughts that came across my mind:

What game are we playing?

In the first round, many of the children give small offers which are rejected. This comes as a surprise to many of the proposers. Why might this happen? It appears the receiver of the offer gets almost no satisfaction from the pittance of an offering. Instead the receiver gets joy from rejecting the offer and punishing. The lesson? The children are playing a larger game. The ultimatum game is not wrong, per se, but it is obvious the children are not playing it. They are instead playing the game of “I want candy, but if you are not fair I will be more than happy to punish you.” And it is the very fact that they change the game that alters the outcome.

Repeated play changes the game

Repeated games can have very different outcomes from one-shot games. In a one-shot ultimatum, one would fully expect low offers to be accepted. But not so in a repeated game. In this experiment, the children likely do better by rejecting the offer in the first game and getting an even split in the second (netting say 5 chips) than they would have been by accepting two sets of low offers (netting say 2 chips).

Fairness is very important in division

It is not always easy to say what is fair. But it is often the case we know what is unfair. Fair division is a topic that comes up time and again, in splitting bills, determining homeowner fees, and even in eating peanut butter and jelly sandwiches.

The children are obviously concerned with a fair split which affects the outcome and prevents the offerer from making unreasonable ultimatums.

Discussion questions

1. How might the game change if the children played with other foods like vegetables or slices of pizza? Or money?

2. Do you think the children knew the game would be repeated?

3. Would the outcome be different if the children switched partners between the first and second games?

4. How would the game be different if the recipient could give a counter-offer? [this is sometimes called the double ultimatum game]

5. Comment on how this experiment is similar to the song “Before He Cheats” by Carrie Underwood [video on youtube]

6. Offers to the ultimatum game vary worldwide. Summarize some of the differences as summarized in Tom Siegfried’s article “Social Thermometers” in The Dallas Morning News [link to article - .doc file]

When I first got this question, I was hard pressed to find an answer. Game theory is a mathematical science, and many presentations can be intimidating. For example, many journals and textbooks are so complicated that it takes a mastery of Bayesian probability, set theory, and real analysis just to understand the problems! This is a tragedy, for a subject as interesting as game theory should be made accessible.

So over the last few years I have kept a special eye out for books aimed at general audiences. And I am glad to say there are a few good books on game theory.

I have listed the books I have especially enjoyed in a separate blog page about recommended books. And to do them justice, I plan to write full reviews on each of my favorites so you get a better idea of them.

Today I will discuss Rock, Paper, Scissors: Game Theory in Everyday Life by Len Fisher.

What the book is about

There are two quotes in the “praise” section that nicely summarize the book:

“Why be nice? In answering this simple question, Len Fisher takes us on a wry, fascinating tour of one of the most momentous sciences of our time. You couldn’t ask for a better guide to all the games we play.”
–William Poundstone, author of Gaming the Vote and Fortune’s Formula

“Rock, Paper, Scissors is a refreshingly informal as well as insightful account of key ideas in game theory. Len Fisher gives many examples, several from his own life, of games that post harrowing choices for their players. He shows how game theory not only illuminates the consequences of these choices but also may help the players extricate themselves from situations likely to cause anger or grief.”
–Steven J. Brams, New York University, author of Mathematics and Democracy

My one sentence summary is: Rock, Paper, Scissors is a popular science book that connects game theory to everyday situations and suggests several strategies for achieving cooperation.

(As you can tell, this book is a different style from other books I like such a Thinking Strategically or The Art of Strategy. This book is a lighter read and connects more to anecdotes and science.)

Book highlights

I will warn you that the book starts off a little bit slowly. The first chapter “trapped in a matrix” mainly describes the Prisoner’s dilemma and gives the negative connotation that the Nash equilibrium is a logical trap. The matrix graphics are not that illuminating either. Luckily, these setbacks didn’t stop me from reading the rest of the book which is full of interesting examples and explanations.

The second chapter “I cut and you choose” is where the book picks up. This chapter offers a nice introduction to the concepts of minimax and fair division. Fisher illuminates fair division with anecdotes like how he got in trouble as a kid shooting fireworks, and as a consequence had to yield fireworks with his brother. The answer he intuitively arrived to as a kid was what he know realizes was an application of the minimax principle. I was also impressed that Fisher discusses the principle of equal division of the contested sum, which I have discussed twice before (regarding religion and homeowner fees).

Chapter three is about seven of the most interesting game theory problems, which Fisher aptly dubs “the seven deadly dilemmas.” Here Fisher offers a great summary of such problems as the free rider issue and the game of chicken.

Chapter four is a humorous one, and is about the game “rock, paper, scissors.” It was new to me that rock, paper, scissors is in fact played in most of the world (though under various other names). I was also amused at how rock, paper, scissors can be used in conflict resolution. The reason is that the game has no pure strategy that dominates the others. Hence situations and games which seem to be at a standstill (say too many free-riders in overfishing) can be solved by adding strategies and converting them to rock-paper-scissors situations.

Chapters five through eight are all about cooperation: how we can achieve trust, bargain effectively, and change the game to avoid the “trap” of the Prisoner’s dilemma and other undesirable outcomes. I won’t go into detail, as the main fun points are similar in nature to the other chapters: the narratives and interesting examples from science.

Read the end notes!

One of the best parts of this book is the “Notes” section at the end. This is a substantial part of the book and it is full of narratives, jokes, and random trivia. The end notes are over 50 pages long-and this is for a book that is about 250 pages in total! I am still following up on many of the references and this alone has been worth the read.

Final thoughts

I hope this review gives you a better idea of the book. It is a great introductory read and a good addition for real-life examples of game theory. Check it out:

*I also owe a special thanks to the book publisher for providing a review copy

Hi Presh. I enjoy your blog a lot, and recently a situation arose where I think game theory could be applied, so I thought I’d send you an email to see if you have any opinion on it.

Here in Mexico, “private” neighborhoods are common, which means that the neighborhood is closed to any outsiders, and there’s a guard controlling access and taking care of security. All the neighbors are charged a monthly fee to pay for the guards salary and any extras that might be needed in the neighborhood, such as supplies for the guards, common improvements, etc.

The amount of the fees is decided by a council formed form neighbors. I own a house in one such neighborhood, but I don’t live there and probably won’t live there in the near future, yet the neighbors expect everyone to pay the monthly fee. Since the neighborhood is new, almost half the houses are uninhabited at this moment, so the decision that everyone would pay the fee was taken mostly by the current neighbors. I assume that the other houses will be occupied soon, as it’s a small neighborhood and all the houses have already been sold.

I’ve asked to a couple of friends who live in similar places and they tell me that in their cases, it was decided that people would only start paying after moving into the house, as prior to that, they had not much need for security.

So, on one hand, the neighbors expect me to pay the monthly fee, and on the other hand, I don’t think it’s fair to pay it as the house is empty and I won’t be living there anytime soon. But, I have to consider that I might live there some day, and I wouldn’t want the neighbors to think ill of me.

So, I’m thinking that I might be able to negotiate some partial fee, until I move in there.

What do you think?

My thoughts

(I replied to Hector with a few thoughts. Later I elaborated and here is my current thinking.)

This is a great question–thanks for asking Hector. The topic falls under what is called coalitional or “cooperative” game theory.

The question is: what is the fair division of the fees? How might one negotiate a lower fee?

Fair division is interesting because depends both on game theory and on social customs. As such, there are few universal answers. But there are some methods in fair division which are more popular than others. Three of the fair division methods I’ve discussed before are splitting evenly, proportional division, and equal division of the contested sum. Let’s discuss how these methods might be applicable.

Splitting evenly means simply divide the fees across all houses. The logic here is that it is the house, not the property value or residence, that matters. The arguments for splitting evenly are that its simple to implement and its a forced equality in that everyone pays the same. The arguments against are that its unfair to low-end users (as is your case), and also that splitting evenly can lead to a type of tragedy of the commons where costs are inflated for all. For instance, in the case of splitting the bill at restaurants, a group of three economists have demonstrated an even split leads to inefficient ordering and negative externalities for all.

Another method commonly used is proportional division. Proportional division means each party should pay relative to their contribution to cost (or their size of benefit). In a neighborhood, bigger houses might cost more to monitor and also they receive a larger benefit from security. So a proportional division might translate to homeowners paying neighborhood fees relative to their property values or plot size.

Proportional division is good because it assesses fees relative to costs imposed, and consequently parties will not inflate costs as in the splitting evenly system. The problem with proportional division is that it requires everyone to agree on a valuation system. Also, if it is hard to track payments (like when collecting money in a large restaurant group), some parties are likely to underpay. The shortfall is usually covered by the group evenly.

A final method worth discussing is equal division of the contested sum. This fair division method was first discussed over 2,000 years ago in the Jewish Talmud. It’s an interesting method that depends on splitting the disputed sum or the gains of negotiation. (See a detailed explanation in how game theory solved a religious mystery)

Here is a simplified example where equal division could be applied to a homeowner setting. Suppose that an inhabited house would cost $100 to maintain and secure whereas an uninhabited house would cost $50. But if both ordered together, they could negotiate a reduced fee of $120. Both can gain from cooperation, but how should the cost be split?

A first approach might be to split the cost evenly at $60 a piece. But this solution is not appealing, as the owner of the uninhabited house has to pay more than if he negotiated alone. Another method could be proportional division of the cost. In this case, the split would equate to a cost of $80 for the inhabited home and $40 for the uninhabited home. This is reasonable, though one can see the savings are uneven. The cost for the inhabited home falls by $20 versus the cost for the uninhabited home falls by only $10.

So another way to approach the situation is to split the savings equally. First, we need to calculate the savings from joint negotiation. We can see that if each owner went alone, it would cost a total of $150 as opposed to $120 in joint negotiation. This means there is a potential of $30 in savings from cooperation.  Accordingly, if each party gets half of the savings, then each should get $15 back. This means the costs would be $85 for the inhabited home and $35 for the uninhabited home. This is one application of equal division of the contested sum. Notice the result is close to proportional division though not exactly the same.

So after saying all of this, which method seems best? I leave it for you to judge, but I will mention the custom in my area. The closest analogy in my state is homeowner association fees or condo association fees. These fees cover costs like maintaining common lawns, amenities like pools and gyms, repairs, and so on. These fees are generally split evenly to the dismay of many residents.

And that is why I am anxiously awaiting an association that proposes an equal division of the contested sum

Discussion questions

1. Why do you think homeowner association fees are often split evenly?

2. Naturally homeowner association fees increase over time to reflect inflation and other cost increases. Why else might homeowner association fees increase? See the following: HOA fees rising in California.

3. During a bad economy, would you expect homeowner association fees to rise or fall? How might this change if costs were shared differently? See: fees on the rise and adverse selection example.

Here’s one story I especially enjoyed:

My dad heard this story on the radio. At Duke University, two students had received A’s in chemistry all semester. But on the night before the final exam, they were partying in another state and didn’t get back to Duke until it was over. Their excuse to the professor was that they had a flat tire, and they asked if they could take a make-up test. The professor agreed, wrote out a test and sent the two to separate rooms to take it. The first question (on one side of the paper) was worth 5 points, and they answered it easily. Then they flipped the paper over and found the second question, worth 95 points: ‘Which tire was it?’

Source: excerpted from Marilyn vos Savant, Parade Magazine, 3 March 1996, p 14.

Besides being a nice story, the situation raises some interesting questions in game theory.

Coordination games

The students found themselves in an interesting situation. It mattered less what they answered and more that their answers matched. Such a situation is generally classified as a coordination game.

A coordination game is one where all parties stand to gain and all wish to coordinate. Common examples include the convention of a driving side (left or right), the arrangement of letters on a standard keyboard (qwerty or dvorak).

In such games, the worst choice is for players to miscoordinate and the best is for them to match. Thus, the strategy in coordination games is simply to match what other players might do. If possible, you may signal try to announce your intentions in advance.

Sometimes players are helped because some choices seem natural or attractive. I wrote about topic before in coordinating bike traffic but let me recap the main idea.

Suppose, for example, that I surveyed people today to name a Nobel Peace Prize winner. While I would get a variety of answers, I bet I would find many answers of Barrack Obama since this award is topical and controversial. Obama is a natural answer to the question, and such information is useful when coordinating. More generally, there are choices people consider more prominent for things like naming a person, a number, or a place. This was an observation developed by Harvard economist Thomas Schelling, and the concept is named Schelling points in his honor (or sometimes called focal points).

Now that the stage is set, let us consider how the students might fare in guessing the same tire.

What is the probability they guess correctly?

There are four possible tires to pick: the front-right, front-left, rear-right, and rear-left. The probability they guess correctly is the sum of the probabilities of matching on any of these choices.

To get an estimate, suppose each choice has an equal chance of being picked. Then the probability of guessing correctly will equal to one-forth. That’s because there are four correct matches divided by sixteen pairs of answers. (Alternately, conditional on the first student making a choice, the second student has a one in four chance of making the same selection).

But lucky for the students, the actual chance of matching will likely be even higher. The reason for this is that one of the tires is like a Schelling point and more often to be picked. As discussed in the free textbook Introduction to Probability, an informal classroom survey found that 58 percent chose front-right, 11 percent front-left, 18 percent rear-right, and 13 percent for rear-left.

If we take these probabilities, then the chance of matching is about 40 percent (equal to 0.58 squared plus 0.11 squared plus 0.18 squared plus 0.13 squared). That’s a nice increase from random chance!

Discussion questions

(I am trying something new in this article. I’m adding several discussion questions to help teachers and students. So, here goes–and let me know if you like this section.)

1. The story takes it for granted the students are lying, and the teacher would punish them even if they matched on their alibi. But suppose the students were telling the truth. What steps could they take to signal their honesty?

2. Let’s be honest: a flat tire is not a great excuse. A flat tire is easy to fix and roadside assistance can be relatively quick. What alibis would be more believable? What makes them better?

3. Perhaps the professor was being too nice. The test question actually allowed the students a chance to match by pure chance. What other questions might the professor have asked?

4. Suppose the professor was trained in game theory. Perhaps the test question might have been the following:

“You may pick one of the following options.

• Option 1: Which tire was flat?
• Option 2: Name as many elements from the periodic table as you know.

Now before you answer, let me tell you how I’m grading this question. If you both pick option 1, then I’ll give you full credit only your answer matches what the other student writes. Heck, I’ll even be generous–I’ll give you half credit if your answers don’t match. But there is a catch: if you pick option 1, and the other person does not, then I will give you no credit.

If you pick option 2, I’ll give you one point per element correctly listed. I’ll give you points regardless of what the other person does.

Choose carefully, and good luck!”

What are the Nash equilibria of this game? Hint: how does this game compare to the stag-hunt game?