Теория игр

В1 а21


М


В1

а11


х2 х11 Х

Рис.1. Подписать рисунок


Аналогично строится отрезок В2В2, соответствующий стратегии В2 игрока В.

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

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

В игре (2 ґ 2) обе стратегии являются активными.


В1 а21

В2

а12 К

В2 а22

В1

а11 v


О х2 N х1 1 Х

Рис.2.


Ломаная В1КВ2 является нижней границей выигрыша, получаемого игроком А. (см. рис.2) Точка К, в которой он максимален, определяет цену игры и ее решение. Найдем оптимальную стратегию первого игрока. Запишем систему уравнений


Теория игр


Приравнивая выражения для v из уравнений системы и учитывая, что


x1 + x2 = 1, получим Теория игр, Теория игр, (1)

Теория игр. (2)


Составляя аналогичную систему


Теория игр


и учитывая условие


y1 + y2 = 1,

можно найти оптимальную стратегию игрока В:

Теория игрТеория игр. (3)


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


Теория игр.


a = max (1,1) = 1, b = min (3,2) = 2, a № b, Теория игр. Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий. Построим на плоскости отрезки, соответствующие стратегиям второго игрока. (см. рис.3)


Рис.3.


По формулам (1) - (3) находим оптимальные стратегии и цену игры:


x1 = 1/3, x2 = 2/3; y1 = 2/3, y2 = 1/3; v =5/3.


Ответ. Оптимальные смешанные стратегии игроков Теория игр (1/3, 2/3) и Теория игр (2/3, 1/3), цена игры составляет v =5/3.

Данный ответ означает следующее:

если первый игрок с вероятностью 1/3 будет применять первую стратегию и с вероятностью 2/3 вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 5/3;

если второй игрок с вероятностью 2/3 будет применять первую стратегию и с вероятностью 1/3 вторую, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 5/3.

Второй случай. Рассмотрим игру (2 ґ n) с матрицей


Теория игр.


Для каждой из n стратегий игрока В строится соответствующий ей отрезок на плоскости. Находится нижняя граница выигрыша, получаемого игроком А, и определяется точка на нижней границе, соответствующая наибольшему выигрышу. Выделяются две активные стратегии игрока В, отрезки которых проходят через данную точку. Далее рассматриваются только эти две стратегии игрока В. Игра сводится к игре с матрицей (2 ґ 2). Оптимальные стратегии и цену игры находят по формулам (1) - (3).

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


Теория игр.

a = max (1,1) = 1, b = min (4, 3, 3,4) = 3, a № b, Теория игр.


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

Рис.4.


Нижней границей выигрыша для игрока А является ломаная В3КВ4. Стратегии В3 и В4 являются активными стратегиями игрока В. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Второму игроку невыгодно применять стратегии В1 и В2, поэтому вероятность их применения равна нулю, т.е. у1 = у2= 0. Решение игры сводится к решению игры с матрицей (2 ґ 2)


Теория игр.

a = max (1,1) = 1, b = min (3,4) = 3, a № b, Теория игр.


По формулам (1) - (3) находим оптимальные стратегии и цену игры:


x1 = 2/5, x2 = 3/5; y3 = 3/5, y2 = 2/5; v =11/5.


Ответ. Оптимальные смешанные стратегии игроков Теория игр (2/5, 3/5) и Теория игр (0, 0, 3/5, 2/5), цена игры составляет v =11/5.

Данный ответ означает следующее:

если первый игрок с вероятностью 2/5 будет применять первую стратегию и с вероятностью 3/5 вторую, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 11/5;

если второй игрок с вероятностью 3/5 будет применять третью стратегию, с вероятностью 2/5 четвертую и не будет использовать первую и вторую стратегии, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 11/5.

Третий случай. Рассмотрим игру (m ґ 2) с матрицей


Теория игр.


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

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

Далее рассматриваются только эти две стратегии игрока А. Игра сводится к игре с матрицей (2 ґ 2). Оптимальные стратегии и цену игры находят по формулам (1) - (3).

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


Теория игр.


a = max (3, 2, 0, - 1) = 3, b = min (4,6) = 4, a № b, Теория игр. Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий. Построим на плоскости отрезки, соответствующие стратегиям первого игрока. (см. рис.5).


Рис.5.


Верхней границей проигрыша для игрока В является ломаная А1КА4. Стратегии А1 и А4 являются активными стратегиями игрока А. Точка их пересечения К определяет оптимальные стратегии игроков и цену игры. Первому игроку невыгодно применять стратегии А2 и А3, поэтому вероятность их применения равна нулю, т.е. x2 = x3= 0. Решение игры сводится к решению игры с матрицей (2 ґ 2)


Теория игр.

a = max (3, - 1) = 3, b = min (4,6) = 4, a № b, Теория игр.


По формулам (1) - (3) находим оптимальные стратегии и цену игры:

x1 = 7/8, x4 = 1/8; y1 = 3/8, y2 = 5/8; v =27/8.

Ответ. Оптимальные смешанные стратегии игроков Теория игр (7/8, 0, 0, 1/8) и Теория игр (3/8, 5/8), цена игры составляет v =27/8.

Данный ответ означает следующее:

если первый игрок с вероятностью 7/8 будет применять первую стратегию, с вероятностью 1/8 четвертую и не будет использовать вторую и третью стратегии, то при достаточно большом количестве игр с данной матрицей его выигрыш в среднем составит не менее 27/8;

если второй игрок с вероятностью 3/8 будет применять первую стратегию и с вероятностью 5/8 вторую, то при достаточно большом количестве игр с данной матрицей его проигрыш в среднем составит не более 27/8.


1.5 Сведение матричной игры к задаче линейного программирования


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


Теория игр.


Если платежная матрица не имеет седловой точки, т.е. a <b и Теория игр, то решение игры представлено в смешанных стратегиях Теория игр (x1, x2,..., xm) и Теория игр (y1, y2,..., yn). Применение первым игроком оптимальной стратегии Теория игропт должно обеспечить ему при любых действиях второго игрока выигрыш не меньше цены игры.


Теория игр, Теория игр.

Рассмотрим задачу отыскания оптимальной стратегии игрока А, для которой имеют место ограничения


Теория игр


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

Преобразуем систему ограничений, разделив все члены неравенств на v.


Теория игр (1)

где

Теория игр, Теория игр. (2)


По условию x1 + x2 + … +xm = 1.

Разделим обе части этого равенства на v.


Теория игр.


Оптимальная стратегия Теория игр (x1, x2,..., xm) игрока А должна максимизировать величину v, следовательно, функция

Теория игр (3)


должна принимать минимальное значение.

Таким образом, получена задача линейного программирования: найти минимум целевой функции (3) при ограничениях (1), причем на переменные наложено условие неотрицательности (2). Решая ее, находим значения Теория игр, Теория игр и величину 1/v, затем отыскиваются значения xi = vti.

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


Теория игр, Теория игр.


Рассмотрим задачу отыскания оптимальной стратегии игрока B, для которой имеют место ограничения


Теория игр


Преобразуем систему ограничений, разделив все члены неравенств на v.


Теория игр (4) где Теория игр, Теория игр. (5)

По условию y1 + y2 + … +yn = 1. Разделим обе части этого равенства на v.


Теория игр.


Оптимальная стратегия Теория игр (y1, y2,..., yn) игрока В должна минимизировать величину v, следовательно, функция


Теория игр (6)


должна принимать максимальное значение.

Получена задача линейного программирования: найти максимум целевой функции (6) при ограничениях (4), причем на переменные наложено условие неотрицательности (5).

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

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


Теория игр.


a = max (2, 3,1) = 3, b = min (4, 5, 6,5) = 4, a № b, Теория игр.

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

Для определения оптимальной стратегии игрока А имеем следующую задачу линейного программирования:

Теория игр,

Теория игр

Теория игр, Теория игр.


Для нахождения оптимальной стратегии игрока В имеем следующую задачу линейного программирования:


Теория игр,

Теория игр

Теория игр, Теория игр.


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


Теория игр, Теория игр, Теория игр.


Учитывая соотношения между xi и ti, yj и sj, а также равенство


Теория игр,


можно найти оптимальные стратегии игроков и цену игры:


Теория игр (1/2, 1/2, 0), Теория игр (3/4, 0, 0, 1/4), v=7/2.

1.6 Игры с природой


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

Условия игры задаются матрицей


Теория игр.


Пусть игрок А имеет стратегии А1, А2, …, Аm, а природа - состояния В1, В2, …, Вn. Наиболее простой является ситуация, когда известна вероятность pj каждого состояния природы Вj. При этом, если учтены все возможные состояния, p1 + p2 + … + pj + … + pn = 1.

Если игрок А выбирает чистую стратегию Аi, то математическое ожидание выигрыша составит p1 ai1 + p2 ai2 + … + pn ain. Наиболее выгодной будет та стратегия, при которой достигается


(p1 ai1 + p2 ai2 + … + pn ain).


Если информация о состояниях с природой мала, то можно применить принцип недостаточного основания Лапласа, согласно которому можно считать, что все состояния природы равновероятностны:


Теория игр,


т.е. стратегию, для которой среднее арифметическое элементов соответствующей строки максимальное.

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

1. Критерий Вальда. Рекомендуется применять максиминную стратегию. Она выбирается из условия


Теория игр


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

2. Критерий максимума. Он выбирается из условия


Теория игр.


Критерий является оптимистическим, считается, что природа будет наиболее благоприятна для человека.

3. Критерий Гурвица. Критерий рекомендует стратегию, определяемую по формуле


Теория игр,

где a - степень оптимизма и изменяется в диапазоне [0, 1].

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: