Игры в нормальной форме. Игровые равновесия.

Пусть задано множество игроков . -ый игрок выбирает действие y_i из множества своих допустимых действий . Действия всех игроков называются ситуацией игры (игровой ситуацией): . Целевая функция i-го игрока зависит от вектора действий всех игроков y и является отображением , где . Т.е. каждой комбинации действий игроков соответствует некоторый выигрыш каждого из них. Совокупность множества игроков (агентов), целевых функций и допустимых множеств агентов называется игрой в нормальной форме. При этом предполагается, что каждый из игроков выбирает свои действия однократно, одновременно с другими игроками и независимо, то есть, не имея возможности договариваться с ними о своих стратегиях поведения (так называемая модель некооперативного поведения). Решением игры (равновесием) называется множество устойчивых в том или ином смысле векторов действий агентов.

Давайте возьмем i-го игрока и попробуем применить к нему гипотезу рационального поведения. Так как игрок рационален и выбирает i-ю компоненту вектора y, то своим выбором он пытается максимизировать свою целевую функцию: « ». Но то его действие, на котором достигается максимум целевой функции, будет зависеть от выбора других агентов. Задача такого вида в некотором смысле бессмысленна, т.к. ее решением будет действие , зависящее от действий всех других игроков – вектора , который называется обстановкой игры для i-го агента.

Рассмотрим возможные рассуждения отдельного игрока (агента): «Если остальные будут вести себя таким-то образом, то мне нужно вести себя таким образом, который максимизирует мою целевую функцию при данной обстановке. Но для того, чтобы выбрать свое действие, мне нужно знать, как будут себя вести остальные. Значит, мне нужно делать предположения о поведении остальных игроков». По аналогии с тем, как мы устраняли неопределенность в случае, когда имелся субъект, здесь присутствует множество игроков с так называемой игровой неопределенностью, т.е. неопределенностью, порождаемой целенаправленным поведением других игроков. Каждый игрок не может априори сказать, что сделают остальные. Рассмотрим возможные варианты.

Гарантирующее равновесие. Пусть i-ый игрок считает, что все остальные игроки действуют против него. Это – критерий пессимизма (максимального гарантированного результата – МГР, см. также раздел 2.2.1), который соответствует тому, что игрок выбирает действие

(1) ,

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

Определенный выше вектор действий игроков (состоящий из компонентов, описываемых (1), i Î N) называется максиминным, или гарантирующим равновесием. Это один из вариантов определения исхода игры. Можно сказать, что один из возможных вариантов поведения игроков – каждый из них выберет гарантирующую стратегию, т.е. реализует максиминное равновесие.

Пример 2.9. Обобщим Пример 2.1 на случай двух игроков (экономических агентов), принимающих решения об объемах выпускаемой продукции. То есть: N = {1; 2}, y_i ³ 0 – действие i-го игрока, c_i(y_i, r_i) = (y_i)² / 2 r_i – его функция затрат, i = 1, 2. Предположим, что рыночная цена на продукцию, производимую агентами, зависит от суммарного предложения: l(y) = l₀ – y₁ – y₂. Тогда целевые функции игроков примут вид (рассматриваемая модель называется дуополией Курно [10]):

(2) f_i(y) = (l₀ – y₁ – y₂) y_i – (y_i)² / 2 r_i, i = 1, 2.

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

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

Равновесие в доминантных стратегиях. Представим ситуацию, в которой целевая функция i-го игрока f_i(y) достигает максимума по его действию в точке, которая не зависит от действий других игроков, т.е. у игрока существует его действие, которое является наилучшим независимо от того, что делают оппоненты. Это оптимальное действие, не зависящее от обстановки, называется доминантной стратегией агента.

Формально: стратегия будет доминантной, если какая бы обстановка игры не складывалась и какое бы действие не выбирал i-ый игрок при этой обстановке, его выигрыш будет максимальным при выборе именно доминантной стратегии:

(3) .

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

Если у каждого игрока существует доминантная стратегия, то совокупность доминантных стратегий называется равновесием в доминантных стратегиях (РДС) . Это – идеальная ситуация для исследователя, описывающего математическую модель. Если удалось построить такую модель, в которой есть равновесие в доминантных стратегиях игры управляемых субъектов – это замечательно, т.к. сложно описывать взаимодействие субъектов между собой, учитывать, как они друг на друга влияют, как они принимают решения. Если есть равновесие в доминантных стратегиях, то каждый агент принимает решение независимо. А описывать независимое принятие решений гораздо проще. Но такая ситуация встречается очень редко.

