Game Theory and Poe

Edgar Allen Poe

Julie Rehmeyer of Science News writes in, “The Tell-Tale Anecdote: An Edgar Allan Poe story reveals a flaw in game theory” about a paper Kfir Elias and Ariel Rubenstein called, “Edgar Allan Poe’s Riddle:
Do Guessers Outperform Misleaders in a Repeated Matching Pennies Game?

The paper discusses a game that Poe describes in The Purloined Letter. In it, the Misleader selects a number of marbles, coins, or whatever (grab them in your hand), and the Guesser guesses if the number is even or odd. Poe opines that it’s a game of skill rather than luck. (Read the article for more detail, or even better, the primary source.)

If you look at it from a simple game-theoretic viewpoint, the Guesser and the Misleader have equal odds. They might as well be flipping coins. However, there is a sense in which it’s a game of skill.

Our intrepid mathematicians showed that in their construction of the game, the guesser has a slight advantage — 3% — which is enough to get Las Vegas interested. They also examined modifications of the game and after several modifications brought it back in line with the predictions of game theory.

This brings up a number of interesting things to think about, including that Poe was on to something ahead of his time, as usual. Funny how that wisdom was hiding in plain sight. I wonder if he planned it.

A++++ Fast and Professional!! Would Read Again!

In “Crowd control at eBay,” Nick Carr writes:

EBay has been struggling for some time with growing discontent among its members, and it has rolled out a series of new controls and regulations to try to stem the erosion of trust in its market. At the end of last month, it announced sweeping changes to its feedback system, setting up more “non-public” communication channels and, most dramatically, curtailing the ability of sellers to leave negative feedback on buyers. It turns out that feedback ratings were being used as weapons to deter buyers from leaving negative feedback about sellers.

He goes on to rail against the usefulness of feedback loopss:

As these sites grow, keeping them in line requires more rules and regulations, greater exercise of central control. The digital world, it seems, is not so different from the real world.

However, he doesn’t question EBay’s central decision. If the goal is to control retaliatory feedback, then require all feedback be given within N days (N might vary for transaction types, international shipping, etc), and don’t reveal the feedback until both buyer and seller have finalized what they want to say.

(Personally, I think that some structure in the feedback–was the item as described? was it shipped quickly and as requested? was the interaction business-like, chatty, or rude? could enhance things a lot, as would displaying the value of the transactions. But that’s an aside.)

What’s important is that EBay is replacing a transparent and manipulated system with one that’s going to be worse for their customers, and more expensive to operate. It will be interesting to see what emerges from this. Will a worse feedback system be enough to overcome the network effects and allow a strong competitor to emerge?


Thanks to Nicko van Someren for the pointer.

How dumb do we think spammers are?

Why is it we easily admit that spammers are people smart enough to run massive bot nets, design custom malware, create rootkits, and adapt to changing protection technologies but we still think that they’re unable to write a pattern to match “user at domain dot com”?

Kudos to the first person who puts such a pattern in the comments below.

Measuring the Wrong Stuff

There’s a great deal of discussion out there about security metrics. There’s a belief that better measurement will improve things. And while I don’t disagree, there are substantial risks from measuring the wrong things:

Because the grades are based largely on improvement, not simply meeting state standards, some high-performing schools received low grades. The Clove Valley School in Staten Island, for instance, received an F, although 86.5 percent of the students at the school met state standards in reading on the 2007 tests.

