Методы поиска точки равновесия в седловых играх двух лиц

• Автор: Артемьева, Людмила Анатольевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 207 с. : ил.

Содержание
Введение

Глава 1. Седловые игры двух лиц

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

1.2. Содержательный смысл ссдлоной игры двух лиц

Глава 2. Методы поиска точки равновесия в седловых играх двух лиц

2.1. Итерационный экстраградиентный метод

2.2. Дифференциальный экстраградиентный метод

2.3. Итерационный экстрапроксимальный метод

2.4. Дифсрснциальный экстрапроксимальный метод

Глава 3. Методы поиска точки равновесия в седловых играх двух лиц в случае неточно заданных входных данных
3.1. Регуляризованный экстраградиентный метод
3.2. Регуляризованный дифференциальный экстраградиентный метод
3.3. Регуляризованный экстрапроксимальный метод
3.4. Регуляризованный дифференциальный экстрапроксимальный метод
Приложение
Тестовые примеры
Литература

Введение.
Теория игр, говоря кратко, это математическая теория принятия решений в конфликтных ситуациях. Усилиями многих ученых к настоящему времени исследованы широкие классы математических моделей конфликтных ситуаций различного характера (антагонистические, кооперативные, иерархические, динамические и.т.д.), имеется огромное количество монографий, учебных пособий, журнальных публикаций, посвященных теории игр [18, 27-36, 38-40, 47-52, 54, 57-59, 61-80, 83-86].
В настоящей работе рассматривается относительно новый класс задач теории игр, которые можно назвать седловыми играми двух лиц, предлагаются и исследуются методы поиска точки равновесия таких игр [11-13]. В таких играх каждый игрок распоряжается функцией двух векторных переменных, выбирает седловую точку своей функции и свой выбор (свою стратегию) сообщает другому игроку. Предполагается, что функция каждого игрока зависит от седловой точки другого игрока как от параметра, поэтому ссдловая точка, выбираемая каждым игроком, влияет на выбор седловой точки другого игрока. Такой взаимозависимый выбор ссдловых точек каждым игроком в совокупности порождает седловое отображение. Неподвижная точка этого отображения называется точкой равновесия рассматриваемой седловой игры. Игроки, последовательно обмениваясь седловыми точками, согласуя своп действия, ищут эту неподвижную точку. Такая точка выгодна каждому игроку и определить ее - это цель седловой игры. Точное описание математической модели этой игры дается ниже. Пока мы лишь скажем, что седловые игры возникают при моделировании различных экономических ситуаций, таких как, например, равновесная модель кредитного рынка, равновесная модель взаимодействия двух предприятий, использующих продукцию друг друга как сырье, модель равновесной поставки ресурсов, равновесная модель фирмы, равновесный выбор весовых коэффициентов в задачах многокритериальной оптимизации и другие [4, 11-13].
Каждой седловой игре можно сопоставить некоторую функцию, такую, что всякая точка равновесия седловой игры является седловой точкой этой

функции. Можно сказать, что такая функция в ссдловой игре выполняет такую же роль, как и функция Лагранжа в обычной задаче математического программирования. Это значит, что задача поиска точки равновесия ссдловой игры может быть сведена к ссдловой задаче, и здесь, казалось бы, можно использовать известные методы поиска ссдловой точки [37, 41]. Однако, сходимость таких методов доказывается при весьма жестких требованиях на входные данные (условия типа сильной выпуклости целевой функции, компактности допустимого множества ссдловых параметров). Развитые позднее экстраполяционные методы поиска ссдловых точек (экстраградиентныс, экстрапроксимальныс методы [1, 55, 56]) сходятся при традиционных требованиях (например, условия Липшица для градиентов функции Лагранжа). Однако, как выяснилось, в ссдловых играх эти традиционные условия не всегда выполняются. Поэтому разработка новых вариантов экстраполяционных методов поиска ссдловой точки, развитие техники доказательства сходимости этих методов при умеренных требованиях на входные данные задачи, является актуальной проблемой. Кроме того, важно заметить, что седловые задачи, вообще говоря, неустойчивы к погрешностям задания входных данных и для поиска ссдловых точек нужно использовать специальным образом регуляризованные экстраполяционные методы. Таким образом, разработка устойчивых методов поиска точек равновесия в ссдловых играх является актуальной задачей теории игр.
В работе разрабатываются методы поиска точек равновесия ссдловых игр двух лиц, обладающие монотонной сходимостью к одной из точек равновесия при традиционных ограничениях на входные данные. Создаются ре-гулярпзованные варианты этих методов, способные работать при неточно заданных входных данных.
Для поиска точки равновесия в случае точно заданных входных данных предложены и исследованы новые экстраградиснтные и экстрапроксималь-ные методы, доказана их монотонная сходимость при традиционных ограничениях на входные данные. Для поиска токи равновесия при неточно заданных входных данных предложены и исследованы регуляризованные экс-трагра.диентные и экстрапроксимальныс методы, построен регуляризующий
у* € Атах{(р*, у) у € У0} (1-21)
где А(?/;), Д(гп) = (СДгн)
Игра заключается в том, что участник, владеющий ресурсами у 6 Уо, готов продать их другому участнику, владеющему производством, в объеме у* по цене р*, стремясь получить максимальную прибыль (1.21). Другой участник, владелец производства (1.19), (1-20), покупает этот ресурс у* и желает получить максимальную прибыль или, иначе говоря, минимизировать издержки А(гщ). Каждый из участников игры преследует свои интересы, носящие противоречивый характер, но в тоже время, они не могут существовать друг без друга и вынуждены договариваться и совместно искать точку равновесия (гщ,р*, у*) устраивающую их обоих в смысле выполнения условий (1.19)-(1.21).
Заметим, что пара (го*,р*) 6 Иф х Е™, как следует из (1.19), (1-20) является седловой точкой следующей функции Лагранжа:
£1 (ги,р,у.) = Е(1и) + (р,С(ш) - у*}, го <5 Иф, р € Д" (1.22)
в смысле выполнения неравенств:
£1 (гщ,р,у*) СДгщру*) < £,(?/;, р*, у») Угн € Иф, Ур € Д"1 (1.23)
Включение (1.21) можно записать в следующем виде:
(р*,у) (р*,г/*) Уу € Уо (1.24)
Система (1.23), (1.24) относительно переменных (га,р, у) равносильна исходной системе (1.19)-(1.21).
Покажем, что точка равновесия ('ш*.р„, у*) задачи (1.19)-(1.21) является седловой точкой следующей функции:
£(гщр,у) = Д(ги) + (р, С(гн) - у), ы <Е Иф, Р € Д+, у € Уо (1.25)