Если рассмотреть Пример 2.9, то окажется, что в нем не существует РДС. Хрестоматийным примером игр, в которых существует РДС являются игры с сепарабельными целевыми функциями агентов, то есть такими целевыми функциями, которые монотонны по действию агента, независимо от обстановки игры. Частным случаем сепарабельных целевых функций, являются аддитивные.

Пример 2.10. Пусть целевые функции агентов аддитивны и линейны

(4) f_i(y) = a_i0 + ,

где {a_ij} и {a_i0} – известные константы, причем без потери общности можно считать, что A_i = [0; 1], i Î N. В линейном случае у каждого агента существует доминантная стратегия:

= Sign(a_ii), i Î N.

где Sign (z) = . ·

Определение 9: Стратегия называется доминантной стратегией игрока i, если для любой обстановки и для любых справедливо неравенство

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

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

Определение 10: Если для каждого игрока i существует доминантная стратегия ,то исход называется равновесием в доминантных стратегиях (РДС).

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

Лемма 2. Если в игре n лиц функции выигрыша непрерывны по совокупности стратегий и для каждого игрока частная производная существует и везде знакопостоянна, то существует РДС. При этом доминантной стратегия , i-гоигрока будет стратегия

=

Идею леммы 2 можно обобщить на значительно более широкий класс игр.

Лемма 3. Если в игре п лиц а функция выигрыша произвольного игрока i сепарабельна по стратегии этого игрока, то есть имеет единственный максимум на множестве действий то существует РДС, причем для игрока i его доминантная стратегия:

Для доказательства лемм 2 и 3 достаточно проверить определение РДС.

Определение.

Стратегия игрока в игре в нормальной форме (1) доминирует стратегию , если

,

,

где , , .

Обозначим через множество всех деноминируемых стратегий i-го игрока:

: доминирует .

Стратегия i-го игрока доминирует , если независимо от поведения «остального мира» стратегия для него не дает большего выигрыша, чем , а для некоторого допустимого стратегического выбора игроков ему строго выгоднее выбрать , чем . Отсюда следует, что игроку всегда имеет смысл выбирать стратегию только из множества .

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

Определение.

Стратегия игрока в игре (1) называется доминирующей (абсолютно оптимальной), если

.

Обозначим через множество всех доминирующих стратегий i-го игрока.

Определение.

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

Лемма 1.

Пусть для любого множество компактно, а функция непрерывна. Тогда множество недоминируемых стратегий i-го игрока не пусто.

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

При всех значениях параметра ; в общем случае не приходится ожидать, что такое решение существует

Определение.

Стратегии i-го игрока и называются эквивалентными, если они не различимы с его точки зрения:

.

Лемма 2.

Пусть в игре (1) множество недоминируемых стратегий i-го игрока не пусто: , множества стратегий компактны, функции выигрыша непрерывны, .

Тогда следующие утверждения эквивалентны:

– существует доминирующая стратегия i-го игрока: ;

– все стратегии в множестве эквивалентны.

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

Равновесие Нэша. Гораздо чаще, чем РДС, существует равновесие Нэша (РН). Джон Нэш, американский математик, в начале 50-х годов XX века предложил следующее: устойчивым исходом взаимодействия агентов можно считать такой вектор их действий, от которого в одиночку никому из них не выгодно отклоняться. Это значит, что ни один из агентов, в одиночку меняя свою стратегию на другую, не может увеличить свой выигрыш при условии, что остальные своих стратегий не меняют.

Формальное определение равновесия Нэша таково:

(5) ,

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

Отличие между изложенными подходами (РДС и равновесием Нэша) заключается в том, что в формулировке равновесия в доминантных стратегиях (3) фигурирует произвольная обстановка, то есть доминантная стратегия – наилучшая при любой обстановке. А стратегия по Нэшу – наилучшая при «нэшевской» обстановке (см. (5)).

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

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

Пример 2.11. Возьмем Пример 2.9 и найдем для него равновесие Нэша игры агентов, выбрав l₀ = 5, r₁ = 1, r₂ = 2. Для этого продифференцируем целевую функцию каждого агента по его действию, приравняем производную нулю, и решим систему уравнений. Получим равновесные действия агентов: = 15/13, = 20/13. ·

