2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5  След.
 
 Задачка по теории игр.
Сообщение12.11.2006, 14:18 
Аватара пользователя


24/10/05
400
Препод раздал сложную задач по т.играм.
У каждого из двух игроков имеется своя колода из n карт. Игроки независимо друг от друга метят любое количество карт в своей колоде.
После этого каждую колоду тасуют, и игроки наугад выбирают по одной карте из своей колоды. Если меченая карта достается только одному игроку, он выигрывает два рубля у противника. Если меченые карты достанутся обоим, то два рубля выигрывает тот, кто пометил меньшее число карт. В оставшихся случаях никто никому не платит.
Составьте матрицу игры для любого числа n. Найдите все оптимальные стратегии игроков и цену игры в случае n=5,6,7,8.


Помогите разобраться, с чего начать. :roll: Я начал исследовать ситуацию. У каждого игрока n карт, он может пометить в колоде от 0 до m карт (m<=n). Далее игрок тасует калоду , затем вытаскивает из колоды карту. С вероятнотью P - это меченая карта, с вероятностью Q- это немеченая карта... Q+P=1.

 Профиль  
                  
 
 Re: Задачка по теории игр.
Сообщение12.11.2006, 16:55 
Заслуженный участник


15/05/05
3445
USA
antoshka1303 писал(а):
Я начал исследовать ситуацию.

1. Сначала нужно определить чистые стратегии для каждого игрока.
(В чем состоит выбор стратегии? Сколько их у каждого?)
2. Затем нужно определить цену игры для пары чистых стратегий.
3. Дальше все делается автоматически.

 Профиль  
                  
 
 
Сообщение12.11.2006, 17:49 
Аватара пользователя


24/10/05
400
пробую выполнить пункт первый .
Рассмотрим игру
\[
\Gamma  = \left( {N,M,F} \right)
\]

\[
{N,M}
\] -множества чистых стратегий игрока 1 и игрока 2 соответственно

\[
\begin{array}{l}
 N = \{ \left( {mech,nemech} \right),\left( {mech,mech} \right),\left( {mech,nemech} \right),\left( {nemech,nemech} \right)\}  \\ 
 M = \{ S_1 ,S_2 \}  \\ 
 \end{array}
\]

mech-меченая карта
nemech-немеченая карта
\[
S_1 ,S_2 
\] количество меченных карт у игрока 1 и игрока 2 соотвественно
\[
F - 
\] количество денег, которые выиграл игрок 1
\[
F \in \{ 0,2, - 2\} 
\]
похоже на правду?

 Профиль  
                  
 
 
Сообщение12.11.2006, 18:53 
Заслуженный участник


15/05/05
3445
USA
antoshka1303 писал(а):
... похоже на правду?

"Она выглядела со спины так, как будто спереди очень красиво." :D

Сколько стратегий у 1-го игрока? В чем состоит применение каждой из этих стратегий? Тот же вопрос о 2-м игроке.

Наводящий провокационный вопрос: игра состоит в том, что игроки по одному разу бросают кубик. Выигрывает тот, у кого больше очков. Сколько стратегий у каждого игрока?

 Профиль  
                  
 
 
Сообщение12.11.2006, 19:27 
Аватара пользователя


24/10/05
400
Yuri Gendelman писал(а):
Наводящий провокационный вопрос: игра состоит в том, что игроки по одному разу бросают кубик. Выигрывает тот, у кого больше очков. Сколько стратегий у каждого игрока?

6 стратегий. А если выпали равные числа на кубиках?

 Профиль  
                  
 
 
Сообщение12.11.2006, 19:53 
Заслуженный участник


15/05/05
3445
USA
antoshka1303 писал(а):
6 стратегий.

И каким образом игрок применяет стратегию, скажем, номер 5?
Напомню, что вопрос провокационный.

