Теория игр

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

Вариант 2

Найти все максиминные и минимаксные стратегии игроков, нижнюю и верхнюю цены игры. Указать все ситуации равновесия и решение игры.

Принцип построения стратегии x, основанный на максимизации минимального выигрыша,-- принципом максимина, а выбираемая в соответствии с этим принципом стратегия x -- максиминной стратегией игрока 1.

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

При заданных условиях

Верхняя цена игры равна нижней цене игры и равна -2.

В антагонистической игре Г = (X, Y, K) ситуация (x? , y?) называется ситуацией равновесия или седловой точкой, если K(x, y?) ? K(x? , y?), K(x?, y) ? K(x ? , y?) для всех x ? X и y ? Y. Т.е. в седловой точке элемент матрицы ai ?j ? является одновременно минимумом в своей строке и максимумом в своем столбце.

В заданной задаче ситуация (x2 , y2) является ситуацией равновесия. Решение игры Г=(2,2,-2). Найти ситуацию равновесия и решение игры в смешанных стратегиях графоаналитическим методом.

Игра решается графически, поскольку игрок имеет только две стратегии. При этом игра рассматривается с позиции игрока .

Рис. 1 - Решение матричной игры графическим методом

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

Например, если игрок придерживается своей 1-й стратегии, то выигрыш, который получит игрок , может быть равен -1, если он будет придерживаться своей 1-й стратегии, или может быть равен 2, если игрок В будет придерживаться своей 2-й стратегии. Откладываем эти значения по осям и , соответственно, и соединяем их отрезком прямой, который подписываем . Аналогично строим отрезки прямых, соответствующих остальным двум стратегиям игрока В. Ломаная линия является нижней границей возможного выигрыша игрока . На этой границе находим точку с максимальной ординатой. Видно, что это точка образованная пересечением линий и , которые отвечают стратегиям и игрока . Это означает, что стратегии и являются активными стратегиями игрока , других стратегий он не применяет. Ординатой точки является цена игры, а отрезки и , на которые проекция точки разделяет единичный отрезок оси абсцисс, определяют вероятности и , с которыми игрок будет применять стратегии и , соответственно. Целью графического решения является определение активных стратегий каждого из игроков, далее задача решается аналитически.

В активных стратегиях матрица имеет вид:



.

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

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



Решая методом Крамера получаем

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

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

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

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

ТЕОРИЯ.

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

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

.

Оптимальная стратегия X* обеспечивает первому игроку средний выигрыш, не меньший, чем цена игры V, при любой стратегии второго игрока и выигрыш, равный цене игры V, при оптимальной стратегии второго игрока.

Если первый игрок применяет смешанную стратегию X* против любой чистой стратегии второго игрока, то он получает средний выигрыш, или математическое ожидание выигрыша V(j)=a1jx1+…amjxm, j= 1, 2,…, п (т. е. элементы j-гo столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий первого игрока и результаты складываются).

Для оптимальной стратегии X* все средние выигрыши не меньше цены игры V, поэтому получаем систему неравенств:

a11x1+a21x2+…+am1xmV,

a12x1+a22x2+…+am2xmV,

…………………….. (1)

a1n x1+a2n x2+…+amn xmV.

Каждое из неравенств можно разделить на число V > 0. Введем новые переменные

zi=. (2)

Тогда система (1) примет вид:

 (3)

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

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

 (4)

обращалась в минимум. Это задача линейного программирования. Решая задачу (3) ? (4), получаем оптимальные стратегии .

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

 (5)

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

Если обозначить

 (6)



то получим систему неравенств:

 (7)

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

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

 (8)

Решение задачи линейного программирования (7) ? (8) определяет оптимальную стратегию . При этом цена игры

. (9)

Задачи линейного программирования (3) ? (4) и (7) ? (8) являются взаимно двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.

Решение.



Любая игра сводится к задаче линейного программирования. Для первого игрока ограничения и целевая функция выглядят следующим образом:

где 

Для второго игрока задача линейного программирования является двойственной к предыдущей и имеет вид:

где 

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

Добавим новые переменные и приведем систему к каноническому виду:

Базис составляют переменные 5 6 7

Находим начальное опорное решение. Для этого свободные переменные приравниваем к нулю 1= 2=3=4= 0.

Получили опорное решение N1 = (0,0,0,0,1,1,1) с единичным базисом Б1 =(А5,А6,А7).

F(N1)=0

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

стратегия игрок игра программирование

Дk = CбNk -- ck

Где:

Cб = (с1, с2, ... , сm) -- вектор коэффициентов целевой функции при базисных переменных

Nk = (1k, 2k, ... , mk) -- вектор разложения соответствующего вектора Ак по базису опорного решения

Ск -- коэффициент целевой функции при переменной к.

Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения запишем в симплексной таблице:



			1	1	1	1	0	0	0
Б	Сб	А0	А1	А2	А3	А4	А5	А6	А7
5	0	1	3	4	6	4	1	0	0	1/3
6	0	1	4	4	4	5	0	1	0	1/4
7	0	1	2	3	6	8	0	0	1	1/2
Дk	0	-1	-1	-1	-1	0	0	0

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

В последней строке таблицы с оценками Дk в столбце "А0" записываются значения целевой функции на опорном решении Z (N1).

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

Так как имеется три одинаковых отрицательных оценки, выберем вектор А1. Наименьшее значение - во второй строке. Значит вводим в базис Х2 переменную 1 вместо 6.

