Hey guys, I’m (again) taking time off for a personal matter. I have a lot of ideas in the works, and I will return as soon as I can deliver a quality article. Those of you subscribed by email or RSS will get the update automatically. Thanks for understanding, and hope to be back soon.

Presh

Yes, getting rich is about saving and earning. But it is also about competition. Winning in the job, stock, and housing markets is about outsmarting opponents and thinking strategically. In such games, it is often important to make the right move before the action begins, as the next puzzle illustrates.

The puzzle

I came across an interesting puzzle in Peter Winkler’s Mathematical Puzzles called “Coins in a Row”

On a table is a row of fifty coins, of various denominations. Alice picks a coin from one of the ends and puts it in her pocket; then Bob chooses a coin from one of the (remaining) ends, and the alternation continues until Bob pockets the last coin.

Prove that Alice can play so as to guarantee as much money as Bob.

The implication of the game is mind-blowing. This is a seemingly fair game that is rigged for the first player. No matter how the second player arranges the coins, it is impossible for him to end up with more money.

Why is this the case?

Getting started

The puzzle is hard to approach because it is difficult to imagine all the distributions of fifty coins of various denominations. So let’s build up from a few observations.

Observation 1: Alice and Bob end up with the same number of coins

Since Alice and Bob alternate picking, they end up with 25 coins apiece. This is a rather trivial observation but it turns out to be useful to solving the puzzle.

Observation 2: If the coins were the same denomination, then Alice and Bob end up with the same amount of money

This directly follows from observation 1. It is easy to see that if all the coins were pennies, nickels, dimes, or quarters, then Alice and Bob would end up with equal valued sums.

This observation again is trivial, but it illustrates that Alice’s advantage comes from the precise arrangement of coins of various denominations.

Observation 3: By going first, Alice can affect which coins she picks

To see this, suppose the coins on the table are numbered 1 to 50 from left to right. The amazing part is that Alice by playing first jcan guarantee that she can pick all the odd-numbered coins 1, 3, 5, … 49, or she can all the even-numbered coins 2, 4, 6, …, 50. How is that possible?

To begin, consider what happens if Alice starts the game by picking coin 1. In this case, Bob is forced to choose among coins 2 and 50. Notice that Bob’s choices are both even-numbered coins. This means regardless of what Bob picks, he cannot grab an odd-numbered coin, and additionally he has to leave Alice with an odd-numbered coin. If Bob picks coin 2, then Alice can pick coin 3 (leaving 4 and 50 for Bob). If Bob picks coin 50, then Alice can pick 49 (leaving 2 and 48 for Bob). This logic can be extended, and consequently, Alice can collect all of the odd-numbered coins.

A similar argument demonstrates that Alice can guarantee she can pick all the even-numbered coins if she starts by picking coin 50.

Putting it all together: the solution

Now Alice’s strategy can be formulated. Before the game starts, Alice computes the sum of all of the odd-numbered coins and the even-numbered coins. One of the two sets has to at least be as big as the other (also an application of the pigeonhole principle).

Therefore, Alice can pick the set that gives her at least as much as Bob.

Bonus: what if the game has 51 coins?

If the game has 51 coins, how does that change the game?

(Hint: Winkler’s text says “However, if there are 51 coins instead of 50, it is usually Bob (the second to play) who will have the advantage, despite collecting fewer coins than Alice.”)

Combating the flu is no small feat. It requires anticipating new strains, developing vaccines, and delivering medicine to masses. And ultimately the success depends on coordination of real people, which means global governments, hospitals, and individuals. Accordingly, there are many strategic issues in fighting the flu that can be better understood using the framework of game theory. Here are three strategic questions:

1. Is the swine flu panic good?

A casual observer might be cynical about the media attention. The death toll so far does not seem to warrant the extensive coverage. Is the fear meant to promote ratings and profits? Is it meant to help the government extend its power?

Perhaps the answer is something more beneficial. Jake at EconomPicData offers an interesting alternative on the swine flu scare using game theory. His matrix suggests that “induce panic” is a dominant strategy (I’ve recreating the text in a slightly more readable table):

link to original

Jake’s analysis makes a good point, but there are a few problems. One is the government plays this game repeatedly with the public over many issues. Calling too many false alarms will damage its reputation and limit its effectiveness.

Second, the entry labeled “nothing happens” for a false scare is not accurate. There is much cost to creating a false panic. Hospital emergency rooms are being flooded, schools are closing temporarily, and governments are banning imports of pork products without solid evidence. In a drastic measure, Egypt killed almost 300,000 pigs without conclusive evidence that the pigs were infected with the virus.

The appropriate answer, therefore, is to walk the middle line. Just as excessive punishment does not deter crime appropriately, excessive fear does not prepare populations cost effectively. The punishment must fit the crime, and the fear induced should fit the facts.

2. When a vaccine is developed, who needs to take it?

There is little question why the elderly and the sick are advised to get flu shots. They account for 90 percent of deaths from the flu, and so the benefit of the vaccination appears to outweigh whatever risks there are.

But what about the healthy and young? The flu is not as likely to affect them, and there are costs and risks to the vaccination. What is the right answer?

From a social perspective, it is beneficial for the healthy to get vaccinated, as explained by Robert Bazell in Slate:

That is the major reason you should get a flu shot. Even if spending a week violently sick and bedridden doesn’t worry you, by immunizing yourself you vastly lessen the chances you will spread the virus to some child or older person (family member, friend, or stranger) who might die from it.

