Фонд Дмитрия Зимина «Династия»

Московский физико-технический институт

Институт экономики переходного периода

В.П. Бусыгин, А.К. Ковальджи

Выбор стратегии: вопросы и задачи

(материалы для учителей математики и экономики в средней школе)

Фонд Дмитрия Зимина «Династия»

Московский физико-технический институт

Институт экономики переходного периода

В.П. Бусыгин, А.К. Ковальджи

Выбор стратегии: вопросы и задачи

(материалы для учителей математики и экономики в средней школе)

Москва 2006

УДК [33:519.83](036+075.4) ББК 22.17я78-1+65в635я78-1 Б92

Б92

Бусыгин В.П., Ковальджи А.К. Выбор стратегии: вопросы и задачи (материалы для учителей математики и экономики в средней школе — Москва: ИЭПП, 2006. — 94 с: ил. — ISBN 5-93255-183-6.

Агентство CIP РГБ.

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

Настоящее издание подготовлено за счет средств Фонда Дмитрия Зимина «Династия» по заказу Фонда «Новое экономическое образование»

УДК [33:519.83](036+075.4) ББК 22.17я78-1+65в635я78-1

ISBN 5-93255-183-6

Содержание

Введение.............................................................................................5

1. Развивающие математические игры........................................6

1.1. Тест-разминка (на 30 минут)...................................................6

1.2. Ответы к Тесту-разминке........................................................9

1.3. Тест№1 (на 1 час)..................................................................10

1.4. Ответы и указания к Тесту №1.............................................12

1.5. Тест №2 (на 1 час)..................................................................13

1.6. Ответы и указания к Тесту №2.............................................15

1.7. Математические игры............................................................16

1.8. Указания к играм....................................................................20

2. Элементы теории некооперативных игр...............................24

2.1. Примеры и понятия................................................................24

2.2. Статические игры с полной информацией..........................25

2.3. Концепция доминирования...................................................27

2.4. Последовательное отбрасывание строго доминируемых стратегий.............................................................35

2.5. Равновесие по Нэшу...............................................................40

2.6. Равновесие по Нэшу в смешанных стратегиях ................................. ......................................................48

2.7. Упражнения для самостоятельного решения..........................................................................................54

2.8. Задачи повышенной трудности (для исследования)........................................................................57

3. Динамические игры с совершенной информацией...................................................................................59

3.1. Примеры и понятия................................................................59

3.2. Дополнительные задачи........................................................71

4. Динамические игры с несовершенной информацией...................................................................................74

4.1. Основные понятия..................................................................74

4.2. Уточнение понятия стратегии...............................................76

5. Некоторые применения теории игр........................................80

5.1. Государство и экономика......................................................80

5.2. Общественное благо и проблема координации...................82

5.3. Общественное благо со слабыми связями...........................83

5.4. Координирующая функция государства..............................85

5.5. Общественные блага добровольного типа...........................87

5.6. Кто будет добровольцем........................................................88

5.7. Общая модель добровольного общественного блага.........92

Введение

Цель настоящей брошюры — помочь читателям освоить экономический образ мышления. Базой такого мышления является логика и навык работы с числами и выражениями. Первая часть предлагаемой брошюры посвящена проверке и тренировке необходимых математических навыков.

Экономическое мышление сегодня является частью стратегического мышления, навыки которого формирует теория игр. Вторая часть брошюры представляет введение в теорию игр, доступное для вдумчивого и заинтересованного старшеклассника. В частности, не предполагается знакомства читателя с математическим анализом.

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

Авторы: к.ф.-м.н., сотрудник Института экономики и организации промышленного производства В. П. Бусыгин и организатор математических олимпиад заместитель директора Лицея «Вторая школа» по научной работе А. К. Ковальджи.

1. Развивающие математические игры

Сначала читателю предлагается выполнить тесты, которые покажут степень его готовности к восприятию дальнейшего материала, а также уровень его математических способностей. Тесты №1 и №2 использовались при наборе в 7-9 физико-математические и экономико-математические классы Лицея «Вторая школа» г. Москвы.

Примерно из 1000 школьников 7-11 классов, писавших тесты №1 и №2, только 5 человек правильно решили все задачи, что составляет 0,5%. В 90% случаев у людей есть пробелы, а в 10% случаев допущены «глупые» ошибки. Невнимательность, конечно, меньшее зло, чем непонимание, но представьте себе водителя, который иногда путает газ и тормоз.

Тесты составлялись по принципу: какие задачи должен уметь решать обычный выпускник средней школы, когда он «всё» забудет, -забудет квадратные уравнения, синусы и логарифмы, — но всё же у него должны в «сухом остатке» сохраниться простейшие навыки решения практических задач.

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

1.1. Тест-разминка (на 30 минут)

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

Если в одной задаче несколько вопросов, то «плюс» ставится за верные ответы на все вопросы. Обобщенным результатом является число плюсов.

Далее предложены критерии для оценки вашей готовности к восприятию материала брошюры. Цель тестов — проверить минимально

необходимый технический уровень и элементарную логическую культуру.

Вы готовы к восприятию содержания и языка теории игр, если получили не менее 35 плюсов из 40 (допустимы ошибки в задачах 31 и 32, и еще допустимо не более трех ошибок «по невнимательности».

Если получено менее 30 «плюсов», то ситуация тревожная, и надо понять, в каких типах задач и почему сделаны ошибки. Возможны два «диагноза»: либо Вы слишком невнимательны и «спотыкаетесь на ровном месте», либо какие-то темы у Вас «хромают».

1. Укажите первые три простых числа_

2. Сократите дробь 45/54_

3. Найдите частное_и остаток_от деления 44 на 5.

4. Выделите целую часть _

5. Переведите смешанную дробь в обыкновенную _

6. Переведите в десятичную дробь 1/8_

7. Переведите в обыкновенную дробь 0,75_

8. Укажите число, которое больше 0,1, но меньше 0,11_

9. На сколько 2/3 больше чем 4/9? _

10. Во сколько раз 2/3 больше чем 4/9?_

11. Какая дробь больше 5/7 или 7/10?_

12. Разделите 112233445566778899 на 11_

13. Найдите наибольший общий делитель чисел 84 и 90_

14. Приведите дроби 1/36 и 1/54 к наименьшему общему знаменателю _

15. Килограмм сыра стоит 80 руб. Сколько стоит 300 г сыра?_

16. Сколько процентов составляет 2 от 5?_

17. Найдите 3% от 150_

18. Если 5% числа равны 10, то чему равно число?_

19. Прибыль первой фирмы уменьшилась в 2 раза. На сколько процентов она уменьшилось?_. Прибыль второй фирмы увеличилась в 2 раза. На сколько процентов она увеличилось?

20. Решите уравнение

21. Решите уравнение

22. Решите уравнение

23. Турист прошел за 4 часа 18 км. С какой скоростью он шел?_

24. Турист прошел 14 км со скоростью 4 км/ч. Сколько времени он шел? _

25. Турист шел 3 часа со скоростью 3,5 км/ч. Какое расстояние он прошел?_

26. Один трактор вспахивает 3 га за 8 часов. За какое время 10 тракторов вспашут 30 га? _

27. Стог сена корова съедает за 3 дня, а коза — за 6 дней. За сколько дней они съедят стог сена вместе? _

28. На числовой прямой А(-10), В(50), найдите координату середины отрезка AB_

29. Если периметр квадрата 20 см, то его площадь_

30. Если диаметр круга 4 см, то его радиус_

31. Сколько вершин у куба?_Сколько ребер?_Сколько граней?_

32. Если сторона второго квадрата в 1,5 раза больше первого, то во сколько раз больше его периметр_, во сколько раз больше площадь?_

33. Если считать от первого вагона, то вагон-ресторан — 8-й, а если считать от последнего вагона, то вагон-ресторан — 7-й. Сколько вагонов в поезде?_

34. Бревно пилили 5 раз. Сколько кусков получилось?_

35. Сколько существует трехзначных чисел (от 100 до 999)?_

36. Деревни А, В и С расположены вдоль шоссе в указанном порядке. Расстояние от А до В в пределах от 3 до 4 км, расстояние от В до С — в пределах от 1 до 2 км. В каких пределах находится расстояние от А до С? От_до_

37. На карте указан масштаб 1:250000 (единицы измерения одинаковые). Расстояние между двумя пунктами на карте 1 см. Сколько это километров? _

38. Круглый пирог разрезали по 10-и различным диаметрам (от края до края через центр). Сколько кусков получилось? _

39. Квадратный пол со стороной 4 м покрывают квадратной кафельной плиткой со стороной 20 см. Плитки укладывают вплотную. Сколько плиток понадобится?_

40. За доллар дают 30 руб., за евро дают 36 руб. Сколько долларов дают за евро?_

1.2. Ответы к Тесту-разминке

1.

2, 3,5

21.

х = 4/3

2.

5/6

22.

х = 7/4

3.

Частное 8, остаток 4

23.

4,5 км/ч

4.

2 3/7

24. 25.

3,5 ч. 10,5 км

5.

11/4

26.

За 8 ч.

6.

0,125

27.

За 2 дня

7.

3/4.

28.

20

8.

Например: 0,105

29.

25 см2

9.

На 2/9

30.

2 см

10. 11.

В 3/2 раза Больше 5/7

31.

Вершин 8, ребер 12, граней 6

12.

10203040506070809

32.

Периметр — в 1,5 раза,

13.

НОД(84, 90) = 6

площадь — в 2,25 раза

14.

3/108 и 2/108

33.

14 вагонов

15.

24 руб.

34.

6 кусков

16.

40%

35.

900

17.

4,5

36.

От 4 до 6 км

18.

200

37.

2,5 км

19.

На 50%, на 100%.

38.

20 кусков

20.

х= 1,5

39. 40.

400 плиток

1 евро = 1,2 доллара

1.3. Тест № 1 (на 1 час)

Необходимо решить не менее 10 задач

1. Родители. В классе 26 учеников, они едут на экскурсию на автомобилях, в каждую машину, кроме водителя, помещается еще 4 ученика. Какое наименьшее число родителей (они же водители) нужно пригласить на экскурсию?_

2. Отец и сын. Отцу 36 лет, сыну 12 лет. Через сколько лет отец будет в 2 раза старше сына? _

3. Куб1. Куб со стороной 4 см покрасили целиком, а потом распилили на кубики со стороной 1 см. Сколько получилось кубиков, у которых покрашена ровно одна грань?_

4. Рюкзак. В поход идут 10 мальчиков и 10 девочек. Общий вес их рюкзаков 300 кг. Мальчикам положено нести рюкзаки одинаковые по весу, и девочкам тоже, но рюкзак у мальчика в 1,5 раза тяжелее, чем у девочки. Сколько будет весить рюкзак мальчика?_

5. Движение. Первый муравей бежал 1 час с постоянной скоростью, а второй бежал 1/2 часа в 2 раза быстрее первого, а еще 1/2 часа — в 2 раза медленнее первого. Какой из муравьев пробежал больший путь?_. Во сколько раз?_

6. Раствор. Имеется 100 г раствора соли концентрацией 7%. Сколько нужно добавить чистой воды, чтобы концентрация раствора стала 1%? _

7. Отрицание. Контрольную работу назовем легкой, если каждый ученик решил хотя бы 3 задачи. Как описать те контрольные работы, которые нельзя назвать легкими? Контрольная работа называется нелегкой, если _

8. Коды. Кодовый замок имеет 3 окошка, в каждом окошке можно выставить одну цифру от 0 до 9. Сколько различных кодов можно набрать на этом замке (цифры могут повторяться)?_

9. Роботы. 2 робота за 2 дня изготовили вместе 2 компьютера. Сколько компьютеров изготовят 10 роботов за 10 дней?_

10. Турнир. В турнире участвовало 10 команд. Каждая сыграла с каждой по одному разу. Сколько было проведено игр? _

11. НОК. Найдите наименьшее натуральное число, которое делится на каждое из чисел 2, 3, 4, 5, 6, 7, 8, 9, 10 (запишите ответ в виде произведения простых чисел)._

12. Картошка. Ведро неочищенной картошки рядовой Петров чистит за 4 часа, при этом очищенной картошки получается 80% ведра. За сколько часов он получит полное ведро очищенной картошки?

13. Часы. Стенные часы спешат на 2 минуты в час, а будильник отстает на 1 минуту в час. Вчера Петя поставил правильно и часы, и будильник. Когда он проснулся, стенные часы показывали 7 часов 30 минут, а будильник — 7 часов. Каково было точное время, когда Петя проснулся? _

14. Вифлеем. В газете было написано, что в Вифлееме 5 лет назад было 80% христиан и 20% мусульман (других конфессий практически нет). Сейчас число христиан уменьшилось в 2 раза, а число мусульман увеличилось на 30 тысяч (число жителей осталось прежним). Сколько христиан и сколько мусульман сейчас в Вифлееме?

15. Куб2. Куб со стороной 4 см покрасили целиком, а потом распилили на кубики со стороной 1 см. Сколько получилось кубиков, у которых покрашено ровно 2 грани?_

16. Куб0. Сколько получилось кубиков, у которых не покрашено ни одной грани?_

17. Кастрюли. Есть две кастрюли одинаковой высоты, но одна в 2 раза шире другой по диаметру. Во сколько раз больше воды в нее поместится? (Можно выяснить ответ без формул.) _

18. Доли. Петя набрал сочинение на компьютере, и оно заняло 4 страницы. Он изменил размер шрифта, и тогда сочинение заняло 5 страниц. На какой странице помещалось больше знаков: при исходном шрифте или при измененном? _. Во сколько раз?_

1.4. Ответы и указания к Тесту № 1

1. Родители. 7 чел. 27 : 4 = 6,5 — это значит, что 6 машин будут полными, а седьмая — на половину.

2. Отец и сын. Через 12 лет. 36 + х = 2(12 + х).

3. Куб1. 24 кубика. На каждой грани таких кубиков 4 (в середине), а граней 6.

4. Рюкзак. 18 кг. 10х — несут девочки, 15х — мальчики, 25х = 300 кг.

5. Муравьи. Второй больше в 1,25 раз. Если первый пробежал путь S, то второй за 1,2 ч пробежал S, и еще за 1/2 ч — 1/4S.

6. Раствор. 600 г. Если концентрация уменьшилась в 7 раз, то количество жидкости увеличилось в 7 раз, т.е. стало 700 г.

7. Отрицание. Хотя бы один ученик решил меньше 3-х задач. (Не каждый ученик решил хотя бы 3 задачи).

8. Коды. 1000 вариантов. В каждой ячейке 10 вариантов, каждому варианту в первой ячейке соответствуют 10 вариантов во второй, значит в двух ячейках 100 вариантов.

9. Роботы. 50 компьютеров. 10 роботов за 2 дня сделают 10 компьютеров.

10. Турнир. 45 игр. Каждая команда выходила 9 раз, команд 10, значит, было 90 выходов, но игра — это 2 выхода.

11. НОК. 23-32-5-7 = 2520. Надо каждое число разложить на простые множители, и для каждого множителя найти максимальную степень, в которой он входит в одно из чисел.

12. Картошка. 5 ч. Петров за 4 ч начистил 0,8 ведра картошки, значит, полное ведро он будет чистить в 10/8 раза дольше, т.е. 5 ч.

13. Часы. 7 ч 10 мин. Каждый час разница в показаниях часов увеличивается на 3 минуты. Когда Петя проснулся, то разница была 30 минут, значит, он спал 10 часов. За это время будильник отстал на 10 минут.

14. Вифлеем. 30 тыс. христиан и 45 тыс. мусульман. Число мусульман увеличилось на 40%, а это 30 тыс. Христиан стало 40%, значит, их стало 30 тыс., а мусульман в полтора раза больше.

15. Куб2. 24 кубика. На каждом ребре 2 таких кубика, граней 12.

16. Куб0. 8 кубиков. Не покрашенные кубики образуют куб 2×2×2.

17. Кастрюли. В 4 раза. В большую кастрюлю помещается две маленьких, да еще место остаётся. Чтобы угадать ответ, рассмотрим квадратные кастрюли.

18. Доли. При исходном шрифте знаков больше в 1,25 раз. Поскольку число знаков не меняется, то во сколько раз увеличится число страниц, во столько раз уменьшится число знаков на странице.

1.5. Тест № 2 (на 1 час)

Необходимо решить не менее 10 задач.

1. Войско. У полковника 10 майоров, у каждого майора 10 лейтенантов, у каждого лейтенанта 10 солдат. Какова численность войска (солдат и офицеров)?_

2. Карандаши. 2 дорогих карандаша стоят как 5 дешевых. Пете хватает денег на 20 дешевых карандашей. Сколько дорогих карандашей он сможет купить на эти деньги?_

3. Дроби. Укажите дробь, которая больше 3/7, но меньше 4/9 (числитель и знаменатель — целые числа)._

4. Максимум. Используя каждую цифру 0,1,2,3,4,5,6,7,8,9 только один раз, составьте два пятизначных числа, сумма которых наибольшая. Укажите эти числа._

5. Пешком. Если половину пути от дома до школы Петя идет пешком, а половину пути едет на автобусе, то он тратит на дорогу 30 минут, а если он весь путь едет на автобусе, то тратит 15 минут. Сколько минут Петя идет пешком весь путь от дома до школы?

6. Делимость. Сколько натуральных чисел от 1 до 1000 делятся и на 2, и на 3 одновременно?_

7. Частное. Во сколько раз изменятся частное и остаток, если делимое и делитель увеличить в 3 раза? (делимое = делитель х частное + остаток). Частное в_, остаток в_.

8. Границы. Известно, что 3 < а < 4, 1 < b < 2. В каких пределах может находиться их сумма? _ < а + b < _; разность? _ < а-b< _

9. Тракторы. 1 трактор вспахивает 3 га за 8 часов. За какое время 10 тракторов вспашут 105 га?_

10. Гуси. Летела стая гусей, а навстречу гусь. Он и говорит: «Здравствуйте, 100 гусей!». А ему отвечают: «Если бы нас было еще столько же, да еще полстолько, да еще четверть столько, да еще ты, гусь, то нас было бы 100». Сколько гусей в стае?_

11. Гномы. По кругу стоят 12 гномов, которые либо правдивы, либо вруны. Каждый сказал своему соседу справа: «Ты врун». Сколько гномов сказали правду?_

12. Отрицание. Некто говорит: «Неверно, что существует охотник, который ни разу в жизни не попал в цель». Перескажите эту фразу так, чтобы ее смысл остался тем же, но она начиналась со слов: «Верно, что_

13. Делёж. Три охотника варили кашу. Первый положил в котел 2 пакета крупы, второй положил 1 пакет, а у третьего крупы не было. Они съели кашу поровну. Третий охотник предложил задачу: «Даю вам 5 патронов. Поделите их в соответствии с тем, как вы меня накормили». Сколько патронов получат охотники? Первый_, второй _

14. Кубик. Кубик со стороной 3 см составлен из 27 кубиков со стороной 1 см. Соседние кубики (с общей гранью) имеют разный цвет, целиком белый или черный. Один из угловых кубиков белый. Сколько всего белых кубиков_, черных кубиков?_

15. Развертки. Бумажный кубик разрезали по некоторым ребрам и развернули на плоскость. Какие фигуры являются развертками куба (Рис. 1.)? Укажите буквы:_

Фигуры можно сгибать по сторонам квадратов

Рис. 1.

16. Ряд. На пустые места 13______19 поставьте числа (возможно, равные) так, чтобы сумма каждых трех чисел, стоящих подряд, равнялась 50.

17. Нули. Сколькими нулями оканчивается обычная десятичная запись числа 2 *5 1_

18. Гири. Укажите веса семи гирь, с помощью которых можно взвесить любой груз в целое число граммов от 1 г до 100 г. (Гири можно класть только на одну чашу весов)._

1.6. Ответы и указания к Тесту № 2

1. Войско. 1111.1 + 10+ 100+1000.

2. Карандаши. 8 штук. 2а = 5b; 20b = 4(5b) = 4(2а) = 8а.

3. Дроби. 55/126 или 7/16 или 275/630. Приведем к общему знаменателю: 27/63 < X < 28/63; 270/630 < х < 280/630.

4. Максимум. Укажем один из 16 возможных вариантов слагаемых: 97531 + 86420. Цифры 9 и 8 стоят в первых разрядах, 7 и 6 стоят во вторых разрядах и т.д.

5. Пешком. 45 минут. Если заменить время «пешком» на время «автобусом», то экономится 15 минут. Значит, если заменить время «автобусом» на время «пешком», то прибавится 15 минут.

6. Делимость. 166. Это числа делящиеся на 6, т.е. каждое шестое число. 1000 при делении на 6 дает частное 166.

7. Частное. Частное не изменится, а остаток возрастет в 3 раза. У Пусть а = вс + d, где с — частное, d — остаток, тогда За = (3в)с + 3d.

8. Границы. 1 < а — b < 3. Разность наименьшая, когда а — наименьшее, b — наибольшее.

9. Тракторы. 28 ч. Скорость работы 10 тракторов 30/8 га/ч. Время вспашки 105/(30/8)= 105*8/30 = 28.

10. Гуси. 36 гусей. Если х — размер стаи, то х + х + х/2 + х/4 + 1 = 100.

11. Вруны. 6 правдивых. Все врунами быть не могут, поскольку врун про вруна на может сказать правду. Начнем с правдивого. Тогда следующий врун. А после вруна опять правдивый и т.д. Каждый второй правдивый.

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

13. Делёж. 5 и 0. Каждый съел по 1 пакету. Второй охотник положил 1 пакет и съел 1 пакет. Он накормил только самого себя.

14. Кубик. 14 белых и 13 черных. На одной грани мы видим 5 белых и 4 черных кубика. В следующем за этой гранью слое кубиков будет наоборот 4 белых и 5 черных. В третьем слое будет опять 5 белых и 4 черных.

15.Развертки, а, г, е. Надо один из квадратиков принять за основание куба, затем отметить, какие из квадратиков являются боковыми гранями, а какой — крышкой.

16. Ряд. 13 18 19 13 18 19 13 18 19. Рассмотрим первые три числа и три числа, начиная со второго. У них есть два общих числа, сумма которых 37. Следовательно четвертое число совпадает с первым и равно 13. Аналогично, седьмое число равно 13.

17. Нули. 20 нулей. Сгруппируем двойки пятерки парами. Получится 20 пар.

18. Гири. Например, 1, 2, 4, 8, 16, 32, 64. Если надо взвесить 1 г, то хватит одной гири в 1 г. Если надо взвесить еще 2 г, то нужна еще одна гиря, например 2 г. Тогда можно взвесить и 3 г. Если надо взвесить 4 г, то нужна еще одна гиря, например, 4 г. Теперь можно взвесить любой вес от 1 до 7 г. Нужна гиря 8 г. Теперь можно взвесить все веса до 15 г и т.д.

1.7. Математические игры

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

1. Камни 1. В куче 20 камней. Двое по очереди берут из кучи 1 или 2 камня по своему выбору. Проигрывает тот, кому нечего брать.

Кто выиграет при правильной игре, и как надо играть? А если камней 21?

2. Камни 2. Есть две кучи камней, 10 и 15 камней, и 2 игрока, которые за ход могут взять любое число камней, но только из одной кучи. Проигрывает тот, кому нечего брать. Кто выиграет при правильной игре?

3. Камни 3. Есть 2 кучи камней, 10 и 12 камней. За ход разрешается разделить любую кучку на две меньшие. Проигрывает тот, кто не сможет сделать ход. Кто выиграет?

4. Крестики-нолики 1. Найдите для первого игрока выигрышную стратегию в игре крестики-нолики «3 в ряд» на нарисованной доске.

5. Пятаки. Двое по очереди кладут пятаки на круглый стол так, чтобы монеты не не накрывали друг друга. Кто не может положить монету — проигрывает. Кто выиграет при правильной игре?

6. Кони. Двое по очереди ставят на шахматную доску 8×8 по одному коню на поле, которое не бьют другие кони. Кто не сможет поставить коня — проиграл. Кто выиграет при правильной игре? А если доска размером 7×7?

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

8. Фокус. Кот Базилио предложил игру. Буратино кладёт на стол 10 золотых монет: 5 гербом вверх и 5 гербом вниз. Затем любые 5 монет он закрывает рукой, а Кот Базилио, не глядя, переворачивает несколько из оставшихся пяти монет. Если число монет, лежащих гербом вверх, под рукой у Буратино будет равно числу монет, лежащих гербом вверх, среди оставшихся, то Кот забирает себе монеты, а если не равно, то Кот даёт Буратино свои 10 монет. Почему Кот гарантированно выиграл?

9. Сумма. Даны 10 чисел: -1,2, -3, 4, -5, 6, -7, 8, -9, 10. Двое по очереди выбирают по одному числу, пока числа не кончатся. Затем

каждый складывает свои 5 чисел. Побеждает тот, у кого сумма больше по абсолютной величине. Докажите, что первый всегда сможет выиграть.

10. Ладьи 1. Двое по очереди ставят на шахматную доску ладьи так, чтобы ни одна ладья не била другую. Кто не сможет поставить ладью, тот проиграл. Кто выиграет?

11. Шоколадка. Двое по очереди ломают плитку шоколада размером 5×8 долек. Они отламывают вдоль канавок по прямой от любого уже полученного куска любой возможный кусок. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре: начинающий или его партнер?

12. Ладьи 2. Двое ставят ладьи на шахматную доску. Проигрывает тот, после чьего хода вся доска оказывается побитой ладьями. Кто выигрывает?

13. Король. Король стоит на поле h8. Разрешается за ход сдвинуть его вниз или влево. Выигрывает тот, кто поставит короля на a1. Кто выиграет при правильной игре? А если король стоял на f8?

14. Хорды. На окружности лежат 20 точек. За ход можно соединить любые две из них хордой так, чтобы она не пересекала проведенные ранее хорды. Разрешается, чтобы хорды выходили из одной точки. Проигрывает тот, кто не сможет провести хорду. Кто выиграет: начинающий или его партнер?

15. Тупик. На плоскости отмечено 6 точек. Двое по очереди соединяют две точки, причем каждый проводит очередной отрезок из той точки, где закончил партнер. Кто не может провести отрезок, — тот проиграл. Отрезки могут пересекаться. Кто выиграет при правильной игре? (Любые две точки можно соединять только один раз).

16. Ломаная. На окружности дано 99 точек. Двое по очереди соединяют отрезками любые две точки, не соединенные ранее. Каждый хочет построить замкнутую ломаную. Кто выиграет при правильной игре? (Отрезки могут пересекаться.)

17. Минусы. Играют двое. Перед ними на бумаге в цепочку написано несколько минусов. Каждый по очереди переправляет 1 или 2 соседних минуса на плюс (минусы соседние, если стоят рядом). Выигрывает тот, кто переправит последний минус. Кто выигрывает при

правильной игре: начинающий или его партнер, и как надо играть, если вначале написано: а) 7 минусов; б) 8 минусов; в) к минусов?

18. Ромашка. Двое по очереди отрывают лепестки у ромашки: 1 или 2 рядом растущих лепестка. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре, если у ромашки а) 38 лепестков, б) 39 лепестков?

19. Крестики-нолики 2. Игра в крестики-нолики на доске 10×10. Двое ходят по очереди, пока доска не заполнится. За каждую пятерку, стоящую подряд (возможно, по диагонали), дается очко. Кто выигрывает при правильной игре?

20. Перехват. Остап Бендер решил дать сеанс одновременной игры Карпову и Каспарову. Один из них должен играть белыми, а другой — черными. Остап уверен, что он или сведет обе партии к ничье, или одну выиграет. Как он собирается играть?

21. Ладьи 3. В противоположных углах клетчатой доски 8×8 ставятся черная и белая ладьи, остальные поля заполняются серыми пешками. Два игрока ходят по очереди, каждый своей ладьей. Начинают белые. Каждым ходом игрок обязан что-нибудь съесть: серую пешку или ладью противника. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?

22. Волк и овцы. Игра происходит на бесконечной плоскости. Играют двое: один передвигает одну фишку-волка, другой — 50 фишек-овец. После хода волка ходит какая-нибудь из овец, затем после следующего хода волка опять какая-нибудь из овец и т.д. И волк, и овцы передвигаются за один ход в любую сторону не более чем на один метр. Верно ли, что при любой первоначальной позиции волк поймает хотя бы одну овцу?