Выполняем преобразования Жордана с элементом х21= 4, получаем второе опорное решение N2 = (0.25; 0; 0; 0;0,25;0;0,5) з базисом Б2 = (А5, А1, А7) (таблица 2)

стратегия игрок программирование

			1	1	1	1	0	0	0
Б	Сб	А0	А1	А2	А3	А4	А5	А6	А7
5	0	1/4	0	1	3	1/4	1	- 3/4	0
1	1	1/4	1	1	1	1 1/4	0	1/4	0
7	0	1/2	0	1	4	5 1/2	0	- 1/2	1
Дk	1/4	0	0	0	1/4	0	1/4	0

Все оценки положительные, то есть решение оптимальное.

Полученное оптимальное решение имеет вид:

Перейдем к исходным переменным:

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

Решение задачи для первого игрока найдем с помощью теорем двойственности.

Первая теорема двойственности

Для взаимодвойственных ЗЛП имеет место один из взаимоисключающих случаев.

1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: max f(X) = min g(Y).

Значит и

Вторая теорема двойственности (теорема о дополняющей нежесткости)

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

 

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

если  

если 

если  

если 

Проверим, какие из ограничений задачи второго игрока превращаются в равенства, а какие в неравенства:

Значит

Подставляем в систему ограничений задачи первого игрока



Полученное оптимальное решение имеет вид:

Перейдем к исходным переменным:

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

В данной задаче такое решение было очевидно еще при анализе матрицы

Имеется точка равновесия (2;1).

Рассматривается корпоративная игра с тремя игроками. Известны значения характеристической функции, определяющие соответственно выигрыши первого, второго и третьего игроков, когда каждый из них играет в одиночку, не кооперируясь ни с кем из других игроков: V(1)=1500; V(2)=1200; V(3)=1000; а также выигрыши, которые они могут обеспечить себе, действуя попарно: V(1,2)=3000; V(1,3)=2700; V(2,3)=2400; и общий выигрыш, который могут обеспечить себе игроки, образуя максимально большую коалицию, состоящую из трех игроков V(1,2,3)=4400. Требуется:

Проверить выполнение условий супераддитивности и существенности для данной кооперативной игры;

Выразить значение характеристической функции в 0-1 редуцированной форме;

Проверить условия, определяющие непустоту С-ядра и найти один из вариантов решения игры (дележ Х);

Определить выигрыши каждого из игроков в случае их объединения на основе использования вектора Шепли. Проверить принадлежность вектора Шепли С-ядру.

Решение.

Пусть N = {1,..., n} -- множество всех игроков. Любое непустое подмножество S N называется коалицией.

Свойство супераддитивности. (Определение) Характеристической функцией игры n лиц будем называть вещественную функцию х, определенную на коалициях S N, при этом для любых непересекающихся коалиций Т, S (Т С N, S С N) выполняется неравенство

v{T) +v{S) < u(TS), v()=0

В данной задаче

V(1)=1500; V(2)=1200; V(3)=1000; V(1,2)=3000; V(1,3)=2700; V(2,3)=2400; V(1,2,3)=4400.



Также

Значит свойство супераддитивности выполняется.

Теорема. Каждая существенная кооперативная игра эквивалентна некоторой игре в (0-1) -- редуцированной форме.

Если н -- характеристическая функция произвольной существенной игры (Н,н), то

есть (0 - 1) - нормализация, соответствующая функции н.



Получили такую редуцированную функцию

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

Определение. Множество недоминируемых дележей кооперативной игры (N, н)называется ее С-ядром.

Теорема. Для того чтобы дележ а принадлежал С-ядру, необходимо и достаточно выполнение для всех S N неравенств

С-ядро не пусто тогда и только тогда, когда для всех |S| = 1,..., n имеет место неравенство



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

В нашей задаче средняя доля каждого игрока в коалиции Н равна

Условия непустоты С-ядра выполняются.

Чтобы дележ а принадлежал С-ядру, необходимо и достаточно выполнение следующих неравенств:

Например a=(3/7; 3/7; 1/7) или a=(6/14; 5/14; 3/14)

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

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

Аксиомы Шепли.

1. Если S -- любой носитель игры (Н,н), то

2. Для любой подстановки р и i N

3. Если (N,u) и (Н,v) -- две любые кооперативные игры, то

Определение. Пусть ц -- функция, ставящая в соответствие согласно аксиомам 1--3 каждой игре (N, н) вектор ц[н]. Тогда ц[v] называется вектором значений или вектором Шепли игры (Н,н).

Для 0-1 редуцированной формы игры с тремя игроками вектор Шепли рассчитывается следующим образом:

Ф1(v) = 1/6 (2 - 2C1 + C2 + C3)

Ф2(v) = 1/6 (2 - 2C2 + C1 + C3)

Ф3(v) = 1/6 (2 - 2C3 + C1 + C2)

где где C1 = v(2,3); C2 = v(1,3); C3 = v(1,2).

Соответственно



Проверим принадлежность вектора Шепли С-ядру.

Чтобы дележ ф принадлежал С-ядру, необходимо и достаточно выполнение следующих неравенств:

Все условия выполняются, значит дележ ф принадлежит ядру.

В нередуцированной форме



Получили

Чтобы дележ ф принадлежал С-ядру, необходимо и достаточно выполнение следующих неравенств:

Все условия выполняются, значит дележ ф принадлежит ядру.

V(1)=1500; V(2)=1200; V(3)=1000; V(1,2)=3000; V(1,3)=2700; V(2,3)=2400; V(1,2,3)=4400.

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