Вам с преподавателем повезло - задача, которую Вам задали, не тривиальная. Ее сложно будет решить "из общих соображений", не познакомившись с теорией игр. Для начала Вам нужно понять, что такое стратегия.

 Профиль  
                  
 
 
Сообщение12.11.2006, 20:24 
Аватара пользователя


24/10/05
400
Yuri Gendelman писал(а):
antoshka1303 писал(а):
6 стратегий.

И каким образом игрок применяет стратегию, скажем, номер 5?
Напомню, что вопрос провокационный.


У игрока 1 и у игрока 2 по шесть стратегий.Поставим в соответствие стратегиям игрока 1
натуральные числа от 1 до 6.(аналогично для игрока 2) \[
\begin{array}{l}
 x = \{ x_1  = 1,x_2  = 2,x_3  = 3,x_4  = 4,x_5  = 5,x_6  = 6\}  \\ 
 y = \{ y_1  = 1,y_2  = 2,y_3  = 3,y_4  = 4,y_5  = 5,y_6  = 6\}  \\ 
 \end{array}
\]
Строим матрицу игры для игрока 1. (допустим, что если выпали на кубиках одинаковые числа, то никто никому не платит, если на кубике игрока 1 выпало число больше, чем у игрока 2, то игрок 2 платит игроку 1 единицу денег; если на кубике игрока 1 выпало число меньше чем у игрока 2, то игрок 1 платит игроку 2 единицу денег)
Элементы матрицы игры вычисляются по \[
a_{ij}  = F\left( {x_i ,y_j } \right)
\] мартица игры будет

\[
\left( {\begin{array}{*{20}c}
   0 & { - 1} & { - 1} & { - 1} & { - 1} & { - 1}  \\
   1 & 0 & { - 1} & { - 1} & { - 1} & { - 1}  \\
   1 & 1 & 0 & { - 1} & { - 1} & { - 1}  \\
   1 & 1 & 1 & 0 & { - 1} & { - 1}  \\
   1 & 1 & 1 & 1 & 0 & { - 1}  \\
   1 & 1 & 1 & 1 & 1 & 0  \\
\end{array}} \right)
\]
(матрица строится неоднозначно)
Если игрок 1 применил стратегию 5, то это знчит, что на кубике выпала цифра 5 и возможна ситуация с 6ю разрешениями(см 5 строчку).
Далее нужен поиск максиминных и минимаксных стратегий.
\[
\begin{array}{l}
 v = \mathop {\max }\limits_{x_i } \mathop {\min }\limits_{y_j } a_{ij}  \\ 
 \bar v = \mathop {\min }\limits_{y_j } \mathop {\max }\limits_{x_i } a_{ij}  \\ 
 \end{array}
\]

 Профиль  
                  
 
 
Сообщение12.11.2006, 20:45 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Позвольте повторить:
Yuri Gendelman писал(а):
И каким образом игрок применяет стратегию, скажем, номер 5?
Напомню, что вопрос провокационный.

 Профиль  
                  
 
 
Сообщение12.11.2006, 20:56 
Аватара пользователя


24/10/05
400
незваный гость писал(а):
:evil:
Позвольте повторить:
Yuri Gendelman писал(а):
И каким образом игрок применяет стратегию, скажем, номер 5?
Напомню, что вопрос провокационный.

стратегия заключается в том, что у игрока 1 выпала на кубику пятерка, и если при этом у игрока 2 выпала на кубике число меньше пяти, то игрок 1 получает от игрока 2 единицу денег, иначе - игрок 1 платит игроку 2 единицу денег.
так?!

 Профиль  
                  
 
 
Сообщение12.11.2006, 21:08 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
antoshka1303 писал(а):
стратегия заключается в том, что у игрока 1 выпала на кубику пятерка, и если при этом у игрока 2 выпала на кубике число меньше пяти, то игрок 1 получает от игрока 2 единицу денег, иначе - игрок 1 платит игроку 2 единицу денег.
так?!

