Тема 3. Игры в смешанных стратегиях

1. Понятие о частоте применения разных стратегий.

2. Матричный метод определения оптимальных смешанных стратегий и цены игры для игр 2х2.

3. Графический метод решения игр 2хm и 3хm.

Семинарское занятие № 3. Решение простейших игр в смешанных стратегиях

Решение игр в смешанных стратегиях матричным и графическим методом. Сложность применения смешанных стратегий на практике. Решение ненулевых игр в смешанных стратегиях. Игра «наступление и оборона». Игра 2х2 в смешанных стратегиях

Темы индивидуальных докладов:

1. Теория игр как оружие «холодной войны». Вклад Рэнд Корпорэйшн в развитие теории игр.

2. Теория игр в СССР (России).

Тема кейса для коллективного обсуждения:

1. Битва у Авранша (август 1944 г.).

Эксперимент:

1. «Конкурс красоты». Равновесие по Нэшу: теория и реальность

2. Эксперимент Дж. Нэша

1. Итак, на прошлой лекции мы выяснили, что большинство игр с нулевой суммой не поддается простому и красивому решению в чистых стратегиях. Конечно, путем исключения доминируемых и дублирующих стратегий иногда удается существенно уменьшить матрицу игры. И если удалось ее свести к одной строке или одному столбцу - игра решена в чистых стратегиях даже без принципа минимакса и нахождения седловой точки. Но чаще приходится признать, что ни одна из чистых стратегий не является оптимальной. Выход из этой казалось бы тупиковой ситуации тем не менее существует - надо чередовать стратегии в определенной пропорции. Поэтому решением игры в этом случае является как раз такая пропорция. Например, если у игрока 3 чистых стратегии и мы после определенных расчетов говорим – ему надо использовать эти стратегии в пропорции 5:1:4. В принципе, здесь могут стоять любые натуральные числа или даже ноль. В последнем случае говорят, что соответствующая стратегия не используется в смеси стратегий и является неактивной. Те же, которые используются, называют активными стратегиями. А само поведение игрока, связанное с чередованием его стратегий, называют смешанной стратегией. Основная теорема теории игр (она же теорема Неймана или теорема о минимаксе) гласит: любая парная игра с нулевой суммой имеет решение в чистых или смешанных стратегиях. Это решение определяет оптимальные минимаксные стратегии игроков и цену игры. Использование любой другой стратегии в среднем менее выгодно каждому из игроков. Цена игры всегда находится между нижней и верхней ценой матрицы игры. Решение в чистых стратегиях – это просто частный случай решения в смешанных стратегиях (когда в смеси активна лишь одна стратегия).

Если смешанная стратегия выражена в виде пропорции, то стоящие в ней числа называют относительными частотами применения стратегий. Существует и другой способ задания смешанной стратегии - через вероятности реализации чистых стратегий. Их легко рассчитать по известным относительным частотам. Пусть например задана смесь четырех стратегий в виде пропорции N₁: N₂: N₃: N₄. Тогда вероятность реализации первой стратегии равна:

р₁ = N₁/(N₁+ N₂+ N₃+ N₄)

Аналогично рассчитываются и остальные 3 вероятности р₂, р₃, р₄. Естественно, что сумма всех вероятностей в этом случае равна 1. На самом деле мы довольно часто сталкиваемся с такого рода понятиями. Например, при игре в русскую рулетку, когда в 6-зарядный барабан револьвера вставляется один патрон и выстрел производится после вращения барабана - реализуется смесь двух стратегий (убить – не убить) с относительными частотами 1:5, а вероятность рокового выстрела – 1/6. Или когда в годы репрессий давали разнарядку типа «каждого десятого» - это тоже смешанная стратегия с частотами 1:9.

Если действия по реализации стратегий производятся многократно, то вполне достаточно буквального использования относительных частот. Например, если работнику консульского отдела рекомендована смесь 2-х стратегий (выдать – не выдать визу) с частотами 2:3, то он может первым двум посетителям оформить визу, следующим 3-м – отказать и т.д. Но при этом он рискует тем, что посетители его «просчитают» и будут заранее знать кому он не откажет. Поэтому в теории игр обычно используется другой способ, который в принципе исключает возможность знать следующий ход. Он основан на вероятностном подходе и связан с использованием датчика случайных чисел. Такие датчики есть во многих компьютерных программах, хотя на практике чаще используют подручные средства типа бросания монетки или игральной кости. Например, при частотах 1:2 надо при каждом ходе бросать кубик и применять первую стратегию, когда выпадет 1 или 2, а в остальных случаях – использовать вторую стратегию. Любые вычислительные методы, использующие датчик случайных чисел, принято называть методами Монте-Карло. Заметим, что по методу Монте-Карло можно реализовать смешанную стратегию даже в одноходовой игре, которыми обычно и являются игры, представленные в нормальной форме. Осталось понять, как найти оптимальную смесь стратегий.

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

Пример 10. Игра «наступление и оборона»

