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

 

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

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

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

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

.

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

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

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

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

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

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

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

 

или

 

 

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

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

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

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

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

				-1

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

Поскольку на графике в точке максимума пересеклись три прямых (y₂, y₃, y₄), то мы можем выбрать из них любую пару прямых с противоположными наклонами, например, (это означает, что у 2-го игрока имеется неединственная оптимальная стратегия). Если активными являются стратегии y₃ и y₄, то η*₁=η*₂=0. Для нахождения η*₃ и η*₄ построим новый график их двух прямых (см. рис. ниже), из которого определяем, что оптимальная стратегия 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).