Седловая точка в теории игр. Вполне определенные игры (игры с седловой точкой)

Матричные игры и понятие седловой точки. Рассмотрим более подробно антагонистические игры и их основные свойства. Удобным способом задания игры двух участников с нулевой суммой является платежная матрица . Отсюда, кстати, происходит еще одно их название - матричные игры . Каждый элемент платежной матрицы а ij содержит числовое значение выигрыша игрока I (проигрыша игрока II), если первый применяет стратегию i , а второй - стратегию j . Термины выигрыш ипроигрыш следует понимать в широком смысле, т. к. они могут принимать отрицательные значения и с житейской точки зрения означать противоположное. Нетривиальность задачи прежде всего заключается в том, что каждый из игроков делает свой выбор, не зная о выборе другого, что существенно осложняет процесс оптимизации выбираемой стратегии.

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

Строки матрицы (6.1) соответствуют стратегиям игрока I, столбцы - стратегиям игрока II, а ее элементы - результатам первого игрока. Также из определения игры следует, что элементы данной матрицы, взятые с обратным знаком, соответствуют выигрышам второго игрока.

Более сложная и содержательная платежная матрица может быть получена, если несколько модифицировать предложенную игру. Допустим, что оба участника имеют право загадывать числа от 1 до 4, что составляет их соответствующие стратегии. В случае, если результат сложения задуманных чисел будет четным, то второй игрок выплачивает первому получившуюся сумму, а если нечетным, то первый - второму. Запишем платежную матрицу для такой игры:

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

Как уже отмечалось, важнейшим в теории игр является вопрос об оптимальности решения (выбора стратегии) для каждого из игроков. Проанализируем с этой точки зрения некоторую матричную игру, для которой задана платежная матрица А =║a ij ║ m xn . При выборе игроком I стратегии i его гарантированный доход независимо от действий игрока II составит min a i,j . Поскольку он может выбирать i самостоятельно, то целесообразно этот выбор сделать таким, чтобы он при любой стратегии противника максимизировал величину гарантированного дохода, т. е. обеспечивал получение max (min a i,j ). Такой принцип выбора стратегии получил название «принцип максимина ». С другой стороны, аналогичные рассуждения могут быть проведены по поводу действий второго игрока. Его наибольший проигрыш при выборе стратегии j составит max a i,j , и, следовательно, ему следует выбирать стратегию так, чтобы минимизировать величину проигрыша при любых действиях соперника, т. е. обеспечить min (max a i,j ). в этом суть принципа минимакса.

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

Однако очевидный интерес представляет ситуация, при которой значение выигрыша (платежа), получаемого игроком I при выборе им максиминной стратегии, равно платежу (проигрышу) II-го игрока при минимаксной стратегии

В этом случае говорят, что игра имеет седловую точку . Совпадение значений гарантированных выигрышей игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (стабильного, равновесного) состояния, от которого невыгодно отклоняться ни одному из участников. Понятие «оптимальность» здесь означает, что ни один разумный (осторожный) игрок не стремится изменить свою стратегию, так как его противник, в принципе, сможет выбрать такую стратегию, которая даст худший для первого результат. Стратегии i* и j *, образующие седловую точку, называются оптимальными , а значение v = a i*j* называют ценой игры . Тройка (i* , j* , v ) считается решением матричной игры с седловой точкой.

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

В данной матрице минимальные (гарантированные) выигрыши первого игрока по строкам равны 1, 5 и (-3). Следовательно, его максиминному выбору будет отвечать стратегия 2, гарантирующая выигрыш 5. Для второго игрока максимальные проигрыши по столбцам матрицы составят 8, 10, 5, 17, поэтому имеет смысл остановиться на стратегии 3, при которой он проиграет только 5. Таким образом, вторая стратегия первого игрока и третья стратегия второго образуют седловую точку со значением 5, т. е. для игры с матрицей (6.5) имеет решение (2; 3; 5).

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

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

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

По характеру взаимодействия игры делятся на:

бескоалиционные : игроки не имеют права вступать в соглашения, образовывать коалиции;

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

В кооперативных играх коалиции наперёд определены.

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

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

Определение . Если в игре с матрицей А=(нижняя чистая цена равна верхней чистой цене), то говорят, что эта игра имеетседловую точку в чистых стратегиях ичистую цену игры==.

Седловая точка –это пара чистых стратегий(i о , j о ) соответственно игроков 1 и 2, при которых достигается равенство=.Если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:, гдеi , j –любые чистые стратегии соответственно игроков 1 и 2;(i о , j о ) –стратегии, образующие седловую точку.

Таким образом, седловой элемент является минимальным вi о -й строке и максимальным вj о -м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждойстроке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своёмстолбце . Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий(i о , j о ) игроков 1 и 2, образующая седловую точку и седловой элемент, называетсярешением игры . При этомi о иj о называютсяоптимальными чистыми стратегиями соответственно игроков 1 и 2.

Свойства седловых точек:

1. Равноценность. Если в игре несколько седловых точек, то значения функции выигрыша в них одинаковы.

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

13.Определение смешанной стратегии. Решение игры 2*2 в смешанных стратегиях.

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

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

P ia – вероятность применения i-ой стратегии со стороны А.

Если подобрать такой набор P ia , который обеспечивает наибольший выигрыш независимо от действий второй стороны, то этот набор вероятностей {p 1 a , p 2 a , …, p ma } = S A и будет называться смешанной стратегией.

S * A = {p * 1 a , p * 2 a , …, p * ma } – оптимальная смешанная стратегия.

{ S A } – множество смешанных стратегий со стороны А, из которых нужно выбрать оптимальную.

Игра 2*2 в смешанных стратегиях.

Если хотя бы у одной стороны только 2 действия, применим графо-аналитический метод решения. Зададим игру в виде следующей матрицы:

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

Рассмотрим с этих позиций игру со следующей платёжной матрицей:

Рассмотрим рассуждения, которыми руководствуется первый игрок. Если он сделает ход 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. Не все матрицы имеют седловую точку, например у матрицы седловых точек нет.

Каждый игрок должен стремиться не вообще к ситуации, в которой значение функции выигрыша максимально или минимально, а прежде всего к такой ситуации, которая может сложиться в процессе игры. Чтобы ситуация могла быть осуществимой, в ней одновременно должны достигаться приемлемые результаты как для игрока 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.

Рассмотрим общие принципы решения игр двух лиц с нулевой суммой. На основании принципа разумности рекомендуется выбирать в качестве наилучшей стратегии ту, которая обеспечивает наибольший гарантированный выигрыш (то есть выигрыш, не зависящий от действий противника, выигрыш, который противник никоим образом не может уменьшить). Пусть игра определяется матрицей: . Игрок 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 называется ценой игры, а сама игра называется игрой с седловой точкой.

Пример. Рассмотрим игру с платежной матрицей.