Матричные игры, их представление. Максиминные и минимаксные стратегии. Нижняя и верхняя цена игры. Седловой элемент.

Основные понятия теории игр. Классификация игр

Понятие игры

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

Характеризующие признаки игры как математической модели ситуации:

1. наличие нескольких участников;

2. неопределенность поведения участников, связанная с наличием у каждого из них нескольких вариантов действий;

3. различие (несовпадение) интересов участников;

4. взаимосвязанность поведения участников, поскольку результат, получаемый каждым из них, зависит от поведения всех участников;

5. наличие правил поведения, известных всем участникам.

Определение. Ход в игре – выбор и осуществление игроком одного

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

Содержание теории игр:

1. установление принципов оптимального поведения в условиях неопределенности (конфликта),

2. доказательство существования решений, удовлетворяющих этим принципам,

3. указание алгоритмов нахождения решений, их реализация.

Моделями теории игр можно описать биологические, экономические, правовые, классовые, военные конфликты, взаимодействие человека с природой.

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

Классификация игр

-стратегические и чисто случайные

- игры в нормальной форме и динамические

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

В зависимости от числа стратегий: - конечные, если у игрока имеется конечное количество стратегий; - бесконечные (в противном случае).

По числу игроков: - парные (два игрока); - множественные (больше двух игроков).

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

Определение. Парные игры с нулевой суммой называются антагонистическими.

Определение. Конечные антагонистические игры называются матричными играми.

Матричные игры, их представление. Максиминные и минимаксные стратегии. Нижняя и верхняя цена игры. Седловой элемент.

В общем случае матричная игра задается прямоугольной матрицей размера mxn:

Считается, что 1-й игрок имеет стратегии , , …, , определяемые строками матрицы, а 2-й игрок – стратегии , , …, определяемые столбцами. Каждый элемент матрицы представляет выигрыш 1-го игрока (может быть и отрицательным) у 2-го, если каждый использует свою одну соответствующую стратегию.

Если представить платежную матрицу игры в виде:

то можно сделать следующие определения:

α -максимальный гарантированный выигрыш игрока Р1, независимый от того, какую бы стратегию ни выбрал игрок Р2. ( Стратегия максимин)

β -минимальный гарантированный проигрыш игрока Р2, независимый от того, какую бы стратегию ни выбрал игрок Р1. ( Стратегия минимакс )

Седловой точкой (седловым элементом) называется компонент платёжной матрицы, расположенный на пересечении строки с максиминной стратегией (игрок Р1) и столбца с минимаксной стратегией (игрок Р2).

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

Графическое решение на следующем примере:

дает такую картину:

Игры 2хn.

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

Например, при решении игры

строится график выигрышей 1-го игрока:

Из этого графика видно, что у 2-го игрока первая стратегия является невыгодной (проигрыш на ней больше) и отбрасывается, после чего остается игра 2х2,

которая решается аналитически по приведенным выше формулам.

Игры mx2.

Здесь на первом этапе строится график относительно выигрышей 2-го игрока. При этом максимальный проигрыш 2-го игрока изображается ломаной вверху графика, самая нижняя точка которой находится на пересечении двух активных стратегий 1-го игрока. Остальные стратегии 1-го игрока не являются активными. Далее аналитически решается игра 2х2 только на активных стратегиях.

Например, игра с матрицей

графически решается так:

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

Решение имеет вид:

7. Доминирование и дублирование стратегий в матричных играх. Эквивалентное преобразование матричной игры.

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

Если i-я строка поэлементно не меньше (≥ ) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B.

Аналогично, если i-й столбец поэлементно не меньше (≥ ) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (≤ ), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности. На цене игры это никак не скажется. Зато размер матрицы игры понизится. С этого и нужно начинать решение игры.

Частный случай доминирования является дублированиестратегий:

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

I i j

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

2. Правило Сэвиджа ( правило минимального риска ). При применении этого правила анализируется матрица рисков R = (r_ij). Рассматривая i -e решение будем полагать, что на самом деле складывается ситуация максимального риска b_i = max [r_ij],

Но теперь уж выберем решение i₀ с наименьшим b_i0. Итак, правило Сэвиджа рекомендует принять решение i₀, такое что:

b_i0 =min b_i = min (max r_ij)

I i j

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

a = min(max r_ij)
Kритерий Сэвиджа ориентирует статистику на самые неблагоприятные состояния природы, т.е. этот критерий выражает пессимистическую оценку ситуации.

3. Правило Гурвица (взвешивающее пессимистический и оптимистический подходы к ситуации). Принимается решение i, на котором достигается максимум:

λ min q_ij + (1-λ ) max q_ij, где 0 < λ < 1

J j

Значение λ выбирается из субъективных соображений. Если λ приближается к 1, то правило Гурвица приближается к правилу Вальда, при приближении λ к 0, правило Гурвица приближается к правилу " розового оптимизма" (догадайтесь сами, что это значит). ( максимакс )

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

Правило максимизации среднего ожидаемого дохода. Доход, получаемый фирмой при реализации i -го решения, является случайной величиной Q_i с рядом распределения. Правило рекомендует принять решение, приносящее максимальный средний ожидаемый доход.

4а. По критерию Байеса за оптимальные принимается та стратегия (чистая) A_i, при которой максимизируется средний выигрыш a или минимизируется средний риск

r - max∑ (a_ijp_j)

4б. Критерий Лапласа.
Если вероятности состояний природы правдоподобны, для их оценки используют принцип недостаточного основания Лапласа, согласно которого все состояния природы полагаются равновероятными, т.е.:

q₁ = q₂ =... = q_n = 1/n.

11. Понятие о статических играх с полной информацией на примере «Дилеммы заключенного».

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

Определение. Под играми с полной информацией понимают игры, в которых каждый из игроков точно знает характеристики других игроков.

Пример. «Дилемма заключенного». Двое заключенных подозреваются в совершении некоторого преступления. Они помещены в разные камеры и не имеют никакой возможности обмениваться информацией. Каждому по отдельности предлагается сознаться (С) к определенному сроку, но можно и молчать (М). Если один сознался, а другой молчит, то сознавшегося освобождают, а молчун получает

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

По традиции считается, что игрок 1 выбирает строки, а игрок 2 – столбцы. В каждой клетке матрицы стоят 2 числа: выигрыш игрока 1, выигрыш игрока 2. Матричная форма удобна для конечных игр двух лиц.

Дуополия Курно.

Пусть есть всего два продавца n=2. Продавец i независимо от другого продавца j≠ i планирует выпуск продукции в объёме . Тогда совокупное предложение Q= + . Цена на рынке устанавливается в соответствии с обратной функцией спроса, которую считаем линейной: P(Q) = (Q) = a − Q, a > 0, где а> 0 характеризует максимально возможную цену покупки.

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

Проблема общин.

В одной деревне живут n крестьян, которые держат коз. Крестьянин i решает, независимо от других, сколько коз gi ему держать. Общее поголовье G=g1+…gn; затраты на содержание одной козы с от него не зависят. Однако ценность козы для крестьянина v(G) зависит от общего поголовья, поскольку пастбище, где кормятся все козы деревни, весьма ограничено.

Наложим на функцию v(G) условия:

Это уравнение всегда имеет единственное решение при c< v(0), поскольку в левой части стоит убывающая функция, принимающая отрицательные значения на правом конце в точке Gmax.

Найдем общинный оптимум из принципа максимизации суммарного выигрыша G⋅ (v(G)− c).

Из условий первого порядка для общинного оптимума получим уравнение:

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

немного больше коз. В итоге ситуация может скатиться в устойчивое, но неэффективное с коллективной точки зрения равновесие Нэша.

21. Смешанные стратегии и смешанное расширение игры, равновесие Нэша в смешанных стратегиях на примере игры «Орлянка» («Совпадение монет»): определение смешанных стратегий, функций отклика и графическое отображение решения задачи.

Функция отклика (наилучшего ответа) первого игрока на действия второго:

Функция отклика (наилучшего ответа) второго игрока на действия первого:

РН соответствует всем точкам (p, q), удовлетворяющим обеим функциям отклика. Для этой цели можно построить график в координатах (p, q), т.е. на единичном квадрате:

Метод обратной индукции.

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

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

После этого игру можно частично свернуть (редуцировать), и дерево игры упрощается:

Поскольку действия террориста в Нью-Йорке несложно предугадать, пилот выбирает лететь в Нью-Йорк, где его выигрыш больше.

Таким образом, обратная индукция показывает, что пилот полетит в Нью-Йорк, а террорист не будет взрывать бомбу.

Обратную индукцию можно реализовать и на основе функций отклика игроков.

24. Применение метода обратной индукции на примере игры «Рэкет».

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

Зная эту функцию, рэкетиры максимизируют свою функцию выигрыша. Для этого надо подставить функцию отклика фирмы в функцию выигрыша рэкетиров и применить к полученному выражению условие первого порядка. Это дает значение α =1/2.

25. Представление динамической игры с полной информацией в нормальной форме (на примере динамического варианта игры «Выбор компьютера»).

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

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

Пример. Динамический вариант игры «Выбор компьютера», в котором 1-й игрок выбирает себе компьютер первым. Дерево игры имеет вид:

1-й игрок имеет две стратегии, совпадающие с альтернативами в вершине 1. Игрок 2 имеет 4 стратегии, каждая из которых определяет его действия в двух вершинах – 2 и 3. Его стратегии следующие: (2IBM, 3IBM), (2IBM, 3Mac), (2Mac, 3IBM), (2Mac, 3Mac).

Нормальная форма имеет вид:

Рассмотрим случай, когда а< c, b< c. Сравним равновесия Нэша с результатом применения обратной индукции.

Сначала применим обратную индукцию. Здесь игроки выберут следующие стратегии:
1: 1IBM

2: (2IBM, 3Mac)

Из таблицы же получаем сразу 3 РН, и только одно из них совпадает с решением, полученным по методу обратной индукции:

Такая ситуация является типичной, т.е. решение, получаемое обратной индукцией, всегда является РН.

26. Совершенное по подыграм равновесие Нэша (СПРН) (на примере динамического варианта игры «Выбор компьютера»). Связь с обратной индукцией. Равновесия пустых угроз.

Определение. Все РН, которые не могут быть получены обратной индукцией, называются «равновесиями пустых угроз». Это название отражает тот факт, что они противоречат предположению о рациональности игроков. Следовательно, концепция РН для динамических игр, вообще говоря, не дает удовлетворительного

прогноза исхода игры, и поэтому её требуется каким-то образом усилить.

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

Теорема. В игре с совершенной информацией и конечным числом ходов множество решений, получаемых обратной индукцией, совпадает с множеством СПРН.

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

ней РН.

Пример в 25 вопросе

Дуополия Штакельберга.

Дуополия Штакельберга – это модель несовершенной отраслевой конкуренции с лидирующей фирмой, которая первой определяет объем выпускаемой на рынок продукции. Зная планы лидера отрасли, другие фирмы определяют объемы собственных выпусков. Такой вид дуополии основан на том, что фирма – лидер имеет возможность прогнозировать ответную реакцию ведомой фирмы или фирм и планировать свой выпуск с учетом этого прогноза.

Пусть в игре участвую две фирмы, т.е. N = {1, 2}, причем фирма 1 – лидер, а фирма 2 – ведомая. Описание отрасли возьмем таким же, как в дуополии Курно.

Здесь фирма – лидер имеет возможность прогнозировать ответную реакцию ведомой фирмы и планировать свой выпуск с учетом этого прогноза.

Зададим порядок ходов:

Ход 1. Фирма 1 выбирает объём выпуска q1.

Ход 2. Фирма 2, зная выбор фирмы 1, выбирает объём своего выпуска q2.

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

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

Совокупный выпуск в дуополии Штакельберга равен QS = (a − c).

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

Корпорации и профсоюзы.

В этой модели два участника: профсоюз и фирма. 1-й ход принадлежит профсоюзу, который может диктовать фирме уровень зарплаты W. Зная предложение профсоюза, фирма в качестве 2-го хода выбирает уровень занятости L.

Профсоюз заинтересован как в увеличении зарплаты, так и в увеличении занятости, поэтому его функция выигрыша (W L), должна возрастать по обеим переменным. Линии безразличия (W L)=const , и направление роста выигрыша профсоюза должны выглядеть примерно так:

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

Изобразим на графике прямую с наклоном W, касательную к графику функции выпуска:

В силу обратной индукции решается задача оптимального выбора уровня зарплаты профсоюзом с учетом прогноза ответной реакции фирмы по занятости:

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

Модель банка.

Существует много моделей, построенных по схеме двухпериодной игры Модель банка:

1. Два инвестора положили деньги в банк на депозит в размере D каждый;

2. Банк вкладывает эти деньги в некоторый проект, который через два периода должен принести доход 2R;

3. Инвестор имеет право забрать деньги после первого периода, но тогда проект не будет реализован и удастся вернуть только 2r;

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

1. Во втором периоде имеется одно РН.

2. Подставим выигрыши в этом РН в игру первого периода.

3. Получается два равновесия РН.

4. Равновесие (нет, нет) лучше для обоих инвесторов.

5. Равновесие (взять, взять) возникает при бегстве капитала из банка из-за испуга, что кто-то заберет деньги из банка.( слухи! )

Выводы: Имеем 2 РН. Одно из них RR предпочтительнее другого, но ситуация r, r может возникнуть из-за слухов: «бегство капитала из банка». Эта ситуация не является единственным равновесием, но одним из РН, которое может реализоваться

Международная конкуренция.

Игра происходит в два этапа (периода):

1. Сначала правительства обеих стран одновременно и независимо назначают тарифы;

2. Затем, зная эти тарифы, фирмы участвуют на объединенном рынке двух стран (дуополия Курно), назначая выпуски продукциидля внутреннего потребления и на экспорт.

1. Выигрыш фирмы определяется их прибылью. ( π i )

2. Выигрыш государства учитывает интересы потребителей и фирмы своей страны, а также доходы от пошлины на импорт. ( Wi )

Выигрыш покупателей на графике соответствует площади заштрихованного треугольника.

Фиксируем тарифы и найдем равновесие Нэша в игре фирм (найдем h^*₁, h^*₂, e^*₁, e^*₂ ) для которых выполнено условие максимума прибыли).Т.к. функция выигрыша распадается на два слагаемых (внутренний рынок и экспорт), то преобразуем задачу.

Подставив равновесие Нэша в игре корпораций, зависящей от тарифов, как от параметров, в функции выигрыша государств, найдем равновесие Нэша в игре государств, назначающих тарифы. (все переменные, кроме тарифов, опущены)

Суммарный выпуск продукции в каждой стране будет равен 5·(ac)/ 9 . Для потребителей это хуже, чем при нулевых тарифах, когдастраны объединяются в один рынок с дуополией Курно и суммарнымвыпуском продукции 2· (a-c)/ 3. С точки зрения правительства, максимум выигрышей двух стран

достигается при нулевых тарифах. РН для правительства достигается в доминирующих стратегиях, нооно хуже чем свободная неравновесная торговля.

Денежная политика.

В этой модели повторяется динамическая игра, в которой участвуют представители власти, управляющие денежной политикой, и корпорации.

Ход 1. Корпорации формируют некоторый ожидаемый уровень инфляции p_e за год.

Ход 2. Власти узнают ожидания корпораций и определяют реальный уровень инфляции p.

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

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

Считается, что реальный уровень ВВП зависит от целевого по формуле:

Тогда

Решаем задачу максимизации ожидаемого выигрыша:

При выводе используем равенство:

Выпишем условие первого порядка для оптимального ответа игрока i

Подставляя это в условие оптимальности, получим дифференциальное уравнение

Общее решение этого уравнения имеет вид:

Получаем единственное симметричное РБН:

Итак, в классе возрастающих дифференцируемых стратегий имеется единственное симметричное равновесие Байеса-Нэша.

Наилучшая заявка продавца

должна определяться из решения задачи максимизации ожидаемого выигрыша продавца:

по всем допустимым заявкам продавца p_s? [ 0, 1]

Для данного аукциона нетрудно найти целое семейство РБН, зависящих от параметра Х – «правильной» цены.

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

Стратегия покупателя Стратегия продавца

Стратегия покупателя: ,

если, иначе

Стратегия продавца: ,

если , иначе

Нетрудно проверить, что эта пара стратегий образует РБН при любом Х от 0 до 1.

Изобразим графически зону потенциально возможных сделок V_s < V_B, которая реализуется при искренних заявках ( p_B(V_B) = V_B и p_S(V_S) = V_S ), при РБН с х – стратегиями.

Вероятность сделки при искренних стратегиях равна ½ , а при х - стратегиях вероятность сделки равна х(1-х) < ¼ .