Основные понятия теории игр.
Теория игр представляет собой интенсивно развивающуюся математическую дисциплину, являющуюся одним из разделов теории принятия решений (исследования операций). Предметом исследования теории игр являются методы принятия решений в конфликтных ситуациях. Ситуация называется конфликтной, если в ней сталкиваются интересы нескольких лиц, преследующих противоположные цели. Каждая из сторон может проводить ряд мероприятий для достижения своих целей, причем успех одной стороны означает неудачу другой.
Авторы первого фундаментального трактата по теории игр Дж. фон Нейман и О. Моргенштерн ориентировались на анализ конфликтных ситуаций в вопросах экономики, когда при наличии свободной конкуренции в роли борющихся сторон выступают торговые фирмы, промышленные предприятия и т.д. Однако конфликтные ситуации встречаются и во многих других областях. К конфликтным ситуациям относятся почти все ситуации, возникающие при планировании военных операций, выборе системы оружия, охране объектов от нападения, преследовании и перехвате цели и т.п. Интересными примерами конфликтных ситуаций являются спортивные состязания, арбитражные споры, аукционы, выборы в парламент при наличии нескольких кандидатов на одно место. То есть областью применения методов теории игр являются:
1) математика;
2) экономика;
3) военная стратегия и тактика;
4) политика.
Приведенные примеры показывают большое разнообразие встречающихся на практике конфликтных ситуаций. Обычно эти ситуации трудны для непосредственного анализа из-за множества второстепенных факторов. Для того, чтобы сделать возможным математический анализ конфликтной ситуации, ее необходимо упростить, учтя только основные факторы. Упрощенную формализованную модель конфликтной ситуации называют игрой, а конфликтующие стороны — игроками или лицами, принимающими решения (если это часть теории принятия решения).
Следует различать понятие игры и понятие индивидуальной партии этой игры. Игра представляет собой совокупность правил, описывающих поведение игроков и известных всем игрокам. Каждый случай разыгрывания игры некоторым конкретным образом от начала и до конца представляет собой партию игры. Элементами игры являются ходы. Правила игры предусматривают, какова должна быть последовательность ходов, и указывают характер каждого хода. Также правила регламентируют, какие ходы может осуществлять каждый игрок, какие ситуации могут возникнуть, каков будет выигрыш каждого игрока в каждой из ситуаций.
Ход — момент игры, связанный с выбором игроком определенной стратегии поведения (определенного образа действий). Ходы бывают личные и случайные. Личный ход представляет собой выбор игроком одного из заданного множества вариантов. Например, каждый ход в шахматах является личным, причем первый ход — выбор из 20 вариантов. Решение, принятое игроком при личном ходе, называют выбором.
Случайный ход также представляет собой выбор одного из множества вариантов, но здесь вариант выбирается не игроком, а некоторым механизмом случайного выбора. Примерами случайных ходов может быть сдача карт или бросание монеты. Выбор, осуществляемый при случайном ходе, называют исходом этого хода.
Таким образом, партия — законченная совокупность ходов, после которой можно говорить о выигрыше или проигрыше игроков в данной партии. В общем случае, игру можно рассматривать как бесконечную последовательность партий. Стратегия — набор правил, сформулированных до начала игры.
Классификация игр.
Классификацию игр проводят по различным признакам:
1) по числу игроков;
2) по числу стратегий;
3) по свойствам платежной функции;
4) по характеру предварительной договоренности между игроками.
Игру, в которой участвует n игроков, называют игрой с n участниками. Количество участников может быть равным 2, 3 и т.д. При наличии двух игроков могут возникать конфликтные ситуации, и необходимость в координированных действиях (кооперация). Если в игре участвуют три игрока и более, то могут создаваться коалиции, т.е. группы из двух игроков и более, имеющих общую цель и координирующих свои стратегии.
По количеству стратегий различают игры конечные и бесконечные. Если хотя бы из игроков располагает бесконечным множеством стратегий, то игру называют бесконечной. Если же каждый из игроков располагает конечным множеством стратегий, то игру называют конечной.
Еще один способ классификации игр — по свойствам платежной функции. В игре с нулевой суммой общая сумма выигрышей всех игроков равна нулю. То есть в игре с нулевой сумме двух участников выигрыш одного из них равен проигрышу другого. Таким образом, в игре с нулевой суммой существует конфликт между игроками, и поэтому их называют также антагонистическими играми. В общем случае в игре с нулевой суммой, как правило, имеют место и конфликты, и согласованные действия игроков. Прямой противоположностью играм с нулевой суммой являются игры двух игроков с постоянной разностью, в которых оба игрока выигрывают или проигрывают одновременно. Поэтому игрокам выгодно действовать согласованно.
В зависимости от характера предварительной договоренности между игроками различают кооперативные и некооперативные игры. Игра является кооперативной, если до ее начала игроки образуют коалиции и принимают взаимообязывающие соглашения о координации своих стратегий. В противоположном случае игра будет некооперативной.
Описание игры в развернутой форме
Существует два способа описания и анализа любой конкретной игры:
1) описание игры в развернутой форме
2) описание игры в нормальной форме.
Описание игры в развернутой форме предполагает следующее:
1) перечисление ходов, которые могут делать игроки;
2) определение информации, которой располагают игроки в процессе игры;
3) определение возможных вариантов действия игроков;
4) указание предельных размеров платежей в конце игры
Этот наиболее детализированный способ описания игр используется для сравнительно простых игр. Их называют позиционными играми, и представляют в виде дерева игры.
Способ описания игры в виде дерева игры включает 3 главных момента:
1) чередования ходов, начиная с первого, причем ходы могут быть как личными, так и случайными;
2) возможна недостаточность информации о действиях других участников игры;
3) определение набора исходов игры (вершин дерева) с заданным значением платежной функции.
Наиболее часто игры с конечным или бесконечным числом стратегий описываются в нормальной форме. Этот способ описания игры предполагает рассмотрение всех возможных стратегий каждого игрока и определение платежей, соответствующих любым возможным комбинациям стратегий всех игроков. Для иллюстрации рассмотрим бескоалиционную игру.
Бескоалиционные игры
Рассмотрим бескоалиционную игру, когда каждый игрок действует самостоятельно. Пусть 
— множество игроков. Каждый из игроков имеет некоторое множество 
своих стратегий. Число стратегий образует множество стратегий каждого игрока, и это число должно быть не меньше двух.
Процесс игры состоит в выборе каждым игроком своей стратегии 
. В результате этого выбора определяется исход партии: 
. Пусть 
— вектор ситуаций в игре, тогда 
— множество всех ситуаций в игре. С другой стороны, множество всевозможных ситуаций S можно рассматривать как 
. Выигрыш каждого игрока в каждой ситуации определяется следующим выражением: 
Тогда после всех введенных обозначений бескоалиционной игрой называют систему следующего вида:
В бескоалиционной игре все множества являются множествами вещественных чисел. Среди явлений, описываемых посредством бескоалиционных игр, довольно много таких, когда по результатам игры приходится распределять некоторые ресурсы.
В теории игр также выделяют игры с постоянной суммой: бескоалиционная игра называется игрой с постоянной суммой, если существует такая константа c, что выполнятся условие 
Если 
, то бескоалиционная игра называется игрой с нулевой суммой.