Определение 4. Парная игра, в которой сумма выигрышей игроков равна нулю (выигрыш первого игрока равен проигрышу второго игрока) называется парной игрой с нулевой суммой или антагонистической игрой .
Замечание. Всякую парную игру с нулевой суммой всегда можно полностью задать платёжной матрицей одного из игроков. Как правило, задают платёжную матрицу первого игрока. Предполагается, что все игроки одинаково разумны. Задача каждого игрокасостоит в том, что каждый игрок стремится обеспечить себе максимально возможный выигрыш при любых действиях другого игрока.
Пусть платёжная матрица первого игрока в игре двух игроков, имеющих соответственно и стратегий, имеет вид 
. Тогда матрица выигрышей второго игрока .
Построим оптимальные стратегии игроков в антагонистической игре.
Оптимальная стратегия первого игрока. Первый игрок желает получить максимальный собственный выигрыш. При этом он предполагает, что в любом случае второй игрок выберет стратегию, минимизирующую выигрыш первого игрока. Задача первого игрока – получить некоторый гарантированный выигрыш.
Обозначим минимальное значение выигрыша первого игрока при каждой его стратегии (в каждой строке матрицы ): , . Зная минимальные выигрыши при различных стратегиях второго игрока, первый игрок выберет ту стратегию, при которой максимально. Обозначим это значение . Тогда 
.
Определение 5. Величина – гарантированный максимальный выигрыш, который может обеспечить себе первый игрок, – называется нижней ценой игры или максимином .
Таким образом, формально оптимальная стратегия первого игрока состоит в выборе строки и в ней элемента матрицы : . Эта стратегия называется максиминной со стороны первого игрока. Если первый игрок будет придерживаться максиминной стратегии, то его выигрыш в любом случае будет не меньше максиминного значения:
Оптимальная стратегия второго игрока. Второй игрок желает минимизировать собственный проигрыш. При этом он предполагает, что в любом случае первый игрок выберет стратегию, максимизирующую собственный выигрыш. Задача второго игрока – проиграть не более некоторой гарантированной суммы.
Обозначим максимальное значение выигрыша первого игрока при каждой стратегии второго игрока (в каждом столбце матрицы ): , . Зная максимальные выигрыши первого игрока при различных стратегиях второго игрока , второй игрок выберет ту стратегию, при которой минимально. Обозначим это значение . Тогда 
.
Определение 6. Величина – минимальный проигрыш, который может обеспечить себе второй игрок, – называется верхней ценой игры или минимаксом .
Таким образом, формально оптимальная стратегия второго игрока состоит в выборе столбца и в ней элемента матрицы : . Эта стратегия называется минимаксной со стороны второго игрока. Если второй игрок будет придерживаться минимаксной стратегии, то он в любом случае проиграет не больше минимаксного значения:
Теорема 1.
Для произвольной прямоугольной матрицы всегда выполняется неравенство 
или
Определение 7. Если верхняя цена игры равна нижней, то есть , то говорят, что игра имеет седловую точку (решается ) в чистых стратегиях .
Определение 8. Значение называется ценой игры (чистой ценой игры ) .
Определение 9. Элемент матрицы называется седловым элементом матрицы .
Замечание.
Седловой элемент матрицы одновременно является минимальным в своей строке и максимальным в своём столбце, то есть 
Определение 10. Пару чистых стратегий и , соответствующих и , называют седловой точкой игры .
Замечание. Стратегии и , образующие седловую точку, являются оптимальными. Существование седловой точки платёжной матрицы соответствует наличию состояния равновесия в данной матричной игре.
Определение 11. Тройка называется решением игры .
Пример 2.4 . В игре участвуют два игрока. Каждый из них может записать независимо от другого цифры 1, 2 и 3. если разность между цифрами, записанными игроками, положительна, то первый игрок выигрывает количество очков, равное разности между цифрами. Если разность отрицательна, то выигрывает второй игрок. Если разность нулевая, то игра заканчивается вничью. Составить платёжную матрицу и найти цену игры.
Решение. У игрока А есть 3 стратегии:
У игрока В также есть три стратегии:
Данная игра является парной игрой с противоположными интересами (антагонистической), следовательно, для её формального описания достаточно задать платёжную матрицу первого игрока.
Вычислим возможные выигрыши первого игрока:
Тогда платёжная матрица первого игрока примет вид:
Найдём оптимальную стратегию первого игрока. Для этого найдём минимальный выигрыш при каждой его стратегии (минимальный элемент в каждой строке):
Найдём нижнюю цену игры (выберем из минимальных элементов наибольший):
Таким образом, оптимальная стратегия первого игрока:
Найдём оптимальную стратегию второго игрока. Для этого найдём максимальный выигрыш первого игрока при каждой стратегии второго игрока (максимальный элемент в каждом столбце):
Найдём верхнюю цену игры (выберем из максимальных элементов наименьший):
Таким образом, оптимальная стратегия второго игрока:
Отклонение первого игрока от оптимальной стратегии уменьшает его выигрыш. Отклонение второго игрока от оптимальной стратегии увеличивает его проигрыш.
Каждый игрок должен стремиться не вообще к ситуации, в которой значение
функции выигрыша
максимально или минимально, а прежде всего к такой ситуации, которая может сложиться в процессе игры. Чтобы ситуация могла быть осуществимой, в ней одновременно должны достигаться приемлемые результаты как для игрока I, так и для игрока II. Ситуации, обладающие этим свойством, называются ситуациями равновесия
. Именно они могут складываться в результате разумного выбора игроками своих стратегий. При выявлении ситуации равновесия
необходимо прежде всего проанализировать последовательно каждую стратегию игрока I с точки зрения наиболее неблагоприятного для него исхода при выборе игроком II одной из своих стратегий. Для этого в - строке матрицы отыскивается минимальное значение
выигрыша. Обозначим его 
, где знаком ( минимум
по ) обозначена операция отыскания минимального из значений функции выигрыша
при всех возможных .
Числа , которые записаны рядом с матрицей в виде добавочного столбца, характеризуют минимальные выигрыши игрока I с учетом разумных действий игрока II. Поэтому игрок I должен выбрать свою стратегию так, чтобы максимизировать свой минимальный выигрыш, то есть он должен остановиться на той стратегии, для которой число является максимальным. Обозначим максимальное значение через , то есть
Величина называется нижним значением игры или максимином , а соответствующая ей стратегия игрока I – максиминной стратегией .
максиминной стратегии игрок I обеспечивает себе (независимо от поведения противника) гарантированный выигрыш не менее .
Далее проанализируем каждую стратегию игрока II с точки зрения наиболее неблагоприятного для него исхода при выборе игроком I одной из своих стратегий. В результате этого найдем максимальные значения проигрыша, которые обозначим
,
где знаком ( максимум по ) обозначено максимальное значение функции выигрыша при всех возможных .
Числа , которые записаны под матрицей в виде добавочной строки, характеризуют максимальные проигрыши игрока II с учетом разумных действий игрока I. Поэтому игрок II должен выбрать свою стратегию так, чтобы минимизировать свой максимальный проигрыш. Для этого он должен остановиться на той стратегии, при которой число будет минимальным. Обозначим минимальное значение через , то есть
Величина называется верхним значением игры или минимаксом , а соответствующая ей стратегия игрока II – минимаксной стратегией .
Очевидно, что при выборе наиболее осторожной минимаксной стратегии игрок II не дает возможности ни при каких обстоятельствах игроку I выиграть больше, чем .
Следовательно, если оба игрока ведут себя разумно, то выигрыш игрока I должен быть не меньше, чем максимин , и не больше, чем минимакс , то есть:
Необходимым и достаточным условием выполнения равенства 7.2. является существование седловой точки. матрицы. Термин " седловая точка " заимствован из геометрии. Однако наличие седловой точки в геометрии рассматривается в локальном, а в теории игр – в глобальном плане. То есть, декларируется существование пары целых чисел , для которых оказывается одновременно минимумом своей строки и максимумом своего столбца. Поэтому игрок I, применяя максиминную стратегию , гарантирует себе выигрыш , а игрок II, применяя минимаксную стратегию , не дает ему выиграть больше, чем .
Следовательно, для игрока I лучше всего выбирать стратегию , а для игрока II - . Согласно этому стратегии и называются оптимальными, а гарантированный выигрыш игрока I – значением игры , которое обозначают через .
Совокупность оптимальных стратегий называется решением игры .
Принцип оптимальности, лежащий в основе выбора игроками своих стратегий, называется принципом минимакса . В соответствии с этим принципом (или минимаксным критерием разумности поведения ) каждый способ действия оценивается по наихудшему для него исходу и оптимальным является способ, приводящий к наилучшему из наихудших результатов.
Рассмотрим матрицу игры.
Так, матрица
имеет седловую точку 
, так как цифра 7 является минимумом второй строки и максимумом первого столбца. Следовательно, оптимальной стратегией игрока I является максиминная , а игрока II – минимаксная . Значение игры
.
Выбрав свою оптимальную стратегию, игрок I может быть уверен, что он получит по меньшей мере 7, а игрок II, выбрав свою оптимальную стратегию, не допустит, чтобы игрок I получил больше 7. Эти стратегии и составляют решение игры с седловой точкой.
Решение игры с седловой точкой обладает таким свойством: если игроки придерживаются своих оптимальных стратегий, то выигрыш равен значению игры. Если один из игроков придерживается своей оптимальной стратегии, а другой отклоняется от нее, то он только теряет в игре и ни в коем случае не может увеличить свой выигрыш. При этом наличие у любого игрока сведений о том, что другой избрал свою оптимальную стратегию, не служит основанием для выбора какой-либо иной, кроме оптимальной (минимаксной или максиминной ), стратегии. Пара оптимальных стратегий в игре с седловой точкой создает ситуацию равновесия, и любое отклонение от оптимальной стратегии приводит игрока, применяющего неоптимальную стратегию, к невыгодным последствиям. Так, для рассматриваемой игры наличие информации у игрока о том, что игрок I выбрал оптимальную стратегию , не влияет на выбор им своей оптимальной стратегии . В противном случае игрок II даст возможность игроку I выиграть 9 вместо 7.
Рассмотрим с этих позиций игру со следующей платёжной матрицей:
Рассмотрим рассуждения, которыми руководствуется первый игрок. Если он сделает ход i=1, то наихудшей для него будет ситуация, когда второй игрок сделает ход j=3, так как в этом случае он получит 0. Если первый игрок сделает ход i=2, то в наихудшем случае (при ходе второго игрока j=1) он также получит 0. Аналогично, при i=3 он в наихудшем случае получит 4 (при j=2), при i=4 - 2 (при j=3) и, наконец, при i=5 он в наихудшем случае получит 0 (при j=3).
Стремясь сделать свой гарантированный выигрыш как можно больше, первый игрок должен выбрать ход i=3, так как в этом случае он гарантирует себе выигрыш, равный 4 (правда, и его максимальный выигрыш невелик - всего 5).
А теперь попробуем посмотреть на эту же матрицу с точки зрения второго игрока. Для него это –- матрица его проигрыша.
Если он выберет ход j=1, то его максимальный проигрыш будет равен 18 (если первый игрок сделает ход i=1). Аналогично, при j=2 его максимальный проигрыш будет равен 4, при j=3- – 8, и, наконец, при j=4 его максимальный проигрыш будет равен 25. Стремясь сделать свой максимальный проигрыш как можно меньше, второй игрок должен выбрать ход j=2, так как в этом случае его максимальный проигрыш, равный 4, самый маленький.
Итак, мы пришли к выводу, что первый игрок должен ходить i=3, а второй j=2. Допустим теперь, что второй игрок, как говорят, «открывает карты» и заявляет первому игроку: «Я буду делать ход j=2». Есть ли первому игроку необходимость менять свой ход? Нет, так как в этом случае его наилучший ход всё равно i=3.
Аналогично, если первый игрок заявит второму, что он будет ходить i=3, то второму игроку также нет смысла менять свой ход, так как наилучшим ответом будет всё равно j=2. Пара i=3, j=2 является, как говорят, уравновешенной парой, так как «открытие карт» игроками не даёт поводов противнику менять свою стратегию. Как говорят, пара i=3, j=2 есть решение игры, а величинавыигрыша при этом первого игрока (и одновременно величина проигрыша второго) - 4 – это цена игры .
Оформим всё это математически. Итак, пусть первый игрок выбирает ход i . В наихудшей для него ситуации он выиграет:
Стремясь сделать свой минимальный выигрыш максимальным, он выбирает свой ход из условия:
.
Такая стратегия называется максиминной , а величина α называется нижней ценой игры , или максимином .
Аналогично, второй игрок, выбирая ход j , в наихудшей для себя ситуации проигрывает:
Стремясь сделать свой максимальный проигрыш минимальным, он должен выбирать свой ход из условия:
Такая стратегия называется минимаксной , а величина β называется верхней ценой игры , или минимаксом .
Цена игры v всегда лежит между нижней ценой игры α и верхней ценой игры β .
Существуют игры, для которых нижняя цена игры равна верхней:
Эти игры занимают особое положение в теории игр и называются играми с седловой точкой. Общее обозначение нижней и верхней цены игры:
называется чистой ценой игры .
Седловая точка матрицы – элемент, который минимален в своей строке, но максимален в своём столбце. Это позволяет легко находить седловые точки матрицы.
Точка i =3, j =2, является седловой точкой. Элемент платежной матрицы a 32 =4 характеризовался именно тем свойством, что он был максимальным в своём столбце и минимальным в своей строке.
Некоторые вопросы, касающиеся седловых точек.
1. У матрицы быть несколько седловых точек, например у матрицы:
две седловых точки (i =1, j =1) и (i =1, j =3).
2. Не все матрицы имеют седловую точку, например у матрицы седловых точек нет.
Рассмотрим конечную бескоалиционную игру с двумя участниками. Игрок А имеет m стратегий, игрок В – n стратегий. Выбор игроком А стратегии с номером I , а игроком В стратегии с номером j – определяет исход игры. Ни один из игроков не знает выбора противника. Игрок А получает в качестве выигрыша сумму а ij , а игрок В – сумму b ij . Такая игра называется игрой двух лиц в нормальной форме .
Игра двух лиц с матрицами выигрыша а ij и b ij называется антагонистической (или игрой с нулевой суммой), если а ij + b ij = 0 при любой стратегии I игрока А и любой стратегии j игрока В. Антагонистическая игра описывается одной матрицей (платежной или выигрышей).
Теория антагонистических игр разработана наиболее детально. Ее математический аппарат связан с таким разделом математики, как линейное программирование.
В теоретико-множественной форме антагонистическая матричная игра записывается в виде
Н = { A, B, H(m,n)}, (1)
где A = {a 1 ,a 2 ,…a m } - множество стратегий игрока А;
В = {b 1 ,b 2 ,…b n } - множество стратегий игрока B;
H(m,n) – платежная матрица или матрица выигрышей, размерностью m х n.
Любой элемент матрицы Н – (a ij) – численно показывает величину выигрыша игрока А, если он примет стратегию i, и соответственно, величину проигрыша игрока В, если он примет стратегию j.
Решить игру (1) означает вычислить пару стратегий (a i ,b j) , которая наилучшим образом удовлетворяла бы интересы обоих игроков.
Наиболее простым случаем матричной антагонистической игры является. вполне определенная игра(ига с седловой точкой).
Вполне определенной игрой или игрой с седловой точкой называется игра, у которой совпадают нижняя и верхняя цены игры, то есть выполняется равенство:
a = max min а ij = min max a ij = b .
i j j i
При этом величина V = a = b называется ценой игры , элемент а ij соответствующий равенству, называют седловой точкой.
Простота решения игры с седловой точкой заключается в том, что оптимальные стратегии (в этом случае их называют чистыми стратегиями ) обоих игроков получаются сразу. Для примера 1 α = β = 6 , т.е цена игры V = 6 у.е., а элемент матрицы Н, находящийся на пересечении строки 2 (стратегия А 2) и столбца 2 (стратегия В 2) – седловая точка игры.
Седловая точка всегда является минимальным элементом соответствующей строки и максимальным элементом соответствующего столбца. Эта точка есть точка равновесия игры, однозначно определяющая чистые оптимальные стратегии.
Такое решение обладает свойством устойчивости в том смысле, что если один из игроков применяет свою оптимальную стратегию, то любое отклонение другого игрока от оптимальной стратегии может оказаться не выгодным для него.
Седловых точек к матрице может быть несколько. Между тем значение цены игры всегда единственное.
Стратегии игроков, подразумевающие разумность действий противников в достижении поставленных целей, получили в теории игр название принципа гарантированного результата, или принципа максимина.
Решением игры в примере 1 является выбор стратегии А 2 игроком А и В 2 игроком В, при этом цена игры V = 6.
Рассмотрим общие принципы решения игр двух лиц с нулевой суммой. На основании принципа разумности рекомендуется выбирать в качестве наилучшей стратегии ту, которая обеспечивает наибольший гарантированный выигрыш (то есть выигрыш, не зависящий от действий противника, выигрыш, который противник никоим образом не может уменьшить). Пусть игра определяется матрицей: . Игрок A
имеет m чистых стратегий A i
, а игрок B
– n
чистых стратегий B j
, 
. Паре стратегий
(A i , B j ) соответствует платеж C ij , выплачиваемый игроком B игроку A в конце игры, то есть выигрыш игрока A .
Если игрок A
использует стратегию A i
, то он получит выигрыш, по крайней мере равный , где минимум берется по всем стратегиям игрока B
. И так как игрок A
свободен в выборе своей стратегии, то для него естественно стремится к тому, чтобы сделать возможно большим; то есть стремится выбрать такую стратегию A i
0 ,
чтобы получить выигрыш не меньше, чем 
, где максимум берется по всем стратегиям игрока A
.
Стратегия A i 0 называется максиминной стратегией игрока A . Это его наиболее осторожная стратегия, применение которой при любом поведении игрока B гарантирует игроку A выигрыш C ij не менее α . Величина α называется нижней ценой игры или максимином.
Игрок B, рассуждая таким же образом, выбирает стратегию B j
0 , при которой игрок A
получит выигрыш не более чем 
. Стратегия B j
0 называется минимаксной стратегией игрока B
. Это его наиболее осторожная стратегия, применение которой дает гарантию игроку B
в том, что игрок A
при любом своем поведении получает выигрыш не более чем . Величина называется верхней ценой игры
или минимаксом.
Таким образом, при наиболее острожной игре игрок A должен применить максиминную, а игрок B минимаксную стратегии.
Принцип осторожности, которой диктует игрокам выбор таких стратегий называется принципом минимакса, а обе стратегии обобщенно минимаксными.
В каком же отношении находятся верхняя и нижняя цены игр. Можно показать, что для этих величин всегда справедливо неравенство
То есть нижняя цена игры всегда не больше верхней α ≤ β.
Если нижняя цена игры равна верхней, то есть если α = β , то те значения i 0, j 0 при которых это равенство достигается указывают оптимальные стратегии игроков A i 0 и B j 0 . В этом случае игрок A придерживаясь своей максиминной стратегии получает не менее чем v , а игрок B придерживаясь своей минимаксной стратегии помешает игроку A получить больше чем v .
Всякое отклонение от оптимальных стратегий невыгодно обоим игрокам, так как для любых стратегий A i и B j справедливы неравенства:
C i , j 0 ≤ C i 0, j 0 ≤ C i 0, j .
Элемент C i 0, j 0 называется седловой точкой матрицы C . Это название соответствует тому, что элемент C i 0, j 0 матрицы C является одновременно минимальным в своей строке и максимальным в своем столбце.
Этот элемент C i 0, j 0 = v называется ценой игры, а сама игра называется игрой с седловой точкой.
Пример. Рассмотрим игру с платежной матрицей.
