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

2020-06-032021-03-09zzyxelСтудИзба

Модели теории игр. Матричные игры

Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задается выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям). Первый игрок имеет m стратегий i = 1,2,…,m, второй – n стратегий j = 1,2,…,n. Каждой паре стратегий поставлено в соответствие число , выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию , 2 – свою j-ю стратегию , после чего игрок 1 получает выигрыш за счет игрока 2 (если , то это значит, что первый игрок платит второму сумму ). На этом игра заканчивается.

Каждая стратегия игрока ; часто называется чистой стратегией.

Если рассмотреть матрицу

то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 – j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша .

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

Рекомендуемые материалы

Задачи по кредитам, процентным ставкам

Деньги и кредит

270 руб.

Анализ финансового состояния финансовой организации ПАО АКБ "Авангард" и рекомендации по его улучшению

Экономика финансовых организаций

500 руб.

Курсовая работа -Эффективность системы мотивации и стимулирования персонала в кофейне «Шоколадница»

Экономика управления персоналом

Определить величину годовых амортизационных отчислений при средней норме амортизации 10%, если стоимость основных средств на 01.01.ХХ составляла 10210 д.е., 01.03.ХХ было введено в действие оборудование стоимостью 2013 д.е., а с 01.09.ХХ выбыло основ

Экономика предприятия

99 руб.

т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет свою i-ю чистую стратегию. Затем из этих минимальных выигрышей отыскивается такая стратегия i=i₀, при которой этот минимальный выигрыш будет максимальным, т.е. находится

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

Игрок 2 при оптимальном поведении должен стремиться за счёт своих стратегий максимально уменьшить выигрыш 1 игрока. Поэтому для игрока 2 отыскивается

т.е. определяется максимальный выигрыш игрока 1 при условии, что игрок 2 применит свою j-ю чистую стратегию; затем игрок 2 отыскивает такую свою j=j₁ стратегию, при которой игрок 1 получит минимальный выигрыш, т.е. находит

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

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

Если в игре с матрицей А = , то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры . Седловая точка – это пара чистых стратегий соответственно игроков 1 и 2, при которых достигается равенство = . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке.

Математически это можно записать и иначе:

где i, j – любые чистые стратегии соответственно игроков 1 и 2; – стратегии, образующие седловую точку.

Таким образом, cедловой элемент является минимальным в i₀-й строке и максимальным в j₀-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждой строке находят минимальный элемент и проверяют, является ли этот элемент максимальным в своём столбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий игроков 1 и 2, образующая седловую точку и седловой элемент , называется решением игры. При этом i₀ и j₀ называются оптимальными чистыми стратегиями соответственно игроков 1 и 2.

Пример 7.

Решение. Седловой точкой является пара чисел , при которой . Заметим, что хотя выигрыш для точки (3;3) также равен , она не является седловой точкой, т.к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 8.

Решение. Из анализа матрицы выигрышей видно, что , т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию i = 2, то игрок 2, выбрав свою минимаксную j = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию i = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию j = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь, игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д. Таким образом, в игре без седловой точки игроки вынуждены применять так называемые смешанные стратегии, заключающиеся в том, что игроки применяют не одну стратегию и выбирают среди них случайным образом.

Графический метод решения матричных игр

Пример 9. Найти решение игры, заданной платежной матрицей:

а) .

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

На плоскости хOу введём систему координат (рис. 7) и на оси Oх отложим отрезок единичной длины А₁А₂, каждой точке которого поставим в соответствие некоторую смешанную стратегию первого игрока – (х, 1–х). В частности, точке А₁(0;0) отвечает стратегия А₁, точке А₂(1;0) – стратегия А₂.

Рис. 7

В точках А₁ и А₂восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью Оу) отложим выигрыш игрока 1 при стратегии А₁, а на втором – при стратегии А₂. Если игрок 1 применит стратегию А₁, то его выигрыш при стратегии второго игрока В₁составляет 2, при стратегии В₂ – 3, а при стратегии В₃ – 11. Числам 2, 3, 11 на оси Ох соответствуют точки В1, В2 и В₃.

Если же игрок 1 применит стратегию А₂, то его выигрыш при стратегии второго игрока В₁ равен 7, при В₂ – 5, а при В₃ – 2. Эти числа определяют точки В'₁, В₂', В₃' на перпендикуляре, восстановленном в точке А₂. Соединяя между собой точки В₁ и В'₁, В₂ и В₂', В₃ и В'₃, получим три прямые, расстояние до которых от оси Ох определяет средний выигрыш при любом сочетании соответствующих стратегий. Например, расстояние от любой точки отрезка В₂В'₂ до оси Ох определяет средний выигрыш при любом сочетании стратегий А₁, А₂ (с частотами х и 1 – х) и стратегией В₂игрока 2. Это расстояние равно

(вспомните планиметрию и рассмотрите трапецию ).

Ординаты точек, принадлежащих ломаной , определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке N. Следовательно, этой точке соответствует оптимальная смешанная стратегия , а ее ордината равна цене игры . Координаты точки N находим как точку пересечения прямых В₂В'₂ и В₃В'₃. Соответствующие два уравнения имеют вид

( при стратегии В₂)

( при стратегии В₃)

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

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

( при стратегии А₁)

( при стратегии А₂)

Следовательно, .

б) Найти решение игры, заданной платежной матрицей:

Решение. Матрица имеет размерность . Строим прямые (рис. 8), соответствующие стратегиям игрока 1 в системе координат yOx. Ломаная отвечает верхней границе выигрыша игрока 2, а отрезок KL – цене игры .

Рис. 8

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