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

1. Виды неопределенностей. Роль точности оценки выигрышей

2. Игры с сигнализацией и дезинформацией.

3. Экстенсивные формы представления игры с учетом неопределенности.

Семинарское занятие № 5. Анализ эффективности стратегий при неполной информации

Построение экстенсивной формы игры с учетом неопределенности. Вычисление среднего выигрыша при разных стратегиях. Влияние неточности определения матрицы игр на оптимальные стратегии. Оценка рисков при «честной» игре и дезинформации.

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

1. Вклад Р.Зельтена и Дж.Харшаньи в развитие теории игр.

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

1. Ядерная программа Ирана и Израиль

2. Ядерная программа КНДР

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

1. Урны с шариками

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

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

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

Для нас наиболее интересен третий тип неопределенности – стратегическая неопределенность. Она связана с неопределенностью хода противника даже при небольшом числе возможных вариантов. Такую неопределенность создает сам выбор той или иной стратегии противником. Соответствующие игры называют стратегическими. Именно применительно к этим играм и создавалась математическая теория игр. Стратегическая неопределенность является наиболее сложной, что видно на примере известной логической задачи про то, как спросить дорогу, ведущую к деревне лжецов. Если на развилке дороги спросить у местного жителя (неизвестно, лжец он или честный): «Если бы вы жили в другой деревне, как бы вы ответили на вопрос, ведет ли левая дорога в деревню честных людей?», то, как видно из лингвистической матрицы игры, можно все-таки получить истинную информацию:

Истинный ответ на вопрос

«да» «нет»

Ответ честного нет да

Ответ лжеца нет да

Но это срабатывает только в том случае, если лжец всегда обманывает. Используют даже термин «стратегический лжец» для обозначения человека, который обманывает только тогда, когда это ему выгодно, создавая стратегическую неопределенность.

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

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

Пусть игрок А обладает некой информацией, неизвестной игроку В. Тогда в связи с этим у него 3 возможные стратегии:

- скрыть информацию,

- передать игроку В всю информацию или ее часть,

- дать противнику неверную информацию.

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

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

У менее информированного игрока В при получении информации от игрока А тоже есть 3 стратегии:

- поверить этой информации,

- не верить и пытаться отделить правду от лжи,

- игнорировать полученную информацию.

Причем принято больше доверять информации, проявляющейся в действиях игрока А, чем его словам. Хотя игрок А зная это может имитировать соответствующие действия с целью обмана. Тогда игроку В необходимо предпринять действия, заставляющие игрока А обнаружить его истинные намерения и возможности. Такую стратегию называют скринингом и можно привести много примеров из самых разных областей. У военных это разведка боем, у партизан «проверки на дорогах» подозрительного новобранца, наконец «если друг оказался вдруг и не друг и не враг, а так», то Высоцкий рекомендовал альпинизм («парня в горы тяни, рискни»). Выделяют также стратегию типа побудительной схемы (incentive scheme), при которой противника заставляют проявить своими действиями истинную информацию с помощью штрафов или поощрений. Примером является библейская притча про царя Соломона, рассудившего, кому из двух женщин принадлежит ребенок. Он приказал разрезать ребенка пополам, то есть штрафом для настоящей матери была бы смерть ребенка и она отказалась от претензий на него, чем и подтвердила свои материнские права. На практике конечно применяют более цивилизованные схемы, позволяющие выяснить ценность объекта для игрока. Например, выплачивают большую премию по результатам работы, что заставляет работника полностью проявить его способности. В международных отношениях примером являются инспекции на ядерных объектах Ирана – если бы он обладал атомной бомбой, ему пришлось бы отказать в проведении таких проверок и тогда к нему применили бы экономические санкции.

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

1\2 C D

A x, 9 3, 6

B 6, 0 6, 9

Здесь у каждого игрока по 2 стратегии: у первого А и В, у второго С и D, причем выигрыш первого игрока при комбинации стратегий АС задан случайным числом х. Пусть про него известно, что с вероятностью 1/3 оно равно 0 и с вероятностью 2/3 оно равно 10. Допустим, что первый игрок при выборе своей стратегии знает, какое значение х на самом деле имеет место, тогда как второй не знает этого. Тогда игра в развернутом виде представляется графом, приведенном на рис.1. Пунктир соответствует отсутствию информации о первом игроке у второго игрока.

