Игры с седловой точкой в чистых стратегиях. Классификация игр

Рассмотрим конечную бескоалиционную игру с двумя участниками. Игрок А имеет 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.

Матричные игры и понятие седловой точки. Рассмотрим более подробно антагонистические игры и их основные свойства. Удобным способом задания игры двух участников с нулевой суммой является платежная матрица . Отсюда, кстати, происходит еще одно их название - матричные игры . Каждый элемент платежной матрицы а 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 игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения. Чем больше игроков - тем больше проблем.

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

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

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

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

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

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

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

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

Седловая точка – это пара чистых стратегий (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 в смешанных стратегиях.

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

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

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

Если подобрать такой набор Pia , который обеспечивает наибольший выигрыш независимо от действий второй стороны, то этот набор вероятностей {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 о , j о ) соответственно игроков 1 и 2, при которых достигается равенство=.Если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:, гдеi , j –любые чистые стратегии соответственно игроков 1 и 2;(i о , j о ) –стратегии, образующие седловую точку.

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

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

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

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 действия, применим графо-аналитический метод решения. Зададим игру в виде следующей матрицы:

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

Классификация игр. Определение седловой точки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а 11	а 12
а 21	а 22

A 11 p * 1 a + a 21 p * 2 a = γ - при игре против первой чистой стратегии стороны В.

a 12 p * 1 a + a 22 p * 2 a = γ – против второй чистой стратегии стороны В.

p * 1 a + p * 2 a = 1

Аналогично для В:

A 11 p * 1 b + a 12 p * 2 b = γ - при игре против первой чистой стратегии стороны В.

a 21 p * 1 b + a 22 p * 2 b = γ – против второй чистой стратегии стороны В.

p * 1 b + p * 2 b = 1

Решение системы уравнений:

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

Если выполняется либо одно, либо другое, то вероятности от 0 до 1.

Для стороны А: Для стороны В:

В задачах теории статистических решений рассматриваются платежные матрицы (для дискретного случая), либо платежная функция (в непрерывном случае). Значения в платеж. матрице, либо в платеж. функции зависят от 2х факторов: 1. состояние природы, 2. варианты решений ЛПР.

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

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

Геометрическая интерпретация.

е 11	е 12
е 21	е 22
…	…
e n 1	е n2

F i – состояние природы.

Е i – варианты решений.

Если отложить точки (e i 1 , e i 2), то они заполнят определенное пространство, ограниченное прямоугольником. РТ – рабочая точка. Внутри этого прямоугольника образовалось 4 квадранта или 4 конуса. Рассмторим свойства точек из этих конусов.

I: все точки хотя бы по одной координате лучше, чем рассматриваемая РТ. Поэтому конус I – конус предпочтения.

III: все точки хотя бы по одной координате заведомо хуже чем РТ.

II и IV: все точки по одной координате могут быть лучше, а по другой хуже. Поэтому эти конусы – конусы неопределенности.

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

Линия биссектрисы (линия 1) соответствует нейтральной критериальной функции. Линия 2 – пессимистическая критериальная функция. Линия 3 – оптимистическая критериальная функция.

Любая из линий 1, 2, 3 соединяет эквивалентные по предпочтению точки. Точки, расположенные правее и выше любой из этих линий предпочтительнее точек, лежащих левее и ниже.

Предельный случай для пессимистической функции – линии, ограничивающие I-ый квадрант. Для оптимистической – III-ий квадрант.