23. Окружение десанта. Двое играют на бесконечной клетчатой плоскости. Первый ставит крестики, причем обязательно в клетку, соседнюю с каким-либо крестиком, а второй ставит сразу по 3 нолика в любые места доски. Смогут ли нолики окружить крестики? Изучите общий случай такой игры (если за ход ставится n ноликов).

24. Красный квадрат. На бесконечном листе клетчатой бумаги играют двое: первый окрашивает произвольную клетку в красный цвет, второй окрашивает произвольную не закрашенную клетку в

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

25. Игра в раскраску. Играют двое. Первый на листе бумаги рисует по одному кружку и соединяет очередной кружок, если хочет, с предыдущими кружками. Линии могут быть любой формы, но они не должны пересекаться. Второй раскрашивает очередной кружок в какой-то цвет, но так, чтобы кружки, соединенные линией, имели разный цвет. Первый выигрывает, если он заставит второго использовать больше, чем заданное число цветов. Может ли первый выиграть, если у второго в запасе 4 цвета? 5 цветов? n цветов?

1.8. Указания к играм

1. Камни 1. Заметим, что число камней, взятых любым игроком, другой игрок может дополнить до числа делящегося на 3. Отсюда стратегия первого игрока: взять сначала два камня, чтобы оставшаяся сумма делилась на 3, затем дополнять ходы противника до трех камней, тогда последний ход будет за первым игроком. Контрольный вопрос: верно ли, что при любом начальном числе камней выиграет первый игрок?

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

3. Камни 3. Хода не будет только в том случае, когда все кучи размером в один камень. При каждом ходе число куч возрастает на 1. Чтобы из двух куч сделать 22 нужно увеличить число куч на 20, следовательно, нужно сделать 20 ходов. Но 20-й ход делает второй игрок, значит, он всегда выигрывает. _

4. Крестики-нолики 1. Первый выигрышный ход указан на рисунке. Второй выигрышный ход делается в соседнюю клетку либо слева, либо сверху.

4. Пятаки. Первый кладет пятак в центр, а затем делает ходы симметричные ходам второго относительно центра стола.

5. Кони. На обычной доске выиграет второй, поскольку он может делать ходы, центрально симметричные ходам первого. На доске 7×7 первый делает ход в центр, а затем использует симметричную стратегию.

6. Дубликаты. Пусть Винни Пух придумал все слова Пятачка и еще 5 слов. Пусть Винни Пух называет слова, которых нет у Пятачка, тогда после пятого хода все слова будут названы, и Винни Пух не сможет сделать хода.

7. Фокус. Кот перевернул все оставшиеся монеты и выиграл. Почему?

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

9. Ладьи 1. Докажите, что таких ладей всегда будет 8, следовательно, всегда побеждает второй.

10. Шоколадка. Докажите, что число разломов всегда одно и то же, следовательно, всегда выигрывает один и тот же игрок. См. задачу «Камни3».

11. Ладьи 2. Второй использует симметричную стратегию.

12. Король. Решаем задачу с конца. На поле a1 ставим «+», что означает выигрышное поле. На поля b1 и а2 ставим «-», поскольку тот, кто поставил короля на эти поля — проиграл. И т.д. раскрасим плюсами и минусами всю доску.

13. Хорды. Первую хорду надо провести так, чтобы по обе стороны от нее было поровну точек, а дальше применять симметричную стратегию.

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

15. Ломаная. Ясно, что нельзя строить ломаную из двух звеньев, поскольку партнер сделает треугольник. Каждым ходом надо выбирать две новые точки, которые не использовались ранее. Таких пар точек 49. Пятидесятый ход, а его делает второй игрок, будет проигрышным.

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

17. Ромашка. Первым ходом круг разрывается, и задача сводится к предыдущей.

18. Крестики-нолики 2. Первый ход делается куда угодно, а затем первый применяет симметричную стратегию относительно центра доски. Если ему надо сделать ход туда, где уже стоит крестик, то он делает произвольный ход.

19. Перехват. Пусть Карпов пошел белыми, тогда Бендер делает такой же ход против Каспарова. Каспаров ответил, а Бендер делает такой же ход против Карпова, и фактически заставляет гроссмейстеров играть между собой. Победа одного из них приведет и к победе Бендера.

20. Ладьи 3. Черные применяют симметричную стратегию. Однако надо доказать, что она приведет к цели.

21. Волк и овцы. Пусть волк стоит в точке с координатами (0; 0), а овцы в точках (4n; 0). Овце с номером n принадлежит полоса х е [4n-2; 4n+2). Как только волк проникает в полосу с номером n, овца с номером n начинает двигаться вертикально в сторону удаления от волка. Остается доказать, что волк останется ни с чем.

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

23. Красный квадрат. Если противник не дает сделать квадрат некоторого размера, то надо удваивать сторону квадрата.

24. Игра в раскраску. Есть известная теорема о раскраске карт, из которой следует, что если первый заранее нарисует все кружочки, то второй сможет их раскрасить не более, чем в 4 цвета. Но если первый задает второму определенный порядок раскраски и конструирует карту по ходу игры, то первому может не хватить никакого ко-

немного числа цветов. Достаточно доказать, что если первый может создать карту, у которой есть n кружочков разного цвета, которые можно соединить с новым кружочком, то он может создать карту, у которой есть n+1 кружочков разного цвета, которые можно соединить с новым кружочком. Действительно, сделаем две карты, у каждой из которых есть n доступных цветов. Если их объединение содержит n+1 цвет, то задача решена, а если наборы цветов совпадают, то к одной из карт добавим новый кружок, соединенный со всеми n цветами. Получим n+1-й цвет, который вместе со второй картой даст карту с n+1 доступным цветом.

2. Элементы теории некооперативных игр

2.1. Примеры и понятия

Чтобы мотивировать дальнейшее изложение рассмотрим следующую ситуацию.

Игра 1. «Выбор компьютера». Двое приятелей одновременно и независимо друг от друга идут покупать компьютеры. При этом они решают, какого типа компьютеры им купить. Первый предпочитает IBM PC, второй — Макинтош. Обладание компьютером любимого типа первый оценивает в а (а > 0) некоторых условных единиц (у.е.), а второй — в b (b > 0) у.е. Ценность компьютера другого типа для обоих будем считать равной нулю. Каждый приятель получает дополнительную выгоду (с > 0), если они выберут одинаковые компьютеры, поскольку в таком случае используемое ими программное обеспечение будет совместимым. Наша задача — понять, какой выбор сделают приятели при различных значениях величин a, b, и с.

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

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

ных субъектов, выбирающих наилучшие (с их точки зрения) альтернативы из тех, которые для них доступны в данной ситуации.

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

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

2.2. Статические игры с полной информацией

Проанализируем, какие трудности мы можем встретить при анализе рассмотренной выше ситуации (игры), которую мы назвали «Выбор компьютера».

Чтобы упростить анализ, сведем известную нам (и игрокам) информацию в таблицу — своего рода табличную (матричную) модель этой игры.

Каждый из игроков (назовем их «Игрок 1» и «Игрок 2») может принять одно из двух решений (или, как говорят, выбрать одну из двух стратегии), которые можно условно назвать «IBM» и «Mac». Описанную игру удобно представить в виде таблицы (матрицы) 2х 2. В игре имеется четыре исхода: (IBM, IBM), (IBM, Mac), (Mac, IBM) и (Mac, Mac), где сначала указывается выбор Игрока 1, а затем выбор Игрока 2. Ситуация — это любой набор стратегий всех игроков.

Все варианты ситуаций

s

Игрок 2

IBM

Mac

Игрок 1

IBM

(IBM, IBM)

(IBM, Mac) (Mac, Mac)

Mac

(Mac, IBM)

Запись решений в виде (IBM, IBM) напоминает запись координат точек на плоскости, и эта аналогия справедлива, хотя вместо точек мы рассматриваем клетки, а значения координат могут быть не только числами. Физики назвали бы такую запись пространством состояний системы или фазовым пространством.

Все варианты выигрышей

В

Игрок 2

IBM

Mac

Игрок 1

IBM

с

а+с

b

а

Mac

0

0

b+с

с

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

В рассмотренном примере можно выделить три элемента:

• множество игроков (Игрок 1, Игрок 2);

• множество стратегий, которые игроки могут применять («IBM» и «Mac»);

• выигрыши игроков в каждой ситуации.

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

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

Множество игроков будем обозначать I: I = {1, ..., m}.

Множество возможных стратегий i-го игрока (или множество стратегий i-го игрока) будем обозначать через Xi.

Отдельную стратегию i-го игрока будем, как правило, обозначать через xi.

Исходом игры будем называть совокупность стратегий, выбранных всеми игроками, т.е. исход игры — это набор стратегий x = (x1, ..., xm).

Будем предполагать, что у каждого игрока есть своя система ценностей или, как говорят, своя функция выигрыша. Функцию выигрыша i-го игрока обозначим через ui(х). Каждому исходу игры она сопоставляет некоторое действительное число — выигрыш. Таким образом, в описании игры следует задать для каждого игрока функцию выигрыша (иногда говорят — целевую функцию).

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

2.3. Концепция доминирования

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

Такая ситуация имеет место в игре «Выбор компьютера», если выгода от совместимости программного обеспечения (с) сравнительно мала, например, в случае, когда а = 2, b = 3, с = 1.

Доминирующие стратегии

s

Игрок 2

IBM

Mac

Игрок 1

IBM

с = 1

а+с = 3

b=1

а = 2

Mac

0

0

b+с = 4

с = 1

Тогда, если Игрок 2 выберет «IBM» (что соответствует левой колонке таблицы), то Игроку 1 выгоднее выбрать «IBM», чем «Mac» (поскольку 3 > 0). Если Игрок 2 выберет «Mac» (правая колонка), то Игроку 1 все равно выгоднее выбрать «IBM», чем «Mac» (поскольку 2> 1).

Иначе говоря, вне зависимости от того, какой компьютер выберет Игрок 2, Игроку 1 выгодно выбрать компьютер IBM PС. Аналогично, Игрок 2 предпочтет Макинтош, поскольку 3 > 1 и 4 > 0.

В каждом столбце (т.е. при заданной стратегии Игрока 2) для Игрока 1 подчеркнем самое большое значение выигрыша (в данном случае это а+с=3 и а=2).

В каждой строке (т.е. при заданной стратегии Игрока 1) для Игрока 2 подчеркнем самое большое значение выигрыша (в данном случае это b=3 и b+с=4).

Для каждого игрока имеет место так называемое строгое доминирование стратегий.

Определения

Если стратегия xi игрока i при любых действиях других игроков дает ему больший выигрыш, чем его стратегия у4, то говорят, что стратегия xi строго доминирует стратегию yi.

Дадим формальное определение строгого доминирования. Здесь и в дальнейшем мы будем применять обозначение x-i что означает «все элементы наборах, кроме i-го», т.е.

При этом будем считать, что (xi, x-i) — это то же самое, что х.

Стратегия xi игрока i строго доминирует стратегию у, этого же игрока, если при любых стратегиях x-i, выбранных остальными игроками, выполнено условие:

(т.е. выигрыш отх, всегда больше выигрыша от yi)

Стратегия xi, игрока i является его строго доминирующей стратегией, если при любых стратегиях, выбранных остальными игро-

ками х-i, она дает игроку i больший выигрыш, чем любая другая его стратегия yi, т.е.

(Строго доминирующая стратегия игрока строго доминирует любую другую его стратегию).

В соответствие с данным определением не может существовать более одной строго доминирующей стратегии.

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

Игра 2. «Дилемма заключенного». Игра представляет знаменитый пример ситуации, которая в дальнейшем будет встречаться в разных вариантах. Опишем ее классический вариант, который дал название целому классу подобных ситуаций.

Два индивида, подозреваемых в совершении тяжкого преступления, могут быть осуждены на срок в 25 лет в том случае, если следствию удастся доказать факт совершения преступления. Следователи убеждены в виновности подозреваемых, но без сотрудничества с ними (по крайней мере, одного из них), не способны доказать их виновность. Поэтому следователи идут на сделку с подозреваемыми, предложив каждому из них сотрудничество в обмен на снижение срока наказания — до 10 лет каждому из подозреваемых, если сотрудничать со следствием согласятся оба подозреваемых, и — до 1 года (согласившемуся на сотрудничество подозреваемому), если сотрудничать согласится только один из них. При отказе от сотрудничества обоих подозреваемых существующие улики позволяют осудить обоих обвиняемых только на срок до 3 лет.

Задача 1. Охарактеризуйте описанную ситуацию в виде игры (игроки, их стратегии, матрица выигрышей). Какие стратегии, по Вашему мнению, выберут игроки, и каким при этом будет исход игры?

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

Доминирующие стратегии

Дилемма заключенного

Игрок 2

Отказаться

Согласиться

Игрок 1

Отказаться

-3

-3

-25

Согласиться

-25

-10

-10

У каждого игрока есть строго доминирующая стратегия «согласиться на сотрудничество».

Замечание. «Дилеммой заключенного» называется любая игра двух лиц, матрица выигрышей которой симметрична и имеет вид, представленный в таблице, причем d > а — b. Ее особенность — наличие у каждого игрока строго доминирующей стратегии и тот факт, что существуют ситуации, в которых выигрыши каждого игрока выше, чем при выборе доминирующих стратегий.

Обобщенная дилемма

Игрок 2

Стратегия 1

Стратегия 2

Игрок 1

Стратегия 1

а

а

а + с

а-b

Стратегия 2

а-b

а + с

d

d

Задача 2. Проверьте, что выбор стратегий в обобщенной «дилемме заключенного» полностью аналогичен рассмотренному частному случаю.

Ответ. Оба выберут Стратегию 2, так как она является доминирующей стратегия для обоих игроков.

Задача 3. В чем Вы видите сходство и различие между решениями игр «Дилемма заключенного» и «Выбор компьютера»? Можете ли Вы предложить ситуации, которые аналогичны «Дилемме заключенного»?

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

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

Определение

Стратегия хi игрока i доминирует (слабо доминирует) его стратегию yi, если при любых стратегиях, выбранных остальными игроками x-i, выполнено

и существует хотя бы один набор стратегий других игроков, такой что

Иначе говорят, что стратегия у, доминируется стратегией xi.

Определение

Стратегия хi игрока i является его доминирующей стратегией (слабо доминирующей), если при любых стратегиях, выбранных остальными игроками, x-i, она доминирует (слабо доминирует) любую другую его стратегию yi, либо эквивалентна ей, т.е.

Из определения следует, что строгое доминирование является частным случаем доминирования.

Определение

Исход игры x* является равновесием в доминирующих стратегиях, если стратегия каждого игрока в этом исходе является его доминирующей стратегией.

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

Игра 3. «Аукцион Викри». Некий предмет продается с аукциона. Каждый из окупателей (i = 1, ..., m) подает в тайне от других свою заявку — предлагаемую им цену pi. Побеждает участник, предложивший самую высокую цену, но платит он самую большую цену, предложенную другими покупателями. Если самую высокую цену предложат сразу несколько участников, то победитель определяется жребием.

Другими словами, если i-й участник окажется победителем, то его выигрыш составит vi—р, где vi — ценность для него данного предмета, р — цена, которую он должен заплатить (выигрыш остальных покупателей будет равен нулю).

Особенность аукциона Викри состоит в том, что «правдивая» стратегия является доминирующей стратегией для каждого участника. «Правдивая» стратегия заключается в том, что участник называет цену, совпадающую с ценностью для него данного предмета (рi = vi).

Проверим это. Сначала проанализируем данную игру в случае, когда есть всего два участника (m = 2), а предлагаемые цены (заявки участников) могут принимать только конечное число значений.

Пусть, например, v1 > v2, и v1 — v2 = 1. Предположим, что заявки могут принимать значения v1—2, v1-1, v1, v1 + 1 или, в других обозначениях V2—1, v2, v2+l, v2+2.

Задача 4. Опишете игру, соответсвующую аукциону Викри (укажите игроков, их стратегии и функции выигыша).

Ответ. Если при равенстве заявок предмет получает любой участник с вероятностью 1/2 и если его выигрыш оценивается (средней) величиной, то матрица выигрышей имеет вид:

Аукцион Викри

Игрок 2 (выбор p2)

v2-l = vi-2

v2= Vi-1

v2+1 = v1

v2+2 = v1+1

Игрок 1 (выбор p1)

v1-2

(ничья) 1/2

1

1

0

1

0

1

0

V1-1

0

2

(ничья) 0

1/2

0

0

0

0

V1

0

2

0

i

(ничья) -1/2

0

-1

0

v1+1

0

2

0

I

0

0

(ничья)-1

-1/2

Например, в левой верхней клетке, если выиграет Игрок 1, то его выигрыш составит 2, но поскольку он выигрывает с вероятностью V2, то его средний выигрыш равен 1.

Стратегия pi = vi является доминирующей (но не строго доминирующей) стратегией каждого участника аукциона. Поэтому в данной игре существует равновесие в доминирующих стратегиях

Задача 5. Проверьте, что «правдивые» заявки являются доминирующими стратегиями каждого игрока, но не строго доминирующими стратегиями.

Вернемся к анализу аукциона с любым числом участников, в котором участники не ограничены в выборе заявок. Покажем, что утверждение задачи 5 имеет место и в случае, когда нет ограничений на величину заявок участников. Для простоты будем по-прежнему предполагать, что в аукционе два участника. (При большем количестве участников рассуждения будут аналогичными).

Поскольку участники входят в данную игру симметрично, то достаточно рассмотреть мотивацию только одного из них, например, 1-го.

Вычислим сначала выигрыши Игрока 1 при разных исходах. Если Игрок 1 назовет более высокую цену, чем Игрок 2 (р1 > р2), то он выиграет аукцион и заплатит р2. При этом его выигрыш составит v1 — p2. Если Игрок 1 назовет более низкую цену, чем Игрок 2 (p1 < p2), то он проиграет аукцион и получит выигрыш 0. Если цены совпадут (р1 = р2), то с вероятностью 1/2 Игрок 1 получит выигрыш v1 — р2,ас вероятностью 1/2 он выигрыш 0. Таким образом, его ожидаемый выигрыш составит (v1 — р2)/2. Окончательно запишем функцию выигрыша Игрока 1 :

Чтобы показать, что «правдивая» стратегия, р1 = v1 является доминирующей, нужно показать, что она дает не меньший выигрыш, чем любая другая стратегия. Следует рассмотреть 3 случая: p2>v1, p2 = v1 и p2<v1.

Случай p2 > v1. В этом случае Игроку 1 не выгодно выигрывать аукцион, поскольку его выигрыш был бы отрицательный, а в случае проигрыша он получит 0. Поэтому «правдивая» стратегия является одной из оптимальных.

Случай p2 = v1. В этом случае Игрок 1 получит 0. Значит, «правдивая» стратегия даст ему выигрыш не меньший, чем любая другая.

Случа p2 < v1. В этом случае Игроку 1 выгодно выиграть аукцион, поскольку его выигрыш будет положительным. «Правдивая» стратегия обеспечивает ему максимальный выигрыш, v1 — р2.

Мы видим, что «правдивая» стратегия, в самом деле, является доминирующей для Игрока 1. Более того, как несложно увидеть, это единственная доминирующая стратегия. Если он назовет цену ниже или выше своей оценки v1, то можно подобрать такую цену Игрока 2, что Игрок 1 потеряет по сравнению с p1=V1.

Проведя аналогичные рассуждения для Игрока 2, мы сделаем вывод, что в этой игре существует (единственное) равновесие в доминирующих стратегиях:

p1 = v1, p2 = v2.

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

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

Рассмотрим игру «Выбор компьютера»в случае, когда а< с< b. Пусть, к примеру, а = 1, с = 2, b = 3.

s

Игрок 2

IBM

Mac

Игрок 1

IBM

с=2

а+с=3

b=3

а=1

Mac

0

0

b+с=5

с=2

Если Игрок 2 выберет IBM, то Игроку 1 тоже выгодно выбрать IBМ. Если же Игрок 2 выберет Макинтош, то Игроку 1 будет выгодно выбрать Макинтош. Эти оптимальные решения выделены в матрице выигрышей подчеркиванием соответствующих выигрышей. Здесь для Игрока 1 оптимальное решение зависит от того, какое решение примет Игрок 2.

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

образом: рациональный игрок не станет выбирать строго доминируемую стратегию.

Определение

Стратегия уi игрока i называется строго доминируемой, если существует стратегия xi, которая ее строго доминирует при любых стратегиях других игроков, т.е.

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

Примером такой ситуации является известная игра «Битва в море Бисмарка».

Игра 4. «Битва в море Бисмарка». В 1943 году японский адмирал получил приказ о переброске войск и военного снаряжения на Новую Гвинею. Он мог выбрать северный либо южный маршрут. Командованию ВВС США удалось узнать о дате такой переброски, но не о выбранном маршруте. И оно не имело достаточного числа самолетов-разведчиков, чтобы установить, какой из двух возможных маршрутов был выбран, чтобы потом направить туда бомбардировщики. В том случае, если самолеты-разведчики командованием ВВС были бы посланы искать транспорт в неверном направлении, этот день был бы потерян для работы бомбардировщиков. Но в таком случае самолетам-разведчикам удалось бы обнаружить транспорт на следующий день, и уже после этого настала бы очередь бомбардировщиков. Известно, что время плавания японского транспорта составляло три дня. Но северный маршрут отличался неустойчивой погодой, и по прогнозу погоды на третий день там ожидалась нелетная погода, так что командование ВВС полагало, что в этот день самолеты не смогут бомбить японский транспорт, если для него будет выбран северный маршрут.

Задача 6. Опишите игроков и их стратегии в этой игре. Считая, что командование ВВС США стремилось максимизировать число дней бомбардировки японского транспорта, а японский адмирал -минимизировать число дней бомбардировки, какой будет матрица выигрышей в данной игре? Какие стратегии, по Вашему мнению, выберут игроки, и каким будет исход этой игры?

Мы рассмотрели примеры игр, когда, по крайней мере, у одного из игроков есть доминирующая стратегия. Теперь перейдем к анализу игр, не обладающих данным свойством.

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

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

Игра 5. «Монополистическая конкуренция». Предположим, что в небольшом городке существует всего две пиццерии — «Нью-Йорк пицца» и «Итальянская пицца». Каждая из них может установить либо высокую, либо среднюю, либо низкую цену на свою продукцию, получая при этом 12, 10 и 5 рублей прибыли с каждой проданной пиццы. Из 10 тысяч потенциальных покупателей пиццы (каждый из которых покупает одну пиццу в неделю) 3 тысячи будут покупать продукцию «Нью-Йорк пицца», по какой бы цене она ни продавалась. Другие 3 тысячи — продукцию «Итальянской пиццы». Оставшиеся 4 тысячи будут предпочитать более дешевую пиццу. Владельцы пиццерий считают также, что если они установят те же

цены, что и их конкуренты, им удастся продать 5 тысяч пицц (т.е. две дополнительные тысячи штук к тем трем тысячам, которые в любом случае купят их «приверженцы»).

Задача 7. Опишите стратегии игроков в этой игре и матрицу выигрышей. Какие стратегии, по Вашему мнению, выберут игроки и каким будет исход этой игры?

Решение. Матрица выигрышей данной игры имеет вид:

Монополистическая конкуренция

Итальянская пицца

Низкая

Средняя

Высокая

Нью-Йорк пицца

Низкая

25

25

30

35

36

35

Средняя

35

30

50

50

36

70

Высокая

35

36

70

36

60

60

Проиллюстрируем процедуру отбрасывания доминируемых стратегий. Заметим, что какую бы цену не выбрал Игрок 2, Игроку 1 невыгодно выбирать низкую цену, т.е. его стратегия «Выбрать низкую цену» является доминируемой. Зачеркнем в каждом столбце доминируемую стратегию для 1-го игрока. Аналогично Игроку 2 невыгодно выбирать низкую цену. Зачеркнем в каждой строке доминируемую стратегию для 2-го игрока Понимая это, оба игрока будут рассматривать только среднюю и высокую цены. С учетом этого факта матрицу выигрышей можно свести к виду:

Монополистическая конкуренция

Итальянская пицца

Средняя

Высокая

Нью-Йорк пицца

Средняя

50

50

36

70

Высокая

70

36

60

60

В этом случае стратегия «Выбрать среднюю цену» оказывается доминирующей (а стратегия «Выбрать высокую цену» — домини-

руемой) стратегией каждого игрока. Поэтому, отбрасывая доминируемые стратегии на втором этапе, мы приходим к набору из единственной стратегии каждого игрока. В итоге, оба игрока выберут среднюю цену.

Игра 6. «Конкуренция на рынке однородного товара». Предположим, что в небольшом городке существует всего две фирмы, производящие стиральный порошок. Покупатели не различают продукцию этих фирм и готовы купить q тысяч пакетов порошка по цене р = 14 — q рублей за пакет.

Задача 8. Какое количество пакетов будут производить обе фирмы, если производство порошка обходится каждой фирме в 2 рубля за пакет (в целях упрощения анализа будем считать, что каждая фирма может производить только число пакетов, кратное одной тысяче (0, 1, 2, 3, ... тысяч пакетов))?

Игра 7. «Выборы большинством голосов с решающим голосом одного из игроков при равенстве голосов». Комитет, состоящий из трех человек, после окончания срока полномочий старого председателя должен выбрать в качестве председателя (на новый срок) одного из своих членов. Правило выбора следующее: председателем на новый срок окажется тот член комитета, который получит большинство голосов; в случае равенства голосов председателем назначается тот член комитета, которого предлагает старый председатель. Припишем членам комитета порядковые номера — 1, 2, 3; номер 1 получает старый председатель.

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

чтобы это место занял старый председатель, а не второй член комитета.

Задача 9. Кто, по Вашему мнению, станет председателем комитета на новый срок при такой процедуре выборов председателя?

2.5. Равновесие по Нэшу

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

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

Формально равновесие по Нэшу определяется следующим образом.

Определение

Набор стратегий x является равновесием по Нэшу,1 если стратегия каждого игрока xi является наилучшим для него откликом на данные стратегии других игроков

Для нахождения равновесий по Нэшу удобно использовать так называемый отклик. Отклик Ri(x-i) игрока i на стратегии x-i других игроков — это стратегия (или несколько стратегий) игрока i, которая дает ему максимальный выигрыш при условии, что другие игроки используют стратегии x-i. Другими словами, каждая стратегия

1 Американский математик Джон Нэш получил Нобелевскую премию по экономике в 1994 г. вместе с Дж. Харшаньи и Р. Зельтеном «за новаторский анализ равновесий в теории некооперативных игр».

xi e Ri(x-i) i-го игрока является его откликом на набор стратегий других игроков х-» если выполняется соотношение

Введение понятие отклика позволяет записать определение равновесия по Нэшу следующим образом: набор стратегий х является равновесием по Нэшу, если для каждого i выполняется соотношение

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

В матрице игры «Монополистическая конкуренция» отклики игроков представлены подчеркиванием выигрышей, соответствующих оптимальным действиям. Так, откликом Игрока 2 на стратегию «Низкая цена» Игрока 1 является стратегия «Высокая цена». Равновесие по Нэшу в данной игре — исход (клетка), где оба выигрыша оказываются подчеркнутыми. Это пара стратегий («Средняя цена»; «Средняя цена») совпадает с равновесием, найденным путем вычеркивания доминируемых стратегий. Это обстоятельство не является случайным, как показывает приведенная далее Теорема 1.

Проиллюстрируем использование функций отклика на примере игры, в которой игроки имеют континуум стратегий.

Игра 8. «Избирательные блоки». Формируются два избирательных блока, которые будут претендовать на места в законодательном собрании города N-ска. Каждый из блоков может выбрать одну из

трех ориентаций: «левая» (L), «правая» (R) и «экологическая» (Е). Каждая из ориентаций может привлечь 50, 30 и 20% избирателей соответственно. Известно, что если интересующая избирателя ориентация не представлена на выборах, то избиратель не будет голосовать. Если блоки выберут разные ориентации, то каждый получит соответствующую долю голосов. Если блоки выберут одну и ту же ориентацию, то голоса соответствующей группы избирателей разделятся поровну между ними. Цель каждого блока — получить наибольшее количество голосов.

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

«Избирательные блоки»

Блок 2

Левая

Правая

Эколог.

Блок 1

Левая

25

25

30

50

20

50

Правая

50

30

15

15

20

30

Эколог.

50

20

30

20

10

10

Замечание. В игре нет доминирующих стратегий.

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

Решение. Предположим противное, т.е. у каждого игрока нет доминирующей стратегии.

«Избирательные блоки»

Игрок 2

1 стратегия

2 стратегия

Игрок 1

1 стратегия

b1

a1

b2

d2

2 стратегия

g1

а2

g2

d2

Пусть, например, ситуация (а1, b1) — равновесие по Нэшу. Тогда а1 > а2, b1 > b2. Но, поскольку у игроков нет доминирущих стратегий, то g2> g1, d2> d1. Но тогда ситуация (d2, g2) является вторым равновесием по Нэшу, что противоречит условию задачи.

Игра 9. «Конкуренция по Курно двух производителей на рынке однородного товара»

Два производителя одновременно (независимо друг от друга) выбирают объем выпуска производимого им товара ti. Цена, по которой они могут его продать, зависит от объемов выпуска как

Цель каждого производителя — максимизировать прибыль (для упрощения анализа будем считать, что издержки производства этого товара равны нулю).

(Эта запись означает, что мы ищем максимум функции ui, по переменной ti.)

Максимизируем выигрыш первого производителя по t1,

считая фиксированной величину t2 (выпуск Игрока 2). Минимум квадратичной функции (условие первого порядка) удовлетворяет условию:

Получаем, что оптимальный отклик Игрока 1 на выпуск Игрока 2 дается формулой:

Мы получаем единственный отклик Игрока 1 на стратегию Игрока 2.

Аналогично, ищем максимум функции

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

Получаем отклик второго на выпуск первого:

Решив систему двух линейных уравнений

найдем равновесие по Нэшу этой игры:

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

Связь между введенными концепциями решений описывается следующими утверждениями.

Теорема 1

Если x* = (x1*, ..., xm*) — равновесие по Нэшу в некоторой игре, то ни одна из составляющих его стратегий не может быть отброшена в результате применения процедуры последовательного отбрасывания строго доминируемых стратегий.

Обратная теорема верна в случае единственности равновесия Нэша

Теорема 2

Если в результате последовательного отбрасывания строго доминируемых стратегий у каждого игрока остается единственная стратегия, xi*, то x* = (х1*, ..., xm*) — равновесие по Нэшу.

Доказательства этих двух утверждений можно найти в пособии http://econom.nsu.ru/lib/NFPK/Micro3_Book.pdf, где содержится также более подробное введение в теорию некооперативных игр.

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

Задача 11. Покажите, что в Игре «Монополистическая конкуренция» единственное равновесие по Нэшу.

Задача 12. Проанализируйте игру «Конкуренция по Курно» для случая, когда издержки линейно зависят от выпуска, т.е. при выпуске ti составляют величину citi.

Задача 13. Найдите равновесие по Нэшу в следующей игре: двое делят между собой 4 ореха. Каждый делает свою заявку на орехи: х, = 1,2 или 3. Если x1 + х2 < 4, то каждый получает сколько просил, в противном случае оба не получают ничего.

Решение. Матрица выигрышей данной игры имеет вид:

Игра «Орехи»

Игрок 2

1 орех

2 ореха

3 ореха

Игрок 1

1 орех

1

1

2

1

3

1

2 ореха

1

2

2

2

0

0

3 ореха

1

3

0

0

0

0

В этой игре 3 равновесия по Нэшу. В ситуациях, когда игроки берут наборы (1; 3), (2; 2) или (3; 1) орехов, ни один из них не может улучшить свой выигрыш (если Игрок 1 берет 1 орех, то Игроку 2 выгоднее брать 3 ореха, и наоборот: если Игрок 1 берет 3 ореха, то Игроку 2 выгоднее брать 1 орех). Все равновесия можно описать короче: когда сумма заявок равна числу орехов.

Задача 14. Найдите равновесие по Нэшу в обобщенной игре дележа: двое делят между собой 4 рубля. Каждый делает свою заявку: Xi > 0. Если x1 + х2 < 4, то каждый получает сколько просил, в противном случае оба не получают ничего.

Указание. Равновесием (решением) по Нэшу в этой игре будет любая ситуация (пара чисел) x1 > 0, х2 > 0, такая, что х1 + х2 = 4. Докажите, что это равновесие, и других равновесий нет.

Задача 15. Покажите, что в игре «Монополистическая конкуренция» есть единственное равновесие по Нэшу, и его можно получить путем отбрасывания доминируемых стратегий.

Задача 16. Докажите, что если у каждого из игроков существует строго доминирующая стратегия, то эти стратегии составляют единственное равновесие по Нэшу.

Указание. Доминирующую стратегию нельзя улучшить.

Задача 17. Докажите, что если у каждого из игроков существует доминирующая стратегия, то набор доминирующих стратегий составляет равновесие по Нэшу.

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

Задача 18. Найдите все равновесия в дискретном варианте аукциона Викри.

Указание. Все равновесия по Нэшу можно найти путем построения отклика каждого игрока на каждую стратегию его конкурента.

Стратегия назначения своей оценки pi = vi является доминирующей (но не строго домиирующей) стратегией каждого участника аукциона. Поэтому в данной игре существует равновесие по Нэшу, которое является равновесием в доминирующих стратегиях. Но в дополнение к равновесию в доминирующих стратегиях в этой игре много и других равновесий по Нэшу.

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

Докажем, что для любого игрока i и при цене предмета аукциона р (0 < р < vi) существует равновесие по Нэшу, в котором игрок i получает этот предмет и платит за него р. Покажем это. Пусть v — наибольшее среди v1... vn, положим

Тогда набор стратегий (р1,р2,...рп)~равновесие по Нэшу.

Действительно, для участника j, jФi любое уклонение, которое меняет исход аукциона (распределение платежей), приводит к отрицательному выигрышу игрока j (вместо нулевого при выборе равновесной стратегии). С другой стороны, любое уклонение для игрока i, которое меняет исход аукциона, дает ему выигрыш 0 вместо Vi—p> 0.

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

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

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

Задача 21. Покажите, приведя пример, что при отбрасывании доминируемых (но не строго доминируемых) стратегий можно отбросить равновесие по Нэшу.

2.6. Равновесие по Нэшу в смешанных стратегиях

Нетрудно привести примеры игр, в которых равновесие по Нэшу отсутствует. В игре «Инспекция» рассматривается именно такая ситуация.

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

Игра «Инспекция»

Инспектор

Проверять

Не проверять

Проверяемый

Нарушать

1

-1

0

1

Не нарушать

-1

0

0

0

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

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

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

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

Но в некоторых играх естественно ввести в рассмотрение также смешанные стратегии. Под смешанной стратегией понимают выбор чистых стратегий с некоторыми вероятностями.

Найдем равновесие по Нэшу в смешанных стратегиях в игре «Инспекция».

Обозначим через μ вероятность того, что налогоплательщик не платит подоходный налог (стратегия «нарушать»), а через v — вероятность того, что инспектор проверяет налогоплательщика.

В этих обозначениях ожидаемый выигрыш налогоплательщика равен

а ожидаемый выигрыш инспектора равен

Если вероятность проверки мала (v < 1/2), то налогоплательщику выгодно не платить налог, т.е. выбрать μ = 1. Если вероятность проверки велика, то налогоплательщику выгодно заплатить налог, т.е. выбрать μ = 0. Если же v = 1/2, то налогоплательщику все равно, платить налог или нет, он может выбрать любую вероятность μ из интервала [0, 1]. Таким образом, отображение отклика налогоплательщика имеет вид:

Рассуждая аналогичным образом, найдем отклик налогового инспектора:

Рис. 2. Отображения отклика в игре «Инспекция»

Графики отображений отклика обоих игроков представлены на Рис. 2. По осям на этой диаграмме откладываются вероятности (μ и v соответственно). Они имеют единственную общую точку (1/2, 1/2). Эта точка соответствует равновесию Нэша в смешанных стратегиях.

Определение

Смешанная стратегия называется невырожденной, если ни одна из стратегий не выбирается с вероятностью 1.

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

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

В конечных играх равновесие в чистых стратегиях существует не всегда, а равновесие в смешанных стратегиях существует всегда.

Теорема 3 (Нэша)

Равновесие по Нэшу в смешанных стратегиях существует в любой конечной игре.

Заметим, что существование в игре равновесия в чистых стратегиях не исключает существования равновесия в смешанных стратегиях.

Рассмотрим вариант игры «Выбор компьютера», когда выгоды от совместимости значительны, т.е. а < с и b < с. Тогда есть два равновесия в чистых стратегиях: (IBM, IBM) и (Mac, Mac). Обозначим μ и V вероятности выбора компьютера IBM PC первым и вторым игроком соответственно.

а

Игрок 2

IBM, V

Mac, 1 — v

Игрок 1

IBM, μ

с

а+с

b

а

Mac 1-μ

0

0

b+c

с

Ожидаемый выигрыш Игрока 1 равен:

а его отклик имеет вид:

Ожидаемый выигрыш Игрока 2 равен:

а его отклик имеет вид:

Графики отображений отклика и точки, соответствующие трем равновесиям изображены на Рис. 3. Как видно, в рассматриваемой игре кроме двух равновесий в чистых стратегиях имеется одно равновесие в невырожденных смешанных стратегиях.

Соответствующие вероятности и средние выигрыши равны:

Сравним выигрыши игроков в чистых и смешанных стратегиях: в случае выбора (IBM, IBM) выигрыши игроков (а+с, с); в случае выбора (Mac, Mac) выигрыши игроков (с, b+c);

в случае

выигрыши игроков

Каждая из чистых стратегий дает преимущество одному из игроков, а смешанная стратегия их выравнивает.

Рис. 3.

2.7. Упражнения для самостоятельного решения

Задача 22. Как изменится выбор игроков в игре «Выбор компьютера» если обладание компьютером нелюбимого типа оценить в d условных единиц, где d < a, d < b, причем а < c+d <b?

Указание. Матрица выигрыша этой игры имеет вид:

â

Игрок 2

IBM

Mac

Игрок 1

IBM

d+c

а+с

b

a

Mac

d

d

b+c

d+c

Проверьте, что Игроку 1 выгоднее выбрать такой же компьютер, как у Игрока 2, а Игроку 2 выгоднее выбрать Mac.

Задача 23. Приведите пример игры, в которой существует равновесие в доминирующих стратегиях, и, кроме того, существуют равновесия по Нэшу, не совпадающие с равновесием в доминирующих стратегиях.

Указание. Проанализируйте вариант игры «Аукцион Викри»

Найдите в следующих играх все равновесия по Нэшу

Задача 24. Каждый из трёх игроков выбирает одну из сторон монеты: «орёл» или «решка». Если выборы игроков совпали, то каждому выдается по 1 рублю. Если выбор одного из игроков отличается от выбора двух других, то он выплачивает им по 1 рублю.

Указание. Поскольку игроков трое, то матрица игры будет трехмерной, и ее строить неудобно. Воспользуемся тем, что все игроки симметричны и стратегии симметричны. Стратегий две, а игроков трое, поэтому хотя бы у двух игроков стратегии совпадут. Рассмот-

рите два случая и определите, может ли кто-то из них увеличить свой выигрыш. В ответе получится два равновесия: «все орлы» и «все решки».

Задача 25. «Орел или решка». Первый из двух игроков прячет монетку, положив ее по своему выбору вверх орлом или решкой. Второй игрок должен угадать, как лежит монетка. Если второй игрок угадает, то первый должен отдать ему рубль, в противном случае второй отдает первому рубль.

«Орел или решка»

Игрок 2

Орел

Решка

Игрок 1

Орел

1

-1

-1

1

Решка

-1

1

1

-1

Ответ. В игре нет равновесий по Нэшу в чистых стратегиях и одно (симметричное) равновесие в смешанных стратегиях, при котором каждая чистая стратегия выбирается каждым игроком с вероятностью 0,5.

Задача 26. «Камень — ножницы — бумага». Играют двое. Каждый называет один из трех предметов: «камень», «ножницы» или «бумага». Игрок, назвавший камень, выигрывает у игрока, назвавшего ножницы (ножницы тупятся о камень), игрок, назвавший ножницы, выигрывает у игрока, назвавшего бумагу (ножницы режут бумагу), а игрок, назвавший бумагу, выигрывает у игрока, назвавшего камень (камень можно завернуть в бумагу). Выигравший игрок получает 1, проигравший получает -1. Если названные предметы совпали, то каждый игрок получает 0.

«Камень — ножницы — бумага»

Игрок 2

Камень

Ножницы

Бумага

Игрок 1

Камень

0

0

-1

1

I

-1

Ножницы

1

-1

0

0

-1

I

Бумага

-1

I

1

-1

0

0

Ответ. В игре нет равновесий по Нэшу в чистых стратегиях. Найдите равновесие по Нэшу в смешанных стратегиях.

Задача 27. Заполните пропущенные выигрыши в следующей таблице так, чтобы в получившейся игре:

(0) не было ни одного равновесия по Нэшу,

(1) было одно равновесие по Нэшу,

(2) было два равновесия по Нэшу,

(3) было три равновесия по Нэшу,

(4) было четыре равновесия по Нэшу.

Ноль

1

2

4

0

Одно

1

2

4

0

Два

1

2

4

0

Три

1

2

4

0

Четыре

1

2

4

0

Определение

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

Определение

Седловой точкой функции f(x, у), называют такую точку (х0,уо), что для любых (х, у) выполнено неравенство

Задача 28. Объясните, почему множество седловых точек функции выигрыша Игрока 1 в антагонистической игре двух лиц совпадает с множеством равновесий по Нэшу.

Решение. Пусть сумма выигрышей равна С. Для Игрока 1 в силу второго неравенства стратегия х = х0 является доминирующей. Поскольку выигрыш Игрока 2 равен С — f(x, у), то в силу первого неравенства стратегия у = у0 является доминирующей для Игрока 2.

Задача 29. Докажите, основываясь на результатах двух предыдущих задач, что в антагонистической игре двух лиц равновесие по Нэшу (в чистых стратегиях) существует тогда и только тогда, когда для функции выигрыша первого игрока выполнено неравенство:

Определение

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

2.8. Задачи повышенной трудности (для исследования)

Задача 30. Два игрока размещают точку на плоскости, то есть выбирают ее координаты (х, у). Игрок 1 находится в точке (х1,у1), а Игрок 2 — в точке (x2,y2). Игрок 1 выбирает координату х, а Игрок 2 — координату у. Каждый стремиться, чтобы точка находилась как можно ближе к нему. Покажите, что в этой игре у каждого игрока есть строго доминирующая стратегия и равновесие в доминирующих стратегиях не является оптимальным по Парето (т.е. у каждого игрока есть стратегии, приводящие к исходу с большим выигрышем для каждого игрока, чем в равновесии в доминирующих стратегиях).

Задача 31. Проанализируйте Игру 1 «Выбор компьютера» и найдите ответы на следующие вопросы:

а) При каких условиях на параметры а, b и с будет существовать равновесие в доминирующих стратегиях? Каким будет это равновесие?

б) При каких условиях на параметры исход (IBM, IBM) будет равновесием по Нэшу? Когда это равновесие единственно? Может ли оно являться также равновесием в доминирующих стратегиях?

Задача 32. Два мороженщика в жаркий день продают на пляже мороженое. Пляж можно представить как единичный отрезок. Мороженщики выбирают, в каком месте пляжа им находиться, т.е. выбирают координату Xi g [0, 1]. Покупатели равномерно рассредоточены по пляжу и покупают мороженое у ближайшего к ним продавца. Если x1 < х2, то первый обслуживает (х1 + х2)/2 долю пляжа, а второй — (1 — (х1+х2)/2). Если они расположатся в одной и той же точке (х1 = x2), то будем считать, что покупатели распределятся поровну между ними. Каждый мороженщик стремиться обслуживать как можно большую долю пляжа.

Ответ к задаче 27. Например, такая расстановка чисел:

Ноль

1

1

0

2

-1

4

0 1

Одно

1

0

1

2

4

0

4

0

Два

1

2

1

2

4

0

4

0

Три

1

0

4

2

0

0

4

2

Четыре

1

4

1

2

0

0

4

2

3. Динамические игры с совершенной информацией

3.1. Примеры и понятия

Многие ситуации, включающие взаимодействие индивидуумов, являются по своему смыслу динамическими. Люди взаимодействуют друг с другом во времени и действуют, реагируя на те решения, которые ранее приняли другие. Другими словами, принимая решения, каждый игрок что-то знает о решениях, уже принимавшихся другими игроками, что предполагает очередность принятия решений (ходов).

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

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

Уместно начать с простого примера динамической игры.

Игра 11. «Террорист». В самолет, который должен лететь из Майами в Нью-Йорк, сел террорист. Террорист требует, чтобы пилот летел на Кубу, угрожая в противном случае взорвать самолет. Предположим, что террорист не может определить, куда действительно летит самолет. Первый ход в этой игре тогда делает пилот. Он может лететь либо на Кубу, либо в Нью-Йорк. Если пилот посадит самолет на Кубе, то его выигрыш составит (-1), а выигрыш террориста составит 1. Если же самолет сядет в Нью-Йорке, то делает свой ход террорист. Он может либо взорвать бомбу, либо не взрывать. Если бомба взорвется, то выигрыши обоих игроков составят -100, в противном случае выигрыш пилота составит 1, а выигрыш террориста составит -1.

Данную игру удобно представить в виде диаграммы (Рис. 4), изображающей дерево игры.

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

Рассмотрим последнюю вершину игры, в которой один из игроков делает выбор, т.е. предположим, что пилот уже сделал свой выбор и этот выбор «Лететь в Нью-Йорк». В данном случае нам надо спрогнозировать, как поступит террорист, оказавшись в Нью-Йорке. Если террорист рационален, то он примет решение не взрывать бомбу, поскольку —1 больше, чем -100. Таким образом, в данной ситуации, если информация о выигрышах является общеизвестной, действия террориста можно предсказать однозначно.

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

Теперь, определяя выбор пилота, можно «свернуть» дерево игры, учитывая то, что действия террориста в Нью-Йорке ему известны. Полученная усеченная (редуцированная) игра показана на Рис. 5.

Рис. 4. Игра «Террорист»

В этой игре действия пилота несложно предсказать — он полетит в Нью-Йорк, поскольку предпочитает выигрыш 1 выигрышу -1. Таким образом, исход игры однозначен: пилот посадит самолет в Нью-Йорке, а террорист не станет взрывать бомбу.

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

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

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

• множество вершин дерева игры, в том числе одну начальную вершину;

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

Рис. 5. Решение игры «Террорист»

• множество игроков;

• для каждой вершины, кроме конечных, — единственного игрока, которому принадлежит ход в данной вершине;

• для каждой конечной вершины, то есть такой, которая не предшествует ни одной другой вершине, — выигрыши всех игроков.

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

Первые два пункта здесь соответствуют описанию дерева игры.

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

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

В случае, когда в динамической игре участвуют два игрока, и игра происходит в 2 этапа, то обратную индукцию удобно провести на основе функции отклика 2-го игрока на действия 1-го. Следующая игра иллюстрирует использование этого приема.

Игра 12. «Рэкет». Рэкетиры выбирают, какую долю а (ае [0,1]) выручки отбирать у фирмы. Они при этом максимизируют произведение ару, где р — цена, у — выпуск фирмы. Фирма имеет квадратичную функцию издержек, так что ее прибыль (выигрыш) равна

Фирма максимизирует прибыль при ограничении у > 0. Рэкетиры делают ход первыми. Зная, какую долю выручки они хотят отбирать, фирма выбирает уровень выпуска.

Дерево игры имеет следующий вид (Рис. 6.)

Рис. 6. Дерево игры «Рэкет»

Поскольку множества возможных действий игроков в рассматриваемой игре не конечны (например, у рэкетиров — интервал [0, 1]), то на Рис. 6 они изображены в виде секторов. При этом в каждой точке верхнего сектора, соответствующего выбору а, начинается некий сектор, соответствующий выбору у. На рисунке представлен лишь один из таких нижних секторов. Поскольку в данной игре имеется бесконечное множество (континуум) действий и исходов, на диаграмме уместно представить способы вычисления выигрышей для выбранных действий игроков как функции от действий игроков.

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

Если а < 7, то у > 0. При а = 1 получаем решение у = 0. Таким образом, рэкетиры могут вывести уравнение оптимального выпуска фирмы как функцию доли а:

Зная эту функцию отклика, рэкетиры максимизируют свой выигрыш (свою целевую функцию), т.е. решают следующую задачу:

или, после подстановки

Максимум достигается при а= 1/2, то есть рэкетиры будут отбирать у фирмы половину выручки. При этом выпуск фирмы составит р/4.

Графически поиск решения представлен на Рис. 7. Каждая кривая -это множество точек (а, у), для которых значение фнкции выигрыша одинаково (называется линия уровня, или кривая безразличия). На географических картах так же рисуют линии высоты местности. Стрелками указано направление возрастания значений функции.

Рис. 7. (а) Получение функции отклика фирмы у(а). (б) Выбор рэкетирами оптимальной отбираемой доли а.

Теорема 4

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

Кроме того, если выигрыши всех игроков во всех конечных вершинах различны, то такое решение единственно.

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

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

Множество игроков будет одним и тем же в нормальной форме и в развернутой форме игры. Прежде всего, уточним понятие стратегии для игр такого типа.

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

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

мы, по сути дела, имеем статическую игру, в которой выигрыши определяются с помощью описанного только что алгоритма.

Проиллюстрируем, как на основе развернутой формы динамической игры получить ее нормальную форму, на примере модифицированного варианта игры «Выбор компьютера». Предположим, что 1-й игрок выбирает себе компьютер первым. Дерево такой игры имеет вид (Рис. 8)

Рис. 8. Динамический вариант игры «Выбор компьютера»

Вершины на дереве пронумерованы для удобства обозначения альтернатив в разных вершинах. Игрок 1 имеет в этой игре две стратегии, совпадающие с альтернативами в вершине ❶. Игрок 2 имеет 4 стратегии. Каждая его стратегия определяет действия в двух вершинах: ❷ и ❸. Таким образом, 2-го игрок имеет следующие стратегии: (❷IBM, ❸IBM), (❷IBM, ❸Mac), (❷Mac, ❸IBM), (❷Mac, ❸Mac).

План, соответствующий, например, второй из указанных стратегий, Игрок 2 формулирует следующим образом: я выберу IBM, если Игрок 1 выберет IBM, и я выберу Mac, если Игрок 1 выберет Mac. Матрица выигрыша данной модификации игры «Выбор компьютера» имеет вид:

â

Игрок 2

❷IBM ❸IBM

❷IBM ❸Mac

❷Mac ❸IBM

❷Mac ❸Mac

Игрок 1

❶IBM

с

a + c

с

a +c

b

a

b

a

❶Mac

0

0

b + c

с

0

0

b + c

c

Можно заметить, что нормальная форма динамического варианта игры более сложна, чем нормальная форма статического варианта игры.

Для нормальной формы игры естественным решением, как мы уже видели, является равновесие по Нэшу. Сравним равновесия по Нэшу с результатом применения метода обратной индукции. Интересен случай, когда а < с и b < с.

Сначала разберем, что предсказывает обратная индукция. При сделанных предположениях о параметрах игры можно предсказать, что Игрок 2 в вершине ❷ выберет IBM, поскольку с < b (он совместимость ценит больше, чем использование компьютера любимого типа), а в вершине ❸ выберет Макинтош, поскольку b + с > 0. В редуцированной игре Игрок 1 должен сделать выбор между выигрышами а +с (IBM) и с (Макинтош). Он выберет IBМ. Таким образом, обратная индукция предсказывает, что игроки выберут следующие стратегии:

Игрок 1 — ❶IBM,

Игрок 2 — (❷IBM, ❸Mac).

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

Теорема 5

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

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

Рассмотрим, например, равновесие ❶Мас и (❷Mac, ❸Mac). Содержательно его можно интерпретировать следующим образом: Игрок 2 угрожает Игроку 1 тем, что он выберет Макинтош в случае, если тот выберет IBM; под влиянием этой угрозы Игрок 1 выбирает Макинтош. Но такая ситуация противоречит предположению о рациональности, на которое опирается метод обратной индукции. Действительно, если Игрок 2 окажется в вершине ❷, то предпочтет выбрать IBМ. Поскольку Игрок 1 знает о том, что Игрок 2 рационален, он не поверит этой угрозе. Таким образом, рассматриваемый набор стратегий вряд ли является естественным прогнозом того, как будут вести себя игроки в такой ситуации. Еще одно равновесие, ❶IBM и (❷IBM, ❸IBM), основано на столь же пустой угрозе, которая, в отличие от предыдущей, никак не назовешь разумной.

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

• При представлении динамической игры в нормальной форме теряется информация о последовательности ходов и информации, доступной игрокам на каждом ходе.

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

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

Предположим, что несколько ходов в игре уже сделано. Можно рассматривать оставшуюся часть игры как самостоятельную игру. Выбранные игроками стратегии предписывают, что в этой оставшейся части игры игроки будут действовать строго определенным образом. Однако такое поведение может оказаться невыгодным игрокам — они могут предпочесть изменить свои выборы. С этой точки зрения естественным представляется требование динамической согласованности:

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

Часть игры, начинающаяся в некоторой вершине и включающая в себя все, что следует за этой вершиной, в теории игр называют подыгрой.

Определение

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

Собственная подыгра — это подыгра, начальная вершина которой не совпадает с начальной вершиной полной игры.

В рассматриваемой игре есть 3 подыгры, одна из них — сама игра и две собственных подыгры, начинающиеся в вершинах ❷ и ❸.

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

Определение

Совершенным равновесием в подыграх называется набор стратегий такой, что он является равновесием по Нэшу в полной игре, а

соответствующие части этого набора стратегий являются равновесиями по Нэшу во всех собственных подыграх этой игры.

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

Ее матрица выигрыша имеет вид

Игрок 2

❷IBM

❷Mac

Игрок 1

а+с

b

а

Игрок 1 не осуществляет в этой подыгре выбора. Игрок 2 имеет две стратегии: ❷IBM и ❷Mac.

В данной игре есть единственное равновесие по Нэшу. В нем 2-й игрок выбирает IBМ. Таким образом, чтобы равновесие по Нэшу в исходной игре было совершенным, требуется, чтобы оно предписывало в вершине ❷ выбор IBМ. Набор стратегий ❶Мас и (❷Mac, ❷Mac) не удовлетворяет этому требованию, поэтому он не может быть совершенным равновесием в подыграх.

Во второй собственной подыгре, которая начинается в вершине ❸, в равновесии по Нэшу 2-й игрок выбирает Макинтош. Поэтому набор стратегий ❶IBM и (❷IBM, ❸IBM) не является совершенным равновесием в подыграх.

С другой стороны, набор ❶IBM и (❷IBM, ❸Mac) является равновесием по Нэшу в полной игре и соответствует равновесиям по Нэшу в каждой из собственных подыгр. Поэтому данный набор стратегий является совершенным равновесием в подыграх. Видим, что он совпал с тем решением, которое мы раньше получили, применив обратную индукцию. Это совпадение не является случайным, как показывает следующая теорема.

Теорема 6

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

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

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

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

3.2. Дополнительные задачи

В следующих играх найдите решение, используя обратную индукцию.

Игра 13. «Кто последний». Играют два школьника. В куче n камней. Каждый по очереди берет из кучи (на его выбор) 1, 2 или 3 камня. Проигрывает тот, кто взял последний камень. Найдите решение игры для n = 6; при каких значениях n первый игрок выигрывает?

Игра 14. «Выбор отдыха». Муж и жена выбирают, где провести вечер: дома или у друзей, причем друзья у них разные. Выигрыши заданы следующей матрицей:

Выбор отдыха

Муж

дома

у друзей

Жена

дома

b

а

с

0

у друзей

0

d

с

d

Величины а, b, с, d > 0 — параметры. Жена делает свой выбор первой. При каких условиях на параметры супруги проведут вечер дома вместе?

Игра 15. «Издольщина». Барин выбирает какую долю а стоимости у урожая забирать у крестьянина в виде издольщины. Он при этом максимизирует функцию вида

то есть желает побольше получить, но не желает разорить полностью крестьянина, что возможно при слишком большом а (ae [0,1]). Крестьянин имеет целевую функцию (1 -a)y — у2, то есть максимизирует прибыль по у (у > 0) при квадратичной функции затрат. Какую долю выберет барин?

Игра 16. «Координаты». Два игрока размещают точку на плоскости, то есть выбирают ее координаты (х,у). Игрок 1 находится в точке (х1,у1), а Игрок 2 — в точке (х2,уг)- Игрок 1 выбирает координату X, а Игрок 2 — координату у. Каждый стремиться, чтобы точка находилась как можно ближе к нему. Найдите решение этой игры в предположении, что первым выбор делает Игрок 1.

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

Предлагается следующая процедура дележа. Игрок 1 режет пирог. Остальные игроки по порядку номеров берут любой из кусков по выбору. Последний кусок достается Игроку 1.

а) Нарисуйте дерево игры при n = 3. Опишите множество стратегий каждого из игроков.

б) Найдите совершенное равновесие в подыграх.

в) Докажите, что справедливый дележ ai = 1/п будет единственным равновесием.

4. Динамические игры с несовершенной информацией

4.1. Основные понятия

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

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

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

Предположим, что Игрок 1 ходит первым. Есть две вершины, в которых ход принадлежит Игроку 2, однако сам он не может разли-

Рис. 9. Представление статической игры «Выбор компьютера» в виде дерева

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

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

Дополнительно накладывается условие, чтобы множества возможных действий во всех вершинах одного и того же информационного множества были одинаковыми. В противном случае игрок мог бы по тому, какие альтернативы ему доступны, определить, в какой именно вершине он находится. Дерево игры «Выбор компьютера» не удовлетворяет этому требованию — и в вершине ❷, и в вершине ❸ Игрок 2 выбирает между IBM и Mac.

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

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

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

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

4.2. Уточнение понятия стратегии

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

В играх с несовершенной информацией определение совершенного равновесия в подыграх совпадает с данным выше определением для игр с совершенной информацией. Однако в играх с несовершенной информацией следует дать несколько другое определение подыгры. Отличие состоит в том, что подыгра может начинаться не из любой вершины. Следует потребовать, чтобы вместе с каждой вершиной, содержащаяся в подыгре, содержалось и всё информационное множество, содержащее данную вершину. Например, в игре, дерево которой показано на рисунке, вершины ❷, ❸ и ❹ не являются начальными вершинами подыгр. Таким образом, в этой игре нет собственных подыгр.

Рис. 10.

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

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

Сначала при использовании обратной индукции на последнем, Т-м, этапе находятся равновесия по Нэшу всех игр этого этапа. Затем, каждая их этих игр заменяется конечной вершиной. Ей сопоставляются выигрыши, соответствующие каждому равновесию по Нэшу. Тем самым мы получаем игру с T-1 этапом и т.д.

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

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

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

Дерево игры имеет вид (Рис. 11)

Рис. 11.

R обозначает «забрать деньги», L — «не забирать». Игра происходит в 2 этапа, на каждом из которых вкладчики одновременно решают, забирать ли деньги. Первый этап происходит по прошествии 1 месяца после вложения денег, второй — по прошествии 2 месяцев.

Редуцированная игра «Набеги на банки»

Первый этап

Игрок 2

L2

R2

Игрок 1

L1

R1

v2

v1

0

2

2

0

1

1

Второй этап

Игрок 2

L4

R4

Игрок 1

L3

3

3

2

0

R3

0

2

1

1

Множество равновесий по Нэшу в редуцированной игре первого этапа зависит от того, какое из двух равновесий может реализоваться на втором этапе. Если игроки считают, что на втором этапе они оба заберут деньги, то им выгоднее забрать деньги на первом этапе, поскольку v1, v2 = 1 < 2. Если же игроки считают, что на втором этапе они оба оставят деньги в банке, то на первом этапе может реализоваться одно из двух равновесий по Нэшу, поскольку v1, v2= 3> 2: либо оба игрока забирают деньги, либо оба оставляют. Таким образом, обратная индукция дает три решения. В двух из этих решений происходит «набег на банк» на первом и втором этапе соответственно. Третье решение соответствует случаю, когда оба вкладчика дожидаются получения максимального выигрыша (3, 3).

Задача 33. «Раз-два-три». Каждый из двух игроков одновременно называет одно из трех чисел: 1, 2 или 3. При совпадении Игрок 2 дает Игроку 1 совпавшее число (при несовпадении никто не платит). Дополнительно игроки получают удовольствие от участия в игре, которые они оценивают в 1/2. Какую сумму z Игрок 1 должен заплатить Игроку 2 до начала игры, чтобы тот согласился играть? Нарисуйте дерево, описывающее данную ситуацию.

5. Некоторые применения теории игр

5.1. Государство и экономика

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

Хотя этот результат часто представляют как следствие частной деятельности в отсутствие правительства, сама возможность таких обменов, хотя и не предполагает наличия правительства, обусловлена существованием успешно действующей системы коллективного выбора, вполне сопоставимой по сложности с рыночной системой, которой она управляет. Действительно, индивиды А и В сталкиваются не только с выбором альтернатив: торговать/не торговать. Ведь А может просто украсть зерно у В. Тоже может сделать и В.

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

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

Игрок 2

Игрок 1

Не воровать

Воровать

Не воровать

① 9

10

④ 11

7

Воровать

② 6

12

③ 8

8

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

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

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

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

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

ведение, собирают налоги для обеспечения своих членов общественными благами, содержат полицию.

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

5.2. Общественное благо и проблема координации

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

Рассмотрим пример из класса игр, называемых координационными играми. Это игра двух лиц {Игрок 1, Игрок 2} с двумя одинаковыми множествами стратегий {Стратегия 1, Стратегия 2}. Матрица выигрышей приведена в таблице

Игрок 2

Игрок 1

Стратегия 1

Стратегия 2

Стратегия 1

① а а

© 0 0

Стратегия 2

④ 0 0

③ b b

Предположим, что а > b. Тогда оба игрока предпочитают исход 1. Если же а = b, любой из двух исходов 1 или 3 одинаково привлекателен для обоих игроков, и если один из них предложит другому выбрать, например, Стратегию 1, то у другого нет оснований отказываться. Поэтому вполне естественно ожидать, что в таких ситуа-

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

5.3. Общественное благо со слабыми связями

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

где индивид i платит за объем блага z.. Если, например, вклад трех индивидов составляет, соответственно 5, 7 и 12, то все получат только 5 единиц блага.

Упражнение. Приведите примеры общественных благ со слабыми связями.

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

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

(4) получает сосед, решивший построить свой участок стены, но не сумевший убедить другого последовать его примеру.

Сосед В

Сосед А

Вносит вклад в строительство стены

Не вносит вклад в строительство стены

Вносит вклад в строительство стены

30

30

8

12

Не вносит вклад в строительство стены

6

12

9

9

Равновесными по Нэшу являются: исход (30, 30), когда стена строится на всем протяжении побережья, и исход (9, 9), когда ни один из соседей не участвует в возведении стены. В обоих случаях каждому соседу не выгодно менять свое решение в одностороннем порядке. Наиболее эффективным из этих равновесий с точки зрения общества, а также и наиболее выгодным вариантом лично для каждого человека является исход (30, 30).

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

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

Общественное благо со слабыми связями

Сосед В

Сосед А

Вносит вклад в общественное благо

Не вносит вклад в общественное благо

Вносит вклад в общественное благо

b

b

а

с

Не вносит вклад в общественное благо

с

а

а

а

Для того, чтобы найти равновесные смешанные стратегии, предположим, что выгоды индивидов от одинаковых решений совпада-

ют. Выгоду в размере а индивид может гарантировано получить, отказавшись сделать вклад. При решении внести вклад предполагаемая выгода составит Рс+(1-Р)b, где Р — это вероятность, с которой другой сосед не вносит вклад. Равновесная смешанная стратегия получается тогда, когда индивиду безразлично, вносить или не вносить вклад:

Из этого выражения следует, что вероятность того, что человек не будет вносить вклад, равна:

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

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

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

5.4. Координирующая функция государства

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

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

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

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

Какие, вы полагаете, есть подходы к решению этой проблемы?

Рассмотренные выше ситуации носят название координационных игр.

Многие другие ситуации с предоставлением общественного блага имеют структуру известной игры «петушиные бои», пример которой приведен ниже

B

А

Вносить вклад в общественное благо

Не вносить вклад

Вносить вклад

① 3 3

④ 3.5 2

Не вносить вклад

② 2 3.5

③ 1 1

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

5.5. Общественные блага добровольного типа

В условиях «дилеммы заключенных», если каждый из n человек вносит плату в размере zi за общественное благо, совокупный объем общественного блага, доступного потребителям, равен сумме индивидуальных вложений:

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

Упражнение. Приведите примеры общественных благ добровольного типа.

Если действий одного человека достаточно для того, чтобы все общество получило выгоду, то объем блага определяется по формуле:

В этом случае по-прежнему каждый потребитель получает одинаковое количество общественного блага:

5.6. Кто будет добровольцем

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

Когда ни один из игроков не делает вклада, то выигрыш обоих составляет 2. Когда же доброволец находится, то выигрыш игрока, вносящего вклад, составляет 10, а выигрыш второго (которому нет необходимости что-либо вкладывать) составит 12. Каждый игрок знает, каковы затраты и выигрыши партнера. Таким образом игроки знают, что их затраты и выгоды идентичны3.

Предоставление общественного блага добровольного типа

Вносить вклад

Не вносить вклад

Вносить вклад

10

10

12

10

Не вносить вклад

10

12

2

2

Совокупный выигрыш в ситуации, когда оба игрока вносят вклад, составляет 10+10=20. Этот исход не равновесен по Нэшу, так как если один человек уже обеспечивает предоставление общественного блага, то наилучшим решением для другого будет «не вносить вклад».

Минимально возможный совокупный выигрыш составит 2 + 2 = 4; такой исход возникает в случае, когда ни один из игроков не вносит вклада. Но этот исход также не равновесен по Нэшу, так как каждый из игроков может улучшить свое положение.

Равновесными по Нэшу являются исходы (12, 10) и (10, 12), когда только один игрок вносит вклад в предоставление общественного блага (ни один из них не может улучшить своего положения путем

3 Имеется в виду, что структура игры и выигрыши — общеизвестная информация. Это означает, что игроки знают издержки и выгоды друг друга, а также они знают, что все это знают и т. д.

изменения своего решения). Это равновесие эффективно. Максимальные совокупные выгоды составляют (12 + 10) = 22. В отличие от ситуации, описываемой «дилеммой заключенных», в данном случае для достижения эффективности не требуется вклада обоих индивидов в предоставление общественного блага.

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

В случае добровольного общественного блага ни у одного игрока нет доминирующей стратегии. Если один участник вносит вклад в предоставление общественного блага, наилучшим ответом другого будет не вносить вклад. Если вклад не вносится другим игроком, наилучшим решением будет внести этот вклад самому.

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

Охарактеризуем равновесную смешанную стратегию. Внося вклад в предоставление общественного блага, Игрок 1 может гарантировать себе выигрыш, равный 10, вне зависимости от того, какое решение примет Игрок 2.

Пусть Игрок 1 принял решение «не вносить вклад», Р — вероятность, с которой Игрок 2 внесет вклад. Если Игрок 2 принимает решение внести вклад, то выигрыш Игрока 1 составляет 12, а если нет, то выгода Игрока 1 составит 2. Тогда средний выигрыш Игрока 1 равен

12P+2(1-P).

В равновесной смешанной стратегии Игрок 1 должен быть безразличен к выбору стратегии. Поэтому для определения величины Р приравниваем величину среднего выигрыша Игрока 1 (при использовании им стратегии «не вносить вклад») к 10 — выигрышу Игрока 1 при использовании им стратегии «вносить вклад», т.е.:

Решив это уравнение, получим Р = 0,8.

Аналогично (в силу симметрии игроков) вероятность, с которой Игрок 1 возьмет на себя расходы по обеспечению общественного блага, равна 0,8. Иначе говоря, каждый игрок обеспечит общественное благо с вероятностью 80%.

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

Вероятности исходов игры

Игрок 2

Игрок 1

Предоставить общественное благо

Не предоставлять общественное благо

Предоставить общественное благо

(0,8) (0,8) =0.64

(0,8) (0,2) =0,16

Не предоставлять общественное благо

(0,2) (0,8) =0,16

(0,2) (0,2) =0,04

Мы видим, что с вероятностью 4% общественное благо не будет предоставлено. В других же трех случаях общественное благо предоставлено будет, т. е. вероятность, с которой тем или иным путем общественное благо будет предоставлено, составляет 1—0,04 = 0,96. Хотя вероятность предоставления коллективного блага достаточно высока, вероятность эффективного исхода составляет только 0,16+0,16 = 0,32, а излишне затратный исход возможен с вероятностью 0,64.

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

Вероятность, с которой индивид вносит вклад в предоставление общественного блага, составляет всего 0,4.

Высокие выгоды от чужого вклада

Индивид В

Индивид А

Обеспечить общественное благо

Не обеспечивать общественное благо

Обеспечить общественное благо

10

10

22

10

Не обеспечивать общественное благо

10

22

2

2

В таблице видно, что общественное благо в рассматриваемой ситуации не будет предоставлено с вероятностью 36% (другими словами, будет предоставлено с вероятностью 64%); каждый из эффективных исходов (когда только один из индивидов вносит вклад в предоставление общественного блага) возможен с вероятностью 24%, т.е. вероятность эффективного исхода составляет 48%. Сравнивая полученные результаты, видим, что вероятность того, что общественное благо не будет предоставлено, увеличилась с 4 до 36%. Вероятность эффективного исхода также увеличилась, но не столь значительно: с 32 до 48%.

Вероятности результатов

Индивид В

Индивид А

Обеспечить общественное благо

Не обеспечивать общественное благо

Обеспечить общественное благо

(0,4) (04) = 0,16

(0,4) (0,6) =0,24

Не обеспечивать общественное благо

(0,6) (0,4) =0,24

(0,6) (0,6) =0,36

Мы также можем учитывать, например, значительные потери индивидов в ситуации, когда общественное благо не предоставляется. Предположим, что каждый индивид теряет 88, если общественное благо не предоставляется. Вероятность того, что индивид предпоч-

тет собственными силами обеспечить предоставление общественного блага, составляет величину Р = 0,98. Если потери индивида в связи с непредставлением общественного блага достаточно высоки, то почти гарантированно каждый индивид будет стремиться внести вклад в предоставление общего блага.

5.7. Общая модель добровольного общественного блага

Обозначим b — выигрыш каждого индивида от предоставления общественного блага, с — затраты индивида на его предоставление. Если общественное благо отсутствует, то выигрыш каждого составляет а.

Основная форма добровольного общественного блага

Индивид В

Индивид A

Обеспечить общественное благо

Не обеспечивать общественное благо

Обеспечить общественное благо

b-с

b-с

b

b-с

Не обеспечивать общественное благо

b-с

b

а

а

Каждый индивид может гарантировать себе выигрыш (b-с), если принимает решение «Внести вклад» независимо от решения другого индивида. Пусть Р — вероятность того, что другой индивид решит взять на себя предоставление общественного блага; тогда вероятность, характеризующая смешанную стратегию, вычисляется по формуле:

откуда

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

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

Бусыгин Владимир Петрович Ковальджи Александр Кириллович

Выбор стратегии: вопросы и задачи

(материалы для учителей математики и экономики в средней школе)

Редактор: Н. Главацкая Компьютерный дизайн: В. Юдичев

Подписано в печать 31.05.2006. Тираж 400 экз.

125993, Москва, Газетный пер., 5

Тел.: (495) 629-6736 Факс: (495) 203-8816

www.iet.ru

E-mail: info@iet.ru