Московский Энергетический Институт

(Технический Университет)

Отчёт по лабораторной работе

по теории игр

«Программа поиска оптимальных стратегий для парной антагонистической игры, заданной в матричной форме»

Выполнили студенты

группы А5-01

Ашрапов Далер

Ашрапова Ольга

Основные понятия теории игр

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

Если цели сторон прямо противоположны, то говорят об антагонистическом конфликте .

Игрой называется упрощённая формализованная модель конфликтной ситуации.

Однократный розыгрыш игры от начала до конца называется партией . Результатом партии являетсяплатёж (иливыигрыш ).

Партия состоит из ходов , т.е. выборов игроков из некоторого множества возможных альтернатив.

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

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

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

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

Задача теории игр – нахождение оптимальных стратегий игроков, т.е. стратегий, обеспечивающих им максимальный выигрыш или минимальный проигрыш.

Классификация теоретико-игровых моделей

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

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

Дискретные (множества стратегийдискретны)

Конечные

Бесконечные

Непрерывные (множества стратегий непрерывны)

Бесконечные

n лиц (
)

Коалиционные (кооперативные)

Некоалиционные (некооперативные)

2-х лиц (парные)

Антагонистические (игры с нулевой суммой)

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

Неантагонистические

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

С неполной информацией

С нулевой суммой (суммарный платёж равен нулю)

С ненулевой суммой

Одноходовые (лотереи)

Многоходовые

Матричное представление парной антагонистической игры

В данном пособии будем рассматривать антагонистические игры двух лиц , заданные в матричной форме. Это означает, что нам известно множество стратегий первого игрока (игрокA ){ A i }, i = 1,…, m и множество стратегий второго игрока (игрокB ){ B j }, j = 1,..., n , а также задана матрицаA = || a ij || выигрышей первого игрока. Поскольку речь идёт об антагонистической игре, то предполагается, что выигрыш первого игрока равен проигрышу второго. Считаем, что элемент матрицыa ij – выигрыш первого игрока при выборе им стратегииA i и ответе ему второго игрока стратегиейB j . Такую игру будем обозначать как
, гдеm - количество стратегий игрокаА, n - количество стратегий игрокаВ. В общем виде она может быть представлена следующей таблицей:

Пример 1

В качестве простейшего примера рассмотрим игру, партия которой состоит из двух ходов.

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

2-й ход : ИгрокВ выбирает одно из чисел (3 или 4).

Итог : Выборы игроковА иВ складываются. Если сумма чётная, тоВ выплачивает её значение игрокуА , если же нечётная - наоборот,А выплачивает сумму игрокуВ .

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

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

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

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

– нижняя оценка цены игры и

– верхняя оценка цены игры.

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

Можно доказать, что α ≤ V ≤ β , гдеV –цена игры , т.е., вероятный выигрыш первого игрока.

Если выполняется соотношение α = β = V , то говорят, чтоигра имеет седловую точку
, ирешается в чистых стратегиях . Иными словами, имеется пара стратегий
, дающих игрокуА V .

Пример 2

Вернёмся к игре, рассмотренной нами в примере 1 и проверим её на наличие седловой точки.

Для данной игры
= -5,
= 4,
, следовательно, она не имеет седловой точки.

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

Пример 3

Внесём в правила игры из примера 1 некоторые изменения. Предоставим игроку В информацию о выборе игрокаА. Тогда уВ появятся две дополнительные стратегии:

- стратегия, выгодная дляА. Если выборА - 1, то В выбирает 3, если выборА - 2, то В выбирает 4;

- стратегия, не выгодная дляА. Если выборА - 1, то В выбирает 4, если выборА - 2, то В выбирает 3.

Эта игра - с полной информацией.

В данном случае
= -5,
= -5,
, следовательно, игра имеет седловую точку
. Данной седловой точке соответствуют две пары оптимальных стратегий:
и
. Цена игрыV = -5. Очевидно, что дляА такая игра невыгодна.

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

Теорема 1

