WWW.DISSERS.RU

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

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


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

2. Если Kk < I +, либо Kk < I –, то игроку выгодно изменить свою страi i тегию скачком xk = xi + (или xk = xi – ), получив выигрыш Kk = I+ + i (или Kk = I– + ). Необходимое условие равновесия Kk I +, Kk I –, i, k.

i i i 3. Пусть игрок 1 (или n) – единственный игрок, выбравший стратегию x11 (или xln). Такому игроку выгодно изменить свою стратегию сдвигом x1 = x1 +, или xn = xn -, увеличив свой выигрыш приблизительно на /2 f ((x1 + x2) / 2) или /2 f ((xn - 1 + xn) / 2). Эта ситуация препятствует существованию равновесия Нэша для многих игр (см. пример в разделе 2.2.2).

4. Если игрок k – единственный, выбравший стратегию xik, ik 1, ik l, и f ((xk – 1 + xk) / 2) f ((xk + xk + 1) / 2), то игроку выгодно изменить стратегию сдвигом xk = xk – или xk = xk + (в зависимости от того, где значение f (x) больше). При этом он увеличивает свой выигрыш приблизительно на /2 |f ((xik – 1 + xik) / 2) – f ((xik + xik + 1) / 2)|. При этом даже если значения f (x) на границах области i-ой стратегии равны, то равновесие будет существовать, только если разность производных функции f (x), взятых на левом и правом концах этой области, неотрицательна. Эта ситуация также приведет к отсутствию равновесий Нэша для многих игр (например, для случая строго монотонной функции f (x)).

5. Пусть xi = xik и эту же стратегию выбрал еще один игрок; если I + I -, то игроку выгодно изменить свою стратегию сдвигом, получив i ik вместо Ii /2 выигрыш max {I – –, I + – }. Необходимое условие равновеi i сия в этом случае I + = I –.

ik ik 6. Пусть при выполнении необходимого условия из предыдущего случая, выполняется дополнительное условие f ((xik - 1 + xik) / 2) f ((xik + xik + 1) / 2). Тогда игроку выгодно изменить свою стратегию сдвигом в сторону возрастания f (x): xk = xk+ (или xk = xk – ), увеличив свой выигрыш приблизительно на max{f ((xik – 1 + xik) / 2), f ((xik + xik + 1) / 2)}.

7. Пусть I + = I –, f ((xik – 1 + xik) / 2) f ((xik + xik + 1) / 2), и либо ik ik f ((xik - 1 + xik) / 2) < 0, либо f ((xik + xik + 1) / 2) > 0. Тогда игроку также выгодно сдвигаться в ту сторону, с которой выполняются соответствующие условия для производных.

8. Если xi = xik и эту же стратегию выбрало j > 1 игроков, то игроку выгодно изменить свою стратегию сдвигом, получив вместо Iik / (j + 1) выигрыш max {I – –, I + – }. Значит равновесие невозможно в случае совik ik падения стратегий более чем двух игроков.

Итак, для игрока i перечислены ситуации, в которых его стратегия будет нарушать условия определения равновесия по Нэшу.

2.2.5.2. ПОСТРОЕНИЕ РАВНОВЕСИЯ В БЕЗОПАСНЫХ СТРАТЕГИЯХ Рассмотрим случай, когда функция f (x) является однопиковой [89].

Обозначим через m – номер стратегии i, в окрестности которой [(xm – + xm) / 2, (xm + xm + 1) / 2] функция f (x) достигает своего максимума, при этом значение Km – определяется согласно (37), kmin Argmink Kk, Kmin = min Kk. Исследуем поведение игрока k = 1. Пусть максимум f (x) на1kn ходится не близко от краев a и b отрезка, то есть f (x) возрастает на всей области x1 и убывает на всей области xl. Из этого следует, что, во-первых, стратегию x1 может выбрать только один игрок и, во-вторых, этому игроку будет выгодно сдвигать x1 в сторону увеличения. Но если при этом окажется, что I – > Kmin, тогда игроку kmin станет выгодно перескочить в область игрока 1, поэтому игрок 1 будет сдвигаться вправо только до тех пор, пока для x1 выполняется неравенство I - Kmin. А это условие означает для первого игрока выполнение определения 4, то есть безопасную стратегию первого порядка. При этом стратегия первого игрока привязана к Kmin, то есть к размеру самого маленького из выигрышей участников.

Теперь исследуем поведение игрока k со стратегией i, 1 < i < m. Функция f(x) возрастает на всей области xik, значит, игроку выгодно сдвигаться вправо, но игроку, находящемуся слева от него тоже выгодно сдвигаться вправо, в силу чего определение 4 для рассматриваемого игрока не выполняется. Но если игрок, находящийся слева от рассматриваемого и стремящийся сдвигаться вправо, имеет в своем движении некоторый ограничитель (которым является дополнительное условие определения 5), и игрок k знает и учитывает это, то, опираясь на такое знание и на знание величины Kmin, он может найти наилучшую для себя стратегию (наилучшую при условии, что ни он, ни другие игроки не выходят за пределы ограничения, заданного определением 5). Из этого рассуждения путем рекурсии от игрока k к игроку 1 получается определение безопасной стратегии порядка k – (в данном случае).

Для игроков i, i > m, выбравших свои стратегии в области убывания f(x), рассуждения аналогичны. Рассмотрим игрока (игроков), выбравшего стратегию m. Если этот игрок один, то, чтобы его стратегия была равновесной, необходимо выполнение следующего условия f ((xim - 1 + xim) / 2) = f ((xim + xim + 1) / 2). Если же их двое, то требуется другое условие: I + = I -, f (xim) > f ((xim – 1 + xim) / 2), f (xim) > f ((xim + xim + 1) / 2).

im im При этом в обоих случаях оказывается, что Kim = Kmin, то есть игроки, оказавшиеся на вершине, получают наименьший выигрыш из всех. Таким образом, мы доказали два утверждения, определяющие игровые ситуации, являющиеся РБС, для случая однопиковых функций f (x). Построение РБС изображено на рисунках 9 и 10. Таким образом, доказаны следующие два утверждения.

f (x) f (x) I – =I – =I3=I + I – =I – =I – =I + =I + 1 2 4 1 2 3 3 I – I – I3 I + x I – I – I – I + I + x 1 2 1 2 3 3 x11 x22 x33 xx11 x22 x33=x34 xРис. 9. Пример РБС для условий Рис. 10. Пример РБС для утверждения 7 условий утверждения Утверждение 7. Пусть f (x) – достигает максимума внутри отрезка [a, b] в точке xmax, строго возрастает при х < xmax, строго убывает при х > xmax. Тогда если xmax [(xm – 1 + xm) / 2, (xm + xm + 1) / 2], I – = I – =…= I – = Im = I + = … = I + = I +, 1 2 m–1 m+1 n+1 n f ((xm – 1 + xm) / 2) = f ((xm + xm + 1) / 2), то x* = (x1,..., xn) – РБС.



Утверждение 8. Пусть f (x) – достигает максимума внутри отрезка [a, b] в точке xmax, строго возрастает при х < xmax, строго убывает при х > xmax. Тогда если xim = xim + 1, xmax [(xm – 1 + xm) / 2, (xm + 1 + xm + 2) / 2], I – = I – = … = I – = I – = I + = I + = … = I + = I +, 1 2 m – 1 m m + 1 m + 2 n + 1 n то x* = (x1,..., xn) – РБС.

Теперь пусть f (x) – постоянная функция. Игроки могут располагаться одиночно и парами xk = xk+1. Однозначно здесь определяются только стратегии игроков xi1 и xil, если они одиночны, из условия I – = I + = Kmin. Для 1 l остальных игроков как одиночных, так и парных требуется только выполнение условия Kk 2Kj, k, j. Для этой игры при n > 3 существуют равновесия Нэша. Для этого крайние игроки должны быть парными x11 = x12, xln– = xln, и должно выполняться указанное условие. Иллюстрация к построению дана на рисунке 11. Доказано следующее утверждение.

f (x) f (x) I – =I + =Kmin2Kmax I – =I – =I– =I+ 1 l 1 2 3 I– Kmin Kmax I+ x I – I – I – I + x 1 l 1 2 3 x1 xmin xmax xn x11 x22 x33=xРис. 11. Пример РБС для Рис 12. Пример РБС для условий утверждения 9. условий утверждения 10.

Утверждение 9. Пусть f (x) – постоянная функция.

Тогда, если x1 = x2, xn–1 = xn, и 2Kmin Kmax, то x* = (x1,..., xn) – равновесие Нэша.

Если стратегия x1 единична и I – = Kmin, либо xn единична и I + = Kmin, 1 l и xmin не совпадает с x1 либо xn;

2Kmin Kmax, то x* = (x1,..., xn) – РБС, не являющееся равновесием Нэша.

Рассмотрим случай строго возрастающей f (x). При этом игрок, находящийся правее всех, будет стремиться сместиться влево, а игрок, находящийся слева от него, – вправо до тех пор, пока их стратегии не совпадут.

При этом I + = I – = I + = Kn = Kn–1 = Kmin. Иллюстрация к построению дана l l l–на рисунке 12. Доказано следующее.

Утверждение 10. Пусть f (x) строго возрастает. Тогда если xn–1=xn, и I – = I – = … = I – = I – = I + = Kmin, 1 2 l – 1 l l то x* = (x1,..., xn) – РБС.

Объединим два предыдущих случая. Пусть f (x) сначала строго возрастает, потом достигает максимума и после этого становится константой.

Иллюстрация к построению дана на рисунке 13. Доказано следующее утверждение.

f (x) f (x) I – =I – =I + =Kmin2Kmax I – =I+ =I+ =I+ =I – =I – =I+ 1 2 l 1 1 2 3 4 5 I – I – Kmin Kmax I + x I – I + I + I + I – I – I + x 1 2 l 1 1 2 3 4 5 x1 x2 xmin xmax xn x11=x12 x23 x34 x45 x56=xРис. 13. Пример РБС для Рис. 14. Пример РБС для условий Утверждения 11 условий Утверждения Утверждение 11. Пусть f (x) строго возрастает при х < xmax, f (x) = f (xmax), при х xmax.

Тогда, если f ((xm – 1 + xm) / 2) < f (xmax), f ((xm + xm + 1) / 2) = f (xmax), номер игрока с наименьшим выигрышем kmin > m, I – = I – = … = I – = I – = Kmin Kmax, 1 2 m – 1 m то x* = (x1,..., xn) – РБС.

Пусть теперь f (x) достигает минимума внутри отрезка в точке xmin, строго убывает при х < xmin, строго возрастает при х > xmin. Рассмотрим игроков, примыкающих к точке минимума, так как ситуации всех других игроков этой игры рассмотрены выше. Два игрока, примыкающих к точке минимума, будут стремиться сдвигаться друг от друга (в сторону возрастания функции) до тех пор, пока их стратегии не окажутся на границах множеств безопасности нулевого порядка. Иллюстрация к построению дана на рисунке 14. Доказано следующее утверждение.

Утверждение 12. Пусть f (x) достигает минимума внутри отрезка в точке xmin, строго убывает при х < xmin, строго возрастает при х > xmin. Тогда если xmin [(xm – 1 + xm) / 2, (xm + 1 + xm + 2) / 2], f ((xm + xm + 1) / 2) < f ((xm – 1 + xm) / 2), f ((xm + xm + 1) / 2) < f ((xm + 1 + xm + 2) / 2), x1 = x2, xn – 1 = xn, I + = I + = … = I + = I + = I – = I – = … = I – = I –, 1 2 m – 1 m m + 1 m + 2 n + 1 n то x* = (x1,..., xn) – РБС.

В Утверждениях 7-12, для ряда типов функций f (x) (однопиковые, строго монотонные, константа и другие) сформулированы достаточные условия того, что игровые ситуации являются РБС. Построение наборов стратегий, удовлетворяющих этим достаточным условиям – самостоятельная задача, которую естественнее всего решать численно. Существование таких наборов следует из геометрических соображений, а единственность может выполняться не всегда: Утверждения 7 и 8 описывают два различных решения одной и той же задачи, а утверждение 9 задает широкое множество ситуаций РБС. Кроме того, в доказанных утверждениях описано поведение игроков, находящихся в различных положениях: крайний игрок в точке максимума, крайний игрок в точке минимума, крайний игрок при постоянной функции, игрок в области монотонности функции, игрок в области постоянства функции, игрок в области максимума, игрок в области минимума. Опираясь на этот результат, можно конструировать решение игры для различных f (x). Потребуется преодоление двух возможных препятствий. Первое – наличие «мелких» минимумов, максимумов, областей возрастания и убывания, то есть если f (x) ведет себя достаточно сложно и количество игроков не настолько велико, чтобы это компенсировать. Второе – определение количества игроков, приходящихся на каждый отрезок возрастания, убывания или постоянства f (x).





2.2.6. Граф угроз игровой ситуации Набор порядков безопасности стратегий игроков (m1, …, mn) дает неполную информацию о сложном РБС. При этом остается неосвещенным вопрос, кто кому угрожает и чьи угрозы являются сдерживающим фактором, обращающим данную игровую ситуацию в равновесие. Цель построения графа угроз – прояснить именно эту структуру отношений игроков.

Граф строится для фиксированной ситуации x* = (x1,..., xn). Вершинам графа соответствуют игроки. Направленные ребра (дуги) графа отражают угрозы и направлены от угрожающего игрока к тому, которому он угрожает. То есть дуга (i, j) принадлежит графу угроз ситуации, если существует xi такое, что Ki(xi, x* ) Ki(x*) и Kj(xi, x* ) < Kj(x*).

-i -i ij i1... ij–1 ij+2... il 1 2 ij+1 Рис. 15. Граф угроз ситуации игры Рис. 16. Граф угроз «хоровод» РБС для примера с рисунка На рисунках 15 и 16 представлены графы угроз, иллюстрирующие игру в примере из раздела 2.2.4.3, «хоровод» (при xij = xij+1) и РБС для варианта основной задачи, показанного на рисунке 10.

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

Сформулируем несколько утверждений о графах угроз для ситуации игры.

Утверждение 13. Простому РБС соответствует пустой граф.

Доказательство. Так как в РБС порядка 0 не имеется ни одной угрозы, то в графе угроз не может быть ни одной дуги.

Утверждение 14. Если граф угроз ситуации содержит циклы, то такая ситуация не является РБС.

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

Утверждение 15. Для графа угроз сложного (m1, …, mn) РБС, если mi = 0, то в вершину i не входит ни одна дуга; если mi > 0, то mi будет равно максимальной длине маршрутов, заканчивающихся в вершине i.

Доказательство. Проводится по индукции. Если mi = 0, то игроку i не угрожает никто, значит, в вершину i не входит ни одна дуга. Если mi = 1, то угрожать игроку i могут только игроки с безопасными стратегиями, значит, в вершину i входят только дуги, выходящие из безопасных вершин. Если mi = m, то игроку i угрожают только игроки со стратегиями, порядок безопасности которых не превышает m - 1, причем хотя бы для одного из них эта величина достигается. Значит, в вершину i входят только дуги, выходящие из вершин, в которые входят маршруты длины не более m - 1, причем хотя бы для одного случая эта величина достигается.

В заключение рассмотрения графов следует сказать, что они не только несут информацию об РБС или просто игровой ситуации, но и делают структуру угроз в ней ясной и наглядной.

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

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










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

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