Тема 2. Решение бескоалиционных игр в чистых стратегиях

1. Исключение заведомо слабых стратегий (итерационное доминирование).

2. Выбор оптимального ответного хода (BR).

3. Принцип минимакса.

4. Седловые точки и равновесие по Нэшу

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

Особенности игр с ненулевой суммой. Множественность точек равновесия и их типы. Фокальные точки. Выявление доминируемых стратегий, игра 3х4. Выбор оптимальной ответной стратегии, игра 5х5. Отсутствие седловой точки, игра 2х2. Нижняя и верхняя цена игры по Нейману и по Нэшу, игра 3х3. Идентификация седловой точки, игра 2х2. Наличие нескольких седловых точек, игра 4х4. Точки равновесия по Нэшу, биматричная игра 3х2.

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

1. Джон Нэш и «Игры разума».

2. Роль эксперимента в развитии теории игр.

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

1. Фокальные точки (назначение свидания)

Написание контрольной работы №1. Задачи на представление игр и их решение в чистых стратегиях

1. Итак, приступим к решению игр. Классическая теория рассматривает решение игр, представленных в нормальной форме. То есть дана матрица игры, размерность которой определяется числом возможных стратегий каждого игрока и по этой числовой матрице надо сделать вывод об оптимальных стратегиях игроков. Если требуется выбрать только по 1 лучшей стратегии – это решение игры в чистых стратегиях. Как мы потом увидим, для некоторых игр решение ищут в виде пропорции сразу нескольких стратегий. Например, в 70% случаев использовать первую стратегию и в 30% - вторую. Тогда говорят о решении в смешанных стратегиях. Рассмотрим для определенности парную антагонистическую игру, в которой у каждого игрока всего по 2 стратегии. Примером в этом случае может служит дуэль, когда каждый игрок решает – стрелять (первая стратегия) или не стрелять (вторая стратегия). Допустим, удалось выяснить, что если оба стреляют, то первый выигрывает 1 у.е., если оба не стреляют - его выигрыш равен 4, если первый стреляет, но второй нет – выигрыш 2 и если второй стреляет, а первый нет, то 3. Вся эта информация компактно представлена матрицей игры вида:

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

Простейшей процедурой, позволяющей приблизиться к решению игры, является исключение заведомо слабых стратегий игроков. Для этого просто просматриваются все строки матрицы и вычеркиваются те, в которых все соответствующие элементы меньше, чем в хотя бы одной другой строке. Видно, например, что такой «невыгодной» строкой является первая строка рассматриваемой матрицы. Потому что 1 меньше 3 и 2 меньше 4. Соответственно, первый игрок в любом случае получит больше, если выберет вторую стратегию, независимо от выбора второго игрока. При этом говорят, что первая строка доминируется второй. В большой матрице может быть сразу несколько доминируемых строк, которые вычеркиваются. Может оказаться так, что в строке одни элементы меньше, а другие равны соответствующим элементам другой строки. Такая строка, вообще говоря, не является доминируемой, хотя тоже может исключаться из рассмотрения во многих играх. Встречаются также полностью одинаковые строки или столбцы, соответствующие им стратегии называются дублирующими. Обычно все такие стратегии кроме одной тоже исключают.

Аналогично рассуждает и второй игрок, с той разницей, что он выбирает столбцы, а не строки и стремится уменьшить, а не увеличить выигрыш первого игрока (при нулевой сумме это его проигрыш). Ясно, что для него первый столбец, так как 1 меньше 2 и 3 меньше 4. Значит независимо от выбора первого игрока второму лучше выбирать первую стратегию, то есть стрелять. Вот и вся процедура, после которой матрица станет на несколько строк и несколько столбцов меньше, что существенно упрощает дальнейший анализ при большом числе возможных стратегий. На самом деле, после того как вычеркнуты некоторые столбцы, надо опять повторить эту процедуру, так как строки стали другими и могло изменится соотношение между ними. При просмотре опять могут быть выявлены «заведомо слабые» стратегии первого игрока. Соответственно и анализ столбцов потом придется повторить. И так далее. Получается, что метод состоит в повторении однотипных шагов, которые в математике называют итерациями. Отсюда и его название – итерационное доминирование.

Пример 3

Пусть у первого игрока 3 возможных стратегии, у второго 4 и матрица игры имеет вид:

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

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

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

2. Ситуация кардинально меняется, если один из игроков уже сделал выбор, его знает противник и уже исходя из этой информации делает свой выбор. Это задача выбора оптимального ответа, которая в англоязычной литературе обозначается аббривиатурой BR (best response). При наличии матрицы игры она решается тривиально. Так, если известен выбор второго игрока, то первому достаточно просмотреть только один столбец матрицы, соответствующий номеру выбранной стратегии второго игрока, и выбрать ту строку, где стоит максимальный в данном столбце элемент.

Пример 4

Пусть у обоих игроков по 5 стратегий и матрица игры имеет вид:

Если известно, что второй игрок выбрал первую стратегию, то достаточно просмотреть лишь первый столбец матрицы и найти в нем максимальный элемент. Это число 9, стоящее в 4-й строке. Значит оптимальным ответом первого игрока является 4-я стратегия.

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

f(S₁,S₂) = 5 - 4S₁² + 3S₂ + 2S₁.

Это так называемые игры с сотрудничеством, к которым мы потом еще вернемся. При известном выборе суммы S₂ вторым игроком выигрыш первого выражается обычной функцией от одной переменной S₁. Переменная S₂ тогда заменяется в выражении для функции числом, например при S₂ = 5 получим f(S₁) = 5 - 4S₁² + 15 + 2S₁, то есть f(S₁) = 20 - 4S₁² + 2S₁, Остается найти значение S₁, при котором достигается максимум данной функции, например, взяв производную или даже просто построив ее график.

3. Вернемся к анализу обычных игр, представленных числовой матрицей в нормальной форме. Если рассматривать все возможные варианты, предполагая, что противник знает ваш ход, то нетрудно предугадать его ответный ход. Это та же задача на оптимальный ответ, которая, как мы видели, сводится в данном случае к выбору минимального элемента из заданной вами строки (то есть вы – это первый игрок). Рассуждая в дальнейшем по принципу «я так, он так» можно найти таким образом минимумы для каждой из строк. И вот тут наступает ключевой момент. В теории игр обычно предполагается, что каждый игрок – сторонник гарантированного выигрыша. То есть, если есть вариант наверняка выиграть 50 у.е. и возможность рискнуть, получив в зависимости от хода второго игрока 40 или 70 у.е., первый игрок выберет вариант с 50 у.е. Такой выбор в теории игр называется рациональным. Поэтому просмотрев минимумы для всех строк матрицы первый просто выбирает ту строку, где это число максимально. Это гарантированный выигрыш, не зависящий от выбора второго игрока. Если повезет – можно выиграть и больше, но меньше нельзя в принципе, сделав такой выбор. Поскольку эта процедура связана сначала с нахождением минимумов строк, а потом максимума среди них, то рассмотренный принцип решения игр называется принципом максимина или минимакса (ведь второй игрок сначала находит максимумы во всех столбцах матрицы и потом из них выбирает минимальный). А выбранные таким образом стратегии игроков называются соответственно максиминными и минимаксными. Из-за благозвучности чаще используется термин «принцип минимакса», а не максимина. Если матрица игры достаточно большая, то просматривать все ее строки и столбцы довольно утомительно. Поэтому в компьютерных программах, предназначенных для работы с матрицами (такими как MATCAD или MATLAB) обычно в меню есть даже специальная функция - нахождение максимального или минимального элемента в заданном столбце (строке) матрицы. В этом случае достаточно задать в программе матрицу и щелкнуть соответствующую клавишу.

Пример 5

Рассмотрим игру с матрицей:

В первой строке минимум равен 1, во второй – 2. Поэтому рациональный выбор первого игрока соответствует второй стратегии. Теперь смотрим столбцы – в первом максимум равен 3, во втором 4. Поэтому минимаксная стратегия второго игрока – это первая стратегия. Таким образом, первый игрок выберет вторую стратегию, второй – первую.

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

Пример 6

Пусть у каждого игрока по 3 стратегии и матрица игры размерности 3х3 имеет вид:

2 3 4 | 2 *

6 0 5 | 0

-1 2 3 | -1

________|

6 4 5

*

Здесь нижняя цены равна 2, а верхняя 4 (они отмечены звездочками). Поскольку они не совпадают, игра не решается в чистых стратегиях. Тем не менее у первого игрока рациональный выбор соответствует 1-й стратегии, а у второго – 2-й.

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

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

Пример 7

У игроков всего по 2 стратегии и матрица игры:

Найдем нижнюю и верхнюю цены игры:

7 4 |4*

1 3 |1

______

7 4

*

Как видим, они совпали и цена игры равна 4. В этом случае минимаксными стратегиями являются первая у первого игрока и вторая – у второго. Причем в данном случае они устойчивы. Если второй игрок вместо минимаксной воспользуется другой стратегией – он проиграет больше. Так, при использовании первым игроком его минимаксной первой стратегии проигрыш второго при нерациональном выборе составит не 4, а 7.

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

Пример 8

2 3 3 1 | 1

5 4 4 6 | 4*

4 4 4 7 | 4*

3 3 3 5 | 3

___________

5 4 4 7

* *

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

А часто таких точек вообще нет. Если матрица игры составлена случайным образом, то вероятность существования седловой точки при размерности матрицы 2х2 равна 0.7, 3х3 – уже 0.3, а в матрицах 9х9 – всего 0.001. Разумеется, седловая точка может быть и в прямоугольной матрице.

Именно с проверки на наличие седловой точки рекомендуется начинать анализ игры, представленной в нормальной форме. При ее наличии сразу получаем решение игры – устойчивые минимаксные стратегии обоих игроков и значение цены игры. Ну а если такой точки нет, то делаем вывод, что игра не решается в чистых стратегиях. Тогда уже применяется итерационное доминирование и методы решения игры в смешанных стратегиях.

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

Пример 9

Пусть у первого игрока 3 стратегии, у второго две и матрица игры (сдвоенная) имеет вид:

(2, 2) (2, 2)

(4, 2) (1, 3)

(5, 4) (1, 3)

Устойчивыми по Нэшу являются 3-я стратегия первого игрока и 1-я – второго. В этом случае первый выигрывает 5, а второй – 4.

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

Вопросы:

1. Примеры игр с заданием матрицы игры.

2. Исключение заведомо невыгодных стратегий методом итерационного доминирования.

3. Определение наилучшего ответного хода по данной матрице игры.

4. Минимаксные стратегии и принцип гарантированного выигрыша.

5. Понятия верхней и нижней цены игры для игр с нулевой суммой (минимакс и максимин).

6. Анализ игровой матрицы на наличие седловой точки.

7. Вероятность наличия седловой точки в матрицах разной размерности.

8. Устойчивость игры в чистых стратегиях.

9. Важность информации о стратегии противника. Пример с выбором места засады при оптимальной перевозке груза.

10. Решение простых игр в чистых стратегиях.

11. Что будет, если один игрок придерживается оптимальной стратегии, а второй – нет?

12. Устойчивость по Нэшу в играх с ненулевой суммой.

13. Примеры биматриц с седловыми точками.

14. Биматрицы с несколькими седловыми точками. Анализ их предпочтительности.

Литература:

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

1. Вентцель Е.С. Элементы теории игр. – М.: ГИФМЛ, 1961. – 68 с.

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

3. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.: Наука, 1985. – 272 с.

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

5. Крушевский А.В. Теория игр. – Киев.: «Вища школа», 1977. – 216 с.

6. Лапшин К.А. Игровые модели и принятие решений: Методические указания для студентов экономического факультета. – М.: МСА им. К.А. Тимирязева, 2001. – 45 с.

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

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

9. Nash J. Non-Cooperative Games. A Dissertation Presented to the Faculty of Princeton University in Candidacy for the Degree of Doctor of Philosophy. May, 1950.

10. Watson J. Strategy. An Introduction to Game Theory. W.W.Norton & Company, 2002.

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

11. Van Damme E. On the Contributions of John C. Harsanyi, John E Nash and Reinhard Selten. International Journal of Game Theory, Vol. 24, 1995, pp. 3-11.

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