Аннотация. В статье рассматриваются оптимальные по Парето равновесия по Нэшу. Получены достаточные условия существования таких равновесий, использующие свертку Гермейера функций выигрыша. В качестве примера построено Парето-оптимальное равновесие по Нэшу в игре Брайанта. Ключевые слова: бескоалиционные игры, Парето-оптимальность, равновесие по Нэшу Выбор равновесия в бескоалиционных играх является важной и непростой задачей. Одна из наиболее известных концепций равновесия - равновесие по Нэшу (NE) [1]. Это понятие широко используется в экономике, социологии, военных науках и во многих других областях человеческой деятельности. Однако, множеству ситуаций равновесия по Нэшу присуще одно негативное свойство: могут существовать две ситуации равновесия по Нэшу такие, что выигрыши каждого игрока в одной из них строго больше соответствующих выигрышей в другой. Избавиться от такого «негатива» можно выбирая из всех равновесий по Нэшу то, которое одновременно является оптимальным по Парето (PoNE). Однако, разработанные на настоящий момент методы построения NE не могут гарантировать его оптимальность по Парето. Известные же нам методы поиска PoNE сводятся, как правило, к нахождению множества всех ситуаций равновесия по Нэшу, с последующим построением их Парето-границы (например [2,3]). Предлагаемый метод построения PoNE сводится к нахождению седловой точки специального вида гермейеровской свертки функций выигрыша. В качестве примера, строится PoNE в игре Брайанта [4].
Рассмотрим бескоалиционную игру N лиц в нормальной форме
Copyright © by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org Ν,XiiN , fi xiN . В (1) множество игроков Ν 1, 2,..., N , их стратегии xi Xi Rni i Ν , ситуации x x1,..., xN X=X1 ... XN , функция выигрыша i-го игрока есть fi x . Далее используем обозначение x zi x1,..., xi1, zi , xi1,..., xN . Определение 1. Ситуация xe x1e ,..., xNe называется равновесной по Нэшу в игре (1), если
mxiaXxi fi xe xi fi xe i 1,..., N . Игре (1) поставим в соответствие N-критериальную задачу
X , fi xiN .
fi x fi xP i 1,..., N , Определение 2. Альтернатива xP X является оптимальной по Парето в (3), если при x X несовместна система неравенств из которых хотя бы одно – строгое. Определение 3. Ситуация x* x1*,..., x*N называется Парето-оптимальным равновесием по Нэшу (PoNE) в игре (1), если она: во-первых, равновесна по Нэшу в игре (1); во-вторых, оптимальна по Парето в задаче (3). 2
Достаточные условия существования PoNE
Рассмотрим далее скалярные функции
i x, z fi z xi fi z i N, N1 x, z fi x fi z ,
iN iN
где z z1,..., zN , zi Xi i 1,..., N , z X , x X . Гермейеровской сверткой
[5] скалярных функций (
X , Z X , x, z ,
(1)
(2)
(3)
(
Седловая точка x0 , z* в игре (6) определяется цепочкой неравенств (x, z*) (x0, z*) (x0, z) x, z X . В [6] были получены достаточные условия существования PoNE, основанные на следующей теореме. Теорема 1. Если в антагонистической игре (6) существует седловая точка x0 , z* , то минимаксная стратегия z* есть PoNE в бескоалиционной игре (1).
Видимо, при построении PoNE более удобным, чем теорема 1, является следующее следствие. Следствие 1. Если в антагонистической игре (6) минимакс min max x, z 0 , zX xX то минимаксная стратегия z* есть PoNE в бескоалиционной игре (1). 3
Игра Брайанта В качестве примера рассмотрим игру Брайанта [4]. В игре принимает участие n игроков, стратегии которых xi 0,5 i 1,..., n . На множестве X ситуаций x x1,..., xn определены функции выигрыша игроков (7) (8) (9) Множество равновесий по Нэшу в этой игре имеет вид [4]
fi x 2 minx1, x2 ,..., xn xi .
X e xe , ,..., 0,5 , но PoNE будет только xe 5,5,...,5 .
Итак, используя следствие 1, построим свертку Гермейера (5), где функции i x, z 2 minz1,..., zi1, xi , zi1,..., zn xi 2 minz1,..., zi1, zi , zi1,..., zn zi i 1,..., n, n1 x, z 2n minx1, , xn xi x2
xn 2n minz1, , zn z1 z2 zn. Для i 1,..., n из (8) будет xi 2 minz1,..., zn, i x, z 2 minz1,..., zi1, zi1, zn xi 2 minz1,..., zn zi , xi minz1,..., zi1, zi1,..., zn.
xi min z1,..., zi1, zi1,..., zn, Ясно, что при каждом i 1,..., n максимум i x, z по xi 0,5 достигается при xi z minz1,..., zi1, zi1,..., zn . При этом
xmia0x,5i x, z minz1,..., zi1, zi1, zn 2 minz1,..., zn zi . Так как minz1,..., zi1, zi1, zn minz1,..., zn и zi minz1,..., zn , то mxaXxi x, z 0 z X , i 1,..., N . Легко заметить, что максимум (9) по x X получится при x 5,5,...,5 , и maxn1 x, z 5n 2n minz1,..., zn z1 ... zn .
xX Из (10) и (11) следует, что при z X будет max x, z maxn1 x, z . xX xX Осталось заметить, что минимум по z X функции max x, z достигается xX при z* 5,5,...,5 и min max x, z 0 . Следовательно PoNE в исходной игре zX xX будет ситуация z* 5,...,5 . (10) (11) 4
Заключение Предложенный подход позволяет свести поиск PoNE к задаче построения седловой точки во вспомогательной антагонистической игре. Заметим, что численные методы построения седловой точки гермейеровской свертки ранее не разрабатывались. Вероятно, в этой задаче есть свои особенности, изучением которых авторы планируют заняться в будущем. Список литературы 1. Nash, J.F.: Equilibrium points in N-person games. Proc. Nat. Academ. Sci. USA. 36, 48 49 (1950) 2. Gasko, N., Suciu, M., Lung, R.I., Dumitrescu, D.: Pareto-optimal Nash equilibrium detection using an evolutionary approach. Acta Univ. Sapientiae, Informatica 4 N.2, 237 - 246 (2012) 3. Gatti, N., Rocco, M., Sandhom, T.: On the verification and computation of strong Nash equilibrium. Proceedings of the ACM International Joint Conference on Autonomous Agents and Multi-Agent Systems, Saint Paul, USA, May 6-10, 723 - 730 (2013)
Konstantin Kudryavtsev1, Vladislav Zhukovskiy2 and Irina Stabulit3 Abstract. In this paper the strategy profiles that are the Pareto-optimal Nash equilibriums are considered. Sufficient conditions for existence of the equilibrium for the pure strategies are found. These conditions use the Germier convolutions of the utility functions. For example, Pareto-optimal Nash equilibrium in Bryant games is constructed.