Задачка по теории игр

Brodnik

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

griz_a

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

Brodnik

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

griz_a

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

olegikristina

LOL, пытаешься заботать задачку из REA GRE Math. Я тоже на ней завис, хотя формула для решения есть. :)
Формула кстати такая: det(M)/(a_11+a_22-a_21-a12)

resident

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

Brodnik

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

griz_a

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

MammonoK

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

Brodnik

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

Goodnight18

ищется решение игры в смешанных стратегиях с помощью решения системы уравнений
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)

griz_a

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

Brodnik

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

Goodnight18

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

toxin

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

Goodnight18

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

romanenkoroman1

вообще-то тут должны быть не ур-ния а неравенства:
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

Goodnight18

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

shpanenoc

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

shpanenoc

>Прояснить ситуацию и прокомментировать формулу det(M)/(a_11+a_22-a_21-a12).
Эта формула не является формулой для минимакса. Например, для матрицы
1 1
1 1
получается ноль, хотя тут как не играй - выигрыш равен 1 :).
Я вообще эту формулу вижу впервые.
Разбираюсь в теории игр на уровне ВМК-шного курса, 1 поток.

romanenkoroman1

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

natunchik

Откуда же возникло 5/2
Подозреваю, что авторы задачи решили, что второй игрок должен юзать смешанную стратегию, потому что вдруг первый выберет 1, тогда второму маза выбирать 2. Но это, очевидно, бред.

olegikristina

Условие задачи следующее:
Consider the two player (P_1,P_2) game G with playoff matrix [здесь матрица]. The minimax value of G is
(A) 5/3 (B) 1 (C) 3/2 (D) 5 (E) 0
Забейте, короче, книга уже подтвердила совою тупость в плане опечаток, их тут куча и при том самых дибильных.

den81

Возможно, тогда правильный ответ 1, потому что авторы перепутали местами стратегии игроков или функцию выигрыша определили наоборот. 1 — максимум по строке, минимум по столбцу.
Оставить комментарий
Имя или ник:
Комментарий: