login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A286676 Numerators of the Nash equilibrium of guesses for the number guessing game for n numbers. 1
1, 3, 9, 2, 20, 12, 23, 27, 31, 35, 187, 1461, 485, 105, 64, 69, 67, 18, 11, 41, 87, 23, 97, 828, 251175, 497650, 1582733, 480083, 3070955, 139927, 1253, 1301, 160, 83, 172, 89, 184, 181, 187, 193, 199, 205, 211, 217, 223, 229, 235, 241, 247, 253, 259, 265 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
Consider two players: one player picks a number between 1-N, and another player guesses numbers, receiving feedback "too high" or "too low". The number picker is trying to maximize the expected number of guesses, whereas the number guesser is trying to minimize the expected number of guesses. While a binary search would in expectation be the optimal strategy if the number was chosen randomly, it is not the case if the number is chosen adversarially.
LINKS
R. Fokkink and M. Stassen, An Asymptotic Solution of Dresher's Guessing Game, Decision and Game Theory for Security, 2011, 104-116.
Michal Forisek, Candy for each guess, p. 15-19, IPSC 2011 booklet.
Michal Forisek, Candy for each guess
EXAMPLE
For n=3, the Nash equilibrium of guesses is 9/5. This is attained when the number picker chooses 1 with 2/5 probability, 2 with 1/5 probability, and 3 with 2/5 probability. The number guesser guesses the numbers 0,2,1 in order with 1/5 probability, 2,0,1 in order with 1/5 probability, and 1,0,2 (i.e. binary search) with 3/5 probability.
CROSSREFS
For denominators see A286677.
Sequence in context: A263559 A262343 A140985 * A246379 A303941 A176885
KEYWORD
nonn,frac
AUTHOR
Lewis Chen, May 12 2017
EXTENSIONS
More terms from Lewis Chen, Oct 29 2019
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)