Обороняющая сторона защищает 2 объекта, причем один из них в 3 раза важнее другого. Сил достаточно только на охрану одного из объектов, причем при нападении на охраняемый объект побеждает оборона. У нападения тоже сил достаточно только для атаки одного объекта. Спрашивается – какой из объектов надо охранять и на какой надо нападать. Это типичная парная игра 2х2. Первая стратегия обороны – защитить важный объект, вторая – защитить не важный. Аналогично и у нападения -

Первая стратегия напасть на важный объект и вторая – на второстепенный. С учетом важности объектов получаем матрицу игры (первый игрок – оборона):

Элементы матрицы равны суммарной важности уцелевших после нападения объектов.

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

4 3 | 3*

1 4 | 1

_____

4 4

* *

Как видим, седловой точки нет, хотя у второго игрока даже 2 минимаксные стратегии. Нижняя цена игры равна 3, верхняя – 4. Чтобы найти решение в смешанных стратегиях, в случае произвольной матрицы 2х2 надо просто вычесть второй столбец матрицы из первого. Отношение двух полученных разностей (независимо от их знаков) равно оптимальному соотношению применения первым игроком второй и первой стратегий. Аналогично потом вычитают вторую строку исходной матрицы из первой, отношение полученных разностей задает оптимальное отношение частоты применения вторым игроком его второй и первой стратегий. Обратим внимание – отношение первой разности ко второй равно в обоих случаях отношению частот именно второй и первой стратегий (а не наоборот) в оптимальной смеси. В данном случае получаем разность столбцов вида:

-3

Поэтому обороне надо использовать стратегии с частотами 3:1, то есть в 3 раза чаще охранять важный объект. Разность строк дает: (3 -1), значит у нападения относительные частоты применения чистых стратегий 1:3. Нападать получается чаще надо на менее важный объект.

Пример 11

Матрица игры имеет вид:

Седловой точки тоже нет. Вычитание столбцов дает (4, -9). Поэтому первый игрок должен применять свои первую и вторую стратегии в пропорции 9:4. Разность строк дает (5, -8), то есть второй игрок применяет свои стратегии с частотой 8:5.

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

ν = р₁а₁₁ + р₂а₂₁

Здесь а₁₁ и а₂₁ – элементы первого столбца матрицы игры. С таким же успехом можно использовать и элементы второго столбца – результат будет тот же. В примере 1 р₁ = ¾ и р₂ = ¼, поэтому:

ν = 0.75*4 + 0.25*1 = 3,25.

Повтор с использованием второго столбца дает тот же результат:

ν = 0.75*3 + 0.25*4 = 3,25.

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

3. Существует и другой – графический метод решения игр, который применим не только к играм 2х2, но и к играм, в которых у второго игрока число стратегий m > 2 (их называют играми 2хm). Метод состоит в построении графиков зависимости выигрыша от пропорции, в которой смешаны 2 стратегии первого игрока. Рассмотрим матрицу игры а_ij размерности 2хm. Пусть у первого игрока доля (вероятность) первой стратегии в смеси равна х, тогда доля второй (1-х). Если второй игрок использует чистую первую стратегию, то выигрыш первого составит:

х*а₁₁ + (1-х)*а₂₁ = а₂₁ + (а₁₁ - а₂₁)х

На графике этой функции соответствует прямая, у которой ордината равна а₂₁

при х=0 и а₁₁ при х=1:

Если у второго игрока 3 стратегии (m = 3), то на таком графике будет 3 линии. Каждая из них строится аналогично – на левой оси откладывается значение a2j, а на правой a1j. Например, при матрице:

слева откладываются 2, 1, 5, а справа 4, 7, 1, после чего соответствующие точки на обеих осях соединяются (см.рис.).

Другими словами – слева откладывают числа со второй строки матрицы, справа – с первой. Ясно, что противник выберет такие стратегии, чтобы ваш выигрыш был меньше. На графике этому соответствует нижняя ломаная линия из трех отрезков. А вы выберете на ней максимум (откуда опущен пунктир на ось). Абсцисса этой точки соответствует оптимальной доли первой стратегии х для первого игрока, а ее ордината равна цене игры. Оптимальная смесь стратегий второго игрока определяется потом путем дополнительных расчетов, хотя сразу можно сказать, что противнику следует использовать только те стратегии, линии которых проходят через выделенную точку (первая и третья в данном случае). Поэтому можно просто вычеркнуть второй столбец из матрицы и для оставшейся матрицы 2х2 найти решение.

Игры 3хm (у первого игрока 3 стратегии) решаются аналогично в трехмерном пространстве. При этом каждой чистой стратегии второго игрока теперь соответствует не прямая, а плоскость. Эти плоскости образуют конструкцию типа крыши и надо сначала выделить самую нижнюю «крышу», а потом найти координаты ее верхней точки.

Приближенно можно решить любую матричную игру, используя средство «Поиск решения» в меню «Сервис» программы EXCEL. Пусть у первого игрока n стратегий, а у второго m. Надо найти оптимальные доли стратегий р_i в их смеси для первого игрока. Обозначим цену игры ν, тогда при использовании противником любой из его m стратегий выигрыш первого игрока будет не меньше ν. Выразив этот выигрыш через р_i и элементы матрицы игры, получим соответствующие m неравенств вида:

a_1j p₁ + a_2j p₂ + … + a_nj p_n ≥ ν

Если обе части разделить на ν и обозначить х_j = p_j/ν, то неравенства преобразуются к виду:

a_1j х₁ + a_2j х₂ + … + a_nj х_n ≥ 1 (1)

Кроме того должно выполняться условие на сумму всех долей:

p₁ + p₂ + … + p_n = 1,

которое для переменных х имеет вид:

х₁ + х₂ + … + х_n = 1/ν. (2)

Так как первый игрок стремится повысить цену игры, последнюю сумму можно рассматривать как функцию цели и решать задачу по нахождению оптимальных значений переменных х_j, на которые наложено ограничение (1). С этой целью на рабочем листе EXCEL для каждой переменной х_j, заводим по ячейке и записываем туда некоторые начальные значения, соответствующие ограничениям (1). Например, это могут быть просто нули и единицы. После этого в одной из ячеек задаем х₁ + х₂ + … + х_n и указываем имя этой ячейки в меню «Поиск решения» на месте функции цели. Указываем также поиск минимума функции. Потом задаем платежную матрицу опять же на рабочем листе и через имена соответствующих ячеек выражаем ограничения на значения х. Для этого заводим ячейки на рабочем листе для вычисления левых частей неравенств (1), после чего в «Поиске решения» указываем в левой части имена этих ячеек, потом знак ≥, потом в правой части 1. Указывается также ограничение на знак величин х_j ≥ 0, при этом опять в левой части указывается только имя ячейки, соответствующей х_j. Далее дается команда «Найти» и в ячейках для х_j появляются оптимальные значения. Их сумма позволяет найти цену игры, пользуясь (2), после чего находятся и сами оптимальные доли стратегий в смеси р_j = х_j * ν. Аналогично находится оптимальная смесь стратегий второго игрока, только теперь потребуется максимизировать функцию цели.

Вопросы:

1) Как достигается смешивание стратегий в одноходовой игре?

2) В чем состоит основная теорема теории игр?

3) Как зависит выигрыш игрока, избравшего оптимальную смешанную стратегию, от использования активных стратегий вторым игроком (теорема об активных стратегиях)?

4) Что надо проверить до того как приступить к решению игры в смешанных стратегиях?

5) Какие игры решаются в смешанных стратегиях точно, а какие - приближенно?

6) Определение выигрыша при заданной смешанной стратегии у одного игрока и чистой стратегии – у другого.

7) Определение выигрыша при заданных смешанных стратегиях обоих игроков, в том числе в биматричной игре.

8) Решение игры 2х2 (определение ее цены и оптимальной смеси стратегий первого игрока).

9) Решение игры 2хm графическим методом (определение цены игры, оптимальной смеси стратегий 1-го игрока и активных стратегий 2-го игрока).

10) Приближенное решение игры с произвольной прямоугольной платежной матрицей (определение цены игры и оптимальной смеси стратегий 1-го игрока).

Литература:

Учебные пособия и монографии:

1. Вильямс Дж.Д. Совершенный стратег или букварь по теории стратегических игр: Пер. с англ. – М.: Советское радио, 1960. – 269 с.

2. Данилов В. Лекции по теории игр: Конспект лекций. - М.: Российская экономическая школа, 2002. – 140 с.

3. Льюис Р.Д., Райфа Х. Игры и решения: Пер. с англ. – М.: Издательство иностранной литературы, 1961. – 642 с.

4. Матвеев В.А. Конечные бескоалиционные игры и равновесия: Учебное пособие. Псков, 2005. – 176 с.

5. Печерский С.Л., Беляева А.А. Теория игр для экономистов: Вводный курс: Учебное пособие. - СПб.: Изд-во европейского университета в Санкт-Петербурге, 2001. – 253 с.

6. Augenstein Bruno W. A brief history of RAND’s Mathematics Department and Some of Its Accomplishments. Rand Corporation, 1993.

7. Brams Steven J. Game Theory and Politics. Dover Publications, 2004.

8. Dixit A., Skeath S. Games of Strategy. W.W.Norton & Company, 1999.

9. Dresher M. Games of Strategy. Theory and Application. Prentice-Hall, Inc., 1961.

10. Robinson Thomas W. Game Theory and Politics: Recent Soviet Views. Rand Corporation, 1970.

Статьи в периодических изданиях:

11. Allan P., Dupont C. International Relations Theory and Game Theory: Baroque Modeling Choices and Empirical Robustness. International Political Science Review (1999), Vol. 20, No. 1, pp.23–47.

Дата добавления: 2015-11-16