Оригинал: COTW: Introduction to Game Theory 

Автор: Cangurino

Дата: 2010-07-22


Введение в теорию игр. Часть 1


Миксуем стратегии


Играя в К-Н-Б (камень-ножницы-бумага) или трехкарточный покер, мы не можем постоянно применять одну и ту же стратегию против разумного игрока, иначе он будет нас эксплуатировать. Следовательно, мы должны "переключаться" между разными стратегиями.


Но если наши переключения будут предсказуемы, то толку от них не будет, так оппонет будет осведомлен о наших действиях. Поэтому, наш единственный шанс - сделать наш выбор случайным (рандомизировать). В К-Н-Б мы можем назначить различные вероятности для каждого выбора.


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


Однако, это приводит нас к парадоксальной ситуации, в которой мы не можем ни проиграть, как и выиграть. Не важно как поступает наш оппонент, мы будем играть в ноль; у него просто нет возможности совершить ошибку. У нас, как сказал бы KurtSF (хз, что за зверь) "0EV против всех, серьезно".


Концепция смешения стратегий приводит нас к следующему определению:

Смешанная стратегия - это вероятностное распределение чистых стратегий.


Итак, перед началом игры мы выбираем определенную стратегию и следуем ей с некоторой вероятностью. (Можно возразить, что мы делаем вероятностные решения во время игры, но можно показать, что это эквивалентно выбору фиксированной стратегии до начала игры).


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


Предположим, что А ставит с дамой с вероятностью х, а В сбрасывает короля с вероятностью у.

  • (A,K) A выигрывает $1 с вероятностью y, и выигрывает $2 с вероятностью (1-y). EV: 2-y
  • (A,Q) A выигрывает $1 EV: 1
  • (K,A) B выигрывает $1 EV:-1
  • (K,Q) A выигрывает $1 EV: 1
  • (Q,A) B выигрывает $2 с вероятностью x, and $1 с вероятностью (1-x). EV: -1-x
  • (Q,K) A отвечает, и B выигрывает $1, с вероятностью (1-x). A ставит и B сбрасывает с вероятностью xy, A выигрывает $1. A ставит и B отвечает с вероятностью x(1-y), B выигрывает $2. EV: (x-1)+xy+2x(y-1) = x-1 + xy + 2xy - 2x = 3xy - x - 1


Совокупный ожидаемый результат:

2-y + 1 - 1 + 1 - 1-x + 3xy - x - 1 = 1 - y - x + 3xy = f(x,y)


С помошью высшей математики мы можем найти оптимальные значения:

0=d/dx f(x,y) = -1+3y -> y = 1/3

0=d/dy f(x,y) = -1+3x -> x = 1/3


Следовательно, чтобы не допустить эксплуатации игрок А должен ставить с дамой в 33% случаев, а игрок Б должен сбрасывать короля с той же частотой. Заметьте, что 1/3 - это также доля банка, которую игрок Б должен коллировать; и это не совпадение.


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

Совокупность стратегий всех игроков называется равновесием Нэша, если ни один игрок не может улучшить свое EV, изменив свою стратегию в одностороннем порядке. Стратегия, входящая в равновесие Неша, называется теоретически оптимальной (GTO, game-theoretically optimal).