Теорема очистки

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

Равновесия смешанной стратегии объясняются как предел равновесия чистой стратегии для нарушенной игры с неполной информацией , в которой выигрыши каждого игрока известны им самим, но не их противникам. Идея состоит в том, что предсказанная смешанная стратегия исходной игры возникает как постоянно улучшающаяся аппроксимация игры, которую не заметил теоретик, создавший исходную идеализированную игру.

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

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

Пример

	С	Д
С	3, 3	2, 4
Д	4, 2	0, 0
Рис. 1: Ястреб-Голубь. игра

Рассмотрим показанную здесь игру «Ястреб–Голубь» . В игре есть два равновесия чистой стратегии (Дефект, Сотрудничество) и (Сотрудничество, Дефект). Также существует смешанное равновесие, в котором каждый игрок играет «Сотрудничать» с вероятностью 2/3.

Предположим, что каждый игрок i несет дополнительные затраты a _i от игры в «Сотрудничать», которые равномерно распределены на [− A , A ]. Игроки знают только свою ценность этой стоимости. Итак, это игра с неполной информацией , которую мы можем решить, используя байесовское равновесие Нэша . Вероятность того, что a _i ≤ а* равно ( а* + А /2 А. ) Если игрок 2 сотрудничает, когда a ₂ ≤ a* , то ожидаемая полезность игрока 1 от сотрудничества равна − a ₁ + 3( a* + A )/2 A + 2(1 − ( a* + A )/2 A ) ; его ожидаемая полезность от дезертирства равна 4( a* + A )/2 A . Следовательно, он сам должен Сотрудничать, когда a ₁ ≤ 2 - 3( a* + A )/2 A . Ища симметричное равновесие, при котором оба игрока сотрудничают, если a _i ≤ a* , мы решаем эту задачу для а* = 1/(2 + 3/ А ).Теперь, когда мы вычислили a* , мы можем вычислить вероятность того, что каждый игрок будет играть в «Сотрудничать» как

$\Pr(a_{i}\leq a^{*})={\frac {{\frac {1}{2+3/A}}+A}{2A}}={\frac {A}{4A^{2}+6A}}+{\frac {1}{2}}.$

При А → 0 это приближается к 2/3 – той же вероятности, что и в смешанной стратегии в полной информационной игре.

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

Технические подробности

Доказательство Харсаньи основано на сильном предположении, что возмущения каждого игрока независимы от других игроков. Однако были предприняты дальнейшие уточнения, чтобы сделать теорему более общей.

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

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