Пример 2.12. Пусть целевая функция i-го агента f_i(y, r_i) представляет собой разность между доходом h_i(y) от совместной деятельности и затратами c_i(y, r_i), где r_i – параметр эффективности (тип) агента, то есть

(6) f_i(y, r_i) = h_i(y) – c_i(y, r_i), i Î N.

Выберем следующий вид функций дохода и затрат:

(7) h_i(y) = g_i l Y, i Î N,

(8) c_i(y, r_i) = , i Î N,

где Y = , Для случая, когда в знаменателе выражения (8) стоит знак «–», предполагается, что .

Содержательно набор агентов может интерпретироваться как некоторая фирма, подразделения которой (агенты) производят однородную продукцию, реализуемую на рынке по цене l. Суммарный доход l Y распределяется между агентами в соответствии с фиксированными долями {g_i}. Затраты агента возрастают по его действиям, а эффективность деятельности (знаменатель выражения (8)) определяется типом агента. Взаимодействие агентов моделируется зависимостью затрат (эффективности деятельности) каждого из них от действий всех (других) агентов. Знак «+» в знаменателе выражения (8) соответствует эффективному взаимодействию агентов (убыванию затрат на масштаб) – чем большие действия выбирают другие агенты, тем меньше затраты (выше эффективность деятельности) рассматриваемого агента, что на практике может соответствовать снижению удельных постоянных издержек, обмену опытом, технологиями и т.д. Знак «-» в знаменателе выражения (8) соответствует неэффективному взаимодействию агентов (возрастанию затрат на масштаб) – чем большие действия выбирают другие агенты, тем больше затраты (ниже эффективность деятельности) рассматриваемого агента, что на практике может соответствовать нехватке основных фондов, ограничениям на побочные показатели (например, загрязнение окружающей среды) и т.д. Коэффициенты {b_i ³ 0} отражают степень взаимозависимости агентов.

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

y_i = g_i l(r_i ± b_i ), i Î N,

получим следующую зависимость суммарных действий от параметра l:

Y(l) = .

Пусть n = 2, g_i = b_i = 1/2, i = 1, 2, тогда суммарное действие и равновесные по Нэшу действия агентов равны, соответственно:

(9) Y(l) = 2 l R / (4 l),

(10) y^*_i(l) = (4 r_i l r_-i), i = 1, 2. ·

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

.

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

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

Пример 2.13. Рассмотрим Пример 2.10, в котором обозначим b_j = , b₀ = . Тогда суммарный выигрыш агентов равен

(11) S(y) = b₀ + .

Доставляющее максимум выражению (11) и эффективное по Парето действие i-го агента есть:

(12) = Sign(b_i), i Î N.

Если " i Î N Sign(a_ii) = Sign(b_i), то РДС является эффективным по Парето. Если $ i Î N:Sign(a_ii) ¹Sign(b_i), то требуется согласование интересов агентов. ·

Пример 2.14. Рассмотрим хрестоматийный пример с конкретными целевыми функциями. Пусть каждый игрок выбирает действия из отрезка A_i = [0; 1]. Выигрыш i-го агента – . Исследуем, существует ли равновесие в доминантных стратегиях или равновесие по Нэшу.

Если внимательно посмотреть на целевую функцию, то видно, что i-му агенту выгодно, максимизируя свою целевую функцию, выбирать максимальное значение своего действия независимо от того, что делают остальные (производная по действию i-го агента строго положительна независимо от обстановки). Значит, каждый агент будет выбирать максимальное значение своего действия, т.е. для него существует доминантная стратегия. Чтобы не выбрали остальные, он, увеличивая свое действие, выигрывает, а больше единицы он выбрать не может, значит, , i Î N.

Вычислим выигрыш каждого агента от равновесия в доминантных стратегиях. Если все выбрали по единице, то каждый получил выигрыш, равный единице: , i Î N.

Рассчитаем теперь один из векторов действий, эффективных по Парето (вычислив, например, максимум суммы целевых функций всех агентов). Это – вектор нулевых действий: , i Î N. Если все агенты выбирают нулевые действия, то выигрыш i-го агента равен , i Î N, и нельзя увеличить выигрыш одновременно всех агентов. Если мы хотим увеличить выигрыш i-го агента и начинаем увеличивать его действие, то тем самым уменьшаем выигрыши остальных, потому что это действие входит с минусом в целевые функции других агентов.

Если играют три или более агентов, то, выбирая действия, эффективные по Парето, они получают строго больше, чем играя доминантные стратегии, так как при n ³ 3.

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

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

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

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

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