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

• Автор: Воробьев, Николай Николаевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Ленинград
• Количество страниц: 126 c. : ил

ГЛАВА. I. ЭФФЕКТИВНЫЕ АЛГОРИТМЫ В БЕСКОАЛИЦИОННЫХ ИГРАХ

^ ЛИЦ

§ I. Ситуации равновесия в бескоалиционных играх

1.1. Основные определения

1.2. Леша Шпернера и теорема Нэша

1.3. Оценки числа компонент множества ситуаций равновесия

§ 2. Бескоалиционные игры и системы алгебраических

уравнений и неравенств

§ 3. Оценки вещественных корней системы алгебраических

уравнений

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

3.2. Множество точек нулевой кривизны гладкой алгебраической гиперповерхности в 1Я.
3.3. Верхние оценки для координат вещественных
корней
3.4. Некоторые нижние оценки
§ 4. Распознавание совместности системы уравнений и
нахождение корней
4.1. Сведение к случаю компактного многообразия
и основная лемма
4.2. Алгоритм решения уравнения - У =. О
4.3. Системы алгебраических неравенств
4.4. Нахождение ситуацій Є- -равновесия в
бескоалиционных играх
ГЛАВА 2. ОЦЕНКИ СЛОЖНОСТИ НЕКОТОРЫХ АЛГОРИТМОВ РЕШЕНИЯ
НЕВЫРОЖДЕННЫХ ИГР
§ 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. Сложность симплекс-метода для решения матричных игр
ЛИТЕРАТУРА

Одной из основных задач теории игр является эффективное нахождение реализации принципов оптимальности в тех или иных классах игр. Сказанное относится, в первую очередь, к ситуациям равновесия по Нэшу для конечных бескоалиционных игр ги лиц, а также для. их важных частных классов: диадических, би-матричных и матричных игр. В настоящее время, для каждого из этих классов игр алгоритмы решения известны, однако, лишь для случая матричных игр можно оказать, что соответствующий алгоритм достаточно эффективен, т.е. имеет малый порядок времени работы ("сложность", о которой подробнее см. ниже). Для остальных классов игр сложность имеющихся алгоритмов либо очень высока (как правило, это очевидные, "прямолинейные" алгоритмы), либо ее оценка неизвестна. В связи с этим возникают проблемы выяснения сложности известных алгоритмов, а также построения новых, более эффективных алгоритмов. Решение указанных проблем весьма актуально, так как является необходимым условием успешного использования ЭВМ в решении игр, и, следовательно, практического применения теоретико-игровых моделей.
Одним из основных используемых в диссертации понятий является временная сложность алгоритма, к определению которой мы и перейдем. Как известно, всякий алгоритм может быть реализован в одной из канонических моделей вычисления, например, в виде машины Тьюринга с тем или иным числом лент и головок, программы для машины с произвольным доступом к памяти (РАМ) и других. В зависимости от выбранной модели, под шагом работы алгоритма естественно понимать один такт работы машины

.. . )бС К является корнем системы С3>.
Пусть - общее ЧИСЛО МОНОМОВ в многочленах
. Введем в рассмотрение систему уравнений
Gro= = • - Gr n-1"0

Gri £ (D^( £■ t —}£«j.') С x-о^КІЗ c і..., vv-1 )
и 0-1 получается из вычитанием из коэффициента при каждом мономе одной из переменных С Л 4 * £
таким образом, чтобы все £ <{- оказались использованными (по одному разу). Рассмотрим последовательность Г с <-*■>_/■ г 40 °°
д с ) з л , где для любого -£- лг г}
вещественные числа 6-^Л, - - - ^ £ алгебраически независимы над , причем -&*у 6. х — О и
О■ с14’ / Л
-^Ог с-,; /о^;+^ ~ о
с*>
Система (б) и последовательность { ё_4° Л 430 удовлет-
•3 ~
воряют всем условиям леммы 1.4. В самом деле, для любого
• система уравнений, получающаяся из (6) подстановкой - - •, вместо, Ь ч, ..., £ соответственно, имеет, в силу теоремы Лазара ( С28Л » см. также лемму 1.4) лишь конечное число корней в проективном пространстве , так как из алгебраической независимости коэффициентов следует, что сс -результант этой системы отличен от тождественного нуля. Далее, для любой рациональной функции 0, = 5/Т 5 е (Ц> предел -&*уч 5 /~т I се->
Л-*-оо * &
равен отношению некоторых коэффициентов многочленов 5 и т , так что условие 3 леммы 1.4 также выполняется. То обе-