Тесты для итогового контроля

1. Антагонистическая игра может быть задана:

а) множеством стратегий обоих игроков и седловой точкой.

б) множеством стратегий обоих игроков и функцией выигрыша первого игрока.

2. Цена игры существует для матричных игр в смешанных стратегиях всегда.

а) да.

3.Если в матрице выигрышей все столбцы одинаковы и имеют вид (4 5 0 1), то какая стратегия оптимальна для 1-го игрока?

а) первая.

б)вторая.

в)любая из четырех.

4.Пусть в матричной игре одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.4, 0, 0.6). Какова размерность этой матрицы?

а) 2*3.

в) другая размерность.

5. Принцип доминирования позволяет удалять из матрицы за один шаг:

а) целиком строки.

б) отдельные числа.

6.В графическом методе решения игр 2*m непосредственно из графика находят:

а) оптимальные стратегии обоих игроков.

б) цену игры и оптимальные стратегии 2-го игрока.

в) цену игры и оптимальные стратегии 1-го игрока.

7.График нижней огибающей для графического метода решения игр 2*m представляет собой в общем случае:

а) ломаную.

б) прямую.

в) параболу.

8. В матричной игре 2*2 две компоненты смешанной стратегии игрока:

а) определяют значения друг друга.

б) независимы.

9. В матричной игре элемент aij представляет собой:

а) выигрыш 1-го игрока при использовании им i-й стратегии, а 2-м – j-й стратегии.

б) оптимальную стратегию 1-го игрока при использовании противником i-й или j-й стратегии.

в) проигрыш 1-го игрока при использовании им j-й стратегии, а 2-м – i-й стратегии.

10.Элемент матрицы aij соответствует седловой точке. Возможны следующие ситуации:

а) этот элемент строго меньше всех в строке.

б) этот элемент второй по порядку в строке.

11. В методе Брауна-Робинсон каждый игрок при выборе стратегии на следующем шаге руководствуется:

а) стратегиями противника на предыдущих шагах.

б) своими стратегиями на предыдущих шагах.

в) чем-то еще.

12. По критерию математического ожидания каждый игрок исходит из того, что:

а) случится наихудшая для него ситуация.

в) все или некоторые ситуации возможны с некоторыми заданными вероятностями.

13. Пусть матричная игра задана матрицей, в которой все элементы отрицательны. Цена игры положительна:

б) нет.

в) нет однозначного ответа.

14. Цена игры - это:

а) число.

б) вектор.

в) матрица.

15.Какое максимальное число седловых точек может быть в игре размерности 5*5 (матрица может содержать любые числа) :

16. Пусть в матричной игре размерности 2*3 одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.3, x, 0.5). Чему равно число x?

в) другому числу.

17. Для какой размерности игровой матрицы критерий Вальда обращается в критерий Лапласа?

в)только в других случаях.

18. Верхняя цена игры всегда меньше нижней цены игры.

б) нет.

б) вопрос некорректен.

19. Какие стратегии бывают в матричной игре:

а) чистые.

б) смешанные.

в) и те, и те.

20. Могут ли в какой-то антагонистической игре значения функции выигрыша обоих игроков для некоторых значений переменных равняться 1?

а) всегда.

б) иногда.

в) никогда.

21.Пусть в матричной игре одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.4, 0.1,0.1,0.4). Какова размерность этой матрицы?

в) иная размерность.

22. Принцип доминирования позволяет удалять из матрицы за один шаг:

а) целиком столбцы,

б) отдельные числа.

в) подматрицы меньших размеров.

23. В матричной игре 3*3 две компоненты смешанной стратегии игрока:

а) определяют третью.

б) не определяют.

24. В матричной игре элемент aij представляет собой:

а) проигрыш 2-го игрока при использовании им j-й стратегии, а 2-м – i-й стратегии .

б) оптимальную стратегию 2-го игрока при использовании противником i-й или j-й стратегии,

в) выигрыш 1-го игрока при использовании им j-й стратегии, а 2-м – i-й стратегии,

25. Элемент матрицы aij соответствует седловой точке. Возможны следующие ситуации:

а) этот элемент больше всех в столбце.

б) этот элемент строго больше всех по порядку в строке.

в) в строке есть элементы и больше, и меньше, чем этот элемент.

26. По критерию Вальда каждый игрок исходит из того, что:

а) случится наиболее плохая для него ситуация.

б) все ситуации равновозможны.

в) все ситуации возможны с некоторыми заданными вероятностями.

27. Нижняя цена меньше верхней цены игры:

б) не всегда.

в) никогда.

28. Сумма компонент смешанной стратегия для матричной игры всегда:

а) равна 1.

б) неотрицательна.

в) положительна.

г) не всегда.

29. Пусть в матричной игре размерности 2*3 одна из смешанных стратегий 1-го игрока имеет вид (0.3, 0.7), а одна из смешанных стратегий 2-го игрока имеет вид (0.2, x, x). Чему равно число x?

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

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

По аналогии с матричными играми чистой нижней ценой игры можно назвать v { = max min U(x, у), а чистой верхней ценой игры -v 2 =

min max U{x, у). Тогда по аналогии можно считать, что если для какой-

у *

либо бесконечной антагонистической игры величины V и v 2 существуют и равны между собой («i =v 2 =v), то такая игра имеет решение в чистых стратегиях, т.е. оптимальной стратегией игрока 1 является выбор числа х° е X, а игрока 2 - числа у 0 е 7, при которых Щх { у 0) -v.

В этом случае v называется чистой ценой игры, а (х°, у 0) - седловой точкой бесконечной антагонистической игры.

Для матричных игр величины v x и v 2 всегда существуют, но в бесконечных антагонистических играх они могут и не существовать, т.е. бесконечная антагонистическая игра не всегда разрешима.

При формализации реальной ситуации в виде бесконечной антагонистической игры обычно выбирается единичный стратегический интервал - единичный промежуток, из которого игроки могут сделать выбор (х - число (стратегия), выбираемое игроком 1; -

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

Для примера допустим, что игрок 1 выбирает число х из множества Х= , игрок 2 выбирает число у из множества Y= . После этого игрок 2 платит игроку 1 сумму Щх, у) -2х 2 -у 2 . Поскольку игрок 2 стремится минимизировать платеж игрока 1, то он определяет min (2х 2 - у 2) = 2х 2 - 1, т.е. при этому= 1. Игрок 1 стремится мак- тег

симизировать свой платеж, поэтому определяет maxi min Щх, у)1 =

xGX у ег

- max (2х 2 - 1) = 2- 1 = 1, который достигается при х = 1.

Таким образом, нижняя чистая цена игры v x - 1. Верхняя чистая

цена игры v 2 = min - min (2 - у 2) = 2 - 1 = 1, т.е. в этой

>ег хех у еу

игре v l =v 2 =l. Поэтому чистая цена игры v = 1, а седловая точка (х° = 1; у°=1).

Предположим теперь, что Хи Y- открытые интервалы, т.е. игрок 1 выбираетxeA"=(0; 1), игрок 2 выбирает уе 7= (0; 1). В этом случае, выбирая х, достаточно близкое к 1, игрок 1 будет уверен, что он получит выигрыш не меньше, чем число, близкое к»=1; выбирая у, близкое к 1, игрок 2 не допустит, чтобы выигрыш игрока 1 значительно превышал чистую цену игры v= 1.

Степень близости к цене игры может характеризоваться числом?>0. Поэтому в описываемой игре можно говорить об оптимальности чистых стратегий х° = 1, у 0 = 1 соответственно игроков 1 и 2 с точностью до произвольного числа?>0. Точка (х„ , у Е), где х е е X, у (. eY, в бесконечной антагонистической игре называется точкой z-равновесия (с.-седловой точкой) , если для любых стратегий хеТигрока 1,уе Тигро- ка 2 имеет место неравенство Щх, у.) - ? Щ x r , у (.) U(x t ., у) + ?. В этом случае стратегии х к. и у. называются с,-оптимальными стратегиями . Эти стратегии являются оптимальными с точностью до? в том смысле, что если отклонение от оптимальной стратегии никакой пользы игроку принести не может, то его отклонение от с-оптимальной стратегии может увеличить его выигрыш не более чем на е.

Если игра не имеет седловой точки (с-седловой точки), т.е. решения в чистых стратегиях, то оптимальные стратегии можно искать среди смешанных стратегий, в качестве которых используются функции распределения вероятностей применения игроками чистых стратегий.

Пусть F(x) - функция распределения вероятностей применения чистых стратегий игроком 1. Если число Е, - чистая стратегия игрока 1, то F(x) = P(q где P(q - Х) - вероятность того, что случайно выбранная чистая стратегия Е, не будет превосходить х. Аналогично рассматривается функция распределения вероятностей применения чистых стратегий г| игроком 2: Q(y) = Р(г .

Функции F(x) и Q(y) называются смешанными стратегиями соответственно игроков 1 и 2. Если Fx) и Q(y) дифференцируемы, то существуют их производные, обозначаемые соответственно через f{x) и q(y) (функции плотности распределения).

В общем случае дифференциал функции распределения dF{x ) выражает вероятность того, что стратегия с, находится в промежутке х Е, Аналогично для игрока 2: dQ(y) означает вероятность того, что его стратегия р находится в интервале у г| у+dy. Тогда платеж игрока 1 составит Щх, у) dF(x), а платеж игрока 2 равен Щх, у) dQ(y).

Средний платеж игрока 1 при условии, что игрок 2 применяет свою чистую стратегию у, можно получить, проинтегрировав платежи по всем возможным значениям х, т.е. на единичном интервале:

Средний платеж игрока 1 при условии, что оба игрока применяют свои смешанные стратегии F{x) и Q(y), будет равен

По аналогии с матричными играми определяются оптимальные смешанные стратегии игроков и цена игры: если пара смешанных стратегий F*(x ) и Q*(y) соответственно для игроков 1 и 2 являются оптимальными, то для любых смешанных стратегий F(x) и Q(y) справедливы соотношения:

Если игрок 1 отступает от своей стратегии F*(x), то его средний выигрыш не может увеличиться, но может уменьшиться из-за рациональных действий игрока 2. Если игрок 2 отступит от своей смешанной стратегии Q*(y), то средний выигрыш игрока 1 может увеличиться, но не уменьшиться, за счет более разумных действий игрока 1. Средний выигрыш E(F*, Q*), получаемый игроком 1 при применении игроками оптимальных смешанных стратегий, соответствует цене игры.

Тогда нижняя цена бесконечной антагонистической игры, решаемой в смешанных стратегиях, может быть определена как v x = шах

min Е (FQ), а верхняя цена игры как v 2 = min max Е(F, Q).

Q Q f

Если существуют такие смешанные стратегии F* (х) и Q* (у) соответственно для игроков 1 и 2, при которых нижняя и верхняя цены игры совпадают, то F*(x) и Q*(y) естественно назвать оптимальными смешанными стратегиями соответствующих игроков, a v=v x = v 2 - ценой игры.

В отличие от матричных игр решение бесконечной антагонистической игры существует не для всякой функции Щх, у). Но доказана теорема о том, что всякая бесконечная антагонистическая игра с непрерывной платежной функцией Щх, у) на единичном квадрате имеет решение (игроки имеют оптимальные смешанные стратегии), хотя общих методов для решения бесконечных антагонистических игр, в том числе непрерывных игр, не существует. Однако достаточно просто решаются антагонистические бесконечные игры с выпуклыми и вогнутыми непрерывными платежными функциями (они называются соответственно выпуклыми и вогнутыми играми).

Рассмотрим решение игр с выпуклой платежной функцией. Решение игр с вогнутой функцией выигрыша симметрично.

Выпуклой функцией/переменной х на интервале (а ; Ь) называется такая функция, для которой выполняется неравенство

где Хх и х 2 - любые две точки из интервала (а; b );

Х.1, А.2 > 0, причем +Х.2= 1.

Если для / ч * 0 Д 2 * 0, всегда имеет место строгое неравенство

то функция/называется строго выпуклой на (а; Ь).

Геометрически выпуклая функция изображает дугу, график которой расположен ниже стягивающей ее хорды. Аналитически выпуклость дважды дифференцируемой функции соответствует неотрицательности (а в случае строгой выпуклости - положительности) ее второй производной.

Для вогнутых функций свойства противоположны, для них должно выполняться неравенство/(/4X1 +А.2Х2) > Kf (xi) +)-if (х 2) (> при строгой вогнутости), а вторая производная/"(х)

Доказано , что непрерывная и строго выпуклая функция на замкнутом интервале принимает минимальное значение только в одной точке интервала. Если Щх, у) - непрерывная функция выигрышей игрока 1 на единичном квадрате и строго выпуклая по у для любого х, то имеется единственная оптимальная чистая стратегия у=у° е для игрока 2, цена игры определяется по формуле

а значение у 0 определяется как решение следующего уравнения:

Если функция Щх, у) не строго выпуклая по у, то у игрока 2 оптимальная чистая стратегия не будет единственной.

