=Paper=
{{Paper
|id=Vol-1623/paperme8
|storemode=property
|title=One Method for Constructing Pareto-Optimal Nash Equilibriums
|pdfUrl=https://ceur-ws.org/Vol-1623/paperme8.pdf
|volume=Vol-1623
|authors=Konstantin Kudryavtsev,Vladislav Zhukovskiy,Irina Stabulit
|dblpUrl=https://dblp.org/rec/conf/door/KudryavtsevZS16
}}
==One Method for Constructing Pareto-Optimal Nash Equilibriums==
https://ceur-ws.org/Vol-1623/paperme8.pdf
Один метод построения Парето-оптимальных
равновесий по Нэшу
К.Н. Кудрявцев1, В.И. Жуковский2, И.С. Стабулит3
1
Южно-Уральский государственный университет (НИУ), Челябинск, Россия
kudrkn@gmail.com
2
Московский государственный университет им. М.В. Ломоносова, Москва, Россия
3
Челябинский государственный университет, Челябинск, Россия
Аннотация. В статье рассматриваются оптимальные по Парето равнове-
сия по Нэшу. Получены достаточные условия существования таких рав-
новесий, использующие свертку Гермейера функций выигрыша. В качест-
ве примера построено Парето-оптимальное равновесие по Нэшу в игре
Брайанта.
Ключевые слова: бескоалиционные игры, Парето-оптимальность, равно-
весие по Нэшу
Выбор равновесия в бескоалиционных играх является важной и непростой зада-
чей. Одна из наиболее известных концепций равновесия – равновесие по Нэшу
(NE) [1]. Это понятие широко используется в экономике, социологии, военных
науках и во многих других областях человеческой деятельности. Однако, мно-
жеству ситуаций равновесия по Нэшу присуще одно негативное свойство: могут
существовать две ситуации равновесия по Нэшу такие, что выигрыши каждого
игрока в одной из них строго больше соответствующих выигрышей в другой.
Избавиться от такого «негатива» можно выбирая из всех равновесий по Нэшу
то, которое одновременно является оптимальным по Парето (PoNE). Однако,
разработанные на настоящий момент методы построения NE не могут гаранти-
ровать его оптимальность по Парето. Известные же нам методы поиска PoNE
сводятся, как правило, к нахождению множества всех ситуаций равновесия по
Нэшу, с последующим построением их Парето-границы (например [2,3]).
Предлагаемый метод построения PoNE сводится к нахождению седловой
точки специального вида гермейеровской свертки функций выигрыша. В каче-
стве примера, строится PoNE в игре Брайанта [4].
1 Оптимальное по Парето равновесие по Нэшу
Рассмотрим бескоалиционную игру 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
Один метод построения Парето-оптимальных равновесий по Нэшу 619
Ν, X i iN , fi x iN . (1)
В (1) множество игроков Ν 1, 2,..., N , их стратегии xi Xi R ni i Ν ,
ситуации x x1 ,..., xN X=X1 ... X N , функция выигрыша i-го игрока есть
fi x . Далее используем обозначение x zi x1 ,..., xi 1 , zi , xi 1 ,..., xN .
Определение 1. Ситуация xe x1e ,..., xNe называется равновесной по Нэшу в
игре (1), если
max fi xe xi fi xe i 1,..., N . (2)
xi X i
Игре (1) поставим в соответствие N-критериальную задачу
X , fi x iN . (3)
Определение 2. Альтернатива x P X является оптимальной по Парето в (3),
если при x X несовместна система неравенств
fi x fi x P i 1,..., N ,
из которых хотя бы одно – строгое.
Определение 3. Ситуация x* x1* ,..., x*N называется Парето-оптимальным
равновесием по Нэшу (PoNE) в игре (1), если она: во-первых, равновесна по Нэ-
шу в игре (1); во-вторых, оптимальна по Парето в задаче (3).
2 Достаточные условия существования PoNE
Рассмотрим далее скалярные функции
i x, z fi z xi fi z i N , N 1 x, z fi x fi z , (4)
iN iN
где z z1 ,..., zN , zi X i i 1,..., N , z X , x X . Гермейеровской сверткой
[5] скалярных функций (4) будет
x, z max j x, z . (5)
j 1,..., N 1
Сопоставим игре (1) вспомогательную антагонистическую игру
X , Z X , x, z , (6)
620 К.Н. Кудрявцев, В.И. Жуковский, И.С. Стабулит
в которой первый игрок выбирает свою стратегию x X с целью увеличить, а
его противник формирует стратегию z X , стремясь уменьшить значение пла-
тежной функции x, z из (4), (5).
Седловая точка x 0 , 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 определены функции выигрыша игроков
fi x 2min x1 , x2 ,..., xn xi . (7)
Множество равновесий по Нэшу в этой игре имеет вид [4]
X e xe , ,..., 0,5 ,
но PoNE будет только xe 5,5,...,5 .
Итак, используя следствие 1, построим свертку Гермейера (5), где функции
i x, z 2 min z1 ,..., zi 1 , xi , zi 1 ,..., zn xi
(8)
2 min z1 ,..., zi 1 , zi , zi 1 ,..., zn zi i 1,..., n ,
n 1 x, z 2n min x1 , , xn xi x2 xn
(9)
2n min z1 , , zn z1 z2 zn .
Для i 1,..., n из (8) будет
Один метод построения Парето-оптимальных равновесий по Нэшу 621
xi 2 min z1 ,..., zn , xi min z1 ,..., zi 1 , zi 1 ,..., zn ,
i x, z 2 min z1 ,..., zi 1 , zi 1 , zn xi
2 min z1 ,..., zn zi , xi min z1 ,..., zi 1 , zi 1 ,..., zn .
Ясно, что при каждом i 1,..., n максимум i x, z по xi 0,5 достигается
при xi z min z1 ,..., zi 1 , zi 1 ,..., zn . При этом
max i x, z min z1 ,..., zi 1 , zi 1 , zn 2 min z1 ,..., zn zi .
xi 0,5
Так как min z1 ,..., zi 1 , zi 1 , zn min z1 ,..., zn и zi min z1 ,..., zn , то
max i x, z 0 z X , i 1,..., N . (10)
xX
Легко заметить, что максимум (9) по x X получится при x 5,5,...,5 , и
max n 1 x, z 5n 2n min z1 ,..., zn z1 ... zn . (11)
xX
Из (10) и (11) следует, что при z X будет max x, z max n 1 x, z .
xX xX
Осталось заметить, что минимум по z X функции max x, z достигается
x X
при z* 5,5,...,5 и min max x, z 0 . Следовательно PoNE в исходной игре
zX xX
будет ситуация z 5,...,5 .
*
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 detec-
tion 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)
622 К.Н. Кудрявцев, В.И. Жуковский, И.С. Стабулит
4. Bryant, J.: A simple rational expectations Keynes type model. Quarterly J. Economics 98,
525 – 529 (1983)
5. Гермейер, Ю Б.: Введение в теорию исследования операций. М.: Наука (1971)
6. Жуковский, В.И., Кудрявцев, К.Н.: Парето-равновесная ситуация: достаточные ус-
ловия и существование в смешанных стратегиях. Математическая теория игр и ее
приложения. Т.7, N.1. 74 - 91 (2015)
Один метод построения Парето-оптимальных равновесий по Нэшу 623
One Method for Constructing Pareto-Optimal Nash
Equilibriums
Konstantin Kudryavtsev1, Vladislav Zhukovskiy2 and Irina Stabulit3
1
South Ural State University, 76 Lenin Ave., Chelyabinsk, Russian Federation
kudrkn@gmail.com
2
M.V. Lomonosov Moscow State University, Leninskie Gory, Moscow, Russian Federation
3
Chelyabinsk State University, 129 Bratiev Kashirinykh st., Chelyabinsk, Russian Federation
Abstract. In this paper the strategy profiles that are the Pareto-optimal Nash
equilibriums are considered. Sufficient conditions for existence of the equilibri-
um for the pure strategies are found. These conditions use the Germier convolu-
tions of the utility functions. For example, Pareto-optimal Nash equilibrium in
Bryant games is constructed.
Keywords: non-cooperative game, Pareto-optimums, Nash equilibrium