Здравствуй, Хабрахабр!
Не так давно где-то на просторах одной социальной сети увидел следующую игру: игроки присылают ведущему (назовем его так) по целому положительному числу (игроки не знают чисел друг друга), побеждает тот, кто прислал наименьшее уникальное число. Например, если играют 7 игроков и они прислали числа 5, 4, 2, 1, 1, 2, 6, побеждает игрок приславший число 4. Стало мне жутко интересно, как же надо «правильно» играть в эту игру, но оказалось, что однозначное решения для n игроков здесь если и есть, то оно достаточно сложное и запутанное, поэтому рассмотрим конкретные случаи для 3-х и 4-х игроков.

Случай трёх игроков

Выбор из {1, 2, 3}

Итак, поехали. Для начала, введем ограничение: пусть игроки могут выбирать числа только из {1, 2, 3} (потом будет проще и очевиднее переход к выбору любого натурального числа). Что мы попытаемся сейчас сделать: найти такую смешанную стратегию , что когда бы все игроки придерживались данной стратегии, никто бы не мог увеличить шансы на победу, изменив свою стратегию (такая штука, кстати, называется, равновесием Нэша). То есть, чтобы каждый игрок с вероятностью выбирал число 1, с вероятностью – число 2 и с вероятностью – 3, и каждому из игроков было бы невыгодно отклоняться от этих вероятностей.

Допустим, что игроки 2 и 3 используют эти вероятности, а игрок 1 решил увеличить свои шансы на победу и теперь использует стратегию . Чтобы победить, он должен выбрать число 1 (а остальные игроки должны выбрать или оба 2, или оба 3, или один 2, а второй – 3), число 2 (остальные же должны выбрать или оба 1, или оба 3), или же 3 (в таком случае остальные должны или оба выбирать 1, или оба выбирать 2). Таким образом, итоговая вероятность победы может быть выражена как сумма этих трёх вероятностей: (1). Не забываем также и о том, что сумма всех вероятностей в конечном итоге равна единице, т. е. (*).

Итак, игроку 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, и с числами больше четырёх дело иметь почти не приходится.

Спасибо за внимание. Играйте в игры.