ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

"ЧЕЛЯБИНСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ"

Кафедра информатики и методики преподавания информатики

Квалификационная работа

ТЕОРИЯ ИГР В НАЧАЛЬНОЙ ШКОЛЕ

Исполнитель:

Новикова Ксения Сергеевна,

студентка группы 591

Научный руководитель:

Дмитриева О.А.,

ассистент кафедры ИМПИ

Зав. кафедрой:

Матрос Д. Ш.,

докт. пед. наук, профессор

Дата допуска к защите:

Челябинск 2007

Введение

1.2 Решение матричной игры в чистых стратегиях

1.3 Решение матричной игры в смешанных стратегиях

1.4 Решение игр графическим методом

1.5 Сведение матричной игры к задаче линейного программирования

1.6 Игры с природой

Выводы по I главе

Глава II Разработка элективного курса “Элементы теории игр в начальной школе”

2.1 Место компьютера в начальной школе

2.3 Игра как метод обучения в начальной школе

2.4 Анализ программ и стандарта по информатике в начальной школе

2.5 Элективный курс

2.6 Педагогический эксперимент

2.7 Описание программного продукта

Выводы по II главе

Заключение

Список использованной литературы

Приложения

Введение

Теория игр была основана Джоном фон Нейманом и Оскаром Моргенштерном в их первой работе "The Theory of Games and Economic Behavior", изданной в 1944 году. В 1928 году в математических анналах фон Нейманом была опубликована статья "О теории общественных игр", в которой впервые было применено понятие "теория игр". Использование этого понятия объясняется схожестью логики принятия решений в таких играх, как шахматы и покер. Характерным для таких ситуаций является то, что результат для принимающего решение зависит не только от его решения, но и от того, какое решение примут другие. Поэтому оптимальный исход не может быть получен в результате принятия решения одним лицом.

Другим предшественником теории игр по праву считается французский математик Э. Борель (1871-1956). Некоторые фундаментальные идеи были независимо предложены А. Вальдом (1902-1950), заложившим основы нового подхода к статистической теории принятия решений.

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

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

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

Цель: изучение теоретических положений по теории игр и создание элективного курса "Элементы теории игр в начальной школе" с методической поддержкой.

Объект исследования: Теория игр

Предмет исследования: Обучение теории игр в начальной школе.

Задачи исследования:

изучить теоретический материал

отобрать задачи для практической реализации

разработать алгоритмы решения задач

программно реализовать отобранные задачи

разработать элективный курс

создать электронное пособие

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

Новизна работы заключается в следующем:

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

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

Разработан элективный курс “Элементы теории игр в начальной школе" и программно-методическая поддержка к нему.

Глава I Основные положения Теории игр

1.1 Предмет и задачи теории игр

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

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

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

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

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

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

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

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

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

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

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

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

Из истории теории игр

История теории игр как самостоятельной дисциплины начинается в 1944 году, когда Джон фон Нейман и Оскар Моргенштерн опубликовали книгу "Теория игр и экономическое поведение" ("Theory of Games and Economic Behavior"). Хотя примеры теории игр встречались и раньше: трактат Вавилонского Талмуда о разделе имущества умершего мужа между его жёнами, карточные игры в 18-м веке, развитие теории шахматной игры в начале 20-го века, доказательство теоремы о минимаксе того же Джона фон Неймана в 1928 году, без которой не было бы никакой теории игр.

В 50-х годах 20-го века Мелвин Дрешер и Мерил Флод из Rand Corporation первыми экспериментально применили дилемму заключённого, Джон Нэш в работах о состоянии равновесия в играх двух лиц развил понятие равновесия Нэша.

Рейнхард Сэлтен в 1965 году опубликовал книгу "Обработка олигополии в теории игр по требованию" ("Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit"), с которой применение теории игр в экономике получило новую движущую силу. Шагом вперёд в эволюции теории игр связан с работой Джона Мейнарда Смита "Эволюционно стабильная стратегия" ("Evolutionary Stable Strategy", 1974). Дилемма заключённого была популяризована в книге Роберта Аксельрода "Эволюция кооперации" ("The Evolution of Cooperation"), опубликованной в 1984 году. В 1994 году именно за вклад в теорию игр Нобелевской премии были удостоены Джон Нэш, Джон Харсаньи и Рейнхард Сэлтен.

Теория игр в жизни и бизнесе

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

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

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

Военный кофликт, по определению, есть столкновение интересов, в котором ни одна из сторон не распоряжается полностью переменными, определяющими исход, который решается рядом битв. Можно просто считать исход выигрышем или проигрышем и приписать им численные значения 1 и 0.

Одна из самых простых конфликтных ситуаций, которая может быть записана и решена в теории игр - дуэль, представляющая собой конфликт двух игроков 1 и 2, имеющих соответственно p и q выстрелов. Для каждого игрока существует функция, указывающая вероятность того, что выстрел игрока i в момент времени t даст попадание, которое окажется смертельным.

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

Математическая модель в теории игр и формализация задач

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

1. заинтересованных сторон;
2. возможных действий с каждой стороны;
3. интересов сторон.

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

Реальная конфликтная ситуация не всегда, а игра (в понятии теории игр) - всегда - протекает по определённым правилам , которые точно определяют:

1. варианты действий игроков;
2. объём информации каждого игрока о поведении партнёра;
3. выигрыш, к которому приводит каждая совокупность действий.

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

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

Для игры характерна неопределённость результата . Причины неопределённости можно распределить по следующим группам:

1. комбинаторные (как в шахматах);
2. влияние случайных факторов (как в игре "орёл или решка", кости, карточные игры);
3. стратегические (игрок не знает, какое действие предпримет противник).

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

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

Классификация игр

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

Классический пример из теории игр - дилемма заключённого

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

Если эту стратегическую задачу сформулировать в сроках заключения, то она сводится к следующему:

Таким образом, если оба заключённых не признаются, они получат по 1 году каждый. Если оба признаются, то каждый получит по 8 лет. А если один признается, другой не признается, то тот, который признался отделается тремя месяцами заключения, а тот, который не признается, получит 10 лет. Приведённая выше матрица правильно отражает дилемму заключённого: перед каждым стоит вопрос - признаться или не признаться. Игра, которую окружной прокурор предлагает заключённым, представляет собой некооперативную игру или иначе - бескоалиционную игру . Если бы оба заключённых имели возможность сотрудничать (то есть игра была бы кооперативной или иначе коалиционной игрой ), то оба не признались бы и получили по году тюрьмы каждый.

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

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

Пример формализации некооперативной (бескоалиционной) игры двух лиц

В предыдущем параграфе мы уже рассмотрели пример некооперативной (бескоалиционной) игры (дилемма заключённого). Давайте закрепим наши навыки. Для этого подойдёт также классический сюжет, навеянный "Приключениями Шерлока Холмса" Артура Конан Дойля. Можно, конечно, возразить: пример не из жизни, а из литературы, но ведь Конан Дойль не зарекомендовал себя как писатель-фантаст! Классический ещё и потому, что задание выполнено Оскаром Моргенштерном, как мы уже установили - одним из основателей теории игр.

Пример 1. Будет приведено сокращённое изложение фрагмента одного из "Приключений Шерлока Холмса". Согласно известным понятиям теории игр составить модель конфликтной ситуации и формально записать игру.

Шерлок Холмс намерен отправиться из Лондона в Дувр с дальнейшей целю попасть на континент (европейский), чтобы спастись от профессора Мориарти, который преследует его. Сев в поезд, он увидел на вокзальной платформе профессора Мориарти. Шерлок Холмс допускает, что Мориарти может выбрать особый поезд и обогнать его. У Шерлока Холмса две альтернативы: продолжать поездку до Дувра или сойти на станции Кентерберри, являющейся единственной промежуточной станцией на его маршруте. Мы принимаем, что его противник достаточно разумен, чтобы определить возможности Холмса, поэтому перед ним те же две альтернативы. Оба противника должны выбрать станцию, чтобы сойти на ней с поезда, не зная, какое решение примет каждый из них. Если в результате принятия решения оба окажутся на одной и той же станции, то можно однозначно считать, что Шерлок Холмс будет убит профессором Мориарти. Если же Шерлок Холмс благополучно доберётся до Дувра, то он будет спасён.

Решение. Героев Конан Дойля можем рассматривать как участников игры, то есть игроков. В распоряжении каждого игрока i (i =1,2) две чистые стратегии:

• сойти в Дувре (стратегия s i1 (i =1,2) );
• сойти на промежуточной станции (стратегия s i2 (i =1,2) )

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

Каждой комбинации можно поставить в соответствие событие - исход попытки убийства Шерлока Холмса профессором Мориарти. Составляем матрицу данной игры с возможными событиями.

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

Пример формализации и решения кооперативной (коалиционной) игры n лиц

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

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

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

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

Для игры n обозначим множество всех её игроков как N = {1,2,...,n} Любое непустое подмножество множества N обозначим как Т (включая само N и все подмножества, состоящие из одного элемента). На сайте есть занятие "Множества и операции над множествами ", которое при переходе по ссылке открывается в новом окне.

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

Для двух непустых коалиций из подмножеств T 1 и T 2 аддитивность характеристической функции кооперативной (коалиционной) игры записывается так:

А супераддитивность так:

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

В среднем их выручка за один вечер составляла:

• у скрипача 600 единиц;
• у гитариста 700 единиц;
• у певицы 900 единиц.

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

• скрипач + гитарист зарабатывали 1500 единиц;
• скрипач + певица зарабатывали 1800 единиц;
• гитарист + певица зарабатывали 1900 единиц;
• скрипач + гитарист + певица зарабатывали 3000 единиц.

Решение. В этом примере число участников игры n = 3 , следовательно, область определения характеристической функции игры состоит из 2³ = 8 возможных подмножеств множества всех игроков. Перечислим все возможные коалиции T :

• коалиции из одного элемента, каждая из которых состоит из одного игрока - музыканта: T {1} , T {2} , T {3} ;
• коалиции из двух элементов: T {1,2} , T {1,3} , T {2,3} ;
• коалиция из трёх элементов: T {1,2,3} .

Каждому из игроков присвоим порядковый номер:

• скрипач - 1-й игрок;
• гитарист - 2-й игрок;
• певица - 3-й игрок.

По данным задачи определим характеристическую функцию игры v :

v(T{1}) = 600 ; v(T{2}) = 700 ; v(T{3}) = 900 ; эти значения характеристической функции определены исходя из выигрышей соответственно первого, второго и третьего игроков, когда они не объединяются в коалиции;

v(T{1,2}) = 1500 ; v(T{1,3}) = 1800 ; v(T{2,3}) = 1900 ; эти значения характеристической функции определены по выручке каждой пары игроков, объединившихся в коалиции;

v(T{1,2,3}) = 3000 ; это значение характеристической функции определено по средней выручке в случае, когда игроки объединялись в тройки.

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

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

Забавный пример применения теории игр есть в фэнтезийной книжке Энтони Пирса «Бравый голем»

Много текста

– Смысл того, что я сейчас вам всем продемонстрирую, – начал Гранди, – заключается в наборе необходимого количества баллов. Баллы могут быть самыми различными – все зависит от комбинации решений, которые принимаются участниками игры. К примеру, предположим, что каждый участник свидетельствует против своего товарища по игре. В этом случае каждому участнику можно присудить по одному очку!
– Одно очко! – сказала Морская Ведьма, проявляя к игре неожиданный интерес. Очевидно, колдунья хотела удостовериться в том, что у голема нет никаких шансов, чтобы демон Ксант остался им доволен.
– А теперь давайте предположим, что каждый из участников игры не свидетельствует против своего товарища! – продолжал Гранди. – В этом случае каждому можно присудить по три балла. Я хочу особенно отметить, что покуда все участники действуют одинаково, то им присуждается одинаковое количество баллов. Ни у кого нет никаких преимуществ перед другим.
– Три очка! – сказала вторая ведьма.
– Но вот теперь мы вправе предложить, что один из игроков начал давать показания против второго, а второй все равно молчит! – сказал Гранди. – В таком случае тот, кто эти показания дает, получает сразу пять очков, а тот, который молчит, не получает ни одного очка!
– Ага! – в один голос воскликнули обе ведьмы, хищно облизывая губы. Было видно, что обе они явно собирались получить по пять очков.
– Я все время терял очки! – воскликнул демон. – Но ведь ты пока только обрисовал ситуацию, а способа ее разрешения еще не представил! Так в чем заключается твоя стратегия? Не надо тянуть время!
– Погоди, сейчас я все объясню! – воскликнул Гранди. – Каждый из нас четверых – нас тут двое големов и две ведьмы – будет сражаться против своих противников. Конечно же, ведьмы постараются никому ни в чем не уступить…
– Конечно! – воскликнули снова обе ведьмы в унисон. Они отлично понимали голема с полуслова!
– А второй голем будет следовать моей тактике, – продолжал Гранди невозмутимо. Он посмотрел на своего двойника. – Ты, конечно, в курсе?
– Да, конечно! Я ведь твоя копия! Я прекрасно все понимаю, что ты думаешь!
– Вот и отлично! В таком случае, давайте-ка сделаем первый ход, чтобы демон смог сам все увидеть. В каждом поединке будет несколько раундов, чтобы вся стратегия смогла проявиться до конца и произвела впечатление целостной системы. Пожалуй, мне следует начать.

– Теперь каждый из нас должен наносить отметки на своих листках бумаги! – обратился голем к ведьме. – Сначала следует нарисовать улыбающееся лицо. Это будет означать, что мы не будем давать показания на товарища по заключению. Можно также нарисовать насупленное лицо, которое означает, что мы думаем только о себе и нужные показания на своего товарища даем. Мы оба сознаем, что лучше было бы, если бы никто не оказался тем самым насупленным лицом, но ведь, с другой стороны, насупленное лицо получает определенные преимущества перед улыбающимся! Но суть заключается в том, что каждый из нас не знает, что выберет другой! Не будем знать до тех пор, покуда партнер по игре не откроет своего рисунка!
– Начинай ты, сволочь! – выругалась ведьма. Она, как всегда, не могла обойтись без бранных эпитетов!
– Готово! – воскликнул Гранди, нарисовав большое улыбающееся лицо на своем листочке бумаги таким образом, чтобы ведьма не смогла увидеть, что он изобразил там. Ведьма сделала свой ход, тоже изобразив лицо. Надо думать, она непременно изобразила недобрую физиономию!
– Ну, а теперь нам остается только показать друг другу наши рисунки, – объявил Гранди. Обернувшись назад, он открыл рисунок публике и показал его во все стороны, чтобы рисунок смогли увидеть все. Что-то недовольно ворча, то же самое сделала и Морская Ведьма.
Как Гранди и рассчитывал, с рисунка колдуньи смотрело злое, недовольное лицо.
– Теперь вы, уважаемые зрители, – сказал Гранди торжественно, – видите, что ведьма предпочла давать на меня показания. Я не собираюсь этого делать. Таким образом, Морская Ведьма набирает пять очков. А я, соответственно, не получаю ни одного балла. И тут…
По рядам зрителей снова прокатился легкий шумок. Все явно сочувствовали голему и страстно желали, чтобы Морская Ведьма проиграла.
Но ведь игра только-только началась! Если только его стратегия была верной…
– Теперь мы можем перейти ко второму раунду! – объявил Гранди торжественно. – Мы снова должны повторить ходы. Каждый рисует лицо, которое ему ближе!
Так и сделали. Гранди изображал теперь хмурое, недовольное лицо.
Как только игроки показали свои рисунки, публика увидела, что теперь оба они изобразили злые лица.
– По два очка каждому! – сказал Гранди.
– Семь два в мою пользу! – заорала ведьма радостно. – Ты никуда отсюда не выберешься, мерзавец!
– Начинаем снова! – воскликнул Гранди. Они сделали по очередному рисунку и показали их публике. Снова те же самые злые лица.
– Каждый из нас повторил предыдущий ход, повел себя эгоистично, а потому, как мне кажется, лучше никому не присуждать очков! – заявил голем.
– Но я все равно веду в игре! – сказала ведьма, радостно потирая руки.
– Ладно, не шуми! – сказал Гранди. – Игра ведь не закончилась. Посмотрим, что будет! Итак, уважаемая публика, мы начинаем четвертый по счету раунд!
Игроки снова сделали рисунки, показав публике то, что они изобразили на своих листках. Оба листка снова явили зрителям те же злые физиономии.
– Восемь – три! – закричала ведьма, заливаясь злобным смехом. – Своей дурацкой стратегией ты выкопал себе могилу, голем!
– Пятый раунд! – закричал Гранди. Повторилось то же самое, что и в прежние раунды, – снова злые лица, только счет изменился – он стал девять – четыре в пользу колдуньи.
– Теперь последний, шестой раунд! – возвестил Гранди. Его предварительные расчеты показывали, что именно этот раунд должен стать судьбоносным. Теперь теория должна была подтвердиться либо быть опровергнута практикой.
Несколько быстрых и нервных движений карандаша по бумаге – и оба рисунка предстали перед глазами публики. Снова два лица, теперь даже с оскаленными зубами!
– Десять – пять в мою пользу! Моя игра! Я победила! – загоготала Морская Ведьма.

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

– Но наше состязание еще не закончено! – крикнул звонко Гранди. – Это ведь была только первая часть игры.
– Да вам целую вечность подавай! – заворчал демон Ксант недовольно.
– Это верно! – сказал Гранди спокойно. – Но ведь один тур ничего не решает, только методичность указывает на лучший результат.
Теперь голем подошел к другой ведьме.
– Я хотел бы сыграть этот тур с другим противником! – объявил он. – Каждый из нас будет изображать лица, как это было в предыдущий раз, потом будет демонстрировать нарисованное публике!
Так они и сделали. Результат был таким же, как и в прошлый раз – Гранди нарисовал улыбающуюся рожицу, а ведьма – так вообще череп. Она сразу набрала преимущество в целых пять баллов, оставив Гранди позади.
Оставшиеся пять раундов окончились с теми результатами, которых и можно было ожидать. Снова счет стал десять – пять в пользу Морской Ведьмы.
– Голем, мне очень нравится твоя стратегия! – хохотала колдунья.
– Итак, вы просмотрели два тура игры, уважаемые зрители! – воскликнул Гранди. – Я, таким образом, набрал десять очков, а мои соперницы – двадцать!
Публика, которая тоже вела подсчет очков, скорбно закивала головами. Их подсчет совпал с подсчетами голема. Только облако по имени Фракто казалось весьма довольным, хотя, конечно, ведьме оно тоже не симпатизировало.
Но Рапунцелия одобряюще улыбнулась голему – она продолжала верить в него. Она, возможно, осталась единственной, кто верил ему теперь. Гранди надеялся, что он оправдает это безграничное доверие.
Теперь Гранди подошел к своему третьему сопернику – своему двойнику. Он должен был стать его последним противником. Быстро чиркнув карандашами по бумаге, големы показали листочки публике. Все увидели две смеющихся рожицы.
– Заметьте, дорогие зрители, каждый из нас предпочел быть добрым сокамерником! – воскликнул Гранди. – А посему никто из нас не получил в этой игре необходимого преимущества перед соперником. Таким образом, мы оба получаем по три балла и приступаем к следующему раунду!
Второй раунд начался. Результат был тот же, что и в предыдущий раз. Затем оставшиеся раунды. И в каждый раунд оба противника набирали опять по три балла! Это было просто невероятно, но публика была готова подтвердить все происходящее.

Наконец и этот тур подошел к концу, и Гранди, быстро водя своим карандашиком по бумаге, стал подсчитывать результат. Наконец он объявил торжественно:
– Восемнадцать на восемнадцать! В общей сложности я набрал двадцать восемь очков, а мои соперники набрали тридцать восемь!
– Значит, ты проиграл, – возвестила Морская Ведьма радостно. – Победителем станет, таким образом, кто-то из нас!
– Возможно! – спокойно отозвался Гранди. Теперь наступал еще один важный момент. Если все пройдет так, как им и было задумано…
– Нужно довести дело до конца! – воскликнул второй голем. – Мне ведь тоже еще нужно сразиться с двумя Морскими Ведьмами! Игра еще не закончена!
– Да, конечно, давай! – сказал Гранди. – Но только руководствуйся стратегией!
– Да, конечно! – заверил его двойник.
Этот голем подошел к одной из ведьм, и тур начался. Завершился он с тем же результатом, с которым из подобного раунда вышел сам Гранди – счет был десять-пять в пользу колдуньи. Ведьма прямо-таки сияла от невыразимой радости, а публика угрюмо замолчала. Демон Ксант выглядел несколько уставшим, что было не слишком добрым предзнаменованием.
Теперь пришло время заключительного раунда – одна ведьма должна была сражаться против второй. Каждая имела в активе по двадцать очков, которые она смогла получить, сражаясь с големами.
– А теперь, если ты позволишь набрать мне хотя бы несколько лишних очков… – заговорщицки прошептала Морская Ведьма своему двойнику.
Гранди старался сохранить спокойствие хотя бы внешне, хотя в душе его бушевал ураган противоречивых чувств. Его удача сейчас зависела от того, насколько верно он предугадал возможное поведение обеих ведьм – ведь характер их был, в сущности, одним и тем же!
Сейчас наступал самый, пожалуй, критический момент. Но если он ошибся!
– С какой это стати я должна тебе уступать! – прокаркала вторая ведьма первой. – Я сама хочу набрать больше очков и выбраться отсюда!
– Ну, если ты так нахально ведешь себя, – завопила претендентка, – то я тебя сейчас отделаю так, что ты больше не будешь похожа на меня!
Ведьмы, одарив друг друга ненавидящими взглядами, начертили свои рисунки и показали их публике. Конечно же, ничего другого, кроме двух черепов, там оказаться просто не могло! Каждая набрала по одному очку.
Ведьмы, осыпая друг друга проклятьями, приступили ко второму раунду. Результат опять тот же самый – снова два коряво нарисованных черепа. Ведьмы, таким образом, набрали еще по одному очку. Публика старательно все фиксировала.
Так продолжалось и в дальнейшем. Когда тур закончился, усталые ведьмы обнаружили, что каждая из них набрала по шесть очков. Снова ничья!
– Теперь давайте подсчитаем получившиеся результаты и все сравним! – торжествующе сказал Гранди. – Каждая из ведьм набрала по двадцать шесть очков, а големы набрали по двадцать восемь баллов. Итак, что мы имеем? А имеем мы тот результат, что големы имеют большее количество очков!
По рядам зрителей прокатился вздох удивления. Взволнованные зрители стали писать на своих листочках столбики цифр, проверяя правильность подсчета. Многие за это время просто не считали количество набранных баллов, считая, что результат игры им уже известен. Обе ведьмы стали рычать от негодования, непонятно, кого именно обвиняя в происшедшем. Глаза демона Ксанта вновь загорелись настороженным огнем. Его доверие оправдалось!
– Я прошу вас, уважаемая публика, обратить внимание на тот факт, – поднял руку Гранди, требуя от зрителей успокоиться, – что ни один из големов не выиграл ни единого раунда. Но окончательная победа все-таки будет за одним из нас, из големов. Результаты будут более красноречивыми, если состязание продолжится и дальше! Я хочу сказать, дорогие мои зрители, что в вечном поединке моя стратегия будет неизменно оказываться выигрышной!
Демон Ксант с интересом прислушивался к тому, что говорил Гранди. Наконец он, испуская клубы пара, открыл рот:
– А в чем конкретно заключается твоя стратегия?
– Я называю ее «Быть твердым, но честным»! – пояснил Гранди. – Я начинаю игру честно, но затем начинаю проигрывать, потому что мне попадаются очень специфические партнеры. Поэтому в первом раунде, когда оказывается, что Морская Ведьма начинает давать против меня показания, я автоматически остаюсь проигравшим и во втором раунде – и так продолжается до конца. Результат может быть другим, ежели ведьма переменит свою тактику ведения игры. Но поскольку ей такое даже в голову прийти не может, мы продолжали играть по предыдущему шаблону. Когда я начал играть со своим двойником, то он хорошо отнесся ко мне, а я хорошо относился к нему в следующем раунде игры. Поэтому игра у нас пошла тоже по-другому и несколько однообразно, поскольку мы не хотели изменять тактику…
– Но ведь вы не выиграли ни единого тура! – удивленно возразил демон.
– Да, а эти ведьмы не проиграли ни одного тура! – подтвердил Гранди. – Но ведь победа не автоматически достается тому, за кем остались туры. Победа достается тому, кто набрал большее количество баллов, а это совсем другое дело! Мне удалось набрать больше очков, когда мы играли вместе с моим двойником, чем когда я играл с ведьмами. Их эгоистическое отношение принесло им сиюминутную победу, но в плане более долгосрочном оказалось, что именно из-за этого обе они проиграли игру целиком. Часто случается и такое!

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

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

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

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

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

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

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

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

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

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

Врученная в 1994 году первая Нобелевская премия за результаты в области теории игр (Джону Нэшу, Райнхарду Зелтену и Джону Харсаньи) фактически утвердила статус теории игр как самостоятельного научного направления со своими задачами и методами их решений. Последовавшие за этим еще несколько Нобелевских премий вручались как за фундаментальные теоретико-игровые результаты, так и за приложения теории игр к той или иной стороне нашей жизни. В ведущих университетах мира на программах и по экономике, и по политическим наукам теория игр обязательно входит в стандартный набор курсов. Часто ее изучают и психологи, и математики.

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

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

Возникшая в сороковых годах XX века математическая теория игр чаще всего применяется именно в экономике. Но как с помощью концепции игр смоделировать поведение людей в обществе? Зачем экономисты изучают, в какой угол чаще бьют пенальти футболисты, и как выиграть в «Камень, ножницы, бумагу» в своей лекции рассказал старший преподаватель кафедры микроэкономического анализа ВШЭ Данил Федоровых.

Джон Нэш и блондинка в баре

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

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

Игра - любая ситуация, в которой выигрыши агентов зависят друг от друга.

Стратегия - описание действий игрока во всех возможных ситуациях.

Исход - комбинация выбранных стратегий.

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

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

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

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

Рассмотрим другие игры на предмет равновесия. Например, в «Камне, ножницах, бумаге» нет равновесия по Нэшу: во всех ее вероятных исходах нет варианта, в котором оба участника были бы довольны своим выбором. Тем не менее, существует Чемпионат мира и World Rock Paper Scissors Society, собирающее игровую статистику. Очевидно, что вы можете повысить свои шансы на победу, если будете что-то знать об обычном поведении людей в этой игре.

Чистая стратегия в игре - это такая стратегия, при которой человек всегда играет одинаково, выбирая одни и те же ходы.

По данным World RPS Society, камень является самым часто выбираемым ходом (37,8%). Бумагу ставят 32,6%, ножницы - 29,6%. Теперь вы знаете, что нужно выбирать бумагу. Однако, если вы играете с тем, кто тоже это знает, вам уже не надо выбирать бумагу, потому что от вас ожидается то же самое. Есть знаменитый случай: в 2005 году два аукционных дома Sotheby“s и Christie”s решали, кому достанется очень крупный лот - коллекция Пикассо и Ван Гога со стартовой ценой в 20 миллионов долларов. Собственник предложил им сыграть в «Камень, ножницы, бумагу», и представители домов отправили ему свои варианты по электронной почте. Sotheby“s, как они позже рассказали, особо не задумываясь, выбрали бумагу. Выиграл Christie”s. Принимая решение, они обратились к эксперту - 11-летней дочери одного из топ-менеджеров. Она сказала: «Камень кажется самым сильным, поэтому большинство людей его выбирают. Но если мы играем не с совсем глупым новичком, он камень не выбросит, будет ожидать, что это сделаем мы, и сам выбросит бумагу. Но мы будем думать на ход вперед, и выбросим ножницы».

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

Смешанные стратегии и спорт

Более серьезных примеров смешанных стратегий очень много. Например, куда подавать в теннисе или бить/принимать пенальти в футболе. Если вы ничего не знаете о вашем сопернике или просто постоянно играете против разных, лучшей стратегией будет поступать более-менее случайно. Профессор Лондонской школы экономики Игнасио Паласиос-Уэрта в 2003 году опубликовал в American Economic Review работу, суть которой заключалась в поиске равновесия по Нэшу в смешанных стратегиях. Предметом исследования Паласиос-Уэрта выбрал футбол и в связи с этим просмотрел более 1400 ударов пенальти. Разумеется, в спорте все устроено хитрее, чем в «Камне, ножницах, бумаге»: там учитывается сильная нога спортсмена, попадания в разные углы при ударе со всей силы и тому подобное. Равновесие по Нэшу здесь заключается в расчете вариантов, то есть, к примеру, определении углов ворот, в которые надо бить, чтобы выиграть с большей вероятностью, зная свои слабые и сильные стороны. Статистика по каждому футболисту и найденное в ней равновесие в смешанных стратегиях, показало, что футболисты поступают примерно так, как предсказывают экономисты. Вряд ли стоит утверждать, что люди, которые бьют пенальти, читали учебники по теории игр и занимались довольно непростой математикой. Скорее всего, есть разные способы научиться оптимально себя вести: можно быть гениальным футболистом, и чувствовать, что делать, а можно - экономистом, и искать равновесие в смешанных стратегиях.

В 2008 году профессор Игнасио Паласиос-Уэрта познакомился с Авраамом Грантом, тренером «Челси», который играл тогда в финале Лиги чемпионов в Москве. Ученый написал записку тренеру с рекомендациями по серии пенальти, которые касались поведения вратаря соперника - Эдвина ван дер Сара из «Манчестер Юнайтед». Например, по статистике, он почти всегда отбивал удары на среднем уровне и чаще бросался в естественную для пробивающего пенальти сторону. Как мы определили выше, правильнее все-таки рандомизировать свое поведение с учетом знаний о сопернике. Когда счет по пенальти был уже 6:5, Николя Анелька, нападающий «Челси», должен был забивать. Показывая перед ударом в правый угол, ван дер Сар будто спросил у Анелька, не собирается ли он бить туда.

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

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

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

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

Улучшение по Парето

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

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

Трагедия общины

«Дилемма заключенного» - это игрушечная стилизованная история. Вряд ли вы ожидаете оказаться в подобной ситуации, но похожие эффекты есть везде вокруг нас. Рассмотрим «Дилемму» с большим количеством игроков, ее иногда называют трагедией общины. Например, на дорогах - пробки, и я решаю, как ехать на работу: на машине или на автобусе. Это же делают остальные. Если я поеду на машине, и все решат сделать то же самое, будет пробка, но мы доедем с комфортом. Если я поеду на автобусе, пробка-то все равно будет, но ехать я буду некомфортно и не особо быстрее, поэтому такой исход еще хуже. Если же в среднем все ездят на автобусе, то я, сделав то же самое, довольно быстро доеду без пробки. Но если при таких условиях поехать на машине, я тоже доеду быстро, но еще и с комфортом. Итак, наличие пробки не зависит от моих действий. Равновесие по Нэшу здесь - в ситуации, когда все выбирают ехать на машине. Что бы не делали остальные, мне лучше выбрать машину, потому что будет там пробка или нет, неизвестно, но я в любом случае доеду с комфортом. Это доминирующая стратегия, поэтому в итоге все едут на машине, и мы имеем то, что имеем. Задача государства - сделать поездку на автобусе лучшим вариантом хотя бы для некоторых, поэтому появляются платные въезды в центр, парковки и так далее.

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

Когда вас призывают прийти на субботник, ни от кого в отдельности не будет зависеть, станет двор чистым или нет: если я выйду один, я не смогу убрать все, или, если выйдут все, то не выйду я, потому что все и без меня уберут. Другой пример - перевозка грузов в Китае, о котором я узнал в замечательной книге Стивена Ландсбурга «Экономист на диване». 100-150 лет назад в Китае был распространен способ перевозки грузов: все складывалось в большой кузов, который тащили семь человек. Заказчики платили, если груз доставлялся вовремя. Представьте, что вы - один из этих шести. Вы можете прилагать усилия, и тянуть изо всех сил, и если все будут так делать, груз доедет вовремя. Если кто-нибудь один так делать не будет, все тоже доедут вовремя. Каждый думает: «Если все остальные тянут как следует, зачем это делать мне, а если все остальные тянут не со всей силы, то я ничего не смогу изменить». В итоге, со временем доставки все было очень плохо, и сами грузчики нашли выход: они стали нанимать седьмого и платить ему деньги за то, чтобы он стегал лентяев плетью. Само наличие такого человека заставляло всех работать изо всех сил, потому что иначе все попадали в плохое равновесие, из которого никому в отдельности с выгодой не выйти.

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

Сommitment device

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

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

Другие примеры игр:

Модель Бертрана

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

Разъезд на узкой дороге

Рассмотрим примеры выбора между двумя возможными равновесиями. Представьте, что Петя и Маша едут навстречу друг другу по узкой дороге. Дорога настолько узкая, что им обоим нужно съехать на обочину. Если они решат повернуть налево или направо от себя, они просто разъедутся. Если же один повернет направо, а другой налево от себя, или наоборот, случится авария. Как выбрать, куда съехать? Чтобы помогать искать равновесие в подобных играх, существуют, например, правила дорожного движения. В России каждому нужно повернуть направо.

В забаве Chiken, когда два человека едут на большой скорости навстречу друг другу, тоже есть два равновесия. Если оба сворачивают на обочину, возникает ситуация, которая называется Chiken out, если оба не сворачивают, то погибают в страшной аварии. Если я знаю, что мой соперник едет прямо, мне выгодно съехать, чтобы выжить. Если я знаю, что мой соперник съедет, то мне выгодно ехать прямо, чтобы после получить 100 долларов. Сложно предсказать, что случится на самом деле, однако, у каждого из игроков есть свой метод выиграть. Представьте, что я закрепил руль так, что его нельзя повернуть, и показал это своему сопернику. Зная, что у меня нет выбора, соперник отскочит.

QWERTY-эффект

Иногда бывает очень сложно перейти из одного равновесия в другое, даже если оно означает пользу для всех. Раскладка QWERTY была создана, чтобы замедлить скорость печати. Поскольку если бы все печатали слишком быстро, головки печатной машинки, которые бьют по бумаге, цеплялись бы друг за друга. Поэтому Кристофер Шоулз разместил часто стоящие рядом буквы на максимально далеком расстоянии. Если вы зайдете в настройки клавиатуры на своем компьютере, вы сможете выбрать там раскладку Dvorak и печатать гораздо быстрее, так как сейчас нет проблемы аналоговых печатных машин. Дворак рассчитывал, что мир перейдет на его клавиатуру, но мы по-прежнему живем с QWERTY. Конечно, если бы мы перешли на раскладку Дворака, будущее поколение было бы нам благодарно. Все мы приложили бы усилия и переучились, в результате вышло бы равновесие, в котором все печатают быстро. Сейчас мы тоже в равновесии - в плохом. Но никому не выгодно быть единственным, кто переучится, потому что за любым компьютером, кроме личного, работать будет неудобно.