WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 11 | 12 || 14 | 15 |

xi iS фигурацию x на новую конфигурацию y, то такое заявление реальНа множестве эффективных распределений существует единно может угрожать целостности коалиции T и называется угрозой ственное распределение, такое, что для любого эффективного игрока 1 игроку 2. В свою очередь, игрок 2, интересы которого распределения x вектор e() предпочтительнее e(x) в смысле лек- ущемлены подобным сценарием, может заявить игроку 1, что в 113 случае подобных его действий он может предложить игроку 3 та- получат не меньше своей первоначальной доли. Если для этого кую конфигурацию z коалиционной структуры {{1}, {2, 3}}, что членам L в качестве партнеров нужны некоторые партнеры коалиигрок 3 получит больший доход, чем в конфигурации y, а сам иг- ции K (или даже некоторые члены K) в конфигурации угрозы, то рок 2 получит не меньше, чем в исходной конфигурации x. Таким им дают не меньше, чем они получали в коалиционно рациональобразом, игрок 2 выдвигает контругрозу, «защищающую» его до- ной конфигурации угрозы.

лю x2. Для математического описания этой идеи введем следую- Определение 46: Конфигурация называется устойчивой, если щие определения. на каждую угрозу произвольной коалиции K против любой другой коалиции L найдется контругроза коалиции L против коалиции K.

Пусть = {T1,...,TN } – некоторая коалиционная структура, а K Определение 47: Множество всех устойчивых конфигураций – произвольная коалиция. Тогда партнерами коалиции K назовем называется решением в угрозах и контругрозах (или решением по множество P(K,) = {i : i Tk, Tk K }.

Ауману-Машлеру [72]).

Таким образом, игрок i – партнер коалиции K в Г, если он входит в ту же коалицию, что и какой-либо из игроков K. Смысл 5.14. Роль информированности этого определения состоит в следующем: чтобы члены коалиции K Как отмечалось ранее, на современном этапе развития теории могли получить свою долю в коалиционно рациональной конигр не найдено единого понятия решения, которое для всех класфигурации (x, Г), им необходимо согласие только своих партнеров.

сов игр давало бы однозначное указание, какая из стратегий является оптимальной для игроков. Это относится как к некоопеПусть (x, Г) – коалиционно рациональная конфигурация в ративной теории игр, так и к кооперативным моделям. Возможно, игре v, а K и L – непустые непересекающиеся подмножества некочто из-за огромного многообразия игровых ситуаций подобная торой коалиции Tk. Тогда угрозой коалиции K против коалиобщая концепция не существует вообще.

ции L называется коалиционно рациональная конфигурация (y, U), Имеющиеся концепции решения (равновесие Нэша, Паретоудовлетворяющая условиям: P(K,U ) L =, yi > xi для всех доминирование, C-ядро и пр.) могут применяться в основном i K, yi xi для всех i P(K,U ). лишь для определенных классов игр. Поэтому при исследовании каждой конкретной задачи необходимо выбирать концепцию реПусть (x, Г) – коалиционно рациональная конфигурация в шения, которая будет использоваться. При ее выборе необходимо игре v, а K и L – те же коалиции, что и в предыдущем определемаксимально использовать специфику задачи и имеющуюся в раснии. Если (y, U) – угроза коалиции K против коалиции L, то поряжении ЛПР информацию (см. главу 1).

контругрозой коалиции L против коалиции K называется коалиционно рациональная конфигурация (z, V), удовлетворяющая условиям: K P(L,V ), zi xi для всех i P(L,V ), zi yi для всех i P(L,V ) P(K,U ).

То есть члены коалиции K, выдвигая угрозу против L, претендуют на то, что они смогут получить больше путем перехода к новой коалиционно рациональной конфигурации, и что их новые партнеры будут согласны с этим. Члены коалиции L могут выдвинуть контругрозу, если они сумеют найти третью коалиционно рациональную конфигурацию, в которой и они, и все их партнеры 115 ГЛАВА 6. ИЕРАРХИЧЕСКИЕ ИГРЫ числе допускающая последовательное принятие решений игроками в рамках некоторого фиксированного порядка ходов.

Требования применения теории игр к задачам управления в 6.1. Игры с фиксированным порядком ходов ОС приводят, таким образом, к необходимости разработки опиОписание игр в нормальной или в байесовой форме во многих сания игры и концепций решения, ориентированных именно на случаях может оказаться громоздким. В том числе, для многих эти случаи.

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

мых базовых моделей. При их рассмотрении очень важно, однако, Причина этих сложностей состоит, в частности, в том, что придерживаться единого подхода к описанию игры. Такой подход, модель «классической» теории игр, на самом деле, не всегда теория иерархических игр, был сформулирован в работах является самой простой. Предположение об одновременном Ю.Б. Гермейера и его учеников [21-24, 27, 33, 35]. Ниже привовыборе игроками своих стратегий значительно усложняет дятся некоторые результаты теории иерархических игр двух лиц.

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



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

возможных игровых ситуациях.

Критерии эффективности (целевые функции) первого и втоТак, в примере 1 (задача стимулирования) с одним агентом рого игроков обозначим w1 = f1(x1, x2 ) и w2 = f2(x1, x2 ) соответмножество стратегий центра Xц будет состоять из всех допустимых ственно. Выигрыши игроков зависят от их действий x1 и x2 из функций стимулирования, то есть будет множеством всех кусочномножеств действий X10, X.

непрерывных неотрицательных функций ( y), y A. Множество Во всех моделях иерархических игр считается, что первый игвсех стратегий агента еще сложнее – оно состоит из всевозможных ответов на заданное поведение центра, то есть является множест- рок (центр) имеет право первого хода. Его ход состоит в выборе ~ вом отображений X A. В построенной таким образом игре стратегии x1. Понятие стратегии существенно отличается от поняц тия действия и тесно связано с информированностью первого игравновесие Нэша ищется в виде пары функций – контракта рока о поведении второго игрока – агента. Под стратегией игро{(), y()}. Но, так как задачи стимулирования очень распрострака здесь и далее понимается правило его поведения, то есть правинены в управлении, то для их плодотворного рассмотрения необло выбора конкретного действия в зависимости от содержания и ходима соответствующая концепция решения (см. ниже), в том конкретного значения той информации, которую он получит в 117 * * процессе игры. Выбирать же собственно действие центр может и Определение 48 : Пара действий (x1, x2) в игре Г1 называется после выбора действия агентом.

равновесием Штакельберга, если Самая простая стратегия центра состоит в выборе непосред* (33) x1 Arg max f1(x1, x2 ), ственно действия x1 (если поступления дополнительной инфорx1X1,x2R2 ( x1) мации о действии агента в процессе игры не ожидается), более * * * ~ (34) x2 R2 (x1 ) = Arg max f2 (x1, x2 ), сложная – в выборе функции x1(x2) (если в процессе игры ожи- x2X дается информация о действии агента). Также стратегия центра то есть R2(x1 ) – функция наилучшего ответа агента на действие может состоять в сообщении агенту некоторой информации, нацентра.

пример, информации о планах своего поведения в зависимости от Равновесие в игре Г1 отличается от равновесия Штакельберга выбора действия агентом. При этом агент должен быть уверен, что (33) тем, что при определении оптимальной стратегии первого первый игрок может реализовать эту стратегию, то есть что игрока вычисляется минимум по множеству R2 (x1 ) :

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

x1 Arg max min f1 (x1, x2 ) [21].

x1X1 x2R2 ( x1) Например, если агент (выбирающий стратегию вторым) не ожидает информации о действии центра, то реализация права Равновесие по Штакельбергу реализуется, если агент выбирает первого хода центра может состоять в сообщении им агенту действие, максимизируя свой выигрыш при известном ему на ~ функции x1(x2). Такое сообщение может рассматриваться как момент принятия решения действии центра, а центр, зная о таком ~ поведении агента, выбором действия x1 максимизирует свой обещание выбрать действие x1 = x1(x2) при выборе агентом дейвыигрыш, считая заданной реакцию агента на свои действия.

ствия x2. Тогда стратегия агента состоит в выборе действия в за~ Кроме того, видно, что, максимизируя свой выигрыш по ~ висимости от сообщения центра, x2 = x2(~1(.)). Если при этом x x2 R2(x1 ), центр, по сути, рассчитывает на благожелательность агент доверяет сообщению центра, он должен выбрать действие агента, то есть на то, что агент из множества равнозначных для * x2, реализующее max f2 (~1(x2 ), x2 ).

x x2Xнего действий R2(x1 ) выберет наиболее благоприятное для центра Игра с описанным выше порядком функционирования назы- действие.

вается для краткости игрой Г2 (примером такой игры служит, как Будем считать множество равновесий Штакельберга решенираз, задача стимулирования в условиях информированности центра ем игры Г1.

о действии агента – см. теорему 19). 0 Теорема 17 [21]. Если в игре Г1 множества действий X1, X Если центр не ожидает информации о действии агента, и это компактны, функции выигрыша f1, f2 непрерывны, то в этой игре известно агенту, то стратегия центра состоит, как уже было ска* существует по крайней мере одно равновесие Штакельберга.

зано, просто из выбора некоторого действия x1. Стратегия агента Справедливость теоремы 17 следует непосредственно из суще~ * состоит в выборе x2 = x2(x1 ) (он делает ход вторым, уже зная ствования в условиях теоремы максимумов (33), (34).• действие центра). Такая игра называется игрой Г1 (это, например, В игре Г1 агент выбирает действие в условиях полной инфорта же задача стимулирования, но уже в условиях отсутствия у мированности, уже зная действие центра. Максимизация выигрыцентра информации о действии агента).





ша выбором своего действия является здесь частным случаем приРассмотрим сначала игру Г1. менения принципа МГР. Равновесное по Штакельбергу действие 119 * * центра также дает ему гарантированный результат, если центр max fi (x1, x2 ) fi (x1, x2), i {1, 2}, j i.

xi X, уверен в том, что агент выбирает свое действие в соответствии с i x R (xi ) j j (34) и принципом благожелательности. Таким образом, равновесТеорема 18 [65]. Если в игре двух лиц имеются хотя бы два ные стратегии как центра, так и агента, являются для них и гараноптимальных по Парето равновесия Нэша, в которых вектора вытирующими.

игрышей отличаются, то в этой игре имеет место борьба за первый Пример 20 [65]. «Нахождение равновесия Штакельберга».

ход.

В игре примера 9 («Семейный спор»), если первый игрок Для игры «Семейный спор» условия теоремы 18 выполнены, имеет право первого хода (является центром), то равновесием поэтому в этой игре каждый игрок заинтересован в том, чтобы Штакельберга будет ситуация (1, 1), дающая ему выигрыш 4. • выбирать действие первым (см. пример 20).

В этой игре право первого хода дает центру преимущество Тем не менее, во многих случаях соответствующее игре Гперед агентом. Однако это не всегда так.

поведение центра нельзя назвать эффективным. Если в задаче Пример 21. «Невыгодное для центра равновесие Штакельберстимулирования (пример 1) центр будет первым выбирать дейстга». В антагонистической игре «чет-нечет» с матрицей вие (стимулирование агента, уровень зарплаты), а затем уже агент (1, -1) (-1, 1) будет выбирать свое действие при заданном стимулировании, (-1, 1) (1, -1) единственное равновесие Штакельберга будет состоять в том, что центр ничего не будет платить агенту, а агент, соответственно, не имеются два равновесия Штакельберга: (1, 2) и (2, 1). Оба они будет работать. Эффективное решение этой проблемы в условиях, дают центру, делающему ход первым, выигрыш –1. Однако в этой когда центр не может в момент принятия решения наблюдать игре есть равновесие Нэша в смешанных стратегиях, дающее действие агента, приводится ниже, в разделе «Метаигры». В слуобоим игрокам нулевой выигрыш.

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

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

К этой игре сводятся многие модели управления, например, задача Однако ситуация, когда первый ход дает преимущество, все стимулирования в условиях полной информированности [57]. Для же более типична. Тогда, если порядок ходов определяется самими наглядности ход доказательства теоремы и вводимые при этом игроками, между ними возникает борьба за лидерство. Игре двух понятия демонстрируются на примере именно этой задачи. В лиц в нормальной форме можно поставить в соответствие две левой колонке приводятся выражения для произвольной игры типа игры Г1 (игры первого порядка), отличающиеся последоваГ2, в правой – их описание в терминах задачи стимулирования.

тельностью ходов. Тогда борьба за лидерство (первый ход) определяется выгодностью перехода от исходной игры к какой-либо из иерархических игр первого порядка.

Теорема 19 [21]: (Теорема Ю.Б. Гермейера).

Определение 49: В игре двух лиц имеет место борьба за пер- Определение необходимых для формулировки теоремы поня* тий:

вый ход, если не существует ситуации (x1, x* ), для которой Целевые функции игроков: Пусть 121 вие x2, максимизируя свою ции при заданном контракте w1 = f1(x1, x2), A(1-e-x2 )-B-x1,x2 >f1(x1,x2) =, целевую функцию с под- (обещании центра).

w2 = f2 (x1, x2 ).

-x1,x2 = ставленной туда стратегией 0 x1 X1, x2 X.

2 x1 первого игрока, а затем - C, x2 < 0.f2 (x1, x2 ) = x - x2, x2 0.5.

При доказательстве будем первый игрок – действие ~ считать, что f (x1, x2 ) неx1(x2 ).

Это – задача стимулирования прерывна по x1 при любом Стратегия наказания Стратегией наказания в данном второго рода [55], где x1 играет x2. н н случае будет отказ центра выплаx1 = x1 (x2) определяется из роль зарплаты, выплаченной чивать зарплату, так как при люцентром (игроком 1) работнику условия бом действии x2, минимум f2 досн (агенту, игроку 2). При этом x2 – f2(x1 (x2),x2) = min f2(x1, x2).

0 тигается при нулевой зарплате x1Xэто результат работы, от которо(x1 = 0).

го зависит доход цен- Если стратегий наказания несколько, то будем назытра A(1 - e- x2 ), где A – ценовой вать оптимальной стратекоэффициент, B – постоянные гией наказания ту из них, затраты центра. Затраты работна которой достигается ника считаются равными C<0.максимум выигрыша перпри малых (x2<0.5) действиях, а вого игрока.

дальше быстро растут.

Гарантированный результат Наилучшее действие, которое sup f (~1 (x2 ), x2 ) > L2, x1 X10 = [0,10] – это ограничеx второго игрока (при ис- может выбрать работник при x X 2 ние по заработной плате, более пользовании первым игро- нулевой зарплате, принадлежит 10 единиц она быть не может.

Pages:     | 1 |   ...   | 11 | 12 || 14 | 15 |










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

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