Элементы теории игр

Элементы теории игр

Основные определения

Как наука, теория игр возникла совсем недавно, в 20-х годах 20-го века, когда была доказана теорема о максимине. Шахматы - первоначальная модель конфликтной ситуации.

Предмет теории игр

ТЕОРИЯ ИГР - это математическая модель принятия решений в конфликтных ситуациях.

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

Методикой формализации конфликтной ситуации занимаются специалисты в области конкретной ситуации.

Рекомендуемые материалы

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

Конфликт и его формальная модель

КОНФЛИКТОМ называется всякое явление, относительно которого можно сказать, кто и как в этом явлении участвует, каковы его возможные исходы, кто в этих исходах заинтересован и в чем состоит эта заинтересованность.

УЧАСТНИКИ КОНФЛИКТА - суть элементы которого абстрактного множества, которое называется множеством игроков. Подмножество этого множества, которое является действующими сторонами/игроками, началами/называется коалицией действия. R_d

Поведение коалиции действия определяет протекание конфликта.

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

Выбор каждой коалицией действия своей стратегии называется исходом конфликта.

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

Ситуации составляют некоторое множество S, являющееся подмножеством множества всех стратегий коалиций действия, т.е. образуют декартово произведение множества стратегий.

Заинтересованные в исходе конфликта стороны называются коалициями интересов - суть подмножества множества игроков-R4.

Каждой коалиции интересов на множестве S задается бинарноре отношение предпочтения.

Коалиция

Ситуация     и  ситуация  ,       ,

/ситуация  предпочтительнее коалиции интересов , чем ситуация S**/

Игра - формальная модель конфликта, т.е. система

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

тогда бинарное отношение предпочтения определяется так.

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

Бинарные отношения предпочтения будут иметь вид:

,  , ;     ,   если

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

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

Классификация игр представлена на рис. 1

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

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

В зависимости от числи игроков: игра с одним игроком и многими игроками.

В зависимости от характера взаимоотношений игроков игры делятся на кооперативные / когда игроки образуют коалиции с целью применения согласованной стратегии, это политические игры - блоки НАТО, СЕАТО/ и некооперативные.

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

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

По информации о множествах стратегий и функциях выигрыша игры делятся на

игры с полной и неполной информацией.

Биматричная игра - игра с двумя игроками, каждый игрок имеет свою функцию выигрыша.

Игра на единичном квадрате, функция платежа принимает значение

0, ± I.

Результат выбора стратегии есть позиция.

К дифференциальным играм относятся игры на убегание.

ФОРМЫ ОПИСАНИЯ ИГРЫ.

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

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

мн-во

2. Нормальная форма.

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

!!! Основное допущение в теории игр – это допущение о разумном противнике.

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

Антагонистические игры

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

Пример №1: Игра в орлянку ( подбрасывание монет).

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

Составим матрицу игры:

Матрица выигрыша 1-го игрока:  Н1=

Матрица выигрыша 2-го игрока:  Н1=

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

Выбор каждого из игроков своей стратегии называется ситуацией в игре. Каждая ситуация в игре  заканчивается исходом:

4 ситуации-4 исхода.

Пусть S1-множество стратегий 1-го игрока

S2-множество стратегий 2-го игрока

S-множество ситуаций в игре

S=S1  S2

S1=(г,р)     , S2=(г,р)   ,тогда       S={(г, г)(г, р)(р, г)(р, р)}

Ситуация равновесия

Матричная игра-игра ,в которой функция выигрыша есть матрица Н с элементами :

             h₁₁   h₁₂   ^… h_1n

H=        h₂₁     h₂₂  ^…  h_2n

                   ^{………………………}

             h_m1   h_m2 ^…  h_mn        ,

то есть, это матрица Н=[h_ij]_{m x n} , стратегиями 1-го игрока являются строки матрицы Н ,а стратегиями 2-го-столбцы матрицы Н.

Если 1-ый игрок выберет своей стратегией строку i ,а 2-ой игрок-стратегией столбец j ,то элемент ,полученный на их пересечении  h_ij в матрице Н будит выигрышем 1-го игрока ,а выигрыш 2-го игрока определяется из условия Н1=-Н2.

Игрок 1: S1={1,2,3,…,m}

Игрок 2: S2={1,2,3,…,n}

S=S1 X S2; где 

Ситуация в игре определяется: s=(s1, s2), , 

Ситуация  s^*=(s1^*, s2) называется приемлимой для игрока 1 , если для всех других его стратегий из множества  S выполняется следующее неравенство:  H(s^*)   s1), , то есть когда стратегия S1 заменена любой другой стратегией.

Аналогичная ситуация для 2-го игрока:

s^**=(s1, s2^*), когда   H(s^**)     s2), ,

Ситуация, приемлимая для обоих игроков, называется равновесной ,то есть  H(s^*)H(s), 

Теорема о ситуации равновесия для матричных игр

Пусть (i^*; j^*) –ситуация равновесия в матричной игре с матрицей

Н = [ h_ij ]_mxn . Тогда для нее справедливо:

H(i, j^*)H(i^*, j^*) H(i^*, j), i, j            (1)

Док-во:

Из определения ситуации равновесия имеем:

H1(i^*, j^*) H1(i, j^*), i                               (2)

H2(i^*, j^*) H2(i^*, j), j                               (3)

H2= - H1                                                     (4)

Тогда              - H1(i^*, j^*) - H1(i^*, j), j   *(-1)

H1(i^*, j^*)H1(i^*, j), j     (5)

Объединим (2) и (5) по общей части:

H1(i, j^*) H1(i^*, j^*) H1(i^*, j), i ,j        (6)

Т. к. H = H1  => H1(i, j^*) H1(i^*, j^*) H1(i^*, j), i ,j       (1)

Замечание :решить игру-значит найти все ситуации равновесия и значение функции выигрыша Н в этой ситуации.

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

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

1-ый игрок максимизирует выигрыш

2-ой игрок минимизирует проигрыш

1-й игрок рассуждает следующим образом:

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

2-й игрок рассуждает следующим образом:

Так как противник разумный и стремится максимизировать свой выигрыш, то он выбирает такую стратегиюi, чтобы получить max h_ij, но второй игрок выберет i тогда стратегия j минимизирует его проигрыш, т. е. h_ij

Ситуация (i^*, j^*) удовлетворяет обоим условиям, т. е.

h_{ij =} h_ij        (3)

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

Пример 2

H =

Т.к. в матрице Н нет отрицательных элементов , то 1-ый игрок всегда выигрывает.

Если выражение состоит из нахождения нескольких экстремумов, то нахождение общего экстремума начинается с взятия внутреннего экстремума.

H =   

h_{ij =}{a1, a2,a2} = 4 = a

H =  

 h_{ij =}{7,4,9} = 4 =b

Т. е .   (i^*, j^*) = (2, 2)

h(i^*, j^*) =  4

Пример 3

H=

h_ij = -1 = a

 h_ij = 1 = b

Т.к. ab, то игра не имеет решения в чистых стратегиях , тогда:

a - нижняя цена игры

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

Т.к. a<b , тогда как распределится b-a между игроками ? В этом случае переходят к новой игре , которая строится на основе исходной и которая называется смешанным расширением исходной игры.

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

Матричные игры – с полной информацией

На результат игры  влияет своё поведение и поведение противника.Разность b-a  распределяется случайным образом  и матричная игра из вполне определённой игры с полной информацией уже будет состоять из нескольких ходов.Тогда стратегиями игроков будут смешанные стратегии

x – смешанная стратегия 1-го игрока , x = (х1,х2,…,х_m), где x_i – вероятность выбора 1-ым игроком  своей  i-ой  чистой стратегии(строки  i)

x_i0, i =1,2,…,n       (1)

=1         (2)

y - смешанная стратегия 2-го игрока, y = (y1,y2,…,y_n), y_j0             (3)

=1         (4)

Стратегия игроков:  x = (x1,x2)                                          x = (x1,x2,x3)

dim S_m=m-1 ;                 dim S_n= n-1 ,

xÎS_m                                    yÎS_n

Значение игры:

Ситуации в смешанном расширении матрицы игры – пары (x,y), xÎS_m, yÎS_n

(x,y)= S_m´S_n

Понятие средневероятностного – математическое ожидание.

Т.о. мат. ожидание выигрыша в матричной игре определяется по правилу средневероятностного:=H(x,y),xÎS_m,yÎS_n         (5)

Смешанное расширение матричной игры – это антогонистическая игра Г^s , которая определяется системой , состоящей из множества стратегий 1 и 2-го игрока и множеством выигрыша , т.е.

Г^s =                       (6)

Ситуация равновесия  смешанной игры

H(i, j^*)H(i^*, j^*) H(i^*, j), i, j            (7)

H(x, y^*)H(x^*, y^*) H(x^*, y),  xÎS_m  ,  yÎS_n                 (8)

Замечание: Выигрыш игроков своей чистой стратегии  является частным случаем смешанной стратегии , например :

(i^*, j^*) = (2, 2)

x^*=(0,1,0)

y^*=(0,1,0)

Основная теорема теории матричных игр

Т. Любая матричная игра с матрицей  выигрыша Н имеет всегда решение , которое является общим значением maxmin , т.е.

H(x,y)=  H(x,y)=V(H)         (9)

H(x,y)= =XHY^T

Решение игр размерностью  2´2

H=

XHY^T=(x,1-x)

=0

=0

Из этих условий выводятся следующие формулы:

Х^*=

Y^*=

V(H)=

Пример 1

Предприятие выпускает два вида продукции А и В при этом спрос на продукцию имеет 2 состояния Д1 и Д2 , а прибыль , получаемая предприятием задается таблицей:

Определить  стратегию выпуска продукции предприятием.

Н=

       3  3

         3

Чистая стратегия : h_{ij =} h_ij

3¹0 =>игра не имеет решения в чистых стратегиях, тогда она имеет решение в смешанной стратегии , т.е.:

ХНУ^т=  ХНУ^т

X^*== ½;      Y^*== ½;        V(H)== 3/2;

тогда решение игры имеет вид:

х^*=(1/2;1/2) , y^*=(1/2;1/2) , V(H)=3/2

Получили : предприятие должно выпускать  50% первой и 50% второй продукции , тогда  спрос будет находится в  состоянии Д1 с вероятностью ½  и в состоянии Д2 с вероятностью ½ .

Пример 2    (решение примера 1 с другой матрицей)

Н=

       2  3

         2

h_ij-прибыль  предприятия при условии выпуска продукции типа i  и состояние спроса  j .

2=2 => решении в чистой стратегии есть.

Следовательно , предприятию выгодно выпускать  продукцию типа А , тогда спрос будет находится в состоянии Д1 и прибыль будет равна 2 единицам.

Решение игр размерностью 2´n

Матрица игры  , размерностью 2´n имеет следующий вид:

Н=

Пусть 1-ый игрок применяет свою чистую стратегию х=(х;1-х) ,тогда 2-ой игрок выбирает чистую стратегию j

Выигрыш в такой игре определяется :

ХН_j=(x;1-x)=h_1jx+h_2j-h_2jx=(h_1j-h_2j)x+h_2j

Геометрическая интерпритация будет иметь вид :

Пример 1

Н=

        1    0,9    1

              0,9

0,9¹0,5=> игра не имеет решения в чистых стратегиях.

xH_j=V(H)

 -это нижняя огибающая графика

- это верхняя точка этой огибающей

Эта стратегия образована стратегиями 1 и 3 , т.е.

H_r =

Х^*===5/11

Y^*===5/11

V(H)= ==8/11

X^*=(5/11;6/11)  ;    Y^*=(5/11;0;6/11)

Проверка:

X^*HY^*T=V(H)

(5/11;6/11)=(2+6/11;8,9/11;8/11) =40/121+48/121=8/11

Решение игр размерностью m´2

Матрица игры размерностью m´2 имеет вид:

H=

Чистая стратегия игрока 1: у =(у,1-у), а стратегия игрока 2: i . Тогда выигрыш игры:

Н_iY^T==h_i1y+h_i2-h_i2y=(h_i1-h_i2)y+h_i2

Пример 1

H=

H_iY^T=V(H)

-верхняя огибающая графика

-нижняя точка огибающей

Точку М образуют стратегии 1 и 3, тогда

Н_r=

Х^*===1/2       X^*=(1/2;0;1/2;0)

Y^*===1/2    Y^*=(1/2;1/2)

V(H)= ==2,5       V(H)=2,5

Проверка:    Х^*НУ^*Т=V(H)

(1/2;0;1/2;0) =(5/2;5/2) =5/2+5/2=2,5

Упрощение игр

Из определения ситуации равновесия =>что некоторые стратегии игроки никогда не будут применять , т.о. вводится понятие доминирования .

Доминирование в чистых стратегиях

Ситуация равновесия в чистых стратегиях определялась :

H1(i, j^*) H1(i^*, j^*) H1(i^*, j), i ,j           (1)

Опр.1    Стратегия  i^¢ доминирует стратегию i^¢¢  (или говорят стратегия i^¢¢

доминируется стратегией i^¢) если для любой чистой стратегии игрока  2

выполняется неравенство:

h_i^¢_j ³ h_i^¢¢_j   ,j           (2)

Опр.2       Стратегия j^¢  доминирует стратегию j^¢¢ если для любой чистой

стратегии игрока 1 выполняется неравенство:

h_ij^¢ h_ij^¢¢   ,i          (3)

Замечание: Если в соотношениях (2) и (3)  имеют место строгие неравенства ,

то говорят о строгом доминировании .

Пример 1

H=

Тогда  H_r= , а такие игры решаются просто.

Доминирование в смешанном расширении матричной игры

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

XHY^*T£ X^*H Y^*T£ X^* HY^T                  (4)

XH_j£ X^*H Y^*T£ H_iY^T   , i ,j ,xÎS_m,yÎS_n         (5)

Опр.3    Смешанная стратегия игрока х¢ доминирует его мешанную стратегию

х² если выполняется следующее неравенство:

х¢H_j³ х² H_j        ,j       (6)

Опр.4     Смешанная стратегия игрока 2  у^¢ доминирует его смешанную

стратегию у^²  если выполняется следующее неравенство:

HiY^¢T£ HiY^¢¢T      ,j         (7)

Замечание: если игра не имеет решения в чистых стратегиях, то её надо

попытаться упростить с помощью доминирования (см. пример 1).

Решение игр размерностью m´n

Матрица игры размерностью m´n имеет вид:

H=

Решение матричной игры с сведением её к задаче линейного программирования(ЗЛП)

Необходимым условием сведения матричной игры к ЗЛП является условие неотрицательности элементов. Если в матрице Н содержатся отрицательные элементы, то прибавление числа  t=[maxïh_ij<0ï+1] получим игру с матрицей  H_r , которая будет стратегически эквивалентна исходной игре (она будет иметь такую же ситуацию равновесия и такое же значение игры).

Пусть V_x=XH_j        ,j  ,xÎS_m               (1)

V_x£XH_j                    (2)

V_x£V(H)              (3)

Если     V_x=V(H)              (4) , то стратегия х , при которой достигается это равенство будет оптимальной стратегией игрока 1 ,т.е.

V_x=V(H)         (5)

Рассмотрим =*Х         (6)

Следовательно , х=*V_x         (7)

Подставим выражение  (7) в выражение  (2), получим:

V_x £ *V_x* H_j        =>      * H_j ³ 1         (8)

Из равенства (6) следует: т.к. х-стратегия 1-го игрока, то

=1

Если   *I   ,где  I={1,1,…,1} ,то получим

*I =             (9)

то есть    *I = *х*I = 1

Из (6) следует ,что   >0  , т.к. >0

Т. о .  мы  сформулировали следующую ЗЛП для 1-го игрока:

Задача А: Стратегия     будет оптимальной если она определяется из решения

следующей задачи:

*I

R=

Аналогично можно сформулировать ЗЛП для 2-го игрока:

Обозначим  через  V_y = H_i*Y^T    , i ,yÎS_n         (10)

V_y ³ H_i * Y^T (11)

V_y  ³ V(H)               (12)

Если   V_y  ³ V(H)               (13)  => стратегия у , при которой достигается это равенство, будет оптимальной стратегией игрока 2 .

Рассмотрим =*Y       , yÎS_n         (14)

Отсюда      Y=V_y*          (15)

Подставив (15) в (11) получим :

V_y  ³ H_i*V_y*^T      =>  H_i*^T £1        (16)

Из (15)  =>    ³0    (17)        т. к. У³0    ,V_y>0

Умножим  (14) на J={1,1,…,1} , получим      *J^T = *Y*J^T    ,т. е.

* J^T =

Т.о мы сформулировали следующую ЗЛП для 2-го игрока:

Задача В:

* J^T

Q=

Получили, что ЗЛП(В) и ЗЛП(А) взаимнодвойственны.

Замечание 1:   Любая матричная игра, в которой все элементы  H_ij больше 0

сводится к ЗЛП и решается с помощью симплекс-метода.

Замечание 2:    Любая исходная  ЗЛП и двойственная к ней  могут быть сведены

к игре.

Пример:

H=

Вместе с этой лекцией читают "3 Взаимодействие органов исполнительной власти РФ ее и субъектов".

Введём в рассмотрение:         =(;;)

=(;;)

Сформулируем ЗЛП для 1-го игрока:f₀()==

R=

Сформулируем ЗЛП для 2-го игрока:g₀()==

Q=