Если в игре каждый из противников применяет только одну и ту же стратегию, то про саму игру в этом случае говорят, что она происходит в чистых стратегиях , а используемые игроком А и игроком В пара стратегий называются чистыми стратегиями .
Определение. В антагонистической игре пара стратегий (А i , В j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.
Применять чистые стратегии имеет смысл тогда, когда игроки А и В располагают сведениями о действиях друг друга и достигнутых результатах. Если допустим, что хотя бы одна из сторон не знает о поведении противника, то идея равновесия нарушается, и игра ведется бессистемно.
Рассмотрим матричную игру G (3х4)
В этом примере нижняя цена игры равна верхней: ==9, т.е. игра имеет седловую точку.
Оказывается, что в этом случае максиминные стратегии А 2 и В 2 будут устойчивыми по отношению к информации о поведении противника.
Действительно, пусть игрок А узнал, что противник применяет стратегию В 2 . Но и в этом случае игрок А будет по-прежнему придерживаться стратегии А 2 , потому что любое отступление от стратегии А 2 только уменьшит выигрыш. Равным образом, информация, полученная игроком В , не заставит его отступить от своей стратегии В 2 .
Пара стратегий А 2 и В 2 обладает свойством устойчивости, а выигрыш (в рассматриваемом примере он равен 9), достигаемый при этой паре стратегий, оказывается седловой точкой платежной матрицы.
Признак устойчивости (равновесности) пары стратегии - это равенство нижней и верхней цены игры.
Стратегии А i и В j (в рассматриваемом примере А 2 , В 2), при котором выполняется равенство нижней и верхней цены игры, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях.
Величина называется ценой игры.
Если 0, то игра выгодна для игрока А, если 0 - для игрока В; при =0 игра справедлива, т.е. является одинаково выгодной для обоих участников.
Однако наличие седловой точки в игре - это далеко не правило, скорее - исключение. Большинство матричных игр, не имеет седловой точки, а следовательно, не имеет оптимальных чистых стратегий. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это - игры с полной информацией.
Теорема 2. Каждая игра с полной информацией имеет седловую точку, а следовательно, решается в чистых стратегиях, т.е. имеется пара оптимальных чистых стратегий, дающая устойчивый выигрыш, равный.
Если такая игра состоит только из личных ходов, то при применении каждым игроком своей оптимальной чистой стратегии она должна кончаться выигрышем, равным цене игры. Скажем, шахматная игра, как игра с полной информацией, либо всегда кончается выигрышем белых, либо всегда - выигрышем черных, либо всегда - ничьей (только чем именно - мы пока не знаем, так как число возможных стратегий в шахматной игре огромно).
Если матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.
Возникает вопрос: как найти решение игры, платежная матрица которой не имеет седловой точки? Применение максиминного принципа каждым из игроков обеспечивает игроку А выигрыш не менее, игроку - проигрыш не больше. Учитывая что, естественно для игрока А желание увеличить выигрыш, а для игрока В - уменьшить проигрыш. Поиск такого решения производит к необходимости применять смешанные стратегии: чередовать чистые стратегии с какими-то частотами.
Определение. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией .
Таким образом, задание смешанной стратегии игрока состоит в указании тех вероятностей, с которыми выбираются его чистые стратегии.
Будем обозначать смешанные стратегии игроков А и В соответственно
S A =||p 1 , p 2 , ..., p m ||,
S B =||q 1 , q 2 , ..., q n ||,
где p i - вероятность применения игроком А чистой с тратегии А і ; ; q j - вероятность применения игроком В чистой стратегии B j ; .
В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.
Применение смешанных стратегий осуществляется, например, таким образом: игра повторяется много раз, но в каждой партии игрок применяет различные чистые стратегии с относительными частотами их применения, равными p i и q j .
Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, какую чистую стратегию выберет противник в данной партии.
Если игрок А применяет смешанную стратегию S A =||p 1 , p 2 , ..., p m ||, а игрок В смешанную стратегию S B =||q 1 , q 2 , ..., q n ||, то средний выигрыш (математическое ожидание) игрока А определяется соотношением
Естественно, что ожидаемый проигрыш игрока В равен такой же величине.
Итак, если матричная игра не имеет седловой точки, то игрок должен использовать оптимальную смешанную стратегию, которая обеспечит максимальный выигрыш.
Естественно возникает вопрос: какими соображениями нужно руководствоваться при выборе смешанных стратегий? Оказывается принцип максимина сохраняет свое значение и в этом случае. Кроме того, важное значение для понимания решения игр, играют основные теоремы теории игр.
Различают
стратегии чистые и смешанные. Чистая
стратегия
первого игрока (чистая стратегия
второго игрока) – это возможный ход
первого (второго) игрока, выбранный им
с вероятностью, равной 1.
Если
первый игрок имеет m
стратегий, а второй – n
стратегий, то для любой пары стратегий
первого и второго игроков чистые
стратегии можно представить в виде
единичных векторов. Например, для пары
стратегий
,
чистые стратегии первого и второго
игроков запишутся в виде:
,
.
Для пары стратегий
,
чистые стратегии можно записать в виде:
,
.
Теорема
:
В матричной игре нижняя чистая цена
игры не превосходит верхней чистой цены
игры, т. е.
.
Определение:
Если для
чистых стратегий
,
игроковA
и В соответственно имеет место равенство
,
то пару чистых стратегий (
,
)
называют седловой точкой матричной
игры, элемент
матрицы, стоящий на пересеченииi-й
строки и j-го
столбца – седловым элементом платежной
матрицы, а число
- чистой ценой игры.
Пример: Найти нижнюю и верхнюю чистые цены, установить наличие седловых точек матричной игры
.
Определим
нижние и верхние чистые цены игры:
,
,
.
|
|
|||||
|
|
В
данном случае имеем одну седловую точку
(А 1 ;
В 2),
а седловой элемент равен 5. Этот элемент
является наименьшим в 1-й строке и
наибольшим во 2-м столбце. Отклонение
игрока А от максиминной стратегии А 1
ведет к уменьшению его выигрыша, а
отклонение игрока В от минимаксной
стратегии В 2
ведет к увеличению его проигрыша. Иными
словами, если в матричной игре имеется
седловой элемент, то наилучшими для
игроков являются их минимаксные
стратегии. И эти чистые стратегии,
образующие седловую точку и выделяющие
в матрице игры седловой элемент a 12 =5,
есть оптимальные чистые стратегии
и
соответственно игроков А и В.
Если
же матричная игра не имеет седловой
точки, то решение игры затрудняется. В
этих играх
.
Применение минимаксных стратегий в
таких играх приводит к тому, что для
каждого из игроков выигрыш не превышает
,
а проигрыш - не меньше
.
Для каждого игрока возникает вопрос
увеличения выигрыша (уменьшение
проигрыша). Решение находят, применяя
смешанные стратегии.
Определение:
Смешанной
стратегией первого (второго) игрока
называется вектор
,
где
и
(
,
где
и
).
Вектор p(q) означает вероятность применения i-й чистой стратегии первым игроком (j-й чистой стратегии вторым игроком).
Поскольку игроки выбирают свои чистые стратегии случайно и независимо друг от друга, игра имеет случайный характер и случайной становится величина выигрыша (проигрыша). В таком случае средняя величина выигрыша (проигрыша) – математическое ожидание – является функцией от смешанных стратегий р, q:
.
Определение:
Функция f(р,
q)
называется платежной функцией игры с
матрицей
.
Определение:
Стратегии
,
называются оптимальными, если для
произвольных стратегий
,
выполняется условие
Использование в игре оптимальных смешанных стратегий обеспечивает первому игроку выигрыш, не меньший, чем при использовании им любой другой стратегии р; второму игроку – проигрыш, не больший, чем при использовании им любой другой стратегии q.
Совокупность оптимальных стратегий и цены игры составляет решение игры.
теория игра стратегия смешанная
Смешанные стратегии
Если в матричной игре отсутствует седловая точка в чистых стратегиях, то находят верхнюю и нижнюю цены игры. Они показывают, что игрок 1 не получит выигрыша, превосходящего верхнюю цену игры, и что игроку 1 гарантирован выигрыш, не меньший нижней цены игры.
Смешанная стратегия игрока - это полный набор его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Подведем итоги сказанного и перечислим условия применения смешанных стратегий:
- * игра без седловой точки;
- * игроки используют случайную смесь чистых стратегий с заданными вероятностями;
- * игра многократно повторяется в сходных условиях;
- * при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;
- * допускается осреднение результатов игр.
Применяются следующие обозначения смешанных стратегий.
Для игрока 1 смешанная стратегия, заключающаяся в применении чистых стратегий А 1 , А 2 , ..., А т с соответствующими вероятностями р 1 , р 2, ..., р т.
Для игрока 2
q j -- вероятность применения чистой стратегии B j .
В случае когда р i = 1, для игрока 1 имеем чистую стратегию
Чистые стратегии игрока являются единственно возможными несовместными событиями. В матричной игре, зная матрицу А (она относится и к игроку 1, и к игроку 2), можно определить при заданных векторах и средний выигрыш (математическое ожидание эффекта) игрока 1:
где и - векторы;
p i и q i - компоненты векторов.
Путем применения своих смешанных стратегий игрок 1 стремится максимально увеличить свой средний выигрыш, а игрок 2 - довести этот эффект до минимально возможного значения. Игрок 1 стремится достигнуть
Игрок 2 добивается того, чтобы выполнялось условие
Обозначим и векторы, соответствующие оптимальным смешанным стратегиям игроков 1 и 2, т.е. такие векторы и, при которых будет выполнено равенство
Цена игры - средний выигрыш игрока 1 при использовании обоими игроками смешанных стратегий. Следовательно, решением матричной игры является:
- - оптимальная смешанная стратегия игрока 1;
- - оптимальная смешанная стратегия игрока 2;
Цена игры.
Смешанные стратегии будут оптимальными (и), если образуют седловую точку для функции т.е.
Существует основная теорема математических игр.
Для матричной игры с любой матрицей А величины
существуют и равны между собой: = = .
Следует отметить, что при выборе оптимальных стратегий игроку 1 всегда будет гарантирован средний выигрыш, не меньший чем цена игры, при любой фиксированной стратегии игрока 2 (и, наоборот, для игрока 2). Активными стратегиями игроков 1 и 2 называют стратегии, входящие в состав оптимальных смешанных стратегий соответствующих игроков с вероятностями, отличными от нуля. Значит, в состав оптимальных смешанных стратегий игроков могут входить не все априори заданные их стратегии.
Решить игру - означает найти цену игры и оптимальные стратегии. Рассмотрение методов нахождения оптимальных смешанных стратегий для матричных игр начнем с простейшей игры, описываемой матрицей 22. Игры с седловой точкой специально рассматриваться не будут. Если получена седловая точка, то это означает, что имеются невыгодные стратегии, от которых следует отказываться. При отсутствии седловой точки можно получить две оптимальные смешанные стратегии. Как уже отмечалось, эти смешанные стратегии записываются так:
Значит, имеется платежная матрица
a 11 p 1 + a 21 p 2 = ; (1.16)
a 12 p 1 + a 22 p 2 = ; (1.17)
p 1 + p 2 = 1. (1.18)
a 11 p 1 + a 21 (1 - p 1) = a 12 p 1 + a 22 (1 - p 1); (1.19)
a 11 p 1 + a 21 - a 21 p 1 = a 12 p 1 + a 22 - a 22 p 1 , (1.20)
откуда получаем оптимальные значенияи:
Зная и, находим:
Вычислив, находим и:
a 11 q 1 + a 12 q 2 = ; q 1 + q 2 = 1; (1.24)
a 11 q 1 + a 12 (1 - q 1) = . (1.25)
при a 11 a 12 . (1.26)
Задача решена, так как найдены векторы и цена игры. Имея матрицу платежей А, можно решить задачу графически. При этом методе алгоритм решения весьма прост (рис. 2.1).
- 1. По оси абсцисс откладывается отрезок единичной длины.
- 2. По оси ординат откладываются выигрыши при стратегии А 1 .
- 3. На линии, параллельной оси ординат, в точке 1 откладываются выигрыши при стратегии a 2 .
- 4. Концы отрезков обозначаются для a 11 -b 11 , a 12 -b 21 , a 22 -b 22 , a 21 -b 12 и проводятся две прямые линии b 11 b 12 и b 21 b 22 .
- 5. Определяется ордината точки пересечения с. Она равна. Абсцисса точки с равна р 2 (р 1 = 1 - р 2).
Рис. 1.1.
Данный метод имеет достаточно широкую область приложения. Это основано на общем свойстве игр тп, состоящем в том, что в любой игре тп каждый игрок имеет оптимальную смешанную стратегию, в которой число чистых стратегий не больше, чем min(m, n). Из этого свойства можно получить известное следствие: в любой игре 2п и т2 каждая оптимальная стратегия и содержит не более двух активных стратегий. Значит, любая игра 2п и т2 может быть сведена к игре 22. Следовательно, игры 2п и т2 можно решить графически. Если матрица конечной игры имеет размерность тп, где т > 2 и п > 2, то для определения оптимальных смешанных стратегий используется линейное программирование.
Математические методы и модели в экономике
Введение
В экономической практике часто возникают ситуации, в которых различные стороны преследуют различные цели. Например, отношения между продавцом и покупателем, поставщиком и потребителем, банком и вкладчиком и т.д. Такие конфликтные ситуации возникают не только в экономике, но в других видах деятельности. Например, при игре в шахматы, шашки, домино, лото и т.д.
Игра – это математическая модель конфликтной ситуации с участием не менее двух лиц, использующих несколько различных способов для достижения своих целей. Игра называется парной, если в ней участвуют два игрока. Игра называется антагонистической, если выигрыш одного игрока равен проигрышу другого. Следовательно, для задания игры достаточно задать величины выигрышей одного игрока в различных ситуациях.
Любой способ действия игрока в зависимости от сложившейся ситуации называется стратегией. Каждый игрок располагает определенным набором стратегий. Если число стратегий конечно, то игра называется конечной, в противном случае – бесконечной . Стратегии называются чистыми, если каждый из игроков выбирает только одну стратегию определенным, а не случайным образом.
Решение игры заключается в выборе такой стратегии, которая удовлетворяет условию оптимальности. Это условие состоит в том, что один игрок получает максимальный выигрыш , если второй придерживается своей стратегии. И наоборот, второй игрок получает минимальный проигрыш , если первый из игроков придерживается своей стратегии. Такие стратегии называются оптимальными . Таким образом, цель игры – это определение оптимальной стратегии для каждого игрока.
Игра в чистых стратегиях
Рассмотрим игру с двумя игроками А и В. Предположим, что игрок А имеет m стратегий А 1 , А 2 , …, А m , а игрок В имеет n стратегий B 1 , B 2 , … ,B n . Будем считать, что выбор игроком А стратегии А i , а игроком В стратегии B j однозначно определяет исход игры, т.е. выигрыш a ij игрока А и выигрыш b ij игрока В. Здесь i=1,2,…,m, j=1,2,…,n.
Простейшей игрой с двумя игроками является антагонистическая игра, т.е. игра, в которой интересы игроков прямо противоположны. В этом случае выигрыши игроков связаны равенством
b ij =-a ij
Это равенство означает, что выигрыш одного из игроков равен проигрышу другого. В этом случае достаточно рассматривать лишь выигрыши одного из игроков, например, игрока А.
Каждой паре стратегий А i и B j соответствует выигрыш a ij игрока А. Все эти выигрыши удобно записывать в виде так называемой платежной матрицы
Строки этой матрицы соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В. В общем случае такая игра называется (m×n)-игрой.
Пример 1. Два игрока А и В бросают монету. Если стороны монеты совпадают, то выигрывает А , т.е. игрок В платит игроку А некоторую сумму, равную 1, а если не совпадают, то выигрывает игрок В, т.е. наоборот, игрок А платит игроку В эту же сумму, равную 1. Сформировать платежную матрицу.
Решение. По условию задачи
