Tuesday, February 15, 2011

How to win the final wager in Jeopardy

Here's a fun sideline to the human-vs-AI Jeopardy showdown: optimal wagering strategies for final Jeopardy. The challenge: given what you know about yourself, your opponents, their bankrolls, and the question, choose the betting strategy most likely to secure a win or at least a tie. What do you do?

As it happens, some smart game theorists have already worked on this problem. Work in the 1990's shows that against your average human, it's not too complicated.
  • If you're winning, assume your opponents will bet everything, and react accordingly by betting enough to double the number two player's score, plus one dollar.
  • If you're in the middle it can be tricky, but a good bet is to triple your score and subtract double the first player's score.
  • If you're losing by a lot, bet everything.
Following these rules should increase your chances of winning, regardless of your starting position. (See pg 271 in the paper.)

Against a human (or computer) who knows some game theory, the ideal strategy is complicated, because your strategizing will prompt strategizing by your opponents, and vice versa, ad infinitum. The Gilbert and Hatcher paper gives a solution for the two-player scenario. This situation happens when one contestant has no money to wager in the final round -- it's actually not all that unusual.

The three-player scenario is unsolved, but it's almost certainly a mixed strategy. Sounds like a good problem for a different kind of AI: computational game theory. Given that simple versions of poker have been completely solved, a mixed strategy over wagers should be child's play.

With all that as background, here's IBM's page on how Watson wagers. They cite the ridiculously detailed Jeopardy folklore of betting strategies --- the entries for "two-thirds" and "Shore's conjecture" are particularly on point --- but evidently, they haven't worked through the game theory. Knowing this, Ken and Brad should be able to outflank Watson in the final round, giving them slightly better odds at cinching a win.

Punchline: in the world of AI, Watson is a verbal genius in need of some remedial math.

No comments: