Файл: Теория_игр_УП_ЭК_ЭлРесурс.pdf

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 31.07.2021

Просмотров: 705

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
background image

 

11

 

 

В

0

 

В

1

 

В

2

 

В

3

 

В

4

 

А

0

 1  -1 -1 -1 -1 

А

1

 1  1  -1 -1 -1 

А

2

 -1 1  1 -1 -1 

А

3

 -1 -1 1  1 -1 

А

4

 -1 -1 -1  1  1 

А

5

 -1 -1 -1 -1  1 

Здесь

 

А

i

 – 

стратегия

 

фирмы

 

А

заключающаяся

 

в

 

выделении

 

условных

 

денежных

 

единиц

 

на

 

защиту

 

первого

 

рынка

В

j

 – 

стратегия

 

фирмы

 

В

заключающаяся

 

в

 

выделении

 

условных

 

денежных

 

единиц

 

на

 

завоевание

 

первого

 

рынка

Если

 

бы

 

на

 

защиту

 

или

 

завоевание

 

рынков

 

фирмы

 

могли

 

выделить

 

любое

 

количество

 

средств

 

из

 

имеющихся

то

 

игра

 

стала

 

бы

 

бесконечной

 

ТЕСТЫ

 

(

В

 – 

Верно

Н

 – 

Неверно

1. 

Всякая

 

конфликтная

 

ситуация

 

является

 

антагонистической

2. 

Всякая

 

антагонистическая

 

ситуация

 

является

 

конфликтной

3. 

Цель

 

теории

 

игр

 – 

выработка

 

рекомендаций

 

по

 

разумному

 

поведению

 

участников

 

конфликта

4. 

Недостатком

 

теории

 

игр

 

является

 

предположение

 

о

 

полной

 

разумности

 

противников

5. 

В

 

теории

 

игр

 

предполагается

что

 

не

 

все

 

возможные

 

стратегии

 

противника

 

известны

6. 

Теория

 

игр

 

включает

 

элементы

 

риска

неизбежно

 

сопровождающие

 

разумные

 

решения

 

в

 

реальных

 

конфликтах

7. 

В

 

теории

 

игр

 

нахождение

 

оптимальной

 

стратегии

 

осуществляется

 

по

 

многим

 

критериям

8. 

Стратегические

 

игры

 

состоят

 

только

 

из

 

личных

 

ходов

9. 

В

 

парной

 

игре

 

число

 

стратегий

 

каждого

 

участника

 

равно

 

двум

10. 

Игры

в

 

которых

 

действия

 

игроков

 

направлены

 

на

 

максимизацию

 

выигрышей

 

коалиций

 

без

 

последующего

 

их

 

разделения

 

между

 

игроками

называются

 

коалиционными

11. 

Исходом

 

кооперативной

 

игры

 

является

 

дележ

 

выигрыша

 

коалиции

который

 

возникает

 

не

 

как

 

следствие

 

тех

 

или

 

иных

 

действий

 

игроков

а

 

как

 

результат

 

их

 

наперед

 

определенных

 

соглашений

12. 

По

 

виду

 

описания

 

игры

 

делятся

 

на

 

игры

 

с

 

полной

 

информацией

 

или

 

игры

 

с

 

неполной

 

информацией

13. 

Конечная

 

множественная

 

игра

 

с

 

нулевой

 

суммой

 

называется

 

матричной

14. 

Конечная

 

парная

 

игра

 

с

 

нулевой

 

суммой

 

называется

 

биматричной

 

игрой

(

Ответы

1-

Н

; 2-

В

; 3-

В

; 4-

В

; 5-

Н

; 6-

Н

; 7-

Н

; 8-

Н

; 9-

Н

; 10-

В

; 11-

В

; 12-

Н

; 13-

Н

; 14-

Н

). 


background image

 

12

2. 

МАТРИЧНЫЕ

 

ИГРЫ

 

2.1. 

Описание

 

матричной

 

игры

 

Наиболее

 

разработанной

 

в

 

теории

 

игр

 

является

 

конечная

 

парная

 

игра

 

с

 

нулевой

 

суммой

  (

антагонистическая

 

игра

 

двух

 

лиц

 

или

 

двух

 

коалиций

), 

называемая

 

матричной

 

игрой

Рассмотрим

 

такую

 

игру

 

G

в

 

которой

 

участвуют

 

два

 

игрока

 

А

 

и

 

В

имеющие

 

антагонистические

 

интересы

выигрыш

 

одного

 

игрока

 

равен

 

проигрышу

 

второго

Так

 

как

 

выигрыш

 

игрока

 

А

 

равен

 

выигрышу

 

игрока

 

В

 

с

 

обратным

 

знаком

можем

 

интересоваться

 

только

 

выигрышем

 

а

 

игрока

 

А

Естественно

игрок

 

А

 

хочет

 

максимизировать

 

а

а

 

игрок

 

В

 – 

минимизировать

 

а

Для

 

простаты

 

отождествим

 

себя

 

мысленно

 

с

 

одним

 

из

 

игроков

  (

пусть

 

это

 

будет

 

игрок

 

А

), 

тогда

 

будем

 

называть

 

игрока

 

В

 – 

противник

” (

разумеется

каких

-

то

 

реальных

 

преимуществ

 

для

 

А

 

из

 

этого

 

не

 

вытекает

). 

Пусть

 

у

 

игрока

 

А

 

имеется

 

m

 

возможных

 

стратегий

 

А

1

А

2

, ..., 

А

m

а

 

у

 

противника

 – 

n

 

возможных

 

стратегий

 

В

1

В

2

, ..., 

B

n

 (

такая

 

игра

 

называется

 

игрой

 

х

 

n

). 

Обозначим

 

через

 

a

ij

 

выигрыш

 

игрока

 

А

в

 

случае

если

 

он

 

воспользуется

 

стратегией

 

А

i

а

 

игрок

 

В

 – 

стратегией

 

В

j

Предполагается

что

 

выигрыш

 

a

ij

 

известен

Тогда

 

мы

 

можем

 

составить

 

прямоугольную

 

таблицу

  (

матрицу

), 

в

 

которой

 

перечислены

 

стратегии

 

игроков

 

и

 

соответствующие

 

выигрыши

 (

рис

. 2.1). 

B

j

 

 
A

i

 

 

B

1

 

 

B

2

 

 

... 

 

B

n

 

A

1

 

a

11

 

a

12

 ... a

1n

 

A

2

 

a

21

 

a

22

 ... a

2n

 

... ... ... ... ... 

A

m

 

a

m1

 

a

m2

 ... a

mn

 

Рис

. 2.1. 

Если

 

такая

 

таблица

 

составлена

то

 

говорят

что

 

игра

 

G

 

приведено

 

к

 

матричной

 

форме

Отсюда

 

рассматриваемая

 

игра

 

и

 

получила

 

название

 

матричная

Само

 

по

 

себе

 

приведение

 

игры

 

к

 

такой

 

форме

 

уже

 

может

 

составить

 

трудную

 

задачу

а

 

иногда

 

и

 

невыполнимую

из

-

за

 

необозримого

 

множества

 

возможных

 

стратегий

 

игроков

 

и

 

трудности

 

определения

 

выигрышей

 

a

ij

Рассмотрим

 

некоторые

 

задачи

решение

 

которых

 

сводится

 

к

 

решению

 

матричных

 

игр

 

Игра

 1. 

Вариант

 

игры

 «

Морра

» 

Игра

 

состоит

 

в

 

том

что

 

каждый

 

из

 

двух

 

игроков

 

независимо

 

друг

 

от

 

друга

 

выбирает

 

определенную

 

сторону

 

монеты

 (“

герб

” 

или

 “

решка

”), 

затем

 

одновременно

 

называют

 

свой

 

выбор

Если

 

игроки

 

выбрали

 

одну

 

и

 

ту

 

же

 

сторону

 

монеты

то

 

второй

 

игрок

 

платит

 

первому

 

одну

 

гривну

если

 

разные

то

 

первый

 

платит

 

второму

 

такую

 

же

 

сумму

Легко

 

видеть

что

 

матрица

 

выигрышей

 (

платежная

 

матрица

этой

 

игры

 

имеет

 

вид

 


background image

 

13

 

B

j

 

 
A

i

 

 

B

1

 

 

B

2

 

A

1

 1  -1 

A

2

 -1  1 

 

Здесь

 

стратегии

 

А

1

 

и

 

В

1

 – 

игроки

 

А

 

и

 

В

 

выбирают

 “

герб

”, 

а

 

А

2

 

и

 

В

2

 – 

игроки

 

А

 

и

 

В

 

выбирают

 “

решку

”. 

Нетривиальность

 

сформулированной

 

задачи

как

 

и

 

любой

 

матричной

 

игры

состоит

 

в

 

том

что

 

каждый

 

из

 

игроков

 

делает

 

свой

 

выбор

 

независимо

 

друг

 

от

 

друга

 

Игра

 2. 

Борьба

 

за

 

рынки

 

Фирмы

 

А

 

и

 

В

 

производят

 

одинаковый

 

товар

 

и

 

в

 

настоящее

 

время

 

каждая

 «

контролирует

» 50% 

рынка

Улучшив

 

качество

 

товара

обе

 

фирмы

 

собираются

 

развернуть

 

рекламные

 

кампании

При

 

этом

приобретение

 

новых

 

покупателей

 

одной

 

фирмой

 

сопровождается

 

потерей

 

этих

 

покупателей

 

другой

 

фирмой

Исследование

 

показало

что

 60% 

потенциальных

 

покупателей

 

получают

 

информацию

 

через

 

телевидение

30% – 

через

 

газеты

 

и

 10% – 

через

 

радиовещание

Задача

 

каждой

 

фирмы

 – 

выбрать

 

стратегию

 

рекламной

 

кампании

В

 

данной

 

игре

 

у

 

каждого

 

из

 

игроков

 

по

 

три

 

стратегии

А

1

В

1

 – 

рекламировать

 

товар

 

через

 

телевидение

А

2

В

2

 – 

через

 

газеты

А

3

В

3

 – 

через

 

радиовещание

Поскольку

 

это

 

игра

 

с

 

нулевой

 

суммой

то

 

матрицу

 

выигрышей

 

фирмы

 

А

 

можно

 

представить

 

в

 

следующем

 

виде

 

 

 

B

1

 

 

B

2

 

 

B

3

 

A

1

 0 30 50 

A

2

 -30  0  20 

A

3

 -50 -20  0 

 

где

  a

ij

 – 

количество

 

покупателей

 

товара

 

фирмы

 

А

 

в

 

процентах

на

 

которое

 

оно

 

увеличивается

если

 

фирма

 

А

 

применяет

 

стратегию

 

А

i

 , 

а

 

фирма

 

В

 – 

стратегию

 

В

j

 

2.2. 

Принцип

 

максимина

 

в

 

антагонистических

 

играх

Седловая

 

точка

 

Как

 

отмечалось

важнейшим

 

вопросом

 

в

 

теории

 

игр

  (

в

 

том

 

числе

 

и

 

матричных

является

 

вопрос

 

о

 

выборе

 

оптимальных

 

стратегий

 

для

 

каждого

 

из

 

игроков

Оптимальной

 

стратегией

 

игрока

   

в

 

матричной

 

игре

 

называется

 

такая

которая

 

обеспечивает

 

ему

 

максимальный

 

выигрыш

Если

 

игра

 


background image

 

14

повторяется

 

неоднократно

то

 

оптимальная

 

стратегия

 

должна

 

обеспечивать

 

максимальный

 

средний

 

выигрыш

При

 

выборе

 

этой

 

стратегии

 

основой

 

рассуждений

 

является

 

предположение

что

 

противник

 

является

по

 

меньшей

 

мере

так

 

же

 

разумен

как

 

и

 

мы

 

сами

 

и

 

делает

 

все

чтобы

 

добиться

 

такой

 

же

 

цели

Расчет

 

на

 

разумного

 

противника

 – 

лишь

 

одна

 

из

 

возможных

 

позиций

 

в

 

конфликте

но

 

в

 

теории

 

игр

 

именно

 

она

 

кладется

 

в

 

основу

При

 

этом

 

для

 

выбора

 

оптимальной

 

стратегии

 

используют

 

принцип

 

максимина

выбирай

 

ту

 

стратегию

чтобы

 

при

 

наихудшем

 

для

 

нас

 

поведении

 

противника

 

получить

 

максимальный

 

выигрыш

Другими

 

словами

принцип

 

максимина

 

предполагает

 

выбор

 

той

 

стратегии

при

 

которой

 

наш

 

минимальный

 

выигрыш

 

для

 

различных

 

стратегий

 

максимален

Отсюда

 

и

 

название

 «

принцип

 

максимина

». 

Как

 

видно

принцип

 

максимина

 – 

это

 

принцип

 

крайне

 

осторожного

 

игрока

но

 

именно

 

он

 

является

 

основным

 

принципом

 

теории

 

матричных

 

игр

Для

 

пояснения

 

принципа

 

максимина

 

рассмотрим

 

пример

 1 

матричной

 

игры

 G (4

х

5) 

с

 

платежной

 

матрицей

приведенной

 

на

 

рис

. 2.2. 

Пример

 1. 

 

B

j

 

 
A

i

 

 

B

1

 

 

B

2

 

 

B

3

 

 

B

4

 

 

B

5

 

i

 

 

A

1

 5  6  7 

4  5 4 

 

A

2

 3 10  6 

5  6 3 

 

A

3

 12  5 

9  8  3 

 

A

4

 6  7  5 

6  10

максимин

 

max min

i

j

a

ij

 

j

 

12 10  7 9 

10

 

 

 

 

 

 

минимакс

 

 

min max

j

i

a

ij

 

 

 

 

 

Рис

. 2.2. 

 

Какой

 

стратегией

 

игроку

 

А

 

воспользоваться

Есть

 

соблазнительный

 

выигрыш

 12, 

при

 

применении

 

стратегии

 

А

3

Но

 

при

 

этом

 

противник

 

может

 

выбрать

 

стратегию

 

В

3

и

 

игрок

 

А

 

получит

 

выигрыш

равный

 

всего

 

трем

Для

 

определения

 

оптимальной

 

стратегии

  

в

 

соответствии

 

с

 

принципом

 

максимина

запишем

 

в

 

правом

 

добавочном

 

столбце

 

платежной

 

матрицы

 

минимальное

 

значение

 

i

 

в

 

каждой

 

строке

  (

минимум

 

строки

). 

Из

 

всех

 

значений

 

i

  (

правый

 

столбец

выделим

 

наибольшее

Ему

 

соответствует

 

стратегия

 

А

4

Выбрав

 

эту

 

стратегию

мы

 

во

 

всяком

 

случае

 

можем

 

быть

 

уверены

что

 

при

 

любом

 

поведении

 

противника

 

выигрыш

 

будет

 

не

 

менее

 

пяти


background image

 

15

Эта

 

величина

 – 

наш

 

гарантированный

 

выигрыш

Он

 

называется

 

нижней

 

ценой

 

игры

  (

или

  «

максимином

» – 

максимальный

 

из

 

минимальных

 

выигрышей

). 

Будем

 

обозначать

 

его

 

.  

В

 

нашем

 

примере

 

 = 

j

i

min

max

a

ij

 =5. 

Теперь

 

станем

 

на

 

точку

 

зрения

 

игрока

 

В

 

и

 

порассуждаем

 

за

 

него

Выбирая

 

стратегию

он

 

хотел

 

бы

 

отдать

 

поменьше

но

 

должен

 

рассчитывать

 

на

 

наихудшее

 

для

 

него

 

поведение

 

игрока

 

А

Припишем

 

к

 

платежной

 

матрице

  (

рис

. 2.2) 

нижнюю

 

строку

 

и

 

в

 

ней

 

запишем

 

наихудшее

 

для

 

игрока

 

В

 

возможные

 

результаты

  (

максимумы

 

столбцов

 

j

Очевидно

осторожный

 

противник

 

должен

 

выбрать

 

стратегию

при

 

которой

 

величина

 

j

 

минимальна

Эта

 

величина

 

называется

 

верхней

 

ценой

 

игры

 (

или

 “

минимаксом

” – 

минимальный

 

из

 

максимальных

 

проигрышей

). 

Будем

 

обозначать

 

ее

 

В

 

нашем

 

примере

 

 = 

min max

j

i

a

ij

 = 7. 

Итак

исходя

 

из

 

принципа

 

осторожности

игрок

 

А

 

должен

 

выбрать

 

стратегию

 

А

4

а

 

его

 

противник

 – 

В

3

Такие

 

стратегии

 

называются

 

максиминными

 

или

 

минимаксными

 

стратегиями

  (

вытекающие

 

из

 

принципа

 

максимина

). 

До

 

тех

 

пор

пока

 

обе

 

стороны

 

в

 

нашем

 

примере

 

будут

 

придерживаться

 

своих

 

максиминных

 

стратегий

выигрыш

 

игрока

 

А

 

и

 

проигрыш

 

игрока

 

В

 

будет

 

равен

 

а

43

=5. 

Легко

 

показать

что

 

нижняя

 

цена

 

игры

 

никогда

 

не

 

превосходит

 

верхней

 

цены

 

игры

Лемма

 1

Пусть

 

задана

 

матрица

 

выигрышей

  

А

 = 



ij



и

 

определены

 

ij

i

j

a

max

min

 

и

 

ij

j

i

a

min

max

Тогда

 

.

min

max

max

min

ij

j

i

ij

i

j

a

a

Доказательство

По

 

определению

 

максимума

 

и

 

минимума

 

для

 

любых

 

фиксированных

 

значений

 

i

 

и

 

j

 

имеем

 

.

min

max

j

i

j

ij

ij

i

a

a

a

 (2.1) 

Поскольку

 

левая

 

часть

 

неравенства

 (2.1) 

не

 

зависит

 

от

 

i

то

 

можем

 

записать

 

.

min

max

max

j

i

j

i

ij

i

a

a

 (2.2) 

Так

 

как

 

правая

 

часть

 

неравенства

 (2.1) 

не

 

зависит

 

от

 

j

то

 

.

min

max

min

ij

j

ij

i

j

a

a

 (2.3) 

Объединяя

 

неравенства

 (2.2) 

и

 (2.3), 

получаем

 

неравенство

 (2.1), 

что

 

и

 

требовалось

 

доказать

Итак

всегда

 



Случай

 

=

соответствует

 

наличию

 

у

 

платежной

 

матрицы

 

так

 

называемой

 

седловой

 

точки

Определение

Точка

  (

i

*, 

j

*) 

называется

 

седловой

 

точкой

 

платежной

 

матрицы

 ||

a

ij

||, 

если

 

для

 

всех

 

остальных

 i 

и

 j 

этой

 

матрицы

 

выполняется

 

условие

 

a

i*j

 

a

i*j*

 a

ij*