Игры 2 лиц с нулевой суммой

 

Тема 3. Игры 2 лиц  с нулевой суммой

1. Решить  игру с матрицей (тип 2хn). В ответе  указать цену игры и вероятности  применения стратегий, т.е. v, p, q.

 

8.

7

8

2

-1

4

 

-6

-8

-1

7

-4


Пусть — произвольная смешанная стратегия игрока 1 в этой игре. Найдем функции :

и построим их графики.


 

Кривая №1

Кривая №2

Кривая №3

Кривая №4

Кривая №5

                   

0

-6

0

-8

0

-1

0

7

0

-4

1

7

1

8

1

2

1

-1

1

4


Экстремальная точка L на нижней огибающей является пересечением прямых, соответствующих 3–ой и 4–ой стратегиям игрока 2, поэтому рассматриваем игру 2´2:

 

Задача имеет решение:

цена игры при этом равна

.

 

По формулам находим:

Из полученных результатов  формируем решение исходной игры:

 

.

 

2. Решить игру  с матрицей (тип mх2). В ответе  указать цену игры и вероятности применения стратегий, т.е. v, p, q.

 

8.

2

-7

 

-7

2

 

-8

7

 

0

-6

 

4

-9


чтобы учесть интересы игрока 2, нужно исходить из соотношения (теорема):

,

где q — первая компонента смешанной стратегии игрока 2, а .

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

 Найдем функции :

и построим их графики.


Экстремальная точка M на верхней огибающей является пересечением прямых, соответствующих 3–ой и 5–ой стратегиям игрока 1, поэтому рассматриваем игру 2´2:

Задача имеет решение:

цена игры при этом равна

.

 

По формулам находим:

Из полученных результатов  формируем решение исходной игры:

 

.

Тема 4. Некооперативные  игры 2 лиц с ненулевой суммой

 Найти точки равновесия в биматричной игре (A – матрица выигрышей игрока 1, B – матрица выигрышей игрока 2)

 

8.

A=

5

3

B=

1

7

   

4

11

  

9

3


 

А/В

1

2

1

(5,1)

(3,7)

2

(4,9)

(11,3)


 

1) (5,1) 1-1

Рассуждает игрок №1: 5>3 → остается в этой точке,

Рассуждает игрок №2: 1<7 → не остается в этой точке,

2) (3,7) 1-2

Рассуждает игрок №1: 3<11 → не остается в этой точке,

Рассуждает игрок №2: 7>3 → остается в этой точке,

3) (11,3) 2-2

Рассуждает игрок №1: 11>4 → остается в этой точке,

Рассуждает игрок №2: 3<9 → не остается в этой точке,

4) (4,9) 2-1

Рассуждает игрок №1: 4<5 → не остается в этой точке,

Рассуждает игрок №2: 9>1 → остается в этой точке.

Ответ: нет точек равновесия.

Тема 6. Теория игр n лиц в нормальной форме

Имеется три предприятия (I, II, III); которые выпускают продукцию #1, продукцию #2 и продукцию #3.Следующая  таблица представляет общие выпуски продукции по каждому предприятию. Продукция продается комплектами (1ед. #1, 1ед. #2 и 1ед. #3). Спрос неограничен. Комплект стоит 1 тыс. руб. Требуется решить вопрос о целесообразности объединения предприятий, найти максимальный возможный доход объединения, справедливый дележ – вектор Шепли. В левом верхнем углу указан номер варианта.

 

 

8

#1

#2

#3

I

800

500

0

II

700

0

800

III

0

1100

800


Решение. Подсчитаем выигрыши коалиций, т.е. доход, который они  получат при объединении. Для 3 игроков  имеем 23=8 коалиций.

Так как каждое из предприятий не выпускает одного из типов продукции, то без объединения никто ничего не зарабатывает. v(Æ)=v(I)=v(II)=v(III)=0.

При объединении I и II предприятий, их общий выпуск равен 

 

 

#1

#2

#3

I

800

500

0

II

700

0

800

итого

1500

500

800


Они могут сформировать 500 комплектов и выручить за них 500 тыс. руб.

При объединении I и III предприятий, их общий выпуск равен 

 

 

#1

#2

#3

I

800

500

0

III

0

1100

800

итого

800

1600

800


 

Они могут сформировать 800 комплектов и выручить за них 800 тыс. руб.

При объединении II и III предприятий, их общий выпуск равен 

 

 

#1

#2

#3

II

700

0

800

III

0

1100

800

итого

700

1100

1600


 

Они могут сформировать 700 комплектов и выручить за них 700 тыс. руб.

При объединении всех трех предприятий, их суммарный выпуск равен

 

 

#1

#2

#3

I

800

500

0

II

700

0

800

III

0

1100

800

итого

1500

1600

1600


 

Они могут сформировать 1500 комплектов и выручить за них 1500 тыс. руб.

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

 

S

v(S)

  

S

v(S)

Æ

0

  

{I, II}

500

{I}

0

  

{I, III}

800

{II}

0

  

{II, III}

700

{III}

0

  

{I, II, III}

1500


 

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

 

Порядок входа 

в коалицию

  

Сколько получает

коалиция

  

Сколько получает

каждый участник

первый

второй

третий

  

один

двое

трое

  

I

II

III

I

II

III

  

0

500

1500

  

0

500

1000

I

III

II

  

0

800

1500

  

0

700

800

II

I

III

  

0

500

1500

  

500

0

1000

II

III

I

  

0

700

1500

  

800

0

700

III

I

II

  

0

800

1500

  

800

700

0

III

II

I

  

0

700

1500

  

800

700

0

Итого

      

2900

2600

3500


 

Например, на 5 строке указан порядок входа III, I, II.

Сначала приходит участник III. Так как v(III)=0, то он получает 0.

Следующим приходит участник I. Так как v(I,III)=800, то он получает 800-0=800.

Последним приходит участник II. Так  как v(I,II,III)=1500, то ему достается 1500-800=700. Аналогично заполнены все остальные  строки.

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

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

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

.

Тема 8. Приложения теории игр n лиц

 Располагая информацией о количестве голосов, которыми располагают партии, и о размере выигрывающей коалиции, найти веса партий при голосовании.

 

№ варианта

1

2

3

4

Размер выигрывающей коалиции

8

34,3%

27,6%

23,1%

15,1%

64%


 

Решение. Используем схему решения игры, аналогичную расчету вектора Шепли. Представим данную игру в виде таблицы. Подсчитав выигрыши коалиций, причем для коалиции S имеем v(S)=1, если |S|>64%. В противном случае v(S)=0. Для 4 участников имеем 24=16 коалиций.

 

S

v(S)

  

S

v(S)

  

S

v(S)

  

S

v(S)

Æ

0

  

{4}

0

  

{2, 3}

0

  

{1, 2, 4}

1

{1}

0

  

{1, 2}

0

  

{2, 4}

0

  

{1, 3, 4}

1

{2}

0

  

{1, 3}

0

  

{3, 4}

0

  

{2, 3, 4}

1

{3}

0

  

{1, 4}

0

  

{1, 2, 3}

1

  

{1, 2, 3, 4}

1


 

Расстановка 1 и 0 осуществляется так. Например, для 1 и 2 партий сумма  их голосов составляет 34,3%+27,6%=61,9%. Это  меньше порогового значения 64%, поэтому  ставим 0.

Теперь составим таблицу  всевозможных порядков образования максимальной коалиции, раздавая 1 тому участнику, с чьим приходом эта коалиция становится выигрывающей. Всего существует 4!=24 порядка формирования коалиций.

 

 

 

 

вход

  

Накопленные голоса (%)

  

выигрыш

Перв.

Втор.

Трет.

Четв.

  

первый

двое

трое

все

  

1

2

3

4

1

2

3

4

  

34,30%

61,90%

85,00%

100

  

0

0

1

0

1

2

4

3

  

34,30%

61,90%

77,00%

100

  

0

0

0

1

1

3

2

4

  

34,30%

57,40%

85,00%

100

  

0

1

0

0

1

3

4

2

  

34,30%

57,40%

72,50%

100

  

0

0

0

1

1

4

2

3

  

34,30%

49,40%

77,00%

100

  

0

1

0

0

1

4

3

2

  

34,30%

49,40%

72,50%

100

  

0

0

1

0

2

1

3

4

  

27,60%

61,90%

85,00%

100

  

0

0

1

0

2

1

4

3

  

27,60%

61,90%

77,00%

100

  

0

0

0

1

2

3

1

4

  

27,60%

50,70%

85,00%

100

  

1

0

0

0

2

3

4

1

  

27,60%

50,70%

65,80%

100

  

0

0

0

1

2

4

1

3

  

27,60%

42,70%

77,00%

100

  

1

0

0

0

2

4

3

1

  

27,60%

42,70%

65,80%

100

  

0

0

1

0

3

1

2

4

  

23,10%

57,40%

85,00%

100

  

0

1

0

0

3

1

4

2

  

23,10%

57,40%

72,50%

100

  

0

0

0

1

3

2

1

4

  

23,10%

50,70%

85,00%

100

  

1

0

0

0

3

2

4

1

  

23,10%

50,70%

65,80%

100

  

0

0

0

1

3

4

1

2

  

23,10%

38,20%

72,50%

100

  

1

0

0

0

3

4

2

1

  

23,10%

38,20%

65,80%

100

  

0

1

0

0

4

1

2

3

  

15,10%

49,40%

77,00%

100

  

0

1

0

0

4

1

3

2

  

15,10%

49,40%

72,50%

100

  

0

0

1

0

4

2

1

3

  

15,10%

42,70%

77,00%

100

  

1

0

0

0

4

2

3

1

  

15,10%

42,70%

65,80%

100

  

0

0

1

0

4

3

1

2

  

15,10%

38,20%

72,50%

100

  

1

0

0

0

4

3

2

1

  

15,10%

38,20%

65,80%

100

  

0

1

0

0

итого

      

6

6

6

6


 

1 получает тот игрок,  с приходом которого суммарный  вес коалиции превышает 64%. Например, на первой строке – это игрок  №3, который вошел третьим, и  с его появлением вес коалиции  стал равен 85%, до него вес был равен 61,9%, что меньше 64%. В заключение поделим полученные выигрыши на 24 и получим вектор весов партий .

Тема 12. Равновесия Нэша

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

 

8.

A=

5

3

B=

1

7

   

4

11

  

9

3


 

А/В

1

2

1

(5,1)

(3,7)

2

(4,9)

(11,3)


Изобразим эту информацию на графике, откладывая выигрыши игрока А по оси Ox, выигрыши игрока Б– по оси Oy.

 


Точки A, B, C, D соответствуют чистым стратегиям. Отрезки, их соединяющие – смешанным стратегиям.

Точки линии СD (C(4,9); D(11,3) составляют Парето-оптимальное множество. Во-первых, они доминируют все остальные точки области, во-вторых, между собой они несравнимы.

Уравнение линии CD:

(х-х1)/(х2-х1) = (y-y1)/(y2-y1)

(x-4)/(11-4) = (y-9)/(3-9)

(x-4)/7 = (y-9)/(-6)

6x+7y=87

 

6n1 + 7n2 = 87

 

Точка Нэша N(n1,n2). Она является решением оптимизационной задачи , где (m1,m2) – уровни дохода, которые игроки могут обеспечить себе, не вступая в коалицию. В данном примере

1) m1= 4, m2 = 3, имеем задачу:

Найти максимум выражения (n1-4)(n2-3), при условии 6n1 + 7n2 = 87  (уравнение линии AC). Можно перейти к одной переменной , подставить в функцию и получить ƒ(n1)=(n1-4)((87-6n2)/7-3)=(30n1-2n1-144)/7, решить уравнение ƒʹ( n1)=(30-4n1)/7 , откуда n1=7,5; n2=6 .

2) аналогично со второй  точкой (11,3) получим n1=7,5; n2=6.


Игры 2 лиц с нулевой суммой 📙 Контрольная → 🆔 34252

Игры 2 лиц с нулевой суммой 📙 Контрольная → 🆔 34252

Игры 2 лиц с нулевой суммой