Эффективные алгоритмы решения конечных безкоалиционных игр тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА. 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. Сложность симплекс-метода для решения матричных игр.-.

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

Одним из основных используемых в диссертации понятий является временная сложность алгоритма, к определению которой мы и перейдем. Как известно, всякий алгоритм может быть реализован в одной из канонических моделей вычисления, например, в виде машины Тьюринга с тем или иным числом лент и головок, программы для машины с произвольным доступом к памяти (РАМ) и друтих. В зависимости от выбранной модели, под шагом работы алгоритма естественно понимать один такт работы машины

Тьюринга, выполнение одной РАМ-команды и т.п. Временной сложностью алгоритма (в дальнейшем просто - сложностью) называется число шагов алгоритма, как функция длины записи входных данных. В тех случаях, когда для обработки входных данных одной и той же длины алгоритм использует разное число шагов, в качестве значения функции берется максимальное по всем входам данной длины число шагов. Иногда, вместо термина "сложность" используют оборот "время работы алгоритма". Если сложность алгоритма имеет порядок Р (О , где I- - длина записи входа, а Р многочлен, то говорят, что сложность полиномиальна, если она имеет порядок , где с - константа, то сложность называется субэкспоненциальной, а если порядок ~ , то экспоненциальной. Подробнее о сложности и ее применении к анализу конкретных задач см. в книге [ 2 ] и в обзоре С 12 ] .

Хорошо известно (см., например, [21 ), что большинство разумных моделей вычислений (в частности, машины Тьюринга с разным числом лент и головок, РАМ-программы) полиномиально связаны, т.е. могут моделировать друг друга за полиномиальное время. Сложность же алгоритмов, рассматриваемых в настоящей диссертации будет изучаться с точностью до полинома; поэтому у нас не возникнет необходимости в конкретизации модели вычислений и все алгоритмы будут излагаться на обычном математическом языке.

Перечислим некоторые известные ранее результаты, связанные с затрагиваемой в диссертации проблематикой. Большое число работ было посвящено описанию алгоритмов отыскания ситуаций равновесия (решению) матричных, биматричных и, в меньшей степени бескоалиционных игр п* лиц , однако, как уже отмечалось выше, сложность большинства этих алгоритмов либо очень высока, либо ее оценка неизвестна. Замечательным исключением является, принадлежащий Л.Г.Хачияну [31] , алгоритм полиномиальной сложности для решения матричных игр (или задачи линейного программирования; хорошо известно С С 6□ ), что эти две задачи взаимно сводимы за полиномиальное время). Все остальные исследования, касающиеся решения бескоалиционных игр ограничивались, в основном, доказательствами NP--полноты (см. [261 или п. 1.3, гл. П) или NP- SPACE --полноты ( [ 261 ) для ряда, так называемых, "комбинаторных" игр (типа шахмат или шашек на бесконечной доске и т.п.).

В описываемых в данной диссертации алгоритмах решения бескоалиционных игр rv. лиц существенную роль играют вспомогательные алгоритмы для нахождения вещественных решений систем алгебраических (полиномиальных) уравнений и неравенств, которые приходится достаточно подробно рассматривать. Известные ранее результаты в этом направлении содержатся в работах [25] , [34] , [24] .

Диссертация состоит из настоящего введения, двух глав, объединяющих семь параграфов, и библиографии.

Первая глава посвящена подробному исследованию множеств ситуаций равновесия в конечных бескоалиционных играх и построению эффективных алгоритмов решения игр лиц. В начале главы (§1) приводятся необходимые определения и устанавливается связь между теоремой о конечности и нечетности числа ситуаций равновесия в невырожденной игре и известной комбинаторной леммой Шпернера. Даются оценки числа компонент (см. § I) множества ситуаций равновесия. В § 2 описываются некоторые способы сведения решения игры ги лиц к нахождению вещественных решений систем алгебраических уравнений и неравенств. В случае невырожденной игры соответствующие системы уравнений устроены сравнительно просто и алгоритм для их решения удается построить на основе известного (см. С 24"] ) алгоритма для уравнений над алгебраически замкнутым полем, В результате получается эффективный алгоритм для нахождения всех ситуаций равновесия в невырозденной бескоалиционной игре.

Далее, в связи с вырожденными играми гъ лиц, рассматри вается задача эффективного решения в ^ произвольных систем алгебраических уравнений и неравенств, которая представляет, по-видимому, и самостоятельный интерес. В качестве предварительного этапа, в § 3 получаются некоторые новые.верхние и нижние оценки модулей координат вещественных корней систем уравнений. В § 4 предлагаются алгоритмы субэкспоненциальной сложности для распознавания совместности в 1(3. систем уравнений и неравенств, а также для приближенного решения в систем уравнений. На их основе строится эффективный алгоритм для нахождения ситуации £- -равновесия в произвольной игре лиц.

Для решения невырожденных игр некоторых классов могут быть использованы алгоритмы, основанные на идее леммы Шперне-ра. Проблема оценки сложности подобных алгоритмов нетривиальна. В §§ I и 2 главы П эта проблема решается для линейных диа-дических и полудиагональных биматричных игр. Уже для этих простых классов игр сложность алгоритма Шпернера оказывается экспоненциальной. В качестве вспомогательного аппарата доказываются некоторые теоремы о представлении комплексов многогранников граничными комплексами многогранников.

Кроме того, в § I доказана МР -полнота задачи распознавания наличия ситуации равновесия в чистых стратегиях в одном массе бескоалиционных игр с "компактно заданными" функциями выигрыша.

Хорошо известно, что симплекс-метод для решения задач'линейного программирования имеет экспоненциальную сложность ( 1.271 ), Вопрос оказывается более тонким, если ограничиться задачами линейного программирования, естественно возникающими при решении матричных игр. В § 3 главы П доказывается, что и для этого класса задач симплекс-метод экспоненциален. Соответствующая конструкция получается существенно более громоздкой, чем в случае класса задач, рассмотренного в £27] .

Почти все параграфы для удобства чтения разбиты на пункты, снабженные названиями. Все утверждения (теоремы или леммы) нумеруются двумя числами, первое из которых совпадает с номером соответствующей главы, а второе - с номером утверждения по порядку в рамках этой главы. Формулы нумеруются отдельно в каждом параграфе.

Всюду в диссертации буквы "Ж , О, , 1К, , С обозначают соответственно множества целых, рациональных, вещественных и комплексных чисел. Все логарифмы берутся по основанию 2.

Основные результаты диссертации опубликованы автором в следующих работах:

I. О сложности распознавания устойчивости в графах. -В кн.: Многошаговые, дифференциальные, бескоалиционные и кооперативные игры и их приложения. Калинин, 1982, g. 110114.

2. Сложность двух алгоритмов решения игр двух лиц. -Ленинград, 1983. - 19 с. - Ред.я. "Вестник ЛГУ". Деп. в ВИНИТИ 20 дек. 1983, Jfc 6881-83.

3.Оценки вещественных корней системы алгебраических уравнений. - Зап.науч.семин. ЛОМИ, 1984, т. 137, с. 7-19.

4. Экспоненциальная сложность алгоритма Шпернера для диадических бескоалиционных игр. - Вильнюс: Ин-т математики и кибернетики АН Лит.ССР, 1984. (Матем.методы в социальных науках, вып. 17, с. 9-17).

1. Александров П.С. Комбинаторная топология. - М.-Л.: Гос-техиздат, 1947. - 660 с.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

3. Берж К. Теория графов и ее применение. М.: ИЛ, 1962. -248 с.

4. Ван-дер-Варден Б.Л. Алгебра. М.: Наука, 1976. - 648 с.

5. Ван-дер-Варден Б.Л. Современная алгебра. М.-Л.: Гостех-издат, 1947. - 340 с.

6. Воробьев Н.Н. Основы теории игр. Бескоалиционные игры. -М.: Наука, 1984. 496 с.

7. Григорьев Д.Ю. Разложение многочленов над конечным полеми решение систем алгебраических уравнений. Зап.науч.семин. ЛОМИ АН СССР, 1984, т. 137, с. 20-79.

8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

9. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981. - 342 с.

10. Милнор Дж., Уоллес А. Дифференциальная топология. М.: Мир, 1972. - 278 с.

11. Нэш Дж. Бескоалиционные игры. В кн.: Матричные игры. М., 1961, с. 205-221.

12. Слисенко А.0. Сложностные задачи теории вычислений. -Успехи матем.наук, 1981, т. 36, вып. 6, с. 21-103.

13. Торп Дж. Начальные главы дифференциальной геометрии. -М.: Мир, 1982. 360 с.

14. Фоменко А.Т. Дифференциальная геометрия и топология. Дополнительные главы. М.: МГУ, 1983. - 214 о.

15. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании. Докл. АН СССР, 1979, т. 244, вып. 5, с. 10931098.

16. Хачиян Л.Г. Полиномиальные алгоритма в линейном программировании. ЖВМ и Му), 1980, т. 20, й I, с. 51-68.

17. Хирш Ы. Дифференциальная топология. М.: Мир, 1979.- 280 с.

18. Хода 3., Пидо Д. Методы алгебраической геометрии. М.: ИЛ. - т. 2, 432 с.

19. Черников G.H. Линейные неравенства. М.: Наука, 1968.- 340 с.

20. Черняков А.Г. Устойчивость для конечных бескоалиционных игр. Докл. АН СССР, 1979, т. 247, вып. 4, с. 809-811.

21. Чистов А.Л. Алгоритм полиномиальной сложности для разложения многочленов и нахождение компонент многообразия в субэкспоненциальное время. Зап.науч.семин. ЛОМИ АН СССР, 1984, т. 137, с. 124-188.

22. Шафаревич И.Р. Основы алгебраической геометрии. М.: Наука, 1972. - 568 с.

23. Akritas A.G. The fastest exact algorithms for the isolation of the real roots of a polynomial equation.-Computing, 1980, v.24, p.299-313.

24. Chistov A.L., Grigoryev D.Yu. Subexponential-time solving systems of algebraik equations.- LOMI preprint E-9-83, Leningrad, 1983.

25. Collins G.e. Quantifier elimination for real closed,1 fields by cylindrical algebraic decomposition. Lect.Notes Comput, Sei., 1975, v.33, p.134-183.

26. Fraenkel A.S. Planar kernel and Grundy with d < 3, dQut < 2,d. <2 are NP-complete. Discrete Appl.Math., 1981, 3, m =p.257-262.Klee V., Minty G.J. How good is the simplex algorithm? -In: Inequalities-Ill, 1972, p.159-175.

27. Lemke O.E., Howson J.T. Equilibrium points in bimati'ix games. SIAM J.Appl.Math., T964, v.12, 2, p.413-423.

28. Lazard D. Rezolutions des systemes d*equations algebriques. Theor.Comput.Sei., 1981, v.15, p.77-110.

29. Milnor J. On the Betti numbers of real varieties. Pros. Amer.Math.Soc., 1964, v.15, 2, p.275-280.

30. Rosenmüller J. On a generalization of the Lemke-Howson algorithm to noncooperative N-person games. SIAM J.Appl. Math., 1971, v.21, 1, p.73-79.

31. Sahni S. Computationally related problems. SIAM J.Comput., 1974, v.3, 4, p.262-279.

32. Wilson R. Computing equilibria of N-person games. SIAM J.Appl.Math., 1971, v.21, 1, p.80-87.

33. Wüthrich H.R. Ein Entscheidungsverfahren für die Theorie der reel-abgeschlossenen Körper. Lect.Notes Comp.Sei., 1976, v.43, p.138-162.

34. Game theor;/ and related topics./Moeschlin 0., Pallaschke D. ed. North Holland, 1979. - 398 p.