Какие здесь есть равновесия?

[hello19]

Дана матрица некоторой игры. Необходимо найти все равновесия в чистых стратегиях. Вот сама матрица:
$ \begin{bmatrix}5,4 & 5,3 & 1,5 & 2,1 & 4,2 \\ 3,4 & 3,6 & 5,7 & 2,5 & 5,3 \\ 3,2 & 2,1 & 7,0 & 3,5 & 6,3 \\ 4,2 & 8,4 & 3,3 & 1,4 & 3,6\end{bmatrix} $
В этой матрице нет доминирующих стратегий, к сожалению. Простым перебором клеток матрицы нашел несколько равновесий. Вот они (взял их в скобки):
$\begin{bmatrix} \big(5,4) & 5,3 & 1,5 & 2,1 & 4,2 \\\ 3,4 & 3,6 & 5,7 & 2,5 & 5,3 \\\ 3,2 & 2,1 & 7,0 & \big(3,5) & 6,3 \\\ 4,2 & \big(8,4) & 3,3 & 1,4 & 3,6\end{bmatrix}$
Есть ли тут еще какие-либо равновесия?

[provincialka]

А в чем дело? Там ведь, кажется, четкий алгоритм, почему вы сомневаетесь? Вы как рассуждали?
Я так понимаю, что стратегии первого игрока расположены по вертикали, а второго - по горизонтали?

Кстати, вы выделили игровую ситуацию в клетке $(4, 2)$ с выигрышами $8,4$, но ведь в той же строке есть пара $3,6$ - о чем это говорит?

[hello19]

Да, говорит. Говорит о том, что это не равновесие.
Равновесие в матрице всего лишь одно - это профиль $(s_3;t_4)$ с вектором выигрышей $(3;5)$

Теперь мне нужно найти равновесие в смешанных стратегиях.Считаю, что первый игрок (слева) выбирает свои стратегии с вероятностями $p, q, r, s. $
Соответственно считаю выигрыш второго игрока.
стратегия $t_1: 4p + 4q + 2r + 2s $
стратегия $t_2: 3p + 6q + r + 4s $
стратегия $t_3: 5p + 7q + 0r + 3s $
стратегия $t_4: p + 5q + 5r + 4s $
стратегия $t_5: 2p + 3q + 3r + 6s $
Ну и необходимое условие: $p + q + r + s = 1$
Система соответственно получится, если приравнять выигрыши второго игрока от всех стратегий. Т.е. вот так:
$4p + 4q + 2r + 2s = 3p + 6q + r + 4s $
и т.д...
Решение совсем уж кривое...(

[provincialka]

Честно говоря, я знаю про смешанные стратегии только для антагонистических игр (с нулевой суммой). Как ставится задача в общем случае?

-- 19.10.2013, 23:46 --

В любом случае оптимальной является не (смешанная) стратегия одного из игроков, а пара смешанных стратегий, по одной на каждого игрока. То есть искомыми являютмя вероятности $(p_1, p_2, p_3, p_4)$ ддя первого игрока и $(q_1,q_2,q_3,q_4,q_5)$ для второго. Всего 7 неизвестных.

Кстати, офррмляйте формулы с помощью ТеХ, а то тему перенесут в Карантин.

[hello19]

В описании задачи вот что:
(a) Найти все чистые равновесия Нэша
(b) Последовательно исключите все доминируемые стратегии. При удалении стратегий указывайте, какой чистой или смешанной стратегией она доминируется.
(c) Найдите все смешанные равновесия.

У меня еще вопрос - как указать, что какая-то стратегия доминируется смешанной?

[provincialka]

Может, еще кто подключится, а у нас ночь (час ночи). Завтра гляну на определения. И вы их поищите.

[hello19]

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

[provincialka]

Кого "ее"? Отдельная стратегия же не может быть равновесной. Что касается доминирования, пока вижу только прямой метод. Например, проверим стратегию $s_1$. Для этого при произвольных вероятностях $p_2,p_3,p_4, p_2+p_3+p_4=1$ построим смешанную стратегию из стратегий $s_2, s_3, s_4$. Может ли она доминировать $s_1$? Для этого пытаемся решить систему неравенств. И так для всех $4+5=9$ стратегий.
Но, может, есть способ получше

[hello19]

Под "ее" я подразумевал лишь распределение по стратегиям для первого игрока. Конечно это не смешанная стратегия. Извиняюсь за "кривое" изложение.

[Toucan]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»

[provincialka]

Думаю, неплохо в каждом столбце найти максимальный элемент (среди первых в паре) и пометить его. Также найти максимальный встроке (среди выигрышей второго игрока) и тоже пометить. Если в строке (выигрыши первого игрока) есть помеченный элемент, она точно недоминируема. Например, в клетке $s_1,t_1$ выигрыш первого игрока равен 5. Его нельзя превысить, комбинируя числа $3,3,4$ из остальных строк этого столбца. Значит, стратегия $s_1$ недоминируема.

[hello19]

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

[provincialka]

$ \begin{bmatrix}(5),4 & 5,3 & 1,(5) & 2,1 & 4,2 \\ 3,4 & 3,6 & 5,(7) & 2,5 & 5,3 \\ 3,2 & 2,1 & (7),0 & (3),(5) & (6),3 \\ 4,2 & (8),4 & 3,3 & 1,4 & 3,(6)\end{bmatrix} $
Вот что получилось, когда мы нашли максимальный выигрыш первого в каждом столбце и максимальный выигрыш второго в каждой строке. Сразу видна единственная равновесная ситуация, в которой помечены оба числа в паре.
Теперь видно, что доминируемыми могут быть только стратегии $s_2$ (вторая строка) и $t_1,t_2$ - первый и второй столбцы. Их и надо проверять.

-- 20.10.2013, 08:42 --

Вторая строка действительно доминируется третьей и четвертой, если взять их в соотношении 2:1, то есть с вероятностями $\frac23$ и $\frac13$. Нашла подбором в уме.

[hello19]

я вот еще чего не понимаю...
Нас учили делать так: смотрим на матрицу, находим строго доминируемую стратегию, вычеркиваем ее и далее работаем с матрицей меньшей размерности. Делаем вот такую пометку: $s \succ t$ (cnhfntubz s строго доминирует статегию t)
Если я правильно понимаю, то в случае со смешанными стратегиями надо также вычеркивать строку, которая является доминируемой, при это писать так: $ \frac{2}{3} s_{3} + \frac{1}{3} s_{4} \succ s_{2}$ Я прав?

[provincialka]

Как писать - это я на знаю, но вычеркивать, конечно, надо. Зачем нам лишние данные?