что такое седловая точка в теории игр

06. Принцип максимина в антагонистических играх. Седловая точка

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

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

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

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

Для пояснения принципа максимина рассмотрим пример 1 матричной игры G (4х5) с платежной матрицей, приведенной на рис. 2.2.

Какой стратегией игроку А воспользоваться? Есть соблазнительный выигрыш 12, при применении стратегии А3. Но при этом противник может выбрать стратегию В3, и игрок А получит выигрыш, равный всего трем.

Для определения оптимальной стратегии в соответствии с принципом максимина, запишем в правом добавочном столбце платежной матрицы минимальное значение AI в каждой строке (минимум строки). Из всех значений AI (правый столбец) выделим наибольшее. Ему соответствует стратегия А4. Выбрав эту стратегию, мы во всяком случае можем быть уверены, что при любом поведении противника выигрыш будет не менее пяти.

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

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

До тех пор, пока обе стороны в нашем примере будут придерживаться своих максиминных стратегий, выигрыш игрока А и проигрыш игрока В будет равен А43=5.

Легко показать, что нижняя цена игры никогда не превосходит верхней цены игры.

Лемма 1. Пусть задана матрица выигрышей

А = êêaijêêи определены b= и a= .

Тогда .

Доказательство. По определению максимума и минимума для любых фиксированных значений I и J имеем

(2.1)

Поскольку левая часть неравенства (2.1) не зависит от I, то можем записать

(2.2)

Так как правая часть неравенства (2.1) не зависит от J, то

(2.3)

Объединяя неравенства (2.2) и (2.3), получаем неравенство (2.1), что и требовалось доказать. Итак, всегда B³A.

Случай B=A, соответствует наличию у платежной матрицы так называемой Седловой точки.

Определение. Точка (I*, J*) называется седловой точкой платежной матрицы ||AIj||, если для всех остальных i и j этой матрицы выполняется условие

Т. е. Аij является одновременно минимумом своей строки и максимумом своего столбца.

Приведем без доказательства следующую теорему.

Теорема 1. Для того чтобы

(2.4)

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

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

Источник

Седловая точка. Чистая цена игры

Рассмотрим пример. Пусть дана матрица игры (4):

Решение. Из анализа дополнительных столбца и строки получаем: α = 5, β =5. Максимин равен минимаксу! Случай особый. Что же из этого следует?

Возьмем пару минимаксных стратегий: К₂ и С₃. Если оба держатся этих стратегий, то выигрыш будет равен 5. Теперь, допустим, мы узнали о поведении противника. Что будем делать? А ничего! Мы по-прежнему будем дер­жаться стратегии К₂, потому что любое отступ­ление от нее нам невыгодно. Знаем мы или не знаем о поведении противника — все равно будем держаться стратегии К₂! То же относится и к «синим» — им нет смысла менять свою стратегию С₃.

В данном примере пара стратегий К₂ и С₃ устойчива, т. е. представляет собой положение равновесия и дает решение игры.

Почему так получилось? Потому что в матрице имеется особый элемент 5; он является минимальным в своей строке и одновременно максимальным в своем столбце. Такой элемент называется седловой точкой. Если матри­ца имеет седловую точку (т. е. нижняя цена игры равна верхней), то игра имеет решение в чистых стратегиях: это — пара стратегий, пересекающихся в седловой точке. Сама же седловая точка дает цену игры — в нашем примере она равна 5.

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

Примерами игр с полной информацией мо­гут служить: шахматы, шашки, «крестики и нолики» и т. п.

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

Два игрока — К и С — поочередно кладут одинаковые монеты на круглый стол. Положение каждой монеты выбирается произвольно, лишь бы она не перекрывалась другими. Выигры­вает тот из игроков, который положит монету последним (когда места для других уже не остается).

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

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

Теоретически доказано, что решение су­ществует и исход шахматной игры в сущно­сти предрешен: если каждая сторона будет поль­зоваться своей оптимальной стратегией, то игра либо всегда будет кончаться выигрышем белых, либо всегда выигрышем черных, либо всегда ничьей! Но чем же именно? Мы пока этого не знаем, так как число возможных стра­тегий слишком велико, чтобы можно было построить матрицу шахматной игры и найти в ней седловую точку.

