Графы и игры

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

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

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

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

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

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

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

• игры сетевого взаимодействия (networking games);
• «когнитивные» игры (cognitive maps games);
• игры на социальных сетях (social networks games);
• игры на сетевых графиках.

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