Методы и модели игры

ГРАФИЧЕСКОЕ РЕШЕНИЕ ИГР. Рассмотрим игру 2 x n, в которой игрок А имеет две стратегии.

Игра предполагает, что игрок А смешивает стратегии А₁ и А₂ с соответствующими вероятностями x₁ и 1 –х₁, 0 ≤ x₁ ≤ 1. Игрок В смешивает стратегии В₁, В₂,..., В_n с вероятностями у₁, у₂, ...,у_п, где y_j ≥ 0,j = 1, 2,..., и, y₁ + у₂ + …+ у_n = 1. В этом случае ожидаемый выигрыш игрока А, соответствующий j-й чистой стратегии игрока В, вычисляется в виде

Следовательно, игрок А ищет величину х₁, которая максимизирует минимум ожидаемых выигрышей

 

.

Пример 3.6-3

Рассмотрим следующую игру 2x4, в которой платежи выплачиваются игроку А.

 

	B1	B2	B3	B4
A1	2	2	3	–1
A2	4	3	2	6

 

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

 

Чистые стратегии игрока В	Ожидаемые выигрыши игрока А
1	–2x1 + 4
2	–x1 + 3
3	x1 + 2
4	–7x1 + 6

 

На рис. 14.6 изображены четыре прямые линии, соответствующие чистым стратегиям игрока В. Чтобы определить наилучший результат из наихудших, построения нижняя огибающая четырех указанных прямых (изображенная на рисунке толстыми линейными сегментами), которая представляет минимальный (наихудший) выигрыш для игрока А независимо от того, что делает игрок В. Максимум (наилучшее) нижней огибающей соответствует максиминному решению в точке х₁* = 0.5. Эта точка определяется пересечением прямых 3 и 4. Следовательно, оптимальным решением для игрока А является смешивание стратегий A₁ и A₂ вероятностями 0.5 и 0.5 соответственно. Соответствующая цена игры v определяется подстановкой х₁ = 0.5 уравнение либо прямой 3, либо 4, что приводит к следующему.

 

 

рис. 14.6

 

Оптимальная смешанная стратегия  игрока В определяется двумя стратегиями, которые определяют нижнюю огибающую графика. Это значит, что игрок В может смешивать стратегии B₃ и В₄, в этом случае у₁ = y₂ = 0 и у₄ = 1 – у₃. Следовательно, ожидаемые платежи игрока В, соответствующие чистым стратегиям игрока А, имеют следующий вид.

 

Чистые стратегии игрока В	Ожидаемые выигрыши игрока А
1	4ό3 – 1
2	–4ò3 + 6

 

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

 

.

 

Его решением будет у₃ = 7/8, что определяет цену игры v = 4 х (7/8) – 1 = 5/2.

Таким образом, решением игры для игрока А является смешивание стратегий А₁ и А₂ равными вероятностями 0.5 и 0.5, а для игрока В – смешивание стратегий В₃ и В₄ с вероятностями 7/8 и 1/8. (В действительности игра имеет альтернативное решение для игрока В, так как максиминная точка на рис. 14.6 определяется более чем двумя прямыми. Любая выпуклая линейная комбинация этих альтернативных решений также является решением задачи.)

 

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

Упражнения 3.6,b

1. Решите графически игру с  подбрасыванием монет из примера  3.6-2.

2. Робин часто путешествует между  двумя городами. При этом есть  возможность выбирать один из  двух маршрутов: маршрут А представляет собой скоростное шоссе в четыре полосы, маршрут В – длинную обдуваемую ветром дорогу. Патрулирование дорог осуществляется ограниченным числом полицейских. Если все полицейские расположены на одном маршруте, Робин с ее страстным желанием ездить очень быстро, несомненно, получит штраф в 100 долларов за превышение скорости. Если полицейские патрулируют на двух маршрутах в соотношении 50 на 50, то имеется 50%-ная вероятность, что Робин получит штраф в 100 долларов на маршруте А и 30%-ная вероятность, что она получит такой же штраф на маршруте В. Кроме того, маршрут В длиннее, поэтому бензина расходуется на 15 долларов больше, чем на маршруте А. Определите стратегию как для Робин, так и для полиции.

3. Решите графически следующие  игры, в которых платежи выплачиваются игроку А.

а)

 

	B1	B2	B3
A1	1	–3	7
A2	2	4	–6

 

b)

 

	B1	B2
A1	5	8
A2	6	5
A3	5	7

 

4. Дана следующая игра двух  лиц с нулевой суммой.

 

	B1	B2	B3
A1	5.0	50.0	50.0
A2	1.0	1.0	0.1
A3	10.0	1.0	10.0

 

a) Проверьте, что смешанные  стратегии с вероятностями (1/6, 0, 5/6) для игрока А и с вероятностями (49/54, 5/54, 0) для игрока В являются оптимальными, и определите цену игры.

