О субоптимальных решениях антагонистических игр разбиений

Автор(ы): Бочаров П.С., Горяшко А.П.

Выпуск: 70

Рубрика: Системный анализ

Год: 2017

Библиография: Бочаров П.С., Горяшко А.П. О субоптимальных решениях антагонистических игр разбиений // Управление большими системами. Выпуск 70. М.: ИПУ РАН, 2017. С.6-24. URL: https://doi.org/10.25728/ubs.2017.70.1

Дата опубликования: 30.11.2017

Ключевые слова: разбиение целого числа, композиция целого числа, теория игр, игры Блотто, игры Лотто, epsilon-оптимальное решение игры, цена игры, собственный ресурс разбиения, уравновешенность разбиения

Аннотация: Представлены экспериментальные результаты изучения субоптимальных решений в смешанных стратегиях антагонистических игр разбиений. Показано, что множество чистых стратегий epsilon-оптимального алгоритма обладает специальной структурой распределения ресурсов и эта структура может быть легко воспроизведена на базе ранее изученных свойств разбиений. Результаты подтверждены численным сравнением с поведением epsilon-оптимального алгоритма.

Author(s): Bocharov P., Goryashko A.

Article title: Suboptimal solutions of antagonistic partition games

Issue: 70

Year: 2017

Keywords: integer partition, composition on integer, game theory, Blotto games, Lotto games, epsilon-optimal solution, value of game, peculiar resource, partition balance

Abstract: The paper examines (n, m)-partition games in order to develop tractable method of suboptimal decision of the resource allocation games such as colonel Blotto game or colonel Lotto game. The main goal is to develop tractable method for building suboptimal solution in mixed strategies for these games without solving the relevant optimization problem. The foundation of proposed method lies in the specific combinatorial properties of the (n, m)-partition games. It turned out that if for all game strategies the values of the balance and peculiar resource have the values from specific range it could be sufficient to get of suboptimal decisions of the games mentioned above. The proposed methods are based on both the analytical and numerical results, analytical partitions properties and numerical simulation results. The numerical simulation for the partition games (120, 6) and (100, 10) demonstrated that one could design of the epsilon-optimal decision where epsilon <= 0.02. The support set of these decisions contain no more two hundred pure strategies and decisions complexity equals const x m^2 for considered games. Results of the numerical simulation provide reasons to suppose that our approach is quite competitive with epsilon-optimal solution. The simplicity of our suboptimal solution method could be advantage in the behavioral game theory.