<<
>>

ПРИЛОЖЕНИЕ 1. ЭЛЕМЕНТЫ ТЕОРИИ ИГР

Настоящее приложение содержит описание основных понятий и моделей теории игр. В том числе кратко рас­сматриваются: некооперативные игры, кооперативные игры, иерархические игры и рефлексивные игры.
Для бо­лее полного ознакомления с проблематикой и результатами использования теоретико-игровых моделей в задачах управления организационными системами можно реко­мендовать учебники и монографии [20, 23, 25, 34, 38, 39, 60, 68, 69].

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

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

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

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

д.

Каждый агент осуществляет выбор действия хг, принадлежащего допустимому множеству Хг, I е N = {1, 2, ..., п} - множеству агентов. Выбор действий агентами осуществляется однократно, одновременно и независимо.

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

Х-г = (Х1, Х2, ... , Х;-1, Х; +1, ..., Хп) е X- = П Ху

оппонентов Ж^} и от состояния природы[32] в е О и описы­вается действительнозначной функцией выигрыша / = / (в, Х), где Х = (Хг, Х-г) = (Х1, Х2, ..., Хп) е X' = П Ху -

^■еN

вектор действий всех агентов, который называется ситуа­цией игры. При фиксированном значении состояния при­роды совокупность Г0 = {XI}; е ^ {/(•)} е N множества агентов, множеств их допустимых действий и целевых функций называется игрой в нормальной форме. Решением игры (равновесием) называется множество устойчивых в том или ином (и оговариваемом в каждом конкретном случае) смысле векторов действий агентов [25].

В силу гипотезы рационального поведения каждый агент будет стремиться выбрать наилучшие для него (с точки зрения значения его целевой функции) действия при заданной обстановке. Обстановкой для него будет сово­купность состояния природы в е W и обстановки игры x-i = (xi, Х2, ..., x-j, x1+1, ..., xn) e X-i = ПX1 .

jeN\{i}

Следовательно, принцип принятия i-м агентом реше­ния о выбираемом действии (при фиксированных обстанов­ке и состоянии природы) можно записать следующим обра­зом (BR обозначает наилучший ответ - best response)[33]:

BRi(e, x-i) = Arg max fi (в, xi, x-i), i e N.

xi eXi

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

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

Для реализации агентами РДС, если последнее суще­ствует, достаточно знания каждым из них только своей целевой функции и допустимых множеств X' и W.

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

x^ е Arg max min min f (ß, xt, x-i), i е N.

xteXi x_i eX_i 0eQ

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

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

BR(ß, x) = (BRi(9, x_i); BRi(ß, x-i), BRn(9, x-n)).

Равновесием Нэша [25] при состоянии природы ß (точнее, параметрическим равновесием Нэша) называется точка x (ß) е X', удовлетворяющая следующему условию: x (ß) е BR(ß, x (ß)).

Последнее вложение можно также записать в виде: " i е N, "y е X f (ß x\ß) >f (ß,y, x_i(ß)).

Множество En (ß) равновесий Нэша можно описать следующим образом:

En(0) = {x = (xi, x2, ..., xn) е X | xt е BRi(ß, x-), i е N}.

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

Кроме того, он знает, что другие агенты знают это, а также то, что они знают, что он это знает, и так далее до бесконечности. Отказ от предположения об общем знании превращает игру в нормальной форме в рефлексивную игру (см. ниже раздел П.1.4 и [57]).

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

Предположим, что 7-й агент рассчитывает на реализа­цию обстановки игры XB («В» обозначает beliefs; иногда используются термины «предположение», «догадка» - conjecture) и состояния природы q , тогда он выберет

xB е ВОД , xB ), i е N.

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

Отметим, что при таком определении «равновесия» не требуется обоснованности предположений агентов о действиях оппонентов, то есть может оказаться, что 3 i е N: ХВ Ф xB7. Обоснованное субъективное равновесие, то есть такое, что xB7 = xBt, i е N, является равновесием

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

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

реализацию состояния природы из множества Д ^ Д

i е N. Тогда наилучшим ответом будет гарантирующее субъективное равновесие:

Xi ( XBt, Д ) е Arg max min min f (в, x,, x-i), i е N.

Xi eXi X_i eXB eeWi

Если XB = X.u Д = Д i e N, то Xi( XB) = x*, i e N,

то есть гарантирующее субъективное равновесие является «классическим» гарантирующим равновесием.

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

В еще более общем случае в качестве наилучшего от­вета i-го агента можно рассматривать распределение веро­ятностей pi (xi), где pi (•) е A(X) - множеству всевозможных распределений на Xi, которое максимизирует ожидаемый выигрыш агента с учетом его представлений о распределении вероятностей m (x-i) е A(X-i) действий, выбираемых другими агентами, и распределении вероятностей q (в) е А(Д) со­стояния природы (получим Байесов принцип принятия решений) [69]:

Рг (m (-Х qi ОХ 0 е

е Arg mAax > I f (в,xi, x-i) Р,(x,) q,(в) m(x-i) de dx, i е N.

pi eA(лi) J X'.n

Таким образом, для реализации субъективного равно­весия требуется минимальная информированность агентов: каждый из них должен знать свою целевую функцию f (•) и допустимые множества Д и X'. Однако при такой инфор­мированности предположения агентов о состоянии приро­ды и о поведении оппонентов могут быть несогласованны­ми. Для достижения согласованности, то есть для того, чтобы предположения оправдывались, необходимы допол­нительные предположения о взаимной информированности агентов. Наиболее сильным является предположение об общем знании, которое превращает субъективное точечное равновесие в равновесие Нэша, а совокупность Баейсовых принципов принятия решений - в равновесие Байеса-Нэша.

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

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

- множеством К' возможных типов агентов, где тип г-го агента к, е Кг, г е N, вектор типов к = (к1, кг, ..., кп) е К' = ПК,;

iеN

- множеством X' = П X допустимых векторов

iеN

действий агентов;

- набором функций полезности и,: К' хX' ® Ш 1;

- представлениями /л, (- |к,) е А(К), г е N, агентов.

Равновесие Байеса-Нэша в игре с неполной инфор­мацией определяется как набор стратегий агентов вида ог: К, ® X,, г е N, которые максимизируют соответствую­щие ожидаемые полезности

и, (кг, о, (-), СТ-гО)) = | и(к, о, (к,), о-к)) /л, (к-,| к,) ёк-ь г еN.

к -г еП Кз

В Байесовых играх, как правило, предполагается, что представления {/(-|-)}г е N являются общим знанием. Для этого, в частности, достаточно, чтобы они были согласова­ны, то есть выводились каждым из агентов по формуле Байеса из распределения /(к) е А(К) которое является общим знанием.

Выше рассмотрены некоторые концепции решения некооперативных игр. Приведем основные понятия коопе­ративных игр, моделирующих взаимодействие агентов, которые имеют возможность образовывать коалиции и в рамках этих коалиций договариваться о выбираемых дей­ствиях, перераспределять полезность и так далее (отметим, что в настоящей работе рассматриваются в основном не­кооперативные модели - результаты исследования коопе­ративного взаимодействия участников организационных систем описаны в [24, 25, 38, 68]).

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

Кооперативная игра задается множеством игроков N = {1, ..., п} и характеристической функцией V: 2м® Я, ставя­щей в соответствие каждой коалиции игроков с N ее выигрыш.

Дележом игры (М, V) называется вектор х = (х1, ..., хп), для которого Е Хі = v(N) (свойство эффективности),

iєN

хі > v({i}), і єМ (свойство индивидуальной рационально­сти).

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

Говорят, что дележ х доминирует дележ у по коали­ции 5 ( х у 5 у ), если "і є 5 хі > уі, Е хі £ v(S). Если су-

іє5

ществует такая коалиция 5, что х у 5 у, говорят, что дележ

х доминирует дележ у. Множество недоминируемых деле­жей игры называется ее С-ядром.