Рис.1. Развернутая форма игры с точкой случая (выбора природы).

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

- выбирать при х = 0 стратегию А, и при х = 10 – стратегию А (стратегия А¹⁰А⁰);

- выбирать при х = 0 стратегию А, а при х = 10 – стратегию В (стратегия В¹⁰А⁰);

- выбирать при х = 0 стратегию В, а при х = 10 – стратегию А (стратегия А¹⁰В⁰);

- выбирать при х = 0 стратегию В, и при х = 10 – стратегию В (стратегия В¹⁰В⁰);

Поэтому в обычной нормальной форме игра принимает вид матрицы размерности 4х2. Такая матрица называется нормальной формой по Байесу, потому что значения ее элементов рассчитываются по правилу Байеса для вычисления среднего значения вероятностных величин. Например, элемент, соответствующий набору стратегий В¹⁰А⁰ и D вычисляется с учетом вероятностей реализации разных значений параметра х следующим образом:

(2/3)*(6, 9) + (1/3)*(3, 6) = (5, 8)

Здесь в скобках через запятую указаны компоненты вектора выигрышей игроков. Так, вектор с компонентами (6, 9) соответствует элементу первоначальной матрицы при наборе стратегий В и D, а вектор (3, 6) соответствует стратегиям А и D. В результате таких расчетов получается уже обычная числовая матрица игры, с использованием которой удобно анализировать предпочтительность разных комплексных стратегий. Можно, в частности, найти равновесные по Нэшу наборы стратегий. Так, профиль В¹⁰В⁰ – D здесь является равновесным.

1\2 C D

А¹⁰А⁰ 20/3, 9 3, 6

В¹⁰А⁰ 4, 3 5, 8

А¹⁰В⁰ 26/3, б 4, 7

В¹⁰В⁰ 6, 0 6, 9

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

Аналогичный подход используется для построения дерева решений в случае, когда решения принимает только одна сторона и известны вероятности их последствий. Это позволяет, в частности, учесть риски при реализации разных стратегий. Пусть, например, у лица, принимающего решение (ЛПР) есть два варианта действий. В первом случае он может получить 10 тыс. у.е. с вероятностью 50%, а во втором – 20 тыс. с вероятностью 10%. Чтобы сделать правильный выбор надо найти математические ожидания выигрыша в обоих случаях и сравнить их. Это «ожидание» рассчитывается как произведение вероятности на величину выигрыша. Таким образом первому варианту соответствует 0,5*10000 = 5000, а второму 0,1*20000 = 2000. Отсюда ясно, что лучше первый вариант.

Вопросы:

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

2. Пояснить решение логической задачи со 100-процентным лжецом.

3. Привести примеры сигнализации из области международных отношений.

4. Привести примеры дезинформации в международных отношениях.

5. Привести примеры скрининга и побудительных схем.

6. Построить нормальную форму игры по Байесу по заданной развернутой форме.

7. Привести пример парной игры с нулевой суммой, в которой оба игрока не знают один из элементов матрицы игры. Как зависят их стратегии от этого элемента?

8. Какая игра называется ассиметричной по информации?

9. Пояснить понятие точки случая (выбора природы). Как она изображается?

Литература:

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

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

2. Шеллинг Т. Стратегия конфликта: Пер. с англ. – М.: ИРИСЭН, 2007. – 366 с.

3. Axelrod R. The Evolution of Cooperation. Basic Books, 2006.

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

5. Brodie B. Strategy in the Missile Age. Princeton University Press, 1959

6. Davis Morton D. Game Theory: a Nontechnical Introduction. – Dover Publications, 1997.

7. Diplomacy Games. Formal Models and International Negotiations. Edited by Rudolf Avenhaus & I.William Zartman. Springer 2007.

8. Gates S., Humes B. Games, Information and Politics. Applying Game Theoretic Models to Political Science. The University of Michigan Press, 2007.

9. McKinsey J.C.C. Introduction to the Theory of Games. Rand Corporation, 1952.

10. Mayerson R.B. Game Theory. Analysis of Conflict. Harvard University Press, 1997.

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

11. Walsh James I. Do States Play Signaling Games. Cooperation and Conflict: Journal of the Nordic International Studies Association, Vol. 42, No.4, 2007, pp. 441–459.

12. 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