Теория игр

Введение

«Теория игр - раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта...».

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

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

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

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

Целью теории игр является определение оптимальной стратегии для каждого игрока.

В настоящее время в теории игр известны несколько способов приближенного решения матричных игр. Рассмотрим графическое решение матричных игр.

1. Теоретическая часть

1.1 Смешанные стратегии в матричных играх

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

Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия x - это набор чисел x = (x1, ..., xm) удовлетворяющих соотношениям

xi >= 0 (i = 1,m), = 1.

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y - это набор чисел

y = (y1, ..., yn), yj >= 0, (j = 1,n), = 1.

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей

E (A, x, y) == x A yT

Первый игрок имеет целью за счёт изменения своих смешанных стратегий х максимально увеличить свой средний выигрыш Е (А, х, y), а второй - за счёт своих смешанных стратегий стремится сделать Е (А, х, y) минимальным, т.е. для решения игры необходимо найти такие х и y, при которых достигается верхняя цена игры

Е (А, х, y).

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть

Е (А, х, y).

Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборы хо, уо соответственно, которые удовлетворяют равенству

Е (А, х, y) = Е (А, х, y) = Е (А, хо, уо).

Величина Е (А, хо ,уо) называется при этом ценой игры и обозначается через u.

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

Е (А, х, уо)<= Е (А, хо, уо)<= Е (А, хо, у)

Оптимальные смешанные стратегии и цена игры называются решением матричной игры.

1.2 Свойства решений матричных игр

Обозначим через G (Х,Y,А) игру двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию х є Х, игрок 2 - y є U, после чего игрок 1 получает выигрыш А = А (х, y) за счёт игрока 2.

Определение. Стратегия х1 игрока 1 доминирует (строго доминирует) над стратегией х2, если

А (х^1, y)>= А (х^2, y)(А (х^1, y) > А (х^2, y)), y є U.

Стратегия y1 игрока 2 доминирует (строго доминирует) над стратегией y2, если

А (х, y^1)<= А (х, y^2)(А (х, y^1) < А (х, y^2)), х є Х.

При этом стратегии х2 и y2 называются доминируемыми (строго доминируемыми).

Спектром смешанной стратегии игрока в конечной антагонистической игре называется множество всех его чистых стратегий, вероятность которых согласно этой стратегии положительна.

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

Свойство 2. Ни одна строго доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.

Игра G' = (Х',Y',А') называется подыгрой игры G (Х,Y,А), если Х'c Х, U'c U, а матрица А' является подматрицей матрицы А. Матрица А' при этом строится следующим образом. В матрице А остаются строки и столбцы, соответствующие стратегиям Х' и U', а остальные “вычеркиваются”. Всё то что “останется” после этого в матрице А и будет матрицей А'.

Свойство 3. Пусть G = (Х,Y,А) - конечная антагонистическая игра, G' = (Х \ х',Y,А) - подыгра игры G, а х' - чистая стратегия игрока 1 в игре G, доминируемая некоторой стратегией , спектр которой не содержит х'. Тогда всякое решение (хо, yо, u) игры G' является решением игры G.

Свойство 4. Пусть G = (Х,Y,А) - конечная антагонистическая игра, G' = (Х,Y \ y',А) - подыгра игры G, а y' - чистая стратегия игрока 2 в игре G, доминируемая некоторой стратегией , спектр которой не содержит y'.Тогда всякое решение игры G' является решением G.

Свойство 5. Если для чистой стратегии х' игрока 1 выполнены условия свойства 3, а для чистой стратегии y' игрока 2 выполнены условия свойства 4, то всякое решение игры G' = (Х \ х',Y \ y',А) является решением игры G = (Х,Y,А).

Свойство 6. Тройка (хо, yо, u) является решением игры G = (Х,Y,А) тогда и только тогда, когда (хо, yо, кu +а) является решением игры G(Х,Y,кА+а), где а - любое вещественное число, к > 0.

Свойство 7. Для того, чтобы хо = () была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры u, необходимо и достаточно выполнение следующих неравенств

(j = )

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

(i = )

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

,

получим решение матричной игры.

Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (*) (**) и линейных уравнений (***). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например для матрицы 33 имеем систему из 6 неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства

=

Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок 1 - чистую максиминная, а игрок 2 - чистую минимаксная). В противном случае хотя бы у одного игрока оптимальные стратегии будут смешанные. Для матричных игр небольшого размера эти решения можно найти, применяя свойства 1 - 5.

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

1.3 Графический метод решения игр 2xn и mx2

Графический метод применим к тем играм, в которых хотя бы один из игроков имеет две стратегии.

Основные этапы нахождения решения игры 2?n или m?2:

1.Строят прямые, соответствующие стратегиям первого (второго) игрока.

2.Определяют нижнюю (верхнюю) границу выигрыша.

3.Находят две стратегии второго (первого) игрока, которым соответствуют две прямые, пересекающиеся в точке с максимальной (минимальной) ординатой.

4.Определяют цену игры и оптимальные стратегии.

Поясним метод на примераx.

Пример 1. Рассмотрим игру, заданную платёжной матрицей.

На плоскости xОy введём систему координат и на оси Оx отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (x, 1 - x). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1;0) - стратегия А2 и т.д.

В точкаx А1 и А2 восстановим перпендикуляр и на полученныx прямыx будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии А1, а на втором - при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1 игрока 2 - 2, при стратегии В2 - 3, а при стратегии В3 - 11. Числам 2, 3, 11 на оси 0x соответствуют точки В1, В2 и В3.

Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 - 5, а при В3 - 2. Эти числа определяют точки В'1, В2', В3' на перпендикуляре, восстановленном в точке А2.Соединяя между собой точки В1 и В'1, В2 и В'2, В3 и В'3 получим три прямые, расстояние до которыx от оси 0x определяет средний выигрыш при любом сочетании соответствующиx стратегий. Например, расстояние от любой точки отрезка В1В'1 до оси 0x определяет средний выигрыш u1 при любом сочетании стратегий А1 А2 (с частотами x и 1-x) и стратегией В1 игрока 2. Это расстояние равно

2x1 + 6(1 - x2) = u1

(Вспомните планиметрию и рассмотрите трапецию А1 B1 B'1 A2). Таким образом, ординаты точек, принадлежащиx ломанной В1 M N В'3 определяют минимальный выигрыш игрока 1 при применении им любыx смешанныx стратегий. Эта минимальная величина является максимальной в точке N; следовательно этой точке соответствует оптимальная стратегия Х* = (x, 1-x), а её ордината равна цене игры u. Координаты точки N наxодим как точку пересечения прямыx В2 B'2 и В3 B'3.

Соответствующие два уравнения имеют вид

.

Следовательно Х = (;), при цене игры u = . Таким образом мы можем найти оптимальную стратегию при помощи матрицы

Оптимальные стратегии для игрока 2 можно найти из системы

и, следовательно, Y = (0; ; ). (Из рисунка видно, что стратегия B1 не войдёт в оптимальную стратегию.

Пример 2. Найти решение игры, заданной матрицей

Решение. Матрица имеет размерность 2 x 4. Строим прямые, соответствующие стратегиям игрока 1. Ломанная А1 K А'4 соответствует верxней границе выигрыша игрока 1, а отрезок N K -цене игры. Решение игры таково

U = (;); Х = (; 0; 0; ); u = .

2. Практическая часть

Одно из транспортных предприятий, с учётом трёх возможных вариантов поведения конкурента (стратегии ) разработало две стратегии своей деятельности: . Прибыль предприятия в ситуации, когда оно выбирает свою стратегию , а конкурент - стратегию приведена в платёжной матрице:

.

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

Решение:

.

Покажем, что данная матричная игра не имеет седловой точки или не имеет решения в чистых стратегиях. Для этого найдём нижнюю и верхнюю цены игры:

.

Так как (68), то матричная не имеет Седловой точки или решения в чистых стратегиях. Цена игры при этом . Решение данной игры надо искать в смешанных стратегиях.

Применим графический способ.

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

Построим график нижней огибающей решения. Предварительно запишем уравнения прямых:

Построим эти прямые в системе координат .

Получили нижнюю огибающую решения - ломанную АМВ. Точка М является точкой максимума - она является точкой пересечения прямых и . Найдём её координаты:

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

Цена игры

Определим смешанные стратегии для игрока В. При этом . Для этого составим следующую систему:

Таким образом, оптимальная стратегия для игрока В:

Ответ: цена игры

Заключение

На практике часто приходится сталкиваться с задачами, в которых необходимо принимать решения в условиях неопределённости, т. е. возникают ситуации, в которых две (или более) стороны преследуют различные цели, а результаты любого действия каждой из сторон зависят от мероприятий партнёра. Такие ситуации, возникающие при игре в шахматы, шашки, домино и т. д., относятся к конфликтным: результат каждого хода игрока зависит от ответного хода противника, цель игры - выигрыш одного из партнёров. В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Во всех этих примерах конфликтная ситуация порождается различием интересов партнёров и стремлением каждого из них принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени.

Для грамотного решения задач с конфликтными ситуациями необходимы научно обоснованные методы. Такие методы разработаны математической теорией конфликтных ситуаций, которая носит название теория игр.

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

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

Список литературы

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

2. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения: Учеб. пособие. -М.: ИНФРА-М. 2003.

3. Вилкас Э.И. Оптимальность в играх и решениях. М.: «Наука», 1986

4.Красс М.С., Чупрынов Б.П. Математические методы и модели для экономистов. - СПб.: Питер, 2005.

5.Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика: математическое программирование. - Минск, 2001.

6.Кузнецов А.В. Экономико-математические методы и модели. Минск: БГЭУ,1999.

7.Конюховой П.В. Математические методы исследования операций в экономике. - СПб: Питер,2000.

8.Кремер Н.Ш., Путко Б.А. , Тришин И.М. , Фридман М.Н. Исследование операций в экономике. - Москва. 2003.

9.Морозов В.В., Старёв А.Г., Фёдоров В.В. Исследование операций в задачах и упражнениях. М.: «Высшая школа», 1996

10.Таха Х.А. Введение в исследование операций. - М.: Издательский дом «Вильямс», 2001.