Шикин Е.В. От игр к играм:
Математическое введение. Изд. 7

Оглавление

К читателю

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

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

"Я имею в виду игры на доске, карточные игры, игры в мяч, спортивные игры и т.д. Что свойственно им всем? – Не говори: "Должно быть нечто общее, иначе бы они не назывались "играми", – но посмотри, есть ли что-нибудь общее для них всех. – Ведь когда ты смотришь на них, ты видишь не что-то общее им всем, а подобия, сходства, причем целый ряд. Как уже было сказано: не думай, а смотри! Погляди, например, на игры на доске с их многообразными сходствами. Затем перейди к карточным играм: здесь ты найдешь множество соответствий с первой группой, но много общих черт исчезнет, зато появятся другие. Если мы далее обратимся к играм в мяч, кое-что общее сохранится, но многое утратится. – Все ли они "развлекательны"? Сравни шахматы и "крестики-нолики". Или: всегда ли есть победа и поражение или соперничество между игроками? Подумай о пасьянсах. В играх с мячом есть победа и поражение; но если ребенок бросает мяч в стену и ловит его, то этот признак исчезает. Посмотри, какую роль играют ловкость и удача. И сколь различны ловкость в шахматах и ловкость в теннисе. Теперь подумай о хороводах: здесь есть элемент развлечения, но как много других черт исчезло! И таким образом мы можем пройти через многие и многие группы игр. И увидеть, как сходства то появляются, то снова исчезают.

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

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

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

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

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

Введение

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

Студент приходит на экзамен, тянет билет и... возникает конфликтная ситуация. Действия сторон – студента и преподавателя – различны, да и их интересы не во всем совпадают.

Разбойники делят добычу – снова конфликт.

Конфликтна и ситуация, в которую волею сочинителя оказываются вовлеченными три девицы, что

"...под окном
Пряли поздно вечерком".

Типичный конфликт характеризуется тремя основными составляющими:

1) заинтересованными сторонами,

2) интересами этих сторон и

3) их возможными действиями.

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

Попробуем разобраться, почему для обозначения конфликтных ситуаций было выбрано именно это слово. Берем "Толковый словарь живого великорусскаго языка Владiмира Даля" (в последние годы подобное обращение считается правилом хорошего тона и носит почти ритуальный характер) и на седьмой странице 2-го тома третьего издания (издание т-ва М.О.Вольфъ, С.Петербург – Москва, 1905) читаем, что игра – это

"забава, установленная по правилам".

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

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

Опишем некоторые основные понятия, используемые в этой теории.

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

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

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

"На леву ехати – богатому быть,
На праву ехати – женату быть,
Как прямо ехати – живу не бывати, –
Нет пути ни прохожему, ни проезжему, ни пролетному".
И раздумался старый Илья Муромец,
Илья Муромец, сын Иванович:
Да в которую дороженьку буде ехати?

В дальнейшем мы ограничимся рассмотрением только игр с выигрышами.

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

– выработке принципов оптимальности, то есть того, какое поведение игроков следует считать разумным, или целесообразным,

– выяснению реализуемости этих принципов, то есть установлению существования оптимальных в выработанном смысле ситуаций и

– отысканию этих реализаций.

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

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

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

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

Об авторе

Шикин Евгений Викторович

Доктор физико-математических наук, профессор кафедры общей математики факультета вычислительной математики и кибернетики МГУ (1982–2001), заведующий кафедрой математических методов в управлении факультета государственного управления МГУ (2002–2016). Заслуженный профессор МГУ. Лауреат премии Президента Российской федерации, лауреат многих научных премий. Был удостоен государственных наград. Член Американского математического общества и других иностранных академий наук. Область научных интересов: геометрия, геометрическое моделирование, игры поиска, компьютерная графика. Подготовил 12 кандидатов наук; в числе его учеников — три доктора наук. Автор более 210 опубликованных работ, в числе которых монографии и учебники.