Достижимые платежи и теорема Фридмана

Определение 4.3. Назовем платеж (x_vx₂y…_fx_N) достижимым в базовой игре G, если он является выпуклой линейной комбинацией (т.е. линейной комбинацией с неотрицательными коэффициентами, в сумме составляющими единицу) платежей всех чистых стратегий в игре G.

Множество достижимых стратегий в базовой игре «Дилемма заключенных» с матрицей платежей.

составляет затененный четырехугольник (рис. 4.1).

Рис. 4.1.

Его реальная достижимость вытекает из того, что любую точку Т = (х, у) внутри четырехугольника можно представить в виде (х, у) = р⁷ J7q, p_v q_x > О,.

Так, например, платеж можно получить при.

выборе смешанных стратегий игроков (рис. 4.2). При таких стратегиях получим

Рис. 4.2.

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

Множество достижимых средних платежей в бесконечно повторяемой игре — все внутренние и граничные точки треугольника А В С (рис. 4.3) с вершинами в точках Л (0;0), В (2;1), С (1;2). Множество всех значений, которые могут принимать платежи при различных смешанных стратегиях игроков, т. е. множество всех точек с координатами составляет криволинейный треугольник ЛВС.

Платеж является достижимым, хотя не существует таких р и q,

при которых В смешанных стратегиях этот исход недостижим (докажите это самостоятельно).

Покажем стратегии, при которых этот исход достижим. Стратегия первого игрока: «Играть в базовых играх следующую последовательность чистых стратегий: {я;b]b;я;b;Ь;я;Ь, Ь;…}. Стратегия второго игрока: «Играть в базовых играх следующую последовательность чистых стратегий: {c;d', d;c;d', d;c, d) d;.). При таких стратегиях игроков рассчитаем средний выигрыш каждого из них. Имеем.

Следовательно, при выбранных стратегиях и при средние платежи игроков составят

Рис. 4.3.

Можно и иначе реализовать платежи . А именно, рассмотрим совместную смешанную стратегию на множестве ходов (а; с) и (b d), при которых выигрыши игроков равны соответственно (1; 2) и (2; 1). Пусть эти ходы реализуются с вероятностью . Существенно то, что реализация ходов должна осуществляться датчиком случайных чисел до каждой базовой игры. Аналогично можно реализовать любую точку внутри и на границе множества достижимых платежей. Это значит, что для любой точки этого множества найдутся такие стратегии игроков и такое 8, при которых эта точка достигается в качестве средних платежей в бесконечно повторяемой игре.

Теорема 4.2 (Фридман, 1971). Пусть G — конечная статическая игра N игроков с полной информацией. Пусть (e_x, e₂,…, e_N) — платежи, соответствующие точке равновесия Нэша игры G и (x_vx₂,…, x_N) — любой другой достижимый платеж из G. Если x_t > e_t для каждого игрока i и если 6 достаточно близко к единице, то существует совершенное подыгровое равновесие Нэша в бесконечно повторяемой игре G (°°, 8), в котором платеж (х_х, х₂,…, x_N) достигается как средний платеж.

В примере «Дилемма заключенных» теорема Фридмана гарантирует, что любая точка затененной области на рис. 4.4 может быть достигнута как средний платеж в совершенном подыгровом равновесии 11эша в бесконечно повторяемой игре G{°°, 8) при условии, что фактор дисконтирования достаточно близок к единице.

Рис. 4.4.

Доказательство теоремы 4.2. Пусть а_е = («с, а_е…й_еу) — равновесие Нэша в базовой игре G, в котором платежи равны е = (е, е₂…e_N). И пусть.

а_х. = (а_Г), а_Х2 а_ХЛ.) — совокупность стратегий, которые дают достижимые платежи.

x = (x_vx₂,…, x_N). Рассмотрим следующую стратегию переключения для г-го игрока: «Играю а_г в первой базовой игре. В t-й базовой игре играю а_х., если во всех предыдущих базовых играх был осуществлен исход а_х. В противном случае играю а_е «.

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

Предположим, что все игроки, кроме г-го, придерживаются стратегии переключения. Поскольку они играют (а_е, а_е^,…, а_е, а_е ,…, a_eN) всегда, как только хотя бы один из предыдущих исходов будет отличаться от а,‘наилучшим ответом игрока i в этой ситуации будет а_е (поскольку точка е — равновесие Нэша в игре G) во всех последующих базовых играх. Пусть a_d. — наилучшее отклонение i-го игрока от а_х:

Имеем dj >х, > е_г В случае отклонения от а_х игроком i его максимальный платеж равен

В случае выполнения договоренности об а_х платеж игрока i равенТаким образом, стратегия а_х. будет оптимальной тогда и только тогда, когда

Если теперь потребовать, чтобы последнее неравенство выполнялось для всех значений /, т. е., то для такого 5 исход а_х будет равновесием Нэша.

в бесконечной игре.

Заметим также, что поскольку для всех i. Следовательно, этому условию удовлетворяет и соответственно подобранное 8.

Осталось доказать, что это равновесие Нэша является совершенным подыгровым равновесием, т. е. стратегии переключения составляют равновесие Нэша в каждой подыгрс игры С (°°, 5). В равновесии Нэша, построенном на стратегиях переключения, эти подыгры могут быть двух видов:

• а) подыгры, в которых во всех предыдущих базовых играх выбирались исходы а_х;
• б) подыгры, в которых исход по крайней мере одной из предыдущих базовых игр отличался от а_х.

В первом случае в силу идентичности таких подыгр стратегия переключения остается равновесием Нэша и в иодыграх. Во втором случае стратегиями игроков в подыграх просто являются а_е. для всех i, что тоже является равновесием Нэша.