You are currently browsing the tag archive for the ‘game theory’ tag.

Good grammar makes for bad passwords:

[…]there’s an Achilles’ heel in creating phrase-based passwords. It’s the fact that most English speakers will craft phrases that make sense.

Ashwini Rao and Gananand Kini at Carnegie Mellon and Birenda Jha at MIT have developed proof-of-concept password-cracking software that takes advantage of that weakness. It cracks long passwords, and beats existing cracking software, simply by following rules of English grammar.

“Using an analytical model based on parts-of-speech tagging, we show that the decrease in search space due to the presence of grammatical structures can be as high as 50 percent,” the researchers write in their paper.

Bad grammar makes for good passwords:

Instead, get creative. Try poor grammar and spelling, as in “de whippoorsnapper sashay sideway,” or get completely silly, as in “flipper flopper fliddle fladdle.”

It doesn’t matter how correct it is, as long as you can easily remember it.

The final seconds are ticking off the clock and the opposing team is lining up to kick a game winning field goal. There is no time for another play so the game is on the kicker’s foot. You have a timeout to use.

Calling the timeout causes the kicker to stand around for another minute pondering his fateful task. They call it “icing” the kicker because the common perception is that the extra time in the spotlight and the extra time to think about it will increase the chance that he chokes. On the other hand you might think that the extra time only works in the kickers favor. After all, up to this point he wasn’t sure if or when he was going to take the field and what distance he would be trying for. The timeout gives him a chance to line up the kick and mentally prepare.

What do the data say? According to this article in the Wall Street Journal, icing the kicker has almost no effect and if anything only backfires. Among all field goal attempts taken since the 2000 season when there were less than 2 minutes remaining, kickers made 77.3% of them when there was no timeout called and 79.7% when the kicker was “iced.”

So much for icing? No! Icing the kicker is a successful strategy because it keeps the kicker guessing as to when he will actually have to prepare himself to perform. The optimal use of the strategy is to randomize the decision whether to call a timeout in order to maximize uncertainty. We’ve all seen kickers, golfers, players of any type of finesse sport mentally and physically prepare themselves for a one-off performance. The mental focus required is a scarce resource. Randomizing the decision to ice the kicker forces the kicker to choose how to ration this resource between two potential moments when he will have to step up.

If you ice with probability zero he knows to focus all his attention when he first takes the field. If you ice with probability 1 he knows to save it all for the timeout. The optimal icing probability leaves him indifferent between allocating the marginal capacity of attention between the two moments and minimizes his overall probability of a successful field goal. (The overall probability is the probability of icing times the success probability conditional on icing plus the probability of not icing times the success probability conditional on icing.)

Indeed the simplest model would imply that the optimal icing strategy equalizes the kicker’s success probability conditional on icing and conditional on no icing. So the statistics quoted in the WSJ article are perfectly consistent with icing as part of an optimal strategy, properly understood.

But whatever you do, call the timeout before he gets a freebie practice kick.

From Bloomberg:

“JPMorgan Chase & Co. (JPM) asked more than 2,000 current and former employees to contribute to a settlement with the U.K.’s tax authority over their use of an offshore trust for bonus payments, according to a person briefed on the situation…..

People who used JPMorgan’s trust told the FT they were asked to participate in a so-called blind auction, in which they would volunteer to pay a tax rate of their choosing.

If the auction fails to generate enough money to fund the settlement, people who submitted less than the average bid would be excluded from the deal and face a 52 percent tax rate when the trust’s assets are liquidated, the newspaper said.

People who don’t wish to participate can try to fight the government’s demand, the person briefed on the situation said.”

The rules of the auction are not 100% clear from the article. Taken at face value, there is the possibility of multiple coordination equilibria. If I expect everyone else to contribute a lot but not enough to pay off the tax debt, then I will contribute a lot too to avoid the 52% tax. If I expect everyone to contribute a little, so will I hoping people who decided not to participate or contributed less than the average bid will bear the punishment. Finally, if I expect total contributions to exceed the tax debt, I will contribute zero. Uncertainty about everyone’s willingness to pay, deep pockets etc will generate randomness and perhaps refine equilibria but leave open the possibility of multiplicity. Also, there will be positive probability that the auction does not fully recompense the tax authorities. This is also true in mixed strategy equilibria of the complete information game.

To increase contributions and guarantee success, the auction should specify that everyone who contributes more than the average bid will escape the 52% tax if total contributions are lacking. Then, people will submit more than the average just to be safe. Then, the average expected bid will go up. Then, they’ll submit even more etc.

Because talking takes time.  And how much time it takes to talk depends in large part on how much time it takes to think of what you are going to say.  The time spent reveals how much thinking you did.  Here’s where truthtelling distinguishes itself.  The time it takes to tell the truth is just the time it takes to remember what actually happened.

The time it takes to lie is the time it takes to invent a lie, check that its consistent with the facts, and invent all of the subsequent lies you are going to have to tell in order for your whole story to hang together.

Watching the Olympic Games this Summer I noticed that the volleyball competition has changed the scoring system from the old “sideout” system to what used to be called “quick score.”  (This change may have happened a long time ago, I don’t watch much volleyball.)  The traditional sideout scoring method increments the score only when the serving team wins a point.  When the serving team loses the point the serve is awarded to the other team (a “sideout”) but the score is unchanged.  This can lead to long drawn out games with repeated sideouts and little scoring.  As a stopgap, in the old days, volleyball matches would switch to the quick score system after a certain amount of time has elapsed.  In quick scoring a sideout earns a point for the team that gains the serve.

I always liked the sideout system, thinking of it as a characteristic volleyball rule that is compromised for expediency by the switch to quick score.  Instinctively it seemed that the fact you could only score when you are serving played a big role in volleyball strategy.  But when I was watching this summer it occurred to me that the two scoring systems are less different than it appeared at first.

The basic observation is that at any stage of the game sideout scores are just quick scores minus the number of sideouts.  And sideouts necessarily alternate between teams so the number you are subtracting differs by at most one across the two teams.  So I started to think if there was a way to characterize the mapping between scoring systems that would clarify precisely the strategic impact of the switch.  And I think I figured it out.

Quick scoring is defined as follows.  The team who wins a point has its score incremented by one, regardless of who was serving that point. (The serve switches when the receiving team wins a point just as in the sideout system.)  The winner of the game is the first team to have a score of at least 15 (or 25 in other cases) and at least a 2 point lead. (I.e. the game continues past 15 if neither team has a two point lead.)

Quick scoring is equivalent to the following system: 28 points will be played. After 28 points (let’s call it regulation) if the score is tied (14-14) then they continue to play until some team has a 2 point advantage.

This is in turn equivalent to side-out scoring with the following amended rules. Lets refer to the team that receives serve in the first point of the game as the receiving team.

  1. A total of 28 ponts is played in regulation.
  2. At the end of play if either team is ahead by 2 points then that team wins except if
  3. the receiving team either scored the last point or earned a side-out in the last point and the receiving team is ahead by 1 point.  In this case the receiving team wins.

If none of these conditions are met then the game continues past regulation. We define the team that has the serve in the first point past regulation as team 1 and the other team as team 2. The score is reset to 0-0.  Play continues (with side-out scoring) until the first moment at which one of the following occurs.

  1. Team 1 has a 2 point lead, in which case team 1 is the winner.
  2. Team 2 has a 1 point lead, in which case team 2 is the winner.

The proof of this equivalence is below the jump. Here’s what it means. Quick scoring is not an innoccuous change in the rules to speed up play but its pretty close. Because a near identical outcome would obtain if instead of switching to quick score, we keep sideout scoring but cap the number of regulation points at 28. Its nearly, but not exactly identical because of the two scoring “epicycles” that have to be appended, namely #3 in regulation and #2 in overtime. Note that both of these wrinkles tend to benefit the receiving team. I don’t know the stats (anybody?) but it appears to me that the receiving team already has a large advantage in volleyball at the level of an individual point. You could say that an effect of sideout scoring is that it levels the playing field by giving a small overall advantage to the serving team. The switch to quick scoring eliminates that.

I wonder if there is a noticeable difference in the frequency with which the (initially) receiving team wins a volleyball game after the switch to quick scoring.

Read the rest of this entry »

David McAdams sends this along:

I’ve created a fun and simple game-theory problem that I thought you might enjoy …  This is the sort of problem you could give undergrads to find out who are the really bright ones.  It might also be fun to mention (or play) in class.
Problem: Find the (unique) symmetic equilibrium of “The World’s Simplest Poker Game”, played as follows:
**0** two players
**1** each player pays ante of $100
**2** each player receives ONE card, which we can think of as independent random numbers on [0,1]
**3** each player SIMULTANEOUSLY decides whether to “raise” $100 or “stay”
**4A** if one player raises and the other stays, the raiser wins the pot, for net gain +$100
**4B** if both raise, the players show their cards and whoever has the highest card wins for net gain +$200
**4C** if both stay, the players show their cards and whoever has the highest card wins for net gain +$100
If you decide to solve this problem, please let me know how long it takes you … I’m curious how immediately obvious the answer is to you 🙂  I have solved it myself and, I can tell you, the answer is simple and elegant.
Cheers,
David

N.B. My answer based on 5 minutes of thinking was wrong.  I will post David’s solution over the weekend.

 

Update:  As promised, here is David’s solution.  Looks like Keith was the first to post the correct answer in the comments and thanks to Nicolas for pointing out that this example appeared in von Neumann and Morgenstern.

Here’s the explainer.

As budget negotiations get underway with the threat of sequestration looming, it’s worth recalling a basic lesson from game theory.

Consider two parties in the same vehicle speeding towards a cliff. The one who concedes, i.e. chickens out and steers the car out of danger, is the loser. Winning is better than losing but either is better than driving off the cliff. Finally, time is valuable: if you are going to concede, you prefer to do it earlier rather than later. Still you are prepared to wait if you expect your rival will concede first.

In equilibrium of this game, unless someone concedes right away there is necessarily a positive probability that they will go over the cliff.  

The proof is simple.  Consider player 1 and suppose his strategy is not to concede immediately. Then we will show 1’s strategy is such that if 2 never concedes there is a positive probability that 1 will also never concede and they will drive off the cliff together. To prove it, suppose the contrary: that 1’s strategy will eventually concede with probability 1 (if 2 doesn’t concede first).  If that is 1’s strategy then 2’s best reply is to wait for 1 to concede. In equilibrium 2 will play such a strategy and the outcome will therefore be that 1 is the loser with probability 1. But if 1 is going to be the loser for sure anyway he should have conceded immediately. That’s a contradiction. We have shown that if 1 does not concede immediately then his strategy will allow the car to drive off the cliff with positive probability. The exact same argument applies to 2. Thus in equilibrium, if the game begins without an immediate concession there is a positive probability they will plunge from the cliff.