Это не стратегия. Стратегия — это план действий игрока. А планировать выкинуть 5 может только мошенник. И Ясон дин Альт (в этом смысле, он тоже мошенник, впрочем).

 Профиль  
                  
 
 
Сообщение12.11.2006, 21:14 
Аватара пользователя


24/10/05
400
незваный гость писал(а):
:evil:
Это не стратегия. Стратегия — это план действий игрока.
Тогда в чем она заключается?

 Профиль  
                  
 
 
Сообщение12.11.2006, 21:47 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Еще раз — какой у Игрока может быть план? Колода, это конечно слишком много. Рассмотрите колоду из трех карт. Что могут игроки выбирать?

Еще один наводящий вопрос: Рассмотрите игру с посредниками (proxy). Игроки 1 и 2 (частично) метят свои колоды, и отдают их 1' и 2', соответственно. 1' и 2' их тасуют, выбирают по карте и определяют победителя. Как это изменяет стратегии 1 и 2? А у 1' и 2'?

 Профиль  
                  
 
 
Сообщение12.11.2006, 22:35 
Аватара пользователя


24/10/05
400
незваный гость писал(а):
Еще один наводящий вопрос: Рассмотрите игру с посредниками (proxy). Игроки 1 и 2 (частично) метят свои колоды, и отдают их 1' и 2', соответственно. 1' и 2' их тасуют, выбирают по карте и определяют победителя. Как это изменяет стратегии 1 и 2? А у 1' и 2'?

Ситуацая может зменится зменится, так как посредник может вытащить две подряд карты из колоды "одного" из игроков.

 Профиль  
                  
 
 
Сообщение12.11.2006, 22:53 
Заслуженный участник


15/05/05
3445
USA
antoshka1303 писал(а):
незваный гость писал(а):
:evil:
Это не стратегия. Стратегия — это план действий игрока.
Тогда в чем она заключается?

"-- Почему Вы отвечаете вопросом на вопрос?
-- А почему бы и нет!?"

Вам ведь задают наводящие вопросы, чтобы помочь Вам разобраться в предмете.
Все Ваши ответы пока что наводят на подозрение что Вы с теорией игр не знакомы. Похоже, что Вы пропустили в учебнике первые главы, а сразу перешли к минимаксу.
Еще раз, начните с понятия стратегии. Является ли бросание кубика стратегическим выбором?

2 незваный гость
Спасибо за помощь. :D

antoshka1303 писал(а):
Ситуацая может зменится зменится, так как посредник может вытащить две подряд карты из колоды "одного" из игроков.

:shock: Мда...

 Профиль  
                  
 
 
Сообщение12.11.2006, 23:47 
Аватара пользователя


24/10/05
400
Значит так.
У игрока 1 имеется три карты. Он может пометить либо ни одной карты, либо одну карту, либо
две карты, либо три карты.(ННН,либо ННМ,либо НММ,либо МММ),где Н-немеченая карта, М-меченая карта.
У игрока 2 имеется три карты. Он может пометить либо ни одной карты, либо одну карту, либо
две карты, либо три карты.(ННН,либо ННМ, либо НММ,либо МММ)

такий образом, получается 64 комбинации в тасованой колоде.

Добавлено спустя 49 минут 50 секунд:

Yuri Gendelman писал(а):
Вам ведь задают наводящие вопросы, чтобы помочь Вам разобраться в предмете.
я и пытаюсь разобраться...

Yuri Gendelman писал(а):
Все Ваши ответы пока что наводят на подозрение что Вы с теорией игр не знакомы. Похоже, что Вы пропустили в учебнике первые главы, а сразу перешли к минимаксу.

Да нет, внимательно читаю главы учебника. Многое,конечно, не ясно сразу.
Вы каким, кстати, учебником пользуетесь?У меня Петросян,Зенкевич,Семина Теория игр.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 71 ]  На страницу 1, 2, 3, 4, 5  След.

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



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

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


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

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