Один метод построения Парето-оптимальных равновесий по Нэшу К.Н. Кудрявцев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 iN ,  fi  x iN . (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 iN . (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) iN iN где 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 , zX xX то минимаксная стратегия 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) xX Легко заметить, что максимум (9) по x  X получится при x   5,5,...,5 , и max n 1  x, z   5n  2n min z1 ,..., zn   z1  ...  zn . (11) xX Из (10) и (11) следует, что при z  X будет max   x, z   max n 1  x, z  . xX xX Осталось заметить, что минимум по z  X функции max   x, z  достигается x X при z*   5,5,...,5 и min max   x, z   0 . Следовательно PoNE в исходной игре zX xX будет ситуация 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