Теория игр

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

66

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

КУРСОВАЯ РАБОТА

"ТЕОРИЯ ИГР"

Введение

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

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

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

1. Изучить теоретические аспекты и выявить природу «Теории игр»;

2. Сказать об актуальности проблемы «Теория игр» в современных условиях;

3. Изложить возможности решения тематики «Теория игр»;

4. Обозначить тенденции развития тематики «Теория игр».

Краткое содержание:

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

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

В 4-ой главе будут рассмотрены вопросы «Кооперативных игр» и раскрыты все моменты данной темы

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

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

1. Классификация игр

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

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

Решение матричных игр в чистых стратегиях

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

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

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

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

А =

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

а ( = )

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

а = = (1).

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

а

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

= = (2).

Определение. Число , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1. Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше , а игрок 2 за счёт применения своих чистых стратегий может не допустить выигрыш игрока 1 больше, чем . Определение. Если в игре с матрицей А =, то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры

= =.

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

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

Пример 1

Седловой точкой является пара (_о = 3; _о = 1), при которой == = 2. Заметим, что хотя выигрыш в ситуации (3; 3) также равен 2 ==, она не является седловой точкой, т. к. этот выигрыш не является максимальным среди выигрышей третьего столбца.

Пример 2

Из анализа матрицы выигрышей видно, что , т.е. данная матрица не имеет седловой точки. Если игрок 1 выбирает свою чистую максиминную стратегию = 2, то игрок 2, выбрав свою минимаксную = 2, проиграет только 20. В этом случае игроку 1 выгодно выбрать стратегию = 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30. Тогда игроку 2 будет выгодно выбрать стратегию = 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а игрок 2 ответит выбором 2-й стратегии и т.д.

1.2 Смешанное расширение матричной игры

Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивается исследование игры. Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных игр следует искать в использовании секретности применения чистых стратегий и возможности многократного повторения игр в виде партии. Этот результат достигается путём применения чистых стратегий случайно, с определённой вероятностью. Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий. Таким образом, если игрок 1 имеет чистых стратегий 1,2,…, , то его смешанная стратегия x это набор чисел x = (x₁,…, x_m) удовлетворяющих соотношениям

x_i 0 (i = 1, ), = 1.

Аналогично для игрока 2, который имеет чистых стратегий, смешанная стратегия это набор чисел

= (₁,…, ), 0, ( = 1, ), = 1.

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

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

E (A, x, y) == x A y^T

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

Е (А, х, ).

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть

Е (А, х, ).

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

Е (А, х, ) = Е (А, х, ) = Е (А, х^о, у^о).

Величина Е (А, х^о,у^о) называется при этом ценой игры и обозначается через .

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

Е (А, х, у^о) Е (А, х^о, у^о) Е (А, х^о, у)

Оптимальные смешанные стратегии и цена игры называются решением матричной игры. Основная теорема матричных игр имеет вид:

Теорема (о минимаксе). Для матричной игры с любой матрицей А величины

Е (А, х, ) и Е (А, х, )

существуют и равны между собой.

Свойства решений матричных игр.

Обозначим через (Х, , А) игру двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию х Х, игрок 2 , после чего игрок 1 получает выигрыш А = А (х, ) за счёт игрока 2.

Определение. Стратегия х¹ игрока 1 доминирует (строго доминирует) над стратегией х², если

А (х¹, ) А (х², ) (А (х¹, ) А (х², )), .

Стратегия ¹ игрока 2 доминирует (строго доминирует) над стратегией ², если

А (х, ¹) А (х, ²) (А (х, ¹) А (х, ²)), х Х.

