Оптимальная стратегия выбора подарка

[Red_Herring]

Следующая задача основана на американо-канадской традиции:

Дано $n$ игроков, с номерами $1,\ldots,n$ и имеется $n$ подарков, (предполагается, что все игроки проранжировали подарки одинаково: $1 < 2 < \ldots < n$ ). По очереди, по кругу, каждый игрок, не имеющий к данному моменту подарка, может либо выбрать бесхозный подарок, либо отобрать у кого-то подарок (тогда обездоленный может сделать то же самое в свой черед). Бесконечной петли не возникает в силу следующего правила: никто не может выбрать один и тот же подарок дважды.

Требуется определить оптимальную стратегию для каждого игрока, и если все играют оптимально, какой подарок кто получит. При $n=2$ все просто.

[ozheredov]

Red_Herring

Верно ли что пропустить ход и остаться при своём подарке не получится, и тогда число итераций до останова алгоритма — это количество перестановок без неподвижных точек?

[atlakatl]

Red_Herring в сообщении #1278695 писал(а):

каждый игрок, не имеющий к данному моменту подарка, может либо выбрать бесхозный подарок, либо отобрать у кого-то подарок

Т.е. игрок с подарком свою очередь пропускает.

[worm2]

Тут ведь какая ещё сложность?
Игра детерминирована, значит, какой-то игрок получит самый дешёвый подарок, как бы он ни играл.
Зная это, он может выбрать абсолютно любую стратегию. Но от этой стратегии может зависеть оптимальное распределение подарков у остальных игроков.
Так, для $n=3$ у меня, вроде бы, получается, что при оптимальной игре 2-го и 3-го игроков первый игрок проигрывает, как бы он ни ходил.
Но он может своими ходами повлиять на то, кому достанется самый дорогой подарок.

[Red_Herring]

worm2 в сообщении #1278848 писал(а):

Игра детерминирована, значит, какой-то игрок получит самый дешёвый подарок, как бы он ни играл.
Зная это, он может выбрать абсолютно любую стратегию. Но от этой стратегии может зависеть оптимальное распределение подарков у остальных игроков.

Поскольку задача родилась из разговора, то я не уверен, что она правильно поставлена. Поэтому ее можно модифицировать. И тогда первый вопрос: кто же неудачник (которому достанется самый дешевый подарок)? При любом ли $n$ это первый?

[worm2]

По-видимому, да.
Если второй игрок будет всегда отнимать подарок (кроме самого дешёвого) у первого, то он, по крайней мере, гарантирует себе подарок стоимостью не менее 2. Первый же вынужден будет либо перебрать все подарки дороже 1, пока ему не достанется единственный "счастливый билет", либо, чтобы не мучаться, возьмёт себе 1 ещё раньше.

[sup]

При кооперативной игре, команда может заставить первого игрока забрать любой наперед заданный подарок.
Но это только первого. Любого другого команда может заставить забрать лишь один из двух заданных. Ясно, что он заберет с большим номером. Так что любому игроку (кроме первого) гарантирован лишь подарок 2.
Как отсечь кооперативную игру я не знаю.

[atlakatl]

При следующей стратегии - вроде бы рациональной - 1-й и 2-й игроки оказываются без подарков:
Игрок 1 2 3
Ход1 3 3 3
Ход2 2 2 2
Ход3 1 1 1
Это лучше/хуже последнего подарка?

[worm2]

При втором ходе третий игрок (у которого к тому моменту 3) не имеет права ходить: подарок у него уже есть.

[Red_Herring]

Я поговорил с ... от которого узнал эту задачу. Первый игрок--гарантированный лузер. Любой, кроме первого, может гарантировать себе не самый худший подарок.

Эта игра (с несколько иными правилами) широко известна как "Yankee swap", "Dirty Santa", "White elephant".