Название: Математические модели принятия решений в экономике - Розен В. В.

Жанр: Экономика

Рейтинг:

Просмотров: 903


Лекция 15. игры п лиц в нормальной форме

Игра п лиц как математическая модель совместного принятия решения в условиях несовпадения интересов. Бескоалиционные иг­ры. Примеры экономических задач, моделируемых бескоалиционными играми. • Принцип оптимальности в форме равновесия по Нэшу. Некоторые особенности принципа равновесия по Нэшу. • Теорема Нэша о реализуемости принципа равновесия в смешанных стратегиях.

К.-устойчивость. Формулировка условия К.-устойчивости в рамках системного описания и на языке стратегий. • Задача 20. Задача рас­пределения ресурсов.

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

чае задается в виде отображения множества ситуаций X = ]~[ Хг во

г=1

множество исходов А. Таким образом, функция реализации каждой ситуации х — [х,..., хп) Є X ставит в соответствие определяемый ею исход F(x) Є Л. В теоретико-игровой терминологии управляю­щие подсистемы называются игроками,а множество Хг — мно­жеством стратегий игрока г (г = 1,п).

Для задания целевой структуры рассматриваемой задачи при­нятия решения необходимо задать оценочную функцию ір\% : А -> К для каждого игрока і. Композиция /, = (ргоЕ называется функцией выигрыша игрока г, а число fl(x,..., хп) есть оценка полезности ситуации (х,..., хп) с точки зрения игрока і.

Итак, математическая модель данной задачи принятия решения имеет вид

Г = (/, (Хг)іе1, Шгеї), (І5"1)

где / = {1,. . ., n} — множество игроков, Хг — множество стратегий ,0-рока г, /, : X —»• К — функция выигрыша игрока г. Такая математическая модель называется игрой п лиц в нормальной форме.

Формирование ситуации в игре Г состоит в выборе каждым игроком і Є I некоторой стратегии хг Є Хг, при этом возника­ет ситуация х = (хг)гєі. Полученную ситуацию каждый игрок і; = 1,тг оценивает со своей точки зрения с помощью функции /г; удобно считать, что /г(х) есть величина выигрыша, получаемого игроком г в ситуации х. Таким образом, игра п лиц может рас­сматриваться как математическая модель совместного приня­тия решения несколькими сторонами, имеющими несовпадающие интересы.

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

Игра Г вида (15.1), в которой п = 2 и множества стратегий игро­ков конечны, называется биматричной игрой; такая игра может быть задана парой матриц А = \а3г\, В — \b3t\ (і — 1,тг; j = 1,ттг), где А — матрица выигрышей игрока 1 ж В — матрица выигры­шей игрока 2. Указанная биматричная игра далее обозначается че­рез Г(^в). Иногда биматричная игра задается одной матрицей фор­мата п х 771, причем элемент, стоящий в г-й строке и j-м столбце этой матрицы должен представлять собой пару вида (а3г, Ъ3), первая компонента которой есть выигрыш игрока 1, а вторая — выигрыш игрока 2 в ситуации (i,j).

Отметим, что в биматричной игре выигрыш игрока 1 может не совпадать с проигрышем игрока 2. В случае, когда это обстоятель­ство имеет место, т.е. когда а3г = —Ъ^ при всех г = 1, п, j — 1, т, Получается матричная игра с платежной матрицей А. Задание мат­рицы В становится здесь излишним.

Замечание. Если в биматричной игре Г(д^) при всех і — j, j — 1, m выполняется равенство aJt +fr? = с, где с — некоторая постоянная то, переходя к биматричной игре Г^д щ по формулам а. = а — с/2 ц Vl = Ь — с/2, получаем игру, эквивалентную первоначальной, которая будет антагонистической.

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

• Пример 15.1 (производство конкурирующей продукции) Два небольших предприятия общественного питания производят однотипную продукцию, которую затем продают на одном рынке. Каждое предприятие может использовать большую или малую по­точную линию. Если оба они используют большую линию, то имеет место перепроизводство продукции, и в результате оба предприя­тия несут убытки в 9денежных ед. Если одно из предприятий ис­пользует большую линию, а другое — малую, то первое предприя­тие получает прибыль в 5 денежных ед., а второе только покрывает убытки. Наконец, если оба предприятия используют малую линию, то оба они получают одинаковую прибыль в 1 денежную ед.

Эта игра также может быть задана парой матриц (А, В), где

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

А =

1 0

5 -9

В

• Пример 15.2 (неантагонистическая конкуренция фирМ-производителей). Рассмотрим ситуацию, описанную в задаче 17, счятая, что теперь целью фирмы В является не разорение фирмы А, а максимизация собственной прибыли. Тогда функция выигры­ша Fb фирмы В будет связана с функцией выигрыша FA фирмы А равенством FB(j,i) = FA(i,j). При этом FA(i,j) + FB(i,j) ф const, г е. такая игра не будет антагонистической.

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

• Пример 15.3 (конкуренция производителей на однотовар-ном рынке). Имеется п фермеров, производящих одинаковый про­дукт (например, зерно). Пусть — максимальное количество зер­на, которое может произвести фермер і, & Хі — количество зерна, которое он произвел фактически (0 < хг < йц). Доход фермера і мо­жет быть представлен в виде сХі, где с — рыночная цена единицы продукта. Как известно, рыночная цена продукта является моно­тонно убывающей функцией от его общего количества; можно счи­тать, например, что при фиксировании всех остальных параметров, определяющих цену, с = k/y/xi + ■ ■ ■ + хп (см. [18]). Тогда доход фермера г будет выражаться функцией fi(x,..., хп) = ,

В результате получаем бескоалиционную игру п игроков (фер­меров), в которой множеством стратегий игрока і является ин­тервал [0, ai], а функция выигрыша в ситуации (хі,. . . ,хп) есть Л(#1, ..., хп).

В этом примере наглядно проявляется отличие теоретико-игровой задачи от оптимизационной. Так, если бы фермеры сда­вали зерно по фиксированной цене с, то решение оптимизационной задачи — задачи максимизации дохода всех фермеров — было бы тривиальным: х* — ai. Однако в уловиях рыночного ценообразова­ния необходим теоретико-игровой подход, учитывающий не толь­ко действия данного игрока, но также и действия всех остальных игроков. Ясно, что оптимальное решение оптимизационной зада­чи х* = ai не будет оптимальным при теоретико-игровом подходе: Перепроизводство продуктов снизит цену, и доход фермеров упадет.

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

п *

примесей может быть рассчитана по формуле q =  VJ с,жг, Где

г = 1

с,...,сп — некоторые постоянные. За загрязнение окружающей среды каждое предприятие платит штраф, величина которого для г-го предприятия пропорциональна доле, которую оно «вклады­вает» в показатель q, т.е. величина штрафа находится по формуле ft(xi,..., хп) = + х q, где к — константа. В результате получа­ем бескоалиционную игру п игроков, в которой функция выигрыша

(здесь         фуНКЦИЯ ПОТерь) ЄСТЬ /г(жі, . . . , Хп).

Можно рассматривать также различные видоизменения функ­ции штрафа (см. [44]), учитывающие дополнительные факторы (на­пример, резкое увеличение штрафа, если показатель q превышает некоторое пороговое значение — величину предельно допустимой концентрации).

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

Определение. Пусть Г — (/, (Хг)гЄ/, (/г)гє/) — игра п лиц, за­данная в нормальной форме. Ситуация х° = (х®,..., ж°) Є X назы­вается ситуацией равновесия в игре Г (равновесием в смысле Нэша), если для всех і Є /, хг Є Хг выполняется условие

/г(х°\хг) < /,(*°). (15.2)

Пояснение. Через ос01| ос, обозначается ситуация, полученная из ситу­ации а;0 заменой ее г-й компоненты х® на стратегию xt. Таким образом, а;01|ж, есть ситуация, возникающая при одностороннем отклонении игро­ка г от ситуации а;0.

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

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

В примере 15.1 имеются две равновесные ситуации: (М, Б) „ (f>, М). Из табл. 15.1 видно, что при одностороннем отклне-цйй от этих ситуаций отклонившийся игрок проигрывает. Напри­мер, если в ситуации (М, Б) игрок 1 заменит свою стратегию М на Б, то возникнет ситуация (Б, Б), в которой он терпит убытки в 9денежных ед.; если же от ситуации (М, Б) отклоняется игрок 2, то его выигрыш уменьшается с 5 до 1 денежных ед.

Замечания. 1. Ситуация равновесия по Нэшу является устойчивой относительно односторонних отклонений игроков (так как отклонивший­ся игрок «наказывается» уменьшением своего выигрыша). Однако, если, например, в биматричной игре от ситуации равновесия отклонятся оба игрока, то может возникнуть ситуация, в которой их выигрыши уве­личатся. Еще больше картина усложняется при переходе к игре п лиц, где п > 2. В такой игре существуют нетривиальные коалиции, т е. ко­алиции, содержащие более одного игрока и отличные от коалиции всех игроков В игре п лиц может иметься нетривиальная коалиция S С / такая, что при переходе от ситуации равновесия х° к некоторой ситу­ации а;1 выигрыши всех игроков из S увеличиваются, причем игроки коалиции 5 могут «своими силами» преобразовать ситуацию х° в ситу­ацию xі. В этом случае ситуация а:0, будучи устойчивой относительно отклонений отдельных игроков, имеет реальные основания быть «разру­шенной» коалицией S, заинтересованной в переходе от х кі'и имеющей возможность этот переход осуществить.

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

2. Для биматричной игры Г(а,в) ситуация (го, Jo) является ситуацией Равновесия по Нэшу тогда и только тогда, когда при всех г = 1,п, J = 1,т выполняеются неравенства

а10 < а3,0,       V  < bJ°          (15 3)

г    —    г0 '     го —    го        /

В частном случае, когда биматричная игра является матричной (т е когда b3t = —а3г), второе из неравенств (15.3) принимает вид a3t° < Qj и в результате приходим к двойному неравенству а30 < а30 < аз'' которое означает, что ситуация (го,Jo) есть седловая точка в nrpf с платежной матрицей А. Таким образом, принцип равновесия мозкио рассматривать как обобщение принципа седловой точки при переходу от класса матричных игр к более широкому классу биматричных игр

Укажем некоторые особенности ситуаций равновесия в бимат­ричных играх по сравнению с седловыии точками в матричных иг­рах (см. лекцию 13, п. 2).

В матричной игре исход в седловой точке равен цене игры, поэтому во всех седловых точках выигрыши игрока одни и те же. В биматричных играх аналогичное свойство для ситуаций равновесия не имеет места. Так, в примере 15.1 для игрока 1 его выигрыши в ситуациях равновесия (М, Б) и (Б, М) различны.

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

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

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

3. Перейдем теперь к вопросу реализуемости принципа равно­весия для класса биматричных игр, т.е. к вопросу существова­ния в них ситуаций равновесия. Так как матричная игра являет­ся частным случаем биматричной, причем ситуации равновесия в этом случае «превращаются» в седловые точки, то вопрос сущест­д0вания в любой биматричной игре ситуации равновесия в чистых ^ратегиях решается сразу отрицательным образом (так как даже fle всякая матричная игра имеет седловую точку в чистых страте­гиях)-

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

Пусть Г(дв) — биматричная игра с матрицами выигрышей А я В формата п х га; будем считать, что множеством чистых стра- тегий игрока 1 является {1,...,тг} и множеством чистых стра- тегий игрока 2 является {1,...,га}. Под смешанной стратегией игрока 1 в игре Т(А,В) понимается любой вероятностный вектор х — (х,..., хп) Є Sn, а под смешанной стратегией игрока 2 — любой вероятностный вектор у = (уі,---,Ут) Є Sm. Если игрок 1 использует смешанную стратегию х, а игрок 2 — смешанную стра- тегию у, то в силу независимости соответствующих распределений, вероятность появления ситуации   равна произведению хгу3 и

в этой ситуации игрок 1 получает выигрыш а, а игрок 2 — выиг­рыш Ь31. Таким образом, в ситуации в смешанных стратегиях (х, у)

исходом для первого игрока будет случайная величина t\ =

ХіУу j

( b>

а для игрока 2 — случайная величина £2=1 1

При построении смешанного расширения игры Т(а,В) в качестве выигрышей игроков 1 и 2 берутся математические ожидания этих случайных величин:

 

FA(x,y)=         (ХгУзК,     FB{x,y)=  (ХгУ])К- (15'4)

г=1,п г=1,тг j — l,m j=l,jn

В результате получается новая игра игроков 1 и 2, в которой Множествами их стратегий будут множества вероятностных век-Торов Sn и Sm соответственно, а функции выигрыша игроков опре­деляются равенствами (15.4). Построенная игра называется сме­шанным расширением игры Г(А<в) и обозначается через Г^.в). Поскольку стратегии и ситуации игры Г(дв) имеют естественную интерпретацию в игре Г^д), обычно говорят, что векторы х є s у Є Sm являются смешанными стратегиями в игре Г(дв), (х,у) ситуацией в смешанных стратегиях в игре Г(А щ, а значения фуй1с ций выигрыша FA(x, у) и Fe{x,y) — выигрышами игроков 1 и в ситуации (х, у) в смешанных стратегиях в игре Т^а,В)-

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

Теорема 15.1 (теорема Нэша). Всякая биматричная игра име-em ситуацию равновесия в сметанных стратегиях.

Заметим, прежде всего, что ситуация (ж0, у0) Є Sn х Sm является ситуацией равновесия в смешанных стратегиях тогда и только тогда, когда при любых i£ Sn, у Є Sm выполняется

FA(x,y0)

Доказательство того, что в любой биматричной игре имеется ситу­ация равновесия в смешанных стратегиях, впервые дал американский математик Джон Нэш в 1951г. Идея доказательства чрезвычайно прос­та и состоит в применении теоремы Брауэра о неподвижной точке. Вос­произведем кратко метод доказательства. Пусть S(„,m) = 5„ X Sm — множество ситуаций в смешанных стратегиях в игре Г^а,в) ■ Определим отображение Т : 5(„im) —> S(n^m) следующим образом. Для произвольной ситуации [х,у) Є 5(Піт) рассмотрим числа 5г,а3  (i = 1,п; j = l,m), где

дг = max{FA(i,y) - FA(x,y),0},

(15.6)

ffj = max.{FB{x,j) - FB(x,y),0}.

Числа Si и o-j имеют прозрачный теоретико-игровой смысл: Si есть вы­года, которую получает в ситуации (х, у) игрок 1 при замене смешанной стратегии х чистой стратегией і в случае, когда эта выгода имеется (т.е. когда FA(i, у) — FA(x,y) > 0), и 0 — в противном случае. Аналогично ин­терпретируются числа <7j. Далее положим

/ _     Xj + Sj    , _    yj + ffj

Xi —   „        >            У} —  m •

)t=i      »=i 1

ЯСНО, ЧТО Векторы Х   = (х'і, . . . ,x'n) И у' = (y'l, ■ ■ ■ ,y'm) ЯВЛЯЮТСЯ верОЯТ-

ностными векторами, т.е. х' Є Sn и у' £ Sm. Полагаем Т(х,у) = (а/,у ) Т есть преобразование множества 5(„ т) в себя. Легко проверить, что это преобразование непрерывно. Замечая, что 5(П т) является выпук­лым компактным подмножеством арифметического пространства К"+,п> лучаем, что выполнены все предположения теоремы Брауэра о непо-цжной точке. Следовательно, согласно теореме Брауэра, у преобразова­ла Т существует хотя бы одна неподвижная точка. Нетрудно убедиться, чТо неподвижными точками преобразования Т являются ситуации рав-я0Весия в смешанных стратегиях игры Г(д в) и только они.

Замечание. Так как доказательство теоремы Нэша основано на те­реме Брауэра, оно является чистым доказательством существования и ge дает метода нахождения ситуаций равновесия. Несмотря на это, уста­новленный в теореме Нэша результат имеет принципиальное значение, так как он «подводит фундамент» под важнейший принцип оптималь­ности — принцип равновесия.

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

Рассмотрим вначале формулировку общего понятия устойчивос­ти для задачи принятия решения в рамках системного описания. Пусть / — множество управляющих подсистем (игроков), воздей­ствующих на некоторую управляемую систему, и Л — множест­во ее состояний. Всякое непустое подмножество S С I называется коалицией. Будем предполагать, что для каждой коалиции S С I задано отношение достижимости 5s, характеризующее возмож­ности коалиции S по изменению состояний системы, и отношение предпочтения ш$, указывающее предпочтения коалиции 5* на мно­жестве состояний системы.

Формально отношение достижимости Ss коалиции S есть бинарное отношение на множестве состояний системы А, причем условие (аі, а2) Є Ss означает, что коалиция 5* может собственными силами (без участия игроков, не входящих в коалицию 5"), перевести систему из состояния cl в состояние а2. Через 6s(а) обозначим множество всех а' Є А, для которых (а, а') Є Ss-

Отношение предпочтения коалиции S есть бинарное отно­шение u>s на множестве состояний А, причем условие a' >~ШБ а означает, что состояние а' является для коалиции S более пред-Почтительным (в строгом смысле), чем состояние а.

Набор объекта вида

 

G = (/, A, (Ss)sci, (us)sci) (15.7)

будем называть коалиционной структурой над множество^ игроков /. Сформулируем теперь основное понятие. Пусть К. ~-некоторое фиксированное семейство коалиций игроков /.

Определение. Состояние а* Є А называется К.-устойчи. вым, если для любой коалиции S Є /С в множестве 6s(а*) не существует состояния, которое является более предпочтитель­ным для коалиции S, чем состояние а*.

Формально: состояние а* является /С-устойчивым, если не су- ществует такого состояния а' Є А, что а'   а* и (а*, а') Є 3$, где S Є 1С.

Поясним содержание понятия ^-устойчивости. Пусть система находится в состоянии а*. Рассмотрим произвольную коалицию S С I. Коалиция S будет стремиться перевести систему из состо­яния а* в некоторое другое состояние а' Є А в том случае, если, во-первых, состояние а' для коалиции S более предпочтительно, чем состояние а* (т.е. a' yws а*), и, во-вторых, коалиция 5* может собственными силами осуществить переход из состояния а* в состо­яние а' (т.е. (а*,а') Є 6s). На содержательном уровне соединение условий а' УШБ а* и (а*, а') Є 6s соответствует соединению «же­ланий и возможностей» коалиции S. /С-устойчивость состояния а* означает, что в этом состоянии ни для одной коалиции S Є /С такое соединение «желаний и возможностей» по переходу из а* в а' не име­ет места. Таким образом, если система находится в состоянии а*, то ни одна из коалиций S Є /С не будет стремиться перевести систему в некоторое другое состояние. Другими словами, в К,-устойчивом состоянии а* не возникает угрозы со стороны коалиций S € 1С по разрушению этого состояния.

Рассмотрим теперь три наиболее важных конкретизации поня­тия /С-устойчивости.

Семейство 1С состоит из всех одноэлементных коалиций: К. — {{г} : і Є /}. Тогда /С-устойчивость состояния а* означает его устойчивость относительно отклонений отдельных игроков и представляет собой равновесие в смысле Нэша.

Семейство коалиций /С состоит из единственной коалиций всех игроков: К. — {/}. В этом случае /С-устойчивость состояния а* означает отсутствие такого состояния а' Є А, которое было бы

 

gojiee предпочтительным, чем состояние а* для коалиции / всех игроков; это есть оптимальность по Парето.

3)   Семейство К,  состоит  из  всех  непустых коалиций: £={5: 0 ^ S С /}. В этом случае /С-устойчивость называет-■g сильным равновесием.

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

Переформулируем теперь рассмотренные выше понятия /С-устойчивости для игры Г, заданной в нормальной форме (15.1). В этом случае множество X = \ Хі ситуаций игры Г рассматри-

ієі

вается как множество состояний системы. Посмотрим, какой вид в данной модели приобретает отношение достижимости и отноше­ние предпочтения коалиций.

а)         Отношение достижимости 5s коалиции S характеризует воз- можности коалиции S по «преобразованию» одних ситуаций игры в другие. Если игроки коалиции S действуют совместно, то они могут договориться о выборе любого набора стратегий где х{ є Х{. Будем обозначать такие наборы через xs, а множество всех таких наборов (т.е. Г] Хг) рассматривать как множество стра-

ieS

тегий коалиции S. Через x0||a;s обозначим ситуацию игры (15.1), которая получается из ситуации х° заменой тех ее компонент, кото­рые соответствуют игрокам из 5, на соответствующие компоненты стратегии xs- Итак, если игроки коалиции S действуют совместно, то они в состоянии преобразовать произвольную ситуацию х° Є X в ситуацию вида х°||х5, где xs Є f| Хі. Получаем, что в рассмат-

риваемом случае

Ss(x°) = {x°\xs : ^єДі,}. (15.8)

ieS

б)         Отношение предпочтения uis коалиции S в данном слу- чае может быть «построено» из отношений предпочтения игроков, составляющих коалицию 5*. Наиболее естественный способ такого Построения основан на отношении доминирования по Парето (см. Лекцию 5). Будем считать, что ситуация х1 является более пред- почтительной для коалиции S, чем ситуация х2, если для каждого

р°зен в.в.

225

і Є S выполнено неравенство fi(xl) > ft(x2), причем хотя бы одного г Є о неравенство должно выполняться как строгое:

х1^!2   Л(хг)>Л(^2) (15.9

Рассмотрим теперь некоторые конкретизации понятия /С-устойчивости для случая игры Г вида (15.1).

Пусть /С состоит из всех одноэлементных коалиций. Тогда М-устойчивость ситуации х° в игре Г означает, что для каждого г Є I ни в одной ситуации х°||хг, где хг Є 1„ не имеет места неравенство /г(х°\хг) > Л (я0), т.е. ft(x°\xt) < ft(x°). Это условие есть, в точности, равновесие по Нэшу для игры Г (см. п. 2).

Пусть /С состоит из единственной коалиции всех игроков Тогда условие /С-устойчивости ситуации х° сводится к тому, что не существует такой ситуации х1 Є X, для которой при всех і є / выполняется неравенство fi(xl) > /г(х°), причем хотя бы одно неравенство является строгим. Указанное условие есть условие Парето-оптимальности (см. лекцию 5) ситуации х° в множестве X всех ситуаций игры Г (в качестве оценочной функции критерия г = 1,тг здесь выступает функция выигрыша игрока г).

Пусть К. состоит из всех коалиций игры Г. Тогда условие М-устойчивости ситуации х° состоит в том, что для любой коали­ции S С / не существует такой стратегии щ£ Г] Хг, при которой

для всех г Є 5 имеет место неравенство /г(ж0j|ars) > Л (я0), причем хотя бы для одного индекса г Є S неравенство должно быть стро­гим. Таким образом, сильная устойчивость ситуации х° в игре Г означает отсутствие такой коалиции S С 7, которая могла бы пре­образовать ситуацию х° в какую-либо другую при единогласной заинтересованности в этом всех своих членов.

5. Задача 20. Задача распределения ресурсов.

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

 

Имеется два варианта задачи распределения ресурсов, соответ-сТВуЮіиих централизованному и децентрализованному распределе­нию- Рассмотрим оба эти варианта.

Вариант 1 (задача централизованного распределения ресур­сов)- Здесь предполагается, что управляющий орган (центр) об-лаДает некоторым запасом ресурсов, который задается вектором j, = (б1,. • •, Ьт), где Ь3 — запас ресурса типа j. Пусть Т> — множес-

п

твовсех наборов ресурсных векторов (xi,. .., хп), причем      Хг = Ь

1=1

^неравенство понимается как покомпонентное). Вектор хг инте-дретируется как ресурсный вектор, выделенный центром г'-му пред­приятию. Каждому набору (х,... ,хп) Є Т> соответствует вектор эффективностей (fi(xi),..., fn(xn)). В результате получаем задачу многокритериальной оптимизации (см. лекцию 5), в которой V — множество альтернатив, /, — оценочная функция по критерию і = 1, п. Оптимальное решение такой задачи ищется в множест­ве ее Парето-оптимальных альтернатив. При некоторых ограни­чениях на область допустимых альтернатив Т> задача нахождения Парето-оптимальных альтернатив может быть сведена к задаче на-

n

хождения максимума обобщенного критерия / = ^2 atfi, где аг > О

i=i

(см. лекцию 5).

Рассмотрим более подробно вариант децентрализованного рас­пределения ресурсов.

Вариант 2 (задача перераспределения ресурсов). В этом слу­чае предполагается, что каждое предприятие і = 1,тг обладает на­чальным запасом ресурсов, задаваемым вектором хг = (х,. .., х™). Предприятие может продавать принадлежащие ему ресурсы, а так­же покупать любые ресурсы по установленным ценам при един­ственном ограничении: общая стоимость покупаемых ресурсов не Должна превышать общей стоимости начального запаса ресурсов этого предприятия. Пусть р = (р1,.. . ,рт) — вектор цен, где р> — стоимость единицы ресурса j-ro типа (j = l,m). Если предприя­тие і покупает ресурсный вектор хг = (х,.. ., х™), то общая стои­мость покупки есть р1х + ■ ■ • + ртх^г; она представляется в виде скалярного произведения (р, хг). Аналогично, стоимость начально­го запаса ресурсов предприятия і равна (р, хг) и указанное выше ограничение принимает вид

(р,хг)<(р,Хі). (15.10)

8*

227

Условие (15.10) называется условием платежеспособности спроса при векторе цен р.

Определение. Набор (х*,..., где х* — ресурсный век

тор предприятия і = 1,тг, а р* — вектор цен, называет^ состоянием экономического равновесия, если выполняющСа следующие два условия.

При каждом і - 1,тг ресурсный вектор х* максимизируй функцию эффективности предприятия і по множеству всех ре. сурсных векторов этого предприятия, находящихся в пределах его платежеспособного спроса по ценам р*:

Л«) = тах{/г(а;г) : (р*, хг) < (p*,xt)}. (15.11)

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

х, (15.12)

где х* = ^2 х*, х = ^2 хг {неравенство (15.12) понимается как

г = 1 г=1

покомпонентное).

Рассмотрим теперь игру Гп+і игроков 1,..., п, п + 1, в которой первыми п игроками являются предприятия, а в качестве (тг+ 1)-го игрока выступает ценообразующий орган. В этой игре стратегия­ми каждого предприятия являются его ресурсные векторы, а стра­тегиями ценообразующего органа — векторы цен. Ситуациями иг­ры Гп+і считаются такие наборы (х,. .., хп,р), в которых каждый вектор хг является ресурсным вектором предприятия г, удовлетво­ряющим условию платежеспособности спроса при векторе цен р Цель игрока і состоит в максимизации функции эффективности /, (г = 1,п), а цель игрока (п + 1) — в минимизации взвешенного дисбаланса, т.е. в минимизации функции

n п

fn + l{xi,...,Xn,p) ~ (p,^Txt - 5ZXt) = (Р>Х~ Х)-

i=l        t = l

Покажем, что экономическое равновесие можно представить как равновесие по Нэшу в игре Г„+і. Действительно, пусть (xi,. ■ ■ , хп, р) — ситуация равновесия по Нэшу в игре Гп+1. Тогда при каждом г = 1,п для всех ресурсных векторов хг, удовлетворя­ющих условию (р, хг) < (р,хг), выполняется неравенство

/,(*,) < /,(£,), (I5-13) а для игрока п + 1 при произвольном векторе цен р имеет место ^равенство

(р, х — х) > (р, х - х). (15.14)

Убедимся, что набор {х,...,хп,р) является состоянием эко­номического равновесия. Неравенства (15.13) означают, что при каждом і = 1,п ресурсный вектор хг максимизирует функцию эф­фективности предприятия г по множеству всех ресурсных векторов, находящихся в пределах его платежеспособного спроса по ценам р. Таким образом, условие 1) выполнено. Проверим условие 2). Так как набор (її,..., хп,р) является ситуацией в игре Гп+і, то при всех j = 1,п выполнено условие платежеспособности: (р, хг) < (р,хг). Суммируя эти неравенства по і   =   l,n и используя линей-

ность скалярного произведения, получаем (р, ]Г хг — ]Г хЛ < О,

^    i=l  г=1 '

т.е. (р, х, — х) < 0. Учитывая неравенство (15.14), имеем (р, х — х) < 0. Так как вектор цен р произволен, то отсюда следует, что х ^ х, и условие 2) проверено. Итак, всякая си­туация равновесия по Нэшу игры Гп+і является экономическим равновесием.

Обратно, пусть (х*,..., х*п, р*) — состояние экономического рав­новесия. В силу (15.11), получаем, что в состоянии экономического равновесия отклонение игрока і = 1,п от стратегии х* приводит к уменьшению его выигрыша. Остается установить уменьшение (точнее, неувеличение) выигрыша игрока п + 1 при его односторон­нем отклонении от стратегии р*. Будем предполагать, что функции эффективности /г (г = 1,п) являются строго монотонно возраста­ющими (т.е. из уг >Раг хг следует /г{уг) > /і(хг))- Тогда в состо­янии экономического равновесия не может быть «недопотребления

n n

ресурсов», откуда      x* =      хч т-е- х* = х- ^ этом случае по

1=1 г=1

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

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


Оцените книгу: 1 2 3 4 5