Д. В. ЗАЙЦЕВ, В. Е. САЛОВ, Д. С. ПРОКУШЕВ
Центральный физико-технический институт
ФОРМАЛИЗАЦИЯ КОНФЛИКТНОЙ ИГРЫ В ВИДЕ СЕТи МАССОВОГО ОБСЛУЖИВАНИЯ ДЖЕКСОНА
Показано, что конфликтная игра между двумя командами игроков может быть корректно рассмотрена в рамках теории сетей массового обслуживания Джексона с ненадежными каналами обслуживания. Получены конечные распределения плотности вероятности возможных исходов в случае разнотипных игроков.
Рассматривается конфликтная игра между двумя множествами (командами) разнотипных игроков A={1, …, NA} и B={1, …, NB}. Суть игры заключается в том, что каждый из игроков вступает в конфликт с каким-либо игроком противоположной команды. Конфликт между игроками может закончиться либо выигрышем i-го игрока команды А с вероятностью рАi (соответственно проигрышем j-го игрока команды В с вероятностью 1– рАi), либо выигрышем j-го игрока команды В с вероятностью рВj (соответственно проигрышем i-го игрока команды А с вероятностью 1– рВj). Проигравший игрок выбывает из игры. Команда, потерявшая всех игроков, считается проигравшей.
Решение данной задачи в случае однотипных игроков в каждой команде получено в [1]. Суть решения заключается в том, что конфликтная игра формализуется в виде графа, каждое состояние Sij которого характеризует потери команды А – i и потери команды В – j. Переходы из одного состояния в другое характеризуются вероятностями рА или рВ. Конечные распределения исходов рассматриваемой игры – есть количество возможных переходов из состояния S00 в состояние SiNB (победа стороны А) или в состояние SNAj (победа стороны B).
Однако в случае разнотипных игроков решение, полученное в [1] применить практически невозможно. Это связано с тем, что в случае разнотипных игроков возможные переходы из состояния S00 в состояние SiNB или в состояние SNAj будут различными. Поэтому для определения вероятности возможного исхода игры необходимо просчитать вероятность каждого перехода в явном виде, что практически нереализуемо из-за их большого количества.
Для нахождения конечного распределения вероятностей возможных исходов конфликтной игры предложено воспользоваться методами сетей массового обслуживания Джексона (см., например [2]).
Сравним постановку задачи для разомкнутой марковской сети Джексона с ненадежными каналами обслуживания [2] с задачей для конфликтной игры.
сеть Джексона с ненадежными каналами обслуживания | Конфликтная игра |
Сеть состоит из m многоканальных узлов | Команда А состоит из m отделений |
В j-ом узле имеется nj каналов обслуживания | В j-ом отделении имеется nj игроков |
В интервал времени (t+dt) в сеть поступает новое требование с вероятностью ldt | В интервал времени (t+dt) команда В вводит в игру нового игрока с вероятностью ldt |
Это требование с вероятностью P0i направляется в i узел | Этот игрок с вероятностью P0i передается на обслуживание в i отделение |
В интервале времени (t+dt) j канал откажет с вероятностью ajdt | В интервале времени (t+dt) j игрок команды А может выбыть из игры с вероятностью ajdt |
В интервале времени (t+dt) j канал будет восстановлен с вероятностью bjdt | В интервале времени (t+dt) j игрок команды А может вернуться в игру с вероятностью bjdt |
В интервале времени (t+dt) одно требование закончит обслуживание с вероятностью mjdt | В интервале времени (t+dt) один игрок команды В может выбыть из игры с вероятностью mjdt |
Задачей исследования сети Джексона является нахождение стационарных распределений вероятностей состояний сети. Задача исследования конфликтной игры та же – нахождение конечного распределения вероятностей возможных исходов.
Список литературы
1. Конечное распределение плотности вероятности возможных исходов для конфликтной игры. Научная сессия МИФИ – 2004. Сборник научных трудов. Т.7. Москва, 26-30 января 2004 г. С.158-159.
2. . Теория сетей массового обслуживания. – М.: Физматлит, 2004.
