Student Probability Seminar

---

Optimal Strategy in "Guess Who?": Beyond Binary Search

Speaker: Mihai Nica

Location: Warren Weaver Hall 1314

Date: Thursday, October 8, 2015, 2 p.m.

Synopsis:

"Guess Who?" is a popular two player game where players ask "Yes" or "No" questions to search for their opponent's secret identity from a pool of possible candidates. We model this as a simple stochastic game under the assumption that the opponent's secret identity is uniformly distributed. Using this model, we explicitly find the optimal strategy and prove it is optimal for both players and for all possible candidate pool sizes. Contrary to popular belief, performing a binary search is not the optimal strategy for both players. Instead, the optimal strategy for the player who trails is to make certain bold plays in an attempt catch up. We also find an interesting log-periodic behavior that naturally arises in the landscape of this game.