Всякая парная антагонистическая игра с полной информацией решается в чистых стратегиях.

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

Вслучае же отсутствия седловой точки, в качестве решения используются т.н.смешанные стратегии :, гдеp i и q j – вероятности выбора стратегийA i и B j первым и вторым игроками соответственно. Решением игры в данном случае является пара смешанных стратегий
, максимизирующих математическое ожидание цены игры.

Обобщением теоремы 1 на случай игры с неполной информацией служит следующая теорема:

Теорема 2

Любая парная антагонистическая игра имеет хотя бы одно оптимальное решение, т.е., пару в общем случае смешанных стратегий
, дающих игрокуА устойчивый выигрыш, равный цене игрыV , причёмα ≤ V ≤ β .

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

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

Такая игра представляется как игра двух игроков, в которой игрок 1 выбирает число х из множества X, игрок 2 выбирает число у из множества 7, и после этого игроки 1 и 2 получают соответственно выигрыши U (х, у) и -U(x, у). Выбор определенного числа игроком означает применение его чистой стратегии, соответствующей этому числу.

По аналогии с матричными играми чистой нижней ценой игры можно назвать v { = max min U(x, у), а чистой верхней ценой игры -v 2 =

min max U{x, у). Тогда по аналогии можно считать, что если для какой-

у *

либо бесконечной антагонистической игры величины V и v 2 существуют и равны между собой («i =v 2 =v), то такая игра имеет решение в чистых стратегиях, т.е. оптимальной стратегией игрока 1 является выбор числа х° е X, а игрока 2 - числа у 0 е 7, при которых Щх { у 0) -v.

В этом случае v называется чистой ценой игры, а (х°, у 0) - седловой точкой бесконечной антагонистической игры.

Для матричных игр величины v x и v 2 всегда существуют, но в бесконечных антагонистических играх они могут и не существовать, т.е. бесконечная антагонистическая игра не всегда разрешима.

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

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

Для примера допустим, что игрок 1 выбирает число х из множества Х= , игрок 2 выбирает число у из множества Y= . После этого игрок 2 платит игроку 1 сумму Щх, у) -2х 2 -у 2 . Поскольку игрок 2 стремится минимизировать платеж игрока 1, то он определяет min (2х 2 - у 2) = 2х 2 - 1, т.е. при этому= 1. Игрок 1 стремится мак- тег

симизировать свой платеж, поэтому определяет maxi min Щх, у)1 =

xGX у ег

- max (2х 2 - 1) = 2- 1 = 1, который достигается при х = 1.

Таким образом, нижняя чистая цена игры v x - 1. Верхняя чистая

цена игры v 2 = min - min (2 - у 2) = 2 - 1 = 1, т.е. в этой

>ег хех у еу

игре v l =v 2 =l. Поэтому чистая цена игры v = 1, а седловая точка (х° = 1; у°=1).

Предположим теперь, что Хи Y- открытые интервалы, т.е. игрок 1 выбираетxeA"=(0; 1), игрок 2 выбирает уе 7= (0; 1). В этом случае, выбирая х, достаточно близкое к 1, игрок 1 будет уверен, что он получит выигрыш не меньше, чем число, близкое к»=1; выбирая у, близкое к 1, игрок 2 не допустит, чтобы выигрыш игрока 1 значительно превышал чистую цену игры v= 1.

Степень близости к цене игры может характеризоваться числом?>0. Поэтому в описываемой игре можно говорить об оптимальности чистых стратегий х° = 1, у 0 = 1 соответственно игроков 1 и 2 с точностью до произвольного числа?>0. Точка (х„ , у Е), где х е е X, у (. eY, в бесконечной антагонистической игре называется точкой z-равновесия (с.-седловой точкой) , если для любых стратегий хеТигрока 1,уе Тигро- ка 2 имеет место неравенство Щх, у.) - ? Щ x r , у (.) U(x t ., у) + ?. В этом случае стратегии х к. и у. называются с,-оптимальными стратегиями . Эти стратегии являются оптимальными с точностью до? в том смысле, что если отклонение от оптимальной стратегии никакой пользы игроку принести не может, то его отклонение от с-оптимальной стратегии может увеличить его выигрыш не более чем на е.

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

Пусть F(x) - функция распределения вероятностей применения чистых стратегий игроком 1. Если число Е, - чистая стратегия игрока 1, то F(x) = P(q где P(q - Х) - вероятность того, что случайно выбранная чистая стратегия Е, не будет превосходить х. Аналогично рассматривается функция распределения вероятностей применения чистых стратегий г| игроком 2: Q(y) = Р(г .

Функции F(x) и Q(y) называются смешанными стратегиями соответственно игроков 1 и 2. Если Fx) и Q(y) дифференцируемы, то существуют их производные, обозначаемые соответственно через f{x) и q(y) (функции плотности распределения).

В общем случае дифференциал функции распределения dF{x ) выражает вероятность того, что стратегия с, находится в промежутке х Е, Аналогично для игрока 2: dQ(y) означает вероятность того, что его стратегия р находится в интервале у г| у+dy. Тогда платеж игрока 1 составит Щх, у) dF(x), а платеж игрока 2 равен Щх, у) dQ(y).

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

Средний платеж игрока 1 при условии, что оба игрока применяют свои смешанные стратегии F{x) и Q(y), будет равен

По аналогии с матричными играми определяются оптимальные смешанные стратегии игроков и цена игры: если пара смешанных стратегий F*(x ) и Q*(y) соответственно для игроков 1 и 2 являются оптимальными, то для любых смешанных стратегий F(x) и Q(y) справедливы соотношения:

Если игрок 1 отступает от своей стратегии F*(x), то его средний выигрыш не может увеличиться, но может уменьшиться из-за рациональных действий игрока 2. Если игрок 2 отступит от своей смешанной стратегии Q*(y), то средний выигрыш игрока 1 может увеличиться, но не уменьшиться, за счет более разумных действий игрока 1. Средний выигрыш E(F*, Q*), получаемый игроком 1 при применении игроками оптимальных смешанных стратегий, соответствует цене игры.

Тогда нижняя цена бесконечной антагонистической игры, решаемой в смешанных стратегиях, может быть определена как v x = шах

min Е (FQ), а верхняя цена игры как v 2 = min max Е(F, Q).

Q Q f

Если существуют такие смешанные стратегии F* (х) и Q* (у) соответственно для игроков 1 и 2, при которых нижняя и верхняя цены игры совпадают, то F*(x) и Q*(y) естественно назвать оптимальными смешанными стратегиями соответствующих игроков, a v=v x = v 2 - ценой игры.

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

Рассмотрим решение игр с выпуклой платежной функцией. Решение игр с вогнутой функцией выигрыша симметрично.

Выпуклой функцией/переменной х на интервале (а ; Ь) называется такая функция, для которой выполняется неравенство

где Хх и х 2 - любые две точки из интервала (а; b );

Х.1, А.2 > 0, причем +Х.2= 1.

Если для / ч * 0 Д 2 * 0, всегда имеет место строгое неравенство

то функция/называется строго выпуклой на (а; Ь).

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

Для вогнутых функций свойства противоположны, для них должно выполняться неравенство/(/4X1 +А.2Х2) > Kf (xi) +)-if (х 2) (> при строгой вогнутости), а вторая производная/"(х)

Доказано , что непрерывная и строго выпуклая функция на замкнутом интервале принимает минимальное значение только в одной точке интервала. Если Щх, у) - непрерывная функция выигрышей игрока 1 на единичном квадрате и строго выпуклая по у для любого х, то имеется единственная оптимальная чистая стратегия у=у° е для игрока 2, цена игры определяется по формуле

а значение у 0 определяется как решение следующего уравнения:

Если функция Щх, у) не строго выпуклая по у, то у игрока 2 оптимальная чистая стратегия не будет единственной.

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

Цена игры определяется по формуле

