|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,frac
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|