Теория игр и принятие решений
Часть 2. Теория игр.
КЛАССИФИКАЦИЯ ИГР.
Классификацию игр можно проводить: по количеству игроков,
количеству стратегий, характеру взаимодействия игроков, характеру выигрыша,
количеству ходов, состоянию информации и т.д.
В зависимости от количества игроков различают игры двух
и n игроков. Первые из них наиболее изучены. Игры
трёх и более игроков менее исследованы из-за возникающих принципиальных
трудностей и технических возможностей получения решения. Чем больше игроков -
тем больше проблем.
По количеству стратегий игры делятся на конечные и
бесконечные. Если в игре все игроки имеют конечное число возможных стратегий,
то она называется конечной. Если же хотя бы один из игроков имеет
бесконечное количество возможных стратегий игра называется бесконечной.
По характеру взаимодействия игры делятся на:
1)
бескоалиционные: игроки не имеют права вступать в
соглашения, образовывать коалиции;
2)
коалиционные
(кооперативные) –
могут вступать в коалиции.
В кооперативных играх коалиции наперёд определены.
По характеру выигрышей игры делятся на: игры с нулевой
суммой (общий капитал всех игроков не меняется, а перераспределяется между
игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой.
По виду функций выигрыша игры делятся на: матричные,
биматричные, непрерывные, выпуклые, сепарабельные, типа дуэлей и др.
Матричная игра – это конечная игра
двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы
соответствует номеру применяемой стратегии игрока 2, столбец –
номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы
находится выигрыш игрока 1, соответствующий применяемым стратегиям).
Для матричных игр доказано, что любая из них имеет решение и
оно может быть легко найдено путём сведения игры к задаче линейного
программирования.
Биматричная игра – это конечная игра
двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются
матрицами отдельно для соответствующего игрока (в каждой матрице строка
соответствует стратегии игрока 1, столбец – стратегии игрока 2,
на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во
второй матрице –
выигрыш игрока 2.)
Для биматричных игр также разработана теория оптимального
поведения игроков, однако решать такие игры сложнее, чем обычные матричные.
Непрерывной считается игра, в которой функция
выигрышей каждого игрока является непрерывной в зависимости от стратегий.
Доказано, что игры этого класса имеют решения, однако не разработано
практически приемлемых методов их нахождения.
Если функция выигрышей является выпуклой, то такая игра
называется выпуклой. Для них разработаны приемлемые методы решения,
состоящие в отыскании чистой оптимальной стратегии (определённого числа) для
одного игрока и вероятностей применения чистых оптимальных стратегий другого
игрока. Такая задача решается сравнительно легко.
ГЛАВА 1. МАТРИЧНЫЕ ИГРЫ.
§ 1. РЕШЕНИЕ
МАТРИЧНЫХ ИГР В
ЧИСТЫХ СТРАТЕГИЯХ.
Матричная игра двух игроков с нулевой суммой может
рассматриваться как следующая абстрактная игра двух игроков.
Первый игрок имеет m стратегий i
= 1,2,...,m, второй
имеет n стратегий j
= 1,2,...,n. Каждой
паре стратегий (i,j) поставлено в соответствие число аij,
выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 –
свою j-ю стратегию.
Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=), 2 – свою j-ю
стратегию (j=), после чего игрок 1 получает выигрыш аij
за счёт игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму
сумму | аij
| ). На этом игра заканчивается.
Каждая стратегия игрока
i=; j
= часто называется
чистой стратегией.
Если рассмотреть матрицу
А =
то проведение каждой партии
матричной игры с матрицей А сводится к выбору игроком 1
i-й строки, а
игроком 2 j-го
столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij.
Главным в исследовании игр является понятие оптимальных
стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия
игрока является оптимальной, если применение этой стратегии обеспечивает ему
наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока.
Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А
следующим образом: для каждого значения
i (i
=) определяется минимальное значение выигрыша в
зависимости от применяемых стратегий игрока 2
аij (i
= )
т.е. определяется минимальный
выигрыш для игрока 1 при условии, что он примет свою i-ю
чистую стратегию, затем из этих минимальных выигрышей отыскивается такая
стратегия i
= iо,
при которой этот минимальный выигрыш будет максимальным, т.е. находится
аij
= = (1).
Определение.
Число , определённое по формуле (1) называется нижней чистой ценой игры
и показывает, какой минимальный выигрыш может гарантировать себе игрок 1,
применяя свои чистые стратегии при всевозможных действиях игрока 2.
Игрок 2 при оптимальном своём поведении должен стремится по
возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1.
Поэтому для игрока 2 отыскивается
аij
т.е. определяется max
выигрыш игрока 1, при условии, что игрок 2 применит свою j-ю
чистую стратегию, затем игрок 2 отыскивает такую свою j
= j1
стратегию, при которой игрок 1 получит min
выигрыш, т.е. находит
aij
= = (2).
Определение.
Число , определяемое по формуле (2), называется чистой верхней ценой игры и показывает, какой
максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.
Другими словами, применяя свои чистые стратегии игрок 1
может обеспечить себе выигрыш не меньше , а игрок 2 за счёт применения своих чистых стратегий может
не допустить выигрыш игрока 1 больше, чем .
Определение.
Если в игре с матрицей А =, то говорят, что эта игра имеет седловую точку
в чистых стратегиях и чистую цену
игры
u = =.
Седловая точка
это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых
достигается равенство = . В это понятие вложен следующий смысл: если один из игроков
придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет
поступить лучше, чем придерживаться стратегии, соответствующей седловой точке.
Математически это можно записать и иначе:
где i,
j
любые чистые стратегии соответственно игроков 1 и 2; (iо,jо)
стратегии, образующие седловую точку.
Таким образом, исходя из (3), седловой элемент является минимальным
в iо-й
строке и максимальным в jо-м столбце в матрице А. Отыскание
седловой точки матрицы А происходит следующим образом: в матрице А последовательно
в каждой строке находят минимальный элемент и проверяют, является ли
этот элемент максимальным в своём столбце. Если да, то он и есть
седловой элемент, а пара стратегий, ему соответствующая, образует седловую
точку. Пара чистых стратегий (iо,jо)
игроков 1 и 2, образующая седловую точку и седловой элемент , называется решением
игры. При этом iо и jо называются оптимальными чистыми стратегиями соответственно игроков 1 и 2.
Пример 1
Седловой точкой является пара (iо
= 3; jо = 1),
при которой u == = 2.
Заметим, что хотя выигрыш в ситуации (3;3) также равен 2 ==, она не является седловой точкой, т.к. этот выигрыш не
является максимальным среди выигрышей третьего столбца.
Пример 2
Из анализа матрицы выигрышей видно, что , т.е. данная матрица не имеет седловой точки. Если игрок 1
выбирает свою чистую максиминную стратегию
i = 2, то игрок 2,
выбрав свою минимаксную j = 2, проиграет только 20. В этом случае
игроку 1 выгодно выбрать стратегию i
= 1, т.е. отклониться от своей чистой максиминной стратегии и выиграть 30.
Тогда игроку 2 будет выгодно выбрать стратегию
j
= 1, т.е. отклониться от своей чистой минимаксной стратегии и проиграть 10. В
свою очередь игрок 1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а
игрок 2 ответит выбором 2-й стратегии и т.д.
§ 2. СМЕШАННОЕ
РАСШИРЕНИЕ МАТРИЧНОЙ ИГРЫ.
Исследование в матричных играх начинается с нахождения её
седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в
чистых стратегиях, то нахождением этой седловой точки заканчивается исследование
игры. Если же в игре нет седловой точки в чистых стратегиях, то можно найти
нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не
должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен
в получении выигрыша не меньше нижней цены игры. Улучшение решений матричных
игр следует искать в использовании секретности применения чистых стратегий и
возможности многократного повторения игр в виде партии. Этот результат
достигается путём применения чистых стратегий случайно, с определённой вероятностью.
Определение. Смешанной
стратегией игрока называется полный набор вероятностей применения его
чистых стратегий.
Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m,
то его смешанная стратегия x – это набор чисел x = (x1, ..., xm) удовлетворяющих соотношениям
xi ³
0 (i =
1,m),
= 1.
Аналогично для игрока 2, который
имеет n чистых стратегий, смешанная стратегия y
это набор чисел
y
= (y1,
..., yn), yj
³
0, (j
= 1,n), = 1.
Так как каждый раз применение
игроком одной чистой стратегии исключает применение другой, то чистые стратегии
являются несовместными событиями. Кроме того, они являются единственными
возможными событиями.
Чистая стратегия есть частный случай смешанной стратегии.
Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью
1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем
смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои
стратегии независимо от выбора другого игрока.
Определение.
Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей
E (A, x, y) == x A yT
Первый игрок имеет
целью за счёт изменения своих смешанных стратегий х максимально увеличить свой средний выигрыш Е (А, х, y),
а второй –
за счёт своих смешанных стратегий стремится сделать Е (А, х, y)
минимальным, т.е. для решения игры необходимо найти такие х и y, при которых достигается верхняя цена
игры
Е
(А, х, y).
Аналогичной должна быть ситуация и
для игрока 2, т.е. нижняя цена игры должна быть
Е (А, х, y).
Подобно играм,
имеющим седловые точки в
чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборы хо, уо соответственно, которые удовлетворяют
равенству
Е
(А, х, y)
= Е (А, х, y) = Е (А,
хо, уо).
Величина Е (А, хо ,уо) называется при этом ценой игры и обозначается
через u.
Имеется и другое определение оптимальных смешанных
стратегий: хо, уо называются оптимальными смешанными
стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:
Е (А, х, уо) £
Е (А, хо, уо) £
Е (А, хо, у)
Оптимальные смешанные стратегии и цена игры называются решением матричной игры.
Основная теорема матричных игр имеет вид :
Теорема (о минимаксе). Для
матричной игры с любой матрицей А
величины
Е (А, х, y) и Е
(А, х, y)
существуют и равны между собой.
§ 3. СВОЙСТВА
РЕШЕНИЙ МАТРИЧНЫХ ИГР.
Обозначим через G
(Х,Y,А) игру двух лиц
с нулевой суммой, в которой игрок 1 выбирает стратегию х Î Х, игрок 2 – y
Î U, после чего игрок 1 получает выигрыш А = А (х, y)
за счёт игрока 2.
Определение.
Стратегия х1 игрока 1 доминирует (строго доминирует) над
стратегией х2, если
А (х1, y) ³
А (х2, y) (А (х1,
y) > А (х2, y)), y Î U.
Стратегия y1
игрока 2 доминирует (строго доминирует) над стратегией y2, если
А (х, y1) £
А (х, y2) (А (х,
y1) < А (х, y2)), х Î
Х.
При этом стратегии х2
и y2
называются доминируемыми (строго доминируемыми).
Спектром смешанной
стратегии игрока в конечной антагонистической игре называется множество
всех его чистых стратегий, вероятность которых согласно этой стратегии положительна.
Свойство 1.
Если чистая стратегия одного из игроков содержится в спектре некоторой его
оптимальной стратегии, то выигрыш этого игрока в ситуации, образованной данной
чистой стратегией и любой оптимальной стратегией другого игрока, равен значению
конечной антагонистической игры.
Свойство 2. Ни
одна строго доминируемая чистая стратегия игрока не содержится в спектре его
оптимальной стратегии.
Игра G¢ = (Х¢,Y¢,А¢) называется подыгрой игры G
(Х,Y,А), если Х¢Ì Х, U¢Ì
U, а матрица А¢
является подматрицей матрицы А.
Матрица А¢
при этом строится следующим образом. В матрице А остаются строки и столбцы, соответствующие стратегиям Х¢
и U¢,
а остальные “вычеркиваются”. Всё то что “останется” после этого в матрице А и будет матрицей А¢.
Свойство 3.
Пусть G = (Х,Y,А) –
конечная антагонистическая игра, G¢ = (Х \
х¢,Y,А)
подыгра игры G, а х¢
чистая стратегия игрока 1 в игре G,
доминируемая некоторой стратегией , спектр которой не содержит х¢. Тогда всякое
решение (хо, yо,
u) игры G¢ является решением игры G.
Свойство 4.
Пусть G = (Х,Y,А) –
конечная антагонистическая игра, G¢ = (Х,Y
\
y¢,А) – подыгра игры G, а y¢ – чистая стратегия игрока 2 в игре G, доминируемая
некоторой стратегией , спектр которой не содержит y¢.Тогда всякое решение игры G¢ является решением G.
Свойство 5.
Если для чистой стратегии х¢ игрока 1 выполнены условия свойства 3, а для
чистой стратегии y¢ игрока 2 выполнены условия свойства 4, то
всякое решение игры G¢ = (Х \
х¢,Y
\
y¢,А) является решением игры G
= (Х,Y,А).
Свойство 6.
Тройка (хо, yо,
u) является решением
игры G = (Х,Y,А) тогда и только
тогда, когда (хо, yо,
кu +а) является решением
игры G(Х,Y,кА+а), где а – любое вещественное
число, к > 0.
Свойство 7.
Для того, чтобы хо = () была оптимальной
смешанной стратегией
матричной игры с матрицей А и ценой
игры u, необходимо и
достаточно выполнение следующих неравенств
(j = )
Аналогично для игрока 2 : чтобы yо = (, ...,, ...,) была оптимальной смешанной стратегией игрока 2
необходимо и достаточно выполнение следующих неравенств:
(i = )
Из последнего свойства вытекает:
чтобы установить, является ли предполагаемые (х, y)
и u решением матричной игры,
достаточно проверить, удовлетворяют ли они неравенствам (*) и (**). С другой
стороны, найдя неотрицательные решения неравенств (*) и (**) совместно со следующими
уравнениями
,
получим решение матричной игры.
Таким образом, решение матричной игры сводится к нахождению
неотрицательных параметров решений линейных неравенств (*) (**) и линейных
уравнений (***). Однако это требует большого объёма вычислений, которое растёт
с увеличением числа чистых стратегий игроков. (Например для матрицы 33 имеем систему из 6
неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности
используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем
следует во всех случаях проверить выполнение неравенства
= .
Если оно выполняется, то игроки имеют чистые оптимальные
стратегии (игрок 1 – чистую максиминная, а игрок 2 –
чистую минимаксная). В противном случае хотя бы у одного игрока оптимальные
стратегии будут смешанные. Для матричных игр небольшого размера эти решения
можно найти, применяя свойства 1 –
5.
Замечание.
Отметим, что исключение доминируемых (не
строго) стратегий может привести к потере некоторых решений. Если же
исключаются только строго доминируемые стратегии, то множество решений
игры не изменится.
Пример 3. Пусть G
= (Х,Y,А), где Х = {1, 2, 3, 4};
Y = {1,
2, 3, 4},
а функция выигрыша А задана следующим
образом :
где С >
0.
Решение. Прежде всего заметим, что по свойству 6
достаточно решить игру G1
= (Х,Y,А), где А1 =А . В матричной
форме игра G1
определяется матрицей выигрышей
Элементы четвёртой строки этой матрицы “ £ ” соответствующих элементов третьей строки и
поэтому третья стратегия игрока 1 доминирует над четвёртой. Кроме того,
элементы первого столбца матрицы А1 “ ³
соответствующих элементов второго столбца, Следовательно, вторая стратегия
игрока 2 доминирует над его первой стратегией.
Далее, из свойства 5 следует, что всякое решение игры G2 = (Х \ {4}, Y \
{1}, А1) является решением игры G1. В
матричной форме игру G2
можно представить матрицей
.
Очевидно, что элементы второй
строки “ ³” полусуммы соответствующих элементов первой и
третьей строк. Кроме того, элементы третьего столбца матрицы А2 “ ³“ соответствующих элементов второго столбца.
Применяя свойство 5 получим, что всякое решение игры G3
= (Х \ {4,2},
Y \
{1,4},
А2) является решением игры
G2, а
следовательно и игры G1.
Игра G3
определяется матрицей
.
Матрица А3 не имеет седловой точки, т.к. не выполнено равенство
= ,
а игра G3
не имеет решения в чистых стратегиях, т.е. оптимальные стратегии игроков
являются смешанными. Эти стратегии (в данном случае) легко найти из анализа
структуры матрицы А3.
Поскольку матрица А3 симметрична,
можно предположить, что игроки в оптимальной стратегии используют свои чистые
стратегии с равными вероятностями.
Действительно, если игрок 1 выбирает с равными вероятностями
стратегии 1 и 3, то при применении любой из двух чистых стратегий игроком 2
математическое ожидание выигрыша игрока 1 будет равным либо
,
либо
.
Аналогично, если игрок 2 использует
свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание
его проигрыша будет равно . Следовательно, указанные стратегии являются оптимальными в
игре G3, а величины
–
значением игры G3.
Из предыдущего следует, что эти стратегии оптимальны и в G1.
Таким образом, стратегия Х = (, 0,, 0) является оптимальной стратегией игрока 1, стратегия Y = (0,,, 0) – оптимальной стратегией игрока 2 в игре G1, а
значение игры G1
равно . В силу свойства 4 решением игры G
будет тройка (Х,Y,).
§ 4. ИГРЫ
ПОРЯДКА 2 х 2.
В общем случае игра
22 определяется
матрицей
Прежде всего необходимо проверить,
есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых
стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут
чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей
выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие
оптимальные стратегии, которые используют все свои чистые стратегии с
положительными вероятностями. В противном случае один из игроков (например 1)
имеет чистую оптимальную стратегию, а другой – только смешанные. Не
ограничивая общности, можно считать, что оптимальной стратегией игрока 1
является выбор с вероятностью 1 первой строки. Далее, по свойству 1 следует, что а11 = а12 = u и матрица имеет вид
.
Легко видеть, что для матриц такого
вида одна из стратегий игрока 2 является доминируемой. Следовательно, по
свойству 4 этот игрок имеет чистую стратегию, что противоречит предположению.
Пусть Х = (x, 1 - x) – оптимальная стратегия игрока 1. Так как
игрок 2 имеет смешанную оптимальную стратегию, из свойства 1 получим, что (см.
также свойство 7)
Отсюда следует, что при u ¹
0 столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности,
отличным от единицы. Если же коэффициент пропорциональности равен единице, то
матрица А принимает вид
и игрок 1 имеет чистую оптимальную
стратегию (он выбирает с вероятностью 1 ту из строк, элементы которой не меньше
соответствующих элементов другой), что противоречит предположению.
Следовательно, если u ¹
0 и игроки имеют только смешанные оптимальные стратегии, то определитель
матрицы А отличен от нуля. Из этого
следует, что последняя система уравнений имеет единственное решение. Решая её,
находим
;
.
Аналогичные рассуждения приводят нас к
тому, что оптимальная
стратегия игрока 2 Y
= (h, 1 - h) удовлетворяет
системе уравнений
откуда
.
§ 5. ГРАФИЧЕСКИЙ
МЕТОД РЕШЕНИЯ ИГР 2 х n
И m х 2.
Поясним метод на примерах.
Пример 1.
Рассмотрим игру, заданную платёжной матрицей.
На плоскости хОy введём систему координат и на оси Ох
отложим отрезок единичной длины А1, А2, каждой
точке которого поставим в соответствие некоторую смешанную стратегию игрока 1
(х, 1 -
х). В частности, точке А1 (0;0) отвечает стратегия А1,
точке А2 (1;0) – стратегия А2 и т.д.
y
11
7
М
N 5
3
2 u 2
x
В точках А1 и А2 восстановим
перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На
первом перпендикуляре (в данном случае он совпадает с осью 0y)
отложим выигрыш игрока 1 при стратегии
А1, а на втором –
при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1
игрока 2 –
2, при стратегии В2 – 3, а при стратегии В3 –
11. Числам 2, 3, 11 на оси 0х соответствуют точки В1, В2 и В3.
Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1
равен 7, при В2 –
5, а при В3 –
2. Эти числа определяют точки В¢1, В2¢, В3¢ на перпендикуляре, восстановленном в
точке А2.Соединяя между собой точки В1 и В¢1, В2 и В¢2, В3 и В¢3
получим три прямые, расстояние до
которых от оси 0х определяет средний
выигрыш при любом сочетании соответствующих стратегий. Например, расстояние
от любой точки отрезка В1В¢1 до оси 0х определяет средний выигрыш u1 при
любом сочетании стратегий А1 А2 (с частотами х и 1–х) и стратегией В1
игрока 2. Это расстояние равно
2х1 +
6(1 - х2)
= u1
(Вспомните планиметрию и рассмотрите
трапецию А1 B1 B¢1 A2). Таким образом, ординаты точек, принадлежащих ломанной В1 M N В¢3
определяют
минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является
максимальной в точке N;
следовательно этой точке соответствует оптимальная стратегия Х* =
(х, 1-х),
а её ордината равна цене игры u. Координаты точки N находим как точку
пересечения прямых В2
B¢2 и В3 B¢3.
Соответствующие два уравнения имеют
вид
.
Следовательно Х =
(; ), при цене игры u = . Таким образом мы можем найти оптимальную стратегию при
помощи матрицы
Оптимальные стратегии для игрока 2
можно найти из системы
и, следовательно, Y = (0; ; ). (Из рисунка видно, что стратегия B1 не войдёт в оптимальную
стратегию.
Пример 2. Найти решение игры, заданной матрицей A¢4
x
8 A¢3
7 A1 A¢2
6 К
6
A¢1
5 A2
4 A3
u
2 A4
1 B2 B1
y
Решение. Матрица имеет размерность 2 х 4. Строим прямые,
соответствующие стратегиям игрока 1. Ломанная
А1 K А¢4
соответствует
верхней границе выигрыша игрока 1, а отрезок N K
цене
игры. Решение игры таково
U
= (; ); Х = (; 0; 0; ); u = .
§6. СВЕДЕНИЕ МАТРИЧНОЙ
ИГРЫ К ЗАДАЧЕ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Предположим, что
цена игры положительна (u > 0). Если это не так, то согласно свойству 6 всегда можно подобрать такое число с,
прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными
элементами, и следовательно, с положительным значением цены игры. При этом
оптимальные смешанные стратегии обоих игроков не изменяются.
Итак, пусть
дана матричная игра с матрицей А
порядка m х n. Согласно свойству 7 оптимальные смешанные стратегии х = (х1,
..., хm), y = (y1, ..., yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.
Разделим все уравнения и неравенства
в (1) и (2) на u (это можно сделать, т.к. по предположению u
> 0) и введём обозначения :
, ,
Тогда (1) и (2) перепишется в виде :
, , , ,
, , , .
Поскольку первый игрок стремится
найти такие значения хi и, следовательно, pi , чтобы
цена игры u была максимальной, то
решение первой задачи сводится к нахождению таких неотрицательных значений pi , при которых
, .
Поскольку второй игрок стремится
найти такие значения yj и, следовательно, qj,
чтобы цена игры u была наименьшей, то
решение второй задачи сводится к нахождению таких неотрицательных значений qj, , при которых
, .
Формулы (3) и (4) выражают
двойственные друг другу задачи линейного
программирования (ЛП).
Решив эти задачи, получим значения pi , qj и u.Тогда смешанные стратегии, т.е. xi и yj получаются по формулам :
Пример. Найти решение игры, определяемой матрицей.
Решение. При решении этой игры к каждому элементу
матрицы А прибавим 1 и получим следующую
матрицу
Составим теперь пару
взаимно-двойственных задач :
Решим вторую из них Б.п. q1 q2 q3 q4 q5 q6 Решение å Отношение -1 -1 -1 0 0 0 0 -3 q4 1 2 0 1 0 0 1 5 — q5 1 0 1 0 1 0 1 4 q6 2 1 0 0 0 1 1 5 — Б.п. q1 q2 q3 q4 q5 q6 Решение å Отношение 0 -1 0 0 1 0 1 1 q4 1 2 0 1 0 0 1 5 q3 1 0 1 0 1 0 1 4 — q6 2 1 0 0 0 1 1 5 Б.п. q1 q2 q3 q4 q5 q6 Решение å Отношение 0 0 1 0 q2 1 0 0 0 q3 1 0 1 0 1 0 1 4 q6 0 0 0 1
Из оптимальной симплекс-таблицы
следует, что
(q1, q2, q3) = (0;; 1),
а из соотношений двойственности
следует, что
( p1, p2, p3) = (; 1; 0).
Следовательно, цена игры с платёжной
матрицей А1 равна
. ,
а игры с платёжной матрицей А :
.
При этом оптимальные стратегии
игроков имеют вид:
Х = (х1, х2, х3)
= (uр1; uр2; uр3)
= =
Y = (y1, y2, y3) = (uq1; uq2;
uq3) = = .
ГЛАВА 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,M1,M2)
игра двух игроков, с ненулевой суммой, в которой игрок 1 выбирает число х из множества Х, игрок 2 выбирает число y из множества Y, и после этого игроки 1
и 2 получают соответственно выигрыши M1(x, y) и M2(x, y). Пусть, далее, G (X,Y,M) –
игра двух игроков с нулевой суммой, в которой игрок 1 выбирает число х,
игрок 2 –
число y, после чего игрок 1 получает
выигрыш М(x, y) за счёт второго игрока.
Большое значение в теории
БАИ имеет вид функции
выигрышей M(x, y). Так, в отличии от матричных игр, не для всякой функции
M(x, y) существует решение. Будем считать, что выбор определённого числа
игроком означает применение его чистой стратегии, соответствующей этому числу.
По аналогии с матричными играми назовём чистой
нижней ценой игры величину
V1 = M(x, y)
или V1 = M(x, y),
а чистой верхней ценой игры величину
V2 = M(x, y) или V2 = M(x, y),
Для матричных игр
величины V1 и V2 всегда существуют, а в бесконечных играх они могут
не существовать.
Естественно считать, что, если для какой-либо бесконечной
игры величины V1 и V2 существуют и равны между
собой (V1 = V2 = V), то такая игра имеет решение в чистых стратегиях, т.е.
оптимальной стратегией игрока 1 есть выбор числа xoÎX и игрока 2 –
числа yoÎY, при которых M(xo, yo) = V, в этом случае
V называется ценой игры, а (xo, yo) – седловой точкой в чистых
стратегиях.
Пример 1. Игрок
1 выбирает число х из множества Х = [0; 1], игрок 2 выбирает число y из множества
Y = [0; 1]. После этого
игрок 2 платит игроку 1
сумму
M(x, y) = 2х2 - y2.
Поскольку игрок 2 хочет
минимизировать выигрыш игрока 1, то он определяет
(2x2 - y2) = 2х2 - 1,
т.е. при этом y = 1. Игрок 1 желает максимизировать
свой выигрыш, и поэтому определяет
(M(x, y))
= (2х2 - 1)
= 2-1 = 1,
который достигается при х = 1.
Итак, нижняя цена игры равна V1
= 1. Верхняя цена игры
V2 = ((2х2 - y2)) = (2 - y2) = 2-1 = 1,
т.е. в этой игре V1 = V2 = 1. Поэтому цена игры V = 1, а седловая точка (1;1).
Пример 2. Игрок
1 выбирает хÎX = (0; 1), игрок 2 выбирает yÎY = (0; 1). После этого игрок 1 получает сумму
M(x, y) = x + y
за счёт игрока 2. Поскольку Х и Y -
открытые интервалы, то на них V1 и V2 не существуют. Если бы Х и Y
были замкнутые интервалы, то, очевидно, было бы следующее :
V1 = V2
= 1 при xo = 1, yo = 0.
С другой стороны, ясно, что,
выбирая х достаточно близкое к 1, игрок 1 будет уверен, что он получит
выигрыш не меньше, чем число, близкое к цене игры V =
1; выбирая y близкое к нулю, игрок 2 не допустит, чтобы выигрыш игрока 1 значительно отличался от цены игры V = 1.
Степень близости к цене игры может характеризоваться числом e > 0. Поэтому в описываемой
игре можно говорить об оптимальности чистых стратегий хo = 1, yo = 0
соответственно игроков 1 и 2 с точностью до произвольного числа e > 0. В связи с этим введём
следующие определения.
Точка (,), где ÎX, ÎY, в антагонистической непрерывной игре G
называется точкой e-равновесия , если для любых стратегий xÎX игрока 1, yÎY
игрока 2 имеет место неравенство
М(х,) - e £ M(,) £
М(, y) + e.
Точка e-равновесия (,) называется также e-седловой
точкой функции М(x, y), а стратегии и
называются e-оптимальными стратегиями. Эти
стратегии являются оптимальными с точностью до e в том смысле, что, если
отклонение от оптимальной стратегии никакой пользы игроку принести не может, то
его отклонение от e-оптимальной
стратегии может увеличить его выигрыш не более, чем на e.
Можно доказать, что для того, чтобы функция М имела e-седловые точки для любого
e>0 необходимо
и достаточно чтобы
M(x, y) = M(x, y).
Если игра G не
имеет седловой точки (e-седловой точки) в чистых стратегиях, то оптимальные
стратегии можно искать среди смешанных стратегий. Однако, в качестве вероятностной
меры здесь вводятся функции распределения вероятностей применения игроками
чистых стратегий.
Пусть F(х) – функция распределения
вероятностей применения чистых стратегий игроком 1. Если число x -
чистая стратегия игрока 1, то
F(х) = P(x
£
х),
где P(x
£
х) означает вероятность того, что
случайно выбранная чистая стратегия x не будет превосходить числа х. Аналогично рассматривается функция
распределения вероятностей применения чистых стратегий h игроком 2
Q(y) = P(h £ y).
Функции F(х) и Q(y) называются смешанными стратегиями
соответственно игроков 1 и 2. Если F(х) и Q(y) дифференцируемы, то существуют их производные,
обозначаемые соответственно через f(x) и q(y) (функции плотности распределения).
В общем случае дифференциал функции распределения dF(х) выражает вероятность того, что
стратегия x
находится в промежутке
х £ x £ х + dх.
Аналогично для игрока 2: dQ(y) означает вероятность
того, что его стратегия h находится в интервале
y £ h £ 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 при применении игроками оптимальных смешанных стратегий,
называется ценой игры.
По аналогии с матричными играми рассматривается нижняя цена
непрерывной игры в смешанных стратегиях
V1 = E(F,Q)
и верхняя цена игры
V2 = E(F,Q).
Если существуют такие смешанные
стратегии F*(х) и Q*(y)
соответственно для игроков 1 и 2, при которых нижняя и верхняя цены
непрерывной игры совпадают, то F*(х) и Q*(y) естественно назвать оптимальными
смешанными стратегиями соответствующих игроков, а V1 = V2 =
V –
ценой игры.
Можно доказать, что существование седловой точки в смешанных
стратегиях игры G(Х,Y,М) равносильно существованию верхней
V2 и нижней V1 цен игры в
смешанных стратегиях и их равенству V1 = V2 = V.
Таким образом, решить игру G(Х,Y,М) –
означает найти седловую точку или такие смешанные стратегии, при которых нижняя
и верхняя цены игры совпадают.
Теорема 1 (существования). Всякая
антагонистическая бесконечная игра двух игроков G с
непрерывной функцией выигрышей М(х,y) на единичном квадрате имеет решение
(игроки имеют оптимальные смешанные стратегии).
Теорема 2. Пусть – бесконечная
антагонистическая игра с непрерывной функцией выигрышей М(х, y) на единичном
квадрате и ценой игры V. Тогда, если Q(y) – оптимальная стратегия
игрока 2 и для некоторого xo
,
то xo не
может входить в точки спектра оптимальной стратегии игрока 1; если F(х)
оптимальная стратегия игрока 1и для некоторого yo
,
то yo не может быть точкой спектра
оптимальной стратегии игрока 2.
Из теоремы 2 следует, что
если один из игроков применяет оптимальную стратегию, а другой –
чистую, притом что средний выигрыш игрока 1 отличается от цены игры, то эта чистая
стратегия не может войти в его оптимальную стратегию (или она входит в неё с
вероятностью нуль).
Теорема 3. Пусть в бесконечной антагонистической
игре функция выигрышей М(х,y) непрерывная для хÎ[0;
1], yÎ[0;
1] и
М(х, y) = -М(y, х),
тогда цена игры равна нулю и любая
оптимальная стратегия одного игрока будет также оптимальной стратегией другого
игрока.
Сформулированные свойства оптимальных смешанных стратегий и
цены игры помогают находить или проверять решения, но они ещё не дают в общем
виде приемлемых методов решения игры. Более того, не существует общих методов
для точного нахождения решения БАИ, и в том числе непрерывных игр на единичном
квадрате. Поэтому рассматриваются частные виды антагонистических бесконечных
игр.
§2. ИГРЫ
С ВЫПУКЛЫМИ ФУНКЦИЯМИ
ВЫИГРЫШЕЙ.
Игры с выпуклыми непрерывными функциями выигрышей,
называемые часто ядром, называются
выпуклыми.
Напомним, что выпуклой
функцией f действительной переменной х
на интервале (а,b) называется такая функция, для которой выполняется
неравенство
f(a1 х1 + a2 х2) £
a1 f(х1)
+ a2 f(х2),
где
х1
и х2 – любые две точки из интервала (а,b);
a1, a2 ³ 0, причём a1
+ a2
= 1.
Если для a1 ¹ 0, a2 ¹ 0 всегда имеет место строгое
неравенство
f(a1 х1 + a2 х2) < a1 f(х1) + a2 f(х2),
то функция f называется строго выпуклой на (а;b).
Геометрически выпуклая функция изображает дугу, график которой расположен ниже
стягивающей её хорды (см. рис.)
Напомним, также, что непрерывная и строго выпуклая
функция f на замкнутом интервале принимает
минимальное значение только в одной точке интервала.
Для нахождения решения выпуклой игры можно воспользоваться
следующей теоремой.
Теорема 4. Пусть М(х, y) –
непрерывная функция выигрышей игрока 1, на единичном квадрате и строго выпуклая по y для любого
х. Тогда имеется единственная оптимальная чистая стратегия y = yo Î[0;1] для игрока 2, цена
игры определяется по формуле
V = M(x, y),
значение yo определяется как
решение следующего уравнения
M(x, yo) = V.
Замечание.
Если в теореме 4 не
предполагать строгую выпуклость функции М(х, y) по y, а просто выпуклость, то теорема остаётся в силе с тем отличием,
что у игрока 2 оптимальная чистая стратегия не будет единственной.
Замечание.
Выпуклые игры называют часто выпукло-вогнутыми, т.к. игра в них имеет седлообразное
ядро, а так как ядро седлообразное, то игра имеет седловую точку в чистых
стратегиях.
Таким образом, если М(х, y) непрерывна и выпукла по y, то цена игры определяется по формуле (1), и
игрок 2 имеет оптимальную чистую стратегию, определяемую из уравнения (2).
Аналогично и для игрока 1: если функция выигрышей М(х,
y) непрерывна по обоим аргументам и строго
вогнута по х при любом
y, то в этом случае игрок 1 имеет единственную оптимальную
стратегию.
Цена игры определяется по формуле
V = M(x,y),
а чистая оптимальная стратегия хo игрока 1
определяется из уравнения
M(xo, 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 существует оптимальная чистая стратегия
yo, определяемая из
уравнения (4)
=
Очевидно, максимум по х достигается при х = , и последнее уравнение примет вид
= .
Решением последнего уравнения будет yo =
0. Следовательно, игрок 2 имеет оптимальную чистую стратегию yo = 0.
Замечание. В приведённом выше примере мы могли определить
оптимальную стратегию игрока 1, а игрока 2 - только случайно, в силу “удачного”
вида М(х, y).
Рассмотрим теперь метод определения оптимальных стратегий
того игрока, для которого функция выигрышей не обязательно выпукла. Пусть непрерывная функция М(х, y),
заданная на единичном квадрате, выпукла по y. Нас будет интересовать вопрос нахождения оптимальных стратегий 1
игрока. Предположим также, что для х Î[0; 1],
y Î[0; 1] существует частная производная
функции М(х, y) по y, причём в точках y
= 0 и y = 1 (х, y)
= понимается как правая
и левая производная соответственно. Обозначим через yo одну из оптимальных чистых
стратегий игрока 2 (эта стратегия существует в соответствии с теоремой 4).
Согласно теореме 2 чистые стратегии х игрока 1 могут входить в его оптимальную стратегию
с положительной вероятностью, если для них выполняется равенство
М(х, yo) = V.
Такие чистые стратегии х называются существенными.
Теорема 5. Пусть
дана бесконечная антагонистическая игра с непрерывной и дифференцируемой по y на единичном
квадрате при любом х функцией выигрышей М(х,
y), с оптимальной чистой стратегией yo игрока 2 и ценой игры V, тогда :
1) если yo = 1, то среди оптимальных
стратегий игрока 1 имеется существенная чистая стратегия х1,
для которой
(х1, 1) £ 1;
2) если yo = 0, то среди оптимальных
стратегий игрока 1 имеется существенная чистая стратегия х2, для
которой
(х2, 0) ³ 0;
3) если 0 £
yo £
1, то среди оптимальных стратегий
игрока 1 найдётся такая, которая является смесью двух существенных
стратегий х1 и х2. Для этих
стратегий
(х1, yo)
£ 0, (х2, yo)
³ 0,
стратегия х1 употребляется
с вероятностью a,
стратегия х2 –
с вероятностью (1 -
a),
где a
находится из уравнения
a(х1, yo) + (1 -
a)(х2, yo) = 0.
Пример. Пусть функция выигрышей в бесконечной
антагонистической игре задана на единичном квадрате и равна
М(х, y) = (х - y)2
= х2 - 2хy
+ y2.
Эта функция непрерывна по х и
y, и поэтому эта игра имеет решение.
Кроме того
= 2 > 0.
Следовательно, М(х, y) выпукла по y,
и поэтому согласно теореме 4 цена игры определяется по формуле (1), игрок 2
имеет чистую оптимальную стратегию yo, определяемую из уравнения (2). Таким образом, имеем
V = (x - y)2;
Для определения (x2 - 2xy + y2) последовательно найдём
= 2x - 2y := 0 Þ x = y
= 2 > 0 Þ при x = y
функция M имеет минимум для любого y.
Þ максимум достигается в одной из крайних
точек x = 0 и (или) x = 1
M(0; y) = y2
M(1; y) = 1 - 2y +
y2 = (y - 1)2
Þ
V= max {y2; (1 - y)2}
Данный max {...} достигается в том случае, если y2 = (1 - y)2,
т.е. y = .
Следовательно V = при yo = .
Определим теперь оптимальные стратегии для игрока 1.
Поскольку yo = , то 0 < yo < 1. Согласно теореме 5 рассмотрим третий случай.
Определим х
из уравнения
М(х, yo) = V,
то есть
(х -)2
= .
Решая последнее уравнение,
получим х1 = 0, х2
= 1. Теперь необходимо определить величину a–
вероятность применения чистой стратегии
х1
= 0. С этой целью используем уравнение (*).
a(0,) + (1 - a)(1,) = 0.
Нетрудно найти
Тогда уравнение для a примет вид :
a - (1 - a) =
0,
откуда a
=. Следовательно, стратегия игрока 1
F(х) = Jo(х) + J1(х),
а игрока 2
Q(y) = (y).
Здесь через (x) обозначена ступенчатая функция
(x) = .
Глава 3. БЕСКОАЛИЦИОННЫЕ ИГРЫ
Антагонистические игры, которые
мы изучали ранее, описывают конфликты весьма частного вида. Более того, для
большинства имеющих место в реальной жизни конфликтов антагонистические игры
либо вовсе не могут считаться приемлемыми, адекватными описаниями, либо, в
лучшем случае, могут рассматриваться как первые грубые приближения.
Во-первых, антагонистические игры
никак не затрагивают своими описаниями конфликты с числом строк, большим чем
два. В месте с тем, такие многосторонние конфликты не только встречаются в
действительности, но являются принципиально более сложными, чем конфликты с
двумя участниками, и даже не поддаются сведению к последним.
Во-вторых, даже в конфликтах с
двумя участниками интересы сторон вовсе не обязаны быть противоположными; во
многих конфликтах такого рода случается так, что одна из ситуаций оказывается
предпочтительнее другой для обоих участников.
В-третьих, даже если любые две
ситуации сравниваются игроками по их предпочтительности противоположным образом,
различие разностей в оценках этой предпочтительности оставляет место для
соглашений, компромисов и коопераций.
Наконец, в-четвёртых,
содержательная острота конфликта не обязательно соответствует его формальной
антагонистичности. Например, при встрече двух боевых единиц воюющих сторон
(скажем, танков) обоюдное их стремление уничтожить друг друга не выражает антогонистичности
конфликта: в антогонистическом конфликте цели сторон оказываются строго противоположными,
и стремлению одной стороны уничтожить другую противоположным будет
стремление избежать уничтожения.
В качестве примера БАИ
рассмотрим:
1. Игры двух лиц с произвольной
суммой.
Бескоалиционные игры.
В конечной бескоалиционной игре
двух игроков (КБИДИ)каждый из них делает один ход – выбирает одну
стратегию из имеющегося у него конечного числа стратегий, и после этого он
получает свой выигрыш согласно определённым для каждого из них матрицами
выигрышей. Другими словами КБИДИ полностью определяется двумя матрицами
выигрышей для двух игроков. Поэтому такие игры называются биматричными. Пусть у игрока 1 имеется m стратегий, i =, у игрока 2 имеется n
стратегий, j =. Выигрыши игроков 1 и 2 соответственно задаются матрицами
А = , В =
Будем по-прежнему
считать полный набор вероятностей x = (x1, ..., xm) применения 1 игроком своих
чистых стратегий смешанной стратегией игрока 1, и у = (y1, ..., yn) –
смешанной стратегией игрока 2. тогда средние выигрыши игроков 1 и 2
соответственно равны
Ситуация
равновесия для биматричной игры составляет пару (x,y) таких
смешанных стратегий игроков 1 и 2, которые удовлетворяют неравенствам :
или
Для определения ситуаций
равновесия необходимо решить систему неравенств (1) и (2) ( и )
относительно неизвестных x = (x1, ..., xm) и у = (y1, ..., yn) при условиях
, , xi
³ 0 (i =), yj
³ 0 (j =).
Теорема (Нэша). Каждая биматричная игра имеет по крайней мере одну
ситуацию равновесия.
В качестве примера рассмотрим
случай, когда каждый игрок имеет две чистые стратегии. В этом случае матрицы A и B равны :
A = , B = .
Смешанные
стратегии для игроков 1 и 2 имеют вид :
(x, 1– x), (y, 1–
y) 0 £ x £ 1; 0 £ y £ 1,
а средние выигрыши
равны :
E1(A,x,y)
= xA = (x; 1- x)=
= (a11
a12 –
a21 + a22) xy
+ (a12 - a22) x + (a21 - a22) y + a22.
E2(B,x,y)
= xB = (x; 1- x)=
= (b11
- b12 - b21 + b22) xy + (b12 - b22) x + (b21 - b22) y + b22.
Условия и будут выглядеть
£ E1(A,x,y),
(x; 1- x) £ E2(B,x,y),
или
Преобразовав (3) и (4), получим
(1-
x) y + (1- x) £ 0
(a11
- a12 - a21 + a22) xy + (a12 - a22) x ³ 0
или
Т. о., множество всех приемлемых
стратегий для игрока 1 удовлетворяет условиям (5) и (6), 0
£ x £ 1;
0 £ y
£ 1. Чтобы найти x рассмотрим 3 случая :
1. Если x = 0, то (6) справедливо " y, а (5)
имеет вид :
a1y - a2
£ 0.
2. Если x = 1, то (5) справедливо " y, а (6)
имеет вид :
a1y - a2
³ 0.
3. Если 0 < x < 1, то (5) разделим на (1 - x), а (6) – на x и получим
Итак, множество К решений системы (5) –
(6) состоит из
1) всех ситуаций вида
(0; y), если a1y - a2 £ 0; 0 £
y £ 1;
2) всех ситуаций вида
(x; y),
если a1y - a2
= 0; 0 < x
< 1;
3) всех ситуаций вида
(1; y), если a1y - a2 ³ 0; 0 £ y £ 1.
Если a1 = a2 = 0, то решением является xÎ[0; 1], yÎ[0; 1], т. к. все неравенства
(7) –
(8) выполняются при всех x и y, т. е. множество приемлемых для игрока 1
ситуаций покрывает весь единичный квадрат.
Если a1 = 0, a2 ¹ 0, то выполняется либо (7), либо (8), и поэтому решением является либо x = 0, либо x=1 при 0 £
y £ 1 (приемлемой
стратегии в игре не существует).
Если a1 > 0, то из (7) получаем решение
x = 0; y £ := a,
Из (8) следует
ещё решение x = 1, y ³ a, из (9) следует ещё решение
0 < x
< 1, y = a.
Если a1 < 0, то решение следующее
:
x = 0, y ³ a;
x = 1, y £ a;
0 < x < 1, y
= a.
При этом
необходимо учитывать, что дополнительно должно быть
0 £
y £ 1.
Геометрически это выглядит
следующим образом :
y ¥ y ¥ y ¥
1 1 1
a1>0 a1>0
a1>0
a<0 a=0 1< a<1
(x, a)
0 1 x 0 1 x 0 1
x
– ¥ –
¥ –
¥
y ¥ y y
¥
¥
1 a1>0 1 a1>0 1 a1< 0
(x, 1) a=1 a >1 (x, a) 0< a<1
(0, b)
x x x
0 – ¥
1 0 – ¥
1 0 – ¥
1
Для игрока 2 исследования
аналогичны. Если ввести обозначения
b1 := b11
- b12 - b21 + b22
b2 := b22
-
то множество L приемлемых для него ситуаций
состоит из :
1)
всех ситуаций вида (x, 0), если b1x - b2
< 0; 0 £
x £ 1,
2)
всех ситуаций вида (x, y),
если b1x - b2
= 0; 0 £
x £ 1; 0 < y < 1,
3)
всех ситуаций вида (x, 1), если b1x - b2 > 0; 0 £
x £ 1.
Результаты следующие :
если b1 = b2 = 0, то решение 0 £
x £ 1; 0 £ y £ 1;
если b1 = 0; b2 ¹ 0, то решение либо y = 0, либо y = 1 при 0 £
x £ 1 (приемлемой
стратегии в игре не существует);
если b1 > 0, то решения следующие
:
y = 0, x < = b; y = 1, x > b; 0 < y
< 1; x = b;
если b1 < 0, то решения следующие
:
y = 0, x > b; y =
1, x < b; 0 < y < 1; x = b
При этом
необходимо учитывать, что 0 £ x £
1.
y y
1
1
(b,y) (b,y)
x x
0 1 0 1
b1 >
0 b1 < 0
0 < b < 1 0 < b < 1
Решением игры является
пересечение множеств K
и L, т.е. те значения x и y, которые
являются общими для множеств K
и L.
y y
1
1
x x
0 1 0 1
а)
б)
При этом
зигзаги K и L могут быть не
только одинаковой, но и противоположной направленности. В первом случае зигзаги
имеют одну точку пересечения, а во-втором – три. Средние выигрыши
при этом определяются по формулам (*), если в них подставить полученное
решение x и y (рис.а)). Очевидно a входит в смешанную стратегию игрока 2, хотя зависит
только от выигрышей 1 игрока; b входит в смешанную стратегию игрока 1, хотя зависит
только от выигрышей игрока 2. Сравнение этих результатов с результатами решения
матричных игр с нулевой суммой показывает, что a совпадает с оптимальной
стратегией игрока 1 в матричной игре с матрицей A, а b –
с оптимальной стратегией игрока 2 в матричной игре с матрицей B. Отсюда можно сделать вывод, что равновесная ситуация
направляет поведение игроков не только на максимизацию
своего выигрыша, сколько на минимизацию
выигрыша противника.
С другой стороны, естественно
также рассматривать подходящим поведение игроков в конечных бескоалиционных
играх, направленное на максимизацию своего выигрыша с учётом максимального
противодействия игрока, т.е. подходящей стратегией игрока 1 считать оптимальную
смешанную стратегию игрока 1 в матричной игре с матрицей A, а
подходящей стратегией игрока 2 считать оптимальную смешанную стратегию игрока 2
в матричной игре с матрицей B, если в ней
рассматривать решение с позиций максимизации выигрыша игрока 2, т.е. решать её,
как для игрока 1, с матрицей .
Пример1. Министерство
желает построить один из двух объектов на территории города. Городские власти могут
принять предложения министерства или отказать. Министерство –
игрок 1 –
имеет две стратегии: строить объект 1, строить объект 2. Город –
игрок 2 –
имеет две стратегии: принять предложение министерства или отказать. Свои
действия (стратегии) они применяют независимо друг от друга, и результаты
определяются прибылью (выигрышем) согласно следующим матрицам :
A = , B =
(например: если
игроки применяют свои первые стратегии, министерство решает строить 1 объект, а
городские власти разрешают его постройку, тогда город получает выигрыш 5 млн, а
министерство теряет 10 млн, и т.д.)
Решение. Для этой игры
имеем :
a1 = a11 - a12 - a21 + a22 = -10 - 2 - 1 - 1 = -14 < 0,
a2 = a22 - a12 = -1 - 2 = -3,
.
Так как a1 < 0, то множество решений
K имеет следующий вид :
(0, y) при ;
(x, ) при 0 £ x £ 1;
(1, y) при 0 £ y £ .
Для 2 игрока имеем :
b1 = b11 - b12 - b21 + b22 = 5 + 2 + 1 + 1 = 9 > 0,
b2 = b22 - b21 = 1 + 1 = 2,
.
y
1
Так
как b1 >
0, то множество решений L L
имеет следующий
вид :
K
(x; 0), при
0 £
x £;
(; y), при 0 £
y £ 1; 0
1 x
(x; 1), при £
x £ 1.
Точка пересечения
множеств L и K есть
точка C с координатами x = ; y = и является соответственно
приемлемыми стратегиями министерства и города.
При этом выигрыш соответственно
равен
E1(A,x,y)
= (x, 1-x)=
= =
E2(A,x,y)
= (x, 1-x)=
Замечание. Если решить эту
игру как матричные игры двух игроков с нулевой суммой, то для игры с матрицей A оптимальные смешанные для 1
игрока и цена игры получаются из решения уравнений
откуда
вероятность применения игроком 1 первой стратегии равна , цена игры – , что совпадает с E1,
вероятность применения игроком 2 первой стратегии ; для игры с матрицей B оптимальные смешанные стратегии и цена игры для игрока 2
определяются из системы :
Следовательно,
вероятность применения игроком 2 своей стратегии , а игроком 1, цена игры , что совпадает с E2.
Таким образом, если каждый из
игроков будет применять свои стратегии в этой игре, исходя только из матриц
своих выигрышей, то их оптимальные средние выигрыши совпадают с их выигрышами
при ситуации равновесия.
Глава 4. КООПЕРАТИВНЫЕ ИГРЫ
Кооперативные игры получаются в тех случаях, когда, в игре n игроков
разрешается образовывать определённые коалиции. Обозначим через N множество всех игроков, N={1,2,...,n}, а через K – любое его
подмножество. Пусть игроки из K
договариваются между собой о совместных действиях и, таким образом, образуют
одну коалицию. Очевидно, что число таких коалиций, состоящих из r игроков, равно числу сочетаний из n по r , то есть , а число всевозможных коалиций равно
= 2n –
1.
Из этой формулы видно, что число
всевозможных коалиций значительно растёт в зависимости от числа всех игроков в
данной игре. Для исследования этих игр необходимо учитывать все возможные
коалиции, и поэтому трудности исследований возрастают с ростом n. Образовав коалицию,
множество игроков K действует как один игрок против остальных игроков, и выигрыш
этой коалиции зависит от применяемых стратегий каждым из n игроков.
Функция u,
ставящая в соответствие каждой коалиции K наибольший, уверенно получаемый его
выигрыш u(K), называется характеристической функцией
игры. Так, например, для бескоалиционной игры n игроков u(K) может
получиться, когда игроки из множества K оптимально действуют
как один игрок против остальных N\K игроков, образующих другую коалицию
(второй игрок).
Характеристическая функция u называется простой, если она принимает
только два значения: 0 и 1. Если характеристическая функция u
простая, то коалиции K, для которых u(K)=1, называются выигрывающими, а коалиции K, для которых u(K) = 0, – проигрывающими.
Если в простой характеристической функции u
выигрывающими являются те и только те коалиции, которые содержат фиксированную
непустую коалицию R, то характеристическая функция u,
обозначаемая в этом случае через uR, называется простейшей.
Содержательно простые характеристические функции возникают,
например, в условиях голосования, когда коалиция является выигрывающей, если
она собирает более половины голосов (простое большинство) или не менее двух
третей голосов (квалифицированное большинство).
Более сложным является пример оценки результатов голосования
в Совете безопасности ООН, где выигрывающими коалициями являются все коалиции,
состоящие из всех пяти постоянных членов Совета плюс ещё хотя бы один непостоянный
член, и только они.
Простейшая характеристическая функция появляется, когда в
голосующем коллективе имеется некоторое “ядро”,
голосующее с соблюдением правила “вето”, а голоса остальных
участников оказываются несущественными.
Обозначим через uG характеристическую функцию
бескоалиционной игры. Эта функция обладает следующими свойствами :
1) персональность
uG(Æ)
= 0,
т.е. коалиция, не содержащая ни
одного игрока, ничего не выигрывает;
2)
супераддитивность
uG(KÈL) ³ uG(K) + uG(L), если
K, L Ì N, KÇL ¹ Æ,
т.е. общий выигрыш коалиции не
меньше суммарного выигрыша всех участников коалиции;
3)
дополнительность
uG(K) + u(N\K) = u(N)
т.е. для бескоалиционной игры с
постоянной суммой сумма выигрышей коалиции и остальных игроков должна равняться
общей сумме выигрышей всех игроков.
Распределение выигрышей (делёж) игроков должно удовлетворять
следующим естественным условиям: если обозначить через xi выигрыш i-го игрока, то, во-первых, должно удовлетворяться
условие индивидуальной рациональности
xi ³ u( i ), для i ÎN
т.е. любой игрок должен получить
выигрыш в коалиции не меньше, чем он получил бы, не участвуя в ней (в противном
случае он не будет участвовать в коалиции); во-вторых,
должно удовлетворяться условие коллективной
рациональности
= u(N)
т.е. сумма выигрышей игроков должна
соответствовать возможностям (если сумма выигрышей всех игроков меньше, чем u(N),
то игрокам незачем вступать в коалицию; если же потребовать, чтобы сумма
выигрышей была больше, чем u(N), то это значит, что игроки должны делить между собой сумму
большую, чем у них есть).
Таким образом, вектор x = (x1,
..., xn),
удовлетворяющий условиям индивидуальной и коллективной рациональности,
называется дележём в условиях
характеристической функции u.
Система {N, u}, состоящая из множества игроков,
характеристической функции над этим множеством и множеством дележей, удовлетворяющих
соотношениям (2) и (3) в условиях характеристической функции, называется классической кооперативной игрой.
Из этих определений непосредственно вытекает следующая
Теорема. Чтобы вектор x = (x1, ..., xn)
был дележём в классической кооперативной игре {N, u},
необходимо и
достаточно, чтобы
xi
= u(
i ) + ai, (iÎN)
причём
ai ³
0 (iÎN)
= u(N) –
В бескоалиционных играх исход формируется в результате
действий тех самых игроков, которые в этой ситуации получают свои выигрыши.
Исходом в кооперативной игре является делёж, возникающий не как следствие действия
игроков, а как результат их соглашений. Поэтому в кооперативных играх
сравниваются не ситуации, как это имеет место в бескоалиционных играх, а
дележи, и сравнение это носит более сложный характер.
Кооперативные игры считаются существенными, если для любых коалиций K и L выполняется
неравенство
u(K) + u(L) < u(KÈL),
т.е. в условии супераддитивности
выполняется строгое неравенство. Если же в условии супераддитивности выполняется
равенство
u(K) + u(L) = u(KÈL),
т.е. выполняется свойство
аддитивности, то такие игры называются несущественными.
Справедливы следующие свойства :
1) для того чтобы характеристическая функция была аддитивной
(кооперативная игра – несущественной), необходимо и достаточно
выполнение следующего равенства:
= u(N)
2) в несущественной игре имеется только один делёж
{u(1) , u(2) , ... , u(n)
};
3) в существенной игре с более чем одним
игроком множество дележей бесконечно
( u(1) + a1 , u(2) + a2 , ... , u(n)
+an
)
где
ai ³ 0 ( i Î N
) , u(N)
> 0
Кооперативная игра с множеством игроков N и
характеристической функцией u называется стратегически
эквивалентной игрой с тем же множеством игроков и характеристической
функцией u1
, если найдутся такие к > 0 и произвольные
вещественные Ci ( iÎN ),
что для любой коалиции К Ì N имеет место равенство:
u1(K) = k
u (K)
+
Смысл определения стратегической эквивалентности
кооперативных игр (с.э.к.и.) состоит в том что характеристические
функции с.э.к.и. отличаются только масштабом измерения
выигрышей k и начальным капиталом Ci .
Стратегическая эквивалентность кооперативных игр с характеристическими
функциями u
и u1
обозначается так u~u1. Часто вместо стратегической
эквивалентности кооперативных игр говорят о стратегической эквивалентности их характеристических
функций .
Справедливы следующие свойства для стратегических
эквивалентных игр:
1. Рефлексивность, т.е. каждая характеристическая функция
эквивалентна себе u~u.
2. Симметрия, т.е. если u~u1, то u1~u.
3. Транзитивность, т.е. если u~u1 и u1~u2, то u~u2.
Из свойств рефлексивности, симметрии и транзитивности вытекает, что множество всех характеристических
функций единственным образом распадается на попарно непересекающиеся классы, которые называются классами стратегической эквивалентности.
Отношение стратегической эквивалентности игр и их
характеристических функций переносится на отдельные дележи :
пусть u~u1 , т.е. выполняется (5), и x = (x1, ..., xn) – дележи в
условиях характерис- тической функции u; рассмотрим вектор x1 = (, ..., ) , где = k xi+Ci ; для него выполняется
= k xi + Ci ³ k u( i ) + Сi = u1( i );
т.е.
выполняется условие индивидуальной рациональности, и
== k+= k u(N) += u1(N)
т.е.
выполняется условие коллективной рациональности. Поэтому вектор является
дележом в условиях u1. Говорят, что делёж x1 соответствует дележу x при стратегической
эквивалентности u~u1.
Кооперативная игра называется нулевой,
если все значения её характеристической функции равны нулю. Содержательное значение нулевой игры
состоит в том, что в
ней игроки не имеют никакой заинтересованности .
Всякая несущественная игра стратегически эквивалентна
нулевой .
Определение. Кооперативная игра с характеристической функцией u
имеет (0,1)-редуцированную форму, если выполняются
соотношения :
u( i ) = 0 ( i Î N ),
u(N)
= 1.
Теорема. Каждая существенная
кооперативная игра стратегически эквивалентна одной и только одной игре в (0,1)-редуцированной форме.
Сформулированная теорема показывает, что мы можем выбрать
игру в (0,1)-редуцированной форме для представления любого класса
эквивалентности игр. Удобство этого выбора состоит в том, что в такой форме
значение u(K) непосредственно демонстрирует нам силу коалиции S (т.е. ту дополнительную прибыль,
которую получают члены коалиции, образовав её), а все дележи являются
вероятностными векторами.
В игре в (0,1)-редуцированной форме дележём является любой
вектор x = (x1, ..., xn),
для которого
xi ³
0 (i Î N) = 1.
ПЕРЕЧИСЛЕНИЕ ХАРАКТЕРИСТИЧЕСКИХ ФУНКЦИЙ
С
МАЛЫМ ЧИСЛОМ ИГРОКОВ.
Как было сказано ранее, для каждого множества игроков N существует единственный класс стратегически эквивалентных
несущественных игр с множеством игроков N. Таким образом,
остаётся рассмотреть классы существенных кооперативных игр.
Рассмотрим сначала классы игр в (0,1)-редуцированной форме
для случая игр с нулевой суммой.
1. Игры 2-х игроков.
Всякая кооперативная игра двух игроков с нулевой суммой является
несущественной.
Доказательство. Предположим, что имеется существенная
кооперативная игра двух игроков с характеристической функцией u,
Тогда она должна быть стратегически эквивалентна некоторой игре в
(0,1)-редуцированной форме с характеристической функцией u1, что означает следующее :
u1(1) = 0, u1(2) = 0, u1(1,2) = 1
По свойству дополнительности должно
u1(2) = u1(1,2) – u1(1) = 1 –
0 =1,
что противоречит (*). А это значит,
что наше предположение о существенности кооперативной игры двух игроков с
нулевой суммой неверно.
Итак, класс
кооперативных игр двух игроков с нулевой суммой ограничивается несущественными
играми.
2. Игры 3-х игроков.
Пусть u
характеристическая функция существенной игры в (0,1)-редуцированной
форме, тогда
u(1)
= u(2) = u(3)
= 0, u(1,2,3) = 1.
По свойству дополнительности имеем :
u(1,2) = u(1,2,3) – u(3) = 1– 0 =1,
u(1,3) = u(1,2,3) – u(2) = 1– 0 =1,
u(2,3) = u(1,2,3) – u(1) = 1– 0 =1,
и, таким образом, характеристическая
функция полностью определена.
Итак, имеется два класса
кооперативных игр трёх игроков с нулевой суммой: класс
существенных и класс несущественных игр.
3. Игры 4-х игроков.
Рассмотрим все классы стратегической эквивалентности таких игр.
Прежде всего имеется класс несущественных игр в (0,1)-редуцированной форме
определим характеристическую функцию u такой игры
u(1)
= u(2) = u(3)
= u(4)
= 0
u(1,2,3,4) = 1.
Исходя из свойства дополнительности, получаем
u(1,2,3) = u(1,2,3,4) – u(4) = 1– 0 =1;
u(1,2,4) = u(1,2,3,4) – u(3) = 1– 0 =1;
u(1,3,4) = u(1,2,3,4) – u(2) = 1– 0 =1;
u(2,3,4) = u(1,2,3,4) – u(1) = 1– 0 =1.
Теперь необходимо определить значения характеристической
функции на коалициях двух игроков. Всего таких коалиций шесть
(1,2), (1,3), (1,4), (2,3), (2,4), (3,4).
Характеристическая функция на этих коалициях согласно
свойству дополнительности удовлетворяет только следующим соотношениям :
u(1,4) = 1– u(2,3),
u(1,3) = 1– u(2,4),
u(1,2) = 1– u(3,4).
Так как значений неизвестных шесть, а соотношений только три, то значения из шести могут
быть выбрана произвольно.
Обозначим эти произвольные значения через x1, x2, x3,
т.е.
u(1,4) = x1 , u(2,4) = x2 , u(3,4) = x3 ,
Тогда
u(2,3) = 1–
x1
, u(1,3) = 1– x2 ,
u(1,2) = 1– x3 .
Кроме того должно быть
0 £ x1, x2, x3 £
1 ,
так как значение характеристической
функции на коалиции из двух игроков не может быть меньше, чем значение характеристической
функции для одного из этих игроков (равное нулю для одного игрока), и не может быть больше, чем значение
характеристической функции для коалиции из трёх игроков (равное 1 для трех
игроков). Геометрически
(x1, x2, x3) можно
изобразить как точку единичного куба, т.е. каждому классу стратегической эквивалентности игр четырёх
игроков будет соответствовать точка единичного куба.
Итак,
множество классов стратегической эквивалентности существенных игр четырёх игроков
бесконечно и зависит от трёх произвольных параметров.
4. Игры, состоящие из более чем 4-х игроков, имеют большее разнообразие классов стратегической
эквивалентности существенных игр.
Так, размерность
множества классов игр n игроков равна , т.е.
имеется произвольных параметров.
Рассмотрим теперь кооперативные игры
без условия постоянства суммы.
1. Для игр 2-х
игроков множество N={1,2}, условия редуцированности дают
u(Æ)
= u(1)
= u(2)
= u(1,2)
= 1.
Таким образом, существенные
кооперативные игры двух игроков с ненулевой суммой составляют один класс стратегической
эквивалентности.
2. Для игр 3-х
игроков множество N={1,2,3}, условия редуцированности дают
u(Æ)
= u(1)
= u(2)
= u(3)
= 0; u(1,2,3) = 1.
Значения характеристической функции
на множествах коалиций двух игроков произвольные (здесь нет условия дополнительности)
u(1,2)
= C3, u(1,3) = C2, u(2,3)
= C1,
но удовлетворяющие условию
0 £
C1, C2, C3 £ 1.
Таким образом, классы стратегической
эквивалентности общих кооперативных игр трёх игроков могут быть поставлены в
соответствие точкам трёхмерного единичного куба подобно тому, как это
получилось для игр 4-х игроков с нулевой суммой.
Для игр более 3-х игроков с ненулевой суммой рассмотрения
аналогичны.
Для исследования игр большое значение имеет возможность
учёта предпочтения дележей, который осуществляется с помощью понятия доминирования.
Определение.
Пусть имеется два дележа x = (x1, ..., xn) и
y = (y1, ..., yn) в кооперативной игре G = {N,u}, и
KÌ N – некоторая коалиция. Тогда делёж x доминирует y
по коалиции K, если
1) £
u(K) (свойство эффективности доминирующего платежа)
2) xi > yi
для всех iÎK (свойство предпочтительности)
Свойство эффективности означает, что сравниваемый коалицией
делёж x должен быть,
реализуемым этой коалицией: сумма выигрышей каждого из членов коалиции не
должна превосходить уверенно получаемое ею количество. В противном случае
коалиция, встретившись с дележём, дающим ей столько, сколько она самостоятельно
не в состоянии добиться, должна согласиться на него и не заниматься его
сравнением с какими либо другими дележами.
Условие предпочтительности отражает необходимость “единодушия”
в предпочтении со стороны коалиции: если хотя бы одно из неравенств xi > yi будет нарушено, т.е. если
хотя бы для одного из членов коалиции K выигрыш в условиях дележа y будет не меньшим, чем в условиях дележа x, то можно будет
говорить о предпочтении дележа x дележу y не всей коалицией K, а только
теми её членами, для которых соответствующее неравенство xi > yi
соблюдается.
Соотношение доминирования
x над y по коалиции K
обозначается через
.
Определение.
Делёж x доминирует
y, если существует такая коалиция K, для
которой делёж x доминирует
y. Это доминирование обозначается так:
x > y.
Наличие доминирования x > y означает, что в
множестве игроков N найдётся коалиция, для
которой x предпочтительнее y. Отношение доминирования не
обладает полностью свойствами рефлексивности, симметрии, транзитивности,
возможна только частичная симметрия и транзитивность. Соотношение
доминирования возможно не по всякой коалиции. Так, невозможно доминирование
по коалиции, состоящей из одного игрока или из всех игроков.
Справедлива следующая теорема.
Теорема. Если u и u1
две стратегически эквивалентные характеристические функции, причём дележам x и y соответствуют дележи и , то из x > y следует >.
Очевидно, все явления, описываемые в терминах доминирования
дележей, относятся к классам стратегической эквивалентности, поэтому достаточно
изучать эти классы (а не сами игры) для существенных игр по их
(0,1)-редуцированной форме, а для несущественных игр – по нулевым
играм.
В любой несущественной игре имеется только один делёж,
поэтому никаких доминирований в ней нет.
Рассмотрим доминирование дележей в существенной игре на
следующем примере.
Пример. Пусть имеется (0,1)-редуцированная форма
существенной игры трёх игроков с постоянной суммой (равной 1). Поскольку
доминирование невозможно ни по одной из одноэлементных коалиций 1,2,3, а также
по коалиции, состоящей из всех трёх игроков, то доминирование возможно только
по одной из двухэлементных коалиций {1,2}, {1,3}, {2,3}.
Для наглядности доминирования дележей введём понятие
бароцентрических координат. Осями координат служат три оси x1, x2,
x3, составляющие
между собой одинаковые углы 60о, ось x3 находится на расстоянии
единицы от точки пересечения осей x1
и x2 (рис.1), координаты
точки x = (x1, x2, x3)
соответственно расстояния от этой точки до осей x1, x2,
x3, взятые с такими знаками, как указано на рис.1.
(Например, для точки x на рис.1. x1 <
0, x2 > 0,
x3 > 0).
В барицентрической системе координат всегда выполняется
равенство
x1 + x2 + x3 = 1.
В плоскости всегда имеется точка с
координатами x1, x2, x3,
удовлетворяющими равенству (6). По этому бароцентрическая система координат
автоматически удовлетворяет одному из условий, определяющих исход игры трёх игроков.
С другой стороны, поскольку игра в (0, 1)-редуцированной форме, то точка x должна находиться в заштрихованном треугольнике (см. рис.
2). Дележи x1, x2, x3
должны удовлетворять неравенствам
x1 + x2 £ u(1,
2), x1 +
x3 £ u(1,
3), x2 + x3 £
u(2, 3).
Очевидно, из условия
дополнительности, что
x1 + x2 = 1 - x3 £ 1 = u(1,
2), x1 + x3 £ 1, x2 + x3 £
1.
Делёж x = (x1,
x2, x3) доминирует дележ y = (y1,
y2, y3)
по коалиции {1, 2}, если x1 > y1, x2 > y2;
по коалиции {1, 3}, если x1 > y1, x3 > y3;
по коалиции {2, 3}, если x2 > y2, x3 > y3,
т.е. если делёж y находится в одном из заштрихованных
параллелограммов (за исключением трёх граничных прямых, проходящих через точку x) на рис. 3, то делёж
x доминирует
делёж y, а всякая
точка находящаяся в не заштрихованных треугольниках, является предпочтительнее
исхода x.
x3
= - 1
x2 = - 1
x = (x1, x2,
x3)
x3 = 1 - C3
x1 = 0
x1
= 1 - C1 x2
= 1 - C2
Рис.3
Рис. 4
Таким образом, если x и y
-
два исхода и ни один из них не предпочтительнее другого, то соответствующие
точки лежат на прямой, параллельной одной из координатных осей.
Пример. Пусть имеется (0, 1)-редуцированная игра трёх
игроков с ненулевой суммой.
Рассмотрим сначала условия доминирования дележа x = (x1, x2, x3) над дележём y = (y1, y2, y3) по коалиции {1, 2}. В этом случае имеем :
Поскольку может быть, что C3 <
1 , то первое из условий (7) нельзя отбросить, как это делает- ся в играх с
постоянной суммой. Это значит что, x должна быть не ниже
прямой
x1 + x2 = C3.
Или, учитывая (6), последнее
уравнение принимает вид
x3 = 1 + C3 .
Таким образом, если делёж x таков, что
x1 ³ 1 - C1,
x2 ³ 1 - C2, x3
³ 1 - C3,
то имеется три параллелограмма,
заштрихованных на рис. 4, находясь в которых, точки x доминируют y.
Если в (8) одно из неравенств, например, третье не имеет
места, то есть только 2 парал- лелограмма, заштрихованных на рис. 5, находясь в
некоторых точках x доминирует
y.
x1
= 1 - C1 x2 = 1 - C2
x2 = 1 - C2
x1 = 1 - C1
x3 = 1 - C3
x
Рис. 5 Рис.
6
Из рассмотренного примера видно, что возможно много
вариантов, которые возникают при изучении вопросов, связанных с доминированием
дележей в кооперативных играх. С ростом числа игроков чрезвычайно быстро растёт
количество таких вариантов. В связи с этим возникает необходимость выделения вполне устойчивых дележей, т.е.
таких дележей, которые не доминируются никакими другими дележами. Множество
вполне устойчивых дележей в кооперативной игре называется с-ядром
этой игры.
Теорема. Для того
чтобы делёж x принадлежал с-ядру кооперативной игры с
характеристической функцией u,
необходимо и достаточно, чтобы для любой коалиции K выполнялось
неравенство
Поскольку неравенства (9) линейны относительно x, то из последней
теоремы следует, что с-ядро в любой
кооперативной игре является выпуклым многогранником.
К особенностям кооперативных игр относительно существования с-ядра относятся :
1) в
несущественной игре с-ядро существует
и состоит из единственного дележа этой игры;
2) во всякой
существенной игре с постоянной суммой с-ядро пусто.
Для общей игры трёх игроков в (0; 1)-редуцированной форме
имеем следующее (рис. 7).
Её характеристическая функция имеет вид :
u(Æ)
= u(1)
= u(2)
= u(3)
= 0;
u(1,
2, 3) = 1,
u(1,
2) = С3; u(1, 3) = С2; u(2,
3) = С1,
где 0 £ С1, С2, С3
£
1.
На основании последней теоремы для принадлежности
дележа x с-ядру
необходимо и достаточно выполнение неравенств
x1 + x2
³ C3, x1 +
x3 ³ C2, x2 + x3 ³ C1
или, используя равенство x1 + x2 + x3 = 1, получим
x3 £
1 -
C3, x2
£ 1 - C2,
x3 £ 1 - C1.
3
1 2
Рис.
7
Это означает, что точка x должна лежать ближе к i-й вершине основного треугольника (см.
рис. 7), чем прямая
xi = 1 - Сi (i = 1,2,3)
Из неравенства (10) путём
суммирования получим
x1 + x2 + x3 £
3 -
(С1 + С2 + С3)
или, учитывая, что x1 + x2 + x3 = 1, получим
С1
+ С2 + С3 £ 2.
Неравенство (12) является
необходимым условием существования непустого с-ядра. С другой стороны, если (12) выполняется, то можно взять
такие неотрицательные e1, e2,
e3,
чтобы
,
и положить
xi = 1 - Ci - ei (i = )
Такие значения xi и удовлетворяют неравенствам (10), т.е. такой
делёж x = (x1, x2,
x3) принад- лежит с-ядру.
Геометрически непустое с-ядро
является заштрихованным треугольником (рис. 7), со сто- ронами, выраженными
уравнениями (11)
3
3
1
2 1
2
Рис.
8
Рис. 9
при условии, что выполняется
соотношение
x1
+ x2
+ x3
= 1,
и решения любой пары уравнений (11)
являются неотрицательными. Так, например, рассмот- рим систему
x1
= 1 -
С1, x2 = 1 - С2.
Поскольку 0 £
С1 £ 1, 0 £
С2 £ 1, то x1, x2 ³
0. Отсюда получаем
x3
= 1 -
x1
-
x2
= 1 -
(1 -
С1) - (1 - С2)
= С1 + С2 - 1.
Для того, чтобы было x3
³
0, необходимо чтобы
С1
+ С2 -
1 ³
0
или
С1 + С2 ³
1.
В этом случае с-ядро представлено на рис.7 в виде заштрихованного треугольника
внутри основного треугольника. Аналогично рассматриваются остальные возможные
варианты сочета- ний неравенств. Например, если С1 + С2 < 1, то с-ядро имеет
вид заштрихованного четырёх- угольника внутри основного треугольника (рис.8).
Вообще многогранник, представляющий с‑ядро,
образуется как выпуклый многогранник пересечением прямых (11) и строк основного
треугольника. Если, например, выполняются неравенства
С1 + С2 < 1; С2
+ С3 <
1; С1
+ С3 <
1,
то с-ядро представляется в виде шестигранника, заштрихованного на
рис.9.
Очевидно, в решение кооперативной игры должны входить
дележи, лучшие с определён- ной точки зрения. Так, дележи, входящие в с-ядро, являются устойчивыми в несколько
пассив- ном смысле, т.е. при этих обстоятельствах нет оснований отклоняться от
такого дележа. Одна- ко, найти делёж, который не только не доминировался бы
какими-либо другими дележами, но сам доминировал бы любой другой делёж, не
удаётся. Поэтому решение отыскивают на пути расширения класса дележей . И это
расширение состоит в том, что решением игры должен быть не один делёж, а
некоторое их множество.
Дж. фон Нейман
и О. Моргенштерн предложили
потребовать от множества дележей, которое принимается в качестве решения
кооперативной игры следующие два свойства: внут- реннюю устойчивость, состоящую
в том, чтобы дележи из решений нельзя было противопоста- вить друг другу, и
внешнюю устойчивость, состоящую в возможности каждому отклонению от решения
противопоставлять некоторый делёж, принадлежащий решению. В результате мы приходим
к следующему определению.
Определение. Решением
по Нейману-Моргенштерну (Н-М-решением) кооперативной игры называется множество
R дележей в нём, обладающее следующими свойствами :
1) внутренняя устойчивость: никакие два дележа из R не доминируют друг друга;
2) внешняя устойчивость: каков бы ни был делёж S не принадлежащий R, найдётся делёж r, принадлежащий R, который доминировал бы
S.
Содержательная интерпретация Н-М-решения состоит в том, что
любые две нормы пове- дения, соответствующие Н-М-решению, не могут быть
противопоставлены друг другу; каково бы ни было отклонение от допустимых
поведений, найдётся такая коалиция, которая будет стремиться к восстановлению
нормы.
Теорема. Если в
кооперативной игре существует с-ядро C и Н-М-решение R, то CÌ R.
Свойства
Н-М-решений.
Н-М-решение кооперативной игры не может состоять только из
одного дележа, т.к. в этом случае характеристическая функция игры
несущественная.
Недостатки
Н-М-решения.
1. Известны примеры кооперативных
игр, которые не имеют Н-М-решений. Более того, в настоящее время не известно
каких-либо критериев, позволяющих судить о наличии у кооперативных игр
Н-М-решений. Тем самым заложенный в Н-М-решении принцип оптимальности не является
универсально реализуемым, и область его реализуемости пока остаётся неопределён-
ной.
2. Кооперативные игры, если не имеют
Н-М-решения, то, как правило, более одного. Поэтому принцип оптимальности,
приводящий к Н-М-решению, не является полным: он, вообще говоря, не в состоянии
указать игрокам единственной системы норм распределения выигрыша.
3. Решения существенных
кооперативных игр состоит более, чем из одного дележа. Таким образом, даже
выбор какого-либо конкретного Н-М-решения ещё не определяет выигрыша каждого из
игроков.
4. Понятие Н-М-решения отражает
только в очень малой степени черты справедливости.
Перечисленные недостатки отражают положение дел в
действительности: большинство экономических и социальных проблем допускает
множественные решения, и эти решения не всегда поддаются непосредственному
сравнению по их предпочтительности.
Перечисленные недостатки Н-М-решения коалиционных игр
способствуют поискам новых подходов. Одним из таких подходов является подход
Шепли, суть которого в том, что он строиться на основании аксиом, отражающих
справедливость дележей.
Определение. Носителем
игры с характеристической функцией u называется такая
коали-ция T, что
u(S) = u(S Ç T)
для любой коалиции S.
Смысл носителя T состоит в том, что
любой игрок, не принадлежащий T, является нейтральным,
он не может ничего внести в коалицию и ему ничего не следует выделять из общих
средств.
Определение. Пусть u –
характеристическая функция кооперативной игры n игроков, p – любая перестановка
множества N игроков. Через pu
обозначим характеристическую функцию
и та- кой игры, что для коалиции
S = {i1, i2,
..., iS} будет
u ({p( i1),
p( i2), ..., p( iS)}) = u(S).
Содержательный смысл функции pu состоит в том, что если в
игре с характеристической функцией u поменять местами игроков согласно перестановке p, то
получим игру с характерис- тической функцией pu.
Аксиомы Шепли.
1о.
Аксиома эффективности. Если S – любой носитель игры с
характеристической функцией u, то
= u(S)
Иными словами, “справедливость
требует”,
что при разделении общего выигрыша носителя игры ничего не выделять на долю
посторонних, не принадлежащих этому носителю, равно как и ничего не взимать с
них.
2о. Аксиома симметрии. Для любой
перестановки p и iÎN должно выполняться
(pu) = ji
(u),
т.е. игроки,
одинаково входящие в игру, должны “по справедливости” получать
одинаковые выигрыши.
3о.
Аксиома агрегации. Если есть
две игры с характеристическими функциями u¢ и u¢¢,
то
j i
(u¢ + u¢¢) = j i (u¢) + j i (u¢¢),
т.е. ради “справедливости”
необходимо считать, что при участии игроков в двух играх их выигрыши в
отдельных играх должны складываться.
Определение. Вектором
цен (вектором Шепли) игры с характеристической функцией u
называется n-мерный
вектор
j
(u)
= (j1(u), j2(u),
..., jn(u)),
удовлетворяющий аксиомам Шепли.
Существование вектора Шепли вытекает из следующей теоремы
Теорема.
Существует единственная функция j, определённая для всех игр и удовлетворяющая аксиомам
Шепли.
Определение.
Характеристическая функция wS(T),
определённая для любой коалиции S, называется простейшей, если
wS(T)
=
Содержательно простейшая
характеристическая функция описывает такое положение дел, при котором множество
игроков S выигрывает единицу тогда и только
тогда, когда оно содержит некоторую основную минимальную выигрывающую коалицию S.
Можно доказать, что компоненты вектора Шепли в явном виде
запишутся следующим образом
где t – число элементов в T.
Вектор Шепли содержательно можно интерпретировать следующим
образом: предельная величина, которую вносит i-й игрок в
коалицию T, выражается как
u(T) - u(T \{i})
и считается выигрышем i-го игрока; gi (T) – это вероятность того, что i-й игрок вступит в коалицию T \{i}; ji (u) – средний выигрыш i-го игрока
в такой схеме интерпретации. В том случае, когда u – простейшая,
Следовательно
,
где суммирование по T распространяется на все такие выигрывающие коалиции T, что коалиция T \{i}не
является выигрывающей.
Пример. Рассматривается корпорация из четырёх
акционеров, имеющих акции соответственно в следующих размерах
a1 = 10, a2 = 20, a3 = 30, a4 = 40.
Любое решение утверждается
акционерами, имеющими в сумме большинство акций. Это решение считается выигрышем,
равным 1. Поэтому данная ситуация может рассматриваться как простая игра
четырёх игроков, в которой выигрывающими коалициями являются следующие:
{2; 4}, {3; 4},
{1; 2; 3}, {1; 2; 4}, {2; 3; 4}, {1; 3; 4},
{1; 2; 3; 4}.
Найдём вектор Шепли для этой игры.
При нахождении j1 необходимо учитывать, что имеется только
одна коалиция T={1;2;3}, которая выигрывает, а коалиция T \{1} = {2;
3} не выигрывает. В коалиции T имеется t = 3 игрока, поэтому
.
Далее, определяем все выигрывающие
коалиции, но не выигрывающие без 2-го игрока: {2; 4}, {1; 2; 3}, {2; 3; 4}. Поэтому
.
Аналогично получаем, что , .
В результате получаем, что вектор Шепли равен . При этом, если считать, что вес голоса акционера
пропорционален количеству имеющихся у него акций, то получим следующий вектор
голосования
,
который, очевидно, отличается от
вектора Шепли.
Анализ игры показывает, что компоненты 2-го и 3-го игроков
равны, хотя третий игрок имеет больше акций. Это получается вследствие того,
что возможности образования коалиций у 2-го и 3-го игрока одинаковые. Для 1-го
и 4-го игрока ситуация естественная, отвечающая силе их капитала.
Если в игре отсутствует седловая точка то цена игры удовлетворяет условию и нижняя. Стратегия выбираемая игроком определенным а не случайным образом называется. Оптимальное решение в игре двух лиц с нулевой суммой всегда является. Математическое ожидание выигрыша первого игрока в платёжной матрице. В игре без седловой точки каждая минимаксная стратегия игрока В. Пусть количество стратегий игрока количество стратегий игрока. Что означает термин принятие решений Воронеж Россия Воронеже. Игры с чистыми и смешанными стратегиями Кооперативные игры. Определение оптимальной стратегии с матрицей платежей. Основная теорема теории матричных игр доказательство. Общий порядок решения игры доминирующие стратегии. Оптимальную смешанную стратегию для двух игроков. Теорема о минимаксе и смысл смешанных стратегий. Элементы теории матричных игр готовый реферат. Решение матричной игры Москва Россия Москве.
|
