Игры с ненулевой суммой

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

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

Пусть участник игры А может выбрать любую из стратегий А₁, А₂, …, А_m, а участник В – любую из стратегий В₁, В₂, …, В_n. Если игрок А выбрал стратегию А_i, а игрок В – стратегию B_k, то выигрыш игрока А будет равен числу а_ik, а выигрыш игрока В – числу b_ik,Таким образом, каждый из игроков получит свой приз. Выигрыши игроков А и В могут быть представлены двумя матрицами:

,

Таким образом, имеем две матрицы: А – платежную матрицу игрока А; В – платежную матрицу игрока В. Поэтому такие игры получили название биматричных. Рассмотренные раньше матричные игры являются частным случаем биматричных, у которых a_ik=-b_ik.

Так же, как и для случая матричной игры, обозначим через вероятности с которыми игрок А использует в ходе игры свои чистые стратегии А₁, А₂, …, А_m. Для этих вероятностей выполняются условия

Аналогично, обозначим через , ,…, вероятности, с которыми игрок B использует в ходе игры свои чистые стратегии , ,…, . Для этих вероятностей выполняются условия:

Векторы и полностью определяют характер игры игроков A и B и называются смешанными стратегиями.

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

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

Рассмотрим случай биматричной игры размера . В этом случае платежные матрицы игроков имеют вид:

вероятности

а средние выигрыши вычисляются по формулам:

(5.1)

Пара чисел определяет равновесную ситуацию, если для любых p и q, удовлетворяющих условиям , , одновременно выполняются следующие неравенства:

(5.2)

Выполнение неравенств (6.2) равносильно выполнению следующих неравенств:

(5.3)

Четыре неравенства (5.3) позволяют провести поиск точки равновесия.

Перепишем формулы (5.1)для средних выигрышей в виде:

(5.4)

Положив в первой формуле (5.4) p=1 и p=0, получим:

Найдем соотношения для разностей:

где

Перепишем эти соотношения в виде:

В случае, если пара (p,q) определяет точку равновесия, то в соответствии с (5.3) эти разности неотрицательны:

Сравнив это с предыдущей формулой, получим:

Аналогично для игрока B найдем:

где

Таким образом, для того чтобы в биматричной игре:

пара (p, q) определяла равновесную ситуацию, необходимо и достаточно одновременное выполнение следующих неравенств:

(5.5)

где

(5.6)

Использование соотношений (5.5), (5.6) для решения задач рассмотрим на примерах.

Борьба за рынки

Фирмы А и В производят однородный товар, который могут сбыть на одном из двух рынков. Фирма В является более состоятельной. Фирмы выбирают для борьбы один из рынков независимо друг от друга. Если фирмы выберут один и тот же рынок, то в конкурентной борьбе фирма А потерпит поражение. Если фирмы выберут разные рынки, то фирма А, не встречая противодействия, захватит выбранный рынок. Пусть платежные матрицы игроков имеют вид:

; .

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

По формулам (5.6) рассчитаем коэффициенты :

;

;

Подставив полученные значения в (5.5), получим

(5.7)

(5.8)

Рассмотрим сначала пару неравенств (5.7) для трех различных случаев: p=1, p=0, 0<p<1.

Для первого случая p=1получим:

Из второго неравенства находим:

или (5.9)

Для второго случая p=0 и

Из первого неравенства находим

или (5.10)

Для третьего случая 0<p<1 получим

Отсюда находим и . Выполнение этих двух неравенств одновременно возможно лишь при

(5.11)

Полученные результаты изображены на рис. 5.1.

Рис. 5.1

На рис. 5.1 выделен единичный квадрат, соответствующий неравенствам

Для первого случая p=1 имеем . На рис. 5.1 это луч, идущий из точки с координатами вниз. Для второго случая p=0 и . На рис. 5.1 это луч, идущий из точки с координатами вверх. Для третьего случая 0<p<1получили . Это горизонтальный отрезок на интервале 0<p<1.

Получили зигзаг, выделенный полужирной линией. Нас интересует та часть зигзага, которая попала в выделенный единичный квадрат.

Рассмотрим теперь пару неравенств (5.8) для трех различных случаев q=1, q=0, 0<q<1.

Для первого случая q=1 найдем

Из второго неравенства получим или .

Для второго случая q=0 и , а для третьего случая 0<q<1 имеем .

Полученные результаты изображены на рис 5.2. Так же, как и в предыдущем случае, получили зигзаг, выделенный полужирной линией.

Результаты объединения рис. 5.1, 5.2 представлены на рис. 5.3.

Рис. 5.2 Рис. 5.3

Точкой равновесия является общая точка построенных зигзагов. Ее координаты равны . Тогда смешанные стратегии игроков имеют вид

.

Средние выигрыши игроков определим по формулам (5.1):

Дилемма узников

Пример: Два узника находятся в предварительном заключении по подозрению в совершении преступления. Каждый узник имеет по две стратегии: молчать (стратегия М) или говорить (стратегия Г). Стратегия М – узник не признается в преступлении, стратегия Г- узник сознается в совершенном преступлении совместно с товарищем.

Если ни тот ни другой из узников не сознается в преступлении, то их потери составят -1, т.е.

Если и тот и другой узники сознаются в преступлении, то их потери составляют -6 т.е.

Приведенные условия представлены матрицами А и В:

; .

Определить параметры равновесной ситуации.

По формулам (5.6) рассчитаем коэффициенты С, α, D, β:

;

;

Подставив полученные значения в (5.5), получим:

(5.12)

(5.13)

Рассмотрим сначала пару неравенств (5.12) для трех различных случаев; p= 1, р = 0, 0< p < 1.

Для первого случая р = 1 получим:

Из второго неравенства находим

2q-3≥0, 2q≥3 или (5.14)

Для второго случая p= 0 и

Из первого неравенства находим

или . (5.15)

Для третьего случая 0< p < 1 получим

Отсюда находим -2q+3≥0 и 2q-3≥0. Выполнение этих двух неравенств одновременно возможно лишь при

(5.16)

Полученные результаты изображены на рис. 5.4.

Рис. 5.4

На рисунке 5.4 выделен единичный квадрат, соответствующий неравенствам

0< p < 1 и 0< q < 1.

Для первого случая р = 1 имеем . На рис.5.4 это луч, идущий из точки с координатами вверх.

Для второго случая р = 0 и . На рис.5.4 это луч, идущий из точки с координатами вниз.

Для третьего случая 0< p < 1 получили . Этот горизонтальный отрезок на интервале 0 <p< 1 , соединяющий точки с координатами и .

Получили зигзаг, выделенный полужирной линией. Нас интересует та часть зигзага, которая попала в выделенный единичный квадрат.

Рассмотрим теперь пару неравенств (5.13) для трёх различных случаев: q=1, q=0, 0 < q < 1.

Для первого случая q=1найдем

Из второго неравенства получим или .

Для второго случая и , а для третьего случая 0<q<1имеем .

Полученные результаты изображены на рис. 5.4. Так же, как и в предыдущем случае, получили зигзаг, выделенный полужирной линией.

Точкой равновесия является общая точка построенных зигзагов. Её координаты (0,0). Тогда смешанные стратегии игроков имеют вид

.

Средние выигрыши игроков вычисляются по формулам (5.1):

.

Это значит, что каждый игрок выбирает вторую смешанную стратегию (сознаться) и его потери составят -6. По условию задачи сговор (создание коалиции) между игроками запрещён. В противном случае игроки выбрали бы первую чистую стратегию (молчать), по которой каждый теряет -1.

Кооперативные игры

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

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

Пусть выигрыши двух игроков определяются множеством S в пространстве переменных x и у, где х – выигрыш первого игрока, а у – выигрыш второго игрока (рис. 5.4).

Рис. 5.4

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

Парето-оптимальным множеством называется множество точек, образующих северо-восточную границу множества S (множество АВ на рис. 5.4).

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

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

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

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

Если множество возможных платежей S выпукло, замкнуто и ограничено сверху, то точка Нэша существует и единственна.

Пример 5.1. Найти точку Нэша. Платежные матрицы в этой игре имеют вид

.

Определить параметры равновесной ситуации.

Решение. Средние выигрыши игроков А и В вычисляются по формулам (5.1):

(5.17)

Две эти функции заданы на единичном квадрате (рис. 5.5)

.

Рис. 5.5

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

(5.18)

Функция задана параметрически, где параметром является р. Умножив первое уравнение (5.18) на 2 и сложив уравнения системы (5.18), получим

.

Это уравнение прямой, т.е. граница искомой области является отрезком данной прямой (отрезок CF на рис. 5.6), причем точка соответствует , а точка — . Точно так же можно оказать, что остальные границы искомой области являются отрезками прямых.

Вторая граница. При и соотношения (5.17) приобретают вид:

При имеем , т.е. точку ; при — , т.е. точку . Таким образом, искомым отрезком является отрезок LF.

Третья граница. При и :

При имеем , т.е. точку ; при - , т.е. точку . Искомым отрезком является отрезок CD.

Четвертая граница. При и :

При имеем , т.е. точку ; при — , т.е. точку . Искомым отрезком является отрезок LD.

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

Рис. 5.6

Координаты точки угрозы Т определяются путем подстановки в (5.17) координат точки равновесия биматричной игры. Эти координаты были найдены при решении примера 5.11: р* = 0, q* = 0 .

Тогда

Таким образом, точкой угрозы является точка .

Точкой решения Нэша называется точка, в которой достигается максимум . Можно показать, что это точка . Ей соответствуют чистые стратегии обоих игроков: , . Все это означает, что потери узников составят -1, и стратегиями узников является «молчать», т.е. ни тот ни другой из узников не сознается в преступлении.