Симметричное свойство выполняется и для строго вогнутых функций. Если функция Щх, у) непрерывна по обоим аргументам и строго вогнута по х при любом у, то игрок 1 имеет единственную оптимальную стратегию.

Цена игры определяется по формуле

а чистая оптимальная стратегия х 0 игрока 1 определяется из уравнения

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

1. Проверить функцию Щх, у) на выпуклость по у (вторая частная производная должна быть больше либо равна 0).

2. Определить у 0 из соотношения v- min max Щх, у) как значение

у, на котором достигается минимакс.

3. Найти решение уравнения v = U(x, у 0) и составить пары его решений Х и х 2 , для которых

4. Найти параметр а из уравнения

Параметр а определяет оптимальную стратегию игрока 1 и имеет смысл вероятности выбора им его чистой стратегии х х. Величина 1 - а имеет смысл вероятности выбора игроком 1 его чистой стратегии х 2 .

Покажем на примере использование этой схемы для решения игры такого вида. Пусть функция выигрыша в бесконечной антагонистической игре задана на единичном квадрате и равна Щх, у) = = (х - у) 2 =х 2 - 2ху ч-у 2 .

1. Эта функция непрерывна по х и у, и поэтому эта игра имеет решение. Функция Щх, у) строго выпукла по у, так как

Следовательно, игрок 2 имеет единственную чистую оптимальную стратегию у 0 .

2. Имеем v = min max (х - у) 2 . Для определения max (х 2 - 2ху Ч-у 2)

последовательно найдем первую и вторую частные производные пла- тежной функции по х:

Таким образом, функция U имеет минимум для любого у при х=у. Это значит, что при ху - возрастает, а ее максимум должен достигаться в одной из крайних точек х=0 или х= 1. Определим значения функции U в этих точках:

Тогда шах (х - у) 2 = тах {у 2 ; 1 - 2у+у 2 }. Сравнивая «внутренние»

максимумы, стоящие в фигурных скобках, легко заметить, что у 2 > 1 - - 2у+у 2 , если у > */ 2 и у 2 1 - 2у+у 2 , если у "/ 2 . Более наглядно это представляется графиком (рис. 2.5).

Рис. 2.5. Внутренние максимумы платежной функции U(х, у) = (х- у ) 2

Поэтому выражение (х - у) 2 достигает своего максимума при х=0, если у > 7 2 , и при х= 1, если у У 2:

Следовательно, v= min { min у 2 ; min (1 - у) 2 }. Каждый из вну-

тренних минимумов достигается при у= */ 2 и принимает значение У 4 . Таким образом, цена игры г = У 4 , а оптимальная стратегия игрока 2:

3. Определим оптимальную стратегию игрока 1 из уравнения U(x, у 0)=v, т.е. для данной игры (х - У 2) 2 =У 4 . Решением этого уравнения ЯВЛЯЮТСЯ Х| =0, х 2 = 1.

Для них выполняются условия

4. Определим параметр а, т.е. вероятность применения игроком 1 его чистой стратегии Х] = 0. Составим уравнение а-1 + (1 - а) (-1)=0, откуда а = У 2 . Таким образом, оптимальная стратегия игрока 1 состоит в выборе им своих чистых стратегий 0 и 1 с вероятностью 1 / 2 каждая. Задача решена.

Назначение сервиса . С помощью сервиса в онлайн режиме можно:

• определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии, найти минимаксную стратегию игроков;
• записать математическую модель пары двойственных задач линейного программирования, решить матричную игру методами: минимакс, симплекс-метод , графический (геометрический) метод, методом Брауна .

Инструкция . Выберите размерность матрицы, нажмите Далее. В новом диалоговом окне выберите метод решения матричной игры. Пример заполнения . Результаты вычислений оформляются в отчете формата Word .

Игра – это математическая модель реальной конфликтной ситуации. Конфликтная ситуация двух игроков называется парной игрой. Парную игру с нулевой суммой удобно исследовать, если она описана в виде матрицы. Такая игра называется матричной ; матрица, составленная из чисел a ij , называется платежной . В таблице представлены варианты решения игры, заданной платежной матрицей А.

Описание алгоритма:

1. На основании анализа платёжной матрицы следует определить, существуют ли в ней доминируемые стратегии, и исключить их.
2. Найти верхнюю и нижнюю цены игры и определить, имеет ли данная игра седловую точку (нижняя цена игры должна быть равна верхней цене игры).
3. Если седловая точка существует, то оптимальными стратегиями игроков, являющимися решением игры, будут их чистые стратегии, соответствующие седловой точке. Цена игры равна верхней и нижней цены игры, которые равны между собой.
4. Если игра не имеет седловой точки, то решение игры следует искать в смешанных стратегиях. Для определения оптимальных смешанных стратегий в играх m × n следует использовать симплекс-метод, предварительно переформулировав игровую задачу в задачу линейного программирования.

Представим алгоритм решения матричной игры графически.

Рисунок - Схема решения матричной игры.

Методы решения матричной игры в смешанных стратегиях

Итак, если седловая точка отсутствует, решение игры проводят в смешанных стратегиях и решают следующими методами:

1. Решение игры через систему уравнений.
   Если задана квадратная матрица nxn (n=m), то вектор вероятностей можно найти, решив систему уравнений. Этот метод используется не всегда и применим только в отдельных случаях (если матрица 2x2 , то решение игры получается практически всегда). Если в решении получаются отрицательные вероятности, то данную систему решают симплекс-методом.
2. Решение игры графическим методом.
   В случаях, когда n=2 или m=2 , матричную игру можно решить графически .
3. Решение матричной игры симплекс-методом.
   В этом случае матричная игра сводится к

Московский Энергетический Институт

(Технический Университет)

Отчёт по лабораторной работе

по теории игр

«Программа поиска оптимальных стратегий для парной антагонистической игры, заданной в матричной форме»

Выполнили студенты

группы А5-01

Ашрапов Далер

Ашрапова Ольга

Основные понятия теории игр

Теория игр разработана для разрешения конфликтных ситуаций , т.е. ситуаций, в которых сталкиваются интересы двух и более сторон, преследующих различные цели.

Если цели сторон прямо противоположны, то говорят об антагонистическом конфликте .

Игрой называется упрощённая формализованная модель конфликтной ситуации.

Однократный розыгрыш игры от начала до конца называется партией . Результатом партии являетсяплатёж (иливыигрыш ).

Партия состоит из ходов , т.е. выборов игроков из некоторого множества возможных альтернатив.

Ходы могут быть личные ислучайные .Личный ход , в отличие отслучайного , предполагает сознательный выбор игроком некоторого варианта.

Игры, в которых имеется хотя бы один личный ход, называются стратегическими .

Игры, в которых все ходы случайны, называются азартными .

При совершении личного хода говорят также о стратегии игрока, т.е. о правиле или совокупности правил, определяющих выбор игрока. При этом стратегия должна быть всеобъемлющей, т.е. выбор должен быть определён для любой возможной в ходе партии ситуации.

Задача теории игр – нахождение оптимальных стратегий игроков, т.е. стратегий, обеспечивающих им максимальный выигрыш или минимальный проигрыш.

Классификация теоретико-игровых моделей

Игру n лиц принято обозначать как, где
- множество стратегийi-го игрока,
- платёж игры.

В соответствии с данным обозначением можно предложить следующую классификацию теоретико-игровых моделей:

Дискретные (множества стратегийдискретны)

Конечные

Бесконечные

Непрерывные (множества стратегий непрерывны)

Бесконечные

n лиц (
)

Коалиционные (кооперативные)

Некоалиционные (некооперативные)

2-х лиц (парные)

Антагонистические (игры с нулевой суммой)

(интересы сторон противоположны, т.е. проигрыш одного игрока равен выигрышу другого)

Неантагонистические

С полной информацией (если игроку, делающему личный ход известна вся предыстория игры, т.е. все ходы противника)

С неполной информацией

С нулевой суммой (суммарный платёж равен нулю)

С ненулевой суммой

Одноходовые (лотереи)

Многоходовые

Матричное представление парной антагонистической игры

В данном пособии будем рассматривать антагонистические игры двух лиц , заданные в матричной форме. Это означает, что нам известно множество стратегий первого игрока (игрокA ){ A i }, i = 1,…, m и множество стратегий второго игрока (игрокB ){ B j }, j = 1,..., n , а также задана матрицаA = || a ij || выигрышей первого игрока. Поскольку речь идёт об антагонистической игре, то предполагается, что выигрыш первого игрока равен проигрышу второго. Считаем, что элемент матрицыa ij – выигрыш первого игрока при выборе им стратегииA i и ответе ему второго игрока стратегиейB j . Такую игру будем обозначать как
, гдеm - количество стратегий игрокаА, n - количество стратегий игрокаВ. В общем виде она может быть представлена следующей таблицей:

	B 1		B j		B n
A 1
A i
A m

Пример 1

В качестве простейшего примера рассмотрим игру, партия которой состоит из двух ходов.

1-й ход : ИгрокА выбирает одно из чисел (1 или 2), не сообщая о своём выборе сопернику.

2-й ход : ИгрокВ выбирает одно из чисел (3 или 4).

Итог : Выборы игроковА иВ складываются. Если сумма чётная, тоВ выплачивает её значение игрокуА , если же нечётная - наоборот,А выплачивает сумму игрокуВ .

Данная игра может быть представлена в виде
следующим образом:

	(выбор 3)	(выбор 4)
(выбор 1)
(выбор 2)

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

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

При решении игры в матричной форме следует проверить игру на наличие седловой точки . Для этого вводятся две величины:

– нижняя оценка цены игры и

– верхняя оценка цены игры.

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

Можно доказать, что α ≤ V ≤ β , гдеV –цена игры , т.е., вероятный выигрыш первого игрока.

Если выполняется соотношение α = β = V , то говорят, чтоигра имеет седловую точку
, ирешается в чистых стратегиях . Иными словами, имеется пара стратегий
, дающих игрокуА V .

Пример 2

Вернёмся к игре, рассмотренной нами в примере 1 и проверим её на наличие седловой точки.

	(выбор 3)	(выбор 4)
(выбор 1)
(выбор 2)

Для данной игры
= -5,
= 4,
, следовательно, она не имеет седловой точки.

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

Пример 3

Внесём в правила игры из примера 1 некоторые изменения. Предоставим игроку В информацию о выборе игрокаА. Тогда уВ появятся две дополнительные стратегии:

- стратегия, выгодная дляА. Если выборА - 1, то В выбирает 3, если выборА - 2, то В выбирает 4;

- стратегия, не выгодная дляА. Если выборА - 1, то В выбирает 4, если выборА - 2, то В выбирает 3.

	(выбор 3)	(выбор 4)
(выбор 1)
(выбор 2)

Эта игра - с полной информацией.

В данном случае
= -5,
= -5,
, следовательно, игра имеет седловую точку
. Данной седловой точке соответствуют две пары оптимальных стратегий:
и
. Цена игрыV = -5. Очевидно, что дляА такая игра невыгодна.

Примеры 2 и 3 являются неплохой иллюстрацией к следующей теореме, доказанной в теории игр:

Теорема 1

Всякая парная антагонистическая игра с полной информацией решается в чистых стратегиях.

Т.о. теорема 1 говорит о том, что любая игра двух лиц с полной информацией имеет седловую точку и существует пара чистых стратегий
, дающих игрокуА устойчивый выигрыш, равный цене игрыV .

Вслучае же отсутствия седловой точки, в качестве решения используются т.н.смешанные стратегии :, гдеp i и q j – вероятности выбора стратегийA i и B j первым и вторым игроками соответственно. Решением игры в данном случае является пара смешанных стратегий
, максимизирующих математическое ожидание цены игры.

Обобщением теоремы 1 на случай игры с неполной информацией служит следующая теорема:

Теорема 2

Любая парная антагонистическая игра имеет хотя бы одно оптимальное решение, т.е., пару в общем случае смешанных стратегий
, дающих игрокуА устойчивый выигрыш, равный цене игрыV , причёмα ≤ V ≤ β .

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

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

Таким образом, Игрок 1 выбирает i

Игрок 2 точно также стремится обеспечить себе наивысшую величину выигрыша (или, что эквивалентно, наименьшую величину проигрыша) вне зависимости от выбранной стратегии противника. Его оптимальной стратегией будет столбец Н 0 с наименьшим максимальным платежом. Таким образом, Игрок 2 выберет j -ю стратегию, которая является решением задачи

В итоге, если Игрок 1 придерживается избранной стратегией (называемой максиминнной стратегией ), его выигрыш в любом случае будет меньше максиминного значения (называемого «нижней ценой игры» ), т.е.

Соответственно, если Игрок 2 придерживается своей минимаксной стратегии, то его проигрыш будет не больше максиминного значения (называемого «верхней ценой игры» ), т.е.

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

Элемент матрицы h ij матрицы выигрышей, соответствующей стратегиям, называется седловой точкой матрицы Н .

В случае, если цена антагонистической игры равна 0, игра называется справедливой .

Рассмотрим игру, в которой Игрок 1 располагает двумя стратегиями, а Игрок 2 – тремя. Матрица выигрышей Игрока 1 имеет вид:

Замечание . Поскольку мы рассматриваем пример антагонистической игры, то матрица выигрышей Игрока 2 будет Н 2 =-Н 1 .

Игрок 1 рассчитывает, что если он выберет первую стратегию (т.е. первую строку матрицы Н 1 ), то противник выберет свою вторую стратегию (т.е. второй столбец) так, что выигрыш будет равен 1 . Если же он выбирает вторую стратегию, то противник может выбрать первую стратегию, так что выигрыш будет равен -1.

Проанализировав полученные значения: Игрок 1 останавливается на своей первой стратегии, которая обеспечивает ему максимальный гарантированный выигрыш, равный 1.

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

Взяв минимальные значения этих максимумов, Игрок 2 останавливается на своей второй стратегии, при которой его проигрыш минимален и равен :

Следовательно, в этой игре существуют совместные выборы стратегий, те. Е

Следовательно в этой игре разумно ожидать, что противники будут придерживаться избранных стратегий. Матричная антагонистическая игра, для которой - называется вполне определенной, или игрой имеющей решение в чистых стратегиях.

Однако не все матричные антагонистические игры являются вполне определенными.

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

Рассмотрим пример такой игры:

Для этой игры .

В итоге если игроки будут следовать предложенным выше правилам, то Игрок 1 выберет стратегию 1 и будет ожидать, что Игрок 2 выберет стратегию 2, при которой проигрыш равен -2, в то время как Игрок 2 изберет стратегию 3 и будет ожидать что Игрок 1 выберет стратегию 2 с выигрышем равным 4.

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

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

По существу, смешанная стратегия игрока представляет собой схему случайного выбора чистой стратегии. Математически ее можно представить как вероятностное распределение на множестве чистых стратегий данного игрока. В итоге вектор , где соответствует вероятности применения Игроком 1 -той стратегии и , задает смешанную стратегию этого игрока. Аналогично определяется смешанная стратегия у Игрока 2 .

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

или матричных обозначениях

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

.

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

.

Фундаментальным результатом теории игр является так называемая Теорема о минимаксе, которая утверждает, что сформулированные задачи Игрока 1 и Игрока 2 всегда имеют решение для любой матрицы выигрышей , и кроме того, .

Как и для вполне определенных игр, стратегия Игрока 1 называется Максиминной стратегией , стратегия Игрока 2 - минимаксной стратегией, значение - ценой игры; в случае, когда игра называется справедливой.

Очевидным следствием из Теоремы о минимаксе является соотношение:

.

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

Это верно также и для чистых стратегий, как для частного случая смешанных стратегий. (Т.к. чистая стратегия – это стратегия, используемая с вероятностью 1): Использование любой чистой стратегии, в случае если противник использует свою оптимальную стратегию, не позволяет выиграть больше (проиграть меньше) цены игры.

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

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

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

Аналогично -й столбец доминирует -й столбец, если для всех , хотя бы для одного .

Смысл этого определения состоит в том, что доминирующая стратегия никогда не хуже, а в некоторых случаях даже лучше, чем доминируемая стратегия. Отсюда, важный вывод – игроку нет необходимости использовать доминируемую стратегию. Это позволяет на практике все доминируемые строки и столбцы отбросить, что позволит уменьшить размеры матрицы (заметим, что этот подход может использоваться также при поиске решения в чистых стратегиях).

Пример. Рассмотрим игру со следующей матрицей:

→ третья строка этой матрицы доминирует вторую

Исключение второй строки приводит к матрице: третий столбец в этой урезанной матрице доминирует второй, и исключение второго столбца дает: .

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

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

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

Кроме того может быть использован графический способ для решения игры (и вообще игр или ).

Например, матрица выигрышей имеет вид: .

Пусть Игрок 1 выбирает свою первую стратегию с вероятностью , а вторую с вероятностью . Если Игрок 2 выбирает свою первую стратегию, то (из первого столбца матрицы) математическое ожидание для Игрока 1 будет равно . Если Игрок 2 выбирает свою вторую стратегию, то в соответствии со вторым столбцом матрицы: .

Каждое из этих уравнений может быть изображено графически отрезком прямой линии в области на графике с координатами и .