If you are a parent you probably know of a few kids who have life-threatening allergies. And if you are forty-something like me you probably didn’t know anybody with life-threatening food allergies when you were a kid.  It seems like the prevalence of food allergies have increased ten-fold in the last thirty years. Which seems impossible.

Here’s one potential explanation. Suppose that a small percentage of people have a life-threatening allergy to, say, peanuts. And suppose that doctors begin more carefully screening kids for potential food allergies. For example, a kid who gets a rash after eating something is given a skin test or blood test. A positive test correlates with food allergy but does not conclusively demonstrate it. In addition the test cannot distinguish a mild allergy from one that is life threatening.

But life-threatening food allergies are life threatening.  The risk is so great that any child with a non-negligible probability of having it should be restricted from eating peanuts.  Such a child will return to school with a note from the doctor that there should be no peanuts in class because of the risk of a life-threatening allergic reaction.  This is what’s knows as “being allergic to peanuts.”

This is all unassailable behavior on everybody’s part.  And note that what it means is that while there continues to be just a small percentage of people who are deathly allergic to peanuts, there is a much larger percentage of people who, perfectly rightly, avoid peanuts because of the significant chance it could give them a life-threatening allergic reaction.

From The Wages of Wins Journal:

I’ve decided to lump speed together with all of these other (hypothesized) factors under the general heading of “Floor Stretch”.  We’ll use it for an exercise in theoretical sports economics…Whatever it is that truly makes up “Floor Stretch”, it has to be sufficiently valuable that it offsets the lower raw productivity of the smaller players….

Floor Stretch, however, is really a relative function.  Having 5 point guards on the floor only stretches the other team if they don’t also have 5 point guards playing.  In this sense, what we really care about is the ratio of Floor Stretch between the two teams competing.  Theoretically, the Floor Stretch ratio is what the raw productivity must be balanced against in order to determine the best mix of players.  This, then, gets us into some classical Game Theory….

I’m too focussed on the election to digest fully. But I got this from Goolsbee’s Twitter feed today – he must be confident?

 

The average voter’s prior belief is that the incumbent is better than the challenger. Because without knowing anything more about either candidate, you know that the incumbent defeated a previous opponent. To the extent that the previous electoral outcome was based on the voters’ information about the candidates this is good news about the current incumbent. No such inference can be made about the challenger.

Headline events that occurred during the current incumbent’s term were likely to generate additional information about the incumbent’s fitness for office. The bigger the headline the more correlated that information is going to be among the voters. For example, a significant natural disaster such as Hurricane Katrina or Hurricane Sandy is likely to have a large common effect on how voters’ evaluate the incumbent’s ability to manage a crisis.

For exactly this reason, an event like that is bad for the incumbent on average. Because the incumbent begins with the advantage of the prior.  The upside benefit of a good signal is therefore much smaller than the downside risk of a bad signal.

As I understand it, this is the theory developed in a paper by Ethan Bueno de Mesquita and Scott Ashworth, who use it to explain how events outside of the control of political leaders (like natural disasters) seem, empirically, to be blamed on incumbents. This pattern emerges in their model not because voters are confused about political accountability, but instead through the informational channel outlined above.

It occurs to me that such a model also explains the benefit of saturation advertising. The incumbent unleashes a barrage of ads to drive voters away from their televisions thus cutting them off from information and blunting the associated risks. Note that after the first Obama-Romney debate, Obama’s national poll numbers went south but they held steady in most of the battleground states where voters had already been subjected to weeks of wall-to-wall advertising.

In 1797 Johann Wolfgang von Goethe had completed a new poem Hermann and Dorothea, and he was interested in knowing and publicizing its “true worth.”  So he concocted a scheme with his lawyer Mr. Bottiger and wrote this in a letter to his publisher:

I am inclined to offer Mr. Vieweg from Berlin an epic poem, Hermann and Dorothea, which will have approximately 2000 hexameters…. Concerning the royalty we will proceed as follows: I will hand over to Mr. Counsel B6ttiger a sealed note which contains my demand, and I wait for what Mr. Vieweg will suggest to offer for my work. If his offer is lower than my demand, then I take my note back, unopened, and the negotiation is broken. If, however, his offer is higher, then I will not ask for more than what is written in the note to be opened by Mr. Bottiger.

To understand this scheme first consider the alternative scenario where the publisher is told the amount demanded.  Then the publisher will say yes or no depending on whether his willingness to pay (the poem’s “true worth”) exceeds or falls short of the demand.  But then Goethe would never know exactly the poem’s true worth, just an upper or lower bound for it.

With the demand kept secret, the publisher’s incentives remain the same:  he wants to agree to a demand that is below his willingness to pay and refuse a demand that exceeds it.  Without knowing what that demand is, there is one and only one way to ensure this.  The publisher should offer exactly the poem’s true worth.

Goethe had devised what is apparently the first dominant-strategy incentive compatible truthful revelation mechanism.  The Vickrey auction is based on exactly this principle and so Goethe’s mechanism makes for a great starting point for teaching efficient auctions.

(quote is from “Goethe’s Second-Price Auction” by Moldovanu and Tietzel.  Mortarboard mosey:  Markus Mobius.)

The Romney campaign is expanding ad buys beyond the battleground states. Is there a huge swell of enthusiasm so Romney is trying for a blowout or is it a bluff?

