WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 7 | 8 || 10 | 11 |   ...   | 15 |

чает создание всеми игроками информационной коалиции – реА.4. Функция дохода центра непрерывна по всем переменным гулирующего органа. Тем не менее, он довольно широко испольи достигает максимума при ненулевых действиях агентов.

зуется некоторыми исследователями [82].

Если стимулирование каждого агента зависит от действий В теории управления широко распространен метод повторевсех агентов, то определение множества равновесий Нэша PN() ния игры, или «метод фиктивного разыгрывания» для реализаимеет вид:

ции равновесных ситуаций. При этом игрокам разрешается разыгN рывать игру многократно, возможно, меняя стратегии от тура к PN() = {yNA| iN yiAi i(yN) – ci( y ) туру. При этом оказывается, что стремление к максимизации выN N i(yi, y-i ) - ci(yi, y-i )};

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

РДС yd A' определяется условием: yid Ai – доминантная Оправданность такого подхода объясняется тем, что при проведестратегия i-го агента тогда и только тогда, когда нии экспериментов – так называемых, имитационных игр [4, 9, yi Ai, y-i A-i i( yid, y-i) – ci( yid, y-i) i(yi, y-i) – ci(yi, y60], – игроки ведут себя таким образом, что, после проведения достаточного числа повторений игры (при этом можно даже не Если при заданной системе). стимулирования у всех агентов i выплачивать игрокам их выигрыш, а лишь ставить их в извест- имеется доминантная стратегия, то говорят, что данная система ность о его величине) стратегии игроков сходятся к одному из рав- стимулирования реализует соответствующий вектор действий как новесий Нэша34. Можно заметить, что рефлексивные рассуждения, РДС.

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

N EN() = {yNA' | iN yiAi i( yiN ) – ci( y ) Сходимость различных процедур выбора агентами стратегий к равN i(yi) – ci(yi, y-i )}, новесию Нэша и другие эффекты динамики коллективного поведения исследовались в [4, 9, 50, 60].

75 Содержательно, при использовании системы стимулирования РДС yd A определяется условием: yid Ai – доминантная стра* центр использует следующий принцип декомпозиции: он предтегия i-го агента тогда и только тогда, когда * лагает i-му агенту: «выбирай действие yi, а я компенсирую тебе yi Ai, y-i A-i i( yid ) – ci( yid, y-i) i(yi) – ci(yi, y-i).

затраты, независимо от того какие действия выбрали остальные Фиксируем произвольный вектор действий агентов y* A’ и агенты, если же ты выберешь любое другое действие, то возрассмотрим следующую систему стимулирования:

награждение будет равно нулю». При использовании системы * * ci ( yi, y-i ) + i, yi = yi стимулирования ** центр предлагает i-му агенту: «выбирай дей*i(y*, y) =, i 0, i N.

* 0, yi y* ствие yi, а я компенсирую тебе затраты, считая, что остальные i * Если стимулирование каждого агента зависит только от его агенты также выбрали соответствующие компоненты – y-i, если собственного действия, то, фиксировав для каждого агента обже ты выберешь любое другое действие, то вознаграждение будет становку игры, перейдем от * к системе индивидуального стиравно нулю». Используя такую стратегию, центр декомпозирует мулирования следующим образом: фиксируем произвольный векигру агентов. • тор действий агентов y* A’ и определим систему стимулирования:

3.10. Вычисление равновесий Нэша * * ci ( yi, y*i ) + i, yi = yi Чтобы для конкретной игры вычислить равновесие Нэша в **i(y*, yi) =, i 0, i N.

чистых стратегиях, необходимо проверить наличие собственного 0, yi y* i значения оператора R (см. (9)) для собственного числа 1. Оператор Справедливы следующие утверждения [56]:

R – отображение произвольной игровой ситуации на совокупность 1) При использовании центром системы стимулирования * векнаилучших ответов игроков на задаваемую для них этой ситуацией тор действий y* является РДС. Более того, если i > 0, i N, то y* – обстановку. Таким образом, для бесконечных игр, задача сводится единственное РДС.

к нахождению вида этого оператора и решения уравнения 2) При использовании центром системы стимулирования ** век(10) x* = R(x*).

тор действий y* является равновесием Нэша.

Пример 13. Вычисление равновесий Нэша для игры «Фермеры на 3) Вектор оптимальных реализуемых действий агентов y*, фигуобщем поле».

рирующий в качестве параметра в системах стимулирования * и Целевые функции игроков в этой игре Ki = xi (120 - x1 - x2).

**, определяется в результате решения следующей задачи:

Функции выигрыша вогнуты по стратегиям игроков, поэтому в y* Arg max {H(t) – (t) }, этой игре существует равновесие Нэша в чистых стратегиях (см.

c i tA iN теорему 6).

а эффективность этих систем стимулирования равна следующей Наилучший ответ игрока при фиксированном поведении проn тивника вычисляется в результате нахождения максимума функвеличине: K* = H(y*) – ( y*) –, где := ci i ции выигрыша по стратегии этого игрока, то есть i=1 iN xi* = Ri (x-i ) = arg max Ki (xi, x-i ). Частная производная в этой 5) Класс (с параметром y*) систем стимулирования * и ** являxi X i ется -оптимальным.