а чистая оптимальная стратегия х 0 игрока 1 определяется из уравнения

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

1. Проверить функцию Щх, у) на выпуклость по у (вторая частная производная должна быть больше либо равна 0).

2. Определить у 0 из соотношения v- min max Щх, у) как значение

у, на котором достигается минимакс.

3. Найти решение уравнения v = U(x, у 0) и составить пары его решений Х и х 2 , для которых

4. Найти параметр а из уравнения

Параметр а определяет оптимальную стратегию игрока 1 и имеет смысл вероятности выбора им его чистой стратегии х х. Величина 1 - а имеет смысл вероятности выбора игроком 1 его чистой стратегии х 2 .

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

1. Эта функция непрерывна по х и у, и поэтому эта игра имеет решение. Функция Щх, у) строго выпукла по у, так как

Следовательно, игрок 2 имеет единственную чистую оптимальную стратегию у 0 .

2. Имеем v = min max (х - у) 2 . Для определения max (х 2 - 2ху Ч-у 2)

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

Таким образом, функция U имеет минимум для любого у при х=у. Это значит, что при ху - возрастает, а ее максимум должен достигаться в одной из крайних точек х=0 или х= 1. Определим значения функции U в этих точках:

Тогда шах (х - у) 2 = тах {у 2 ; 1 - 2у+у 2 }. Сравнивая «внутренние»

максимумы, стоящие в фигурных скобках, легко заметить, что у 2 > 1 - - 2у+у 2 , если у > */ 2 и у 2 1 - 2у+у 2 , если у "/ 2 . Более наглядно это представляется графиком (рис. 2.5).

Рис. 2.5. Внутренние максимумы платежной функции U(х, у) = (х- у ) 2

Поэтому выражение (х - у) 2 достигает своего максимума при х=0, если у > 7 2 , и при х= 1, если у У 2:

Следовательно, v= min { min у 2 ; min (1 - у) 2 }. Каждый из вну-

тренних минимумов достигается при у= */ 2 и принимает значение У 4 . Таким образом, цена игры г = У 4 , а оптимальная стратегия игрока 2:

3. Определим оптимальную стратегию игрока 1 из уравнения U(x, у 0)=v, т.е. для данной игры (х - У 2) 2 =У 4 . Решением этого уравнения ЯВЛЯЮТСЯ Х| =0, х 2 = 1.

Для них выполняются условия

4. Определим параметр а, т.е. вероятность применения игроком 1 его чистой стратегии Х] = 0. Составим уравнение а-1 + (1 - а) (-1)=0, откуда а = У 2 . Таким образом, оптимальная стратегия игрока 1 состоит в выборе им своих чистых стратегий 0 и 1 с вероятностью 1 / 2 каждая. Задача решена.

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

В теоретико-игровой терминологии 1-я управляющая подсистема называется игроком 1 , 2-я управляющая подсистема - игроком 2 , множества

их альтернативных действий называются множествами стратегий этих игроков. Пусть Х - множество стратегий игрока 1, Y - множество стратегий

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

x ∈X и y ∈Y . Пусть F (x ,y )- оценка полезности для игрока 1 того состояния

системы, в которое она переходит при выборе игроком 1 стратегии х и

игроком 2 стратегии у . Число F (x ,y ) называется выигрышем игрока 1 в ситуации (x ,y ), а функция F - функцией выигрыша игрока 1 . Выигрыш игрока

1 одновременно является проигрышем игрока 2 , то есть величиной, которую первый игрок стремится увеличить, а второй – уменьшить. Это и есть

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

Антагонистическую игру естественно задать системой Г= (Х, Y, F ).

Заметим, что формально антагонистическая игра задается фактически так же, как и задача принятия решения в условиях неопределенности - если

отождествить управляющую подсистему 2 со средой. Содержательное различие между управляющей подсистемой и средой состоит в том, что

поведение первой носит целенаправленный характер. Если при составлении математической модели реального конфликта у нас есть основание (или намерение) рассматривать среду как противника, цель которого - принести

нам максимальный вред, то такую ситуацию можно представить в виде антагонистической игры. Другими словами, антагонистическую игру можно трактовать как крайний случай ЗПР в условиях неопределенности,

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

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

Определение. Если Х и Y конечны, то антагонистическая игра называется матричной. В матричной игре можно считать, что X ={1,…,n },

Y ={1,…,m } и положить aij=F (i,j ). Таким образом, матричная игра полностью определяется матрицей A= (aij ), i =1,…,n, j =1,…,m .

Пример 3.1. Игра с двумя пальцами.

Два человека одновременно показывают один или два пальца и называют число 1 или 2, означающее, по мнению говорящего, количество

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

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

Это антагонистическая матричная игра. Каждый игрок имеет четыре стратегии: 1- показать 1 палец и назвать 1, 2- показать 1 палец и назвать 2, 3-

показать 2 пальца и назвать 1, 4 - показать 2 пальца и назвать 2. Тогда матрица выигрышей A=(aij), i= 1,…, 4, j= 1,…, 4 определяется следующим образом:

a12= 2, a21 = – 2, a13=a42= –3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 в остальных случаях.

Пример 3.2. Дискретная игра типа дуэли.

Задачами дуэльного типа описывается, например, борьба двух игроков,

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

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

Таким образом, Игрок 1 выбирает i

Игрок 2 точно также стремится обеспечить себе наивысшую величину выигрыша (или, что эквивалентно, наименьшую величину проигрыша) вне зависимости от выбранной стратегии противника. Его оптимальной стратегией будет столбец Н 0 с наименьшим максимальным платежом. Таким образом, Игрок 2 выберет j -ю стратегию, которая является решением задачи

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

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

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

Элемент матрицы h ij матрицы выигрышей, соответствующей стратегиям, называется седловой точкой матрицы Н .

В случае, если цена антагонистической игры равна 0, игра называется справедливой .

Рассмотрим игру, в которой Игрок 1 располагает двумя стратегиями, а Игрок 2 – тремя. Матрица выигрышей Игрока 1 имеет вид:

Замечание . Поскольку мы рассматриваем пример антагонистической игры, то матрица выигрышей Игрока 2 будет Н 2 =-Н 1 .

Игрок 1 рассчитывает, что если он выберет первую стратегию (т.е. первую строку матрицы Н 1 ), то противник выберет свою вторую стратегию (т.е. второй столбец) так, что выигрыш будет равен 1 . Если же он выбирает вторую стратегию, то противник может выбрать первую стратегию, так что выигрыш будет равен -1.

Проанализировав полученные значения: Игрок 1 останавливается на своей первой стратегии, которая обеспечивает ему максимальный гарантированный выигрыш, равный 1.

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

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

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

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

Однако не все матричные антагонистические игры являются вполне определенными.

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

Рассмотрим пример такой игры:

Для этой игры .

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

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

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

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

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

или матричных обозначениях

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

.

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

.

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

Как и для вполне определенных игр, стратегия Игрока 1 называется Максиминной стратегией , стратегия Игрока 2 - минимаксной стратегией, значение - ценой игры; в случае, когда игра называется справедливой.

Очевидным следствием из Теоремы о минимаксе является соотношение:

.

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

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

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

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

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

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

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

Пример. Рассмотрим игру со следующей матрицей:

Исключение второй строки приводит к матрице: третий столбец в этой урезанной матрице доминирует второй, и исключение второго столбца дает: .

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

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

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

Кроме того может быть использован графический способ для решения игры (и вообще игр или ).

Например, матрица выигрышей имеет вид: .

Пусть Игрок 1 выбирает свою первую стратегию с вероятностью , а вторую с вероятностью . Если Игрок 2 выбирает свою первую стратегию, то (из первого столбца матрицы) математическое ожидание для Игрока 1 будет равно . Если Игрок 2 выбирает свою вторую стратегию, то в соответствии со вторым столбцом матрицы: .

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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