Равновесие Нэша

GAN - это zero-sum игра. Генератор против дискриминатора. Nash equilibrium: генератор производит неотличимые образцы, дискриминатор отвечает ровно 0.5. Mode collapse - это провал сходимости к NE. Та же математика, что лежит в основе GANov, в 1950 году вместила в 27 страниц идею, получившую Нобелевскую премию.

• **GANs**: генератор и дискриминатор - zero-sum игра; NE - неотличимые образцы; mode collapse = недостижение равновесия
• **Реклама Google и Facebook**: аукцион второй цены (механизм Викри) - доминирующая стратегия говорить правду о ценности, это следствие теории NE
• **Пенальти**: профессиональные вратари и бьющие рандомизируют с вероятностями, близкими к смешанному NE - Chiappori, Levitt, Groseclose 2002

Предварительные знания

• Введение в теорию игр

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

1994 год. Стокгольм. Нобелевскую премию по экономике вручают математику, чья диссертация содержит 27 страниц и одну идею. Джону Нэшу - 66 лет, из которых 30 он провёл в борьбе с параноидной шизофренией. Идее - 44 года. И эта идея изменила экономику, биологию, компьютерные науки и дизайн аукционов.

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

Профиль стратегий s* = (s1*, s2*, ..., sn*) такой, что для каждого игрока i: ui(si*, s-i*) >= ui(si, s-i*) для всех si из Si Никто не выигрывает от одностороннего отклонения.

Здесь важен подвох: NE - не «лучший» исход. В дилемме заключённого NE=(D,D) даёт (-2,-2), хотя (C,C)=(-1,-1) лучше для обоих. NE отвечает на вопрос «что произойдёт?», а не «что было бы хорошо?». Стабильность и оптимальность - разные вещи.

GANs (генеративно-состязательные сети) - та же конструкция. Генератор и дискриминатор играют zero-sum игру: генератор минимизирует вероятность обнаружения, дискриминатор максимизирует. Nash equilibrium теоретически достигается когда генератор производит неотличимые образцы, а дискриминатор отвечает 0.5. Провал сходимости в реальных GAN - это именно недостижение NE: mode collapse, oscillation, divergence.

Игра может иметь несколько NE. Битва полов (Battle of the Sexes) имеет два чистых NE: (Опера, Опера) и (Футбол, Футбол). Какой из них реализуется - зависит от координации, фокальных точек и истории взаимодействия.

Функция наилучшего ответа

**Наилучший ответ** (best response) игрока i на стратегии остальных s-i - это стратегия, максимизирующая выигрыш i при данных s-i: BRi(s-i) = argmax ui(si, s-i)

NE - это профиль, где каждый играет наилучший ответ на стратегии остальных: si* принадлежит BRi(s-i*) для всех i. Другими словами, NE - **пересечение наилучших ответов** всех игроков одновременно.

В некоторых играх (Matching Pennies, Камень-Ножницы-Бумага) пересечение best response в чистых стратегиях пусто - чистых NE не существует. Именно для таких случаев нужны смешанные стратегии.

Смешанное равновесие Нэша

В **Matching Pennies** нет чистого NE: если один играет орёл, другому выгодна решка - бесконечная гонка без конца. Чистые стратегии не дают устойчивой точки. Нужна рандомизация.

Ключевой принцип смешанного NE звучит контринтуитивно: игрок рандомизирует **не для себя**, а чтобы оппонент был безразличен между своими стратегиями. Если оппонент предпочитает одну из стратегий - нужно изменить вероятности так, чтобы уравнять его ожидаемые выигрыши.

Реальный пример: анализ пенальти в футболе (Chiappori, Levitt, Groseclose, 2002) показал, что профессиональные вратари и бьющие рандомизируют с вероятностями, близкими к смешанному NE. Теория предсказывает поведение в реальном спорте с точностью, недоступной интуиции.

