Элементы теории матричных игр

⇐ ПредыдущаяСтр 6 из 6

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

Игра определяется следующим образом.

1. Имеется n конфликтующих сторон (игроков), принимающих решения.

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

3. Существует определенный набор состояний, которыми заканчивается игра.

4. Заранее известны всем игрокам выигрыши, соответствующие каждому возможному конечному состоянию.

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

Будем нумеровать стратегии первого игрока индексами i=1, 2, …, m, второго игрока индексами k=1, 2, …, n.

Оптимальной стратегией игрока называется такая, которая обеспечивает ему максимальный выигрыш в данной игре. Задача теории игр – выявление оптимальных стратегий игроков.

Рассмотрим одноразовую реализацию игры, в которой результат определяется после двух ходов игроков. Первый игрок выбирает i-ю стратегию, второй игрок k-ю стратегию, причем выбор стратегий производится при отсутствии информации о выборе другого игрока.

Результат игры характеризуется величиной выигрыша a_ik. Всевозможные результаты игры a_ik образуют матрицу , называемую платежной матрицей. Положительные элементы a_ik > 0 определяют выигрыши первого игрока, отрицательные элементы a_ik < 0 – выигрыши второго игрока.

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

Величина α называется нижней ценой игры. Нижняя цена игры является гарантированным выигрышем первого игрока при любой стратегии второго игрока. Аналогично, второй игрок будет стремиться выбрать такую стратегию k, , при которой его наибольший проигрыш β был бы минимальным. Такая величина β называется верхней ценой игры

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

Всегда имеет место равенство α β .

Если α =β =ν , то величина ν называется чистой ценой игры. Она определяет выигрыш первого игрока и проигрыш второго при выборе ими оптимальных стратегий.

Цена игры ν совпадает с некоторым элементом a_sl, который одновременно является минимальным в своей строке и максимальным в своем столбце. Такой элемент называется седловой точкой. Седловая точка определяет оптимальные стратегии игроков.

Рассмотрим задачу.

Две транспортные компании X и Y осуществляют перевозки грузов. Компания X рекламирует свою деятельность на радио (стратегия х1), телевидении (х2) и в газетах (х3). Компания Y, в дополнение к использованию радио (стратегия у1), телевидения (у2), и газет (у3), может рассылать также по почте брошюры (у4). В зависимости от качества и интенсивности проведения рекламной компании, каждая из компаний может привлечь на свою сторону часть клиентов конкурирующей компании. Платежная матрица А характеризует процент клиентов, привлеченных или потерянных компанией X:

Столбцы матрицы А соответствуют стратегиям y₁, y₂, y₃, y₄ компании Y, а строки–стратегиям x₁, x₂, x₃ компании X. Решение задачи основано на обеспечении наилучшего результата из наихудших для каждого игрока.

Определим нижнюю цену игры α . Для этого в каждой строке найдем наименьшие элементы

и среди них выберем наибольший (максимин)

Для определения верхней цены игры в каждом столбце выберем наибольший элемент

Верхняя цена β определяется как наименьший элемент из выбранных (минимакс)

В нашем случае α =β =a₂₂=5. Элемент а₂₂является седловым.

Следовательно, оптимальной для компании X является стратегия х₂, а для компании Y – стратегия y₂, обеим компаниям следует проводить рекламу на телевидении. При этом выигрыш будет в пользу компании Х, ее рынок увеличится на 5%. В этом случае цена игры равна 5%.

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

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

Пусть смешанная стратегия состоит в применении первым игроком чистых стратегий с относительными частотами р₁ и р₂, а вторым игроком – чистых стратегий с относительными частотами q₁, q₂, …, q_n_. Считается, что стратегии образуют полный набор, то есть

p₁+p₂=1

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

z_k=p₁a_1k+p₂a_2k=p₁a_1k+(1-p₁)a_2k=(a_1k-a_2k)p₁+a_2k, k=1, 2,.., n. (10.1)

Таким образом, ожидаемый выигрыш первого игрока при любой чистой стратегии (а, следовательно, и при смешанной) второго игрока является линейной функцией относительной частоты р₁ выбора первым игроком своей первой чистой стратегии.

Рассматриваемая задача заключается в том, что первый игрок должен определять значение р₁ так, чтобы максимизировать свой минимальный ожидаемый выигрыш, определяемый равенствами (10.1). Эта задача легко решается графически, путем построения прямых (10.1) соответствующих ожидаемым выигрышам первого игрока при различных чистых стратегиях второго игрока. Эти прямые образуют ломаную линию, определяющую минимальный гарантированный выигрыш первого игрока, независимо от действий второго игрока. Решением задачи будет точка ломаной с наибольшим значением z.

В качестве примера рассмотрим игру двух участников с нулевой суммой и платежной матрицей

Для определения нижней цены игры в каждой строке находим наименьшие элементы и выбираем среди них наибольший а₂₂=1. Следовательно, α =1 . Аналогично находим верхнюю цену игры. Для этого в каждом столбце ищем наибольший элемент

и выбираем среди них наименьший

Верхняя и нижняя цены игры не совпадают. Чтобы определить оптимальную смешанную стратегию первого игрока, представим его ожидаемые выигрыши для всех возможных стратегий второго игрока в виде (10.1)

;

; (10.2)

Построим линии z=z(p₁), определяемые равенствами (10.2) на графике

р₁

Z₃

_{0, 5}

_{0, 1}

₀

₃

Рис. 10.1

Ломаная АВС определяет минимальный выигрыш первого игрока. При этом наибольшее значение z на ломанной достигается в точке В, соответствующей пересечению z₂ (p₁) и z₃(p₁). Определим координаты точки В. Для этого решаем систему

Отсюда ; .

Тогда p₂=1- = .

Таким образом, оптимальная смешанная стратегия первого игрока состоит в использовании первой стратегии с относительной частотой и второй стратегии с относительной частотой . При этом цена игры (выигрыш первого игрока) составит ν = .

Найдем оптимальную смешанную стратегию второго игрока. Для этого запишем систему равенств для ожидаемого проигрыша второго игрока в случае использования первым игроком своих чистых стратегий

L_k=q₁a₁+q₂a_k2+q₃a_k3+q₄a_k4_,

где q_i- относительная частота использования вторым игроком i-ой чистой стратегии.

Тогда получим систему

L₁=7q₁+3q₂-q₃+8q₄;

L₂=2q₁+q₂+6q₃+5q₄.

Учтем, что в оптимальном для игроков случае ожидаемый проигрыш второго игрока совпадает с ценой игры L₁=L₂=ν = .

Кроме того, ранее получено, что оптимальная стратегия реализуется в точке В, соответствующей применению вторым игроком второй и третьей стратегий. Следовательно, q₁=q₄=0.

Тогда система равенств примет вид

(10.3)

Отсюда находим q₂= ; q₃= .

Таким образом, оптимальная смешанная стратегия второго игрока состоит в использовании второй стратегии с относительной частотой q₂= и третьей стратегии с относительной частотой q₃= .

ЛИТЕРАТУРА

1. Волков И.К., Загоруйко Е.А. Исследование операций. М.: Изд. МГТУ им. Н.Э. Баумана, 2000.

2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М.: Высшая школа, 1980.

3. Таха Х. Введение в исследование операций М.: Изд. Дом Вильямс, 2001.

4. Ашманов С.А. Линейное программирование М.: Наука, 1981.

5. Вентцель Е.С. Исследование операций. М.: Высшая школа, 2001.

6. Акулич И.Л. Математическое программирование в примерах и задачах М.: Высшая школа, 1986.

7. Банди Б. Основы линейного программирования. М.: Радио и связь, 1989.

8. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. М.: Изд. «Дело», 2000.

9. Сборник задач по высшей математике для экономистов: Учебное пособие / Под ред. В.И. Ермакова. – М.: ИНФА – М, 2002. – 575 с.

10. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах. В 2-х ч. Ч.I: Учебное пособие для втузов. – 5-е изд., испр. – М.: Высш. шк., 1999. – 304 с.

⇐ Предыдущая 1 2 3 4 56