Наверное, любители шахмат заинтересованы в том, чтобы шахматная игра была решена еще не скоро.

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

Источник

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

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

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

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

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-ой стратегии со стороны А.

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

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

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

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

a₁₂ p * _1a + a₂₂ p * _2a = γ – против второй чистой стратегии стороны В.

a₂₁ p * _1b + a₂₂ p * _2b = γ – против второй чистой стратегии стороны В.

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

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

или

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

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

Источник

Матричные игры: примеры решения задач

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

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

Теперь обо всём по порядку и подробно.

Платёжная матрица, чистые стратегии, цена игры

В матричной игре её правила определяет платёжная матрица.

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

Составим платёжную матрицу:

.

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

.

Как происходит выбор стратегии в матричной игре?

Вновь посмотрим на платёжную матрицу:

.

Пример 1. Дана матричная игра с платёжной матрицей

.

Определить максиминную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.

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

Итак, гарантированный выигрыш первого игрока:

.

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

.

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

.

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

.

Ещё пример из этой же серии.

Пример 2. Дана матричная игра с платёжной матрицей

.

Определить максиминную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.

Седловая точка в матричных играх

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

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

В этом случае матричная игра имеет решение в чистых стратегиях.

Пример 3. Дана матричная игра с платёжной матрицей

.

Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку?

Решить задачу на матричную игру самостоятельно, а затем посмотреть решение

Пример 4. Дана матричная игра с платёжной матрицей

.

Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку?

Матричные игры с оптимальной смешанной стратегией

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

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

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

Если первый игрок использует чистые стратегии с вероятностями , то вектор называется смешанной стратегией первого игрока. Иначе говоря, это «смесь» чистых стратегий. При этом сумма этих вероятностей равна единице:

.

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

.

.

Если уже подзабыто произведение матриц, то следует повторить материал.

Пример 5. Дана матричная игра с платёжной матрицей

.

Определить математическое ожидание выигрыша первого игрока (проигрыша второго игрока), если смешанная стратегия первого игрока , а смешанная стратегия второго игрока .

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

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

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

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

,

.

В таком случае для функции E существует седловая точка, что означает равенство .

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

Сведение матричной игры к задаче линейного программирования

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

Функция цели в прямой задаче линейного программирования:

.

Система ограничений в прямой задаче линейного программирования:

Функция цели в двойственной задаче:

.

Система ограничений в двойственной задаче:

Оптимальный план прямой задачи линейного программирования обозначим

,

а оптимальный план двойственной задачи обозначим

Линейные формы для соответствующих оптимальных планов обозначим и ,

а находить их нужно как суммы соответствующих координат оптимальных планов.

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

,

.

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

,

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

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

,

,

Пример 6. Дана матричная игра с платёжной матрицей

.

Найти цену игры V и оптимальные смешанные стратегии и .

Решение. Составляем соответствующую данной матричной игре задачу линейного программирования:

Получаем решение прямой задачи:

.

Находим линейную форму оптимальных планов как сумму найденных координат:

.

Получаем решение двойственной задачи:

.

Находим линейную форму оптимальных планов как сумму найденных координат:

.

.

Находим оптимальную смешанную стратегию первого игрока:

.

Находим оптимальную смешанную стратегию второго игрока:

.

Игры с матрицей 2 Х 2

Пусть дана игра с платёжной матрицей

Если эта матричная игра имеет седловую точку, то она имеет решение в чистых стратегиях, как показано в параграфах 1 и 2.

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

Формула для нахождения оптимальной смешанной стратегии первого игрока:

.

Формула для нахождения оптимальной смешанной стратегии второго игрока:

.

Формула для нахождения цены игры:

.

Пример 7. Дана матричная игра с платёжной матрицей

.

Найти оптимальные смешанные стратегии игроков и цену игры.

Решение. Оптимальные смешанные стратегии первого игрока получаем по соответствующей из приведённых формул:

.

Оптимальные смешанные стратегии второго игрока получаем также по соответствующей формуле:

.

.

Составление матричной игры

Матричная игра, седловая точка, чистые стратегии, смешанные стратегии. А для чего всё это? Рассмотрим на примере, как с помощью матричных игр решаются экономические задачи.

Пример 8. Составить матричную игру для следующей задачи.

.

Далее составляется и решается задача линейного программирования. Это мы уже умеем.

Источник