Седловая точка в матричных играх
Если верхняя и нижняя цена игры одинаковая, то считается, что матричная игра имеет седловую точку. Верно и обратное утверждение: если матричная игра имеет седловую точку, то верхняя и нижняя цены матричной игры одинаковы. Соответствующий элемент одновременно является наименьшим в строке и наибольшим в столбце и равен цене игры.
Таким образом, если 
, то 
- оптимальная чистая стратегия первого игрока, а 
- оптимальная чистая стратегия второго игрока. То есть равные между собой нижняя и верхняя цены игры достигаются на одной и той же паре стратегий.
В этом случае матричная игра имеет решение в чистых стратегиях.
Пример 3. Дана матричная игра с платёжной матрицей
.
Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку?
Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы - наибольшие элементы в столбцах и выберем минимальный из них:
Нижняя цена игры совпадает с верхней ценой игры. Таким образом, цена игры равна 5. То есть 
. Цена игры равна значению седловой точки 
. Максиминная стратегия первого игрока - вторая чистая стратегия, а минимаксная стратегия второго игрока - третья чистая стратегия. Данная матричная игра имеет решение в чистых стратегиях.
Матричные игры с оптимальной смешанной стратегией
В большинстве случаев матричная игра не имеет седловой точки, поэтому соответствующая матричная игра не имеет решений в чистых стратегиях.
|
|
|
Но она имеет решение в оптимальных смешанных стратегиях. Для их нахождения нужно принять, что игра повторяется достаточное число раз, чтобы на основании опыта можно было предположить, какая стратегия является более предпочтительной. Поэтому решение связывается с понятием вероятности и среднего (математического ожидания). В окончательном же решении есть и аналог седловой точки (то есть равенства нижней и верхней цены игры), и аналог соответствующих им стратегий.
Итак, чтобы чтобы первый игрок получил максимальный средний выигрыш и чтобы средний проигрыш второго игрока был минимальным, чистые стратегии следует использовать с определённой вероятностью.
Если первый игрок использует чистые стратегии с вероятностями 
, то вектор 
называется смешанной стратегией первого игрока. Иначе говоря, это "смесь" чистых стратегий. При этом сумма этих вероятностей равна единице:
.
Если второй игрок использует чистые стратегии с вероятностями 
, то вектор 
называется смешанной стратегией второго игрока. При этом сумма этих вероятностей равна единице:
.
Если первый игрок использует смешанную стратегию p, а второй игрок - смешанную стратегию q, то имеет смысл математическое ожидание 
выигрыша первого игрока (проигрыша второго игрока). Чтобы его найти, нужно перемножить вектор смешанной стратении первого игрока (который будет матрицей из одной строки), платёжную матрицу и вектор смешанной стратегии второго игрока (который будет матрицей из одного столбца):
|
|
|
.
Пример 4. Дана матричная игра с платёжной матрицей
.
Определить математическое ожидание выигрыша первого игрока (проигрыша второго игрока), если смешанная стратегия первого игрока 
, а смешанная стратегия второго игрока 
.
Решение. Согласно формуле математического ожидания выигрыша первого игрока (проигрыша второго игрока) оно равно произведению вектора смешанной стратегии первого игрока, платёжной матрицы и вектора смешанной стратегии второго игрока:
Оптимальной смешанной стратегией первого игрока называется такая смешанная стратегия 
, которая обеспечивала бы ему максимальный средний выигрыш 
, если игра повторяется достаточное число раз.
Оптимальной смешанной стратегией второго игрока называется такая смешанная стратегия 
, которая обеспечивала бы ему минимальный средний проигрыш 
, если игра повторяется достаточное число раз.
|
|
|
По аналогии с обозначениями максимина и минимакса в случах чистых стратегий оптимальные смешанные стратегии обозначаются так (и увязываются с математическим ожиданием, то есть средним, выигрыша первого игрока и проигрыша второго игрока):
, 
.
В таком случае для функции E существует седловая точка, что означает равенство 
.
Игры с матрицей 2 Х 2
Аналитический метод. Пусть дана игра с платёжной матрицей
Если эта матричная игра имеет седловую точку, то она имеет решение в чистых стратегиях.
Если же игра не имеет седловой точки, то она имеет решение в оптимальных смешанных стратегиях. Для этого простейшего случая матричной игры при её решениях путём сведения к задаче линейного программирования были найдены формулы стратегий игроков и цены игры, благодаря которым такая игра решается менее трудоёмким способом.
Формула для нахождения оптимальной смешанной стратегии первого игрока:
.
Формула для нахождения оптимальной смешанной стратегии второго игрока:
.
Формула для нахождения цены игры:
Пример 5. Дана матричная игра с платёжной матрицей
.
Найти оптимальные смешанные стратегии игроков и цену игры аналитическим методом.
|
|
|
Решение. Оптимальные смешанные стратегии первого игрока получаем по соответствующей из приведённых формул:
.
Оптимальные смешанные стратегии второго игрока получаем также по соответствующей формуле:
.
Цена игры: 
.
Дата добавления: 2019-02-26; просмотров: 724; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!