2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Оптимальная стратегия выбора подарка
Сообщение25.12.2017, 21:16 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Оптимальная стратегия выбора подарка
Сообщение25.12.2017, 23:00 


10/03/16
3871
Aeroport
Red_Herring

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

 Профиль  
                  
 
 Re: Оптимальная стратегия выбора подарка
Сообщение25.12.2017, 23:08 
Аватара пользователя


21/09/12

1871
Red_Herring в сообщении #1278695 писал(а):
каждый игрок, не имеющий к данному моменту подарка, может либо выбрать бесхозный подарок, либо отобрать у кого-то подарок
Т.е. игрок с подарком свою очередь пропускает.

 Профиль  
                  
 
 Re: Оптимальная стратегия выбора подарка
Сообщение26.12.2017, 13:06 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Оптимальная стратегия выбора подарка
Сообщение26.12.2017, 13:29 
Заслуженный участник
Аватара пользователя


31/01/14
11018
Hogtown
worm2 в сообщении #1278848 писал(а):
Игра детерминирована, значит, какой-то игрок получит самый дешёвый подарок, как бы он ни играл.
Зная это, он может выбрать абсолютно любую стратегию. Но от этой стратегии может зависеть оптимальное распределение подарков у остальных игроков.

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

 Профиль  
                  
 
 Re: Оптимальная стратегия выбора подарка
Сообщение26.12.2017, 13:57 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Оптимальная стратегия выбора подарка
Сообщение26.12.2017, 15:43 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Оптимальная стратегия выбора подарка
Сообщение26.12.2017, 16:07 
Аватара пользователя


21/09/12

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

 Профиль  
                  
 
 Re: Оптимальная стратегия выбора подарка
Сообщение26.12.2017, 16:12 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
При втором ходе третий игрок (у которого к тому моменту 3) не имеет права ходить: подарок у него уже есть.

 Профиль  
                  
 
 Re: Оптимальная стратегия выбора подарка
Сообщение26.12.2017, 16:16 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group