Алгоритм численного построения решений по Нэшу в позиционной дифференциальной игре двух лиц

ВЕСТНИК
УДМУРТСКОГО
УНИВЕРСИТЕТА

МАТЕМАТИКА
2009. Вып. 3

УДК 517.977.8

c
⃝ Д. Р. Кувшинов

АЛГОРИТМ ЧИСЛЕННОГО ПОСТРОЕНИЯ РЕШЕНИЙ ПО НЭШУ
В ПОЗИЦИОННОЙ ДИФФЕРЕНЦИАЛЬНОЙ ИГРЕ ДВУХ ЛИЦ1

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

Ключевые слова: позиционные дифференциальные игры, равновесное по Нэшу решение, численный
алгоритм.

Введение

Работа посвящена численному алгоритму построения равновесных по Нэшу решений в позиционной дифференциальной игре двух лиц с терминальными показателями качества игроков
и геометрическими ограничениями на управления.
Формализация рассматриваемой неантагонистической игры опирается на формализацию
и результаты теории антагонистических позиционных дифференциальных игр, построенной
Н. Н. Красовским, А. И. Субботиным и их сотрудниками [1; 2], и излагается в работе А. Ф. Клейменова [3]. В [3] задача построения равновесных по Нэшу решений сведена к решению некоторой задачи (оптимального) управления. Этот подход позволяет использовать известные процедуры численного построения стабильных мостов в антагонистических позиционных дифференциальных играх (см., например, работы В. Н. Ушакова, В. С. Пацко и их учеников [4; 5]).
Предлагаемый алгоритм был создан как обобщение алгоритма численного построения решений Штакельберга в дифференциальной позиционной игре, разработанного С. И. Осиповым
[6; 7]. Вначале ставилась задача поиска только неулучшаемых решений Нэша, в дальнейшем
полученный алгоритм был дополнен для получения всех решений Нэша.
Изложение построено следующим образом. В § 1 даны формализация рассматриваемой игры и определения решений в достаточно общей форме. Далее описан общий подход к построению решений Нэша, основанный на сведении исходной задачи к нестандартной задаче (оптимального) управления, названной здесь «вспомогательной задачей» (§ 2). Собственно алгоритм
для линейной игры, приводимой к игре на плоскости, дан в § 3. Результаты численного эксперимента для задачи движения материальной точки в плоскости представлены в § 4.
Отметим, что ограничение размерности фазового вектора связано с уровнем развития алгоритмов вычислительной геометрии и их программных реализаций. В частности, автору неизвестны алгоритмы, строящие результаты теоретико-множественных операций над многогранниками в пространствах размерности больше 3.
Материал, изложенный в статье, был доложен на Всероссийской конференции «Динамические системы, управление и наномеханика» [8].

§ 1. Постановка задачи

Пусть динамика управляемой системы описывается уравнением вида

˙x = f(t, x, u, v),
x(t0) = x0;
t ∈ [t0, ϑ],
x ∈ Rn,
u ∈ P ⊂ Rk,
v ∈ Q ⊂ Rl,
(1.1)

1Работа выполнена при финансовой поддержке РФФИ (грант 09–01–00313).