In medicine, this concept is called “herd immunity”-that is, if enough members of a group of animals (including humans) are immunized against a disease, the entire group is more likely to escape infection.

The problem with herd immunity, however, is deciding who has to get the shots. Individually healthy people would prefer not to go through the effort of getting the shot and “free ride” on those who do. The situation is akin to the prisoner’s dilemma, which may explain the low vaccination rate in the U.S.

(Two ways to tackle this problem would be to make vaccinations mandatory and subsidizee flu shots to minimize the cost barrier).

3. Going forward, what’s the best way to select the flu vaccine?

Selecting the flu vaccine is an amazingly complex problem, and the mathematics are stunning. Consider the following simplified and slightly unrealistic math problem (obtained from these lecture slide ppt)

Suppose there are two expected strains of flu and two vaccines that can combat them. The distribution of strains is unknown and one can only guess how effective the vaccines can be.

It is believed that vaccine 1 will have an 85 percent chance of working against strain 1 but only a 70 percent chance against strain 2. Similarly, vaccine 2 has a 60 percent chance against strain 1 but a 90 percent change against strain 2. Here is the matrix to summarize the odds:

Suppose each person can only get one vaccine due to cost considerations. Clearly neither vaccine is effective against both strains. Is there a combination that can maximize the population immunity?

The answer is yes, and the solution is entirely similar to an earlier post about optimizing serves in tennis. If the strains are equally likely to occur, for instance, then give vaccine 1 to 2/3 of the population and vaccine 2 to 1/3 of the population to yield a 76.7 percent immunity rate. (The problem can also be solved for other distribution of strains, per the minimax theorem)

In practice, there are many more issues to be modeled. But even then, game theory and probability are used in both coordinating the supply chain (ppt) as well as selecting the flu vaccine the W.H.O. recommends.

This background got me interested in learning more, and I was pleased to find that Mesquita has given a talk on TED.com giving some insight in to how he operates. In this February 2009 talk, Mesquita explains three predictions about Iran derived from his game theoretic calculations.

The 19 minute talk is available from TED.com (you can also download the video (zipped mp4 or iTunes):

Video link: Bruce Bueno de Mesquita talk on TED.com

(video subject to terms of Creative Commons license)

My reactions to the talk:

[2:20]: A non-technical explanation of game theory. I like the point he makes about understanding limitations of players. Mesquita gives the example that the mathematician Ramanujam was a great person, but limited by geography.

[3:15]: What is rational? This is a highly debated concept (see my discussion about miracles and rationality). Mesquita suggests rational simply means doing what one thinks is good for oneself. He suggests everyone except young kids and those with mental disorders like schizophrenia can be considered rational.

[4:00]: Changing the world depends on understanding influence and incentives. In game theory you do not trust someone because they like you, but rather because it is in their self interest. It is important to see where the influences are coming from.

[5:33]: To predict correctly, one has to pay attention not just to big players, but also small players that influence them. This is what makes game theory interesting is the dynamic among players.

[6:00]: Modeling such small interactions gets complicated. With five players, there are 120 connections one can model among them. This is difficult though not impossible to track mentally. The complexity scales very rapidly. With 10 players, for instance, there are over 3.6 million connections. At this stage one must use computer simulations to keep track of all the data.

[8:00]: Mesquita’s shows a slide that his model works 90 percent of the time, according to a CIA study. This is quite amazing and I am interested in reading how they came up with this number.

[8:25]: The keys to the model are simple: who are the players, what they say they want, how focused the players are, and how much power each player has. Mesquita says he uses public sources and experts to gather the inputs.

[10:15]: What isn’t needed: history! How players get to their current stage has historical importance, but not modeling importance. It is sufficient to accurately model the current situation to predict reasonably well. Interesting idea, but I wonder if taking history into account may do even better.

[11:11]: Three predictions about Iran. I wasn’t impressed by this part of the presentation which goes on for a few minutes. There was not enough detail explaining the somewhat confusing graphs.

[16:00]: Mesquita claims other complicated negotiations can be predicted, like health care, mergers, etc. Interesting hope to speed

[17:40]: The host asks an amazing question: does making the prediction public lessen it’s accuracy since parties might react to it? Rational expectations mean it’s necessary to act by surprise (see article on the Federal Reserve interest rate policy.) Mesquita’s answer: he doesn’t think his model predictions will be affected since negotiations typically end up at the same point regardless, so making predictions public may even speed the process and lead everyone to an agreeable solution without “manipulation” like economic sanctions.

What are your thoughts on Mesquita’s talk?

In such times, it is useful to remember that money isn’t everything. There are many things that cannot be had for money. Here’s an inspirational passage from the writer Arne Garborg that hits the nail on the head:

It is said that for money you can have everything, but you cannot. You can buy food, but not appetite; medicine, but not health; knowledge, but not wisdom; glitter, but not beauty; fun, but not joy; acquaintances, but not friends; servants, but not faithfulness; leisure, but not peace. You can have the husk of everything for money, but not the kernel.

The passage reminds me that the essence of virtually any enjoyable activity depends on non-monetary factors. On that note, here are a few more comparisons that came to my mind:

• You can buy a college degree, but not an education
• You can buy insurance, but not safety
• You can buy jokes, but not laughter
• You can buy a bed, but not sleep
• You can buy a house, but not a home

I suspect you’ve thought about this topic at some point too…any ideas you’d add to the list?