2.1. Основные понятия и определения.

2.2. Классификация игр.

2.3. Оптимальные стратегии.

2.4. Смешанные стратегии.

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ 
Теория игр – математический метод изучения оптимальных стратегий в играх. Под игрой понимается процесс, в котором участвуют две и более сторон (игроков), ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу – в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учетом представлений о других участниках, их ресурсах и их возможных поступках (стратегиях). Теория игр – это раздел прикладной математики, точнее – исследования операций. Чаще всего методы теории игр находят применение в экономике, чуть реже в других общественных науках – социологии, политологии, психологии, этике и других. При решении ряда практических задач приходится анализировать ситуации, в которых сталкиваются две (или более) враждующие стороны, преследующие различные цели, причем результат любого мероприятия каждой из сторон зависит от того, какой образ действий выберет противник. Такие ситуации мы можно отнести к конфликтным ситуациям. Теория игр является математической теорией конфликтных ситуаций, при помощи которой можно выработать рекомендации по рациональному образу действий участников конфликта. Чтобы сделать возможным математический анализ ситуации без учета второстепенных факторов, строят упрощенную, схематизированную модель ситуации, которая называется игрой. Игра ведется по вполне определенным правилам, под которыми понимается система условий, регламентирующая возможные варианты действий игроков; объем информации каждой стороны о поведении другой; результат игры, к которому приводит каждая данная совокупность ходов. 
Признаки игры как математической модели ситуации: 
 наличие нескольких участников (игроков); 
 неопределенность поведения участников, связанная с наличием у каждого из них нескольких вариантов действий (стратеги); 
 различие (несовпадение) интересов участников; 
 взаимосвязанность поведения участников, поскольку результат, получаемый каждым из них, зависит от поведения всех участников; 
 наличие правил поведения, известных всем участникам.

Выигрыш показывает, какую прибыль получит конкретный игрок при выборе стратегий другими игроками. Единственная цель каждого игрока – максимизация его выигрыша. Результат игры (выигрыш или проигрыш) вообще не всегда имеет количественное выражение, но обычно можно, хотя бы условно, выразить его числовым значением. Ход – выбор одного из предусмотренных правилами игры действий и его осуществление. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор игроком одного из возможных вариантов действий и его осуществление. Случайным ходом называется выбор из ряда возможностей, осуществляемый не решением игрока, а каким-либо механизмом случайного выбора (бросание монеты, выбор карты из перетасованной колоды и т. п.). Для каждого случайного хода правила игры определяют распределение вероятностей возможных исходов. Игра может состоять только их личных или только из случайных ходов, или из их комбинации. Стратегия – это априори принятая игроком система решений (вида «если-то»), которых он придерживается во время ведения игры. Оптимальная стратегия – это такая стратегия, которая при многократном повторении игры обеспечит данному игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш). Целью теории игр является выработка рекомендаций для разумного поведения игроков в конфликтной ситуации, т. е. определение «оптимальной стратегии» для каждого из них. Стратегия, оптимальная по одному показателю, необязательно будет оптимальной по другим. Сознавая эти ограничения и поэтому не придерживаясь слепо рекомендаций, полученных игровыми методами, можно все же разумно использовать математический аппарат теории игр для выработки, если не в точности оптимальной, то, во всяком случае приемлемой стратегии. 

КЛАССИФИКАЦИИ ИГР 
В зависимости от количества игроков различают игры двух и n игроков. Первые из них 
наиболее изучены. Игры трех и более игроков менее исследованы из-за возникающих 
принципиальных трудностей и технических возможностей получения решения. 
В зависимости от числа возможных стратегий игры делятся на «конечные» и 
«бесконечные». Игра называется: 
 конечной, если у каждого игрока имеется только конечное число стратегий; 
 бесконечной, если хотя бы у одного из игроков имеется бесконечное число стратегий. 
По характеру взаимодействия игры делятся на 
 бескоалиционные – игроки не имеют права вступать в соглашения, образовывать 
коалиции; 
 коалиционные (кооперативные) – могут вступать в коалиции. В кооперативных играх 
коалиции заранее определены. 
По характеру выигрышей игры делятся на: 
 игры с нулевой суммой (общий капитал всех игроков не меняется, а 
перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) , в 
случае двух игроков – антагонистические игры; 
 игры с ненулевой суммой. 
Пример 3. «Дилемма заключенного». Двое подозреваемых, A и B, находятся в разных 
камерах. Следователь, навещая их поодиночке, предлагает сделку следующего 
содержания: если один из них будет свидетельствовать против другого, а второй будет 
молчать, то первый заключенный будет освобожден, а второго осудят на 10 лет. Если 
оба будут молчать, то отсидят по 1 году. Если оба предадут друг друга, то каждый 
получит по 2 года. Каждый из заключенных должен принять решение: предать 
подельника или молчать, не зная о том, какое решение принял другой. Дилемма: какое 
решение примут заключенные? 
Платежная матрица игры: 

	Заключенный B молчит	Заключенный B предает
Заключенный A молчит	-1,-1	-10,0
Заключенный A предает	0,-10	-2,-2

Смешанные стратегии

В общем случае V_* ≠ V^* - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи, аналогичный рассмотренному выше. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию.

Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом:

P = (p₁, p₂,…, p_m),

где p_i≥ 0, p₁ + p₂ +…+ p_m= 1. Величина p_i называется вероятностью (относительной частотой) применения стратегии A_i.

Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид:

Q = (q₁, q₂,…, q_n),

где q_j≥ 0, q₁ + q₂ +…+ q_n = 1. Величина q_j называется вероятностью (относительной частотой) применения стратегии B_j. Совокупность (комбинация) чистых стратегий A₁, A₂, …A_m и B_1, B_2, …B_n в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.

Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана: каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.

Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P^* и Q^*, таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.

Средний выигрыш игрока A определяется математическим ожиданием:

Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной.

Стратегии P^*, Q^* называются оптимальными смешанными стратегиями, если

M_A(P, Q^*) ≤ M_A(P^*, Q^*) ≤ M_A(P^*, Q) (1)

В этом случае M_A(P^*, Q^*) называется ценой игры и обозначается через V (V_* ≤ V ≤ V^*). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B.

Оптимальная стратегия игры

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

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

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

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

Итеративный метод решения игр (метод Брауна). В 1951 г. американский математик Браун предложил метод отыскания оптимальных стратегий в матричных играх, опирающийся на известное правило -- принимать то или иное решение на основании изучения предыстории, накопленного опыта. Суть метода состоит в том, что игроки, прежде чем сделать ход, разыгрывают как бы «в уме» целый ряд фиктивных партий, учитывая стратегии друг друга и всякий раз выбирая оптимальную чистую стратегию против смешанной стратегии по всем прошлым партиям противника.