В машинном обучении смешанные стратегии - это распределения над действиями. RLHF (Reinforcement Learning from Human Feedback) оптимизирует политику как стохастическое отображение: policy(action | state) - вероятностное распределение. Алгоритм PPO при обучении агентов поддерживает достаточную стохастичность (entropy bonus), чтобы избежать детерминированных ловушек - аналог принудительной рандомизации в смешанных NE.

В смешанном NE ожидаемый выигрыш от каждой чистой стратегии одинаков - иначе игрок переключился бы на лучшую. Принцип безразличия - вычислительный инструмент: приравниваем ожидаемые выигрыши, решаем уравнение и получаем равновесные вероятности.

Теорема Нэша о существовании

В Matching Pennies нет чистого NE, но есть смешанное. Это наводит на вопрос: а существует ли хотя бы одно NE всегда? Нэш в 1950 году доказал: **да**. В любой конечной игре.

Любая конечная игра (конечное число игроков, конечные множества стратегий) имеет хотя бы одно равновесие Нэша в смешанных стратегиях.

Доказательство использует **теорему Какутани о неподвижной точке** - обобщение классической теоремы Брауэра. Идея: отображение best response на пространстве смешанных стратегий - многозначная функция на выпуклом компакте с «хорошими» свойствами полунепрерывности. Какутани гарантирует неподвижную точку. А неподвижная точка best response - это и есть NE.

Теорема Нэша - теорема существования, не конструктивная. Она не говорит, как найти NE. И это проблема: задача нахождения NE в общих играх является PPAD-полной (класс сложности, содержащий задачи, для которых решение гарантированно существует, но найти его вычислительно трудно). Нет алгоритма полиномиального времени - если только P = PPAD, что считается крайне маловероятным.

Механизм-дизайн использует знание о NE в обратную сторону: вместо предсказания исхода при данных правилах - **проектирование правил** так, чтобы NE был желаемым исходом. Google и Facebook проводят аукционы второй цены (механизм Викри). Доминирующая стратегия в таком аукционе - говорить правду о своей ценности. Это не догадка и не бизнес-решение. Это теорема.

Ключевые идеи

• **NE** - профиль, где каждый играет best response: никто не выигрывает от одностороннего отклонения
• **Best response** - оптимальная стратегия при данных стратегиях остальных; NE = пересечение BR всех игроков
• **Смешанное NE** находится через принцип безразличия: вероятности выбираются так, чтобы оппонент был безразличен
• **Теорема Нэша (1950)**: каждая конечная игра имеет хотя бы одно NE в смешанных стратегиях
• **NE стабильно, но не оптимально** - дилемма заключённого показывает разрыв между индивидуальной рациональностью и коллективным благом

Связанные темы

Равновесие Нэша - отправная точка для дальнейших концепций теории игр:

• Введение в теорию игр — Определения игроков, стратегий и выигрышей - необходимый фундамент для понимания NE
• Доминирование и IESDS — Удаление доминируемых стратегий упрощает поиск NE - оставшиеся профили содержат все NE
• Дилемма заключённого — Классическая игра, демонстрирующая разрыв между NE и оптимумом Парето

Вопросы для размышления

• Если NE не оптимально (дилемма заключённого), как общество «вырывается» из плохого равновесия? Какую роль играют институты, законы, репутация?
• Поиск NE - PPAD-полная задача. Если даже компьютер не может быстро найти NE, откуда рациональные агенты «знают» его в реальных ситуациях?
• GAN учатся, никогда не достигая Nash equilibrium в точности. Почему это не мешает им производить качественные изображения?

Связанные уроки

• gt-01 — Игроки, стратегии, нормальная форма - фундамент NE
• gt-03 — Доминирование и IESDS упрощают поиск NE
• gt-04 — Дилемма заключённого - главный контрпример к оптимальности NE
• prob-03-conditional — Смешанные стратегии - вероятности над чистыми действиями
• prob-07-expectation — Ожидаемый выигрыш в смешанных равновесиях