Три вида рациональности в кооперативной игре

Три вида рациональности в кооперативной игре В. И. Жуковский г. Москва, Московский государственный университет им. М. В. Ломоносова e-mail: [email protected] Л. В. Жуковская г. Москва, ФГБУН Центральный экономико-математический институт РАН e-mail: zhukovska[email protected] М. И. Высокос,Л. В. Смирнова г. Орехово Зуево, ГОУ ВО МО Государственный гуманитарно-технологический университет e-mail: mvysok[email protected], smirnovalidiy[email protected] Аннотация: В математической теории игр для определения решения любой игры требуется установить, какое поведение игроков следует считать оптимальным. В бескоалиционных играх понятие оптимальности связано, например, с концепциями равновесия по Нэшу и равновесия по Бержу. Для оптимальности в теории кооперативных игр характерны условия индивидуальной и коллективной рациональности. В работе рассматривается кооперативная игра трех лиц в нормальной форме. Для этой игры вводится понятие коалиционной рациональности, которое сочетает в себе, кроме условий индивидуальной и коллективной рациональности, определенное объединение концепций равновесия по Нэшу и равновесия по Бержу. Для предложенного коалиционного равновесия игры устанавливаются достаточные условия существования. Кроме того, доказано существование такого решения в смешанных стратегиях при непрерывных функциях выигрыша и компактности множества стратегий. Ключевые слова: максимин, максимум по Парето, максимум по Слейтеру, коалиционная рациональность, гермейеровская свертка, смешанные стратегии. Рассматривается игра трех лиц: Γ = ⟨{1,2,3},{𝑋𝑖}𝑖=1,2,3,{𝑓𝑖(𝑥)}𝑖=1,2,3⟩. В игре Γ{1,2,3}— множество порядковых номеров игроков, каждый из которых выбирает свою стратегию 𝑥𝑖∈𝑋𝑖⊂R𝑛𝑖(𝑖= 1,2,3), в результате чего образуются ситуации 𝑥= (𝑥1, 𝑥2, 𝑥3)∈𝑋=∏︀3 𝑖=1 𝑋𝑖⊂R𝑛, 𝑛=∑︀3 𝑖=1 𝑛𝑖. На множестве ситуаций 𝑋определены функции выигры71 ша 𝑓𝑖(𝑥)каждого из игроков (𝑖= 1,2,3), значение которых называется выигрышем игрока 𝑖. Изучение конфликтов, математическая модель которых представлена, в частности, игрой трех лиц вида Γ, обычно проводится с нормативной точки зрения, устанавливающей, какое поведение игроков следует считать оптимальным (разумным, целесообразным). Основными содержательными чертами оптимальности в математической теории игр считаются [1, С. 13] интуитивные представления о выгодности,устойчивости и справедливости. На свойстве устойчивости основана «царствующая» в бескоалиционных играх концепция равновесности по Нэшу (РН) [2, 3], а также появившиеся под ее непосредственным влиянием [4] равновесность по Бержу (РБ), активное равновесие, равновесие угроз и контругроз. Для оптимальности в теории кооперативных игр характерны условия индивидуальной [5, С. 117] и коллективной [5, С. 125] рациональности. Индивидуальная рациональность означает, что выигрыш каждого игрока не меньше его гарантированного выигрыша, который игрок может себе «обеспечить», действуя самостоятельно (применяя свою максиминную стратегию). Коллективная рациональность обеспечивается одним из векторных максимумов (по Слейтеру, Парето, Джоффриону, Борвейну и т. д.), возникающих при объединении всех игроков в одну общую коалицию. Важным в настоящей работе является понятие коалиционной структуры игры (разбиение игроков на попарно непересекающиеся подмножества). Для игры Γтрех лиц таких коалиционных структур может быть пять: P1={{1},{2},{3}},P2={{1,2},{3}},P3={{1,3},{2}}, P4={{1},{2,3}},P5={{1,2,3}}. Здесь структура P1отвечает бескоалиционному «характеру» игры, а P5— кооперативному. Упомянутые условия индивидуальной рациональности сформулируем для коалиционной структуры P1. При этом используем следующее обозначение: ∀𝑖∈ {1,2,3}считаем −𝑖={{1,2,3}∖{𝑖}}. Тогда условие индивидуальной рациональности для ситуации 𝑥*= (𝑥* 1, 𝑥* 2, 𝑥* 3)∈𝑋означает 𝑓0 𝑖= max 𝑥𝑖∈𝑋𝑖 min 𝑥−𝑖∈𝑋−𝑖 𝑓𝑖(𝑥𝑖, 𝑥−𝑖) = min 𝑥−𝑖∈𝑋−𝑖 𝑓𝑖(𝑥0 𝑖, 𝑥−𝑖)≤𝑓𝑖(𝑥*), 𝑖 = 1,2,3, т. е. при применении максиминной стратегии 𝑥0 𝑖имеют место неравенства 𝑓0 𝑖≤𝑓𝑖(𝑥*),𝑖= 1,2,3. Для коалиционной структуры P5в игре Γусловие коллективной рациональности будет обеспечено максимумом по Парето. Именно, на множестве ситуаций 𝑋*⊂𝑋ситуация 𝑥*∈𝑋*⊂𝑋максимальна по Парето в трехкритериальной задаче Γ𝑋*=⟨𝑋*,{𝑓𝑖(𝑥)}𝑖=1,2,3⟩, если ∀𝑥∈𝑋* несовместна система неравенств 𝑓𝑖(𝑥)≥𝑓𝑖(𝑥*),𝑖= 1,2,3, причем хотя 72 бы одно неравенство строгое. Согласно лемме Карлина [6, С. 71], если 3 ∑︀ 𝑖=1 𝑓𝑖(𝑥)≤ 3 ∑︀ 𝑖=1 𝑓𝑖(𝑥*)∀𝑥∈𝑋*, то ситуация 𝑥*максимальна по Парето в задаче Γ𝑋*. Условие коалиционной рациональности формализуем для коалиционных структур P2,P3иP4, основываться будем на подходящем объединении концепции РН и РБ. Для коалиционной структуры P2условие коалиционного равновесия означает выполнение четырех неравенств 𝑓1(𝑥* 1, 𝑥* 2, 𝑥3)≤𝑓1(𝑥*)∀𝑥3∈𝑋3,(1) 𝑓2(𝑥* 1, 𝑥* 2, 𝑥3)≤𝑓2(𝑥*)∀𝑥3∈𝑋3,(2) 𝑓1(𝑥1, 𝑥2, 𝑥* 3)≤𝑓1(𝑥*)∀𝑥𝑗∈𝑋𝑗, 𝑗 = 1,2,(3) 𝑓2(𝑥1, 𝑥2, 𝑥* 3)≤𝑓2(𝑥*)∀𝑥𝑗∈𝑋𝑗, 𝑗 = 1,2,(4) для структуры P3это условие означает 𝑓1(𝑥* 1, 𝑥2, 𝑥* 3)≤𝑓1(𝑥*)∀𝑥2∈𝑋2,(5) 𝑓3(𝑥* 1, 𝑥2, 𝑥* 3)≤𝑓3(𝑥*)∀𝑥2∈𝑋2,(6) 𝑓1(𝑥1, 𝑥* 2, 𝑥3)≤𝑓1(𝑥*)∀𝑥𝑘∈𝑋𝑘, 𝑘 = 1,3,(7) 𝑓3(𝑥1, 𝑥* 2, 𝑥3)≤𝑓3(𝑥*)∀𝑥𝑘∈𝑋𝑘, 𝑘 = 1,3,(8) и, наконец, для структуры P4оно означает 𝑓2(𝑥1, 𝑥* 2, 𝑥* 3)≤𝑓2(𝑥*)∀𝑥1∈𝑋1,(9) 𝑓3(𝑥1, 𝑥* 2, 𝑥* 3)≤𝑓3(𝑥*)∀𝑥1∈𝑋1,(10) 𝑓2(𝑥* 1, 𝑥2, 𝑥3)≤𝑓2(𝑥*)∀𝑥𝑙∈𝑋𝑙, 𝑙 = 2,3,(11) 𝑓3(𝑥* 1, 𝑥2, 𝑥3)≤𝑓3(𝑥*)∀𝑥𝑙∈𝑋𝑙, 𝑙 = 2,3.(12) Ситуацию 𝑥*∈𝑋, для которой выполняются все эти 12 ограничений, назовем коалиционно рациональной для игры Γ. Множество таких ситуаций обозначим через 𝑋*; очевидно, 𝑋*⊂𝑋. Лемма 1. Если выполнены неравенства (3), (11) и (12), то из них следуют соответственно 𝑓𝑖(𝑥*)≥𝑓0 𝑖= max 𝑥𝑖∈𝑋𝑖 min 𝑥−𝑖∈𝑋−𝑖 𝑓𝑖(𝑥𝑖, 𝑥−𝑖) = min 𝑥−𝑖∈𝑋−𝑖 𝑓𝑖(𝑥0 𝑖, 𝑥−𝑖), 𝑖 = 1,2,3. 73 Лемма 2. Верны очевидные импликации (7)→(1), (11)→(2), (3)→(5), (12)→(6), (7)→(9), (8)→(10). Определение. Пару (𝑥*, 𝑓(𝑥*)) ∈𝑋×R3назовем коалиционно равновесной для игры Γ, если: - имеют место следующие шесть равенств: max 𝑥1,𝑥2 𝑓𝑗(𝑥1, 𝑥2, 𝑥* 3) = 𝑓𝑗(𝑥*), 𝑗 = 1,2, max 𝑥1,𝑥3 𝑓𝑘(𝑥1, 𝑥* 2, 𝑥3) = 𝑓𝑘(𝑥*), 𝑘 = 1,3, max 𝑥2,𝑥3 𝑓𝑙(𝑥* 1, 𝑥2, 𝑥3) = 𝑓𝑙(𝑥*), 𝑙 = 2,3, - ситуация 𝑥*∈𝑋максимальна по Парето на множестве всех коалиционно равновесных ситуаций 𝑋*игры Γ. Будем использовать два 𝑛-вектора 𝑥= (𝑥1, 𝑥2, 𝑥3)∈𝑋⊂R𝑛, 𝑛=∑︀3 𝑖=1 𝑛𝑖и𝑧= (𝑧1, 𝑧2, 𝑧3)∈𝑋, а также следующие семь скалярных функций 𝜙1(𝑥, 𝑧) = 𝑓1(𝑥1, 𝑥2, 𝑧3)−𝑓1(𝑧), 𝜙2(𝑥, 𝑧) = 𝑓2(𝑥1, 𝑥2, 𝑧3)−𝑓2(𝑧), 𝜙3(𝑥, 𝑧) = 𝑓1(𝑥1, 𝑧2, 𝑥3)−𝑓1(𝑧), 𝜙4(𝑥, 𝑧) = 𝑓3(𝑥1, 𝑧2, 𝑥3)−𝑓3(𝑧),(13) 𝜙5(𝑥, 𝑧) = 𝑓2(𝑧1, 𝑥2, 𝑥3)−𝑓2(𝑧), 𝜙6(𝑥, 𝑧) = 𝑓3(𝑧1, 𝑥2, 𝑥3)−𝑓3(𝑧), 𝜙7(𝑥, 𝑧) = 3 ∑︁ 𝑖=1 𝑓𝑖(𝑥)− 3 ∑︁ 𝑖=1 𝑓𝑖(𝑧). Построим гермейеровскую свертку этих семи функций: 𝜙(𝑥, 𝑧) = max 𝑘=1,...,7𝜙𝑘(𝑥, 𝑧),(14) заданную на множестве 𝑋×(𝑍=𝑋)⊂R2𝑛. Седловая точка (¯𝑥, 𝑧*)∈𝑋×𝑍скалярной функции 𝜙(𝑥, 𝑧)(из формул (13), (14)) в антагонистической игре Γ𝛼=⟨𝑋, 𝑍 =𝑋, 𝜙(𝑥, 𝑧)⟩определяется цепочкой неравенств 𝜙(𝑥, 𝑧*)≤𝜙(¯𝑥, 𝑧*)≤𝜙(¯𝑥, 𝑧)∀𝑥, 𝑧 ∈𝑋, причем 𝑧*∈𝑋*является минимаксной стратегией, т. е. min 𝑧∈𝑋max 𝑥∈𝑋𝜙(𝑥, 𝑧) = max 𝑥∈𝑋𝜙(𝑥, 𝑧*). 74 Утверждение. Если в игре Γ𝛼существует седловая точка (¯𝑥, 𝑧*), то минимаксная стратегия 𝑧*∈𝑋из игры Γ𝛼является коалиционно равновесной ситуацией исходной игры Γ. Теорема. Если в игре Γмножества 𝑋𝑖∈comp R𝑛𝑖и𝑓(·)∈𝐶(𝑋), 𝑖= 1,2,3, то в этой игре существует коалиционно равновесная ситуация в смешанных стратегиях. Таким образом формализовано понятие коалиционного равновесия (КР), учитывающее интересы любой коалиции в игре Γ. Установлен конструктивный способ нахождения КР, сводящийся к отысканию минимаксной стратегии для специальной гермейеровской свертки. Доказано существование КР в смешанных стратегиях при «привычных» для математического программирования условиях. По мнению авторов, важны и новые качественные результаты, следующие из настоящей статьи: - результаты распространяются на кооперативные игры с любым конечным числом участников (больше трех), в них РН (РБ) соответственно равновесие по Нэшу (по Бержу); - КР «обеспечивает» устойчивость коалиционной структуры к отклонению от КР любых коалиций; - КР применимо, если даже в течение игры меняются коалиционные структуры или даже если все коалиции остаются в наличии; - КР можно использовать при создании устойчивых союзов (альянсов) игроков. Список литературы 1. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985. 2. Nash J. Non-cooperative games // The Annals of Mathematics. 1951. Vol. 54, no. 2. P. 286–295. 3. Nash J. Equilibrium Points in N-person Games // Proc. Nat. Acad. Sci. 1950. Vol. 36. P. 48–49. 4. Жуковский В.И., Чикрий А.А. Линейно–квадратичные дифференциальные игры. Киев: Наукова Думка, 1994. 5. Жуковский В.И. Кооперативные игры при неопределенности и их приложения. М.: Едиториал УРСС, 2009. 6. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Физматлит, 2007. 75