You are here

Games People Don't Play

Peter Winkler at the Carriage HouseThe games Peter Winkler presented in the MAA Carriage House on April 23 were not familiar from physical education class or slumber parties or long bus trips, but his audience happily played along anyway.

In a lecture called “Games People Don’t Play,” the Dartmouth College mathematics and computer science professor characterized games as a gateway to mathematical understanding. He introduced a few games specifically calculated to prompt mathematical musings.

In one, Winkler had two integers written on pieces of paper, one in each fist. A volunteer randomly chose a hand, looked at the number therein, and then had to guess whether it was the larger or the smaller of the two.

“Is there a strategy you can have for this game that beats random guessing?” Winkler asked.

Yes, it turns out, though just barely. Choose a number at random and add one half to it. This is your threshold. If the number revealed is larger than your threshold, guess that it’s the larger number; if it’s smaller than your threshold, guess that it’s the smaller number.

If your threshold is greater than both of your companion’s numbers, you will be correct 50 percent of the time; likewise if your threshold is smaller than both. The (usually slight) advantage you get by adhering to this rule, then, comes from the slim chance that your threshold lies between the two numbers in your companion’s fists.

Winkler likes this example because it illustrates the potential power of an algorithm that makes use of a random variable.

Winkler explained another of his games—which he learned from Paul Halmos himself—in terms of Alice and Bob.

“You guys know Alice and Bob?” Winkler asked. “Alice goes first; Bob goes second. They’re familiar characters in computer science, game theory, and increasingly I think in a lot of mathematics.”

In the game of Chomp, Alice and Bob are sharing a rectangular chocolate bar that is made up of squares. They take turns—Alice going first, of course—picking a square and eating it and all squares above and to the right of it. The catch is that the bottom left square is poison. Whichever player is forced to eat that square loses.

Winkler mentioned Chomp to disillusion anyone still under the impression that mathematicians are omnipotent. Mathematicians know that the first player can always win Chomp, Winkler explained, but they don’t know how. Winkler even outlined the argument from which this embarrassing state arises.

“It’s impossible that Bob has a winning strategy,” he summarized. “If he did, Alice could steal it and beat him with it. It’s a great argument. It just doesn’t tell you how Alice actually wins the game.”

The mathematics at play in Winkler’s games got more sophisticated as the evening progressed, but his audience—“quick studies,” Winkler deemed them—stuck with him.

He touched on a problem that originally appeared on a Mathematical Olympiad qualifying test in Leningrad. You’re in a large rectangular room mirrored floor to ceiling, Winkler told listeners, and you’re not alone. Elsewhere in the room lurks your enemy—with a laser gun.

But there is good news: “You have bodyguards that you can summon to try to protect you,” Winkler said. “Graduate students are good for this.”

The question is, how many bodyguards do you need to ensure your safety?

“I want you to notice that if we have continuum many bodyguards, then we’re going to be OK,” Winkler quipped. Then he made the astounding claim that a mere 16 bodyguards will suffice.

Winkler ended his talk, however, with a claim more astounding yet, one related to the axiom of choice fundamental to Zermelo-Fraenkel set theory. He described a two-player game in which Alice seems to have the clear advantage and then argued that in fact Bob can win with 99 percent probability.

“That’s clearly ridiculous,” Winkler admitted. “But this is not a trick. This is a consequence of the ridiculous axiom that we use to do almost all of mathematics.” —Katharine Merow


Watch a short version of the lecture on YouTube.

 Listen to an interview with Peter Winkler and MAA Director of Publications Ivars Peterson (mp3)

 Listen to audio of Peter Winkler's lecture (mp3)

 

This MAA Distinguished Lecture was funded by the National Security Agency.

 

Dummy View - NOT TO BE DELETED