Файл: Элементы теории игр.pdf

М.В. Губко Д.А. Новиков А.Г. Чхартишвили

ЭЛЕМЕНТЫ ТЕОРИИ ИГР

Настоящий материал содержит описание основных понятий и моделей теории игр. В том числе кратко рассматриваются: некоо- перативные игры, кооперативные игры и иерархические игры. Для

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

организационными системами можно порекомендовать учебники и монографии [6, 9, 12, 16-18].

Некооперативные игры

Рассмотрим игровую неопределенность, отражающую совме- стное принятие решений несколькими агентами (при заданных управлениях со стороны центра), в рамках которой существенными

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

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

Для описания коллективного поведения агентов недостаточно определить их предпочтения и правила индивидуального рацио- нального выбора по отдельности. В случае, когда в системе имеет- ся единственный агент, гипотеза его рационального (индивидуаль- ного) поведения предполагает, что агент ведет себя таким образом,

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

1

рациональное действие каждого из них зависит от действий других агентов.

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

Каждый агент осуществляет выбор действия xi, принадлежа-

щего допустимому множеству Xi, i Î N = {1, 2, …, n} – множест-

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

Выигрыш i-го агента зависит от его собственного действия xi Xi, от вектора действий

x-i = (x1, x2, …, xi-1, xi+1, …, xn) Î X-i = ∏ X j

j N \{i}

оппонентов N\{i} и от состояния природы1 q Î W, и описывается

агентов. При фиксированном значении состояния природы сово- купность Г = (N, {Xi}i N, {fi(×)}i N) множества агентов, множеств

их допустимых действий и целевых функций называется игрой в нормальной форме. Решением игры (равновесием) называется

множество устойчивых в том или ином смысле векторов действий агентов [6].

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

Следовательно, принцип принятия им решения о выбираемом действии (при фиксированных обстановке и состоянии природы)

1 Состояние природы может быть, в том числе, вектором, компоненты кото- рого отражают индивидуальные характеристики (типы) агентов.

2

можно записать следующим образом (BR обозначает наилучший ответ – best response):

BRi(q, x-i) = Arg max fi(q, xi, x-i), i Î N.

xi X i

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

Равновесие в доминантных стратегиях. Если для некоторого

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

РДС) [6]. Если у каждого из агентов существует доминантная стратегия, то они могут принимать решения независимо, то есть выбирать действия, не имея никакой информации и не делая ника- ких предположений об обстановке. К сожалению, РДС существует далеко не во всех играх.

Для реализации агентами РДС, если последнее существует,

достаточно знания каждым из них только своей целевой функции и допустимых множеств X' и W.

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

Равновесие Нэша. Определим многозначное отображение

BR(q, x) = (BR1(q, x-1); BR2(q, x-2), …, BRn(q, x-n)).

Равновесием Нэша [6] при состоянии природы q (точнее – па-

раметрическим равновесием Нэша) называется точка x*(q) Î X',

удовлетворяющая следующему условию: x*(q) Î BR(q, x*(q)).

Последнее вложение можно также записать в виде:

" i Î N, " yi Î Xi fi(q, x*(q)) ³ fi(q, yi, x−*i (θ ) ).

Множество EN(q) всех точек вида x*(q) можно описать сле- дующим образом:

EN(q) = {x Î X’ | xi Î BRi(q, x-i), i Î N}.

3

Для реализации равновесия Нэша достаточно, чтобы рацио- нальность агентов и все параметры игры, а также значение состоя- ния природы были общим знанием [15], то есть каждый из агентов рационален, знает множество участников игры, целевые функции и допустимые множества всех агентов, а также знает значение со- стояния природы. Кроме того, он знает, что другие агенты знают это, а также то, что они знают, что он это знает и т.д. до бесконеч- ности.

Субъективное равновесие. Рассмотренные виды равновесия являются частными случаями субъективного равновесия, которое определяется как вектор действий агентов, каждая компонента

которого является наилучшим ответом соответствующего агента на ту обстановку игры, которая может реализоваться с его субъек- тивной точки зрения. Рассмотрим возможные случаи.

Предположим, что i-ый агент рассчитывает на реализацию об-

становки игры )B ("B" обозначает beliefs; иногда используются x−i

термины «предположение», «догадка» – conjecture) и состояния природы θi , тогда он выберет

Вектор xB является точечным субъективным равновесием.

Отметим, что при таком определении «равновесия» не требу- ется обоснованности предположений агентов о действиях оппо-

i N, является равновесием Нэша (для этого, в частности, доста- точно, чтобы все параметры игры были общим знанием, и чтобы

каждый агент при построении )B моделировал рациональное x−i

поведение оппонентов). В частном случае, если наилучший ответ каждого агента не зависит от предположений об обстановке, то

субъективное равновесие является равновесием в доминантных стратегиях.

В более общем случае i-ый агент может рассчитывать на вы- бор оппонентами действий из множества X−Bi X-i и реализацию

4

состояния природы из множества Ωi Í W, i Î N. Тогда наилучшим ответом будет гарантирующее субъективное равновесие:

гарантирующее субъективное равновесие является «классическим» гарантирующим равновесием. Разновидностью гарантирующего субъективного равновесия является П-равновесие, подробно опи- санное в [1].

В еще более общем случае в качестве наилучшего ответа i-го агента можно рассматривать распределение вероятностей pi(xi), где pi(×) Î D(Xi) – множеству всевозможных распределений на Xi, кото-

рое максимизирует ожидаемый выигрыш агента с учетом его представлений о распределении вероятностей mi(x-i) Î D(X-i) дейст- вий, выбираемых другими агентами, и распределении вероятно- стей qi(q) Î D(W) состояния природы (получим Байесов принцип

Таким образом, для реализации субъективного равновесия требуется минимальная информированность агентов – каждый из них должен знать свою целевую функцию fi(×) и допустимые мно- жества W и X’. Однако при такой информированности совокуп-

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

Равновесие Байеса–Нэша. Если в игре имеется неполная ин- формация (см. [17, 18]), то Байесова игра описывается следующим набором:

- множеством N агентов;

5