Для заданного множества игроков N сбалансирован­ным покрытием называется такое отображение 55 множе­ства собственных коалиций 2N \{Л} в отрезок [0, 1], что = 1 для всех игроков і є N (суммирование ведется

5: іє5

по собственным коалициям, содержащим игрока і). 464

Необходимые и достаточные условия непустоты С-ядра даются теоремой О. Н. Бондаревой: С-ядро игры (Ы, V) не пусто тогда и только тогда, когда для любого сбалансирован­ного покрытия 5з

£ 5) £ Ч N).

5 с N

Игры с непустым С-ядром называются сбалансиро­ванными.

Кооперативная игра называется несущественной, ес­ли для произвольной коалиции 5 с N v(S) = £ v({/}), в

противном случае игра называется существенной. Несуще­ственность игры означает нулевой эффект от кооперации игроков.

Игровая ситуация является сильным равновесием Нэ- ша, если никакая коалиция не может выиграть, отклоняясь от равновесной ситуации. Множество сильных равновесий Нэша может оказаться пустым, однако если в некоторой игре с трансферабельной полезностью игроков имеется единственное сильное равновесие Нэша, то соответствую­щая кооперативная игра будет несущественной.

Концепция решений в угрозах и контругрозах осно­вана на следующей идее. Пусть, например, в процессе игры трех лиц образовалась коалиционная структура {{1, 2}, {3}}, содержащая коалицию Т = {1, 2}, в которую входят игроки с номерами 1 и 2. При распределении дохо­да коалиции v({1, 2}) игроки 1 и 2 получают суммы х1 и х2 соответственно. Тогда, если игрок 1 недоволен таким рас­пределением, он может сказать своему партнеру, что если его доля дохода не будет увеличена, то он сформирует коалицию 5 = {1, 3}, где сможет рассчитывать на больший выигрыш. Если такая коалиция 5 может образоваться, то есть если игроку 3 выгодно сменить конфигурацию х на новую конфигурацию у, то такое заявление называется угрозой игрока 1 игроку 2. В свою очередь игрок 2 может заявить игроку 1, что в случае подобных его действий он может предложить игроку 3 такую конфигурацию 2 коали­ционной структуры {{1}, {2, 3}}, что игрок 3 получит больший доход, чем в конфигурации у, а сам игрок 2 полу­чит не меньше, чем в исходной конфигурации х. Таким образом, игрок 2 выдвигает контругрозу, «защищающую» его долю х2.

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

П.1.3. Иерархические игры

Если в рассматриваемых до сих пор моделях игровой неопределенности предполагалось, что игроки (агенты) выбирают свои стратегии одновременно и однократно (мо­дели повторяющихся и дифференциальных игр в настоящей работе не рассматриваются - см. [23, 69]), то в иерархиче­ских играх [20, 23, 25, 34] существует фиксированный поря­док ходов - первый ход делает центр, затем свои стратегии выбирают агенты. С этой точки зрения иерархические игры являются наиболее адекватным аппаратом описания задач управления организационными системами.

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

Критерии эффективности (целевые функции) первого и второго игроков обозначим = /(х1, х2) и = /21, х2) соответственно. Выигрыши игроков зависят от их действий х1 и х2 из множеств действий X1, X0.

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

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

Например, если агент (выбирающий стратегию вто­рым) не ожидает информации о действии центра, то реализация права первого хода центра может состоять в сообщении центром агенту функции х, (х2). Такое сооб­щение может рассматриваться, как обещание выбрать действие x1 = Xj( x2) при выборе агентом действия x2. Тогда стратегия агента состоит в выборе действия в зависимости от сообщения центра, x2 = ~2 (X (•)). Если при этом агент доверяет сообщению центра, он должен выбрать действие x*, реализующее

max f2 (Xi(x2), x2).

Игра с описанным выше порядком функционирова­ния называется для краткости игрой Г2 (примером такой игры служит как раз задача стимулирования в условиях информированности центра о действии агента - см. вторую главу) [20].

Если центр не ожидает информации о действии агента и это известно агенту, то стратегия центра состоит, как уже было сказано, просто из выбора некоторого действия x*. Стратегия агента состоит в выборе x2 = ~2(x*) (он делает ход вторым, уже зная действие центра). Такая игра называ­ется игрой Г1 (это, например, та же задача стимулирования, но уже в условиях отсутствия у центра информации о дей­ствии агента) [20].

Рассмотрим сначала игру Г\.

Пара действий (x*, x*) в игре Г1 называется равнове­сием Штакельберга, если

x* є Arg max /(xj, x2), (1)

x1eX10, x2 gR2( x1)

x* Є R2(^ = Arg maxo f2 (x*, x2) , (2)

то есть R2 (x1) - функция наилучшего ответа агента на действие центра.

Равновесие в игре Г1 отличается от равновесия Шта­кельберга (1) тем, что при определении оптимальной стра­тегии первого игрока вычисляется минимум по множеству

x,):

x* е Arg max min f1(x1 ,x2).

X,eX0 x2 eR (x, )

В игре Г, агент выбирает действие в условиях полной информированности, уже зная действие центра. Максими­зация выигрыша выбором своего действия является здесь частным случаем применения принципа МГР. Равновесное по Штакельбергу действие центра также дает ему гаранти­рованный результат, если центр уверен в том, что агент выбирает свое действие в соответствии с (2) и принципом благожелательности. Таким образом, равновесные страте­гии как центра, так и агента, являются для них и гаранти­рующими.

Однако ситуация, когда первый ход дает преимуще­ство, все же более типична. Тогда, если порядок ходов определяется самими игроками, между ними возникает борьба за лидерство. Игре двух лиц в нормальной форме можно поставить в соответствие две игры Г, (игры первого порядка), отличающиеся последовательностью ходов. Тогда борьба за лидерство (первый ход) определяется выгодностью перехода от исходной игры к какой-либо из иерархических игр первого порядка. Известно [25], что если в игре двух лиц имеются хотя бы два различных оп­тимальных по Парето равновесия Нэша, то в этой игре имеет место борьба за первый ход.

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

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

Целевые функции игроков: w1 = /1( х1, х2), w2 = /21, х2) непрерывны на компактных множествах X е х2 е Х2 допустимых действий.

Стратегия центра - х1 = ~12), то есть предполагается следующий порядок функционирования: игрок 1 (центр), обладая правом первого хода, сообщает игроку 2 (агенту) план выбора своей стратегии в зависимости от выбранной игроком 2 стратегии х2. После этого второй игрок выбирает действие х2, максимизируя свою целевую функцию с под­ставленной туда стратегией первого игрока, а затем первый игрок - действие ~(х2) .

Стратегия наказания х1н = х1н2) определяется из ус­ловия:

/21 2 )' Х2 ) = ™Щ/2 ' Х2 )-

х1еХ1

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

Гарантированный результат второго игрока (при ис­пользовании первым игроком стратегии наказания) равен

Множество действий второго игрока, обеспечи­вающих ему максимальный выигрыш при использовании первым игроком стратегии наказания есть Е2 = {х2 I /2( х1 (х2), х2)=!2}.

Множество достижимости Б = х2): /212) >Ц} - это договорное множество рассматриваемой игры, то есть множество сочетаний стратегий первого и второго игроков, которые гарантировали бы второму результат, строго больший того, что тот может получить даже при наихуд­ших для него действиях первого игрока (то есть при ис­пользовании первым игроком стратегии наказания).

Наилучший результат первого игрока на множестве

достижимости есть
Принад-

лежность ситуации множеству достижимости гарантирует реализуемость этого результата путем использования стра­тегии наказания.

Определим действие первого игрока, реализующее К - е при выборе вторым игроком рекомендуемого дейст­вия из Б:

fj(xf, x2,) > K - є , (xE, x^ ) є D .

Вычислим M = inf sup f(x1, x2) - гарантированный

x2 єЕ2 xj єХ0

результат центра при применении им стратегии наказа­ния (так как стратегии второго игрока ограничены мно­жеством Е2).

