Геометрический метод решения игр



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

Геометрический метод решения игр



 

Геометрический метод позволяет найти приближенное решение игры с платежной матрицей размером (2×2), (2×n), (m×2). При наличии определенного пространственногои воображения можно также попытаться решить геометрически игру (3×3).

Решим вначале игру (2×2) с матрицей следующего вида:

 

Здесь , т.е. седловой точки игра не имеет.

Ожидаемые выигрыши 1-го игрока, применяющего смешанную стратегию ξ=(ξ1, ξ2), если 2-й игрок отвечает своими чистыми стратегиями y1 и y2 , равны:

.

Аналогично, ожидаемые проигрыши 2-го игрока, применяющего смешанную стратегию η=(η1, η2), если 1-й игрок отвечает своими чистыми стратегиями х1 и х2 , будут равны:

Видно, что функции линейно зависят от и . В соответствие с критерием оптимальности (максимин/минимакс) 1-й игрок должен выбирать так, чтобы максимизировать свой минимальный ожидаемый выигрыш, а 2-й игрок выбирать так, чтобы минимизировать свой максимальный проигрыш. Эта задача может быть решена графически, путем построения прямых линий, соответствующих линейным функциям L(ξ, yj ) и L(xi ,η).

Найдем геометрически вначале цену игры и оптимальную стратегию 1-го игрока. С этой целью на оси абсцисс выбирается отрезок длиной 1. Левый край отрезка будет соответствовать чистой стратегии 1-го игрока , правый – . Через начало и конец отрезка единичной длины проводятся две оси ординат, точки на которых будут соответствовать значениям выигрыша 1-го игрока, если 2-й игрок применяет свои чистые стратегии y1 и y2.

Тогда все множество смешанных стратегий 1-го игрока представляется точками, образующими прямую линию, которая соединяет крайние точки соответствующие чистым стратегиям. Например, если 1-й игрок применяет свою чистую стратегию х1 (ξ1 =1), то при стратегии 2-го игрока y1 платеж согласно уравнению , а при стратегии y2 - . Наоборот, если 1-й игрок применяет свою чистую стратегию х21 =0), то при стратегии 2-го игрока y1 платеж будет равен 3+2ξ1 =3, а при стратегии y2 – (4-3ξ1)=4. Соответствующие точки соединяем прямыми (y1 y1) и (y2 y2), поскольку средний платеж при смешанных стратегиях соответствует ординатам точек, расположенных на прямых, соединяющих указанные крайние точки.

В соответствие с принципом максимина/минимакса оптимальная стратегия 1-го игрока находится в точке максимума на нижней огибающей двух прямых. Из этой точки опускаем перпендикуляр на ось абсцисс. Высота перпендикуляра будет равна цене игры (ν ≈ 17/5). Расстояние от точки пересечения перпендикуляра с осью абсцисс до правого конца единичного отрезка будет равно ξ1* ( ≈1/5), а расстояние от точки пересечения перпендикуляра с осью абсцисс до левого конца единичного отрезка будет равно ξ2* ( ≈4/5).

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

Рассмотрим обе возможности. На существующем графике через точку максимина проведем прямую параллельную оси абсцисс (см. рис ниже).

 

или

 

 

Обозначим точки ее пересечения с осями ординат через M и N. Тогда η* =( η*1 , η*2) вычисляется по указанным выше формулам и приближенно равно (3/5, 2/5).

Более точное решение получается, если построить новый график для 2-го игрока по аналогичной схеме. Отличие состоит в том, что на графике строится верхняя огибающая ломаная линия, поскольку 2-й игрок стремится минимизировать свой максимальный проигрыш при стратегиях 1-го игрока х1 , х2 . Из точки минимума на верхней огибающей опускаем перпендикуляр на единичный отрезок оси абсцисс и определяем η* =( η*1 , η*2)≈(3/5, 2/5).

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

Отсюда следует, что игры вида (m×2) и (2×n) сводятся к решению игры (2×2).

Рассмотрим, например игру (2×4), в которой нет седловой точки, а платежная матрица имеет вид:

 
-1

Найдем вначале цену игры и оптимальную стратегию 1-го игрока. Из утверждения следует, что у 2-го игрока из четырех стратегий только две являются активными. Построим график, состоящий из 4-х прямых соответствующих смешанным стратегиям 1-го игрока, при условии, что 2-й игрок отвечает чистыми стратегиями y1 , y2 , y3 , y4 . Найдем на графике точку максимума на нижней огибающей (см. рис. ниже). Видно, что ν≈2.5, ξ*1 ≈1/2, ξ*2 ≈1/2.

Поскольку на графике в точке максимума пересеклись три прямых (y2 , y3 , y4), то мы можем выбрать из них любую пару прямых с противоположными наклонами, например, (это означает, что у 2-го игрока имеется неединственная оптимальная стратегия). Если активными являются стратегии y3 и y4, то η*1=η*2=0. Для нахождения η*3 и η*4 построим новый график их двух прямых (см. рис. ниже), из которого определяем, что оптимальная стратегия 2-го игрока η*=(0, 0, 7/8, 1/8). Подстановкой η* в выражение для ожидаемого проигрыша 2-го игрока можно проверить точность найденного решения, которое должно совпасть с ценой игры ν. Например, L(x1, η*)= 4·0+3·0+2·7/8+6·1/8=5/2. Аналогично можно рассмотреть комбинацию двух других прямых с противоположным наклоном (y2 , y3), которая дает другое оптимальное решения для 2-го игрока: η*=(0, 1/2, 0, 1/2). Любое средневзвешенное комбинаций прямых (y2 , y3) и (y3 , y4) также будет давать оптимальное решение, в которое отличной от 0 вероятностью будут входить стратегии y2, y3,y4 (проверить самостоятельно).

Аналогичным образом решается игра (m×2).

В трехмерном пространстве можно решать игры (m×3), (3×n), сводя их к игре (3×3).

 

 



Последнее изменение этой страницы: 2016-09-05; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.214.224.207 (0.01 с.)