WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 15 |

Множество недоминируемых стратегий непусто и в случае бесконечных компактных множеств стратегий и функций выиг- Лемма 2 [65]. Если в игре n лиц xi [ai,bi ], функции выигрыша, непрерывных по всем переменным [82].

рыша непрерывны по совокупности стратегий и для каждого игроТочно так же, как для чистых стратегий, можно определить и Ki ка частная производная (xi, x-i) существует и везде знакоподоминирование смешанных стратегий. Одна смешанная стратегия xi доминируется другой, если для произвольного вектора смешанных стоянна, то существует РДС. При этом доминантной стратегия xi* стратегий остальных игроков ожидаемая полезность от использоi-го игрока будет стратегия Для вектора стратегий (x1, x2, …, xi-1, yi, xi+1, …, xn) используется обозначение (yi, x-i).

65 реализующаяся ситуация зависит от «правильного» выбора всех Ki ai, xi < 0 стратегий. Из принадлежности ситуации множеству недоминируе xi* = b, Ki, i N. мых по Парето ситуаций не следует, что такая ситуация выгодна i > для всех игроков. Как будет показано ниже при рассмотрении рав xi новесия Нэша, отдельные игроки могут быть недовольны своим Идею леммы 2 можно обобщить на более широкий класс игр.

выигрышем в недоминируемой по Парето ситуации, так как, измеЛемма 3 [65]. Если в игре n лиц xi = [ai, bi ], а функция выигнив в одиночку свою стратегию, они могут увеличить свой выигрыша произвольного игрока i сепарабельна по стратегии этого рыш. Ответные действия других игроков, ущемленных таким поведением, могут вывести ситуацию из множества Парето.

игрока, то есть Ki (xi, x-i ) = Ki0 (xi ) + Ki (x-i ), i N, и Ki0 () имеКак и удаление доминируемых стратегий, равновесие Парето ет единственный максимум на множестве действий Xi, то сущестобычно выделяет достаточно широкое множество ситуаций, в ковует РДС, причем для игрока i его доминантная стратегия:

торых одновременно не может быть увеличен выигрыш всех иг* xi = arg max Ki0 (xi ), i N.

роков. Тем не менее, очевидная рациональность оптимальных по xiX i Парето исходов приводит к мысли, что хорошая теоретикоДля доказательства лемм 2 и 3 достаточно проверить опредеигровая концепция решения должна считать рациональными ление РДС.

только оптимальные по Парето исходы.

Пример 11. «Сравнение оптимальности по Парето и РДС».

3.8. Оптимальность по Парето Рассмотрим игру, в которой участвуют n > 2 игроков со стра«Равновесие» Парето можно назвать, наверное, самым общим тегиями xi [0; 1]. Функции выигрыша игроков: Ki = xi - x.

принципом рациональности. Принцип В. Парето утверждает, что, j ji если для ситуации x существует такая ситуация y, что выигрыш Так как целевые функции сепарабельны, доминантными каждого из игроков при реализации ситуации y не меньше, чем стратегиями всех игроков являются стратегии xi = 1 (см. лемму 3).

при реализации ситуации x, и по крайней мере один игрок получает выигрыш, строго больший, то игроки предпочтут ситуацию Выигрыши игроков при этом будут равны Ki = 2 - n < 0.

y ситуации x. Формально определение выглядит следующим обРавновесие в доминантных стратегиях не оптимально по Паразом.

рето, поскольку при выборе, скажем, xi = 0 все игроки получают Определение 11: Ситуация x* в игре Г называется оптимальнулевой выигрыш вместо отрицательного выигрыша в РДС. • ной по Парето, если для любой ситуации x x*, найдется игрок i, Этот пример показывает, что стремление к общему благу такой, что Ki (x) < Ki (x*).

может вступать в противоречие с индивидуальными интересами.

Этот принцип представляется в некотором смысле полярным, Используя доминантные стратегии, все игроки обеспечивают себе противоположным к равновесию в доминантных стратегиях. Если меньший выигрыш, чем при использовании строго доминируемой РДС представляет собой верх индивидуалистического поведения стратегии xi = 0.

игроков, то равновесие Парето является критерием сотрудничестНеустойчивость оптимальной по Парето ситуации поднимает ва. Действительно, если есть ситуация, которая приносит всем игвопрос о целесообразности расширения рассматриваемой модели рокам не меньший доход, чем существующая, то почему им не игры. Можно, например, включить в модель возможность заклюреализовать более выигрышную для всех них ситуацию Однако чения игроками договора о выборе стратегий. Если этот договор для этого необходимы объединенные усилия всех игроков, так как будет предусматривать наказание за невыполнение соглашения, 67 оптимальный по Парето исход в этой игре будет достижим [51]. Определение 14: Набор смешанных стратегий * * * * Такие игровые модели будут рассмотрены ниже. Аналогичные = (1,,..., ) называется ситуацией равновесия Нэша в 2 n идеи используются для обеспечения устойчивости оптимальных по смешанных стратегиях, если для любого игрока i N и произПарето исходов в повторяющихся играх [21, 33, 52, 58].

вольной смешанной стратегии i справедливо неравенство ~ ~ * * 3.9. Равновесие Нэша Ki (i*, -i ) Ki (i, ), -i ~ Стремление к устойчивости решений является широко расгде Ki () – результат усреднения функций выигрыша игроков по пространенным способом формулирования принципов рациоиспользуемым ими смешанным стратегиям.

нального поведения в теории игр. Устойчивость при этом может Множество равновесий Нэша в чистых стратегиях может пониматься по-разному. Самый популярный принцип рациооказаться пустым для некоторых игр, и возможное отсутствие нального поведения в некооперативных играх рекомендует в каравновесных ситуаций является большим недостатком равновесия честве рациональных исходов использовать ситуации равновесия Нэша в чистых стратегиях. Тем не менее, для равновесия в Нэша. Они характеризуются тем, что отклонение от данной сисмешанных стратегиях справедлив следующий результат туации равновесия одним из игроков не может увеличить его выТеорема 3 [59. ]. Для произвольной дискретной игры сущестигрыша. Можно сказать, что ситуация называется равновесной по вует, по меньшей мере, одно равновесие Нэша в смешанных страНэшу, если она устойчива относительно индивидуального отклотегиях.



нения игроков.

Доказательство [82]. Множество смешанных стратегий кажОпределение 12: Ситуация x*=(x1*, x2*, …, xn*) называется сидого игрока – непустой выпуклый компакт (ограниченное и туацией равновесия по Нэшу (в чистых стратегиях), если для замкнутое множество) в конечномерном пространстве. Обозначим всех i N и xi Xi, справедливо неравенство множество наилучших ответов игрока на произвольную обстанов* * * Ki (xi, x-i ) Ki (xi, x-i ).

ку -i Определение 13: Совокупность всех равновесных по Нэшу си- ~ (8) Ri ( ) = Arg max Ki (i, ).

-i -i туаций игры называется множеством равновесий Нэша.

i Если ситуация x* – равновесие Нэша, то никому из игроков не По теореме 2, это множество представляет собой множество выгодно в одиночку отклоняться от нее. Однако возможно, что, всех вероятностных распределений на множестве чистых стратеобъединившись, игроки могут улучшить свое положение выходом гий – наилучших ответов на заданную обстановку. Поэтому Ri – из равновесия Нэша (см. раздел 3.11).

выпуклое множество, так как оно представляет собой ограниченНапример, в примере 5 «Два начальника» единственным равное линейными неравенствами подмножество выпуклого множеновесием Нэша является ситуация (x1 = x2 = «Эгоист.»). При этом, ства смешанных стратегий [74, 82]. Определим многозначное сопоскольку равновесие Нэша в данной игре не является оптимальответствие ным по Парето, оба игрока могут улучшить свое состояние, выбрав (9) R() = (R1(x-1),..., Rn (x-n )), ситуацию (x1 = x2 = «Сотр.»). Однако, эта ситуация уже не будет которое ставит в соответствие каждой ситуации множество – деравновесной, так как отклонение одного из игроков от этой сикартово произведение множеств стратегий – наилучших ответов туации увеличивает его выигрыш (см. также пример 11). Именно каждого игрока на обстановку, заданную остальными компоненпоэтому сложно ожидать от игроков сотрудничества в этой игре.

тами ситуации. Для произвольной ситуации в смешанных стратегиях, R() является непустым, выпуклым компактом (так как 69 является декартовым произведением непустых, выпуклых компак- На основании полученных результатов можно сформулиротов). вать одно из возможных достаточных условий существования равДля дальнейшего доказательства воспользуемся теоремой новесия в чистых стратегиях:

Какутани. Введем сначала определение:

Теорема 6 [65]. Если в непрерывной игре множества стратеОпределение 15: Многозначное отображение F компакта S в гий Xi – выпуклые подмножества линейных метрических просебя, называется полунепрерывным сверху, если для любых схо- странств, для каждого игрока i функция выигрыша Ki непрерывна дящихся последовательностей kS (k), и kS (k), таких, по всем переменным и строго вогнута по переменной xi, то в этой игре существует равновесие Нэша в чистых стратегиях.

что kF(k), принадлежит F().

Доказательство. Ранее была доказана теорема 2 о том, что Теорема 4 [82] (теорема Какутани о неподвижной точке).

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

выпуклое подмножество S, то существует такой элемент *S, что Тогда и равновесие Нэша будет состоять только из чистых страте*F(*).

гий.