Определим стратегию х1аЕ2), которая реализует (с точностью є) наилучший ответ центра на действие х2 аген­та (є-доминантная стратегия), то есть

fl(XT(X2)) > SUPf1(xi,x2)-Є

Теорема Ю. Б. Гермейера [20]. В игре Г2 наиболь­ший гарантированный результат центра равен max [K, M]. При K > M e-оптимальная стратегия центра

e e

X , при x2 = x2 X (x2), при x2 ^ x,

. При K < M оптимальная стра-

тегия центра заключается в применении оптимальной стратегии наказания.

Каким же образом соотносятся выигрыши центра в играх Г1 и Г2 с одинаковыми функциями выигрыша? Суще­ствуют ли более рациональные для центра методы обмена информацией, дающие ему больший выигрыш? Ответ на эти вопросы дает рассмотрение информационных расшире­ний игры, или метаигр.

Если центр не планирует самостоятельно получить информацию о действии агента, он может первым выбрать действие, реализуя игру Г1. Однако ему можно порекомен­довать и более сложное поведение. Центр может попросить агента сообщить ему свою стратегию Х2 = ~21), которая основана на ожидаемой агентом информации о действии центра. Реализация права первого хода центром состоит в этом случае в сообщении агенту стратегии х (~21)). Эту стратегию можно интерпретировать, как обещание центра выбрать действие х (~21)) при условии, что агент обеща­ет выбирать свое действие в соответствии с ~21). Так образуется игра Г3.

Если центр определяет порядок обмена информацией, он может выбирать, играть ему Г1 или Г3. В обеих играх центр вынужден выбирать действие, не зная действия, выбранного агентом. Можно считать Г3 в некотором роде усложнением игры Г1.

Аналогично тому, как с помощью образования до­полнительной «петли обратной связи» из Г1 была образо-

вана Гз, можно усложнить и игру Г2. Так образуется игра Г4. В ней агент, ожидая от центра, как и в Г2, информацию вида х2), формирует и сообщает центру свою страте­гию х2(~і). Центр, обладающий правом первого хода,

пользуется стратегиями ~ (~2), которые определяют, ка­кую функцию х1(х2) выберет центр в зависимости от со­общения агента ~2.

Таким же способом можно на основе Гз построить игру Г5 и так далее. В каждой из построенных четных игр Г, т = 1, 2, ..., центр использует в качестве стратегий отображения множества стратегий агента в этой игре на множество стратегий центра в игре Г2т-2. Аналогично стратегиями агента являются отображения множества стратегий центра в Г2т на множество стратегий агента в игре Г2т-2.

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

Теорема Н. С. Кукушкина [20, 34]. Максимальный гарантированный результат центра в игре Г при т > 1 равен максимальному гарантированному результату центра в игре Г2. В играх же Г2т+1 при т > 1 максимальный гаран­тированный результат центра равен его максимальному гарантированному результату в игре Г3.

Таким образом, при исследовании гарантированного результата центра можно ограничиться только играми Г1, Г2 и Г3. Кроме того, известно [20, 34], что максимальный гарантированный результат центра в игре Г2 не меньше его гарантированного результата в игре Г3, а тот, в свою оче- редь, не меньше гарантированного выигрыша в игре Г1. Этот факт показывает, что Г2 является «идеальной» игрой для центра. Соответственно, если центр имеет возмож­ность определять порядок и содержание обмена информа­цией и, кроме того, при выборе своего действия знает действие, выбранное агентом, он должен играть Г2. Если центр на момент выбора своего действия не знает действия агента - ему наиболее выгодна игра Г3.

Игры и структуры. Выше мы рассмотрели основные понятия теории игр, перейдя от игр, в которых агенты вы­бирают свои действия одновременно (игра Г0 в нормальной форме или в форме характеристической функции) к иерар­хическим играм, в которых последовательность ходов фик­сирована - первым делает ход центр, а затем - агент. Можно усложнять модель и дальше, переходя к все более сложным играм. Опишем общую картину (рис. П.1.1), которая позво­ляет увидеть логику перехода от более простых к более сложным задачам, чтобы более сложная задача могла быть декомпозирована на более простые.

