О модели принятия решений в рефлексивных играх

ИНФОРМАТИКА И СИСТЕМЫ УПРАВЛЕНИЯ

УДК 519.816

Н.Е. Пособилов, Е.А. Борзая

О МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ В РЕФЛЕКСИВНЫХ ИГРАХ

Нижегородский государственный технический университет им. Р.Е. Алексеева

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

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

Применение: Для этого случая целесообразно использование концепции информационного равновесия.

Ключевые слова: рефлексия, общее знание, агент, концепция связанного равновесия, информационное равновесие, фантомный агент.

Введение

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

Одними из конструктивных задач коллективного поведения и теории игр, является моделирование и оценка стратегии поведения агентов. Однако следует отметить, что для модели необходимо проанализировать как можно больше факторов, влияющих на «игру» агентов. Взаимодействие любого количества агентов можно моделировать некоторой игрой в теоретико-игровом смысле [2, 3]. Пусть взаимодействие агентов представлено в виде такой игры в нормальной форме:

г =<{Xi },{f }>,

где X - множество допустимых действий /-го игрока, а F - его целевая функция. Назовем множества X и F - атрибутами /-го игрока.

В этой игре не учтена структура стратегической рефлексии. Чтобы учесть влияние стратегической рефлексии, мы должны расширить множество атрибутов каждого игрока. Добавим правила принятия им решения в условиях неопределенности Д и множество игроков, чей набор атрибутов ему точно известен S . Таким образом, множество атрибутов Д /-го игрока можно записать в виде

© Пособилов Н.Е., Борзая Е.А., 2014.

А ={Xt,Ft,Dt,St}.

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

Традиционно в теории некооперативных игр предполагается, что агенты выбирают свои действия одновременно и независимо, а информация об игре Г0 является общим знанием (common knowledge [2-7]), т.е. каждому агенту известен набор участников игры все целевые функции и допустимые множества, а также известно, что это известно остальным агентам и им известно также о его информированности и т.д. до бесконечности. Можно сделать вывод, что все агенты знают условия игры и интересы участников.

Для выбора действия в какой-либо ситуации каждый агент должен смоделировать действия других агентов, чтобы самому выбрать действие, максимизирующее целевую функцию (предположение о том, что агент, выбирая свое действие, пытается максимизировать целевую функцию с учетом всей имеющейся у него информации, называется гипотезой рационального поведения [2]). Это моделирование агентом хода мысли других агентов называется рефлексией [4-6]. Под термином рефлексии подразумевается - процесс и результат размышлений агента, а также представлений о реальности, принципах принятия решений, авторефлексии и т.д. других субъектов. И здесь весьма существенную роль играет информированность агентов. Размышления агента о выборе своего действия включают в себя стратегическую рефлексию - какие действия выберут остальные? Размышления такого рода могут быть различными, соответственно исход игры будет не одинаков. В настоящей работе мы будем исходить из наиболее распространенной на сегодняшний день концепции решения игры -равновесия Нэша. Равновесие Нэша - это ситуация, в которой каждый агент выбирает наилучшее для себя действие при фиксированных действиях остальных (или, иначе говоря, ситуация, в которой никто не может увеличить свой выигрыш, выбрав в одностороннем порядке другое действие). Более строго: вектор действий (х*,...,х*п) называется равновесным по Нэшу, если

Wi е Nx* е Argmax £

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

Отметим, что в настоящее время существует ряд моделей, в которых стратегическая рефлексия является более сложной, чем в игре в нормальной форме Г0 (в том числе стратегическая рефлексия в биматричных играх). Среди них: иерархические игры [8], информационные расширения игр [9, 10], концепции связанного равновесия (correlated equilibrium) [3] и решения в угрозах-контругрозах [11]. Тем не менее во всех этих моделях условия игры являются общим знанием. В отличие от перечисленных ранее моделей стратегической рефлексии в настоящей работе рассматривается модель, в которой не все параметры игры являются общим знанием. Для описания этой модели предположим, что выигрыши агентов зависят не только от их действий, но и от некоторого параметра 0 е Q («состояния природы»), значение которого не является общим знанием, т.е. целевая функция /-го агента имеет вид

£

Тогда стратегической рефлексии логически предшествует информационная рефлексия - размышления агента о том, что каждый агент знает (предполагает) о параметре 0 , а также

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

Информационное равновесие

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

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

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

Рассмотрим пример.

Пусть в рефлексивной биматричной игре, где 0 = {1,2}, выигрыши заданы биматрица-ми (агент 1 выбирает строку, агент 2 - столбец, т.е. Х1 = Х2 = {1,2}) в приведенной далее формуле, и при этом второй агент считает общим знанием 0 = 2, а первый агент знает реальное состояние природы 0 = 1 и адекватно информирован о втором. Иными словами,

0 = 0 1 = 1 0 2 =0 21 = 2 :

0=1 0=2

^

.(0,1) (2,0) ^ [ (1,1) (2,2) ^

Пусть далее каждый агент наблюдает свой выигрыш (и это является общим знанием). Для рассматриваемого примера граф рефлексивной игры имеет следующий вид: 1 ^ 2 — 21.

Ясно, что информационным равновесием считается набор х1 = х2 = х21 = 2, т. е. первый и второй агенты, а также 21 -агент (первый агент в представлении второго) выбирают вторые действия. Однако реальное состояние природы 0 = 1 становится известным второму агенту после розыгрыша игры (и получения им выигрыша 0 вместо ожидаемого 2). Поэтому в следующий раз второй агент выберет действие х2 = 1, что побуждает и первого агента изменить свое действие (выбрать х1 = 1).

Таким образом, для стабильности равновесия необходимо, чтобы и //-агент, /, у е N, наблюдал «нужную» величину. Функцию wi (•) будем называть функцией наблюдения /-го агента. Будем считать, что функции наблюдения являются общим знанием среди агентов. Он ожидает в результате игры пронаблюдать

На самом же деле (т. е. /-субъективно, ведь //-агент существует в сознании /-агента) он наблюдает величину

Поэтому требование стабильности для ¿/-агента означает совпадение величин (6) и (7).

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

Заключение

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

Фантомный агент - существующий в представлении реального или другого фантомного агента и наделяемый в рамках этих представлений определенной информированностью;

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

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

Стабильное информационное равновесие, в котором каждый агент (как реальный, так и фантомный) наблюдает тот результат игры, которого ожидает.

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

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

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

Библиографический список

1. Новиков, Д.А. Модели рефлексивного принятия решений / Д.А. Новиков, А.Г. Чхартишвили

// Проблемы управления. 2004. № 4. С. 62-70

2. Губко, М.В. Теория игр в управлении организационными системами / М.В. Губко, Д.А. Новиков. - М.: СИНТЕГ, 2002.

3. Myerson, R.B. Game theory: analysis of conflict / R.B. Myerson. - London: Harvard Univ.

Press, 1991.

4. Лефевр, В.А. Конфликтующие структуры / В.А. Лефевр. - М.: Радио и связь, 1967.

5. Новиков, Д.А. Рефлексивные игры / Д.А. Новиков, А.Г. Чхартишвили. - М.: СИНТЕГ, 2003.

6. Новиков, Д.А. Активный прогноз / Д.А. Новиков, А.Г. Чхартишвили. - М.: ИПУ РАН, 2002.

7. Aumann, R.J. Incomplete information / R.J. Aumann, A. Heifetz // Handbook of Game Theory.

V. III. Chapter 43. Amsterdam: Elseiver (forthcoming).

8. Гермейер, Ю.Б. Игры с непротивоположными интересами / Ю.Б. Гермейер. - М.: Наука,

1976.

9. Кукушкин, Н.С. Теория неантагонистических игр / Н.С. Кукушкин, В.В. Морозов. - М.: Изд-во МГУ, 1984.

10.Aumann, R.J. The bargaining set for cooperative games / M. Dresher, L.S. Shapley, and A.W. Tucker, R.J. Aumann, M.Mashler // Advances in Game Theory. Princeton: Princeton University Press, 1964. P. 443-447.

11.Новиков, Д.А. Прикладные модели информационного управления / Д.А. Новиков, А.Г. Чхартишвили. - М.: ИПУ РАН, 2004.

Дата поступления в редакцию 03.10.2014

N.E. Posobilov, E.A. Borzaya

MODEL DECISION REFLEXIVE GAMES

Nizhny Novgorod state technical university n.a. R.E. Alexeev

Objective: The current state of game-theoretic models of reflexive decision-making does not preclude the appearance of infinite structure awareness agents, but should leave the endless data and calculations, the structure and the outcome will be transparent.

Methodology / Approach: Most of equilibrium concepts, used in the game theory, require that the parameters of the game are common knowledge - all agents know it, all agents know that all agents know it and so on ad infinitum. In the general case the agents have different beliefs about beliefs of each other, thus an infinite (reflexive) belief structure appears.

Results: Within the framework of the model described above it is possible to investigate the dependence of equilibrium and information agents wins from their awareness. In addition, it is possible to formulate and solve the problem of information management with information equilibrium dependence on the structure of awareness, in which subjects are controlled in the desired equilibrium.

Application: For this case the concept of informational equilibrium is fruitful.

Key words: reflection, general knowledge, agent, correlated equilibrium, informational equilibrium, phantom

agent.