Коалиционные (кооперативные) игры.




Теория игр.

 

Справочный материал.

 

Формализованная игра характеризуется:

- количеством субъектов, участвующих в конфликте;

- набором возможных действий для каждого игрока, называемых стратегиями;

- функциями выигрыша (платежа);

- результатом игры, к которому приводят выбранные игроками стратегии.

 

Игра двух игроков с n и m стратегиями задается следующей платежной матрицей:

    Стратегии 2-го игрока
        …. n
Стратегии 1-ого игрока  
   
       
m  

 

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

 

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

 

Стратегия игрока называется оптимальной, если при ее применении выигрыш (проигрыш) игрока не может быть уменьшен (увеличен), какими бы стратегиями не пользовался другой игрок.

 

Оптимальные стратегии игроков находятся по принципу осторожности или максимина/минимакса:

 

Пусть первый игрок имеет m стратегий, второй игрок – n стратегий, а платежная матрица

H:

Анализируя платежную матрицу первый игрок для каждой своей стратегии I (i=1,2,…m) найдет минимальное значение ожидаемого выигрыша, а затем из m выбранных элементов выберет максимальный и соответствующую ему стратегию , которая называется максиминной, поскольку она соответствует величине: .

Величина называется нижней ценой игры. Это максимально возможный выигрыш, не зависящий от действий второго игрока.

Второй игрок для каждой своей стратегии I (i=1,2,… n) найдет максимальное значение ожидаемого проигрыша, а затем из n выбранных элементов выберет минимальный и соответствующую ему стратегию , которая называется минимаксной, поскольку она соответствует величине: .

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

 

Если верхняя и нижняя цены игры совпадают, то в игре существует ситуация равновесия в чистых стратегиях: , где называется ценой игры.

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

 

Пример 1.

Дана платежная матрица игры:

1 3 2

H= 0 5 4

2 4 3

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

Решение.

Найдем минимально возможный выигрыш первого игрока, если он применит первую стратегию, он будет соответствовать минимальному элементу первой строки, т.е. 1.

Если первый игрок выберет вторую стратегию, то минимальный выигрыш будет равен 0

(т.к. он равен минимальному элементу второй строки). Для третьей стратегии это 2.

Затем из этих значений первый игрок должен выбрать максимально возможный выигрыш, т.е. 2. Этому выигрышу соответствует 3-ья стратегия, которая и является в данном случае оптимальной. Нижняя цена игры равна 2.

Применяя тот же принцип найдем оптимальную стратегию второго игрока.

Если второй игрок выберет первую стратегию, то максимальный проигрыш будет равен 2

(т.к. он равен максимальному элементу первого столбца).

Если второй игрок выберет вторую стратегию, то максимальный проигрыш будет равен 5

(он равен максимальному элементу второго столбца). Аналогично, для третьей стратегии получаем 4. Затем из выделенных максимально возможных проигрышей нужно выделить минимальный, т.е. 2. Ему соответствует первая стратегия (первый столбец платежной матрицы), она и является оптимальной для второго игрока. Верхняя цена игры равна 2.

Получили, что верхняя цена игры = нижней цене игры =цене игры. Следовательно игра имеет седловую точку (3;2), соответстветствующую оптимальным стратегиям двух игроков.

 

Пример 2.

Пусть каждый игрок имеет по две стратегии. Если оба игрока выбирают стратегии с одинаковыми номерами, то первый игрок выигрывает 100 руб, а второй проигрывает 100 рублей. В противном случае 100 руб выигрывает второй игрок, а первый проигрывает 100 руб. Составить платежную матрицу игры, определить верхнюю и нижнюю цену игры.

Решение.

, =-1, 1, седловой точки нет.

 

Пример 3.

 

Для матричной игры, заданной платежной матрицей:

0 6 15 6

13 6 5 3

H= 11 7 8 7

4 5 16 6

8 7 17 7

найти:

1) все максиминные стратегии первого игрока;

2) все минимаксные стратегии второго игрока;

3) все седловые точки;

4) цену игры.

 

Решение.

Для строк таблицы получаем следующие значения : 0,3,7,4,7. максимумов два – для 3-ей и для пятой строки. Они равны 7. Таким образом первый игрок имеет две максиминные стратегии: 3-ю и 5-ую. нижняя цена игры равна 7.

Для столбцов таблицы получаем равны 13, 7, 17, 7. Второй игрок имеет две минимаксные стратегии: 2-ую и 4-ую. Верхняя цена игры равна 7.

Седловых точек четыре: (3,2), (5,2), (3,4), (5,4). Цена игры равна 7.

 

Упрощение платежных матриц.

Стратегия первого игрока i доминирует стратегию k, если для всех элементов соответствующих этим стратегиям строк платежной матрицы справедливо:

. Это означает что, первому игроку ни при каких условиях не выгодно применять k-ую стратегию, т.к. в этом случае он будет выигрывать меньше, чем если применит стратегию i.

Стратегия второго игрока j доминирует стратегию k, если для всех элементов соответствующих этим стратегиям столбцов платежной матрицы справедливо:

. Это означает что, первому игроку ни при каких условиях не выгодно применять k-ую стратегию, т.к. в этом случае он будет проигрывать больше, чем если применит стратегию j.

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

- цены этих игр равны;

- оптимальные смешанные стратегии игроков в упрощенной игре являются также оптимальными смешанными стратегиями игроков в полной игре (в оптимальных стратегиях для полной игры исключенным строкам и столбцам приписываются нулевые вероятности).

 

Аффинное преобразование платежной матрицы не изменяет решения игры. Цена преобразованной игры может быть получена из цены первоначальной игры при помощи того же преобразования: .

 

Пример 1.

Уменьшить размерность следующей платежной матрицы:

 

5 2 1

Н = 2 4 3

3 6 4

 

Решение.

Необходимо исключить доминируемые стратегии первого и второго игрока.

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

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

 

Таким образом, получаем: Н’ = 5 1

3 4

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

и .

 

Пример 2.

 

Упростить платежную матрицу Н:

+400 -300

+200 +600

 

Решение.

Умножим каждый из элементов на 0,01, получим:

+4 -3

+2 +6

К каждому из элементов прибавим 3, получим:

7 0

5 9

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

 

Смешанные стратегии.

 

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

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

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

Вектор называется его смешанной стратегией.

Аналогично, вектор , для которого справедливо , называется смешанной стратегией второго игрока.

Основная теорема теории игр (теорема Неймана).

 

Для любой матричной игры с матрицей Н существуют и равны между собой величины и :

= .

Более того, существует хотя бы одна ситуация в смешанных стратегиях , когда = = V.

 

Теорема об активных стратегиях.

Если один игрок придерживается своей оптимальной стратегии, то его выигрыш остается неизменным и равным цене игры V, независимо от того. Что делает другой игрок, если он не выходит за рамки своих активных стратегий.

 

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

 

……

 

Аналогично, для второго игрока имеем:

…..

 

Таким образом, решение игры можно получить, разрешив две системы с m+1 и n+1 уравнениями и m+1 и n+1 неизвестными.

 

Пример 1.

Задана платежная матрица игры Н:

Н= 20 40

50 30

Найти решение игры.

Решение.

Определим верхнюю и нижнюю цену игры, использовав для этого минимаксную и максиминную стратегии:

=30;

= 40.

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

Для нахождения оптимальной стратегии первого игрока воспользуемся соотношениями:

Решив эту систему уравнений, получим: .

Для нахождения оптимальной стратегии второго игрока воспользуемся соотношениями:

Решив эту систему уравнений, получим: .

Таким образом решением игры является:

 

Пример 2.

Найти решение следующей игры:

5 3 2 1

2 1 6 2

Н= 2 3 2 0

4 2 8 3

2 1 1 1

 

Решение.

Сначала исключим доминируемые стратегии первого и второго игрока.

Для первого игрока доминируемыми являются стратегии 2,3,5.Для второго – стратегии 1,3.

Получаем упрощенную платежную матрицу:

3 1

2 3

Для оптимальной стратегии первого игрока справедливо:

,

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

Для оптимальной стратегии второго игрока справедливо:

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


 

 

Задачи для самостоятельного решения.

 

1. Дана платежная матрица игры:

3 4 5 2 3

Н= 1 8 4 3 4

10 3 1 7 6

4 5 3 4 8

Найти нижнюю и верхнюю цену игры и седловые точки.

 

2. Решить игру:

1 -3 -2

Н= 0 5 4

2 3 2

 

3. Найти седловые точки и цену игры:

5 3 4 3

Н= 5 3 6 3

0 2 1 3

4. Решить игру:

2 -2 -1

1 6 5

Н= 3 4 3

0 -6 4

 

5. Решить игру:

 

Н= 10 30

40 20

6. Упростить платежную матрицу игры:

1/4 0 1/12 1/6 1/12

½ 1/3 5/12 -1/3 -5/12

Н= ¼ 1/12 1/3 -1/12 -1/4

-1/2 -1/6 -5/12 -1/12 -1/12

Найти решение игры.

 

7. Решить игру, упростив платежную матрицу:

4 7 2 3 4

3 5 6 8 9

Н= 4 4 2 2 8

3 6 1 2 4

3 5 6 8 9

 

8. Составить платежную матрицу игры «чет-нечет» и решить игру.

 

9. Составить платежную матрицу игры полковника Блотто при m=2, n=2

 

Коалиционные (кооперативные) игры.

 

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

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: