Московский государственный институт

Московский государственный институт

Международных отношений (Университет)

МИД России

 

Д.А.Дегтерев

 

Конспект лекций по дисциплине

 

«Теория игр для международников и политологов»

 

 

Москва – 2008

 

ОГЛАВЛЕНИЕ:

РАЗДЕЛ 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР. 3

Лекция 1. Классификация игр и формы их представления. 3

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

Лекция 3. Игры в смешанных стратегиях. 21

Раздел 2. Теоретико-игровой анализ международных отношений. 29

Лекция 4. Простые игровые модели международных конфликтов. 29

Лекция 5. Игры с неполной информацией и дезинформацией. 37

Лекция 6. Динамические модели переговоров. 44

РАЗДЕЛ 3. ТЕОРИЯ ИГР И ПОЛИТОЛОГИЯ.. 50

Лекция 7. Применение теории игр к анализу выборов и голосования в коллективных органах 50

РАЗДЕЛ 4. ПРИМЕНЕНИЕ ТЕОРИИ ИГР В ЭКОНОМИКЕ.. 62

Лекция 8. Модели конкуренции и оптимизация сотрудничества. 62

 

 

РАЗДЕЛ 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР

Пример 1

Играет 2 человека. Они одновременно показывают от 1 до 3 пальцев. Если общее число пальцев четное – выиграл первый игрок, причем выигрыш равен этому же числу, например, в рублях Соответственно такой же получается проигрыш у второго игрока. Если сумма пальцев оказалась нечетной, то выиграл второй игрок и сумма выигрыша тоже равна числу пальцев. Поэтому в матрицу записывается эта сумма с минусом, как проигрыш первого игрока. Это игра с нулевой суммой, у каждого игрока по 3 стратегии: показать 1 палец, 2 или 3.. Соответственно в нормальной форме она представляется матрицей 3 х 3, которая имеет вид:

	-3
-3		-5
	-5

 

Пример 2

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

	-3		-5		-7
-3		-5		-7
	-5		-7		-9
-5		-7		-9
	-7		-9		-11
-7		-9		-11

 

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

 

( Рис.1 из семинаров )

 

 

Здесь первый и второй игроки делают по одному ходу, причем первый выбирает из трех стратегий, а второй – из двух. Пунктир означает, что второй игрок делает ход, не зная хода первого игрока. Игре соответствует нормальная форма:

 

 

5 10

15 20

25 30

 

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

 

Вопросы:

1. Математические модели принятия решений в условиях конфликтов и их теоретико-игровое представление.

2. Понятие о стратегиях (альтернативах) игроков. Конечные и бесконечные игры. Дискретные игры.

3. Игры качества и игры степени.

4. Чистые и смешанные стратегии. Вероятностный выбор стратегии и вероятные последствия выбранной чистой стратегии.

5. Одномоментные и многоходовые игры.

6. Понятие личного и случайного хода в игре. Азартные и стратегические игры.

7. Зависимость выигрыша (платежа) от выбранной стратегии. Построение таблицы выигрышей и определение функции выигрыша.

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

9. Взаимосвязь выигрышей играющих сторон. Игры с нулевой и ненулевой суммой. Антагонистические игры.

10. Примеры игр с ненулевой суммой. Биматричные игры.

11. Игры с природой, парные и множественные игры.

12. Коалиционные и бескоалиционные игры.

13. Построение матрицы парной игры с нулевой суммой. Анализ возможного поведения игроков.

14. Построение.дерева решений. Дерево игры. Аналогия с поочередным передвижением фишки в настольной игре.

15. Нормальная и экстенсивная формы представления игры. Преобразование одной формы в другую.

 

Литература

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

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

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

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

4. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение: Пер. с англ. – М.: Наука, 1970. – 708 c.

5. Олейнов А.Г. Введение в экономический анализ политических процессов: Учебное пособие. – М.: Издательство ЛКИ, 2008. – 144 с.

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

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

8. Haywood O.G. Military Doctrine of Decision and the Von Neumann Theory of Games. Rand Corporation, 1951.

9. Poundstone W. Prisoner’s Dilemma. Anchor Books, 1992.

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

 

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

11. De Bruin B. Reducible and Nonsensical Uses of Game Theory. Philosophy of the Social Sciences, Volume 38, No. 2, June 2008, pp. 247-266.

12. Stone Randall W. The Use and Abuse of Game Theory in International Relations: The Theory of Moves. - Journal of Conflict Resolution, Vol. 45, No.2, April 2001, pp. 216-244.

Пример 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.

 

Пример 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.

 

Рис. 0. Представление динамики переговоров игрой в развернутой форме.

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

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

 

Рис.1. Характерные элементы графа, отображающего ведение переговоров.

 

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

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

 

 

Вопросы:

1. Какой параметр максимизируется в ходе переговоров о совместном проекте двух сторон?

2. Как определяются компенсационные выплаты в простой договорной игре?

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

4. Модель ультимативной игры как пример динамической игры.

5. Примеры игр с точками совместных решений.

6. Описать ход переговоров по данной схеме в виде развернутой формы игры (рис.2).

 

Литература:

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

1. Лефевр В.А., Смолян Г.Л. Алгебра конфликта. Изд. 2-е, стереотипное. – М.: КомКнига, 2007. – 72 с.

2. Оуэн Г. Теория игр: Пер. с англ. – М.: Мир, 1971. – 229 с.

3. Петросян Л.А., Зенкевич Н.А., Семина Е.А. – М.: Высш. шк., Книжный дом «Университет», 1998. – 304 с.

12345678910Следующая ⇒

Поделиться: