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

Abstract

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

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.