Эффективные алгоритмы решения конечных безкоалиционных игр Воробьев, Николай Николаевич

Короткий опис

Воробьев, Николай Николаевич.Эффективные алгоритмы решения конечных безкоалиционных игр : диссертация ... кандидата физико-математических наук : 01.01.09. - Ленинград, 1984. - 125 с. : ил.

Оглавление диссертациикандидат физико-математических наук Воробьев, Николай Николаевич
ВВЕДЕНИЕ.
ГЛАВА. I. ЭФФЕКТИВНЫЕ АЛГОРИТМЫ В БЕСКОАЛИЦИОННЫХ ИГРАХ
§ I. Ситуации равновесия в бескоалиционных играх
1.1. Основные определения
1.2. Лемма Шпернера и теорема Нэша.
1.3. Оценки числа компонент множества ситуаций равновесия
§ 2. Бескоалиционные игры и системы алгебраических уравнений и неравенств.
§ 3. Оценки вещественных корней системы алгебраических уравнений.
3.1. Предельные корни параметризованной системы уравнений
3.2. Множество точек нулевой кривизны гладкой алгебраической гиперповерхности в К,
3.3. Верхние оценки для координат вещественных корней.
3.4. Некоторые нижние оценки
§ 4. Распознавание совместности системы уравнений и нахождение корней
4.1. Сведение к случаю компактного многообразия и основная лемма
4.2. Алгоритм решения уравнения - V = о
4.3. Системы алгебраических неравенств
4.4. Нахождение ситуаций -равновесия в бескоалиционных играх.
ГЛАВА 2. ОЦЕНКИ СЛОЖНОСТИ НЕКОТОРЫХ АЛГОРИТМОВ РЕШЕНИЯ
НЕВЫРОЩЕННЫ1 ИГР.
§ I. Оценки алгоритма Шпернера для игр У* лиц и распознавание ситуаций равновесия в чистых стратегиях
1.1. Алгоритм Шпернера для решения невырожденных игр к, лиц.
1.2. Экспоненциальная нижняя оценка сложности алгоритма Шпернера для линейных диадических игр
1.3. Распознавание игр, имеющих ситуации равновесия в чистых стратегиях
§ 2. Биматричные игры. Экспоненциальная нижняя оценка для алгоритма Шпернера.
2.1. Биматричные игры и комплексы многогранников
2.2. Реализация некоторых комплексов граничными комплексами многогранников
2.3. Алгоритм Шпернера для одного класса биматричных игр.
2.4. Экспоненциальная нижняя оценка длины цепи Шпернера в полудиагональной биматричной игре
§ 3. Сложность симплекс-метода для решения матричных игр
3.1. Матричные игры и линейное программирование
3.2. Сложность решения задач линейного программирования
3.3. Симплекс-метод для решения матричных игр
3.4. Сложность симплекс-метода для решения матричных игр.-.