On the opposite end of the spectrum, some schools that had a small number of students reaching state standards on tests received grades that any child would be thrilled to take home. At the East Village Community School, for example, 60 percent of the students met state standards in reading, but the school received an A, largely because of the improvement it showed over 2006, when 46.3 percent of its students met state standards. (The New York Times, “50 Public Schools Fail Under New Rating System

Get that? The school that flunked has more students meeting state standards than the school that got an A.

There’s two important takeaways. First, if you’re reading “scorecards” from somewhere, make sure you understand the nitty gritty details. Second, if you’re designing metrics, consider what perverse incentives and results you may be getting. For example, if I were a school principal today, every other year I’d forbid teachers from mentioning the test. That year’s students would do awfully, and then I’d have an easy time improving next year.

NYT Reporter Has Never Heard of Descartes

descartes.jpg

Or perhaps more correctly, did not internalize Descartes when he heard of him. In “Our Lives, Controlled From Some Guy’s Couch,” John Tierney writes:

Until I talked to Nick Bostrom, a philosopher at Oxford University, it never occurred to me that our universe might be somebody else’s hobby. I hadn’t imagined that the omniscient, omnipotent creator of the heavens and earth could be an advanced version of a guy who spends his weekends building model railroads or overseeing video-game worlds like the Sims.

It is for occasions such as these that the expressions “gobsmacked” and “WTF” were created. How could you survive to adulthood, let alone get a degree in what I presume was some sort of liberal arts, let alone get a job at The Paper of Record, and not once wonder about whether reality is real? This also suggests that the poor thing’s youth was insufficiently misspent.

Perhaps the real interesting work in this sort of liberal arts has moved to the likes of Edward Fredkin at MIT.

It’s a great article, and I’m happy that serious newspapers are talking about things like this. But in World of Warcraft, a simulation that he gives as a comparison, the characters there have a repertoire of jokes. One of the jokes that a woman might say is, “Do you feel that you aren’t in control of your own destiny — like — you’re being controlled by an invisible hand?”

I’m pleased that Oxford philosophers think about this, and I’m glad that professional journalists are paying attention to it rather than the usual fluff. For our children, however, this is just part of popular culture.

Photo courtesy of denzilm.

Emergent Chaos and Pirates

young-pirates.jpg

… pirate ships limited the power of captains and guaranteed crew members a say in the ship’s affairs. The surprising thing is that, even with this untraditional power structure, pirates were, in Leeson’s words, among “the most sophisticated and successful criminal organizations in history.”

Leeson is fascinated by pirates because they flourished outside the state—and, therefore, outside the law. They could not count on higher authorities to insure that people would live up to promises or obey rules. Unlike the Mafia, pirates were not bound by ethnic or family ties; crews were as remarkably diverse as in the “Pirates of the Caribbean” films. Nor were they held together primarily by violence; while pirates did conscript some crew members, many volunteered.

Mmmmm, chaos and emergent rules that work. Who’da thunk?

Read about pirates in the New Yorker.

Photo: “Tom Ironlocks, Sam Hawkeye and Wilde Oskar posing,” by larsst.

Astronauts and Terrorists: Limits of Screening

astronaut-in-diapers.jpgSo we here at Emergent Chaos have carefully refrained from using the phrase “astronaut in diapers” not because we think that it is now incumbent apon the blogosphere to maintain what little dignity remains in American journalism, but because, within about nine minutes of the arrest of Lisa Nowak, the blogosphere had thoroughly digested the story, and there was apparently nothing left to say.

However, when the New York Times published “Astronaut’s Arrest Spurs Review of NASA Testing” with the lead words “NASA is reviewing its psychological screening and checkup process in the wake of the arrest of Capt. Lisa M. Nowak, the astronaut accused of attempted murder, space agency officials said yesterday,” it occurred to me that we could, after all, jump on the `astronaut in diapers’ bandwagon.

You see, we’re concerned with the idea of screening. We think it’s way over-applied, and reduces the emergence of chaos with which we are enamoured. And we’re forced to ask, if NASA, who, after all, can put a man on the moon, can’t screen its 100-odd astronauts successfully, what odds does the TSA have of screening for terrorists?

The TSA, you’ll recall, is an agency that has never put anything but a gloved hand where it doesn’t belong. And TSA wants to screen millions of Americans every day. They want to screen us for a set of criteria that remain extremely fuzzy. (As we covered in a review of the book, “Who Becomes a Terrorist and Why?“)

Setting (our) silliness aside for a moment, screening for rare conditions, like being a terrorist, or a willingness to don diapers and drive 15 hours to wave a BB gun in someone’s face, is hard. It’s hard because you don’t have good indicia of what to look for. It’s hard because every small over-reach will result in thousands of false positives, because, after all, most Americans aren’t terrorists, any more than most astronauts are murders.


Trying to screen for either is a waste.

When a 0% Success Rate is Worthwhile

There’s an article in Zaman.com, about “Turkish Hacker Depletes 10,000 Bank Accounts

A criminal enterprise comprised of 10 individuals who drained the accounts of 10,580 customers by sending virus-infected e-mails was busted in Istanbul.


The suspects reportedly sent virus-infected emails to 3,450,000 addresses, and subsequently drained 10,850 bank accounts.

That’s a hit rate of 0.314%. Which I’m not going to analyze today.

Additional resources, all in Turkish: “İnternet dolandırıcıları yakalandı,” “İnteraktif banka dolandırıcılığı” both seem to be “TSI” agency stories, and “10 bin müşteri hesabını boşalttılar” seems to be a gov.tr site with additional details. Do any readers speak Turkish?

Halvar on Vulnerability Economics

Back in July, I wrote:

If fewer outbreaks are evidence that things are getting worse, are more outbreaks evidence things are getting better?

Now, I was actually tweaking F-Secure a little, in a post titled “It’s Getting Worse All The Time?” I didn’t expect Halvar Flake would demonstrate that the answer is yes. Attacks getting worse may well mean that things are getting better. Which is kind of counter-intuitive.

In Client Side Exploits, a lot of Office bugs and Vista, he writes about the other side of the Vista exploit coin, and how good security can drive bugs into widespread use:

ASLR is entering the mainstream with Vista, and while it won’t stop any moderately-skilled-but-determined attacker from compromising a server, it will make client side exploits of MSOffice file format parsing bugs a lot harder…As a result of this, client-side bugs in MSOffice are approaching their expiration date. Not quickly, as most customers will not switch to Vista immediately, but they are showing the first brown spots, and will at some point start to smell.

See also “Economics of vulnerabilities,” and “Vulnerability Game Theory.”