Покажем, что отображение R полунепрерывно сверху.

* Для этого рассмотрим произвольные сходящиеся последоваВведем обозначение X ( ) = Arg max Ki (xi, ) – множе-i -i i xi тельности k и k из определения полунепрерывности сверху.

ство чистых стратегий, которые являются наилучшими ответами Из того, что kR(k) следует, что для произвольной смешан~ ~ на обстановку -i. Пусть имеются два наилучших ответа – xi* Xi* k k ной стратегии i выполнено Ki (ik, -i ) Ki (, -i ). По лемме i и xi** Xi*. Так как оба они являются лучшими ответами на обфункция ожидаемого выигрыша непрерывна по совокупности * ~ ~ становку -i, значит Ki (xi, -i ) = Ki (xi**, -i ), то есть переменных, поэтому Ki (i, -i ) Ki (, -i ), то есть R().

i Ki (xi*, x-i ) (x-i )dx-i = Ki (xi**, x-i ) (x-i )dx-i.

По теореме Какутани, существует неподвижная точка – си- -i -i X X -i - i туация *, такая, что *R(*).

~ ~ Для краткости обозначим этот выигрыш буквой M.

* * Значит, для всех игроков Ki (i*, -i ) Ki (i, -i ), где i – * ** ~ Рассмотрим стратегию xi = xi + (1-)xi, где (0, 1).

произвольная смешанная стратегия. То есть * – это равновесие ~ В силу выпуклости Xi, xi Xi. Ожидаемая полезность от примеНэша. • Аналогичные результаты можно получить и для бесконечных нения этой стратегии:

игр, например, справедлива Ki (~i, -i ) = (~i, x-i ) (x-i )dx-i = x i -i K x Теорема 5 [82]. Если множества стратегий игроков компактX -i ны, а функции выигрыша непрерывны по совокупности переменных (чистых стратегий игроков), то в игре существует, по крайней i -i K (xi* + (1 - )xi**, x-i ) (x-i )dx-i.





X мере, одно равновесие Нэша в смешанных стратегиях. -i В силу строгой вогнутости целевой функции Ki, имеем Доказательство теоремы 5 аналогично доказательству теоремы 3.

71 * венно, все равновесия Нэша этих игр совпадают. Однако рассмотKi (~i, -i ) > (xi, x-i )-i (x-i )dx-i + x i K рение исходных игр дает возможность отдать предпочтение одним X-i из равновесий перед другими. В результате можно отбросить не** + (1-) (xi, x-i )-i (x-i )dx-i.

i K которые из равновесий, усилив, тем самым, предсказание поведеX-i ния игроков. Подробно с такими концепциями решения, как: равСледовательно, Ki (~i, -i ) > M + (1 -)M = M, что невозx новесие по подыграм (subgame perfect equilibria), trembling hand можно, так как M – это максимальный ожидаемый выигрыш. Таperfect equilibria и другими можно ознакомиться в [74, 79, 82].

ким образом, наилучший ответ всегда один, а, значит, и равновеДругой выход заключается в предположении (подтвержденсие Нэша будет равновесием в чистых стратегиях. • ном, кстати, экспериментально [82]) о том, что выбор одного из Итак, как показано выше, множество равновесий Нэша в равновесий Нэша игроки производят на основе некоторой второсмешанных стратегиях не пусто для достаточно широкого класса степенной информации, которая не нашла своего отражения в игр. Однако оно далеко не всегда единственно. постановке задачи. Стремление игроков к выбору одного из равТак, например, равновесие Нэша не единственно в игре «Се- новесий Нэша в результате игры называется эффектом фокальной мейный спор» (см. примеры 9, 14): в ней три равновесия Нэша, точки [40, 74, 82].

два – в чистых и одно – в смешанных стратегиях.

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

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

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

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

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

каком из равновесий окажется управляемая система [25, 51, 56, 57].

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

берет на себя вычисление равновесия Нэша и выбор одной из Пример 12 [56]. «Решение задачи стимулирования».

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

представляется следовать рекомендации «центра». Здесь, как минимум, центр должен знать все целевые функции, а игроки должА.1. i N Ai 1.

+ ны доверять центру в этом вопросе (см. описание реализации этого А.2. i N 1) функция ci() непрерывна по всем переменподхода для задач управления организационными системами в [21, ным; 2) yi Ai ci(y) не убывает по yi, i N; 3) y A’ ci(y) 0;

51, 56, 57]).

4) y-i A-i ci(0, y-i) = 0.

Заметим, что этот подход, по сути дела, нарушает ранее ввеА.3. Функции стимулирования кусочно-непрерывны и приденное предположение о бескоалиционности игры, так как ознанимают неотрицательные значения.

Pages:     | 1 |   ...   | 6 | 7 || 9 | 10 |   ...   | 15 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.