Теория игр

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

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

 

 Кооперативная теория игр

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

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

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

Одним из простейших примеров бескоалиционной игры может служить  «морра» в следующем своём варианте. Три игрока показывают одновременно 1 или 2 пальца каждый. Если все три игрока показывают одно и то же число, то выигрыш каждого равен нулю. В противном случае один из игроков показывает a (= 1 или 2) и получает b из некоторого источника (например, из банка, образованного предварительными взносами), а два других игрока, показывающие одно и то же b ¹( a), не получают ничего.

3.   Антагонистические и позиционные игры

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

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

Матричные игры - игры, в которых участвуют два игрока (I и II) с противоположными интересами, причём каждый игрок имеет конечное число чистых стратегий. Если игрок I имеет m стратегий, а игрок II — n стратегий, то игра может быть задана (m ´ n)-maтрицей А = ||a_ij||, где a_ij есть выигрыш игрока I, если он выберет стратегию i (i = -1,..., m), а игрок II — стратегию j (j = 1,..., n).

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

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

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

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

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

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

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

 

ПРАКТИЧЕСКАЯ  ЧАСТЬ

ЗАДАЧА №1.

Найти решение  игры, предварительно упростив её.

 

 

_{Вторая  стратегия явно невыгодна  для игрока А, по сравнению с первой.}

 

  и  .

Обозначив, , i = 1,2,3 и , j = 1,2,3,4,5 составим две взаимно-двойственные задачи линейного программирования.

                   

             

Решаем  симплексным методом задачу 2. Введем добавочные переменные и перейдём к  уравнениям.

I шаг.  Основные переменные –

Неосновные переменные –

Базисное  решение  допустимое. Переводим в основные переменные , а в неосновные.

II шаг.  Основные переменные –

Неосновные переменные –

Базисное  решение  допустимое. Переводим в основные переменные , а в неосновные.

III шаг.  Основные переменные –

Неосновные переменные –

Базисное  решение  является оптимальным, так как отсутствуют положительные коэффициенты при неосновных переменных и .

 

Делаем  переход:

Оптимальное базисное решение задачи 1: , причём , а .

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

                 

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

                  

Здесь учтено, что третий столбец исходной матрицы  отброшен.

 

ЗАДАЧА №2.

Дать  геометрическую интерпретацию игры:

_{Перейдём  к новой матрице  добавив +2.}

 

 

                                  _y

                                   I                                       II

 

                                                                                         

                                           

 _N

                                                                   

                                                 v                              

                                                                                 

 

x

 

Нижняя  цена игры – 

Верхняя цена игры – 

 

Точка N точка пересечения прямых и

Составим  уравнение прямой , проходящей через точки (0;3) и (1;5)

 

Составим  уравнение прямой , проходящей через точки (0;4) и (1;1)

 

Решаем  систему уравнений:

 

Откуда  получаем, что x=0,2; y=3,4; то есть т.N(0,2;3,4)

Мы получили, что оптимальная стратегия игрока А равна:

  

 

Теперь  будем искать оптимальную стратегию  игрока

 

 

 

 

 

 

 

                                  _y

                                   I                                       II

 

                                                                             

                                             

       _M

                                                                   

                                                          v                      

                                                                                 

 

x

Точка M точка пересечения прямых и

Составим  уравнение прямой , проходящей через точки (0;3) и (1;4)