Тахир Юсупович Базаров, МГУ им. М.В. Ломоносова
Никакой достоверности нет в науках там, где нельзя приложить ни одной из математических наук, и в том, что не имеет связи с математикой.
Леонардо да Винчи.
В соответствии с определением, математическая теория игр является теорией математических моделей принятия оптимальных решений в условиях конфликта (а также в условиях неопределенности). Поэтому вопросы, связанные с оптимальным поведением сторон в конфликтах, с желательными исходами конфликтов, являются в ней основными. Непосредственных вопросов такого рода три:
1) Какими принципами оптимальности следует руководствоваться при рассмотрении конфликтов того или иного типа? Иначе говоря, в чем состоит (оптимальное) решение того или иного конфликта?
2) Реализуем ли применительно к данному классу конфликтов выбранный для него принцип оптимальности? Формально этот вопрос сводится к существованию у конфликтов из заданного класса тех решений, которые выбранным принципом квалифицируются как оптимальные.
3) В чем состоит применение выбранного принципа оптимальности к данному конфликту (или к данному классу конфликтов)? Ответом на этот вопрос должно служить нахождение решения конфликта в том же смысле слова, в каком принято говорить о нахождении решения применительно к любой математической задаче.
К сожалению, понятие оптимальности принимаемого решения значительно труднее поддается формализации, чем понятия конфликта и принятия решения. Эта задача и до сих пор — одна из самых важных в теории игр.
Так как математическая теория игр — теория моделей принятия решений, она не занимается этими решениями как психологическими или волевыми актами; не занимается она и вопросами их фактической реализации.
В рамках теории игр, принимаемые решения выступают как достаточно упрощенные и идеализированные схемы реальных явлений. При этом, разумеется, степень этого упрощения не должна превосходить известных пределов, за которыми модель уже утрачивает существенные черты явления.
То, что теория игр есть теория математических моделей, и она является разделом математики, означает, что конструируемые в ней модели являются формальными, знаковыми (а не, скажем, макетными или аналоговыми) и их формирование и средства анализа также формальны.
В частности, формально же должны вводиться и основные понятия.
Практически это означает, что эти понятия должны задаваться своими свойствами, которым тем самым придается смысл аксиом. Дальнейшее образование понятий и установление свойств может вестись уже без того, чтобы прибегать к каким-либо «интуитивным» соображениям. Сказанное отнюдь не оспаривает практической целесообразности использования интуиции, особенно как способа практической проверки формально полученных результатов.
В соответствии со сказанным при построении теории с самого начала необходимо формализовать те понятия, которые входят в ее определение: 1) конфликт, 2) принятие решения и 3) оптимальность решения.
Принимающие участие в конфликте стороны элементы некоторого абстрактного множества. Часто оказывается целесообразным считать их подмножествами некоторого универсального множества; элементы последнего принято называть игроками, а подмножества игроков, которые являются действующими сторонами в конфликте, — коалициями действия (различные коалиции действия могут пересекаться и даже содержаться одна в другой). Множество всех коалиций действия в конфликте далее будет обозначаться через Âd.
Каждая из коалиций действия К принимает некоторое решение из некоторого множества sk доступных для нее решений. Элементы множества sk называются стратегиями коалиции К.
Выбор каждой из коалиций действия некоторой стратегии определяет то, что называется исходом конфликта. При этом не обязательно, чтобы этот исход понимался как однозначно определенное детерминированное явление. Допустимо, чтобы тот или иной из этих исходов был множеством физических явлений или же случайным явлением, т.е. множеством явлений с вероятностной мерой на нем. Кроме того, некоторые комбинации выбранных коалициями действия стратегий могут оказаться несовместимыми и потому неосуществимыми. В этом случае принято считать, что конфликт не состоялся. (В применении к играм (конфликты) это может выражаться в появлении некоторой помехи, прервавшей игру (конфликты) без возможности ее продолжения).
Все исходы конфликта называются ситуациями. Из сказанного выше следует, что ситуации составляют некоторое множество S, являющееся подмножеством множества всех комбинаций стратегий коалиций действия, т.е. декартова произведения множеств стратегий.
S Ì P SК
K Î Âd.
По поводу заинтересованных в исходах конфликта сторон можно повторить почти все, сказанное в связи с коалициями действия. Их называют коалициями интересов, и они считаются элементами некоторого абстрактного множества, которое далее будет обозначаться через Âи. Коалиции интересов суть подмножества того же множества игроков, что и коалиции действия.
В теории игр множества коалиций действия и множества коалиций интересов рассматриваются как различные. Легко видеть, что в реальных конфликтах могут встречаться коалиции действия, не являющиеся коалициями интересов, и наоборот.
Рассмотрим, наконец, форму выражения заинтересованности для коалиций интересов. Эта заинтересованность проявляется в том, что каждая из этих коалиций предпочитает одни исходы конфликта другим.
Это описывается в виде некоторого отношения предпочтения — абстрактного бинарного отношения ýк на множестве всех ситуаций. Тот факт, что коалиция интересов К предпочитает ситуацию х ситуации у, обозначается как х ýк у.
Вообще говоря, никаких свойств у отношения ýк не предполагается, хотя обычно оно считается транзитивным
(т.е. из х ýк у и уýк Z следует х ýк Z).
В частности, не требуется, чтобы отношение было линейным, т.е. чтобы любые две ситуации были сравнимы друг с другом (в формальной записи для любых двух различных ситуаций х и у либо х ýк у, либо у ýк х).
Нередко отношение предпочтения задается следующим образом. На множестве ситуаций S определяется функция Hк, принимающая вещественные значения и называемая функцией выигрыша коалиции интересов К. Ее значение Нк (х) понимается как выигрыш, который коалиция К получает в ситуации х. Естественно принять, что х ýк у, если Нк (х) > Нк (у).
Итак, конфликтом (или игрой) называется система
Г=
где перечисленные в ломаных скобках множества и отношения связаны друг с другом, как это было описано выше. Математическая теория игр занимается изучением конфликтов (игр) именно в этом понимании.
Смешанная стратегия игрока есть вероятностное распределение на множестве его чистых стратегий.
Пусть дан конфликт (игра) Г. Говорят, что ситуация (т.е. n-набор стратегий) (si*, s2**,..., sn *) равновесна, или что она является ситуацией равновесия, если для любого i = 1, ..., п и для любого s1Î Si имеет место неравенство
.
Другими словами, ситуация равновесна, если ни один игрок не имеет никаких разумных оснований для изменения своей стратегии при условии, что все остальные игроки собираются придерживаться своих стратегий. В этом случае, если каждый игрок знает, как будут играть остальные, он имеет основание придерживаться той стратегии, которая соответствует этой ситуации равновесия; тем самым игра становится весьма устойчивой.
Не все игры имеют ситуацию равновесия. Например, игра в орлянку такой ситуации не имеет.
Если конфликт не имеет ситуаций равновесия, то обычно некоторые игроки пытаются отгадать стратегии остальных участников, сохраняя собственные стратегии в тайне. Что постоянно приводит к нестабильности в развитии взаимодействия. Это наводит на мысль (и это действительно верно), что в конфликтах с полной информацией ситуации равновесия существуют.
В качестве первого классификационного признака возьмем множество коалиций интересов Âи. Если это множество пусто, то конфликт вырождается в явление, в исходах которого никто не заинтересован. Математические модели такого рода явлений составляют содержание традиционной описательной математики.
Если множество Âu состоит из единственной коалиции интересов, то мы также имеем конфликт, выродившийся в явление, в котором единственная заинтересованная сторона стремится выбрать наиболее предпочтительную для себя ситуацию.
Математическая трактовка этого круга вопросов сводится к разного рода экстремальным задачам, классическим, как, например, решаемые в дифференциальном или вариационном исчислениях или современным, которые составляют предмет различных отраслей оптимального программирования (линейное, дискретное, динамическое, стохастическое и т.д.).
Собственно теория игр начинается тогда, когда множество Âu. насчитывает не менее двух заинтересованных сторон.
Следующий признак — количество коалиций действия. Ясно, что рассмотрение конфликтов с пустым множеством коалиций действия лишено смысла: множество ситуаций состоит более чем из одного элемента и вопрос об отношении предпочтения вообще не возникает.
Если в конфликте имеется одна коалиция, то исследование конфликта уже становится содержательным. В этом случае имеется единственное множество стратегий sk, а множество всех ситуаций является его подмножеством: S Ì sk. Поэтому рассмотрение подобного конфликта можно начинать с этого множества ситуаций, считая их стратегиями единственной коалиции действия. Поскольку для таких конфликтов стратегии совпадают с ситуациями, можно применительно к ним термин «стратегия» не употреблять вовсе. В связи с этим такого рода конфликты принято называть нестратегическими.
Нестратегическим конфликтам противостоят конфликты, в которых участвуют более одной коалиции действия. Они называются стратегическими. В большинстве работ по теории игр рассматриваются такие стратегические конфликты, в которых множества коалиций действия и коалиций интересов совпадают (как те, так и другие коалиции называют в этом случае игроками), множество ситуаций совпадает с декартовым произведением множеств стратегий:
S = П SK,
к Î Âd.
а отношения предпочтения (для игроков) определяются соответствующими функциями. Такие конфликты называются бескоалиционными.
Важным частным случаем бескоалиционного конфликта является тот, когда число игроков равно двум, а значения функций выигрыша в любой ситуации равны по величине и противоположны по знаку:
Н1 (s) = ¾ H2 (s).
Такие конфликты называются антагонистическими, или конфликтами двух лиц с нулевой суммой.
Основным изучавшимся во многих исследованиях принципом оптимальности в бескоалиционных конфликтах являлось стремление игроков к ситуациям равновесия. Этот принцип оптимальности иногда называют принципом осуществимости цели, потому что только ситуации равновесия могут быть предметом предварительных договоров, которые будут соблюдаться. (Если в договоре зафиксирована неравновесная ситуация, то хотя бы один из игроков будет заинтересован в нарушении договора и ситуация фактически не будет достигнута.)
В случае антагонистического конфликта принцип осуществимости цели превращается в принцип максимина, а ситуации равновесия становятся седловыми точками.
Принцип осуществимости цели, подобно принципам оптимальности в нестратегических конфликтах, страдает неполнотой: соответствующие ему решения конфликта (т.е. ситуации равновесия) для многих игр не существуют; вместе с тем многие игры имеют и более одного решения. Отсутствие у конфликта решений достаточно успешно преодолевается введением так называемых «смешанных стратегий», преодоление же множественности решений является важной и нерешенной пока проблемой.
