WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 15 |

Данная игра, как правило, не имеет равновесия по Нэшу даже в простейших случаях. Например, пусть количество игроков – 3, функция f (x) 1, a = 0, b = 1. Тогда, если стратегии трех игроков совпадают, то любой из них может увеличить свой выигрыш с 1/3 до величины, сколь угодно близкой к, или больше, незначительно отклонившись от общей стратегии. В противном случае существует игрок, стратегия которого не совпадает со стратегией любого другого игрока, и является наибольшей или наименьшей. Такой игрок может увеличить свой выигрыш, сдвигая свою стратегию от края отрезка и приближая ее к стратегиям других игроков.

Но если мы при тех же самых условиях рассмотрим любое четное количество игроков, то для такой игры равновесия Нэша существуют, например: x2k = x2k–1 = b + (a – b)(2k – 1)/n, k = 1, …, n/2.

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

2.2.3. Равновесие в безопасных стратегиях – определения Введем понятие равновесия, более широкое, чем строгое равновесие Нэша [37], совпадающее с ним там, где оно существует, и позволяющее искать решения поставленной задачи. Сначала дадим общие определения, потом разъясним их на примерах. Пусть задана игра с множеством игроков i N = {1, …, n}, множеством действий x = (x1,..., xn) и значениями выигрышей Ki(x). Зафиксируем игровую ситуацию x* = (x*1,..., x* ).

n Определение 2. Ситуация x* содержит угрозу игроку i со стороны игрока j, если xj: Kj(xj, x* ) Kj(x*) и Ki(xj, x* ) < Ki(x*);

-j -j при этом ситуация x* называется угрожаемой, а ситуация (xj, x* ), -j так же как и стратегия xj, – угрожающей игроку i со стороны игрока j.

Определение 3. Множеством Wi(x*) предпочтительных выборов iго игрока с учетом угроз относительно ситуации x* называется множество его стратегий xi таких, что для любого игрока j i и любой его стратегии xj выполнено Ki(xi, xj, x* ) Ki(x*).

-ij Определение 4. Стратегия x*i игрока i называется стратегией безопасной порядка 0 при заданной обстановке x*, если ситуация x* не со-i держит угроз игроку i;

множеством Zi(0)(x* ) обозначается совокупность всех стратегий xi, -i безопасных порядка 0 при заданной обстановке x* ;

-i множеством Yi(0)(x*) называется множество Zi(0)(x* ) Wi(x*).

-i Комментарий. Множество Z есть множество стратегий, безопасных при заданной обстановке, а множество Y – множество стратегий, безопасных относительно игровой ситуации. Второе множество более широкое, так как включает такие отклонения от x*, которые сами по себе не являются безопасными, но все содержащиеся в них угрозы предпочтительней исходной ситуации. Различие двух множеств становится существенным, когда ситуация x* оказывается более проигрышной, чем все возможные угрозы.

Определение 5. Стратегия x*i игрока i называется стратегией безопасной порядка m при заданной обстановке x*, если j i:

-i либо в ситуации x* игрок j не угрожает игроку i, либо x*j Yj(mj)(x*), mj < m, и любая угрожающая игроку i стратегия xj Yj(mj)(x*), причем хотя бы для одного j выполняется вторая часть условия и mj = m–1;

множеством Zi(m)(x* ) обозначается совокупность всех стратегий xi, -i безопасных порядка m при заданной обстановке x* ;

-i множеством Yi(m)(x*) называется множество Zi(m)(x* ) Wi(x*).

-i Комментарий. Это определение означает, что игрок, строящий свою безопасную порядка m стратегию, знает множества безопасности с меньшим порядком своих партнеров, и предполагает, что они не будут из них выходить.

Определение 6. Ситуация x* называется равновесием в безопасных стратегиях (РБС), если i, mi: x*i – безопасная порядка mi стратегия, и x*i arg max Ki (xi, x* ). При этом РБС называется простым, если все со-i xi Yi( mi ) ( x*) ставляющие его стратегии имеют порядок безопасности 0, и сложным (m1, m2, …, mn), если среди составляющих его стратегий {xi}, i N, имеющих порядки безопасности mi, найдется хотя бы одна, для которой mi >0.

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

Сформулируем простейшие утверждения, поясняющие введенную систему определений.

Утверждение 5. Строгое равновесие Нэша является РБС.

Доказательство. Если x* – строгое равновесие Нэша, то для j, xj x*j Kj(xj, x* ) < Kj(x*). Это значит, что по определению 1 все страте-j гии являются безопасными порядка 0.

Утверждение 6. Если стратегия x*i – безопасная порядка m, при заданной обстановке x*, то x*i0, x*i1, …, x*im – 1 x* – стратегии имеющие -i -i порядок безопасности соответственно 0, 1,…, m – 1.

Доказательство. Если имеется x*i, безопасная порядка m стратегия, то по определению 2 должно существовать im–1 такое, что x*im–1 Yim–1(m– 1) (x*). Применив Определение 2 к стратегии x*im–1 и так далее, получаем необходимость существования x*im -2,..., x*i1, x*i0.

Замечание. Из последнего утверждения становится ясной структура РБС и способ его построения. Сначала ищутся безопасные стратегии нулевого порядка, существование которых необходимо для безопасных страте гий более высоких порядков, каждая из которых выстраивается на основе уже построенной стратегии предыдущего порядка безопасности.



2.2.4. Примеры игр с равновесием в безопасных стратегиях 2.2.4.1. ПРИМЕРЫ БИМАТРИЧНЫХ ИГР Пример 1. Матрицы выигрышей игроков следующие:

0 1 - K1 = ; K =.

1 -1 2 1 Ситуация игры (x1, x2) = (1, 1) является простым РБС, так как отклонение от него первого игрока увеличивает целевую функцию второго, а отклонение от него второго игрока уменьшает его собственную целевую функцию. Других простых РБС в этой игре нет. При (x1, x2) = (1, 2) первому игроку угрожает опасность того, что второй игрок выберет стратегию 1, увеличив свой выигрыш и уменьшив выигрыш второго. При (x1, x2) = (1, 1) первому игроку угрожает опасность, что второй выберет 2. При (x1, x2) = (2, 2) второму игроку угрожает опасность, что первый выберет 1.

Теперь рассмотрим сложные РБС в этой игре. Множества безопасных стратегий игроков: Z1(0)(x2=1) = {1}, Z1(0)(x2=2) = {2}, Z2(0)(x1=1) = {1, 2}, Z2(0)(x1=2) = {1}. Если второй игрок выбрал безопасную стратегию x2 = 1, то первый, предполагая, что второй не выйдет из множества безопасных стратегий порядка 0, может выбрать безопасную стратегию первого порядка x1 = 2. Таким образом, (x1, x2) = (2, 1) являются безопасными стратегиями с (1, 0) порядками. Других сложных РБС в этой игре нет. При (x1, x2) = (1, 2) угроза второго игрока выбрать стратегию 2 не выводит его из области безопасных стратегий. При (x1, x2) = (2, 2) отклонение первого игрока x1 = опасно само по себе, не принадлежит множеству Z1(0)(x2 = 2), но угроза для первого перейти из (1, 2) в (1, 1) недейственна относительно (2, 2), так как K1(1, 1) = 0 > K1(2, 2) = –1, то есть {x1 = 1} Y1(0)(2, 2).

Пример 2. Добавим к матрицам предыдущей игры строку и столбец:

0 1 - 2 -1 - K1 = 1 -1 - 2; K2 = 1 2 - 2.

- 2 - 2 -1 - 2 - 2 - В игре появляется новое простое РБС (x1, x2) = (3, 3), являющееся равновесием Нэша. Других равновесий при этом не появляется, так как ситуации (1, 3), (2, 3), (3, 1), (3, 2) очевидно не выгодны никому. На примере этой игры введем алгоритм проверки существования РБС в биматричной игре.

Шаг 1. Выпишем все угрозы, существующие в этой игре: (1, 2) (1, 1), (2, 1) (2, 2), (2, 2) (1, 2). Множество угроз удобно отображать на направленном графе, вершинами которого являются ситуации игры, а угрозам соответствуют Рис. 8. Граф угроз биматричной игры ребра, направленные из угрожаемой ситуации в угрожающую. Для рассматриваемой игры такой граф приведен на рисунке 8. Все вершины графа, из которых не выходит ни одного ребра, будут соответствовать игровым ситуациям, безопасным порядка 0 для обоих игроков. Не все такие ситуации будут простыми РБС, но простые РБС следует искать только среди них.

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

Z1(0)(x2=1) = {1, 3}, Z1(0)(x2=2) = {2, 3}, Z1(0)(x2=3) = {1, 2, 3}, Z2(0)(x1=1) = {1, 2, 3}, Z2(0)(x1=2) = {1, 3}, Z2(0)(x1=3) = {1, 2, 3}.

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

Шаг 4. Из выделенных ситуаций выберем РБС, исключая два случая.

Во-первых, положения, для которых существует угроза отклонения игрока, принадлежащего множеству Yi(mi)(X*), но не принадлежащих более узкому множеству Zi(mi)(X* ). В нашей игре такой ситуацией является (2, 2). Отбра-i сывая такие наборы стратегий, мы исключаем ситуации, которые «безопасны» только потому, что настолько плохи для игроков, что любое отклонение от них, даже с учетом угроз, может лишь увеличить выигрыш. Вовторых, ситуации, хотя и являющиеся безопасными, но доминируемые при отклонении стратегии одного из участников ситуациями с такими же порядками безопасности игроков. В данной игре такими являются стратегии (1, 3), (2, 3), (3, 1), (3, 2). В результате остаются три РБС: (1, 1) с порядками безопасности (0, 0), (2, 1) (1, 0), (3, 3) (0, 0).

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

Пример 3.

0 0 0 0 1 K1 = 3 - 3; K2 = - 3 3.

1 2 - 3 3 0 3 - В этом примере имеются следующие РБС (с порядками безопасности):

(1, 1) (0, 0), (1, 3) (0, 1), (3, 1) (1, 0). Здесь в простом РБС выигрыши обоих игроков нулевые. При переходе к сложным равновесиям увеличивает выигрыш тот игрок, который переходит к стратегии первого порядка безопасности, сумев навязать партнеру сохранение им безопасной стратегии нулевого порядка.

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

Пример 4.

1 1 - K1 = ; K2 =.

1 1 0 - В этой игре есть два равновесия Нэша: (1, 1) и (1, 2) – и одно простое РБС (2, 1). Пример показывает, что возможны нестрогие равновесия Нэша, не являющиеся РБС.

2.2.4.2. СОРЕВНОВАТЕЛЬНАЯ СИСТЕМА СТИМУЛИРОВАНИЯ Рассмотрим с позиций РБС модель соревновательной системы стимулирования, для простейшего случая линейных затрат, описываемую в [62;





90; 105].

Постановка игровой задачи. Имеются n активных элементов (АЭ, игроков). АЭ номера i выбирает действие xi x = (x1,..., xn). Его целевая функция является разностью функций стимулирования и затрат i(xi) = i(xi) – ci(xi). Функция затрат ci(xi) = ki xi, k1 k2... kn >0. Функция стимулирования i(xi) = qli, где размеры премий упорядочены по возрастанию 0 = q1 < q2 <... < qn = 1, а место li определяется по правилу: место, занятое участником i, лучше (больше) места, занятого участником j при xi > xj или при xi = xj, если i > j».

В [105], первой публикации на данную тему, доказано, что эта игра не имеет равновесных по Нэшу ситуаций, и предложен способ построения Срешений игры, основанный на учете игроками взаимных угроз. Понятие Срешения вводится следующим образом: «Пусть X (x0) – множество ситуаций x, при которых при всех i = 1,..., n места Qi = Qi(x0) и ни при каком i участнику i невыгодно бороться на {(x || xi)} за места Qi Qi(x0). Тогда назовем x0 С-решением, если 1) x0 X (x0) и 2) i(x0) = max i (x) xX ( x0 ) (i = 1, 2,..., n)» [105, с. 87]. Это определение С-решения эквивалентно для условий поставленной задачи определению простого РБС, причем множеству X (x0) в терминах определения РБС соответствует совокупность множеств Yi(0)(x*), i N; условию 1) –условие безопасности нулевого порядка стратегий x*i; условию 2) – требование xi Yi(0)(x*): Ki(xi, x* ) Ki(x*) –i (смотри определения 2, 3 и 4).

В [90, с. 78-85] С-решение данной задачи приводится в следующем виде (с точностью до конкретных буквенных обозначений) [там же, с. 80]:

i - q q j j- x*1 = 0, x*i =.

j=2 k j-В [90] показано, что никому из игроков невыгодно отклоняться от этих выборов. Если какой-либо игрок отклонится от x*i в положительную сторону, то он уменьшит свою целевую функцию, если какой-либо игрок отклонится от x*i в отрицательную сторону, то выйдет из множества безопасных стратегий, так как более слабому игроку i–1 станет выгодно конкурировать с ним за занимаемое им место i.

Следует обратить внимание, что если для этой задачи использовать сложные РБС, то среди них окажется много «плохих» ситуаций, например, x*i = 0, i N.

2.2.4.3. ПРИМЕР ИГРЫ БЕЗ РАВНОВЕСИЯ В БЕЗОПАСНЫХ СТРАТЕГИЯХ Приведем пример игры, в которой вообще нет безопасных стратегий.

Рассмотрим игру, описанную в разделе 2.2.2, изменив значения Ii следующим образом:

xi Ii= f (x)dx, i 1, x i-x1 b I1= f (x)dx + f (x)dx.

a xl Покажем, что в такой игре нет безопасных стратегий нулевого порядка (и следовательно, безопасных стратегий вообще). Рассмотрим игрока i.

Если li > 1 (игрок выбрал стратегию, совпадающую с выборами других игроков), то ему выгодней выбрать xi = xi –, если xi a, либо xi = b – в противном случае, где – малая величина. При этом он получает выигрыш Ii –, вместо Ii /li. Если li = 1 (игрок i единственный выбрал стратегию xi), то ему выгодней выбрать xi = b +, увеличивая свой выигрыш на f (xi).

Таким образом, всем игрокам при выборе стратегии выгодно как можно ближе сдвигаться к своему соседу справа, без совпадения своего xi с его, и перескакивая при достижении правого конца отрезка [a, b] в левый, образуя «хоровод».

2.2.5. Исследование задачи нахождения стратегий банков 2.2.5.1. ВОЗМОЖНЫЕ НЕРАВНОВЕСНЫЕ СИТУАЦИИ Теперь вернемся к рассмотрению задачи поставленной в разделе 2.2.2.

для разъяснения тех трудностей, которые заставили ввести определение РБС. Смысл игры заключается в том, что имеется некоторый ресурс, распределенный на отрезке в соответствии с f (x), каждый игрок выбирает точку на этом отрезке и функцией его выигрыша будет та доля ресурса, которая окажется в промежутке точек, ближайших к выбору этого игрока.

Рассмотрим возможные изменения стратегии участника игры, то есть ситуации, которые препятствуют существованию равновесия Нэша в данной игре. Пусть игрок k выбрал стратегию xk и решает, можно ли ее улучшить, выбрав новую стратегию xk. Могут иметь место два случая. Может оказаться так, что новая стратегия получается из старой путем небольшого смещения xk = xk + или xk = xk –. При этом она лежит в той же области, что и старая, ее положение относительно выборов других игроков и особых точек функции f (x) (справа или слева) не изменится, границы интеграла целевой функции лишь слегка (на /2) сместятся. Назовем такое изменение стратегии «сдвигом». Новая стратегия также может быть выбрана в совершенно новой области отрезка [a, b] так, что интегрируемая область целевой функции окажется на новом месте, между другими игроками. Назовем такое изменение стратегии «скачком».

Введем обозначения. Пусть xik перенумерованы так, как указано при постановке задачи в разделе 4.2. Индекс k и величины K относятся к игрокам, индекс i и величины I – к стратегиям. Двойной индекс ik, обозначает номер стратегии i игрока k. Как k, так и i упорядочены по возрастанию номеров игроков и стратегий. Введем дополнительные обозначения:

xi (39) I – = f (x)dx, i 1, i ( xi -1 + xi ) / xl I – = f (x)dx, a ( xi + xi +1 ) / I + = f (x)dx, i l, i xi b I + = f (x)dx.

l xl Kmin = min Kk, Kmax = max Kk.

1kn 1kn Рассмотрим для xi возможные случаи, которые приводят к неравновесности той или иной ситуации.

1. Если 2Kk < Kmax, то для игрока выгодно изменить стратегию скачком xk = xmax, получив выигрыш Kmax. Значит, необходимым условием того, что ситуация будет равновесием, является Kk Kj, k, j.

Pages:     | 1 |   ...   | 5 | 6 || 8 | 9 |   ...   | 15 |










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

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