Если имеется один субъект, принимающий решения (рис. П.1.1 а), то он описывается с точки зрения гипотезы рационального поведения (см. раздел 1.1) как стремящийся максимизировать свою целевую функцию. Далее можно усложнить модель и рассмотреть несколько субъектов на одном уровне (рис. П.1.1 б), описав их взаимодействие игрой Г0 в нормальной форме. Если ввести иерархию, то для двух субъектов (рис. П.1.1 в) их взаимодействие описы­вается игрой Гі, где і = 1, 2 или 3.

Представим себе, что имеется структура «один на­чальник - несколько подчиненных» (рис. П.1.1 г). Взаимо­действие агентов, находящихся на одном уровне, можно описывать игрой Г0. Взаимодействие «начальник - подчи­ненный» описывается игрой Гі. Тогда условно такую

структуру можно представить игрой Гі, определенной на игре Г 0, условно обозначив ее Г і (Г0).

ООО

ГРП

Г і (Г о)

г)

О
о

г,, і = 1,2,3 в)

Г 0

б)

Г о( Г і (Г о))

д)

а)

Г о( Г і (...Г і (Г о)...))

е)

Рис. П.1.1. Игры и структуры

Далее пусть есть несколько начальников (центров) и несколько подчиненных - агентов (рис. П.1.1 д). На ниж­нем уровне агенты играют игру Г0. Над ними центры играют иерархическую игру Г\, но центры в свою оче­редь разыгрывают на своем уровне игру Г0. Итого, полу­чили игру Го(Г (Го)).

Можно взять более сложную структуру с более слож­ным взаимодействием (например, рис. П.1.1 е). Это будет иерархическая игра между уровнями, и «обычная» игра на каждом из уровней: Г0(Г\(...Г\(Г0)...)) .

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

Оказывается, что между играми и структурами существует глубокая связь - момент принятия субъектом решений определяет его «место» в организационной иерархии (см. подробности в [50]).

П.1.4. Рефлексивные игры[34]

Рассмотрим игру, в которой участвуют агенты из множества N = {1, 2, ..., п}. Если в ситуации присутствует неопределенный параметр 9 є О, то структура информи­рованности I (как синоним будем употреблять термины «информационная структура» и «иерархия представле­ний») і-го агента включает в себя следующие элементы. Во-первых, представление і-го агента о параметре 9 - обо­значим его 9, 9 є О. Во-вторых, представления і-го агента о представлениях других агентов о параметре 9 - обозна­чим их 9у, 9у є О, і є N. В третьих, представления і-го агента о представлении і-го агента о представлении к-го агента - обозначим их 9ук, 9ук є О,і, к є N. И так далее.

Таким образом, структура информированности Їі і-го агента задается набором всевозможных значений вида 9г>1 , где і пробегает множество целых неотрица­тельных чисел, і и ..., і є N, а 9у , є О.

1' ' іі 1 --- Іі

Аналогично задается структура информированно­сти Ї игры в целом - набором значений 9гі ^ , где і пробе­гает множество целых неотрицательных чисел, іь ...,іі є N, а 9^ є О. Подчеркнем, что структура ин­формированности Ї «недоступна» наблюдению агентов, каждому из которых известна лишь некоторая ее часть (а именно - Їі). Таким образом, структура информирован­ности - бесконечное п-дерево (то есть тип структуры по­стоянен и является п-деревом), вершинам которого соот­ветствует конкретная информированность реальных и фантомных агентов.

Рефлексивной игрой Г] называется игра, описываемая следующим кортежем [57]:

ГI = N (X) е N,/, (-), е N, О, ]},

где N - множество реальных агентов, X, - множество до­пустимых действий г-го агента, /г (•): О х X' ® Ш1 - его целевая функция, г е N, О - множество возможных значе­ний неопределенного параметра, I - структура информиро­ванности.

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

1) эти элементы известны всем агентам;

2) всем агентам известно 1);

3) всем агентом известно 2) и так далее до бесконечности.

Далее для формулировки некоторых определений и свойств нам понадобятся следующие обозначения:

£+ - множество всевозможных конечных последова­тельностей индексов из N

£ - объединение £ + с пустой последовательностью;

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

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

" г е N " т, о е Е Отгго = Оно .

Эта аксиома означает, в частности, что, зная ОТ для всех т е Е+, таких что |т| = у, можно однозначно найти От для всех т е Е+, таких что |т| < у.

Наряду со структурами информированности Д 1 е N можно рассматривать структуры информированности 1у (структура информированности у'-го агента в представле­нии 1-го агента), Iф и т. д. Отождествляя структуру инфор­мированности с характеризуемым ею агентом, можно сказать, что, наряду с п реальными агентами (г-агентами, где 1 е N со структурами информированности Д в игре участвуют фантомные агенты (т-агенты, где т е Е+, |т| > 2) со структурами информированности 1т = {Ото}, о е Е, существующие в сознании реальных агентов.

Определим фундаментальное для дальнейших рас­смотрений понятие тождественности структур информи­рованности. Структуры информированности 1я и 1т (Я, т е Е+) называются тождественными, если выполнены два условия:

1) ОЯо = Ото для любого о е Е;

2) последние индексы в последовательностях Я и т совпадают.

Будем обозначать тождественность структур инфор­мированности следующим образом: 1Я = 1т.

Понятие тождественности структур информирован­ности позволяет определить их важное свойство - слож­ность. Заметим, что наряду со структурой I имеется счет­ное множество структур 1т, т е Е+, среди которых можно при помощи отношения тождественности выделить классы попарно нетождественных структур. Количество этих классов естественно считать сложностью структуры информированности.

Будем говорить, что структура информированности I имеет конечную сложность V = п(Д если существует такой конечный набор попарно нетождественных структур {ІТі, 1Т2, ..., }, Ті ЄІ+, І Є {1, ..., V}, что для любой

структуры Іа, а є £+, найдется тождественная ей структу­ра I из этого набора. Если такого конечного набора не существует, будем говорить, что структура I имеет беско­нечную сложность: п(І) =

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

Ясно, что минимально возможная сложность струк­туры информированности в точности равна числу участ­вующих в игре реальных агентов (напомним, что по опре­делению тождественности структур информированности они попарно различаются у реальных агентов).

Любой набор (конечный или счетный) попарно нето­ждественных структур ІТ, т є £+, такой что любая структу­ра Іа, а є £+, тождественна одной из них, назовем базисом структуры информированности I.

Если структура информированности I имеет конеч­ную сложность, то можно определить максимальную дли­ну последовательности индексов у такую что, зная все структуры Iт, т є £+, |т| =у , можно найти и все остальные структуры. Эта длина в определенном смысле характеризу­ет ранг рефлексии, необходимый для описания структуры информированности.

Будем говорить, что структура информированности I, у(!) < ¥, имеет конечную глубину у = у(Т), если

1) для любой структуры 1о, о е £+, найдется тождест­венная ей структура !т, т е £+, |т|

<< | >>
Источник: Новиков Д.А.. Теория управления организацион­ными системами. М.: МПСИ, - 584 с.. 2005

Еще по теме ПРИЛОЖЕНИЕ 1. ЭЛЕМЕНТЫ ТЕОРИИ ИГР:

  1. Приложение: Элементы теории некооперативных игр
  2. Элементы теории кооперативных игр
  3. Приложение 3. Рекомендуемая литература по курсу "Жилищное право"
  4. Приложения
  5. Содержание и структура общей теории криминалистики
  6. ПРИЛОЖЕНИЯ
  7. ПРИЛОЖЕНИЯ
  8. 1.2. Стратегия сбыта в контексте общефирменной стратегии: содержание и основные элементы
  9. ПРОЦЕССУАЛЬНЫЕ ТЕОРИИ МОТИВАЦИИ
  10. 1.1.2. Анализ теорий мотиваций