Сведение матричной игры к задаче линейного программирования

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

Допустим, что смешанная стратегия игрока А складывается из стратегий с вероятностями (некоторые из значений вероятностей могут быть равны нулю). Оптимальная смешанная стратегия игрока В складывается из стратегий с вероятностями . Условия игры определяются платежной матрицей с элементами , ; . Если игрок А применяет оптимальную смешанную стратегию, а игрок B — чистую стратегию , то средний выигрыш игрока А (математическое ожидание выигрыша) составит

.

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

(игрок А стремится максимизировать свой выигрыш)

Используя обозначения и соотношение , получим . Отсюда

Эта задача всегда имеет решение , получив которое (например, с помощью надстройки Поиск решения MS Excel) можно найти цену игры и оптимальные значения вероятностей — оптимальную смешанную стратегию игрока А.

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

Поведению игрока B соответствует двойственная задача линейного программирования:

(эквивалентно : игрок B стремится минимизировать свой средний проигрыш)

Здесь .

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

, .

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

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

1.

	В1	В2	В3	В4
А1
А2
А3
А4

2.

	В1	В2	В3	В4
А1	-2			-3
А2
А3			-2
А4

3.

	В1	В2	В3	В4
А1
А2	-3			-2
А3	-4			-1
А4				-3

4.

	В1	В2	В3	В4
А1
А2				-1
А3	-3
А4	-3		-1

5.

	В1	В2	В3	В4
А1			-1
А2
А3
А4			-3

6.

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

7.

	В1	В2	В3	В4
А1
А2
А3
А4		-1

8.

	В1	В2	В3	В4
А1
А2
А3
А4

9.

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

10.

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

11.

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

12.

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

13.

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

14.

	В1	В2	В3	В4
А1	-8
А2		-1
А3
А4	-3

15.

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

16.

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

17.

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

18.

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

19.

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

20.

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

21.

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

22.

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

23.

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

24.

	В1	В2	В3	В4
А1
А2
А3
А4

25.

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

Лабораторная работа №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Г
AР

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

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

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

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