Элементарная задачка по теории игр - Public forum of MSU united student networks

Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.snto-msu.net/showflat.php?Number=7365814&src=arc&showlite=
Дата изменения: Unknown
Дата индексирования: Wed Apr 13 04:14:11 2016
Кодировка: Windows-1251
Поисковые слова: m 11

Элементарная задачка по теории игр - Public forum of MSU united student networks

Root \| Google \| Yandex \| Mail.ru \| Kommersant \| Afisha \| LAN Support

Список форумов | Поиск | Новый пользователь | Вход | Кто в онлайне | FAQ | Пользователи

General Discussion >> Study (Archive)

Страницы: 0 | 20 | показать все | след. страница

Carpal Tunnel

Рег.: 09.03.2006

Сообщений: 2900

Рейтинг: 5047

Элементарная задачка по теории игр
28.03.2008 00:54

Рассмотрим 2х игроков (A, B) и игру G с матрицей выигрышей
$[math][res=130]{ $$ \left( \begin{array}{lcl} 1 -1 \\ 2 \quad 3\\ \end{array} \right) $$ } [/math]$
Найти значине минимакса игры G.

PS сам теорию игр в глаза не видел. Буду признателен за ликбез (или где можно азы теории почитать)

Don't try to live so wise 'cos you will hate yourself in the end

Don't Quixote

Рег.: 20.11.2004

Сообщений: 28501

Рейтинг: 9797

Re: Элементарная задачка по теории игр [re: volant]
28.03.2008 08:04

2

Честно говоря, теория игр меня как-то миновала, а постигнуть ее хотя бы на уровне азов у меня руки не доходят, но, я так понимаю, картина следующая.
В твоей игре есть две стратегии у каждого из игроков.
Если первый выбирает i-ую, второй j-ую стратегии, то выигрыш первого игрока (=проигрыш второго) равен a_i,j
Заметим, что тут у нас max_i min_j a_i,j=min_j max_i a_i,j = 2, (2,1) - это так называемая седловая точка. (т.е. точка, минимальная в строке и максимальная в столбце).
Таким образом 2 - выигрыш, которого может гарантированно добиться первый игрок, выбрав вторую стратегию и проигрыш, которого гарантированно может добиться второй игрок, выбрав первую. Это и есть минимакс

How much wood would woodchuck chuck, if a woodchuck could chuck wood

Carpal Tunnel

Рег.: 09.03.2006

Сообщений: 2900

Рейтинг: 5047

Re: Элементарная задачка по теории игр [re: FrauSoboleva]
28.03.2008 10:05

я после прочтения википедии стал рассуждать также. Соответственно, был уверен что это правильный ответ. Но должно получиться 5/3

Don't try to live so wise 'cos you will hate yourself in the end

Don't Quixote

Рег.: 20.11.2004

Сообщений: 28501

Рейтинг: 9797

Re: Элементарная задачка по теории игр [re: volant]
28.03.2008 10:31

Значит мои посредственные знания недостаточны

Видимо, минимакс - это нечто отличное от выигрыша первого игрока, ибо 2 то он себе точно может гарантировать.
Хотя я видел в книге слово минимакс именно в этом смысле

How much wood would woodchuck chuck, if a woodchuck could chuck wood

enthusiast

Рег.: 12.03.2007

Сообщений: 364

Рейтинг: 316

Re: Элементарная задачка по теории игр [re: volant]
28.03.2008 17:21

1

LOL, пытаешься заботать задачку из REA GRE Math. Я тоже на ней завис, хотя формула для решения есть.

Формула кстати такая: det(M)/(a_11+a_22-a_21-a12)

Carpal Tunnel

Рег.: 29.08.2002

Сообщений: 6503

Рейтинг: 222

Re: Элементарная задачка по теории игр [re: volant]
28.03.2008 18:44

2

а в смешанных стратегиях хоть ?

Carpal Tunnel

Рег.: 09.03.2006

Сообщений: 2900

Рейтинг: 5047

Re: Элементарная задачка по теории игр [re: ykpon]
28.03.2008 19:19

-1

да, наверняка в смешанных. Иначе ответ 2

Don't try to live so wise 'cos you will hate yourself in the end

Don't Quixote

Рег.: 20.11.2004

Сообщений: 28501

Рейтинг: 9797

Re: Элементарная задачка по теории игр [re: ykpon]
28.03.2008 21:18

1

А какой резон первому смешивать, если он получает выигрыш меньше 2? :confused:

:confused:

Если так он гарантирует 2 запросто. Я думал, что смешанные стратегии появляются тогда, когда нет седловых точек

How much wood would woodchuck chuck, if a woodchuck could chuck wood

gegen bolschewismus

Рег.: 24.01.2005

Сообщений: 35861

Рейтинг: 7474

Re: Элементарная задачка по теории игр [re: FrauSoboleva]
28.03.2008 21:20

1

согласен. 2-я стратегия доминирует 1-ю. странная задача :confused:

:confused:

Carpal Tunnel

Рег.: 09.03.2006

Сообщений: 2900

Рейтинг: 5047

Re: Элементарная задачка по теории игр [re: wildschwein]
28.03.2008 22:35

1

Задача, конечно, странная. Но хотелось бы услышать мнение человека, разбирающегося в теории игр. Прояснить ситуацию и прокомментировать формулу det(M)/(a_11+a_22-a_21-a12)

Don't try to live so wise 'cos you will hate yourself in the end

infante terrible

Рег.: 25.01.2005

Сообщений: 282

Рейтинг: 1

Re: Элементарная задачка по теории игр [re: volant]
28.03.2008 23:15

3

ищется решение игры в смешанных стратегиях с помощью решения системы уравнений
p1*a_11+p2*a_21=v
p1*a_12+p2*a_22=v
p1+p2=1

q1*a_11+q2*a_12=v
q1*a_21+q2*a_22=v
q1+q2=1
где (p1,p2) и (q1,q2) - смешанные стратегии 1 и 2 игрока, v - цена игры (собственно решение).

из решения этой системы получается, что v=(a_11*a_22-a_21*a_12)/(a_11+a_22-a_21-a12)

Don't Quixote

Рег.: 20.11.2004

Сообщений: 28501

Рейтинг: 9797

Re: Элементарная задачка по теории игр [re: panter]
28.03.2008 23:34

1

Объясните мне идею применения здесь метода смешанных стратегий? По идее, она должна обеспечивать оптимум, тут же оптимум для первого будет, если первый выберет 2 стратегию с вероятностью 1.
Т.е. первый и второй сговорились и играют так, чтобы средний выигрыш при условии фиксированного выбора второго был постоянен и равен среднему выигрышу при условии фиксированного выбора первого?

How much wood would woodchuck chuck, if a woodchuck could chuck wood

Carpal Tunnel

Рег.: 09.03.2006

Сообщений: 2900

Рейтинг: 5047

Re: Элементарная задачка по теории игр [re: FrauSoboleva]
29.03.2008 00:11

Вот что я понял из того, что написала panter (за что ей огромное спасибо!):

Решение задачи находится из первой системы 3-х линейных уравнений (для первого игрока). При этом он выбирает стратегию так, чтобы в среднем получать одно и тоже при любой фиксированной стратегии второго игрока (как следствие, при любой смешанной). Стратегия странна, но ответ сходится. Это и есть минимакс?

Don't try to live so wise 'cos you will hate yourself in the end

infante terrible

Рег.: 25.01.2005

Сообщений: 282

Рейтинг: 1

Re: Элементарная задачка по теории игр [re: volant]
29.03.2008 10:18

1

прошу прощения, то решение, которое я написала здесь применять нельзя, поскольку, как уже было замечено выше, 2-я строка строго доминирует первую, а значит 1-я строка входит с нулевой вероятностью во все смешанные стратегии 1 игрока (есть такая теорема), т.е. решение этой игры находится только в чистых стратегиях и минимакс (как и максимин) равен 2.
Непонятно тогда - откуда у вас такой ответ :confused:

:confused:

. В данном случае он неверный.

кфмн

Рег.: 14.12.2005

Сообщений: 916

Из: Moscow

Рейтинг: 622

Re: Элементарная задачка по теории игр [re: panter]
29.03.2008 11:48

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

infante terrible

Рег.: 25.01.2005

Сообщений: 282

Рейтинг: 1

Re: Элементарная задачка по теории игр [re: halyavin]
29.03.2008 12:46

да кстати - я систему-то не решала, вероятности q и правда отрицательные. Вообщем, этот ответ к данной задаче однозначно не подходит.

enthusiast

Рег.: 06.12.2006

Сообщений: 335

Из: ГЗ

Рейтинг: 101

Re: Элементарная задачка по теории игр [re: panter]
29.03.2008 16:18

1

вообще-то тут должны быть не ур-ния а неравенства:

p1*a_11+p2*a_21 >= v
p1*a_12+p2*a_22 >= v
p1+p2=1
pi>=0

q1*a_11+q2*a_12 <= v
q1*a_21+q2*a_22 <= v
q1+q2=1
qi>=0

для 1го игрока это означает, что при его смешанной стратегии и любой стратеги 2го он получит не меньше, чем v

дальше, насколько я помню, все это на v делится (считая, что v>0) и решается задача линейного программирования относительно pi/v

infante terrible

Рег.: 25.01.2005

Сообщений: 282

Рейтинг: 1

Re: Элементарная задачка по теории игр [re: Non_trivial]
29.03.2008 16:37

1

а можно упростить задачу, воспользовшись свойством дополняющей нежесткости, по которому если pi>0, то a_i1*q1+a_i2*q2=v и если qj>0, то a_1j*p1+a_2j*p2=v и решать систему. Но это, конечно, не всегда прокатывает.

Carpal Tunnel

Рег.: 30.06.2004

Сообщений: 2884

Рейтинг: 5544

Re: Элементарная задачка по теории игр [re: volant]
29.03.2008 16:50

1

Да, в этой матричной игре минимакс равен двум. В случае, если у матрицы есть седловая точка (как у нас), равновесие в смешанных стратегиях обязано совпадать с равновесием в чистых стратегиях.

Откуда же возникло 5/2? Может, здесь, к примеру не антагонистическая игра? Тогда должна быть вторая матрица.

sometimes I believe compiler ignores all my comments spoiler

Carpal Tunnel

Рег.: 30.06.2004

Сообщений: 2884

Рейтинг: 5544

Re: Элементарная задачка по теории игр [re: volant]
29.03.2008 16:55

1

>Прояснить ситуацию и прокомментировать формулу det(M)/(a_11+a_22-a_21-a12).

Эта формула не является формулой для минимакса. Например, для матрицы
1 1
1 1

получается ноль, хотя тут как не играй - выигрыш равен 1

.
Я вообще эту формулу вижу впервые.

Разбираюсь в теории игр на уровне ВМК-шного курса, 1 поток.

sometimes I believe compiler ignores all my comments spoiler

Страницы: 0 | 20 | показать все | след. страница

General Discussion >> Study (Archive)

Дополнительная информация
1 зарегистрированных и 0 анонимных пользователей просматривают этот форум. Модераторы: Basilio, The_Nameless_One Печать темы >>	Права Вы можете создавать новые темы Вы можете отвечать на сообщения HTML отключен UBBCode включен	Рейтинг: Просмотров темы:
		Переход в