Матричные антагонистические игры с нулевой суммой в чистых стратегиях

Введение

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

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

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

· По виду функций выигрыши игры делятся на матричные (это конечная игра двух игроков с нулевой суммой, в которой задается выигрыш игрока А в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока В, столбец - номеру применяемой стратегии игрока В; на пересечении строки и столбца матрицы находится выигрыш игрока А, соответствующий применяемым стратегиям.

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

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

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

Теория игр - раздел математики, изучающий формальные модели принятия оптимальных решений в условиях конфликта. При этом под конфликтом понимается явление, в котором участвуют различные стороны, наделённые различными интересами и возможностями выбирать доступные для них действия в соответствии с этими интересами. В условиях конфликта стремление противника скрыть свои предстоящие действия порождает неопределённость. Наоборот, неопределённость при принятии решений (например, на основе недостаточных данных) можно интерпретировать как конфликт принимающего решения субъекта с природой. Поэтому теория игр рассматривается также, как теория принятия оптимальных решений в условиях неопределённости. Она позволяет систематизировать некоторые важные аспекты принятия решений в технике, сельском хозяйстве, медицине и социологии и других науках. Участвующие в конфликте стороны называются коалициями действия; доступные для них действия - их стратегиями; возможные исходы конфликта - ситуациями.

Задача теории состоит в том, что является:

1) оптимальным поведением в игре.

2) исследование свойств оптимального поведения

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

4) построение численных методов нахождения оптимального поведения.

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

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

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

Математическая ТЕОРИЯ ИГР началась с анализа спортивных, карточных и других игр. Рассказывают, что первооткрыватель теории игр, выдающийся американский математик XX в. Джон фон Нейман пришел к идеям своей теории, наблюдая за игрой в покер. Отсюда и произошло название «теория игр».

Начнем исследование данной темы с ретроспективного анализа развития теории игр. Рассмотрим историю и развитие вопроса теории игр. Обычно «генеалогическое дерево» представляется в виде дерева в смысле теории графов, в которых разветвление происходит от некоторого единого «корня». Родословная теории игр - книга Дж. фон Неймана и О. Моргенштерна. Поэтому исторический ход развития теории игр как математической дисциплины, естественным образом расчленяется на три этапа:

Первый этап - до выхода в свет монографии Дж. фон Неймана и О. Моргенштерна. Его можно назвать «до монографическим». На этом этапе игра выступает пока еще как конкретное состязание, описываемое своими правилами в содержательных терминах. Лишь в конце его Дж. фон Нейман вырабатывает представление об игре как об общей модели абстрактного конфликта. Итогом этого этапа явилось накопление ряда конкретных математических результатов и даже отдельных принципов будущей теории игр.

Второй этап составляет сама монография Дж. фон Неймана и

О. Моргенштерна «Теория игр и экономическое поведение» (1944), объединившая в себе большинство ранее полученных (впрочем, по современным математическим масштабам довольно немногочисленных) результатов. Она впервые представила математический подход к играм (как в конкретном, так и в абстрактном понимании этого слова) в виде систематической теории.

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

Однако даже математическая теория игр не способна стопроцентно предопределить исход некоторых конфликтов. Представляется возможным выделить три основные причины неопределенности исхода игры (конфликта).

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

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

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

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

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

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

а) множество заинтересованных сторон (мы будем называть их игроками; в литературе по теории игр они именуются также субъектами, лицами, сторонами, участниками). В случае если число игроков, конечно, они различаются по своим номерам (1-й игрок и 2-й игрок в игре в орлянку или в случае дуополии) или по присваиваемым им именам (например, продавец и покупатель в ситуации монополия-монопсония);

б) возможные действия каждой из сторон, именуемые также стратегиями или ходами;

в) интересы сторон, представленные функциями выигрыша (платежа) для каждого из игроков.

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

Теория игр впервые была систематически изложена Дж. фон Нейманом и О. Монгерштерном в 1944 г., хотя отдельные результаты были опубликованы еще в 20-х годах. Нейман и Моргенштерн написали оригинальную книгу, которая содержала главным образом экономические примеры, поскольку экономическому конфликту легче всего придать численную форму. Во время второй мировой войны и сразу после нее теорией игр серьезно заинтересовались военные, которые увидели в ней аппарат для исследования стратегических решений. Затем главное внимание снова стало уделяться экономическим проблемам.

ГЛАВА 1. МАТРИЧНЫЕ АНТАГОНИСТИЧЕСКИЕ ИГРЫ

1.1 Принятие решений

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

Что же такое «наилучшее» решение? В исследованиях операций «наилучшим» считается решение, доставляющее оптимум функции, выражающей цель системы. Более общее определение «правильного» или «наилучшего» решения в смысле принятия решений будем считать выбор такой альтернативы из числа возможных, в которой с учетом всех разнообразных факторов и противоречивых требований будет оптимизирована общая ценность, то есть она будет в максимальной степени соответствовать достижению поставленной цели. Отметим, что в отличии от исследования операций, в теории принятия решений не существует абсолютно лучшего решения. Решение является лучшим лишь для конкретного лица принимающего решение, в отношении поставленных им целей, при заданных условиях. Эта субъективная оценка оказывается в настоящее время единственно возможной основой объединения разнородных физических параметров решаемой проблемы в единую модель, позволяющую оценивать варианты решений.

Альтернативы.

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

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

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

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

Критерии

В современной науке о принятии решений считается, что варианты решений (альтернативы) характеризуются различными показателями их привлекательности для ЛПР (лицо, принимающее решение). Эти показатели называют признаками, факторами, атрибутами, критериями.

Пусть задано некоторое конечное множество альтернатив. Из множества или любого его подмножества необходимо выделить одно или несколько вариантов решений в некотором смысле лучших или более соответствующих каким-либо заранее оговоренным условиям. Для решения этой задачи обычно используется следующий подход:

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

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

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

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

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

Полнота набора означает, что он должен охватывать все важные аспекты проблемы. Набор критериев является полным, если с его помощью можно показать степень достижения общей цели, то есть набор из критериев полон, если, зная значения n-мерного критерия, связанного с общей целью, ЛПР имеет полное представление о степени достижения общей цели.

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

Разложимость. При использовании n критериев необходимо построить n-мерную функцию предпочтений. Для задач с большим числом критериев полезно произвести декомпозицию задачи и разложить ее на подзадачи, каждая из которых содержит меньшее число критериев. То есть желательно, чтобы набор критериев был разложим.

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

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

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

Схема процесса принятия решений

В классической книге лауреата нобелевской премии профессора Г. Саймона «The New Science of Management Decision», 1960 процесс принятия решений разбит на четыре фазы: сбор информации (intelligence); поиск и построение альтернатив (design); выбор альтернатив (choice); оценка результатов (review). Первая фаза - сбор информации, сконцентрирована на идентификации проблемы принятия решения и сборе всей доступной информации о ней. При поиске и построении альтернатив (вторая фаза) центральным вопросом становится определение относительно небольшого числа альтернатив, которые следует изучить в деталях. На третьей фазе происходит выбор одного из вариантов решений из множества альтернатив, подготовленных на второй фазе. Последний шаг в процессе принятия решений - это реализация выбранной альтернативы и обобщение опыта, полученного в процессе решения проблемы.

Таким образом, само решение принимается в рамках второй и третьей фаз:

· конструирование относительно небольшого множества альтернатив;

· окончательный выбор варианта решения из сформированного множества.

Схематически две эти фазы представлены на рисунке 1. Фазы существенным образом различаются как целями и информацией, так и методами. На фазе, в которой одним из вопросов является выбор относительно небольшого числа альтернатив (эту фазу часто называют early screening). ЛПР должно принять во внимание все возможные пути достижения цели. В процессе же детального анализа и окончательного выбора альтернативы, ЛПР ограничивает себя малым числом подготовленных вариантов решений. Выбору альтернативы из этого числа предшествует их детальное изучение.

Рис. 1 - Фазы процесса принятия решений

Классификация задач принятия решений

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

где - постановка задачи;

- множество допустимых альтернативных вариантов;

- множество методов измерения предпочтений;

- множество методов измерения предпочтений (например, использование различных шкал);

- отображение множества допустимых альтернатив в множество критериальных оценок;

- системы предпочтений эксперта;

- решающее правило, отражающее систему предпочтений.

Любой из элементов этого набора может служить классификационным признаком принятия решений.

По виду отображения F. Попытки применения исследования операций для решения различного класса задач выявили большие различия в природе изучаемых систем. В связи с этим Г. Саймоном и А. Ньюэллом была предложена следующая классификация:

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

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

3 Неструктурированные или качественно выраженные проблемы, содержащие лишь описание важнейших ресурсов, признаков и характеристик, количественные зависимости между которыми совершенно неизвестны.

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

Характерными особенностями проблем третьего класса являются:

1 уникальность выбора в том смысле, что каждый раз проблема является новой для ЛПР;

2 неопределенность в оценках альтернативных вариантов решений проблемы;

3 качественный характер оценки вариантов решения проблемы, чаще всего формулируемой в словесной форме;

4 оценка альтернатив может быть получена лишь на основе субъективных предпочтений ЛПР или ГПР;

5 критериальные оценки могут быть получены только от экспертов.

К этому классу проблем относятся, например, проблемы планирования научных исследований, конкурсного отбора проектов, планирования развития города и т.д.

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

По постановке задачи Т. Задачи принятия решений можно разбить на две группы:

Задачи первой группы:

Дано: группа из альтернатив-вариантов решения проблемы и критериев, предназначенных для оценки альтернатив; каждая из альтернатив имеет оценку по каждому из критериев. Требуется: построить решающие правила на основе предпочтений ЛПР, позволяющие: выделить лучшую альтернативу; упорядочить альтернативы по качеству; отнести альтернативы к упорядоченным по качеству классам решений.

Задачи второй группы:

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

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

А теперь от теории принятия решений перейдём к матричным играм.

Матричная игра игроков с нулевой суммой может рассматриваться, как следующая абстрактная игра двух игроков.

Игрок А имеет m стратегий i = 1, 2, …, m. Игрок В имеет n стратегий j = 1, 2, …, n. Каждой паре стратегий (i, j) поставлено в соответствие число а, выражающее выигрыш игрока А за счет игрока В, если первый игрок примет свою i-ю стратегию, а второй - свою j-ю стратегию.

Каждый из игроков делает один ход: игрок А выбирает свою i-ю стратегию (i = ), В - свою j-ю стратегию (j = ), после чего игрок А получает выигрыш а за счет игрока А (если а< 0, то это значит, что игрок В платит второму сумму |а|). На этом игра заканчивается.

Каждая стратегия игрока i = или j = часто называется чистой стратегией.

Если рассмотреть матрицу А:

а	а	…	а	…	а
…	…	…	…	…	…
а	а	…	а	…	а
…	…	…	…	…	…
а	а	…	а	…	а

то проведение каждой партии матричной игры с матрицей сводится к выбору игроком А i-й строки, а игроком В j-го столбца и получения игроком А (за счет игрока В) выигрыша а.

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

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

а (i = )

т.е. определяется минимальный выигрыш для игрока А при условии, что он примет свою i-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = i, при которой этот минимальный выигрыш будет максимальным, т.е. находится

а = а= ?

1.2 Определение игры

Дадим определение понятию «Игра». Игрой называется набор

,

где N - произвольное множество игроков; S - произвольное множество всех исходов игры; X_K - произвольное множество стратегий коалиции KN; S(X^K) S - множество возможных исходов, если коалиция K применяет стратегию х^KХ_K; - транзитивное отношение предпочтения коалиции KN на S. При математической формализации игра, должна проходить по определенным правилам, которые представляют следующую систему условий:

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

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

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

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

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

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

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

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

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

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

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

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

1 чередование ходов, которые могут быть как личными, так и случайными

2 возможная недостаточность информации

3 функция выигрыша

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

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

2 поиск доминирующих стратегий (в случае успеха этого поиска - отбрасывание доминирующих строк и столбцов в исходной матрице игры).

3 замена игры на её смешанное расширение и отыскание оптимальных смешанных стратегий и цены игры.

	Игрок 2 стратегия 1	Игрок 2 стратегия 2
Игрок 1 стратегия 1	4, 3	-1, -1
Игрок 1 стратегия 2	0, 0	3, 4
Нормальная форма для игры с 2 игроками, у каждого из которых по 2 стратегии.

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

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

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

X \ Y	Орел	Решка
Орел	-1, 1	1, -1
Решка	1, -1	-1, 1

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

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

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

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

Более того, существует хотя бы одна ситуация в смешанных стратегиях , для которой выполняется соотношение

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

Приведём доказательство данной теоремы (автор: Дж. Б. Данциг, 1951г.)

Теорема. Каждая матричная игра с нулевой суммой всегда имеет решение в смешанных стратегиях, т.е. существуют такое число и такие стратегии и игроков 1 и 2 соответственно, выполняются неравенства:

.(*)

Комментарий. Формула (*) означает, что: если игрок 1 отклоняется от своей оптимальной стратегии, то его выигрыш не увеличивается по сравнению с ценой игры; если от своей оптимальной стратегии отклоняется игрок 2, то по сравнению с ценой игры его проигрыш не уменьшается.

Доказательство.

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

.

Из этого следует, что от увеличения всех элементов матрицы на величину цена игры увеличивается на эту величину, причём оптимальные смешанные стратегии не изменяются.

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

1.3 Классификация игр

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

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

1 так называемая позиционная форма. При этом определяются:

· порядок ходов

· альтернативы (возможные ходы), доступные каждому из игроков на момент наступления его хода

· информация, которой владеет каждый из игроков на момент очередного хода

· выигрыши (для каждого игрока) как функции от выбранных ходов

· вероятностные распределения на множестве возможных состояний внешней среды

2. нормальная или стратегическая форма. Каждый участник (игрок) k, где, характеризуется наличием индивидуальной системы целевых установок и множеством стратегий , т.е. возможных вариантов действий в игре.

Ранее упоминалось о таком понятии, как «антагонистическая игра». Примером такой игры может служить игра «Орлянка». Дадим определение антагонистической игре.

Антагонистическая игра - игра, в которой участвуют два игрока (обычно обозначаемые I и II) с противоположными интересами. Для антагонистической игры характерно, что выигрыш одного игрока равен проигрышу другого и наоборот, поэтому совместные действия игроков, их переговоры и соглашения лишены смысла.. Определяются антагонистические игры заданием множеств стратегий игроков и выигрышей игрока I в каждой ситуации, состоящей в выборе игроками своих стратегий. Таким образом, формально антагонистическая игра есть тройка ‹А, В, Н›, в которой А и В - множества стратегий игроков, а Н (а, b) - вещественная функция (функция выигрыша) от пар (а, b), где а ? A, b ? В. Игрок I, выбирая а, стремится максимизировать Н(а, b), а игрок II, выбирая b, - минимизировать Н (а, b).

Пример 2:

Рассмотрим игру G (4х5) в матричной форме.

	3	4	5	2	3
	1	8	4	3	4
	10	3	1	7	6
	4	5	3	4	8

Очевидно надо выбирать ту стратегию, при которой выигрыш максимален. (Это так называемый принцип минимакса. О нём чуть позже). В правом добавочном столбце запишем минимальное значение выигрыша в каждой строке; обозначим его для i-ой строки .

	3	4	5	2	3	2
	1	8	4	3	4	1
	10	3	1	7	6	1
	4	5	3	4	8	3
	10	8	5	7	8

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

Теорема о минимаксе.

Можно доказать, что для любой функции F(x,y) определённой на произвольном декартовом произведении X ? Y имеет место неравенство . Отсюда следует, что

Запишем 2 утверждения:

Утверждение 1. Точка 0 (в m-мерном пространстве) содержится в выпуклой оболочке m+n точек

и

Утверждение 2. Существуют числа удовлетворяющие условиям

Доказательство: Пусть А - матричная игра. Имеет место либо утверждение 1, либо утверждение 2. Если верно утверждение 1 то 0 является выпуклой линейной комбинацией m+n векторов. Поэтому существуют такие

что

Если бы все числа были бы равны нулю, то 0 оказывался бы выпуклой линейной комбинацией m единичных векторов , что невозможно, т.к. они линейно независимы. Следовательно, по крайней мере одно из чисел положительно и

тогда можно положить

и получится для всех i

Значит и

Предположим, что верно утверждение 2. Тогда , так что . Следовательно, неравенство не имеет смысла. Предположим, что игра А изменена на игру , где . Для любых х и y , поэтому . Так как неравенство не имеет смысла, то неравенство также не выполняется. Но k произвольно. Значит неравенство невозможно. Т.к. то . Что и требовалось доказать.

Принцип минимакса.

Рассмотрим игру с платежной матрицей Следует определить наилучшую стратегию игрока I среди стратегий , и игрока II среди стратегий , . Определение наилучших стратегий игроков основано на принципе, который предполагает, что противники, участвующие в игре, одинаково разумны и каждый из них делает все для того, чтобы добиться своей цели. Найдем наилучшую стратегию игрока I. Допустим, что он выбрал i-ю стратегию (i -ю строку матрицы (1)). Тогда он получит меньше, чем - наименьшее число в этой строке. Причем это будет в том случае, если игрок II каким-то образом раскроет стратегию игрока I. Из сказанного следует, что I игрок, если он не желает рисковать, т.е. играть не оптимально, должен действовать следующим образом - определить наименьшие элементы всех строк и выбрать ту из них, в которой это число наибольшее. В этом случае он гарантирует себе выигрыш равный наибольшему из меньших чисел всех строк. Этот выигрыш равен Число это “низкий выигрыш” игрока I и его называют нижним значением или нижней ценой игры. Как же рассуждает второй игрок? “Если я выберу j-ую стратегию (j-ый столбец), то самый лучший выигрыш у игрока I будет наибольшее число этого столбца. Чтобы рисковать, я должен выбрать столбец, в котором это число наименьшее. В результате I игрок не сможет получить больше, чем Число представляет собой ”верхний выигрыш” игрока I и называется верхним значение или верхней ценой игры. Можно показать, что для всякой матричной игры выполняется условие . Если , то такие игры называются играми с седловой точкой. Из неравенства следует, что . Это фактически означает, игрок I мог бы рассчитывать на выигрыш .

1.4 Матричные игры

В этом параграфе будет рассказано о принципе максимина, рациональном представлении матрицы игры, о решении игры при помощи фиктивного разыгрывания.

	н/ч	ч
н/ч	1	-1
ч	-1	1

Начнём непосредственно с матричных игр. Тройка (где x и y - множества, H - функция от двух переменных ) называется антагонистической игрой. Процесс разыгрывания конечной антагонистической игры (игра называется конечной, если тройка конечна) состоит в том, что игроки 1 и 2 независимо друг от друга выбирают соответственно некоторые чистые стратегии x и y, в результате чего складывается ситуация (x,y).

Мы знаем, что антагонистическую игру двух участников с нулевой суммой (напомним, что нулевая сумма - это когда выигрыш одного игрока равен проигрышу другого) удобно задавать с помощью, так называемой платёжной матрицы. Каждый элемент такой матрицы содержит числовое значение выигрыша игрока 1 (или проигрыша игрока 2) в ситуации, когда первый игрок применяет стратегию i, а второй - стратегию j. Классическим примером антагонистической игры является игра с двумя участниками, которые независимо друг от друга загадывают числа. Предполагается, что если сумма оказывается чётной, то выигрыш равный 1, достаётся первому игроку, а если нечётной, то второму. Если предположить, что загадывание нечётного числа - стратегия первого игрока, а загадывание чётного числа - стратегия второго игрока, то платёжная матрица выглядит следующим образом:

Строки матрицы соответствуют стратегиям игрока 1, столбцы - стратегиям игрока 2, а её элементы - результатам (т.е. выигрышам) первого. Если взять элементы матрицы с обратным знаком, то это будут выигрыши второго игрока. Здесь надо отметить, что вопрос о выборе стратегии является основным в теории игр. Для примера проанализируем произвольную игру . При выборе игроком 1 стратегии i, его выигрыш в независимости от игрока 2 составит . Стратегия I произвольно, поэтому главная цель игрока 1 максимизировать величину полученного выигрыша, т.е. получить . Такой принцип получил название принципа максимина. Напомним, что максимин - это выигрыш максимальный из минимальных. Надо также отметить, что принцип максимина обеспечивает игрокам гарантированный «выигрыш» при любых стратегиях противников.