При этом стратегии х² и ² называются доминируемыми (строго доминируемыми). Спектром смешанной стратегии игрока в конечной антагонистической игре называется множество всех его чистых стратегий, вероятность которых согласно этой стратегии положительна. Свойство 1. Если чистая стратегия одного из игроков содержится в спектре некоторой его оптимальной стратегии, то выигрыш этого игрока в ситуации, образованной данной чистой стратегией и любой оптимальной стратегией другого игрока, равен значению конечной антагонистической игры. Свойство 2. Ни одна строго доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии. Игра = (Х, , А) называется подыгрой игры (Х, , А), если Х Х, , а матрица А является подматрицей матрицы А. Матрица А при этом строится следующим образом. В матрице А остаются строки и столбцы, соответствующие стратегиям Х и , а остальные «вычеркиваются». Всё то что «останется» после этого в матрице А и будет матрицей А. Свойство 3. Пусть = (Х, , А) конечная антагонистическая игра, = (Х х, , А) подыгра игры , а х чистая стратегия игрока 1 в игре , доминируемая некоторой стратегией , спектр которой не содержит х. Тогда всякое решение (х^о, ^о, ) игры является решением игры . Свойство 4. Пусть = (Х, , А) конечная антагонистическая игра, = (Х, , А) подыгра игры , а чистая стратегия игрока 2 в игре , доминируемая некоторой стратегией , спектр которой не содержит .Тогда всякое решение игры является решением . Свойство 5. Если для чистой стратегии х игрока 1 выполнены условия свойства 3, а для чистой стратегии игрока 2 выполнены условия свойства 4, то всякое решение игры = (Х х, , А) является решением игры = (Х, , А). Свойство 6. Тройка (х^о, ^о, ) является решением игры = (Х, , А) тогда и только тогда, когда (х^о, ^о, к +а) является решением игры (Х, , кА+а), где а любое вещественное число, к 0. Свойство 7. Для того, чтобы х^о = () была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры , необходимо и достаточно выполнение следующих неравенств

(j = )

Аналогично для игрока 2: чтобы ^о = (,…,,…,) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:

(i = )

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

,

получим решение матричной игры. Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (*) (**) и линейных уравнений (***). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например для матрицы 33 имеем систему из 6 неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства

= .

Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок 1 чистую максиминная, а игрок 2 чистую минимаксная). В противном случае хотя бы у одного игрока оптимальные стратегии будут смешанные. Для матричных игр небольшого размера эти решения можно найти, применяя свойства 1 5. Замечание. Отметим, что исключение доминируемых (не строго) стратегий может привести к потере некоторых решений. Если же исключаются только строго доминируемые стратегии, то множество решений игры не изменится.

Пример 3. Пусть = (Х, , А), где Х = 1, 2, 3, 4; = 1, 2, 3, 4, а функция выигрыша А задана следующим образом:

где С 0.

Решение. Прежде всего заметим, что по свойству 6 достаточно решить игру ¹ = (Х, , А), где А¹ =А. В матричной форме игра ¹ определяется матрицей выигрышей

Элементы четвёртой строки этой матрицы «» соответствующих элементов третьей строки и поэтому третья стратегия игрока 1 доминирует над четвёртой. Кроме того, элементы первого столбца матрицы А¹ «» соответствующих элементов второго столбца, Следовательно, вторая стратегия игрока 2 доминирует над его первой стратегией. Далее, из свойства 5 следует, что всякое решение игры ² = (Х 4, 1, А¹) является решением игры ¹. В матричной форме игру ² можно представить матрицей

.

Очевидно, что элементы второй строки «» полусуммы соответствующих элементов первой и третьей строк. Кроме того, элементы третьего столбца матрицы А² «» соответствующих элементов второго столбца. Применяя свойство 5 получим, что всякое решение игры ³ = (Х 4,2, 1,4, А²) является решением игры ², а следовательно и игры ¹. Игра ³ определяется матрицей

.

Матрица А³ не имеет седловой точки, т. к. не выполнено равенство

= ,

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

,

либо

.

Аналогично, если игрок 2 использует свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание его проигрыша будет равно . Следовательно, указанные стратегии являются оптимальными в игре ³, а величины значением игры ³. Из предыдущего следует, что эти стратегии оптимальны и в ¹.

Таким образом, стратегия Х = (, 0,, 0) является оптимальной стратегией игрока 1, стратегия = (0,,, 0) оптимальной стратегией игрока 2 в игре ¹, а значение игры ¹ равно . В силу свойства 4 решением игры будет тройка (Х, ,).

Игры порядка 2 х 2.

В общем случае игра 22 определяется матрицей

Прежде всего, необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. В противном случае один из игроков (например 1) имеет чистую оптимальную стратегию, а другой только смешанные. Не ограничивая общности, можно считать, что оптимальной стратегией игрока 1 является выбор с вероятностью 1 первой строки. Далее, по свойству 1 следует, что а₁₁ = а₁₂ = и матрица имеет вид

.

Легко видеть, что для матриц такого вида одна из стратегий игрока 2 является доминируемой. Следовательно, по свойству 4 этот игрок имеет чистую стратегию, что противоречит предположению. Пусть Х = (, 1 ) оптимальная стратегия игрока 1. Так как игрок 2 имеет смешанную оптимальную стратегию, из свойства 1 получим, что (см. также свойство 7)

Отсюда следует, что при 0 столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица А принимает вид

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

;

.

Аналогичные рассуждения приводят нас к тому, что оптимальная стратегия игрока 2 = (, 1 - ) удовлетворяет системе уравнений

откуда .

2. Бесконечные антагонистические игры.

2.1 Определение бесконечной антагонистической игры

Естественным обобщением матричных игр являются бесконечные антагонистические игры (БАИ), в которых хотя бы один из игроков имеет бесконечное количество возможных стратегий. Мы будем рассматривать игры двух игроков, делающих по одному ходу, и после этого происходит распределение выигрышей. При формализации реальной ситуации с бесконечным числом выборов можно каждую стратегию сопоставить определённому числу из единичного интервала, т. к. всегда можно простым преобразованием любой интервал перевести в единичный и наоборот. Напоминание. Пусть Е некоторое множество вещественных чисел. Если существует число y, такое, что x y при всех хЕ (при этом y не обязательно принадлежит Е), то множество Е называется ограниченным сверху, а число y называется верхней границей множества Е. Аналогично определяется ограниченность снизу и нижняя граница множества Е. Обозначаются верхняя и нижняя границы соответственно через sup Е и inf Е соответственно. Пример. Пусть множество Е состоит из всех чисел вида , n = 1,2,… Тогда множество ограничено, его верхняя грань равна 1, а нижняя 0, причём 0Е, а 1Е.

Для дальнейшего изложения теории игр этого класса введём определения и обозначения: [0; 1] единичный промежуток, из которого игрок может сделать выбор; х число (стратегия), выбираемое игроком 1; y число (стратегия), выбираемое игроком 2; М_i(x, y) выигрыш i-го игрока; G (X, Y, M₁, M₂) игра двух игроков, с ненулевой суммой, в которой игрок 1 выбирает число х из множества Х, игрок 2 выбирает число y из множества Y, и после этого игроки 1 и 2 получают соответственно выигрыши M₁(x, y) и M₂(x, y). Пусть, далее, G (X, Y, M) игра двух игроков с нулевой суммой, в которой игрок 1 выбирает число х, игрок 2 число y, после чего игрок 1 получает выигрыш М (x, y) за счёт второго игрока. Большое значение в теории БАИ имеет вид функции выигрышей M (x, y). Так, в отличии от матричных игр, не для всякой функции M (x, y) существует решение. Будем считать, что выбор определённого числа игроком означает применение его чистой стратегии, соответствующей этому числу. По аналогии с матричными играми назовём чистой нижней ценой игры величину

V₁ = M (x, y) или V₁ = M (x, y),

а чистой верхней ценой игры величину

V₂ = M (x, y) или V₂ = M (x, y),

Для матричных игр величины V₁ и V₂ всегда существуют, а в бесконечных играх они могут не существовать. Естественно считать, что, если для какой-либо бесконечной игры величины V₁ и V₂ существуют и равны между собой (V₁ = V₂ = V), то такая игра имеет решение в чистых стратегиях, т.е. оптимальной стратегией игрока 1 есть выбор числа x_oX и игрока 2 числа y_oY, при которых M(x_o, y_o) = V, в этом случае V называется ценой игры, а (x_o, y_o) седловой точкой в чистых стратегиях. Пример 1. Игрок 1 выбирает число х из множества Х = [0; 1], игрок 2 выбирает число y из множества Y = [0; 1]. После этого игрок 2 платит игроку 1 сумму

M (x, y) = 2х² y².

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

(2x² y²) = 2х² 1,

т.е. при этом y = 1. Игрок 1 желает максимизировать свой выигрыш, и поэтому определяет

(M (x, y)) = (2х² 1) = 21 = 1,

который достигается при х = 1.

Итак, нижняя цена игры равна V₁ = 1. Верхняя цена игры

V₂ = ((2х² y²)) = (2 y²) = 21 = 1,

т.е. в этой игре V₁ = V₂ = 1. Поэтому цена игры V = 1, а седловая точка (1; 1).

Пример 2. Игрок 1 выбирает хX = (0; 1), игрок 2 выбирает yY = (0; 1). После этого игрок 1 получает сумму

M (x, y) = x + y

за счёт игрока 2. Поскольку Х и Y открытые интервалы, то на них V₁ и V₂ не существуют. Если бы Х и Y были замкнутые интервалы, то, очевидно, было бы следующее:

V₁ = V₂ = 1 при x_o = 1, y_o = 0.

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

Степень близости к цене игры может характеризоваться числом > 0. Поэтому в описываемой игре можно говорить об оптимальности чистых стратегий х_o = 1, y_o = 0 соответственно игроков 1 и 2 с точностью до произвольного числа > 0. В связи с этим введём следующие определения.

Точка (,), где X, Y, в антагонистической непрерывной игре G называется точкой -равновесия, если для любых стратегий xX игрока 1, yY игрока 2 имеет место неравенство

М (х,) M(,) М(, y) + .

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

Можно доказать, что для того, чтобы функция М имела -седловые точки для любого  > 0 необходимо и достаточно чтобы

M (x, y) = M (x, y).

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

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

F(х) = P( х),

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

Q(y) = P( y).

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

В общем случае дифференциал функции распределения dF(х) выражает вероятность того, что стратегия находится в промежутке

х х + dх.

Аналогично для игрока 2: dQ(y) означает вероятность того, что его стратегия находится в интервале

y y + dy.

Тогда выигрыш игрока 1 составит

М (х, y) dF(х),

а выигрыш игрока 2 равен

М (х, y) dQ(y).

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

E (F, y) =

Напомним, что множество Y для y является замкнутым промежутком [0; 1].

Если игрок 1 применяет свою чистую стратегию х, а игрок 2 y, то выигрыш игрока 1 составит

М (х, y) dP(х) dQ(y).

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

E (F, Q) = .

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

Е (F, Q*) Е (F*, Q*) Е (F*, Q).

Из левой части последнего неравенства следует, что если игрок 1 отступает от своей стратегии F*(х), то его средний выигрыш не может увеличиться, но может уменьшиться за счёт лучших действий игрока 2, поэтому F*(х) называется оптимальной смешанной стратегией игрока 1.

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

По аналогии с матричными играми рассматривается нижняя цена непрерывной игры в смешанных стратегиях

V₁ = E (F, Q)

и верхняя цена игры

V₂ = E (F, Q).

Если существуют такие смешанные стратегии F*(х) и Q*(y) соответственно для игроков 1 и 2, при которых нижняя и верхняя цены непрерывной игры совпадают, то F*(х) и Q*(y) естественно назвать оптимальными смешанными стратегиями соответствующих игроков, а V₁ = V₂ = V ценой игры. Можно доказать, что существование седловой точки в смешанных стратегиях игры G (Х, Y, М) равносильно существованию верхней V₂ и нижней V₁ цен игры в смешанных стратегиях и их равенству V₁ = V₂ = V. Таким образом, решить игру G (Х, Y, М) означает найти седловую точку или такие смешанные стратегии, при которых нижняя и верхняя цены игры совпадают. Теорема 1 (существования). Всякая антагонистическая бесконечная игра двух игроков G с непрерывной функцией выигрышей М (х, y) на единичном квадрате имеет решение (игроки имеют оптимальные смешанные стратегии). Теорема 2. Пусть бесконечная антагонистическая игра с непрерывной функцией выигрышей М (х, y) на единичном квадрате и ценой игры V. Тогда, если Q(y) оптимальная стратегия игрока 2 и для некоторого x_o

,

то x_o не может входить в точки спектра оптимальной стратегии игрока 1; если F(х) оптимальная стратегия игрока 1и для некоторого y_o

,

то y_o не может быть точкой спектра оптимальной стратегии игрока 2. Из теоремы 2 следует, что если один из игроков применяет оптимальную стратегию, а другой чистую, притом что средний выигрыш игрока 1 отличается от цены игры, то эта чистая стратегия не может войти в его оптимальную стратегию (или она входит в неё с вероятностью нуль). Теорема 3. Пусть в бесконечной антагонистической игре функция выигрышей М (х, y) непрерывная для х[0; 1], y[0; 1] и

М (х, y) = М (y, х),

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

2.2 Игры с выпуклыми функциями выигрышей

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

f(₁ х₁ + ₂ х₂) ₁ f(х₁) + ₂ f(х₂),

где х₁ и х₂ любые две точки из интервала (а, b); ₁, ₂ 0, причём ₁ + ₂ = 1.

Если для ₁ 0, ₂ 0 всегда имеет место строгое неравенство

