Платежная матрица. Нижняя и верхняя цена игры

ПРАКТИЧЕСКАЯ РАБОТА №3

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

Понятие об игровых моделях

Теория игр занимается разработкой различного рода рекомендаций по принятию решений в условиях конфликтной ситуации. Формируя конфликтные ситуации математически, их можно представить как игру двух, трёх и более игроков, каждый из которых преследует цель максимизации своего выигрыша за счет другого игрока. Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте, – игроками, а исход конфликта – выигрышем. Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая:

1. варианты действий игроков;

2. объем информации каждого игрока о поведении партнеров;

3. выигрыш, к которому приводит каждая совокупность действий.

Как правило, выигрыш может быть задан количественно (например, проигрыш – 0, выигрыш – 1, ничья – ½). Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух. Игра называется игрой с нулевой суммой, если выигрыш одного из игроков равен проигрышу другого. Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход – сознательный выбор игроком одного из возможных действий (ход в шахматной игре), случайный ход – случайно выбранное действие (выбор карты из перетасованной колоды).

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

Для того, чтобы решить игру, или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получить максимальный выигрыш, когда второй придерживается своей стратегии. В то же время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными. Целью теории игр является определение оптимальной стратегии для каждого игрока. При выборе оптимальной стратегии естественно предполагать, что оба игрока ведут себя разумно с точки зрения своих интересов.

Платежная матрица. Нижняя и верхняя цена игры

Рассмотрим парную конечную игру. Пусть игрок А располагает m личными стратегиями, которые обозначим А₁, А₂,…,А_m. Пусть у игрока B имеется n личных стратегий, обозначим их B₁, B₂,…,B_n. Говорят, что игра имеет размерность m ´ n. В результате выбора игроками любой пары стратегий А_i и B_j однозначно определяется исход игры, т.е. выигрыш a_ij игрока А (положительный или отрицательный) и проигрыш (-a_ij) игрока В. Матрица Р=(a_ij), элементами которой являются выигрыши, соответствующие стратегиям А_i и B_j, называется платежной матрицей или матрицей игры.

Bj Ai	B1	B2	…	Bn
A1	a11	a12	…	a1n
A2	a21	a22	…	a2n
…	…	…	…	…
Am	am1	am2		amn

Пример – игра «Поиск»

Игрок А может спрятаться в убежище 1 – обозначим эту стратегию за А₁ или в убежище 2 – стратегия А₂. Игрок В может искать первого игрока в убежище 1 –стратегия В₁, либо в убежище 2 – стратегия В₂. Если игрок А находится в убежище 1 и его там обнаруживает игрок В, т.е. осуществляется пара стратегий (А₁,В₁), то игрок А платит штраф, т.е. a₁₁=–1. Аналогично получаем a₂₂=–1. Очевидно, что стратегии (А₁,В₂) и (А₂,В₁) дают игроку А выигрыш 1, поэтому a₁₂=a₂₁=1. Таким образом, получаем платежную матрицу

Рассмотрим игру m ´ n с матрицей Р=(a_ij) и определим наилучшую среди стратегий игрока А. Выбирая стратегию А_i, игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий В_j, для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А).

Обозначим через a_i наименьший выигрыш игрока А при выборе им стратегии А_i для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы), т.е. .

Среди всех чисел a_i выберем наибольшее: . Назовем a нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно, .

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

Среди всех чисел выберем наименьшее иназовем b верхней ценой игры, или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В при любой стратегии игрока А. Следовательно, .

Стратегия, соответствующая минимаксу, называется минимаксной стратегией. Принцип, диктующий игрокам выбор наиболее осторожных минимаксной и максиминной стратегий, называется принципом минимакса.

Статистические игры

Во многих задачах, приводящихся к игровым, неопределенность вызвана отсутствием информации об условиях, в которых осуществляется действие. Эти условия зависят не от сознательных действий другого игрока, а от объективной действительности, которую принято называть «природой». Такие игры называют играми с природой (статистическими играми).

Задача

После нескольких лет эксплуатации промышленное оборудование оказывается в одном из следующих состояний: В₁ – оборудование может использоваться в очередном году после профилактического ремонта; В₂ – для безаварийной работы оборудования в дальнейшем следует заменить отдельные его детали и узлы; В₃ – оборудование требует капитального ремонта или замены.

В зависимости от сложившейся ситуации В₁,В₂,В₃ руководство предприятия может принять такие решения: А₁– отремонтировать оборудование силами заводских специалистов, что требует соответствующих затрат а₁=6, а₂=10, а₃=15 ден.ед; А₂ – вызвать специальную бригаду ремонтников, расходы в этом случае составят b₁=15, b₂=9, b₃=18 ден.ед; А₃ – заменить оборудование новым, реализовав устаревшее оборудование по его остаточной стоимости. Совокупные затраты в результаты этого мероприятия будут равны соответственно с₁=13, с₂=24, с₃=12 ден.ед.

Задание

1. Придав описанной ситуации игровую схему, выявить ее участников, указать возможные чистые стратегии сторон.

2. Составить платежную матрицу, пояснив смысл элементов a_ij матрицы (почему они отрицательные?).

3. Выяснить, какое решение о работе оборудования в предстоящем году целесообразно рекомендовать руководству предприятия, чтобы минимизировать потери при следующих предположениях: а) накопленный на предприятии опыт эксплуатации аналогичного оборудования показывает, что вероятности указанных состояний оборудования равны соответственно q₁=0,15; q₂=0,55; q₃=0,3 (примените критерий Байеса); б) имеющийся опыт свидетельствует о том, что все три возможных состояния оборудования равновероятны (примените критерий Лапласа); в) о вероятности оборудования ничего определенного сказать нельзя (примените критерии Вальда, Сэвиджа, Гурвица). Значение параметра g=0,8 в критерии Гурвица задано.

Решение

1) Описанная ситуация представляет собой статистическую игру.

В качестве статистика выступает руководство предприятия, которое может принять одно из следующих решений: отремонтировать оборудование своими силами (стратегия А₁), вызвать ремонтников (стратегия А₂); заменить оборудование новым (стратегия А₃).

Второй играющей стороной – природой будем считать совокупность факторов, влияющих на состояние оборудования: оборудование может использоваться после профилактического ремонта (состояние В₁); нужно заменить отдельные узлы и детали оборудования (состояние В₂): потребуется капитальный ремонт или замена оборудования (состояние В₃).

2) Составим платежную матрицу игры:

Элемент платежной матрицы а_ij показывает затраты руководства предприятия, если при выбранной стратегии А_i оборудование окажется в состоянии В_j. Элементы платежной матрицы отрицательны, так как при любой выбранной стратегии руководству предприятия придется нести расходы.

3) Выясним, какое решение целесообразно рекомендовать руководству предприятия, чтобы минимизировать потери при следующих предположениях:

а) накопленный на предприятии опыт эксплуатации аналогично оборудования показывает, что вероятности состояний оборудования равны q₁=0,15; q₂=0,55; q₃=0,3.

Платежную матрицу представим в виде:

Стратегии статистика, Ai	Состояния природы Bj
B1	B2	B3
A1	-6	-10	-15	-10,9
A2	-15	-9	-18	-12,6
A3	-13	-24	-12	-18,75
qj	0,15	0,55	0,3

где , (i=1,3)

По критерию Байеса за оптимальную принимается та чистая стратегия А_i, при которой максимизируется средний выигрыш статистика, т.е. обеспечивается =max .

Оптимальной стратегией по Байесу является стратегия А₁.

б) имеющийся опыт свидетельствует о том, что все три возможных состояния оборудования равновероятны, т.е. = 1/3.

Средние выигрыши равны:

= 1/3*(-6-10-15) = -31/3 » -10,33;

= 1/3*(-15-9-18) = -42/3 = -14;

= 1/3*(-13-24-12) = -49/3 » -16,33.

Оптимальной стратегией по Лапласу является стратегия А₁.

в) о вероятностях оборудования нельзя сказать ничего определенного.

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

.

= max (-15, -18, -24) = -15.

Таким образом, оптимальной является стратегия А₁.

Построим матрицу рисков , где .

По критерию Сэвиджа оптимальной является стратегия А₁, для которой в наихудших условиях величина r риска принимает наименьшее значение

= min(3, 9, 15) = 3.

По критерию Гурвица, за оптимальную принимается та стратегия, для которой выполняется соотношение .

По условию задачи g = 0,8.

max (0,8*(-15;-18;-24) + 0,2*(-6;-9;-12)) = max (-13,2; -16,2; -21,6) = -13,2.

Таким образом, оптимальной является стратегия А₁.

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

Задания для самостоятельной работы

Параметры задачи	Варианты заданий
a1 a2 a3
b1 b2 b3
c1 c2 c3
q1 q2 q3	0,3 0,5 0,2	0,4 0,45 0,15	0,15 0,6 0,25	0,15 0,55 0,3	0,2 0,65 0,15	0,35 0,45 0,2	0,35 0,5 0,15	0,15 0,65 0,2	0,35 0,55 0,1	0,3 0,45 0,25	0,3 0,5 0,2	0,4 0,45 0,15	0,15 0,6 0,25	0,15 0,55 0,3	0,2 0,65 0,15	0,35 0,45 0,2	0,35 0,5 0,15	0,15 0,65 0,2	0,35 0,55 0,1	0,3 0,45 0,25
g	0,7	0,9	0,5	0,8	0,6	0,8	0,7	0,9	0,6	0,7	0,6	0,8	0,7	0,9	0,8	0,6	0,9	0,7	0,8	0,6