77 * * [ x2 y2 ] Ki (xi, x-i ) x-i точке равна нулю, то есть = 0, значит xi* = 60 -, Пусть матрица выигрышей имеет вид x1 3, 1 0, 0.

xi 2 0,0 1, i = 1, 2. y * * - x2 / 2 Смешанная стратегия первого игрока определяется одним x1 = Получили систему уравнений, решением ко * * числом p – вероятностью выбора им первой стратегии, смешанная = 60 - x1 / xстратегия второго, соответственно, числом q. Вычисляем:



* * торой является пара стратегий x1 = x2 = 40, приводящих к выигK1(x1, qx2 + (1- q) y2 ) = 3q, K1(x2, qx2 + (1 - q)y2) =1 - q.

рышам K1 = K2 =1600.

Таким образом, при q < 0.25, наилучшим ответом первого игЗаметим, что при условии безусловного сотрудничества игрока является стратегия y1, при q > 0.25 – стратегия x1. При роков, то есть в случае объединения их выигрышей и выбора q = 0.25 обе стратегии равнозначны с точки зрения ожидаемого стратегий из условия максимизации нового критерия выигрыша. То есть наилучший ответ первого игрока:

K = K1(x1, x2) + K2(x1, x2), стратегии игроков были бы x1 = x2 = 30.

0, q < 0. 1, При этом K = 3600, то есть при распределении выигрыша p* (q) = q > 0.25.

поровну на долю каждого из игроков достается по 1800 единиц, [0,1], q = 0. что больше, чем при конкуренции. Эта оптимальная по Парето Аналогично, наилучший ситуация, не является, однако, равновесной, так как неустойчива ответ второго игрока:

по односторонним отклонениям игроков от оптимальной по Па0, p < 0. рето стратегии. • 1, p > 0.75.

Система (10) может давать несколько решений, и все они бу- q*( p) = дут равновесиями Нэша. [0, 1], p = 0. Кроме того, уравнения системы (10) могут оказаться зависиИзобразив эти зависимости мыми. Это значит, что равновесий Нэша в этой игре бесконечное Рис. 6.

на плоскости p q, получим множество. Например, для игры двух лиц с функциями выигрыша рисунок 6. Точки A, B, C 1; x пересечения ломаных линий на рисунке и будут соответствовать Ki = 1(x1 + x2 - c) - xi, где 1(x) := 0; x < 0, x1, x2,c[0,1], мно трем равновесиям Нэша этой игры:

жество равновесных ситуаций описывается равенством x1 + x2 = c. (x1, x2), (y1, y2), (0.75 x1 + 0.25 y1, 0.25 x2 + 0.75 y2). • Такая ситуация характерна, в основном, для игр с разрывной 3.11. Сильное равновесие Нэша функцией выигрыша (см. примеры в [56, 57, 82]).

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

каждый игрок имеет две стратегии.

Определение 16: Для игры n лиц обозначим множество игроПример 14. «Нахождение равновесий Нэша в смешанных ков через N = {1, 2, 3, …, n}. Любое непустое подмножество S стратегиях в игре «Семейный спор».

данного множества, включая и само N, называется коалицией.

79 Понятно, что для игры n лиц возможны 2n–1 коалиций. Мносят как от действий xi Xi всех игроков, так и от их типов жество всех возможных коалиций обозначим 2N. Обозначим ri i, i N.

* (x-S, xS ) ситуацию, в которой игроки, не входящие в коалицию Определение 18: Профилем типов игроков называется вектор S N, используют стратегии xi* ( i N \ S ), а игроки из S испольr = (r1, r2, …, rn) =.

i iN зуют стратегии xj ( j S ).

* * Определение 19: Набор функций x* (r) = (x1 (r),..., xn (r)) будем Определение 17: Ситуация x* называется сильно равновесной называть равновесием Нэша35 (в чистых стратегиях) в игре с папо Нэшу, если для любых коалиций S N и любых раметрически заданными функциями выигрыша, если для каждоxS Xi найдется участник коалиции i S, такой, что го фиксированного профиля r типов игроков для каждого игрока iS * i N и для всех его стратегий xi Xi, справедливо неравенство Ki (x* ) > Ki (x-S, xS ).

* K (x (r), r) Ki ( xi, x* (r), r).

Как видно из определения, сильное равновесие отличается от i -i равновесия Нэша тем, что игроки не только поодиночке не могут Пример 15. «Простая задача распределения ресурса».

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

и двух агентов (игроков). Центру распределяет между игроками Довольно просто показать, что все сильные равновесия Нэша, ресурс, для чего собирает от них заявки si [0;1] (i = 1, 2) и выесли они существуют, оптимальны по Парето.

дает каждому игроку ресурс по формуле Тем не менее, при всех привлекательных чертах сильного s1 + s(11) xi = si -.

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

В этом механизме центр «недодает» игрокам ресурс относительно заявленных ими потребностей, причем, чем больше сооб3.12. «Параметрическое» равновесие Нэша щенная общая потребность в ресурсе s1 + s2, тем существеннее стаДля того чтобы вычислить равновесие Нэша, исследователь новится «недодача».

игры должен точно знать функции выигрыша игроков. В задачах Игроки имеют типы ri [0; 1]. Функции выигрыша игроков управления, однако, часто встречается ситуация, когда на момент зависят от полученного ими ресурса и типа следующим образом:

исследования игры функции выигрыша известны исследователю игры не полностью. Эта ситуация характерна для механизмов xi(12) Ki = 2xi -.

управления с сообщением информации [10, 64] (см. пример 2).

ri Неточную информацию о функциях выигрыша игроков приПараметр ri [0; 1] можно интерпретировать как количество нято описывать с помощью понятия типа игрока. Рассмотрим ресурса, оптимальное для игрока, так как именно при xi = ri достиследующую игру n лиц, в которой каждый из игроков имеет некогается максимум его выигрыша. Центр не знает типы {ri} игроков.





торый тип ri i из множества i возможных типов данного игрока i. Будем считать, что все множества типов i компактны, Для задач управления оказывается существенным, что равновесная i N. Функции выигрыша игроков Ki = Ki (x1,...xn,r1,...,rn) завипо Нэшу стратегия каждого из игроков зависит от типов всех игроков [55, 64, 80, 85].

81 Сообщение достоверной информации в механизмах планироСтратегиями игроков в этой игре являются их заявки si на вания является равновесием в доминантных стратегиях для всех ресурс. Подставив (11) в (12), можно выразить функции выигрыша r, если: r, i N, si i, s-i -i, выполняется через стратегии, получив игру в нормальной форме. В этой игре функции выигрыша игроков зависят не только от их стратегий, но i ( (ri, s-i ), ri ) i (i (si, s-i ), ri ).

i и от типов ri.

Для механизма активной экспертизы справедливо следующее Задача исследователя заключается в том, чтобы предсказать, утверждение [55, 64]: для каждого r [d, D]n равновесие Нэша насколько это возможно, равновесные заявки игроков.

s*(r) имеет следующую структуру:

Можно показать, что в зависимости от типов r1 и r2 игроков равновесие Нэша в этой игре будет задаваться заявками D, если x < ri;

* * 1) si = (s1 (), s2 ()) = d, если x > ri;

(1.5r1 + 0.5r2, 0.5r1 +1.5r2 ); 3r1 + r2 2, r1 + 3r2 2) если d < si < D, то x = ri.

(13).

(4r1 / 3 + 0.25, 1); 3r1 + r2 > 2, r1 1/ = Определим для каждого k = 0, n векторы сообщений:

(1, 4r2 / 3 + 0.25); r1 + 3r2 > 2, r2 1/ k первых экспертов сообщают d;

(1, 1); r1 > 1/ 2, r2 > 1/ s(k) = (n - k) последних экспертов сообщают D Равновесные заявки зависят от типов {ri} игроков. Если в и вычислим последовательность точек Wk = (s(k)).

дальнейшем исследователь получит точную информацию о типах игроков, то, подставив значения типов игроков в (13), сможет по- Упорядочим экспертов в порядке возрастания ri. В [9] докалучить точное равновесие Нэша этой игры. зано, что всегда найдется такой номер q N, что либо Однако полученный результат можно использовать и другим rq [Wq, Wq-1 ], либо rq > Wq-1.

способом. Пусть исследователю известна та же информация, что и Общий результат, характеризующий решение задачи эксперцентру. Пусть игра разыграна один раз, и центр получил от игротизы [9, 55, 64], гласит, что итоговое решение в равновесии имеет ков заявки (s1, s2). Тогда, зная (13), центр может узнать типы игвид: x = max min (rq, Wq-1 ).

роков. Так, например, если обе заявки меньше 1, центр может опkN ределить типы игроков по формуле:

Следовательно, для любой процедуры активной экспертизы r1 = 0.75 s1 – 0.25 s2, r2 = 0.75 s2 – 0.25 s1.

найдется эквивалентный прямой механизм (см. определение в Если обе заявки равны 1, центр может сделать вывод, что первой главе). • типы обоих игроков превышают 0.5. Аналогично можно восстановить типы и для случаев, когда лишь одна из заявок равна 1.

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

Пример 16 [9, 55]. «Решение задачи «Экспертиза».

Области на рисунке 7 представляют собой различные концепПриведем решение задачи примера 2.

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

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

в чистых стратегиях Сильное равновесие Нэша Равновесие в доминантных ГЛАВА 4. ИГРЫ С НЕПОЛНОЙ стратегиях ИНФОРМИРОВАННОСТЬЮ При определении игры в нормальной форме (см. раздел 3.2) предполагалось, что на момент выбора стратегий игроки имеют полную информацию о виде функций (матрице) выигрыша других Рис. 7. Сравнение концепций решения некооперативных игр игроков.

Pages:     | 1 |   ...   | 7 | 8 || 10 | 11 |   ...   | 15 |










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

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