f(₁ х₁ + ₂ х₂) < ₁ f(х₁) + ₂ f(х₂),

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



Напомним, также, что непрерывная и строго выпуклая функция f на замкнутом интервале принимает минимальное значение только в одной точке интервала. Для нахождения решения выпуклой игры можно воспользоваться следующей теоремой. Теорема 4. Пусть М (х, y) непрерывная функция выигрышей игрока 1, на единичном квадрате и строго выпуклая по y для любого х. Тогда имеется единственная оптимальная чистая стратегия y = y_o [0; 1] для игрока 2, цена игры определяется по формуле

V = M (x, y),

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

M (x, y_o) = V.

Замечание. Если в теореме 4 не предполагать строгую выпуклость функции М (х, y) по y, а просто выпуклость, то теорема остаётся в силе с тем отличием, что у игрока 2 оптимальная чистая стратегия не будет единственной. Замечание. Выпуклые игры называют часто выпукло-вогнутыми, т. к. игра в них имеет седлообразное ядро, а так как ядро седлообразное, то игра имеет седловую точку в чистых стратегиях. Таким образом, если М (х, y) непрерывна и выпукла по y, то цена игры определяется по формуле (1), и игрок 2 имеет оптимальную чистую стратегию, определяемую из уравнения (2). Аналогично и для игрока 1: если функция выигрышей М (х, y) непрерывна по обоим аргументам и строго вогнута по х при любом y, то в этом случае игрок 1 имеет единственную оптимальную стратегию.

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

V = M (x, y),

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

M(x_o, y) = V.

Пример. Пусть на квадрате [0; 1] задана функция

М (х, y) = .

Так как

для x [0; 1], y (0; 1),

то М (х, y) строго вогнута по х для любого y (0; 1). Следовательно, цена игры находится по формуле (3)

V = .

Отметим, что при 0 х справедливо равенство

=

а при 0,5 < х 1

=

Поэтому

V = max [; ] =

= max [; ] =

= max [;] = .

При этом значение х получается равным х_o = . Это же значение получается из решения уравнения

= ,

т. к. минимум достигается при y = 0, и это уравнение превращается в следующее

= ,

откуда следует, что х = .

Заметим, что если в функции выигрышей (5) поменять местами х и y, то она не изменится, а следовательно, эта функция выпукла и по y при всех х [0; 1]. Поэтому к ней применима та же теория, т.е. у игрока 2 существует оптимальная чистая стратегия y_o, определяемая из уравнения (4)

=

Очевидно, максимум по х достигается при х = , и последнее уравнение примет вид

= .

Решением последнего уравнения будет y_o = 0. Следовательно, игрок 2 имеет оптимальную чистую стратегию y_o = 0. Замечание. В приведённом выше примере мы могли определить оптимальную стратегию игрока 1, а игрока 2 - только случайно, в силу «удачного» вида М (х, y). Рассмотрим теперь метод определения оптимальных стратегий того игрока, для которого функция выигрышей не обязательно выпукла. Пусть непрерывная функция М (х, y), заданная на единичном квадрате, выпукла по y. Нас будет интересовать вопрос нахождения оптимальных стратегий 1 игрока. Предположим также, что для х [0; 1], y [0; 1] существует частная производная функции М (х, y) по y, причём в точках y = 0 и y = 1 (х, y) = понимается как правая и левая производная соответственно. Обозначим через y_o одну из оптимальных чистых стратегий игрока 2 (эта стратегия существует в соответствии с теоремой 4). Согласно теореме 2 чистые стратегии х игрока 1 могут входить в его оптимальную стратегию с положительной вероятностью, если для них выполняется равенство

М (х, y_o) = V.

Такие чистые стратегии х называются существенными.

Теорема 5. Пусть дана бесконечная антагонистическая игра с непрерывной и дифференцируемой по y на единичном квадрате при любом х функцией выигрышей М (х, y), с оптимальной чистой стратегией y_o игрока 2 и ценой игры V, тогда:

1) если y_o = 1, то среди оптимальных стратегий игрока 1 имеется существенная чистая стратегия х₁, для которой

(х₁, 1) 1;

2) если y_o = 0, то среди оптимальных стратегий игрока 1 имеется существенная чистая стратегия х₂, для которой

(х₂, 0) 0;

3) если 0 y_o 1, то среди оптимальных стратегий игрока 1 найдётся такая, которая является смесью двух существенных стратегий х₁ и х₂. Для этих стратегий