Угадывание наименьшего уникального натурального числа (случаи трёх и четырёх игроков)
Здравствуй, Хабрахабр!
Не так давно где-то на просторах одной социальной сети увидел следующую игру: игроки присылают ведущему (назовем его так) по целому положительному числу (игроки не знают чисел друг друга), побеждает тот, кто прислал наименьшее уникальное число. Например, если играют 7 игроков и они прислали числа 5, 4, 2, 1, 1, 2, 6, побеждает игрок приславший число 4. Стало мне жутко интересно, как же надо «правильно» играть в эту игру, но оказалось, что однозначное решения для n игроков здесь если и есть, то оно достаточно сложное и запутанное, поэтому рассмотрим конкретные случаи для 3-х и 4-х игроков.
Случай трёх игроков
Выбор из {1, 2, 3}
Итак, поехали. Для начала, введем ограничение: пусть игроки могут выбирать числа только из {1, 2, 3} (потом будет проще и очевиднее переход к выбору любого натурального числа). Что мы попытаемся сейчас сделать: найти такую смешанную стратегию
Допустим, что игроки 2 и 3 используют эти вероятности, а игрок 1 решил увеличить свои шансы на победу и теперь использует стратегию
Итак, игроку 1 нужно попытаться увеличить свою вероятность на победу
которые мы и решаем, принимая во внимание, конечно же, равенство (*). Получаем следующие вероятности:
Готово! Какой из этого вывод? Когда 3 игрока могут выбирать только из {1, 2, 3}, для каждого из них оптимальной стратегией будет следующая: приблизительно в половине случаев выбирать 1, приблизительно в четверти – выбирать 2, и приблизительно в четверти – 3. Это и будет равновесием Нэша.
Выбор любого натурального числа
Итак, что же произойдет, если мы снимем ограничения на множество, из которого игроки могут выбирать числа и как нам найти равновесие Нэша для такой игры? Теперь, если игрок выбирает некоторое число i, победит он только в том случае, если все игроки выберут одно и то же число строго меньше i, или же оба выберут по числу, каждое из которых строго больше i. Таким образом, для каждого игрока вероятность победы
Что всё это значит? Если подставить в полученное уравнение конкретные числа, то для первой семерки получаем приблизительно следующие вероятности:
То есть, равновесием Нэша будет такой набор стратегий, где каждый игрок с вероятностью приблизительно 0.46 выбирает 1, с вероятностью 0.25 – 2, с вероятностью 0.13 – 3, и так далее.
Случай четырёх игроков
Та же игра, с четырьмя игроками не сильно отличается от игры с тремя. В этом случае функция, которую нужно максимизировать, имеет следующий вид:
Что здесь к чему:
Решение имеет следующий вид:
Отсюда следует, что чаще всего придется выбирать числа 1 и 2, изредка — 3, очень изредка – 4, и с числами больше четырёх дело иметь почти не приходится.
Спасибо за внимание. Играйте в игры.