Определение игры. 
Теория игр для математического решения задач

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

возможные действия каждого из игроков;

объем информации, которую может получить каждая сторона о действиях другой;

исход игры в результате каждой совокупности ходов противников.

Игроки: Считается заданным список игроков. Если игроков различать по номерам, то их список сводится к множеству, где — число игроков. Считается, что игроки осведомлены о наличии каждого из своих партнеров.

Действия: Каждый игрок имеет в своём распоряжении некоторый набор стратегий. Множества могут быть как конечными, так и бесконечными. В основе рационального поведения участников игры лежит так называемый постулат «общего знания»: каждый полностью информирован о своих стратегических возможностях и о стратегических возможностях своих партнёров. Процесс игры состоит в выборе каждым из игроков своей стратегии:. В результате складывается игровая ситуация. Множество? всех возможных игровых ситуаций образует ситуационное пространство игры, обозначаемое .

Интересы: Степень заинтересованности игрока k в той или иной ситуации sопределяется размером выигрыша, который в этой ситуации он может получить. Таким образом, правила игры получаются заданием так называемых, функций выигрыша. Эти функции принимают числовые значения и имеют общую область определения. Каждая из таких функций есть функция «n-переменных»: .

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

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

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

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

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

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

• 1 чередование ходов, которые могут быть как личными, так и случайными
• 2 возможная недостаточность информации
• 3 функция выигрыша

Запишем теперь основные этапы поиска решения игры:

• 1 проверка наличия (или отсутствия) равновесия в чистых стратегиях (к этому вопросу вернёмся чуть позже). При наличии равновесной ситуации указываются соответствующие оптимальные стратегии игроков и цена игры.
• 2 поиск доминирующих стратегий (в случае успеха этого поиска — отбрасывание доминирующих строк и столбцов в исходной матрице игры).
• 3 замена игры на её смешанное расширение и отыскание оптимальных смешанны х стратегий и цены игры.

Отметим, что нормальная форма антагонистической игры сводится к некоторой матрице, А с числом строк равным числу стратегий игрока 1 и с числом столбцов, равным числу стратегий игрока 2. Выигрыш — если игрок 1 выбирает i-ю стратегию, а игрок 2 j-ю стратегию — представляет собой элемент в i-ой строке и в j-ом столбце данной матрицы.

Игроков, как участников игры, интересует, какие из стратегий являются выигрышными с точки зрения максимизации доли каждого игрока в выигрыше. Однако, результаты случайных ходов, известны только в вероятностном смысле, поэтому лучше рассматривать математическое ожидание функции выигрыша, определённое в случае, когда игроки используют n-набор стратегий. Поэтому для описания математического ожидания функции выигрыша, при условии, что игрок i применяет стратегию, можно употребить следующее обозначение Исходя из этого функцию на множестве всех возможных значений переменных можно выразить либо в форме соотношения, либо в виде n-мерной матрицы n-векторов. Такая n-мерная таблица называется нормальной формойигры Г. В нормальной (стратегической) форме игра описывается платёжной матрицей. Каждая сторона матрицы — это игрок, строки определяют стратегии первого игрока, а столбцы — второго. На пересечении двух стратегий можно увидеть выигрыши, которые получат игроки. На примере, если игрок 1 выбирает первую стратегию, а второй игрок — вторую, то на пересечении получится (1,-1). Это значит, что в результате хода игроки потеряли по одному очку.

Пример 1: игра «Орлянка».

Первый игрок прячет монету орлом или решкой вверх, а второй пытается угадать, как она спрятана. Если он не угадывает — платит первому одну денежную единицу, если угадывает — первый платит ему одну денежную единицу. В данной игре каждый игрок имеет две стратегии: «орёл» и «решка». Множество ситуаций в игре состоит из 4 элементов. В строках таблицы указаны стратегии первого игрока Х, в столбцах — стратегии второго игрока Y. Для каждой из ситуаций указаны выигрыши первого и второго игроков.

Рассмотрим основную теорему матричных игр.

Основная теорема теории матричных игр (по Дж. фон Нейману).

Для матричной игры с любой матрицей, А величины и равны между собой, т. е.

Иными словами, любая матричная игра имеет решение в смешанных стратегиях. Поиск этого решения опирается на установленные факты.

Приведём доказательство данной теоремы (автор: Дж. Б. Данциг, 1951 г.). Доказательство. Пусть матрица игры равна. Всегда можно считать, что все коэффициенты. Если это не так, то предположим, что наименьший из всех отрицательных коэффициентов есть. Тогда увеличим все элементы платёжной матрицы на произвольное положительной число. Функция выигрыша при этом окажется равной Из этого следует, что от увеличения всех элементов матрицы на величину цена игры увеличивается на эту величину, причём оптимальные смешанные стратегии не изменяются.

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