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

Запропоновано метод рівномірної дискретизації фундаментальних симплексів як множин змішаних стратегій гравців у скінченній безкоаліційній грі для її наближеного розв’язку. Цей розв’язок сприймається як рівноважні ситуації з можливими поступками, оскільки на скінченній симплексній решітці не обов’язк...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Проблемы управления и информатики
Datum:	2015
1. Verfasser:	Романюк, В.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schlagworte:	Методы управления и оценивания в условиях неопределенности
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/208035
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками / В.В. Романюк // Проблемы управления и информатики. — 2015. — № 5. — С. 93-101. — Бібліогр.: 21 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-208035
record_format	dspace
spelling	Романюк, В.В. 2025-10-18T10:32:57Z 2015 Равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками / В.В. Романюк // Проблемы управления и информатики. — 2015. — № 5. — С. 93-101. — Бібліогр.: 21 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208035 519.833+519.6 10.1615/JAutomatInfScien.v47.i9.70 Запропоновано метод рівномірної дискретизації фундаментальних симплексів як множин змішаних стратегій гравців у скінченній безкоаліційній грі для її наближеного розв’язку. Цей розв’язок сприймається як рівноважні ситуації з можливими поступками, оскільки на скінченній симплексній решітці не обов’язково знаходяться рівноважні ситуації за Нешем. Умови дискретизації передбачають, що при мінімальній зміні ситуації за вузлами цієї решітки виграш гравця змінюється не більше, ніж на деяку постійну для нього величину. Побудова симплексної решітки множини змішаних стратегій гравця виконується циклічним спуском від першої чистої стратегії до останньої. Пошук ситуацій, котрі є рівноважними з поступкою, можна прискорити за рахунок розпаралелювання перемноження масивів при обчисленні очікуваних виграшів. A method is suggested for sampling uniformly fundamental simplexes as sets of players’ mixed strategies in the finite noncooperative game for its approximate solution. This solution is treated in the sense of equilibrium situations with possible concessions, as Nash equilibrium situations are not necessarily to be on a finite simplex lattice. The sampling conditions presume that, by changing minimally a situation over nodes of the lattice, the player’s payoff varies no greater than within its constant value. Building a simplex lattice of the player’s mixed strategies set is fulfilled by cyclic descent from the first pure strategy down to the last one. Retrieval of concession-equilibrium situations can be sped up by parallelizing arrays’ multiplication when expected payoffs are calculated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы управления и оценивания в условиях неопределенности Равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками Рівномірна дискретизація фундаментальних симплексів як множин змішаних стратегій гравців у скінченній безкоаліційній грі для знаходження рівноважних ситуацій з можливими поступками Uniform sampling of fundamental simplexes as sets of players’ mixed strategies in the finite noncooperative game for finding equilibrium situations with possible concessions Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками
spellingShingle	Равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками Романюк, В.В. Методы управления и оценивания в условиях неопределенности
title_short	Равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками
title_full	Равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками
title_fullStr	Равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками
title_full_unstemmed	Равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками
title_sort	равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками
author	Романюк, В.В.
author_facet	Романюк, В.В.
topic	Методы управления и оценивания в условиях неопределенности
topic_facet	Методы управления и оценивания в условиях неопределенности
publishDate	2015
language	Russian
container_title	Проблемы управления и информатики
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Рівномірна дискретизація фундаментальних симплексів як множин змішаних стратегій гравців у скінченній безкоаліційній грі для знаходження рівноважних ситуацій з можливими поступками Uniform sampling of fundamental simplexes as sets of players’ mixed strategies in the finite noncooperative game for finding equilibrium situations with possible concessions
description	Запропоновано метод рівномірної дискретизації фундаментальних симплексів як множин змішаних стратегій гравців у скінченній безкоаліційній грі для її наближеного розв’язку. Цей розв’язок сприймається як рівноважні ситуації з можливими поступками, оскільки на скінченній симплексній решітці не обов’язково знаходяться рівноважні ситуації за Нешем. Умови дискретизації передбачають, що при мінімальній зміні ситуації за вузлами цієї решітки виграш гравця змінюється не більше, ніж на деяку постійну для нього величину. Побудова симплексної решітки множини змішаних стратегій гравця виконується циклічним спуском від першої чистої стратегії до останньої. Пошук ситуацій, котрі є рівноважними з поступкою, можна прискорити за рахунок розпаралелювання перемноження масивів при обчисленні очікуваних виграшів. A method is suggested for sampling uniformly fundamental simplexes as sets of players’ mixed strategies in the finite noncooperative game for its approximate solution. This solution is treated in the sense of equilibrium situations with possible concessions, as Nash equilibrium situations are not necessarily to be on a finite simplex lattice. The sampling conditions presume that, by changing minimally a situation over nodes of the lattice, the player’s payoff varies no greater than within its constant value. Building a simplex lattice of the player’s mixed strategies set is fulfilled by cyclic descent from the first pure strategy down to the last one. Retrieval of concession-equilibrium situations can be sped up by parallelizing arrays’ multiplication when expected payoffs are calculated.
issn	0572-2691
url	https://nasplib.isofts.kiev.ua/handle/123456789/208035
citation_txt	Равномерная дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков в конечной бескоалиционной игре для нахождения равновесных ситуаций с возможными уступками / В.В. Романюк // Проблемы управления и информатики. — 2015. — № 5. — С. 93-101. — Бібліогр.: 21 назв. — рос.
work_keys_str_mv	AT romanûkvv ravnomernaâdiskretizaciâfundamentalʹnyhsimpleksovkakmnožestvsmešannyhstrategiiigrokovvkonečnoibeskoalicionnoiigredlânahoždeniâravnovesnyhsituaciisvozmožnymiustupkami AT romanûkvv rívnomírnadiskretizacíâfundamentalʹnihsimpleksívâkmnožinzmíšanihstrategíigravcívuskínčenníibezkoalícíiníigrídlâznahodžennârívnovažnihsituacíizmožlivimipostupkami AT romanûkvv uniformsamplingoffundamentalsimplexesassetsofplayersmixedstrategiesinthefinitenoncooperativegameforfindingequilibriumsituationswithpossibleconcessions
first_indexed	2025-11-24T19:09:22Z
last_indexed	2025-11-24T19:09:22Z
_version_	1850493762513403904
fulltext	© В.В. РОМАНЮК, 2015 Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 5 93 УДК 519.833+519.6 В.В. Романюк РАВНОМЕРНАЯ ДИСКРЕТИЗАЦИЯ ФУНДАМЕНТАЛЬНЫХ СИМПЛЕКСОВ КАК МНОЖЕСТВ СМЕШАННЫХ СТРАТЕГИЙ ИГРОКОВ В КОНЕЧНОЙ БЕСКОАЛИЦИОННОЙ ИГРЕ ДЛЯ НАХОЖДЕНИЯ РАВНОВЕСНЫХ СИТУАЦИЙ С ВОЗМОЖНЫМИ УСТУПКАМИ Модели рационального распределения ограниченных ресурсов в форме бескоалиционных игр Рациональность является движущей силой любой задачи принятия решений. Она достижима тогда, когда учитывается реальное влияние каждой из заинтере- сованных сторон. И именно при распределении ограниченных ресурсов сделать это невероятно сложно в силу различных подходов к интерпретации рационально- сти и способов их реализации. Бескоалиционные игры представляют собой некую нейтральную модель взаимодействия субъектов с определенными сферами инте- ресов и рычагами их управления (предъявления), именуемые стратегиями [1, 2], где рациональность вырабатывается поэтапно. Модели рационального распределения ограниченных ресурсов в форме бескоалиционных игр применимы как в социаль- но-экономических и экологических системах и процессах [1, 3, 4], так и в техни- ческих, инженерных и технологических [2, 5, 6]. Взаимодействие субъектов по правилам бескоалиционной игры предполагает отсутствие каких-либо конвенций, что наиболее характерно для распределения ресурсов в условиях доминирующих запросов [1, 2, 4, 7, 8]. В результате можно найти и оперировать равновесными стратегиями по Нэшу (NE-стратегиями), оптимальными стратегиями по Парето, сильно равновесными стратегиями по Нэшу (SNE-стратегиями), а также чистыми или смешанными стратегиями других типов равновесия, выгодности, симметрич- ности [1, 5, 9, 10]. Однако в случаях, когда равновесия в чистых стратегиях не существует, процесс нахождения смешанных NE-стратегий или SNE-стратегий часто вызывает затруднения, поскольку общий алгоритм точного определения смешанных NE-стратегий в играх с тремя и более игроками неизвестен. Проблемы дискретизации игр и решения конечных бескоалиционных игр В большинстве случаев бесконечные игры сводят к конечным, где решение найти гораздо проще. При переводе бесконечной игры в конечную, т.е. в процессе дискретизации игры посредством разбиения и выборки конечных множеств из множеств чистых стратегий всех игроков, важно не потерять своеобразие функ- ции выигрыша каждого из игроков. Иначе такой перевод окажется неадекватным. Условия корректной дискретизации функций выигрыша на компактах [11, 12] не позволяют уменьшаться ни спектральным мощностям, ни плотностям точек с не- нулевыми вероятностями их выбора при минимальном уменьшении шага дискре- тизации. Кроме этого, корректность дискретизации бесконечной игры подразуме- вает, что с уменьшением шага дискретизации разброс выигрышей игрока может разве что уменьшиться, а аппроксимирующая спектральное наполнение ломаная гиперповерхность изменяется не больше, чем если бы шаг дискретизации увели- чивался. Основная трудность здесь состоит в сбалансированным выборе шага 94 ISSN 0572-2691 дискретизации, позволяющем найти адекватное приближенное решение как мож- но быстрее [12, 13]. Таким образом, при дискретизации игр хорошему приближе- нию противопоставляется скорость получения решения. Еще одним важным аргументом за переход к конечным бескоалиционным играм является то, что только стратегии с конечным спектром могут быть реали- зованы практически [14, 15]. Обычная лебегова мера точек бесконечного спектра, выбираемых в процессе практической реализации, равна нулю. Так что опериро- вать стратегиями с бесконечным спектром в практическом смысле невозможно и все равно приходится довольствоваться конечными спектрами. Элементарными конечными бескоалиционными играми являются диадиче- ские [1, 3], когда игрок имеет две чистые стратегии. Решение диадической игры можно найти аналитически [1]. Если же хотя бы один игрок имеет больше двух чистых стратегий, и игра не является биматричной, то аналитический путь реше- ния оказывается громоздким [1, 16]. Кроме того, существуют классы конечных бескоалиционных игр, в которых элементами смешанных NE-стратегий являются иррациональные числа [1, 16]. Практическая ценность таких стратегий незначи- тельна, поскольку так или иначе их приходится аппроксимировать стратегиями с вероятностями, имеющими конечное число знаков после десятичной запятой (как правило, не больше двух). Но общей теории аналитического решения даже конечных бескоалици- онных игр (с тремя и более игроками, по крайней мере один из которых имеет не меньше трех недоминируемых чистых стратегий) пока не существует. По- этому проблема решения конечных бескоалиционных игр открыта. Решение отдельно взятой бескоалиционной игры представляется самостоятельной за- дачей, требующей, как правило, рассуждений [1], обобщение которых за- труднительно. Общеизвестно лишь то, что всякая конечная бескоалиционная игра, не имеющая NE-ситуаций в чистых стратегиях, имеет хотя бы одну NE- ситуацию в смешанных стратегиях [1, 16]. В дальнейшем нас будут интересо- вать только такие игры. Если конечная бескоалиционная игра имеет NE-ситуации в чистых стра- тегиях, то их можно найти прямым перебором, ведь множество всех ситуаций в чистых стратегиях конечно. Перебор распараллеливается, когда находятся множества приемлемых ситуаций для каждого игрока. И если бы множество всех ситуаций в смешанных стратегиях было также конечным, то можно было бы попытаться найти NE-ситуации в смешанных стратегиях (в бескоалицион- ной игре, не имеющей NE-ситуаций в чистых стратегиях), на что потребова- лось бы конечное число итераций. Возможно, в дискретизированном множе- стве ситуаций в смешанных стратегиях и не будет NE-ситуаций (когда, на- пример, в исходной игре элементы смешанных NE-стратегий — иррациональные числа), но в любом случае нам нужны стратегии с конечным спектром и вероятностями, имеющими один-два знака после десятичной за- пятой. Поэтому необходимо обосновать метод дискретизации множеств сме- шанных стратегий игроков, используя постоянный шаг дискретизации. При этом укажем условия приемлемости выполняемой дискретизации, обеспечи- вающие контролируемое изменение выигрышей игроков при минимальном изменении ситуации по узлам решетки множества ситуаций в смешанных стратегиях. Также покажем, как использовать дискретизированное множество ситуаций в смешанных стратегиях для поиска NE-решений и ситуаций, яв- ляющихся равновесными с некоторыми уступками [17, 18]. Впоследствии бу- дут обсуждены варианты ускорения вычислений. Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 5 95 Условия дискретизации фундаментальных симплексов как множеств смешанных стратегий игроков Пусть дана бескоалиционная игра N n n Jn N n M mnmn kxX n 111 }][{,}}{{     FK (1) с }1{\N игроками, где nX — множество чистых стратегий n -го игрока, а nK — матрица его выигрышей, формат которой r N r M   1 F при }1{\rM и индексации ,}{ 1 N iijJ  },1{ ii Mj  .,1 Ni  (2) Множество всех смешанных стратегий n -го игрока суть )1( nM -мерный фундаментальный симплекс .1],1;0[:][ 1 1             n n n M m nmnm M Mnmnn ppp PP (3) Ожидаемый выигрыш n -го игрока в ситуации r N r N ii P    1 1}{P равен .)}({ ,1,,1 1 1                NqMj N r rj n J N iin qq r pkv P (4) Если шаг дискретизации в каждом измерении симплекса (3) положить рав- ным 1s для },1{\s то симплекс (3) превращается в решетку .,11,1, 1 :][ 1 nnnmnMnmnn Mmsh s h pp n PPP           P (5) Будем считать, что именно такое конечное разбиение множества (3) корректно, поскольку концы единичных отрезков в каждом из его измерений должны войти в решетку. Согласно этой концепции все чистые стратегии входят в симплексную решетку (5). Потребуем, чтобы для некоторого 0n было nqq N iin N iin vv    }){}}{\}({{)}({ 0 11 PPPP  (6) при qq 0 P и * ,, 0 ** min qqqq qqqqqq PPPP PPPP     (7) для Nn ,1 и Nq ,1 с обычной евклидовой метрикой в .qM Требование (6) с расстоянием (7) означает, что при минимальном изменении ситуации по узлам решетки r N r P 1 выигрыш n -го игрока изменяется не больше, чем на величину .n Иными словами, дискретизация фундаментальных симплексов как множеств смешанных стратегий игроков должна отвечать принципу «дискретной n -непрерывности» ожидаемых выигрышей игроков. Согласно этому принципу один игрок, действуя в одиночку с минимальным шагом, отвечающим расстоянию (7), 96 ISSN 0572-2691 не может изменить выигрыш любого игрока более, чем на некоторую положи- тельную величину, — на величину n для n -го игрока. Описание этого мини- мального шага приводится в следующем разделе. Построение симплексной решетки (5) Во избежание неоднозначностей можно рассматривать нумерацию nZ элементов каждой симплексной решетки (5). Если ,}][{ 11 n n Z zM z nm z nn p    PP (8) то nMnmn p    1 11 ][P при 11 1  np и 01  nmp .,2 nMm  (9) Элемент 1np изменяется от 1 до 0 с шагом .1s Элементы 1 2}{   nM mnmp также из- меняются от 1 до 0 с шагом ,1s но перед вхождением в цикл для их вычисления перед t -м элементом при 1,2  nMt производится обнуление типа 0nmp 1,  nMtm (10) и проверка условия .1 1 1    nM m nmp (11) В цикле для )1( nM -го элемента вычисляется ,1 1 1     n n M m nmnM pp (12) если только неравенство (11) верно. Очевидно, что последним элементом во множестве (8) будет n nn M Z nm Z n p    1][P при 0  nZ nmp 1,1  nMm и .1  n n Z nM p (13) Не ограничивает общности и тот факт, что, согласно описанному алгоритму построения симплексной решетки (5), nMnmn p    1 22 ][P при 12 1 1   spn и 12 2   spn для 02  nmp ,,3 nMm  (14) n nn M Z nm Z n p    1 11 ][P при 0 1   nZ nmp 2,1  nMm и 11 )1(    sp n n Z Mn для .1 11   sp n n Z nM (15) Тогда легко видеть, что минимальное расстояние между элементами (узлами) симплексной решетки (5) равно    u n l n ZluZl nn nnnnnnnn PPPP PPPP ,1,1,1 * ,, minmin ******  .212221   sssnn PP (16) Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 5 97 Итак, игрок может изменить свою стратегию не менее, чем на величину (16). И если один из игроков изменяет свою стратегию на величину (16), то выигрыш n -го игрока изменится не больше, чем на величину .n Поиск NE-ситуаций и ситуаций, являющихся равновесными с уступкой Напомним, что в игре (1) с обозначениями (2)–(4) ситуация N ii 1 }{ P называ- ется NE-ситуацией, если )}({)}{}}{\}{{( 1 * 1 * N iinnn N iin vv   PPPP  nn P P и .,1 Nn  (17) В пределах узлов симплексной решетки r N r P 1 множество NE-ситуаций может оказаться пустым, поэтому можно рассматривать ситуацию r N r N ii P    1 1 }{P равновесной с уступкой 0n для n -го игрока, если n N iinnn N iin vv   )}({)}{}}{\}{{( 1 * 1 * PPPP  nn PP и .,1 Nn  (18) Использовав нумерацию в (8), неравенства (18) запишем в более удобном (для конечного перебора) виде: n N iin z nn N iin vv     )}({)}{}}{\}{{( 1 ** 1 * PPPP  nZz ,1 и .,1 Nn  (19) При 0n Nn ,1 получаем обычную NE-ситуацию. Если же 0n хо- тя бы для одного n -го игрока, то ситуацию, удовлетворяющую неравенствам (19), назовем Bnn  }{ -NE-ситуацией, где }.0:},1{{  qNqB (20) Также можно оперировать и },1{ }{ NCC   -SNE-ситуациями, т.е. ситуациями r N r N ii     1 1 }{P такими, что C N iin Cn Cq z qCqq N ii Cn n vv         )}({)}{}}{\}{{( 1 * 1 * PPPP  qZz ,1 и },1{ NC  (21) с уступками C -коалиции .0C Поиск, вообще говоря, Bnn  }{ -NE-ситуаций при (20) ничем не отличается от поиска NE-ситуаций. При некотором наборе N iii Zz 1}},1{{  фиксируется ситуация ,}{}{ 11 * N i z i N ii i     PP для которой вычисляются N правых частей в (19). Сначала для фиксированной ситуации N i z i N ii i 11 * }{}{     PP при },1{ ii Zz  про- веряется неравенство (19) для 1n . Если неравенство (19) последовательно вы- полняется для ,,1 rn  то далее оно проверяется для ,1 rn где }.1,1{  Nr 98 ISSN 0572-2691 Иначе цикл разрывается, производится инкремент одного из номеров в наборе N iiz 1}{  и для новой фиксированной ситуации N i z i N ii i 11 * }{}{     PP неравенство (19) снова проверяется для .1n Эти действия выполняются до тех пор, пока не будет проверено неравенство (19) для ситуации .}{ 1 N i Z i i   P Обсуждение возможности ускорения поиска Bnn  }{ -NE- ситуаций Кроме описанной выше процедуры поиска Bnn  }{ -NE- решений, существует вариант поиска, где сначала находятся множества приемлемых ситуаций для каж- дого из игроков, а потом выполняется пересечение этих множеств. Однако этот вариант гораздо медленнее. В предлагаемой процедуре поиска { }n n B -NE- решений приемлемые ситуации ищутся последовательно, начиная с первого игрока. Если некоторая ситуация оказывается неприемлемой для )1( r -го игрока, будучи приемлемой для первых r игроков при },1,1{  Nr то она отбрасывается и фиксируется следующая. Так отбрасываются те ситуации, которые заведомо не будут удовлетворять неравенству (19). Ясно, что чем больше количество элементов во множестве (20) и чем больше зна- чения ,}{ Bnn  тем больше будет приемлемых ситуаций. Это замедлит процесс поис- ка Bnn  }{ -NE- решений. Ускорить его можно за счет распараллеливания перемно- жения матриц (массивов) при вычислении ожидаемых выигрышей по формуле (4). Значения N nn 1}{  и Bnn  }{ подбираются с учетом разбросов )(min)(max ,1,,1,}{,1,,1,}{ 11       n J NiMjjJ n J NiMjjJ kk ii N iiii N ii при .,1 Nn  (22) В процентном эквиваленте эти значения, исходя из практических сооб- ражений, могут составлять до 10 % от соответствующих разбросов (22), хотя здесь удобнее оперировать нормированными выигрышами. Для матриц выиг- рышей N n n Jn g 1}][{   FG формата r N r M   1 F при индексации (2) необхо- димо осуществлять аффинно-эквивалентный [1, 16] переход ,1)(min ,1,,1,}{ 1      n I NiMttI n J n J ggg ii N ii )(max ,1,,1,}{ 1       n I NiMttI n Jn J g g k ii N ii для Nn ,1 (23) к игре (1). Если же требуется однородная аффинная эквивалентность [1, 16], вместо (23) нормирование следует производить так: ,1)(minmin ,1,,1,}{,1 1               r I NiMttINr n J n J ggg ii N ii               )(maxmax ,1,,1,}{,1 1 r I NiMttINr n Jn J g g k ii N ii для .,1 Nn  (24) В результате будет ]1;0(n Jk .,1 Nn  Это позволит там, где требуется, брать 01,0n или ,02,0n поскольку, как показали примеры, значение Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 5 99 1,0n или даже 05,0n уже слишком велико. В частности, в одной 333  - игре без NE-ситуаций в чистых стратегиях после нормирования (24) при 5s получилась одна }3,1{ }01,0{ n -NE-ситуация. При этом длительность процесса поиска этой ситуации оказалась лишь на 17 % больше длительности процесса для 0n ,3,1n в этой же игре при 5s существует девять }3,1{ }02,0{ n -NE- ситуаций, которые были найдены за время, превышающее на 39 % период поиска обычных NE-ситуаций. Следовательно, рациональный выбор небольших значений Bnn  }{ ускоряет поиск Bnn  }{ -NE-ситуаций. С подбором значений N nn 1}{  дело обстоит несколько сложнее. Если тре- бование (6) с расстоянием (7) невыполнимо, понадобится либо повышение значений ,}{ 1 N nn  либо уменьшение шага дискретизации .1s Последнее неизбежно приведет к замедлению процесса поиска Bnn  }{ -NE-ситуаций. Как следствие, значения N nn 1}{  рекомендуется выбирать достаточно большими в зависимости не только от разбросов (22), но и от количества разбросов выигрышей игроков по ситуациям в чистых стратегиях. Заключение Естественно, не существует гарантии, что после дискретизации фундамен- тальных симплексов с очень малым шагом множество NE-ситуаций, удовлетво- ряющих (17) по определению, окажется непустым. Это оправдывает введение Bnn  }{ -NE-ситуаций, а также и },1{ }{ NCC   -SNE-ситуаций. Здесь можно гово- рить о переходе к NE-ситуациям с уступками, вызванном не столько незнанием аналитического способа решения игры, сколько ограничением количества возмож- ных повторов игры, что вынуждает работать со спектральными вероятностями, имеющими один-два знака после десятичной запятой. Вариант построения самой решетки (8) для n -го игрока, где предусматривается выполнение соотношений (9)–(15), не является единственным. Впрочем, особого внимания он не заслуживает ввиду того, что его осуществление происходит на несколько порядков быстрее поиска Bnn  }{ -NE-ситуаций. Практически все время уходит на вычисление ожидаемых выигрышей по формуле (4), фигурирующих в обеих частях неравенств (19) и (21). Все остальные операции требуют ничтожно малой доли времени (ориентировочно — менее 1 %). Программная реализация предлагаемой дискретизации множеств смешанных стратегий выполнима в любой среде, допускающей операции с многомерными массивами. Приоритетными выступают среды, поддерживающие многопоточные вычисления и использование многоядерных процессоров, включая видеопро- цессоры с поддержкой CUDA для эффективного распараллеливания процедур вычисления ожидаемых выигрышей согласно (4). Подбирая значения ,}{ 1 N nn  следует помнить о том, что чрезмерно большие правые части в (6) могут стать причиной грубой конечной аппроксимации фундамен- тальных симплексов. Но подбор рациональных значений Bnn  }{ намного важнее. Величины Bnn  }{ желательно понижать до тех пор, пока не получится единствен- ная Bnn  }{ -NE-ситуация. В результате имеем еще одно ощутимое преимущество решения игры (1) на решетке , 1 r N r P  ведь количество Bnn  }{ -NE-ситуаций регули- 100 ISSN 0572-2691 руемо благодаря изменяемым значениям .}{ Bnn  Отсюда следует, что известная проблема единственности решения игры [19, 20] устраняема с помощью предла- гаемой дискретизации и концепции уступок. В перспективе результат представленной работы можно дополнить. Во- первых, игроки, обладая разными значениями N nn 1}{  и уступая в равновесии по-разному, могут иметь свои собственные шаги дискретизации. Во-вторых, шаг дискретизации можно подстроить индивидуально вдоль каждого из измерений смешанной стратегии. Это вызвано тем, что иногда чистые стратегии бывают раз- личной важности (рангов), поэтому после их ранжирования вероятность выбора чистой стратегии с высшим рангом должна меняться с меньшим шагом. В- третьих, предлагаемая равномерная дискретизация легко распространяема на лю- бые другие игровые модели распределения ограниченных ресурсов и взаимодей- ствия в условиях конфликта, разрешаемого лишь с помощью смешанных (вероят- ностных) расширений. Заметим, что для динамических игровых моделей потребу- ется согласование с шагом кусочно-программного управления [2, 21]. В.В. Романюк РІВНОМІРНА ДИСКРЕТИЗАЦІЯ ФУНДАМЕНТАЛЬНИХ СИМПЛЕКСІВ ЯК МНОЖИН ЗМІШАНИХ СТРАТЕГІЙ ГРАВЦІВ У СКІНЧЕННІЙ БЕЗКОАЛІЦІЙНІЙ ГРІ ДЛЯ ЗНАХОДЖЕННЯ РІВНОВАЖНИХ СИТУАЦІЙ З МОЖЛИВИМИ ПОСТУПКАМИ Запропоновано метод рівномірної дискретизації фундаментальних симплексів як множин змішаних стратегій гравців у скінченній безкоаліційній грі для її набли- женого розв’язку. Цей розв’язок сприймається як рівноважні ситуації з можливими поступками, оскільки на скінченній симплексній решітці не обов’язково знаходять- ся рівноважні ситуації за Нешем. Умови дискретизації передбачають, що при міні- мальній зміні ситуації за вузлами цієї решітки виграш гравця змінюється не більше, ніж на деяку постійну для нього величину. Побудова симплексної решітки множини змішаних стратегій гравця виконується циклічним спуском від першої чистої стратегії до останньої. Пошук ситуацій, котрі є рівноважними з поступкою, можна прискорити за рахунок розпаралелювання перемноження масивів при обчисленні очікуваних виграшів. V.V. Romanuke UNIFORM SAMPLING OF FUNDAMENTAL SIMPLEXES AS SETS OF PLAYERS’ MIXED STRATEGIES IN THE FINITE NONCOOPERATIVE GAME FOR FINDING EQUILIBRIUM SITUATIONS WITH POSSIBLE CONCESSIONS A method is suggested for sampling uniformly fundamental simplexes as sets of players’ mixed strategies in the finite noncooperative game for its approximate solution. This solu- tion is treated in the sense of equilibrium situations with possible concessions, as Nash equilibrium situations are not necessarily to be on a finite simplex lattice. The sampling conditions presume that, by changing minimally a situation over nodes of the lattice, the player’s payoff varies no greater than within its constant value. Building a simplex lattice of the player’s mixed strategies set is fulfilled by cyclic descent from the first pure strategy down to the last one. Retrieval of concession-equilibrium situations can be sped up by par- allelizing arrays’ multiplication when expected payoffs are calculated. Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 5 101 1. Воробьев Н.Н. Основы теории игр. Бескоалиционные игры. — М. : Наука, 1984. — 496 с. 2. Чикрий А.А. Конфликтно-управляемые процессы. — Киев : Наук. думка, 1992. — 383 с. 3. Romanuke V.V. Environment guard model as dyadic three-person game with the generalized fine for the reservoir pollution // Екологічна безпека та природокористування. — 2010. — Вип. 6. — С. 77–94. 4. Scheffran J. The dynamic interaction between economy and ecology: cooperation, stability and sustainability for a dynamic-game model of resource conflicts // Mathematics and Computers in Simulation. — 2000. — 53, N 4–6. — P. 371–380. 5. Gąsior D., Drwal M. Pareto-optimal Nash equilibrium in capacity allocation game for self- managed networks // Computer Networks. — 2013. — 57, N 14. — P. 2817–2832. 6. Ye D., Chen J. Non-cooperative games on multidimensional resource allocation // Future Genera- tion Computer Systems. — 2013. — 29, N 6. — P. 1345–1352. 7. Власенко Л.А., Чикрий А.А. Об одной дифференциальной игре в системе с распределенны- ми параметрами // Тр. Института математики и механики УрО РАН. — 2014. — 20, № 4. — С. 71–80. 8. Чикрий А. А., Белоусов А. А. О линейных дифференциальных играх с выпуклыми инте- гральными ограничениями // Там же. — 2013. — 19, № 4. — С. 308 — 319. 9. Fudenberg D., Tirole J. Perfect Bayesian equilibrium and sequential equilibrium // Journal of Economic Theory. — 1991. — 53, N 2. — P. 236–260. 10. Scalzo V. Pareto efficient Nash equilibria in discontinuous games // Economics Letters. — 2010. — 107, N 3. — P. 364 — 365. 11. Романюк В.В. Дискретизация континуальной антагонистической игры на единичном ги- перкубе и преобразование многомерной матрицы для решения соответствующей матрич- ной игры // Международный научно-технический журнал «Проблемы управления и ин- форматики». — 2015. — № 1. — С. 118–126. 12. Romanuke V.V. Approximation of unit-hypercubic infinite antagonistic game via dimension- dependent irregular samplings and reshaping the payoffs into flat matrix wherewith to solve the matrix game // Journal of Information and Organizational Sciences. — 2014. — 38, N 2. — P. 125 — 143. 13. Kontogiannis S.C., Panagopoulou P.N., Spirakis P.G. Polynomial algorithms for approximating Nash equilibria of bimatrix games // Theoretical Computer Science. — 2009. — 410, N 17. — P. 1599–1606. 14. Bernhard P., Shinar J. On finite approximation of a game solution with mixed strategies // Ap- plied Mathematics Letters. — 1990. — 3, N 1. — P. 1–4. 15. Романюк В.В. Сходимость и оценка процесса компьютерной реализации принципа опти- мальности в матричных играх с видимым горизонтом разыгрываний // Международный научно-технический журнал «Проблемы управления и информатики». — 2013. — № 5. — С. 96–102. 16. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. — М. : Наука, 1985. — 272 с. 17. Tanaka K., Yokoyama K. On -equilibrium point in a noncooperative n -person game // Journal of Mathematical Analysis and Applications. — 1991. — 160, N 2. — P. 413–423. 18. Gerardi D., Myerson R.B. Sequential equilibria in Bayesian games with communication // Games and economic behavior. — 2007. — 60, N 1. — P. 104–134. 19. Harsanyi J. C., Selten R. A general theory of equilibrium selection in games. — Cambridge Mass. : The MIT Press, 1988. — 396 p. 20. Romanuke V.V. Superoptimal mixed strategies in antagonistic games as the advantaged subsets of the optimal mixed strategies set // Bulletin of Donetsk National University. Ser. А. Natural sci- ences. — 2010. — N 2. — P. 289–298. 21. Чикрий А.А., Матичин И.И. Линейные дифференциальные игры с импульсным управлени- ем игроков // Тр. Института математики и механики УрО РАН. — 2005. — 11, № 1. — С. 212–224. Получено 30.04.2015

Institution

Ähnliche Einträge