ОБЗОР МЕТОДА РЕЛАКСАЦИИ ДЛЯ ПОИСКА ТОЧЕК РАВНОВЕСИЯ ПО НЭШУ В НЕПРЕРЫВНЫХ НЕКООПЕРАТИВНЫХ ИГРАХ МНОГИХ ЛИЦ Студент: Чиркина Д.Н., 5 курс Научный руководитель: д.т.н., профессор, Карпенко А.П.

План презентации Введение Общие сведение. История задачи. Применение. Постановка задачи Основные понятия и определения. Метод релаксации Нэша Основы метода, его алгоритм и классификация. Результат работы алгоритма на типовом примере Программная реализация. Исследование работы. Заключение Оценка эффективности. Выводы. 2/10

Введение Дж. Ф. Нэш, «Точки равновесия в играх n лиц» (1950 г.) Разнообразие методов поиска равновесия по Нэшу: Метод Никайдо и Изода, Метод Розена, Метод Смейла, методы частично-целочисленного программирования и другие. Джасек Б. Краусцек, Университет Виктории (г.Веллингтон, Новая Зеландия), Станислав Ярясев, Университет Флориды (США), 1999 г. Алгоритм релаксации для поиска точек равновесия по Нэшу и его экономическое приложение. (2000 г.) Области применения: Механизмы поиска оптимальных решений в системах поддержки принятия управленческих решений (СППР) Оптимизация для повышения быстродействия задачи конфликтно- оптимального целераспределения малых групп летательных аппаратов. 3/10

Постановка задачи n игроков взаимодействуют друг с другом X i – набор возможных альтернативных стратегий – действие игрока i Совокупность действий всех игроков Множество (возможных) коллективных действий или множество ситуаций Функция платы (цены): 4/10

Постановка задачи Задана игра Решение – точка равновесия по Нэшу, если справедливо неравенство Сокращенная форма записи Пусть Решение – точка равновесия по Нэшу, если справедливо неравенство 5/10

Метод релаксации Нэша, Вектор коллективных действий. Оптимальная функция отклика (ответа): Функция Никайдо и Изода Вектор точек равновесия по Нэшу Условие: 6/10

Метод релаксации Нэша Алгоритм релаксации: 1) Инициализация:, 2) Вычисление вектора : 3) Cтандартные условия окончания поиска 7/10

Результат работы алгоритма на типовом примере Типовой пример. 8/10

9 Результат работы алгоритма на типовом примере Аналитические выражения Ценовая функция: Функция оптимального отклика Ценовая функция Критерий окончания итераций. 9/10

Результат работы алгоритма на типовом примере 10/10 Начальные приближения, (x 1 0,x 2 0 ) Решение, (x 1 *,x 2 * ) Количество вычислений ценовой функции, N (0,4;0,4) (0, ; 0, ) 108 (2;1) (0, ; 0, ) 122 (4;2) (0, ; 0, ) 127 (6;3) (0, ; 0, ) 130 (8;4) (0, ; 0, ) 132 (10;5) (0, ; 0, ) 134 (400;140) (0, ; 0, ) 157 2) Постоянный шаг:, N = ) Оптимальный шаг

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

БЛАГОДАРЮ ЗА ВНИМАНИЕ