The traditional model of political advertizing is the Blotto game.  Each candidate can divide up a budget across n states. Each candidate’s probability of winning at a location is increasing in his expenditure and decreasing in the other’s.  These models are hard to solve for explicitly. What makes this election unusual is that the usual binding constraint – money – is slack in the battleground states. Instead, full employment of TV ad time and voter exhaustion with ads makes further expenditure unnecessary.  But, you can still spend the money on improving your get-out-the-vote operation or to expand your ad buy to other states. Finally, you can send your candidate to a state.  Your strategy varies as function of how close the race is.

If the battleground states are increasingly unlikely to be in your column, then a get out the vote strategy will not be enough to tip them back in your favor.  Better to try to make some other state close by advertizing and mobilizing there.  You must maintain your ad buy though in the battleground states to keep your competitor engaged so that they cannot divert resources themselves.

If the battleground states are close, then a get out the vote operation is quite useful even if ad spending is at its maximum.  Better to do that than spend money in other locations where you are way behind.

If you are far ahead in the battleground states, you have to keep on spending there as your competitor is spending there either because he might win or to keep you spending there. But, cash you have sloshing around should be spent “expanding the map”.  This gives you more paths to victory and also exerts a negative externality on your opponent, forcing him to divert resources including perhaps the most valuable resource of all, the candidate’s time.

So, you might spend heavily in a state even when you have little chance there.  This always has the benefit of diverting your opponent’s attention.  This means there is an incentive for a player to invest even if he is far ahead in the battleground states.  But there is also an incentive to invest when you are behind as you need more paths to victory and expenditure on getting out the vote is less useful. So, we can’t infer Romentum from the fact that Romney is advertizing in MN and PA.

I think we can make stronger inferences by making a leap of faith and extrapolating this intuition to a state by state analysis.  By comparing strategies with public polls, we can try to classify them into the three categories.

NC seems to fall into the first category for President Obama. Romney is ahead according to the polls but it gives the Obama campaign more ways to win and keeps the Romney resources stretched.  Romney is roughly as far behind in MI, MN and PA as Obama is in NC. So, they play the same role for Romney as NC does for Obama.  Bill Clinton and Joe Biden are campaigning in PA and MN so the Romney strategy has succeeded in diverting resources.

The most scarce resource is candidate time so we can infer a lot from the candidate recent travel and their travel plans. If the race is close in any states it would be crazy to try a diversion strategy as a candidate visit acts like a get out the vote strategy and hence has great benefits when the race is close. The President is campaigning in WI, FL, NV, VA and CO. In fact, both candidates are frequently in FL and VA.  NC is a strong state for Romney because, as far as I can tell, he has no plans to visit there and nor does the President. Similarly, I don’t see any Romney pans to visit MI, MN or PA. Also, NV also seems to be out of Romney’s grasp as he has no plans to travel there.  It is hard to make inferences about NH as Romney lives there so it is easy to campaign.  OH has so many electoral votes that no candidate can afford not to campaign there – again no inferences can be made. Both candidates are in IA.

So, I think the state by state evidence is against Romentum. NC and NV do not seem to be in play. The rest of the battleground states are going to enjoy many candidate visits so they must be close. That’s about all I have!

  1. Its socially valuable for the University of Michigan measure consumer confidence and announce it even if that is an irrelevant statistic.  Because otherwise somebody with less neutral motives would invent it, manipulate it, and publicize it.
  2. Kids are not purely selfish.  They like it when they get better stuff than their siblings.  To such an extent that they often feel mistreated when they see a sibling get some goodies.
  3. Someone should develop a behavioral theory of how people play Rock, Scissors, Paper when its common knowledge that humans can’t generate random sequences.
  4. The shoulder is the kludgiest joint because there are infinitely many ways to do any one movement.  Almost surely you have settled into a sub-optimal way.
  5. I go to a million different places for lunch but at each one I always order one dish.

Ezra Klein has a great post about the “cheap talk” used by candidates to try to manipulate beliefs about their candidates chances of winning.  He concludes:

The bottom line is that Boston fears scared Republicans won’t vote and Chicago fears confident Democrats won’t vote. And so, in this final stretch, Boston wants Republicans confident and Chicago wants Democrats scared. Keep that in mind as you read the spin.

In an patent race, the firm that is just about to pass the point where it wins the race and gets a patent has an incentive to slack off  a bit and coast to victory.  The competitor who is almost toast has an incentive to slack off as he has little chance of winning.  But if the race is close, all firms work hard.

Elections are similar except the campaigns have the information about whether the campaign is close or not and the voters exert the costly effort of voting.  Campaigns have an incentive to lie to maximize turnout so the team that’s ahead pretends not to be far ahead and the team that’s behind pretends the race is very close.  As Klein says, no-one can believe their spin and no information can be credibly transmitted.

If they really want to influence the election, the campaigns have to take a costly action to attain credibility.  For example, they can release internal polling. This gives their statements credibility at the cost of giving their opponent their internal polling data.

I had just eaten a little plastic carton of yogurt and I tossed it into the recycling bin. She said “That yogurt carton needs to be rinsed before you can recycle it.” And I thought to myself “That can’t be true.  First of all, the recyclers are going to clean whatever they get before they start processing it so it would be a waste for me to do it here.  Plus, the minuscule welfare gains from recycling this small piece of plastic would be swamped by water, labor, and time costs of rinsing it.”  I concluded that, as a matter of policy, I will not rinse my recyclable yogurt containers.

So I replied “Oh yeah you’re right.”

