6. Лабораторная работа №6

Тема: Итерационный метод решения матричных игр

Цель: Приобрести навыки поиска рациональных решений с помощью итерационного метода.

Порядок выполнения работы:

1. Изучить теоретическую часть;

2. Упростить заданную по варианту матрицу, убрав доминантные строки;

3. С помощью MS Excel или написав программу, определить итерационным методом цену игры и оптимальные стратегии для каждого из игроков.

4. Проверить результат решения с помощью приведения задачи к задаче линейного программирования (ЛП).

Теория:

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

Общие понятия матричных игр

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

Для игр характерна неопределенность результата. Причины или источники неопределенности относятся к трем группам:

1. Комбинаторные источники (например игра шахматы);

2. Случайные факторы (например игры кости, карточные игры, где случаен расклад);

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

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

В игре принимают участие два игрока: A и B. В распоряжении каждого игрока имеется конечное множество вариантов выбора — стратегий. Пусть — множество стратегий игрока A, — множество стратегий игрока B. С каждой парой стратегий связан платеж, который один из игроков выплачивает другому. Т.е., когда игрок А выбирает стратегию (свою i-ю стратегию), а игрок В — стратегию , то результатом такого выбора становится платеж . Поскольку стратегий конечное число, то платежи образуют матрицу размерности n x m, называемую матрицей платежей (или матрицей игры). Строки этой матрицы соответствуют стратегиям игрока А, а столбцы — стратегиям игрока В.

Пусть два игрока А и В играют в игру, основанную на подбрасывании монеты. Игроки одновременно и независимо друг от друга выбирают герб (Г) или решку (Р). Если результаты двух подбрасываний монеты совпадают (т.е. ГГ или РР), то игрок А получает один доллар от игрока В. Иначе игрок А платит один доллар игроку В.

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

	BГ	BР
AГ
AР

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

	BГ	BР
AГ	1
AР		1

Если результаты подбрасывания различаются, то доллар получает В, значит платеж А равняется –1 доллар. В игре с нулевой суммой выигрыш игрока B равносилен проигрышу игрока A и равен поэтому .

	BГ	BР
AГ	1	–1
AР	–1	1

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

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

Итерационный метод Брауна-Робинсона

Пусть игра задана матрицей A размерности m x n. Каждое разыгрывание игры в чистых стратегиях будет далее называться партией. Метод Брауна-Робинсон — это итеративная процедура построения последовательности пар смешанных стратегий игроков, сходящейся к решению матричной игры.

В 1-ой партии оба игрока выбирают произвольную чистую стратегию. Пусть сыграно k партий, причем выбор стратегии в каждой партии запоминается. В (k + 1)-ой партии каждый игрок выбирает ту чистую стратегию, которая максимизирует его ожидаемый выигрыш, если противник играет в соответствии с эмпирическим вероятностным распределением, сформировавшимся за k партий. Оценивается интервал для цены игры и, если он достаточно мал, процесс останавливается. Полученные при этом вероятностные распределения определяют смешанные стратегии игроков.

Достоинства метода Брауна:

1. Этот метод ориентирован на произвольную игру G(m×n).

2. Не требует условия a_ij>0.

3. Легко реализуем программными методами.

Недостатки метода Брауна: скорость сходимости метода быстро уменьшается с ростом размерности матрицы игры. 

Рассмотрим метод на примере игры G(3×3).

Ai \ Bj	B1	B2	B3
A1	7	2	9
A2	2	9	0
A3	9	0	11

S_A=(p₁,p₂,p₃)

S_B=(q₁,q₂,q₃)

Строится следующая матрица:

k	i	B1	B2	B3	j	A1	A2	A3	Vmin	Vmax	V*
1	3	9	0	11	2	2	9	0	0	9	4.5
2	2	11	9	11	2	4	18	0	4.5	9	6.75
3	2	13	18	11	3	13	18	11	3.67	6	4.84
4	2	13	18	11	3	22	18	22	…	…	…
5	…	…	…	…	…	…	…	…	…	…	…
…	…	…	…	…	…	…	…	…	…	…	…

где:  k – номер партии.

i – номер стратегии, выбираемой игроком A.

j – номер стратегии, выбираемой игроком В.

B_i– накопленный игроком А выигрыш за k партий, при условии, что в данной партии B выбирает стратегию B_i.

А_j – накопленный игроком В проигрыш за k партий, при условии, что в данной партии A выбирает стратегию А_j.

Vmin – нижняя оценка игры = min (накопленный выигрыш)/k. 

Vmax – верхняя оценка игры = max (накопленный проигрыш)/k.

Доказано, что V^*=(Vmin+Vmix)/2,

    N_i - сколько раз выбирается А_i стратегия.

N_j - сколько раз выбирается B_j стратегия. 

Итерационный процесс метода Брауна-Робинсон не является, вообще говоря, монотонным. Кроме того, скорость сходимости метода быстро уменьшается с ростом размерности матрицы игры. Однако он обладает одним неоспоримым преимуществом, которое заключается в исключительной простоте программирования метода.

Варианты заданий:

	В1	В2	В3	В4	В5
А1	-3	1	3	2	-1
А2	-1	0	2	1	2
А3	-2	0	1	0	3
А4	2	1	-1	-2	-1
А5	-1	0	2	1	2

	В1	В2	В3	В4	В5
А1	4	-3	8	-5	6
А2	-3	-4	2	-9	-2
А3	6	7	3	-8	-9
А4	2	-2	0	-9	6
А5	7	3	6	-7	5

	В1	В2	В3	В4	В5
А1	-5	1	0	-2	-2
А2	-2	5	4	6	3
А3	3	2	1	0	9
А4	6	-2	8	4	7
А5	-1	1	9	2	4

	В1	В2	В3	В4	В5
А1	-3	2	9	6	-4
А2	-2	5	4	8	-2
А3	5	3	-1	7	5
А4	8	-2	6	4	8
А5	-3	2	3	6	-5

	В1	В2	В3	В4	В5
А1	5	4	1	2	6
А2	4	5	1	4	4
А3	3	4	0	3	-3
А4	2	-3	2	4	4
А5	-6	2	5	3	3

	В1	В2	В3	В4	В5
А1	4	3	6	4	0
А2	7	2	4	-6	5
А3	3	6	2	0	2
А4	4	3	5	2	-2
А5	2	-5	3	2	-5

	В1	В2	В3	В4	В5
А1	1	2	3	4	5
А2	-3	-2	-1	1	0
А3	2	8	4	5	6
А4	3	7	-4	0	2
А5	5	4	3	2	1

	В1	В2	В3	В4	В5
А1	0	6	6	3	0
А2	3	3	1	3	-3
А3	6	2	6	4	5
А4	4	4	6	4	3
А5	2	1	-1	2	-5

	В1	В2	В3	В4	В5
А1	3	0	2	4	6
А2	5	2	1	6	3
А3	1	-2	7	4	2
А4	2	3	2	6	6
А5	-1	-2	-3	-4	-5

	В1	В2	В3	В4	В5
А1	5	6	3	7	4
А2	3	2	-4	3	3
А3	2	6	0	-1	5
А4	8	6	6	7	4
А5	4	6	3	5	-4

	В1	В2	В3	В4	В5
А1	6	5	7	0	-2
А2	4	8	5	8	6
А3	5	-1	3	-2	1
А4	-4	1	3	2	5
А5	8	0	8	0	8

	В1	В2	В3	В4	В5
А1	4	5	3	2	-7
А2	5	7	6	3	2
А3	2	7	5	6	-2
А4	-5	-2	0	5	7
А5	3	2	5	-2	3

	В1	В2	В3	В4	В5
А1	4	3	2	6	5
А2	3	3	1	4	1
А3	3	-2	1	-5	0
А4	-4	0	6	0	5
А5	2	1	5	3	-1

	В1	В2	В3	В4	В5
А1	5	-1	2	3	4
А2	6	5	1	8	5
А3	4	5	4	2	3
А4	0	-3	3	0	-3
А5	2	1	0	1	2

	В1	В2	В3	В4	В5
А1	5	-6	3	0	0
А2	0	2	0	5	1
А3	3	6	4	6	5
А4	6	-1	5	2	-4
А5	2	3	-1	4	2

	В1	В2	В3	В4	В5
А1	5	0	0	3	1
А2	4	1	7	1	3
А3	0	1	-3	2	1
А4	5	7	4	5	7
А5	2	5	2	-5	2

	В1	В2	В3	В4	В5
А1	1	5	2	0	-5
А2	5	6	3	3	1
А3	2	6	1	3	6
А4	5	5	2	4	3
А5	5	0	4	3	2

	В1	В2	В3	В4	В5
А1	1	-6	6	1	7
А2	6	1	3	6	3
А3	2	2	3	-7	0
А4	5	7	5	1	3
А5	0	3	4	2	-5

	В1	В2	В3	В4	В5
А1	6	4	7	0	5
А2	7	5	-3	2	3
А3	5	0	0	-5	2
А4	8	1	7	2	3
А5	2	-7	6	6	0

	В1	В2	В3	В4	В5
А1	-2	2	5	2	3
А2	0	4	6	4	5
А3	0	2	0	6	-2
А4	5	-1	5	5	0
А5	7	1	-2	4	6

	В1	В2	В3	В4	В5
А1	6	3	5	8	7
А2	5	3	-4	2	8
А3	3	7	1	7	4
А4	1	-5	-2	2	1
А5	3	5	0	5	0

	В1	В2	В3	В4	В5
А1	2	5	2	0	7
А2	1	3	2	-5	5
А3	7	8	6	6	1
А4	3	4	3	-1	5
А5	6	0	2	6	-3

	В1	В2	В3	В4	В5
А1	3	7	2	5	3
А2	3	5	2	4	5
А3	5	1	5	3	4
А4	2	3	-1	0	3
А5	7	6	5	3	5

	В1	В2	В3	В4	В5
А1	0	6	5	5	2
А2	7	3	6	4	0
А3	4	2	5	3	-4
А4	2	5	-1	2	3
А5	5	6	0	3	5

	В1	В2	В3	В4	В5
А1	0	2	5	3	7
А2	1	6	9	5	1
А3	3	0	-2	1	8
А4	0	5	5	1	4
А5	6	3	7	-5	3