Сайт бесплатных игр

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Введение

1. Теоретическая часть

1.3 Игра порядка 2х2

1.4 Алгебраический метод

1.5 Графический метод

1.6 Игры 2xn или mx2

1.7 Решения игр матричным методом

2. Практическая часть

2.2 Игры 2xn и mx2

2.3 Матричный метод

2.4 Метод Брауна

Анализ результатов

Введение

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

Формально антагонистическая игра может быть представлена тройкой , где X и Y -- множества стратегий первого и второго игроков, соответственно, F -- функция выигрыша первого игрока, ставящая в соответствие каждой паре стратегий (x,y), где действительное число, соответствующее полезности первого игрока при реализации данной ситуации.

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

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

1. Теоретическая часть

1.1 Основные определения и положения игры

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

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

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

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

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

1.1.1 Определение, примеры и решения матричных игр в чистых стратегиях

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

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

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

Каждая стратегия игрока i = 1, 2,…, т; j = 1, 2,…, п часто называется чистой стратегией.

Матричная игра двух игроков с нулевой суммой далее будет называться просто матричной игрой. Очевидно матричная игра относится к антагонистическим играм. Из ее определения следует, что для задания матричной игры достаточно задать матрицу А = (a ij) порядка тп выигрышей первого игрока.

Если рассмотреть матрицу выигрышей

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

Для формализации реальной конфликтной ситуации в виде матричной игры надо выделить и перенумеровать чистые стратегии каждого игрока и составить матрицу выигрышей.

Следующий этап -- это определение оптимальных стратегий и выигрышей игроков.

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

(i = 1, 2,..., m) (1.2)

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

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

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

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

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

Определение. Если в игре с матрицей А нижняя и верхняя чистые цены игры совпадают, т. е. б = в, то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры:

н = б = в (1.6)

Седловая точка -- это пара чистых стратегий () соответственно первого и второго игроков, при которых достигается равенство

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

где i, j -- любые чистые стратегии соответственно первого и второго игроков; (i 0 , j 0) -- стратегии, образующие седловую точку. Ниже будет показана эквивалентность определения седловой точки условиям (1.8).

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

Чистые стратегии i 0 и j 0 образующие седловую точку, называются оптимальными чистыми стратегиями соответственно первого и второго игроков.

Теорема 1. Пусть f (х, у) вещественная функция двух переменных х А и у В и существует

тогда б = в.

Доказательство. Из определения минимума и максимума следует, что

Поскольку в левой части (1.11) х любое, то

В правой части неравенства (1.12) у любое, поэтому

что и требовалось доказать.

В частности, матрица () есть частный случай функции f (х, у), т. е. если положить х = i, у = j, = f (х, у), то из теоремы 1 получим, что нижняя чистая цена не превосходит верхнюю чистую цену игры в матричной игре.

Определение. Пусть f (х, у) действительная функция двух переменных х А и у В. Точка (х 0 , у 0) называется седловой для функции f (х, у), если выполняются следующие неравенства

f (х, у 0) f (х 0 , у 0)f (х 0 , у) (1.14)

при любых х А и у В.

1.2 Оптимальные смешанные стратегии и их свойства

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

Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Таким образом, если первый игрок имеет т чистых стратегий 1, 2, … i,… m, то его смешанная стратегия х -- это набор чисел х = (х 1 , х 2 , ..., х i ,…, х т) удовлетворяющих соотношениям

x i 0 (i = 1, 2, ... , т), = 1. (1.15)

Аналогично для второго игрока, который имеет п чистых стратегий, смешанная стратегия у -- это набор чисел у = (у 1 ,…, у j , … у n), удовлетворяющих соотношениям

y j 0 (j = 1, 2, ... , n), = 1. (1.16)

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

Очевидно, чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью единица, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока.

Определение. Средний выигрыш первого игрока в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей

Е (А, х, у)= (1.20)

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

1.3 Игра порядка 22

Матричная игра порядка 22 задается следующей матрицей выигрышей первого игрока:

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

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

Обозначим через х=(х 1 ,х 2), у=(у 1 ,у 2) смешанные стратегии соответственно первого и второго игроков. Напомним, что х 1 означает вероятность применения первым игроком своей первой стратегии, а х 2 = 1 - х 1 - вероятность применения им своей второй стратегии. Аналогично для второго игрока: у 1 - вероятность применения им первой стратегии, у 2 = 1 - у 1 - вероятность применения им второй стратегии.

Согласно следствию из теореме, для оптимальности смешанных стратегий х и у необходимо и достаточно, чтобы для неотрицательных х 1 , х 2 , у 1 , у 2 выполнялись следующие соотношения:

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

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

0<<1, 0<< 1,

0< <1, 01. (1.25)

Предположим, что оба неравенства из (1.22) будут строгими

тогда согласно теореме должно у 1 = у 2 = 0, что противоречит условиям (1.25).

Аналогично доказывается, что оба неравенства из (1.23) не могут быть строгими неравенствами.

Предположим теперь, что одно из неравенств (1.22) может быть строгим, например первое

Это значит, что согласно теореме у 1 = 0, у 2 =1. Следовательно, из (1.23) получаем

Если оба неравенства (1.24) строгие, то по теореме должно х 1 = х 2 = 0, что противоречит (1.25). Если же а 12 а 22 , то одно из неравенств (1.27) строгое, а другое -- равенство. Причем равенство будет выполняться для большего элемента из а 12 и а 22 , т. е. одно неравенство из (1.27) должно быть строгим. Например а 12 < а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

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

Итак, если матричная игра порядка 22 не имеет седловой точки, то оптимальные смешанные стратегии игроков и цену игры можно определить, решив систему уравнений (1.24). Установлено также, что если в матричной игре порядка 2x2 один из игроков имеет оптимальную чистую стратегию, то и другой игрок также имеет оптимальную чистую стратегию.

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

1.4 Алгебраический метод

Возможны два случая для решения задач алгебраическим методом:

1. матрица имеет седловую точку;

2. матрица не имеет седловую точку.

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

Отыщем стратегии и. При использовании первым игроком своей оптимальной стратегии второй игрок может, например, применить две такие чистые стратегии

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

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

Систему уравнений, аналогичную (2.5), (2.6) можно составить и для оптимальной стратегии второго игрока:

Принимая во внимание условие нормировки:

Решим совместно уравнение (1.37) - (1.41) относительно неизвестных можно решать и не все сразу, а по три: отдельно (1.36), (1.38), (1.40) и (1.37), (1.39), (1.41). В результате решения получим:

1.5 Графический метод

Приближенное решение игры 22 можно довольно просто получить воспользовавшись графическим методом. Суть его заключается в следующем:

Рисунок 1.1- нахождение участка единичной длинны

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

Проведены две оси I-I и II-II. На I-I будем откладывать выигрыш при использовании первым игроком первой стратегии, на II-II при использовании им второй стратегии. Пусть, например, второй игрок применил свою первую стратегию, тогда на оси I-I следует отложить величину, а на оси II-II - величину

При любой смешанной стратегии первого игрока его выигрыш определится величиной отрезка. Линия I-I соответствует применению первой стратегии вторым игроком, будем её называть первой стратегией второго игрока. Аналогично можно построить и вторую стратегию второго игрока. Тогда в целом графическое отображение матрицы игры примет такой вид:

Рисунок 1.2 - нахождение цены игры

Следует однако отметить, что это построение проводилось для первого игрока. Здесь длина отрезка ровна цене игры V.

Линия 1N2 называется нижней границей выигрыша. Здесь наглядно видно, что точка N соответствует максимальной величине гарантированного выигрыша первого игрока.

Вообще то говоря, стратегию второго игрока также можно определить из этого рисунка, например такими способами. На оси I-I:

либо на оси II-II

Однако стратегию второго игрока можно определить и аналогично тому, как это делается для первого игрока, т.е. построить такой график.

Рисунок 1.3 - определение стратегии второго игрока

Здесь линия 1N2 - верхняя граница проигрыша. Точка N соответствует минимальному из возможных проигрышей второго игрока, она то и определяет стратегию.

В зависимость от конкретных значений коэффициентов матрицы графика могут иметь и иной вид, например, такой:

Рисунок 1.4 - определяет оптимальную стратегию первого игрока

В такой ситуации оптимальная стратегия первого игрока является чистой:

1.6 Игры 2n или m2

В играх порядка 2n первый игрок имеет 2 чистых стратегии, а второй n чистых стратегий, т.е. матрица выигрышей первого игрока имеет вид:

Если такая игра имеет седловую точку, то её легко найти и получить решение.

Предположим, что игра имеет седловые точки. Тогда необходимо найти такие смешанные стратегии и соответственно первого и второго игроков и цену игры v, которые удовлетворяют соотношениям:

Поскольку игра не имеет седловой точки, то неравенство (1.54) заменяют не равенствами

Для решения систем (1.56), (1.55), (1.53) целесообразно воспользоваться графическим методом. С целью введем обозначения для левой части неравенства (1.53)

матричный игра математический модель

или, поставив из (1.55) и проведя простые преобразования, получим

где - это средний выигрыш первого игрока при условии, что он применяет свою смешанную стратегию, а второй свою j-ю чистую стратегию.

Каждому значению j=1, 2, … , n согласно выражению соответствует прямая линия в прямоугольной системе координат.

Цель второго игрока минимизировать выигрыш первого игрока за счет выбора своих стратегий. Поэтому вычисляем

где - нижняя граница множества ограничений. На рисунке 1.6 график функции изображен жирной линей.

Размещено на http://www.allbest.ru/

Рисунок 1.6 - график функции

Цель первого игрока максимизировать свой выигрыш за счет выбора, т.е. вычислить

На рисунке 1.6 точка означает максимальное значение, которое получается при. Цена игры, так как:

Таким образом графически определяется оптимальная смешанная стратегия первого игрока и пара чистых стратегий второго игрока, которые в пересечении образуют точку На рисунке 1.6 изображены 2-я и 3-я стратегия второго игрока. Для таких стратегий неравенства (1.53) превращаются в равенства. На рисунке 1.6 это стратегии j=2, j=3.

Теперь можно решить систему уравнений

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

а остальные Эту систему можно решить, пологая Если при некоторой j=j 0 стратегии второго игрока образуют точку М 0 и то максимальное значение нижней границы множеств ограничений изображается отрезком, параллельным оси В этом случае первый игрок имеет бесконечно много оптимальных значений а цена игры Этот случай изображен на рисунке 1.7, где и отрезок MN изображают верхнее ограничений, оптимальные значения находятся в пределах У второго игрока имеется чистая оптимальная стратегия j=j 0 .

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

Смешанные стратегии соответственно первого и второго игроков определяются аналогично, как в случае игр порядка 2n. Пусть по горизонтальной оси откладывается значение от 0 до 1, по вертикальной - значение среднего выигрыша) первого игрока при условиях, что первый игрок применяет свою чистую i-ю стратегию (i=1, 2, …, m), второй - свою смешанную стратегию (y 1 , 1- y 1) =y. Например, при m=4 графически) могут быть представлены так, как изображено на рисунке 1.7.

Рисунок 1.7 - график функции)

Первый игрок старается максимизировать свой средний выигрыш, поэтому он стремиться найти

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

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

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

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

1.7 Матричный метод решения игр

Обозначения:

Любая квадратная подматрица матрицы порядка

Матрица (1);

Матрица, транспонированная к;

Матрица, присоединенная к В;

- (1) матрица полученная из X вычеркиванием элементов, которые соответствуют строкам, вычеркнутым из при получении;

- (1) матрица полученная из вычеркиванием элементов, которые соответствуют строкам, вычеркнутым из при получении.

Алгоритм:

1. Выберем квадратную подматрицу матрицы порядка () и вычислим

2. Если некоторое или, то отбрасываем найденную матрицу и пробуем другую матрицу.

3. Если (), (), вычисляем и строим X и из и, добавляя в соответствующих местах нули.

Проверяем, удовлетворяются ли неравенства

для каждого (1.75)

и неравенства

для каждого (1.76)

Если одно из соотношений не выполнено, то пробуем другое. Если все соотношения справедливы, то X, и искомые решения.

1.8 Метод последовательного приближения цены игры

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

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

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

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

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

2. Практическая часть

Пара решает куда пойти погулять и с пользой для двоих провести время.

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

Парень предлагает пойти сходить в технопарк, после посмотреть матч футболистов местного клуба в центральном стадионе.

В соответствии с этим нужно найти за какое время будет достигнута цель одного из игроков. Матрица выигрышей будет выглядеть таким образом:

Таблица 1. Матрица выигрышей

Стратегии

Так как 1 2 , Очевидно, в этой игре нет седловой точки в чистых стратегиях. Поэтому воспользуемся следующими формулами, и получим:

Размещено на http://www.allbest.ru/

2.2 Игра 2xn и mx2

Задача 1(2xn)

Выращивается две зерновые культуры для сухого и влажного климата.

А состояние природы можно рассматривать как: сухое, влажное, умеренное.

Размещено на http://www.allbest.ru/

Максимальное значение М() достигается в точке М, образуемой пересечением линий, соответствующих j=1, j"=2. По этому полагаем: ,

Задача 2(mx2)

Парень и девушка рассматривают варианты куда пойти на выходные.

Выбор места отдыха можно представить как: парк, кино, рессторан.

Размещено на http://www.allbest.ru/

Максимальное значение М() достигается в точке E, образуемой пересечением линий, соответствующих j=1, j"=2. По этому полагаем: ,

Для определения значения, v надо решить следующие уравнения:

2.5 Матричный метод

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

Центральный ресторан включает следующие услуги:

1) более дорогое и качественное обслуживание клиентов;

2) блюда ориентированы на французскую кухню;

Второй ресторан предоставляет:

1) не дорогое и качественное обслуживание;

2) меню сочетает в себе различные известные кухни мира;

3) также постоянные акции и скидки;

4) осуществляет доставку и принимает заказы по доставке на дом.

В соответствии с заданием прибыль за один день между двумя ресторанами распределится следующим образом:

Таблица 2. Матрица выигрышей

Стратегии

Решение игры вида матричным способом:

Существует шесть подматриц и:

Рассмотрим матрицу:

x 1 = ? 0, x 2 = ? 0

Так как x 2 = < 0, то мы отбрасываем.

Рассмотрим теперь матрицу:

x 1 = ? 0, x 2 = ? 0

Цена игры.

Это соотношение противоречит требованию, поэтому не подходит.

Рассмотрим теперь матрицу:

x 1 = , x 2 = ? 0,

y 1 = < 0, y 2 = ? 0.

Так как y 1 = < 0, то мы отбрасываем и.

Рассмотрим теперь матрицу:

x 1 = , x 2 = 0, так как x 2 = 0, то мы отбрасываем и.

Рассмотрим теперь матрицу:

x 1 = , x 2 = ? 0. Так как x 1 = 0, то мы отбрасываем и.

Рассмотрим теперь матрицу:

x 1 = , x 2 =, y 1 = , y 2 =, то продолжаем дальше:

x 1 = , x 2 =, y 1 = , y 2 = или

Цена игры.

Теперь проверяются основные соотношения:

Размещено на http://www.allbest.ru/

Ответ: x 1 = , x 2 =, y 1 = , y 2 = , y 3 =0, y 4 =0,.

Метод Брауна

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

Пусть игра задана следующей матрицей выигрышей:

Предположим, что второй игрок выбрал свою 2-ю стратегию, тогда первый получит:

2, если он применит свою 1-ю стратегию,

3, если он применит свою 3-ю стратегию.

Полученные значения сводится в таблицу 1.

Таблица 3. Стратегия второго игрока

№ партии	Стратегия 2-го игрока	Выигрыш 1-го игрока

Из таблицы 3 видно, что при 2-й стратегии второго игрока первый получит наибольший выигрыш 3, используя свою 2-ю либо 3-ю стратегию. Поскольку первый игрок желает получить максимальный выигрыш, то он на 2-ю стратегию второго игрока отвечает своей 2-й стратегией. При 2-й стратегии первого игрока второй проиграет:

1, если он применит свою 1-ю стратегию,

3, если он применит свою 2-ю стратегию,

4, если он применит свою 3-ю стратегию.

Таблица 4. Стратегия первого игрока

№ партии	Стратегия 1-го игрока	Проигрыш 2-го игрока

Из таблицы 2 видно, что при 2-й стратегии первого игрока второй игрок будет иметь наименьший проигрыш 1, если он применит свою 1-ю стратегию. Поскольку второй игрок желает проиграть меньше, то в ответ на 2-ю стратегию первого игрока он применит свою 1-ю стратегию. Полученные результаты сводятся в таблицу 5.

Таблица 5. Стратегии соответственно первого и второго игроков

№ партии

Стратегия 2-го игрока

Суммарный выигрыш 1-го игрока

Стратегия 1-го игрока

В табл. 5 в столбце стратегии второго игрока во второй строке находится цифра 1, которая указывает, что во второй партии второму игроку выгодно применять свою 1-ю стратегию; в столбце и находится наибольший средний выигрыш 3 первого игрока, полученный им в первой партии; в столбце w стоит наименьший средний проигрыш 1, полученный вторым игроком в первой партии; в столбце v находится среднее арифметическое v = (и + w) -- т. е. приближенное значение цены игры, полученное в результате проигрывания одной партии игры. Если второй игрок применит свою 1-ю стратегию, то первый получит 3, 1, 2 соответственно при своих 1-й, 2-й, 3-й стратегиях, а суммарный выигрыш первого игрока за обе партии составит:

2 + 3=5 при его 1-й стратегии,

3 + 1=4 при его 2-й стратегии,

3 + 2=5 при его 3-й стратегии.

Эти суммарные выигрыши записываются во второй строке табл. 3 и в столбцах, соответствующих стратегиям первого игрока: 1, 2, 3.

Из всех суммарных выигрышей наибольшим является 5. Он получается при 1-й и 3-й стратегии первого игрока, то ему можно выбирать любую из них; скажем, в таких случаях, когда имеются два (или несколько) одинаковых суммарных выигрышей, выбирают стратегию с наименьшим номером (в нашем случае надо взять 1-ю стратегию).

При 1-й стратегии первого игрока второй проиграет 3, 2, 3 соответственно 1-й, 2-й, 3-й его стратегиям, а суммарный проигрыш второго игрока за обе партии составит:

1 + 3=4 при его 1-й стратегии,

3 + 2=5 при его 2-й стратегии,

4 + 3=7 при его 3-й стратегии.

Эти суммарные проигрыши записываются во второй строке табл. 5 и в столбцах, соответствующих 1-й, 2-й, 3-й стратегиям второго игрока.

Из всех суммарных проигрышей второго игрока наименьшим является 4. Он получается при его 1-й стратегии, следовательно, в третьей партии второй игрок должен применить свою 1-ю стратегию. В столбец и ставится наибольший суммарный выигрыш первого игрока за две партии, деленный на число партий, т. е. ; в столбец w ставится наименьший суммарный проигрыш второго игрока за две партии, деленный на число партий, т. е. ; в столбце v ставится среднее арифметическое этих значений, т. е. = Это число принимается приближенное значение цены игры при двух «сыгранных» партиях.

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

Таблица 6. Суммарные выигрыш и проигрыш игроков при двух сыгранных партиях

Стратегия 2-го игрока

Суммарный выигрыш 1-го игрока

Стратегия 1-го игрока

Суммарный проигрыш 2-го игрока

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

3 + 5 = 8 при его 1-й стратегии,

1 +4 = 5 при его 2-й стратегии,

2 + 5 = 7 при его 3-й стратегии.

Эти суммарные выигрыши первого игрока записываются в третьей строке таблица 6 и столбцах, соответствующих его стратегиям 1, 2, 3. Так как наибольший суммарный выигрыш 8 первого игрока получается при 1-й стратегии, соответственно выбирает 1-ю.

При 1-й стратегии первого игрока второй проиграет 3, 1, 2 соответственно 1-й, 2-й, 3-й его стратегиям, а суммарный проигрыш второго игрока за обе партии составит:

3 + 4=7 при его 1-й стратегии,

2 + 5=7 при его 2-й стратегии,

3 + 7=10 при его 3-й стратегии.

Эти суммарные проигрыши записываются во третьей строке табл. 6 и в столбцах, соответствующих 1-й, 2-й, 3-й стратегиям второго игрока. Из всех суммарных его проигрышей 7 является наименьшим и получается при его 1-й и 2-й стратегиях, далее второму игроку надо применить свою 1-ю стратегию.

В табл. 6 в третьей строке в столбце и записывается наибольший суммарный выигрыш первого игрока за три партии, деленный на число партии, т. е. ; в столбце w ставится наименьший суммарный проигрыш второго игрока за три партии, деленный на число партий, т. е. ; в столбце v ставится их среднее арифметическое

Таким образом получаем табл. 7 для трех партий.

Таблица 7. Суммарные выигрыш и проигрыш игроков при трех сыгранных партиях

№ партии

Стратегия 2-го игрока

Суммарный выигрыш 1-го игрока

Стратегия 1-го игрока

Суммарный проигрыш 2-го игрока

Таблица 8. Конечная таблица при двадцати сыгранных партиях

№ партии

Стратегия 2-го игрока

Суммарный выигрыш 1-го игрока

Стратегия 1-го игрока

Суммарный проигрыш 2-го игрока

Из табл. 7 и 8 видно, что в 20-ти проигранных партиях стратегии 1, 2, 3 для первого игрока встречаются соответственно 12, 3, 5 раз, следовательно, их относительные частоты соответственно равны; стратегии 1, 2, 3 для второго игрока встречаются соответственно 7, 11,2 раза, следовательно их относительные частоты соответственно равны; приближенное значение цены игры. Такое приближение достаточно хорошее.

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

Анализ результатов

В данной курсовой работе изучен материал нахождения решения антагонистических игр графическим, матричным методом, методом последовательного приближения цены игры. Найдены оптимальные стратегии первого и второго игрока, а также цена игры в играх 2x2, 2xn и mx2, а так же в играх с использованием матричного метода и метода Брауна.

На примере пары была смоделирована игра 2x2, которая была решена алгебраическим и графическим методом. Решая игру алгебраическим методом решение показывает, что применяя свои оптимальные смешанные стратегии первый и второй игрок проведут вместе 4.6 часа. Графическое решение задачи получилось с небольшой погрешностью и составило 4.5 часа.

А так же были смоделированы две задачи 2xn и mx2. В задаче 2xn была рассмотрена с/х культура и стратегия показывает, что лучше поле засадить 50 на 50, а цена игры составила 3.75 млн. рублей. А в задаче mx2 была рассмотрена пара, стратегия которой показала, что дешевле пойти в парк и кино, а цена затраты составят 4.3 рублей.

Была смоделирована задача для матричного метода, в которой рассматривались два ресторана, решение задачи показало, что при применение свой оптимальной смешанной стратегии прибыль первого ресторана составит 15.6 млн. рублей, а при использовании своей оптимальной смешанной стратегии вторым рестораном, он не позволит первому заработать больше 15.6 млн. рублей. Решение графическим методом дало погрешность и цена игры составила 14.9 млн. рублей.

Для метода Брауна была составлена задача в которой рассматривается профсоюз и руководство компании, их задача обеспечить питание рабочих. При использовании обоими игроками своих оптимальных стратегий питание на человека составит 2.45 тыс. руб.

Список использованных источников

1) Вилисов В.Я. Конспект лекций «Теория игр и статистических решений», - Филиал - «Восход» МАИ. 1979. 146 с.

2) Крушевский А.В. Теория игр, - Киев: Вища школа, 1977. - 216 с.

3) Черчмень У., Акоф Р., Арноф Л., Введение в исследование операций. - М.: Наука. 1967. - 488 с.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0 %B3%D0%BE%D0%BD%D0%B8%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

Размещено на Allbest.ru

Подобные документы

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

курсовая работа , добавлен 05.05.2010


Игры, повторяемые многократно, их отличительные свойства и этапы. Смешанные стратегии, условия и возможности их использования на практике. Аналитический метод решения игры типа 2 x 2. Основные теоремы для прямоугольных игр. Алгебраические решения.

презентация , добавлен 23.10.2013


Основные определения теории биматричных игр. Пример биматричной игры "Студент-Преподаватель". Смешанные стратегии в биматричных играх. Поиск "равновесной ситуации". 2x2 биматричные игры и формулы для случая, когда у каждого игрока имеется две стратегии.

реферат , добавлен 13.02.2011


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

курсовая работа , добавлен 17.10.2014


Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта. Итеративный метод Брауна-Робинсона. Монотонный итеративный алгоритм решения матричных игр.

дипломная работа , добавлен 08.08.2007


Составление платежной матрицы, поиск нижней и верхней чисты цены игры, максиминной и минимаксной стратегии игроков. Упрощение платежной матрицы. Решение матричной игры с помощью сведения к задаче линейного программирования и надстройки "Поиск решения".

контрольная работа , добавлен 10.11.2014


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

курсовая работа , добавлен 17.08.2013


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

дипломная работа , добавлен 01.06.2015


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

лабораторная работа , добавлен 21.06.2013


Проектирование математической модели. Описание игры в крестики-нолики. Модель логической игры на основе булевой алгебры. Цифровые электронные устройства и разработка их математической модели. Игровой пульт, игровой контроллер, строка игрового поля.

Самым простым случаем, подробно разработанным в теории игр, является конечная парная игра с нулевой суммой (антагонистическая игра двух лиц или двух коалиций). Рассмотрим такую игру G , в которой участвуют два игрока А и В, имеющие противоположные интересы: выигрыш одного равен проигрышу другого. Так как выигрыш игрока А равен выигрышу игрока В с обратным знаком, мы можем интересоваться только выигрышем а игрока А. Естественно, А хочет максимизировать, а В - минимизировать а. Для простоты отождествим себя мысленно с одним из игроков (пусть это будет А) и будем его называть «мы», а игрока В - «противник» (разумеется, никаких реальных преимуществ для А из этого не вытекает). Пусть у нас имеется т возможных стратегий А 1 , A 2 , ..., А m , а у противника - n возможных стратегий В 1 , В 2 , ..; В n (такая игра называется игрой т × n ). Обозначим а ij наш выигрыш в случае, если мы пользуемся стратегией A i , а противник-стратегией B j .

Таблица 26.1

A i B j	B 1	B 2		B n
A 1 A 2 A m	a 11 a 21 a m1	a 21 a m		a 1 n a 2 n a mn

Предположим, что для каждой пары стратегий Л<, В, выигрыш (или средний выигрыш) a , j нам известен. Тогда в принципе можно составить прямоугольную таблицу (матрицу), в которой перечислены стратегии игроков и соответствующие выигрыши (см. таблицу 26.1).

Если такая таблица составлена, то говорят, что игра G приведена к матричной форме (само по себе приведение игры к такой форме уже может составить трудную задачу, а иногда и практически невыполнимую, из-за необозримого множества стратегий). Заметим, что если игра приведена к матричной форме, то многоходовая игра фактически сведена к одноходовой - от игрока требуется сделать только один ход: выбрать стратегию. Будем кратко обозначать матрицу игры (a ij ).

Рассмотрим пример игры G (4×5) в матричной форме. В нашем распоряжении (на выбор) четыре стратегии, у противника - пять стратегий. Матрица игры дана в таблице 26.2

Давайте, поразмышляем о том, какой стратегией нам (игроку А) воспользоваться? В матрице 26.2 есть соблазнительный выигрыш «10»; нас так и тянет выбрать стратегию А 3 , при которой этот «лакомый кусок» нам достанется. Но постойте: противник тоже не дурак! Если мы выберем стратегию А 3 , он, назло нам, выберет стратегию В 3 , и мы получим какой-то жалкий выигрыш «1». Нет, выбирать стратегию А 3 нельзя! Как же быть? Очевидно, исходя из принципа осторожности (а он - основной принцип теории игр), надо выбрать

Таблица 26.2

B j A i	B 1	B 2	B 3	B 4	B 5
A 1 A 2 A 3 A 4

ту стратегию, при которой наш минимальный выигрыш максимален. Это - так называемый «принцип минимакса»: поступай так, чтобы при наихудшем для тебя поведении противника получить максимальный выигрыш.

Перепишем таблицу 26.2 и в правом добавочном столбце запишем минимальное значение выигрыша в каждой строке, (минимум строки); обозначим его для i -й строки α i (см. таблицу 26.3).

Таблица 26.3

B j A i	B 1	B 2	B 3	B 4	B 5
A 1 A 2 A 3 A 4
β j

Из всех значений α i (правый столбец) выделено наибольшее (3). Ему соответствует стратегия A 4 . Выбрав эту стратегию, мы, во всяком случае, можем быть уверены, что (при любом поведении противника) выиграем не меньше, чем 3. Эта величина - наш гарантированный выигрыш; ведя себя осторожно, меньше этого мы получить не можем (я, может быть, получим и больше). Этот выигрыш называется нижней ценой игры (или «максимином» - максимальный из минимальных выигрышей). Будем обозначать его а. В нашем случае α = 3.

Теперь станем на точку зрения противника и порассуждаем за него. Он ведь не пешка какая-нибудь, а тоже разумен! Выбирая стратегию, он хотел бы отдать поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Если он выберет стратегию В 1 , мы ему ответим А 3 , и он отдаст 10; если выберет B 2 - мы ему ответим А 2 , и он отдаст 8 и т. д. Припишем к таблице 26.3 добавочную нижнюю строку и в ней запишем максимумы столбцов β j . Очевидно, осторожный противник должен выбрать ту стратегию, при которой эта величина минимальна (соответствующее значение 5 выделено в таблице 26.3). Эта величина β - то значение выигрыша, больше которого заведомо не отдаст нам разумный противник. Она называется верхней ценой игры (или «минимаксом» - минимальный из максимальных выигрышей). В нашем примере β = 5 и достигается при стратегии противника B 3 .

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

Теперь представим себе на минуту, что мы узнали о том, что противник придерживается стратегии В 3 . А ну-ка, накажем его за это и выберем стратегию А 1 - мы получим 5, а это не так уж плохо. Но ведь противник - тоже не промах; пусть он узнал, что наша стратегия А 1 ; он тоже поторопится выбрать В 4 , сведя наш выигрыш к 2, и т. д. (партнеры «заметались по стратегиям»). Одним словом, минимаксные стратегии в нашем примере неустойчивы по отношению к информации о поведении другой стороны; эти стратегиине обладают свойством равновесия.

Всегда ли это так? Нет, не всегда. Рассмотрим пример с матрицей, данной в таблице 26.4.

В этом примере нижняя Цена игры равна верхней: α = β = 6. Что из этого вытекает? Минимаксные стратегии игроков А и В будут устойчивыми. Пока оба игрока их придерживаются, выигрыш равен 6. Посмотрим, что будет, если мы (А) узнаем, что противник (В)

Таблица 26.4

B j A i	B 1	B 2	B 3	B 4
A 1 A 2 A 3
β j

держится стратегии B 2 ? А ровно ничего не изменится. Потому что любое отступление от стратегии А 2 может только ухудшить наше положение. Равным образом, информация, полученная противником, не заставит его отступить от своей стратегии В 2 . Пара стратегий А 2 , B 2 обладает свойством равновесия (уравновешенная пара стратегий), а выигрыш (в нашем случае 6), достигаемый при этой паре стратегий, называется «седловой точкой матрицы» 1). Признак наличия седловой точки и уравновешенной пары стратегий - это равенство нижней и верхней цены игры; общее значение α и β называется ценой игры. Мы будем обозначать его v :

α = β = v

Стратегии A i , B j (в данном случае А 2 , В 2 ), при которых этот выигрыш достигается, называются оптимальными чистыми стратегиями, а их совокупность - решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях. Обеим сторонам А и В можно указать их оптимальные стратегии, при которых их положение - наилучшее из возможных. А что игрок А при этом выигрывает 6, а игрок В - проигрывает 6,- что же, Таковы условия игры: они выгодны для А и невыгодны для В

1) Термин «седловая точка» взят из геометрии - так называется точка на поверхности, где одновременно достигается минимум по одной координате и максимум по другой.

У читателя может возникнуть вопрос: а почему оптимальные стратегии называются «чистыми»? Несколько забегая вперед, ответим на этот вопрос: бывают стратегии «смешанные», состоящие в том, что игрок применяет не одну какую-то стратегию, а несколько, перемежая их случайным образом. Так вот, если допустить кроме чистых еще и смешанные стратегии, всякая конечная игра имеет решение - точку равновесия. Но об атом речь еще впереди.

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

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

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

А теперь спросим себя, как быть, если игра не имеет седловой точки: α ≠ β ? Ну что же, если каждый игрок вынужден выбрать одну - единственную чистую стратегию, то делать нечего: надо руководствоваться принципом минимакса. Другое дело, если можно скоп стратегии «смешивать», чередовать случайным образом с какими-то вероятностями. Применение смешанных стратегий мыслится таким образом: игра повторяется много раз; перед каждой партией игры, когда игроку предоставляется личный ход, он «передоверяет» свой выбор случайности, «бросает жребий», и берет ту стратегию, которая выпала (как организовать жребий, мы уже знаем из предыдущей главы).

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

Итак, поговорим о смешанных стратегиях. Будем обозначать смешанные стратегии игроков А и В соответственно S A = (p 1 , р 2 , ..., p m ), S B = (q 1 , q 2 , …, q n ), где p 1 , p 2 , …, p m (образующие в сумме единицу) - вероятности применения игроком А стратегий А 1 , A 2 ,… , A m ; q 1 , q 2 , …, q n -вероятности применения игроком В стратегий В 1 , В 2 , ..., В n . В частном случае, когда все вероятности, кроме одной, равны нулю, а эта одна - единице, смешанная стратегия превращается в чистую.

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

Пара оптимальных стратегий
образующих решение игры, обладает следующим свойством:если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно, отступать от своей. Эта пара стратегий образует в игре некое положение равновесия: один игрок хочет обратить выигрыш в максимум, другой - в минимум, каждый тянет в свою сторону и, при разумном поведении обоих, устанавливается равновесие и устойчивый выигрыш v. Если v > 0, то игра выгодна для нас, если v < 0 - для противника; при v = 0 игра «справедливая», одинаково выгодная для обоих участников.

Рассмотрим пример игры без седловой точки и приведем (без доказательства) ее решение. Игра состоит в следующем: два игрока А и В одновременно и не сговариваясь показывают один, два или три пальца. Выигрыш решает общее количество пальцев: если оно четное, выигрывает А и получает у В сумму, равную этому числу; если нечетное, то, наоборот, А платит В сумму, равную этому числу. Как поступать игрокам?

Составим матрицу игры. В одной партии у каждого игрока три стратегии: показать один, два или три пальца. Матрица 3×3 дана в таблице 26.5; в дополнительном правом столбце приведены минимумы строк, а в дополнительной нижней строке - максимумы столбцов.

Нижняя цена игры α = - 3 и соответствует стратегии A 1 . Это значит, что при разумном, осторожном поведении мы гарантируем, что не проиграем больше, чем 3. Слабое утешение, но все же лучше, чем, скажем, выигрыш - 5, встречающийся в некоторых клетках матрицы. Плохо нам, игроку А... Но утешимся:

положение противника, кажется, еще хуже: нижняя цена игры β = 4, т. е. при разумном поведении он отдаст нам минимум 4. В общем, положение не слишком хорошее - ни для той, ни для другой стороны. Но посмотрим: нельзя ли его улучшить? Оказывается, можно. Если каждая сторона будет применять не одну какую-то чистую стратегию, а смешанную, в которую

Таблица 26.5

B j A i	B 1	B 2	B 3
A 1 A 2 A 3
β j

первая и третья входят с вероятностями 1/4, а вторая - с вероятностью 1/2, т. е.

то средний выигрыш будет устойчиво равен нулю (значит, игра «справедлива» и одинаково выгодна той и другой стороне). Стратегии
образуют решение игры, а ее ценаv = 0. Как мы это решение нашли? Это вопрос другой. В следующем параграфе мы покажем, как вообще решаются конечные игры.

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Назначение сервиса . С помощью сервиса в онлайн режиме можно:

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

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

Игра – это математическая модель реальной конфликтной ситуации. Конфликтная ситуация двух игроков называется парной игрой. Парную игру с нулевой суммой удобно исследовать, если она описана в виде матрицы. Такая игра называется матричной ; матрица, составленная из чисел a ij , называется платежной . В таблице представлены варианты решения игры, заданной платежной матрицей А.

Описание алгоритма:

1. На основании анализа платёжной матрицы следует определить, существуют ли в ней доминируемые стратегии, и исключить их.
2. Найти верхнюю и нижнюю цены игры и определить, имеет ли данная игра седловую точку (нижняя цена игры должна быть равна верхней цене игры).
3. Если седловая точка существует, то оптимальными стратегиями игроков, являющимися решением игры, будут их чистые стратегии, соответствующие седловой точке. Цена игры равна верхней и нижней цены игры, которые равны между собой.
4. Если игра не имеет седловой точки, то решение игры следует искать в смешанных стратегиях. Для определения оптимальных смешанных стратегий в играх m × n следует использовать симплекс-метод, предварительно переформулировав игровую задачу в задачу линейного программирования.

Представим алгоритм решения матричной игры графически.

Рисунок - Схема решения матричной игры.

Методы решения матричной игры в смешанных стратегиях

Итак, если седловая точка отсутствует, решение игры проводят в смешанных стратегиях и решают следующими методами:

1. Решение игры через систему уравнений.
   Если задана квадратная матрица nxn (n=m), то вектор вероятностей можно найти, решив систему уравнений. Этот метод используется не всегда и применим только в отдельных случаях (если матрица 2x2 , то решение игры получается практически всегда). Если в решении получаются отрицательные вероятности, то данную систему решают симплекс-методом.
2. Решение игры графическим методом.
   В случаях, когда n=2 или m=2 , матричную игру можно решить графически .
3. Решение матричной игры симплекс-методом.
   В этом случае матричная игра сводится к

Рассмотрим конечную парную игру с нулевой суммой. Обозначим через a выигрыш игрока A , а через b – выигрыш игрока B . Так как a = –b , то при анализе такой игры нет необходимости рассматривать оба этих числа – достаточно рассматривать выигрыш одного из игроков. Пусть это будет, например, A . В дальнейшем для удобства изложения сторону A будем условно именовать "мы ", а сторону B – "противник ".

Пусть у нас имеется m возможных стратегийA 1 , A 2 , …, A m , а у противника n возможных стратегий B 1 , B 2 , …, B n (такая игра называется игрой m×n ). Предположим, что каждая сторона выбрала определенную стратегию: мы выбрали A i , противник B j . Если игра состоит только из личных ходов, то выбор стратегий A i и B j однозначно определяет исход игры – наш выигрыш (положительный или отрицательный). Обозначим этот выигрыш через a ij (выигрыш при выборе нами стратегии A i , а противником – стратегии B j ).

Если игра содержит кроме личных случайные ходы, то выигрыш при паре стратегий A i , B j есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша . Для удобства будем обозначать через a ij как сам выигрыш (в игре без случайных ходов), так и его математическое ожидание (в игре со случайными ходами).

Предположим, что нам известны значения a ij при каждой паре стратегий. Эти значения можно записать в виде матрицы, строки которой соответствуют нашим стратегиями (A i ), а столбцы – стратегиям противника (B j ):

B j A i	B 1	B 2	…	B n
A 1	a 11	a 12	…	a 1n
A 2	a 21	a 22	…	a 2n
…	…	…	…	…
A m	a m 1	a m 2	…	a mn

Такая матрица называется платежной матрицей игры или просто матрицей игры .

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

Рассмотрим пример 1 антагонистической игры 4×5. В нашем распоряжении есть четыре стратегии, у противника – пять стратегий. Матрица игры следующая:

B j A i	B 1	B 2	B 3	B 4	B 5
A 1
A 2
A 3
A 4

Какой стратегией нам (т.е. игроку A ) воспользоваться? Какую бы мы ни выбрали стратегию, разумный противник ответит на нее той стратегией, для которой наш выигрыш будет минимальным. Например, если мы выберем стратегию A 3 (соблазнившись выигрышем 10), противник в ответ выберет стратегию B 1 , и наш выигрыш будет всего лишь 1. Очевидно, исходя из принципа осторожности (а он – основной принцип теории игр), надо выбирать ту стратегию, при которой наш минимальный выигрыш максимален .

Обозначим через α i минимальное значение выигрыша для стратегии A i :

и добавим к матрице игры столбец, содержащий эти значения:

B j A i	B 1	B 2	B 3	B 4	B 5	минимум в строках α i
A 1
A 2
A 3
A 4							максимин

Выбирая стратегию, мы должны предпочесть ту, для которой значение α i максимально. Обозначим это максимальное значение через α :

Величина α называется нижней ценой игры или максимином (максимум минимального выигрыша). Стратегия игрока A , соответствующая максимину α , называется максиминной стратегией .

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

Теперь проведем аналогичные рассуждения за противника B B A B 2 – мы ему ответим A .

Обозначим через β j A B ) для стратегии A i :

β j β :

7.ЧТО НАЗЫВАЕТСЯ ВЕРХНЕЙ ЦЕННОЙ ИГРЫТеперь проведем аналогичные рассуждения за противника B . Он заинтересован в том, чтобы обратить наш выигрыш в минимум, то есть отдать нам поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Например, если он выберет стратегию B 1 , то мы ответим ему стратегией A 3 , и он отдаст нам 10. Если выберет B 2 – мы ему ответим A 2 , и он отдаст 8 и т. д. Очевидно, осторожный противник должен выбрать ту стратегию, при которой наш максимальный выигрыш будет минимален .

Обозначим через β j максимальные значения в столбцах платежной матрицы (максимальный выигрыш игрока A , или, что то же самое, максимальный проигрыш игрока B ) для стратегии A i :

и добавим к матрице игры строку, содержащую эти значения:

Выбирая стратегию, противник предпочтет ту, для которой значение β j минимально. Обозначим его через β :

Величина β называется верхней ценой игры или минимаксом (минимум максимального выигрыша). Соответствующая минимаксу стратегия противника (игрока B ), называется минимаксной стратегией .

Минимакс – это значение выигрыша, больше которого заведомо не отдаст нам разумный противник (иначе говоря, разумный противник проиграет не больше, чем β ). В данном примере минимакс β равен 5 (соответствующая клетка в таблице выделена серым цветом) и достигается он при стратегии противника B 3 .

Итак, исходя из принципа осторожности («всегда рассчитывай на худшее!»), мы должны выбрать стратегию A 4 , а противник – стратегию B 3 . Принцип осторожности является в теории игр основным и называется принципом минимакса .

Рассмотрим пример 2 . Пусть игроки A и В одновременно и независимо друг от друга записывают одно из трех чисел: либо «1», либо «2», либо «3». Если сумма записанных чисел оказывается четной, то игрок B платит игроку A эту сумму. Если сумма нечетная, то эту сумму выплачивает игрок A игроку В .

Запишем платежную матрицу игры, и найдем нижнюю и верхнюю цены игры (номер стратегии соответствует записанному числу):

Игрок A должен придерживаться максиминной стратегии A 1 , чтобы выиграть не меньше –3 (то есть чтобы проиграть не больше 3). Минимаксная стратегия игрока B – любая из стратегий B 1 и B 2 , гарантирующая, что он отдаст не более 4.

Тот же самый результат мы получим, если будем записывать платежную матрицу с точки зрения игрока В . Фактически, эта матрица получается путем транспонирования матрицы, построенной с точки зрения игрока A , и изменения знаков элементов на противоположный (так как выигрыш игрока A – это проигрыш игрока В ):

Исходя из этой матрицы следует, что игрок B должен придерживаться любой из стратегий B 1 и B 2 (и тогда он проиграет не более 4), а игрок A – стратегии A 1 (и тогда он проиграет не более 3). Как видно, результат в точности совпадает с полученным выше, поэтому при анализе не важно, с точки зрения какого игрока мы его проводим.

8 ЧТО НАЗЫВАЕТСЯ ЦЕННОВОЙ ИГРОЙ.

9.В ЧЕМ СОСТОЙТ ПРИНЦЕП МИНИМАКСА.2. Нижняя и верхняя цена игры. Принцип минимакса

Рассмотрим матричную игру типа с платежной матрицей

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

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