b) Покажите, что цена  игры равна

 

.

 

решение матричных игр методами линейного  программирования. Теория игр находится в тесной связи с линейным программированием, так как любую конечную игру двух лиц с нулевой суммой можно представить в виде задачи линейного программирования и наоборот. Дж. Данциг [2] отмечает, что когда в 1947 году создатель теории игр Дж. фон Нейман впервые ознакомился с симплекс-методом, он сразу установил эта взаимосвязь и обратил особое внимание на концепцию двойственности в линейном программировании. Этот раздел иллюстрирует решение матричных игр методами линейного программирования.

Оптимальные значения вероятностей х_i, i = 1, 2,..., m, игрока А могут быть определены путем решения следующей максиминной задачи.

 

,

 

Чтобы сформулировать эту задачу в  виде задачи линейного программирования, положим

 

.

 

Отсюда вытекает, что

 

.

 

Следовательно, задача игрока А может быть записана в виде

 

Максимизировать z = v

при ограничениях

,

 

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

Оптимальные стратегии у₁, у₂, ...,у_n игрока В определяются путем решения задачи

 

 

 

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

 

Минимизировать w = v

при ограничениях

 

 

 

Две полученные задачи оптимизируют одну и ту же (не ограниченную в знаке) переменную v, которая является ценой игры. Причиной этого является то, что задача игрока В является двойственной к задаче игрока А (вам предлагается доказать это утверждение в упр. 3.5,с(6), используя определение двойственности). Это означает, что оптимальное решение одной из задач автоматически определяет оптимальное решение другой.

 

Пример 3.6-4

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

 

	B1	B2	B3	Минимумы строк
A1	3	–1	–3	–3
A2	–2	4	–1	–2
A3	–5	–6	2	–6
Максимумы столбцов	3	4	2

 

Значение цены игры v находится  между –2 и 2.

Задача линейного программирования для игрока А

Максимизировать z = v

при ограничениях

 

Оптимальным решением, полученным с помощью программы TORA, является  
x₁ = 0.3945, х₂ = 0.3119, х₃ = 0.2936 и v = – 0.9083.

Соответствующими двойственными  переменными являются y₁ = –0.3211, у₂ = –0.0826, у₃ = –0.5963. Причина того, что переменные у₁, у₂, у₃ не являются положительными, как это должно быть, заключается в том, что задача линейного программирования для игрока А является задачей максимизации с ограничениями вида "≥". При этих условиях, как известно, соответствующе двойственные переменные должны быть отрицательными. Чтобы убедиться в том, что причина именно в этом, преобразуем все ограничения вид "≥" в задаче линейного программирования для игрока А в ограничения вида "≤" путем умножения каждого неравенства на –1. Соответствующие двойственные переменные будут неотрицательными, как и требуется (см. упр. 3.6,с(1)). Действительно, построение двойственной задачи непосредственно из задачи линейного программирования для игрока А показывает (см. упр. 3.6,с(6)), что в двойственной задаче, являющейся соответствующей задачей линейного программирования для игрока В, Должны быть у_j ≤ 0, но в то же время требуется выполнение условия –y₁ – у₂ – ... – у_n = 1, что равносильно требованиям у_j ≥ 0 и y₁ + у₂ + ... + у_n = 1. К счастью, проблем, связанных со знаками, можно избежать преобразуя ограничения–неравенства вида "≥" в задаче линейного программирования для игрока А в ограничения–неравенства вида "≤".

 

Задача линейного программирования для игрока В

Минимизировать z = v

при ограничениях

Оптимальным решением, полученным с  помощью программы TORA, является  
у₁ = 0.3211, у₂ = 0.0826, уз = 0.5963 и v = –0.9083. Соответствующими двойственными переменными являются х₁ = –0.3945, х₂ = –0.3119, х₃ = –0.2936. Двойственные переменные отрицательны, ибо, подобно разобранной выше задаче для игрока А, в этом случае задача минимизации линейного программирования имеет ограничения–неравенства вида "≤". Приведение ограничений к виду "≥" исправит ситуацию со знаками.

Упражнений 3.6,с

1. Покажите в задаче из примера  3.6-4, что если ограничения–неравенства  задачи линейного программирования  для игрока А приведены к виду "≤", то аналогичные ограничения задачи для игрока В преобразуются в вид "≥" и двойственные переменные, полученные из одной или другой задачи, будут неотрицательными.

 

2. На загородном пикнике две  команды, по два человека в  каждой, играют в прятки. Есть  четыре места, где можно спрятаться (А, Б, В и Г), и два члена  прячущейся команды могут спрятаться каждый отдельно в любых двух из четырех мест. Затем другая команда имеет возможность проверить любые два места. Команда, которая ищет, получает премию, если будут обнаружены оба участника прячущейся команды, если же не обнаружен ни один участник, то она выплачивает премию. Иначе игра заканчивается вничью.