You see, I didn’t want to dig through the recycling bin and rinse that yogurt cup. By telling her that I agree with her general policy, I stood a chance of escaping its mandate in this particular instance. Because knowing that I share her overall objective, she would infer that was that my high private costs of digging through the recycling that dictated against it under these special circumstances.  And she would agree with me that letting this exceptional case go was the right decision.

If instead I told her I disagreed with her policy, then she would know that my unwillingness was some mix of private costs and too little weight on the social costs. Even if she internalizes my private costs she would have reason to doubt they were large enough to justify a pass on the digging and rinsing and she might just insist on it.

A new joint paper with Alex Frankel and Emir Kamenica.  The talk begins with tennis, the discussion of American Idol begins at 12:14, how to write a mystery novel is at 15:51, the M. Night Shamyalan dilemma is at 17:32, the ESPN Classic dilemma is at 18:50, and the optimal sporting contest is at 28:37.

Lee Crawfurd emails me about events in Sudan.  North and South Sudan have agreed to a price at which the North will supply oil to the South.  On his blog, Roving Bandit, Lee writes:

So – whilst this seems like a good deal for North Sudan in the short run and a good deal for South Sudan in the long run, my main concern is the hold-up problem. What is stopping North Sudan ripping up the agreement in 3 years, demanding a higher cut, and just confiscating oil (again).

In his email he adds:

As it turns out, the South’s strategy is to resume piping oil through the North, but also to simultaneously build a pipeline through Kenya, giving them an extra option.

The fact that the North can hold up later makes it less likely that the North and South will invest and trade in their relationship now.  This makes both the North and South worse off.  For this difficulty to be resolved, the North has to be able to commit not to exploit the South in the future.  But the Kenyan pipeline gives them this commitment power to some extent: If the North threatens to raise prices, the South can go the Kenya route.  This means the North will not raise prices in the future and that is good for trade and the welfare of both parties.  Paraphrasing the wrods of the great philosopher Sting, “If Someone Does Not Trust You, Set Them Free“.

One issue is that the South may overinvest in the pipeline to get more bargaining power.  That could lead to inefficiency as the North then has bad incentives.

Another classic Williamsonian solution is to use hostages to support exchange.  I don’t know enough about North and South Sudan to know what they might transfer that is of little value to the recipient and high value to the donor. This sort of solution has been attempted recently in the US in the debt reduction negotiations. Automatic cuts in defense (bad for Republicans) and entitlement expenditures (bad for Democrats) go into force in January if Republicans and Democrats do not agree in debt negotiations. This has not worked so far. First, this is because there are crazy types who are willing to send the country over the “fiscal cliff”. Second, this is because there is no commitment and the automatic cuts can be delayed by Congress and so they are not real hostages.

My memory is terrible but I vaguely recall papers relating to investment in changing outside options in hold up models. These would be the most relevant to the Sudan scenario.

You are planning a nice dinner and are shopping for the necessary groceries. After having already passed the green onions you are reminded that you actually need green onions upon discovering exactly that vegetable, in a bunch, bagged, and apparently abandoned by another shopper.  Do you grab the bag before you or turn around and go out of your way to select your own bunch?

  1. This bag was selected already, and from a weakly larger supply.  It is therefore likely to be better than the best you will find there now.
  2. On the other hand, it was abandoned.  You have to ask yourself why.
  3. You would worry if the typical shopper’s strategy is to select a bag at random and then only carefully inspect it later.  Because then it was abandoned because of some defect.
  4. But this a red herring.  Whatever she could see wrong with the onions you can see too.  The only asymmetry of information between you and your pre-shopper is about the unchosen onions.  The selection effect works unambiguoulsy in favor of the scallions-in-hand.
  5. You can gain information based on where the onions were abandoned.
  6. First of all the fact that they were abandoned somewhere other than the main pile of onions reveals that she was not rejecting these in favor of other onions.  If so, since she was going back to the onion pile she would have brought these with her.  Instead she probably realized that she didn’t need the onions after all.  So again, no negative signal.
  7. If these bunched green onions were abandoned in front of the loose green onions or the leeks or ramps, then this is an even better signal.  She thought these were the best among the green onions but later discovered an even better ingredient.  A sign she has discerning tastes.
  8. It is true though that compared to a randomly selected new bunch, these have been touched by on average one additional pair of human hands.
  9. And also she might be trying to poison you.
  10. But if she was trying to poison someone, is it her optimal strategy to put the poisoned onions into a bag and abandon them in a neighboring aisle?
  11. In equilibrium all bunches are equally likely to be poisoned and the bagging and abandoning ploy amounts to nothing more than cheap talk.
  12. But, she might not be trying to poison just any old person.  She might really be targeting you, the guy who wants the best bunch of onions in the store.
  13. Therefore these onions are either logically the best onions in the store and therefore poisoned, or they are worse than some onions back in the big pile but then those are poisoned.
  14. Opt for take-out.

I wrote about it here.  I had a look at the video and it was the right call given the rule, but as I argued in the original post the rule is an unnecessary kludge.  At best, it does nothing (in equilibrium.)

  1. Is it that women like to socialize more than men do or is it that everyone, men and women alike, prefers to socialize with women?
  2. A great way to test for strategic effort in sports would be to measure the decibel level of Maria Sharapova’s grunts at various points in a match.
  3. If you are browsing the New York Times and you are over your article limit for the month, hit the stop button just after the page renders but before the browser has a chance to load the “Please subscribe” overlay.  This is easy on slow browsers like your phone.
  4. Given the Archimedes Principle why do we think that the sea level will rise when the Polar Caps melt?

David Axelrod, a senior campaign adviser for President Barack Obama’s reelection campaign, trash-talked Mitt Romney on Sunday, calling last week’s Republican National Convention “a terrible failure” and claiming Romney did not receive a polling bounce.

Presidential campaign staff are always saying stuff like that.  How badly the other side is doing.  Promoting polls that show their own candidate doing well and dissing polls that don’t.  While that seems like natural fighting spirit, from the strategic point of view this is sometimes questionable strategy.

If you had the power to implant arbitrary expectations into the minds of your supporters and those of your rival, what would they be?

  1. You wouldn’t want your supporters to think that your candidate was very likely to lose.
  2. But neither would you want your supporters to think that your candidate was very likely to win.
  3. Instead you want your supporters to believe that the race is very close.
  4. But you want to plant the opposite beliefs in the mind of the opposition.  You want them to think that the race is already decided.  It probably doesn’t matter which way.

All of this because you want to motivate your supporters and lure the opposition into complacency.  If you are David Axelrod and your candidate has a lead in the polls and you can’t just conjure up arbitrary expectations but you can nudge your supporter’s mood one way or the other you want to play up the opposition not denigrate them.

Unless its only the opposition that is paying attention.  Indeed suppose that campaign staffers know that the audience that is paying closest attention to their public statements is the opposition.  Then right now we would expect to be hearing Democrats saying they are winning and Republicans saying their own campaign is in disarray.

The two political parties hold conventions to nominate their Presidential candidate. These are huge affairs requiring large blocks of hotel space and a venue, usually something the size of a Basketball stadium. That all requires a lot of advance planning and therefore a commitment to a date.

Presumably there is an advantage to either going first or second. It may be that first impressions matter the most and so going first is desirable. Or it may be that people remember the most recent convention more vividly so that going second is better. Whichever it is, the incumbent party has an advantage in the convention timing game.

The incumbent party already has a nominee. The convention doesn’t accomplish anything formal and is really just an opportunity to advertise its candidate and platform. The challenger, by contrast, has to hold the convention in order to formally nominate its candidate. This is not just to make formal what has usually been decided much earlier in the primaries. Federal law releases the candidate from using some campaign money only after he is formally nominated.

So the incumbent has the freedom to wait as long as necessary for the challenger to commit to a date and then immediately respond by scheduling its own convention either directly before or directly after the challenger’s, depending on which is more desirable. The fact that this year the Democractic National Convention followed immediately on the heel’s of the Republican’s suggests that going last is better.

I haven’t seen the data but this theory makes the following prediction. In every election with an incumbent candidate the incumbent party’s convention is either always before or always after the challenger’s. And in elections with no incumbent, the sequencing is unpredictable just on the basis of party.

Eight female badminton players were disqualified from the Olympics on Wednesday for trying to lose matches the day before, the Badminton World Federation announced after a disciplinary hearing.

The players from China, South Korea and Indonesia were accused of playing to lose in order to face easier opponents in future matches, drawing boos from spectators and warnings from match officials Tuesday night.

All four pairs of players were charged with not doing their best to win a match and abusing or demeaning the sport.

Apparently the Badminton competition has the typical structure of a preliminary round followed by an elimination tournament.  Performance in the preliminary round determines seeding in the elimination tournament.  The Chinese and South Korean teams had already qualified for the elimination tournament but wanted to lose their final qualifying match in order to get a worse seeding in the elimination tournament.  They must have expected to face easier competition with the worse seeding.

This widely-used system is not incentive-compatible.  This is a problem with every sport that uses a seeded elimination tournament.  Economist/Market Designers have fixed Public School Matching and Kidney Exchange, let’s fix tournament seeding.  Here are two examples to illustrate the issue:

1. Suppose there are only three teams in the competition.  Then the elimination tournament will have two teams play in a first elimination round and the remaining team will have a “bye” and face the winner in the final.  This system is incentive compatible.  Having the bye is unambiguously desirable so all teams will play their best in the qualifying to try and win the bye.

2. Now suppose there are four teams.  The typical way to seed the elimination tournament is to put the top performing team against the worst-performing team in one match and the middle two teams in the other match.  But what if the best team in the tournament has bad luck in the qualifying and will be seeded fourth.  Then no team wants to win the top seed and there will be sandbagging.

As I see it the basic problem is that the seeding is too rigid.  One way to try and improve the system is to give the teams some control over their seeding after the qualifying round is over.  For example, we order the teams by their performance then we allow the top team to choose its seed, then the second team chooses, etc. The challenge in designing such a system is to make this seed-selection stage incentive-compatible.  The risk is that the top team chooses a seed and then after all others have chosen theirs the top team regrets its choice and wants to switch.  If the top team foresees this possibility it may not have a clear choice and this instability is not only problematic in itself but could ruin qualifying-round incentives again.

So that is the question.  As far as I know there is no literature on this.  Let’s us, the Cheap Talk community, solve this problem.  Give your analysis in the comments and if we come up with a good answer we will all be co-authors.

UPDATE:  It seems we have a mechanism which solves some problems but not all and a strong conjecture that no mechanism can do much better than ours.  GM was the first to suggest that teams select their opponents with higher qualifiers selecting earlier and Will proposed the recursive version.  (alex, AG, and Hanzhe Zhang had similar proposals) The mechanism, lets call it GMW, works like this:

The qualifiers are ranked in descending order of qualifying results.  (In case the qualifying stage produces only a partial ranking, as is the case with the group stages in the FIFA World Cup, we complete the ranking by randomly ordering within classes.)  In the first round of the elimination stage the top qualifier chooses his opponent.  The second qualifier (if we was not chosen!) then chooses his opponent from the teams that remain.  This continues until the teams are paired up.  In the second round of elimination we pair teams via the same procedure again ordering the surviving teams according to their performance in the qualifying stage.  This process repeats until the final.

It was pointed out by David Miller (also JWH with a concrete example, and afinetheorem) that GMW is not going to satisfy the strongest version of our incentive compatibility condition and indeed no mechanism can.

Let me try to formalize the positive and negative result.  Let’s consider two versions of No Envy.  They are strong and weak versions of a requirement that no team should want to have a lower ranking after qualifying.

Weak No Envy:  Let P_k(r,h) be the pairing that results in stage k of the elimination procedure when the ordering of teams after the qualifying stage was r and the history of eliminations prior to stage k is given by h.  Let r’ be the ordering obtained by altering r by moving team x to some lower position without altering the relative ordering of all other teams.  We insist that for every r, k, h, and x, the pairing P_k(r,h) is preferred by team x to the pairing P_k(r’,h).

Strong No Envy:  Let r’ be an ordering that obtains by moving team x to some lower position and possibly also altering the relative positions of other teams.  We insist that for every r,k,h, and x, the pairing P_k(r,h) is preferred by team x to P_k(r’,h).

GMW satisfies Weak No Envy but no mechanism satisfies Strong No Envy.  (The latter is not quite a formal statement because it could be that the teams pairing choices, which come from the exogenous relative strengths of teams, make Strong No Envy hold “by accident.”  We really want No Envy to hold for every possible pattern of relative strengths.)

One could also weaken Strong No Envy and still get impossibility.  The interesting impossibility result would find exactly the kind of reorderings r->r’ that cause problems.

Finally, we considered a second desideratum like strategy-proofness.  We want the mechanism that determines the seedings to be solvable in dominant strategies.  Note that this is not really an issue when the teams are strictly ordered in objective strength and this ordering is common knowledge.  It becomes an issue when there is some incomplete information (an issue raised by AG, and maybe also when there are heterogeneous strengths and weaknesses, also mentioned by AG.)

Formalizing this may bring up some new issues but it appears that GMW is strategyproof even with incomplete information about teams strengths and weaknesses.

Finally, there are some interesting miscellaneous ideas brought up by Scott (you can unambiguously improve any existing system by allowing a team who wins a qualifying match to choose to be recorded as the loser of the match) and DRDR (you minimize sandbagging, although you don’t eliminate it, by having a group format for qualifiers and randomly pairing groups ex post to determine the elimination matchups, this was also suggested by Erik, ASt and SX.)

Via my favorite source for toilet humor, Adriana Lleras-Muney, here is a paper describing how the urinal game and other bathroom customs can be used in introductory Sociology classes.

the use of “interactive exercises” can also be a valuable way by which to underscore the connection between individual actions and social structure. So stated, this paper identifies a number of “everyday” participatory exercises designed to spur classroom interaction and highlight core sociological concepts. Specifically, I use interactional scenarios within the typical American men’s public restroom to emphasize: 1) that individual actions, even those that exist in the mundane, are influenced by larger social-cultural forces; and 2) that a number of core sociological concepts can be found and explored in a place generally ignored or taken for granted.

I wrote about the urinal game here and the trough variant here.

From CNN:

Sprinters Allyson Felix and Jeneba Tarmoh threw their bodies across the finish line so evenly matched that cameras recording 3,000 frames a second couldn’t tell who beat whom.

Both runners recorded precisely the same finishing time, down to thousandths of a second: 11.068 seconds.

Two women beat Felix and Tarmoh: Carmelita Jeter and Tianna Madison. Their first and second place finishes on Saturday give them the chance to represent the United States at the Olympics in London this summer.

But the photo finish leaves USA Track & Field with a dilemma: Who gets the third slot?

There appears to be no precedent for a dead heat at U.S. Olympic Team track and field trials, prompting the U.S. Olympic Committee to announce new rules Sunday.

One of the runners can give up her claim to a spot on the Olympic team.

If neither one takes that unlikely option, they’ll be asked if they want to run a tie-breaking race or flip a coin.

If they choose the same option, the committee will respect their wishes.

If they disagree, they’ll have to race for it.

And if both athletes refuse to declare a preference, officials will flip a coin — a U.S. quarter to be exact.

They certainly have given it some thought but they may want to consult the previous literature as it seems they might be slightly off track:

Leaving nothing to chance, other than the flip itself, the rules also detail who gets to pick heads or tails and how the coin should be flipped.

“The USATF representative shall bend his or her index finger at a 90-degree angle to his or her thumb, allowing the coin to rest on his or her thumb,” the rules say.

A great story on The Morning News about a guy who is trying to preserve his spoiler-free existence in the face of meddling Internets, bus riders, and Amazon delivery guys:

Well, don’t you worry. This book will be on your doorstep tomorrow afternoon, ready to read.

I, of course, could read the book–YOUR book–right now.

And I gotta admit, it WOULD be fun to be one of the first people in the world to know how it all ends.

Hmm. So, maybe I’ll just read the last page…

OH MY GOD I CANNOT BELIEVE IT!! IT WAS ALL A DREAM???!

