Матричная игра

Eleno4ka

Решите, плиз, матричную игру
 0 -4 3 8
-2 2 -1 7
7 6 4 -10

anestez

Сдается мне, что:
Цена игры: 324/203
Оптимальная стратегия для первого игрока: (59/203, 76/203, 68/203)
Оптимальная стратегия для второго игрока: (14/29, 43/203, 0, 62/203)

Eleno4ka

в уме?

anestez

В Мапле! С привлечением здравого смысла.
Но ты можешь доказать, что предъявленные мною решения, действительно, оптимальные.

Eleno4ka

не ну это читерство
пойду смотреть доминирование/задачи лп писать/вспоминать

anestez

Доминирование не поможет, ничто здесь не доминируется.
Могу предположить план решения. Коли доминирования нет, то предположим, что все стратегии первого игрока - существенные. У второго игрока из трех стратегий существенные - три. Далее для всех четырех способов выбрать из 4 стратегий второго игрока три составляем систему уравнений с четырьмя неизвестными: (p,q,r) - оптимальная стратегия первого игрока, s - цена игры. Четыре уравнения - это то, что наша оптимальная стратегия (p,q,r) против трех выбранных чистых стратегий второго игрока дает выигрыш s, и то, что p+q+r=1. Из четырех систем должна оказаться совместной только одна, соответствующая выбору первой, второй и четвертой стратегии второго игрока. Итак, мы нашли цену игры и оптимальную стратегию первого игрока. Далее находим оптимальную стратегию второго игрока. Наконец, доказываем, что эти стратегии - оптимальные для завершения доказательства.
А проще всего решение опустить и привести только доказательство.

Eleno4ka

Ничего не поняла - какие системы, откуда
Знания тигров базовые

anestez

Главное свойство оптимальной стратегии - оптимальная стратегия игрока оптимальна против любой чистой стратегии противника. Если s - цена игры, то применение оптимальной стратегии против существенной стратегии другого игрока даст значение, равное s, а против несущественной стратегии - значение, которое лучше s (лучше в смысле больше для первого игрока и меньше для второго игрока).
Пусть (p, q, r) - оптимальная стратегия для первого игрока. Тогда применение этой стратегии против первой чистой стратегии второго игрока даст значение игры, равное 0*p-2*q+7*r
Против второй стратегии даст -4*p+2*q+6*r
Против третей стратегии даст 3*p-1*q+4*r
Против четвертой стратегии даст 8*p+7*q-10*r
Если s - цена игры и все бы стратегии второго игрока были бы существенными, то мы получили бы систему:
0*p-2*q+7*r=s
-4*p+2*q+6*r=s
3*p-1*q+4*r=s
8*p+7*q-10*r=s
И еще одно уравнение: p+q+r=1
В этой системе 4 неизвестных и 5 уравнений. Она несовместна. Однако, если выбросить третье уравнение, то должна получиться совместная система. Если выбросить другие уравнения из первых четырех, то должна получиться несовместная система, но этот факт я не проверял.
Решая систему, получим p, q, r, s, какие я указал в ответе. Это цена игры и оптимальная стратегия первого игрока. Подставив p, q, r в третье (выброшенное) уравнение, мы получим величину, большую, чем s. Тем самым мы доказали, что наша найденная стратегия гарантирует первому игроку выигрыш не менее, чем s против любой стратегии второго игрока.
Теперь найдем оптимальную стратегию для второго игрока. Поскольку мы выбросили третье уравнение, третья чистая стратегия дает для второго игрока проигрыш, больший, чем s против оптимальной стратегии первого игрока, то эта стратегия несуществена. Пусть оптимальная стратегия для второго игрока имеет вид (a, b, 0, c). Запишем условия, что применение этой смешанной стратегии против чистых стратегий первого игрока дает цену игры, равную s:
0*a-4*b+8*c=s
-2*s+2*b+7*c=s
7*a+6*b+4*c=s
s уже нашли, получаем совместную систему, решаем, находим оптимальную стратегию для второго игрока. Эта стратегия обеспечивает второму игроку проигрыш, не более, чем s против любой смещанной стратегии первого игрока. Тем самым мы доказали, что s - цена игры, а найденные стратегии являются оптимальными.

angel_18

Рассажите плз., про что вы вообще?

anestez

Это теория игр.
О том, что это такое рассказывается, например, в брошюре Вентцеля для школьников или в книге Оуэна "Теория игр", но ее я в интернете что-то не найду.

angel_18

Спасибо!

Eleno4ka

Да, кстати, спасибо большое за предоставленное решение!
Оставить комментарий
Имя или ник:
Комментарий: