Определение равновесия

Игра в нормальной форме

Лекция № 16-17 Равновесия Нэша.

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

Ключевые слова: равновесие Нэша.

Вопросы:

1. Игра в нормальной форме;

2. Определение равновесия;

3. Выпуклые игр;

4. Примеры.

Определение. Игрой n лиц в нормальной форме называется набор <N,U1,…,Un,g1,…,gn>, где N={1,…,n} - множество, содержащее n элементов, U1,…,U_n - произвольные множества, g1,…,gn - функции, каждая из которых отображает произведение U₁ … U_n в множество действительных чисел.

Числа i N интерпретируются как номера игроков, множество U_i представляет собой множество управлений игрока i, а функция g_i - его критерий.

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

Набор u=(u₁,…,u_n) управлений всех игроков будем называть ситуацией в рассматриваемой игре. Множество всех ситуаций U₁ … U_n будем обозначать буквой U без индекса.

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

Каждой антагонистической игре <U,V,g> можно естественным образом сопоставить игру двух лиц общего вида <{1,2},U,V,g,-g>.

Практически все результаты, полученные для антагонистических игр, с очевидными изменениями переносятся на класс игр с постоянной суммой, то есть таких игр двух лиц <{1,2},U1,U2,g1,g2>, у которых сумма g1(u1,u2)+g2(u1,u2) не зависит от (u1,u2).

То же относится и к более широкому классу квазиантагонистических игр двух лиц, то есть таких игр, для которых каждая точка (u1,u2) U1 U2 является эффективной.

К сожалению, на практике часто приходится сталкиваться с выбором неэффективных решений. Возьмем к примеру Первую мировую войну. Что в ней выиграли конкурирующие стороны? Германия уступила Франции Эльзас и Лотарингию и выплатила странам Антанты репарации. Что мешало ей сделать это до начала военных действий? Ведь при этом каждая из сторон сохранила бы миллионы жизней и огромные материальные ресурсы. Чтобы понять это рассмотрим более простую модельную ситуацию.

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

Если обе фирмы ведут агрессивную рекламную политику, то каждая из них получает выигрыш равный 4, и при этом ни одной из них не выгодно менять свое решение при неизменном выборе конкурента, поскольку это ведет к сокращению собственной прибыли (и увеличению прибыли другой фирмы). Но есть другое решение, позволяющее обеим фирмам получить выигрыш, равный 5. Что же мешает им договориться и получить большие результаты? Если такая договоренность достигнута, то первая фирма, нарушив ее, сумеет увеличить свой выигрыш, от чего вторая фирма существенно потеряет. Опасаясь такого обмана, она, скорее всего, выберет агрессивную политику, что вновь приведет к выигрышам, равным 4.

Таким образом, на практике часто реализуются исходы устойчивые в том смысле, что отклонение от них в одиночку не выгодно ни одной из сторон конфликта. Формализуем это соображение.

Введем удобное обозначение. Пусть u=(u1,…,un) - ситуация, а viUi - управление i-го игрока. Символом (u vi) будем обозначать такую ситуацию w=(w1,…,wn), что

" Нэш Джон (NashJohn, род. 13.06.1928). Лауреат Нобелевской премии по экономике за 1994 г.

Определение. Ситуация называется ситуацией равновесия по Нэшу в игре <N,U1,…,Un,g1,…,gn>, если для любого i N и любого viUi выполняется неравенство gi(u vi) gi(u).

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

Примерно то же происходит на предиктивном уровне. Предположим, несколько игроков стоят перед каким-то выбором, и некий Эксперт предложил прогноз результатов такого выбора. Если этот прогноз соответствует равновесию по Нэшу, то он вероятнее всего сбудется. В самом деле, каждый из игроков может рассуждать так: "Наверное, мои партнеры будут действовать согласно предсказаниям эксперта. Тогда мое решение очевидно. Мне нужно выбирать стратегию, максимизирующую мой собственный критерий". Если все будут рассуждать примерно так, то прогноз реализуется. А вот если эксперт предложит решение не являющееся равновесием, а игроки отнесутся к нему с доверием, то прогноз заведомо не реализуется.

В случае, когда n=1, то есть игра является, по сути, задачей оптимизации, множество всех равновесий по Нэшу совпадает с множеством всех точек максимума единственного критерия. В случае, когда n=2 и g1(u1,u2)=-g2(u1,u2), то есть когда игра является антагонистической, ситуации равновесия по Нэшу и только они являются седловыми точками. Таким образом, принцип равновесия по Нэшу удовлетворяет хотя бы минимальным требованиям, которым должен удовлетворять всякий "разумный" принцип оптимальности.

Любопытно отметить, что ситуации равновесия можно определить по аналогии с эффективными точками.

Определение. Будем говорить, что стратегия u U *-слабо доминирует стратегию v U в многокритериальной задаче, а соответствующий вектор выигрышей (g1(u),…,gm(u)) *-слабо доминирует вектор (g1(v),…,gm(v)), если существует i, для которого выполняется строгое неравенство gi(u)>gi(v).

Определение. Стратегия u U, и соответствующий вектор выигрышей (g1(u),…,gm(u)) называются сильно эффективными, если не существует стратегии v U, которая *-слабо доминировала бы стратегию u.

Поставим в соответствие игре в нормальной форме <N,U1,…,Un,g1,…,gn> многокритериальную задачу, где функции hi (i=1,…,n) определены условиями.

Лемма. Ситуация u является ситуацией равновесия по Нэшу в игре <N,U1,…,Un,g1,…,gn> тогда и только тогда, когда она является сильно эффективной в многокритериальной задаче.

Доказательство непосредственно следует из определений.

Простейшие свойства

Выше были сформулированы некоторые требования, которым должно удовлетворять любое "разумное" понятие оптимального решения. Сформулируем еще одно требование такого рода.

Определение. Исход u0 называется индивидуально рациональным, если для любого i N выполняется неравенство.

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

Лемма. Всякая ситуация равновесия по Нэшу является индивидуально рациональным исходом.

Доказательство. Из определения равновесия следует, что для любого i выполняется неравенство и уж тем более справедливо неравенство. Последнее неравенство даже сильнее, чем нужно для доказательства леммы.

Лемма. Пусть u0 - ситуация равновесия. Тогда для любого i N верхняя грань достигается и.

Доказательство. Так как неравенство gi(u0 vi) gi(u0) выполняется для всех viUi, число gi(u0) является одной из верхних граней значений функции f(vi)=gi(u0 vi), а потому. Но очевидно, то есть - одна из точек максимума функции f(vi), что и доказывает лемму.

Лемма. В игре n лиц существует ситуация равновесия тогда и только тогда, когда.

Доказательство. Пусть в игре существует ситуация равновесия u0. В силу предыдущей леммы для любого i N имеет место равенство, а значит и равенство.

Но в силу определения точной верхней грани, для любой ситуации u U и любого i N выполняются неравенства или. Но тогда и. Значит, 0 - одна из нижних граней функции, стоящей в левой части последнего неравенства, а потому. Сравнивая это неравенство с равенством, полученным в предыдущем абзаце, убеждаемся, что нижняя грань достигается в точке u0, и имеет место равенство.

Обратно, пусть это равенство выполнено, и минимум в нем достигается в точке u0. Тогда, а, значит, для всех i N и viUi выполняется условие gi(u0 vi) gi(u0) и, следовательно, u0 - ситуация равновесия.

Лемма. В игре n лиц существует ситуация равновесия тогда и только тогда, когда.

Доказательство немедленно следует из предыдущей леммы и очевидного равенства.

Лемма. В игре n лиц существует ситуация равновесия тогда и только тогда, когда.

Доказательство. Фиксируем произвольное u U и рассмотрим функцию. В точке v=u значение этой функции равно нулю, поэтому. Поскольку это неравенство выполняется для любого u U, имеем.

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

Обратно, пусть выполняется это равенство, и минимум в нем достигается в точке u0. Тогда. Но каждое слагаемое в этой сумме зависит только от "своего" vi, поэтому. Любое слагаемое в левой части последнего равенства неотрицательно, а вся сумма равна нулю, значит и все слагаемые равны нулю, а это означает, что u0 - ситуация равновесия.

Лемма. Если множества управлений игроков компактны, а функции выигрыша непрерывны, то множество всех ситуаций равновесия по Нэшу компактно.

Доказательство. Рассмотрим функции, определенные условием. Эти функции непрерывны, поэтому множества Wi решений уравнений hi(u)=0 замкнуты. Но тогда замкнуто и пересечение множеств Wi, которое совпадает с множеством ситуаций равновесия по Нэшу. Остается воспользоваться компактностью множества U и тем, что замкнутое подмножество компактного пространства компактно.

Дата добавления: 2014-01-05