Hah hah. I’m just yanking your chain. That’s not how it ends. Or maybe it IS, and I’m just saying it’s not so you’ll be doubly surprised when you finish it. You never know.

I really did read the last page, though. The final word is “haberdashery.” You can verify that when you get the book. Tomorrow. A full day after I had it.

I gotta tell ya, though: Now that I know how it ends, I kind of want to read the whole thing. If I start right now, I could probably finish it and get this book in the mail to you by Wednesday. You wouldn’t mind waiting a few extra days, would you?

Also, I dog-ear pages to save my place. I hope that’s OK.

j/k. I wouldn’t really read this book. 1,000 words about fairies? Yeah, no. Besides, who has the time? Some of us have to work for a living. For instance, I bust my hump 60 hours a week schlepping your books around.

Besides, I’d rather see the movie anyway. That chick who plays Hermione is smoking hot. I’d quidditch, if you know what I’m sayin’.

 Including analysis of the ncessary and sufficient epistemic conditions for an arbitrary statement to qualify as a spoiler:

  • Did your comment spoil my reading experience? Yes.
  • Was my experience any less spoiled because you didn’t know your comment was true? No.
  • Was my experience any less spoiled because you really, truly, honestly, swear to God didn’t mean to spoil the experience for anyone? No.
  • Was my experience any less spoiled because I knew your comment was true only by accident? Nope again.

Read it.  (Spoiler alert.)

This guy wrote a column about The Hunger Games and gave away many details of the plot, some of them big-time spoilers.  Then he wrote a column about how he was actually doing his readers a favor because spoilers actually increase the enjoyment of the book.  For example

The suggestion is that there is a trade-off in the pleasures available to first-time readers or viewers on the one hand, and “repeaters” (as they are called in the scholarly literature) on the other. First-time readers or viewers, because they don’t know what’s going to happen, have access to the pleasures of suspense — going down the wrong path, guessing at the identity of the killer, wondering about the fate of the hero. Repeaters who do know what is going to happen cannot experience those pleasures, but they can recognize significances they missed the first time around, see ironies that emerge only in hindsight and savor the skill with which a plot is constructed. If suspense is taken away by certainty, certainty offers other compensations, and those compensations, rather than being undermined by a spoiler, require one.

and

The positive case for spoilers is even stronger if you are persuaded by those who argue, in the face of common sense, that suspense survives certainty. This is called “the paradox of suspense” and it is explained by A. R. Duckworth: “1. Suspense requires uncertainty. 2. Knowledge of the outcome of a narrative, scene or situation precludes any uncertainty. 3. [Yet] we feel suspense in response to fictions we know the outcomes of” (“The Paradox of Suspense II—The Problem,” The Journal of Film, Art and Aesthetics, Jan. 14, 2012).

and some other related arguments. Even if you accept these arguments, they amount to saying that there is a qualitative difference between the spoiled reading and the fresh reading and you want to have both. But this does not vindicate the spoilage. The problem with the spoiler is that it deprives you of the fresh reading. Spared the spoiler, or suitably alerted, you could have had both.

Now maybe you have time for only one reading. And so the counterargument could be that if the spoiled reading is in fact better than the fresh one then the spoiler saves you the effort of self-spoiling (settle down Beavis!) and gets you straight to the good, i.e. spoiled, stuff.

But notice what this says about the author of the novel. The author invented this whole story. She created the entire spoil-fodder. Indeed the spoiler only exists because the author chose not to “spoil” it himself by informing the reader right away what’s going to happen later. Either that is because this makes for a better story, or because the author is incompetent. In other words, putting a naked spoiler into your column and claiming that it makes the story better is tantamount to saying that the author is a hack. Not

If “The Hunger Games” is so shallow that it can be spoiled by a plot revelation, the alert doesn’t save much. If “The Hunger Games” is a serious accomplishment, no plot revelation can spoil it.

Deerstalker dash:  Alex Frankel.

This is a screenshot from an espn.com webstreaming replay of the French Open match between Maria Sharapova and Klara Zakapalova. As you can see Sharapova won the first set and now they are locked in a tight second set. But hmmm… something tells me that Zakapalova will be able to push it to three sets…

Courtesy of Emir Kamenica.

Ariel Rubinstein brings his game theory debunking manifesto to The Browser.

In general, I would say there were too many claims made by game theoreticians about its relevance. Every book of game theory starts with “Game theory is very relevant to everything that you can imagine, and probably many things that you can’t imagine.” In my opinion that’s just a marketing device.

Let’s show its usefulness by using game theory to analyze Ariel Rubinstein.  We model him with the following game.  Ariel is the first mover.  He privately observes whether game theory is useful.  Then he has the first decision to make.  He can either announce publicly that game theory is not useful or stay silent.  If he stays silent the game is over.  If he announces then everybody else moves next.  We can either try to prove him wrong by citing examples where game theory is useful or we can stay silent.  Then the game ends.

Let’s solve the game by backward induction.  If Ariel has announced that game theory is not useful, each of us has a strong incentive to find examples to prove him wrong so we do (assuming game theory is in fact useful which we will find out by looking for examples.)  Knowing this, and having privately observed that game theory is useful and being the humble yet social-welfare maximizing (not to mention supremely strategic) person Ariel is, Ariel announces that game theory is not useful so as to give the rest of us the incentive and the glory of proving him wrong.

And so it is done.

Jeff’s Twitter Feed

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 2,136 other followers