О сходимости обучающего алгоритма для эволюционной игры

• Автор: Сухотина, Мария Александровна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Санкт-Петербург
• Количество страниц: 121 с. : ил.

Оглавление.
Введение
Глава 1 Исследование сходимости ММ- и МЫ-обучающих алгоритмов для
симметричных биматричных игр размерности 2x2
§1.1 Общая постановка задачи для ММ-обучающего алгоритма
§1.2 Доказательство сходимости ММ-обучающего алгоритма для
симметричных биматричных игр размерности 2x2
§1.3 Классификация стационарных состояний для ММ-обучающего
алгоритма
§1.4 Общая постановка задачи для ММ-обучающего
алгоритма
§1.5 Сходимость ММ - обу чающего алгоритма для симметричных
биматричных игр размерности 2x2
§1.6 Классификация стационарных состояний для ММ-обучающего
алгоритма
Глава 2 Исследование сходимости Р-обучающего алгоритма для
симметричных биматричных игр размерности 2x2
§2.1 Общая постановка задачи для Р-обучающего алгоритма
§2.2 Исследование сходимости Р-обучающего алгоритма для
симметричных биматричных игр размерности 2x2
Глава 3 Сходимость ММ-обучающего алгоритма для симметричных
биматричных игр размерности 3x3
§3.1 Теорема о сходимости ММ-обучающего алгоритма для
симметричных биматричных игр размерности 3x3
§3.2 Конкретные примеры игр для ММ-обучающего алгоритма
Заключение
Приложение А
Приложение В
Приложение С

Приложение П
Приложение Е
Приложение Г
Литература

Введение.
В диссертационной работе исследуется сходимость обучающих алгоритмов для эволюционной игры. Основные положения диссертации, выносимые на защиту, состоят в следующем:
a) Построены три различных обучающих алгоритма (ММ, МЫ и Р-алгоритмы) эволюционной игры на графе, определяющем взаимоотношения игроков между собой.
b) Доказана сходимость ММ и ММ-обучающих алгоритмов для симметричных биматричных игр с матрицей выигрышей размерности 2x2. Для Р-обучающего алгоритма найдены условия, при которых данный алгоритм сходится.
c) Дается классификация получаемых в результате сходимости обучающих алгоритмов стационарных состояний.
<1) Найдены условия сходимости ММ-обучающего алгоритма для симметричных биматричных игр с матрицей выигрышей размерности 3x3.
Прежде, чем перейти к более подробному содержанию диссертационной работы коротко остановимся на истории вопроса.
Когда в 1944 году появилась работа фон Неймана и Моргенштейна «Теория игр и экономическое поведение» [9], она была встречена с большим энтузиазмом. Казалось, что это была совершенная теория стратегического поведения. Но, уже довольно скоро выяснилось, что это не совсем так. На долгий период теория некооперативных игр остановилась в развитии. Все усилия были направлены на изучение антагонистических игр 2-х лиц, а также на теорию кооперативных игр.
Появившиеся в начале 50-х годов работы Нэша [11,39,40,41], где вводилось понятие равновесия по Нэшу - которое и по сей день является основным принципом оптимальности в некооперативных неантагонистических

составлять только I стратегии. Если существует хоть одна пара игроков х, у є X, которые удовлетворяют следующим условиям:
a)хєГу, у є Г,;
b) и игрокх, и игроку» имеют II начальную стратегию;
и у каждого игрока х є X, имеющего I начальную стратегию, все его соседи у є Гг имеют II начальную стратегию, то стационарное состояние сети будут составлять только II стратегии. Если же у каждого игрока х є X, имеющего I начальную стратегию, есть хоть один сосед у є Гх, имеющий тоже I начальную стратегию и у каждого игрока х є X, имеющего II начальную стратегию, есть хоть один сосед у є , имеющий тоже II начальную стратегию, то стационарное состояние сети совпадет с начальным.
Мы перебрали все возможные виды матрицы выигрышей (3) размерности 2x2. И для всех рассмотренных случаев получили, что ММ*-обучающий алгоритм сходится. Поэтому все выше сказанное можно обобщить следующим образом:
Теорема 1.6. Для любой матрицы выигрышей (3) размерности 2x2 и для любого конечного графа ММ*-обучающий алгоритм будет сходиться к стационарному состоянию сети за конечное число шагов.
$ 1.3 Классификация стационарных состояний для ММ-обучающего алгоритма.
Понятно, что вид стационарного состояния зависит от трех факторов:
a) от самого графа.
b) от вида матрицы выигрышей (3).
c) от начального состояния сети.
Но можно выделить некоторые общие закономерности.