Содержание к диссертации
ВВЕДЕНИЕ 4
ГЛАВА 1. ЭФФЕКТИВНЫЕ АЛГОРИТМЫ В БЕСКОАЛИЦИОННЫХ ИГРАХ ЛИЦ 10
§ I. Ситуации равновесия в бескоалиционных играх 10
1.1. Основные определения 10
1.2. Лемма Шпернера и теорема Нэша 17
1.3. Оценки числа компонент множества ситуаций равновесия 22
§ 2. Бескоалиционные игры и системы алгебраических уравнений и неравенств 26
§ 3. Оценки вещественных корней системы алгебраических
уравнений 33
3.1. Предельные корни параметризованной системы уравнений 34
3.2. Множество точек нулевой кривизны гладкой алгебраической гиперповерхности в IR, 40
3.3. Верхние оценки для координат вещественных корней 48
3.4. Некоторые нижние оценки 58
§ 4. Распознавание совместности системы уравнений и нахождение корней 60
4.1. Сведение к случаю компактного многообразия и основная лемма 60
4.2. Алгоритм решения уравнения JL-D=.o 66
4.3. Системы алгебраических неравенств з
4.4. Нахождение ситуацій Є- -равновесия в бескоалиционных играх 72
ГЛАВА 2. ОЦЕНКИ СЛОШОСТИ НЕКОТОРЫХ АЛГОРИТМОВ РЕШЕШ Ш
НЕВЫРОЩЕНШХ ИГР 75
§ I. Оценки алгоритма Шпернера для игр Vt лиц и
распознавание ситуаций равновесия в чистых стратегиях 75
1.1. Алгоритм Шпернера для решения невырожденных игр лиц 75
1.2. Экспоненциальная нижняя оценка сложности алгоритма Шпернера для линейных диадических игр 77
1.3. Распознавание игр, имеющих ситуации равновесия в чистых стратегиях 85
§ 2. Биматричные игры. Экспоненциальная нижняя оценка для алгоритма Шпернера 88
2.1. Биматричные игры и комплексы многогранников 88
2.2. Реализация некоторых комплексов граничными комплексами многогранников 94
2.3. Алгоритм Шпернера для одного класса биматричных игр 98
2.4. Экспоненциальная нижняя оценка длины цепи Шпернера в полудиагональной биматричной игре 101
§ 3. Сложность симплекс-метода для решения матричных игр 109
3.1. Матричные игры и линейное программирование 109
3.2. Сложность решения задач линейного программирования III
3.3. Симплекс-метод для решения матричных игр 114
3.4. Сложность симплекс-метода для решения матричных игр. 114
ЛИТЕРАТУРА 1
Введение к работе
Одной из основных задач теории игр является эффективное нахождение реализации принципов оптимальности в тех или иных классах игр. Сказанное относится, в первую очередь, к ситуациям равновесия по Нэшу для конечных бескоалиционных игр ru лиц, а также для их важных частных классов: диадических, би-матричных и матричных игр. В настоящее время, для каждого из этих классов игр алгоритмы решения известны, однако, лишь для случая матричных игр можно сказать, что соответствующий алгоритм достаточно эффективен, т.е. имеет малый порядок времени работы ("сложность", о которой подробнее см. ниже). Для остальных классов игр сложность имеющихся алгоритмов либо очень высока (как правило, это очевидные, "прямолинейные" алгоритмы), либо ее оценка неизвестна. В связи с этим возникают проблемы выяснения сложности известных алгоритмов, а также построения новых, более эффективных алгоритмов. Решение указанных проблем весьма актуально, так как является необходимым условием успешного использования ЭВМ в решении игр, и, следовательно, практического применения теоретико-игровых моделей.
Одним из основных используемых в диссертации понятий является временная сложность алгоритма, к определению которой мы и перейдем. Как известно, всякий алгоритм может быть реализован в одной из канонических моделей вычисления, например, в виде машины Тьюринга с тем или иным числом лент и головок, программы для машины с произвольным доступом к памяти (РАМ) и других. В зависимости от выбранной модели, под шагом работы алгоритма естественно понимать один такт работы машины Тьюринга, выполнение одной РАМ-команды и т.п. Временной сложностью алгоритма (в дальнейшем просто - сложностью) называется число шагов алгоритма, как функция длины записи входных данных. В тех случаях, когда для обработки входных данных одной и той же длины алгоритм использует разное число шагов, в качестве значения функции берется максимальное по всем входам данной длины число шагов. Иногда, вместо термина "сложность" используют оборот "время работы алгоритма". Если сложность алгоритма имеет порядок Р ( L) , где L - длина записи входа, в Р - многочлен, то говорят, что сложность полиномиальна, если она имеет порядок L "г , где с - константа, то сложность называется субэкспоненциальной, а если порядок L , то экспоненциальной. Подробнее о сложности и ее применении к анализу конкретных задач см. в книге [ 2 ] и в обзоре L 12 ] .
Хорошо известно (см., например, [2 3 ), что большинство разумных моделей вычислений (в частности, машины Тьюринга с разным числом лент и головок, РАМ-программы) полиномиально связаны, т.е. могут моделировать друг друга за полиномиальное время. Сложность же алгоритмов, рассматриваемых в настоящей диссертации будет изучаться с точностью до полинома; поэтому у нас не возникнет необходимости в конкретизации модели вычислений и все алгоритмы будут излагаться на обычном математическом языке.
Перечислим некоторые известные ранее результаты, связанные с затрагиваемой в диссертации проблематикой. Большое число работ было посвящено описанию алгоритмов отыскания ситуаций равновесия (решению) матричных, биматричных и, в меньшей степени бескоалиционных игр п» лиц , однако, как уже отмечалось выше, сложность большинства этих алгоритмов либо очень высока, либо ее оценка неизвестна. Замечательным исключением является, принадлежащий Л.Г.Хачияну [Зі] , алгоритм полиномиальной сложности для решения матричных игр (или задачи линейного программирования; хорошо известно ( С 61 ), что эти две задачи взаимно сводимы за полиномиальное время). Все остальные исследования, касающиеся решения бескоалиционных игр ограничивались, в основном, доказательствами NP--полноты (см. [26] или п. 1.3, гл. П) или NP- SPACE --полноты ( [ 261 ) для ряда, так называемых, "комбинаторных" игр (типа шахмат или шашек на бесконечной доске и т.п.).
В описываемых в данной диссертации алгоритмах решения бескоалиционных игр rv. лиц существенную роль играют вспомогательные алгоритмы для нахождения вещественных решений систем алгебраических (полиномиальных) уравнений и неравенств, которые приходится достаточно подробно рассматривать. Известные ранее результаты в этом направлении содержатся в работах [25] , [34] , [2] .
Диссертация состоит из настоящего введения, двух глав, объединяющих семь параграфов, и библиографии.
Первая глава посвящена подробному исследованию множеств ситуаций равновесия в конечных бескоалиционных играх и построению эффективных алгоритмов решения игр rv лиц. В начале главы (§1) приводятся необходимые определения и устанавливается связь между теоремой о конечности и нечетности числа ситуаций равновесия в невырожденной игре и известной комбинаторной леммой Шпернера. Даются оценки числа компонент (см. § I) множества ситуаций равновесия. В § 2 описываются некоторые способы сведения решения игры ft лиц к нахождению вещественных решений систем алгебраических уравнений и неравенств. В случае невырожденной игры соответствующие системы уравнений устроены сравнительно просто и алгоритм для их решения удается построить на основе известного (см. [ 24"] ) алгоритма для уравнений над алгебраически замкнутым полем. 3 результате получается эффективный алгоритм для нахождения всех ситуаций равновесия в невыроаденной бескоалиционной игре. Далее, в связи с вырожденными играми гъ лиц, рассматри-вается задача эффективного решения в IR произвольных систем алгебраических уравнений и неравенств, которая представляет, по-видимому, и самостоятельный интерес. В качестве предварительного этапа, в § 3 получаются некоторые новые.верхние и нижние оценки модулей координат вещественных корней систем уравнений. В § 4 предлагаются алгоритмы субэкспоненциальной сложности для распознавания совместности в IR систем уравнений и неравенств, а также для приближенного решения в IR систем уравнений. На их основе строится эффективный алгоритм для нахождения ситуации Є -равновесия в произвольной игре Рь лиц.
Для решения невырожденных игр некоторых классов могут быть использованы алгоритмы, основанные на идее леммы Шперне-ра. Проблема оценки сложности подобных алгоритмов нетривиальна. В §§ I и 2 главы П эта проблема решается для линейных диа-дических и полудиагональных биматричных игр. Уже для этих простых классов игр сложность алгоритма Шпернера оказывается экспоненциальной. В качестве вспомогательного аппарата доказываются некоторые теоремы о представлении комплексов многогранников граничными комплексами многогранников.
Кроме того, в § I доказана MP -полнота задачи распознавания наличия ситуации равновесия в чистых стратегиях в одном классе бескоалиционных игр с "компактно заданными" функциями выигрыша.
Хорошо известно, что симплекс-метод для решения задач линейного программирования имеет экспоненциальную сложность ( І27І ). Вопрос оказывается более тонким, если ограничиться задачами линейного программирования, естественно возникающими при решении матричных игр. В § 3 главы П доказывается, что и для этого класса задач симплекс-метод экспоненциален. Соответствующая конструкция получается существенно более громоздкой, чем в случае класса задач, рассмотренного в 27] .
Почти все параграфы для удобства чтения разбиты на пункты, снабженные названиями. Все утверждения (теоремы или леммы) нумеруются двумя числами, первое из которых совпадает с номером соответствующей главы, а второе - с номером утверждения по порядку в рамках этой главы. Формулы нумеруются отдельно в каждом параграфе.
Всюду в диссертации буквы "Ж , Q, , IR , С обозначают соответственно множества целых, рациональных, вещественных и комплексных чисел. Все логарифмы берутся по основанию 2.
Основные результаты диссертации опубликованы автором в следующих работах:
I. О сложности распознавания устойчивости в графах. -В кн.: Многошаговые, дифференциальные, бескоалиционные и кооперативные игры и их приложения. Калинин, 1982, с. 110-114.
2. Сложность двух алгоритмов решения игр двух лиц. -Ленинград, 1983. - 19 с. - Ред.ж. "Вестник ЛГУ". Ден. в ВИНИТИ 20 дек. 1983, J& 6881-83.
3.Оценки вещественных корней системы алгебраических уравнений. - Зап.науч.семин. ЛОМИ, 1984, т. 137, с. 7-19.
4. Экспоненциальная сложность алгоритма Шпернера для диадических бескоалиционных игр. - Вильнюс: Ин-т математики и кибернетики АН Лит.ССР, 1984. (Матем.методы в социальных науках, вып. 17, с. 9-17).
