автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Поиск ситуаций равновесия в биматричных играх

Введение

1 Биматричные игры и d.c. максимизация

1.1 Основные определения и свойства биматричных игр.

1.2 Некоторые известные методы поиска ситуаций равновесия.

1.2.1 Вполне смешанные ситуаций равновесия.

1.2.2 Исчерпывающий поиск.

1.2.3 Перебор носителей стратегий.

1.2.4 Биматричные игры и целочисленное линейное программирование

1.2.5 Связь с матричными играми.

1.2.6 Перебор квадратных подматриц.

1.3 Задача дополнительности и метод Лемке-Хаусона.

1.4 Биматричные игры и математическое программирование.

1.5 Постановка задачи d.c. максимизации и локальный поиск.

1.6 Условия глобальной оптимальности.

1.7 Стратегия глобального поиска.

1.8 Сходимость стратегии глобального поиска.

1.9 О разрешающих наборах

2 Основы поиска ситуаций равновесия в биматричной игре

2.1 D.C. представление целевой функции.

2.2 Условия глобальной оптимальности

2.3 Локальный поиск.

2.4 Алгоритм глобального поиска

2.5 Решение задачи уровня.

2.6 Вычисление интервала одномерного поиска.

2.6.1 Поиск левой границы

2.6.2 Поиск правой границы 7+.

2.7 Построение аппроксимации поверхности уровня

3 Численный поиск ситуаций равновесия

3.1 Особенности первого вычислительного эксперимента.

3.2 Этап 1. Тестирование алгоритма глобального поиска.

3.3 Этап 2. Решение случайно сгенерированных задач небольших размерностей

3.4 Этап 3. Выбор наилучшей аппроксимации поверхности уровня.

3.5 Этап 4. Поиск ситуаций равновесия в играх большой размерности

3.6 Этап 5. Решение серий биматричных игр.

3.7 Модификация алгоритма глобального поиска.

3.8 Второй вычислительный эксперимент.

Проблема принятия решения — важнейшая сторона человеческой деятельности. Во многих случаях решение о выборе целенаправленной совокупности действий приходится принимать в условиях конфликта, т.е. при столкновении сторон, каждая из которых стремится воздействовать на развитие ситуации в своих собственных интересах. Формализацией и изучением различного рода конфликтов занимается математическая теория игр, которая является составной частью исследования операций [23, 28]. Присуждение Дж.Ф.Нэшу Нобелевской премии 1994 г. за цикл работ, посвященных концепции равновесия в экономике и теории игр, послужило очередным подтверждением актуальности этого направления исследований.

Теория игр является мощным средством моделирования стратегических взаимодействий в некоторой системе, когда различные стороны должны действовать и реагировать одновременно, предвосхищая соответствующие реакции друг друга. С помощью моделей теории игр может быть описан широкий спектр проблем, возникающих в жизни и деятельности человека. Например, нерегулируемый рынок может быть изучен посредством теории равновесия Нэша [26, 34, 41, 69, 89,109]. Прогнозные ситуации можно моделировать с помощью теории повторяющихся игр [130], методы теории динамических игр применяются при анализе сложных социально-экономических и экологических систем, а также при решении вопросов глобального стратегического баланса [30, 61]. Теория игр также может помочь в различных переговорных ситуациях, например, в переговорах с террористами [94, 109], в теории статистических решений ("играх" с природой) [11] и при решении экологических проблем [26].

Несмотря на многообразие, игры можно классифицировать, основываясь на том или ином принципе [И].

1) В зависимости от числа участников конфликта (игроков) различают игры с двумя, тремя и более участниками.

2) В зависимости от возможности предварительной договоренности между игроками выделяют кооперативные и некооперативные (бескоалиционные) игры.

3) По количеству стратегий поведения игроков различают конечные и бесконечные непрерывные) игры.

4) В зависимости от числа ходов в игре различают одношаговые и многошаговые игры.

5) Возможны различные случаи информированности игроков о функциях выигрыша друг друга.

6) Наконец, по свойствам функций выигрыша выделяют антагонистические (игры с нулевой суммой) и неантагонистические игры. Антагонистические игры моделируют кофликты двух сторон, интересы которых прямо противоположны, а в неантагонистических играх не исключаются и компромиссные решения. Также возможны ситуации, когда функции выигрыша принимают случайные значения.

Изучение конфликтов, а, следовательно, и игровых моделей можно проводить в различных аспектах: дескриптивном — выявляющем, какие ситуации могут складываться; нормативном — устанавливающем, какое поведение игроков следует считать оптимальным; конструктивном — указывающем, как создавать требуемые ситуации, и прогностическом — занимающимся прогнозированием фактического исхода конфликта. Теория игр в ее современном состоянии занимается, главным образом, нормативным аспектом изучения. В связи с этим можно выделить три основные задачи теории игр: конструирование содержательных принципов оптимального поведения участников конфликта; анализ этих принципов и установление их реализуемости;

- отыскание оптимальных реализаций.

За более чем полувековой период развития теории игр, практически для всех типов игр из вышеприведенной классификации было предложено множество понятий оптимальности и изучены их свойства [11, 19, 21, 24, 57, 58, 62, 64, 95, 98, 116, 117, 118,130, 146]. Классическими понятиями оптимальности являются равновесия Нэша и Парето (см. также [40, 88, 121, 122, 126, 127, 128]). В первом случае ни один игрок, действуя в одиночку, не может увеличить своего выигрыша, во втором — все игроки, действуя совместно, не могут (даже нестрого) увеличить выигрыш каждого.

Общие теоретические исследования игр и их экономических приложений одними из первых проводили Дж. фон Нейман и О.Моргенштерн [41]. В нашей стране это направление начали разрабатывать Ю.Б.Гермейер [23, 24] и Н.Н. Воробьев [19]—[21]. Среди работающих в настоящее время в области теоретического изучения игр российских ученых можно отметить Л.В.Петросяна [61, 63] и его работы в области многошаговых и дифференциальных игр, а также А.С.Антипина [4]-[8], [17], в чьих работах нашла отражение концепция выпуклой игры Дж.Б.Розена [134].

Таким образом, можно считать, что первые две сформулированные задачи теории игр исследованы достаточно глубоко. К сожалению, этого нельзя сказать о третьей задаче — отыскании оптимальных стратегий поведения участников конфликта. В настоящее время можно считать хорошо разработанными только методы численного поиска решений в самом простом классе игр — матричных (конечных антагонистических) [58]. При всей своей элегантности теория матричных игр едва ли приложима к многочисленным проблемам экономики и других социальных наук. Поэтому поиск равновесных решений в более сложных классах игр представляет весьма актуальный вызов реальностей политической, экономической, экологической и технической составляющих функционирования человеческой цивилизации.

В данной работе изучаются биматричные игры, принадлежащие классу неантагонистических игр двух лиц с конечным числом стратегий поведения. Эти игры, простейшие среди бескоалиционных, можно считать первым по сложности обобщением матричных игр. А название рассматриваемого класса объясняется тем, что вся информация о конфликте может быть записана в двух матрицах. Элементы первой матрицы (обычно обозначается через А) — это значения функции выигрыша первого игрока в каждой возможной ситуации, а элементы второй (В) — значения функции выигрыша второго игрока.

В качестве примеров биматричных бескоалиционных игр можно рассмотреть следующие модели.

1. Экологический конфликт

Здесь на конкретном примере рассмотрим общие принципы моделирования подобного сорта проблем без излишней детализации задачи [11].

Два промышленных предприятия, расположенные вблизи водоема, берут из него воду для технических нужд и после использования сбрасывают ее обратно в водоем. Если суммарный объем сбрасываемой (загрязненной) воды превышает некоторую допустимую величину, возникает проблема восстановления водоема за счет предприятий.

Чтобы избежать неприятных последствий, приходится строить очистные сооружения, стоимость которых пропорциональна объему пропускаемой через них воды (пропускной способности). Вопрос заключается в том, как выработать разумную политику по отношению к эксплуатируемому водоему.

Суть конфликта, возникающего между рассматриваемыми предприятиями, сводится к их стремлению обеспечить себе благоприятные условия деятельности путем более свободного расходования природной воды. Это отрицательно влияет на состояние водоема и через него — на технологические режимы и качество продукции обоих предприятий. Эти вещи оказываются взаимосвязанным, и появляется заинтересованность в поиске решений, приемлемых для конфликтующих сторон, хотя никакой договоренности между ними может и не быть. Значит, имеет смысл представить возникшую ситуацию как бескоалиционную игру двух лиц с конечным числом стратегий.

В качестве стратегий игроков возьмем пропускную способность очистных сооружений, которые должно построить каждое предприятие. Конкретный вид биматрич-ной игры и функций выигрыша предприятий, которые характеризуют прибыль от реализации продукции, может быть получен после детализации поставленной задачи. #

2. Нерегулируемый рынок с несовершенной конкуренцией (олигополия)

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

Возможны два основных варианта поведения фирм в зависимости от выбора ими так называемой стратегической переменной (т.е. что выступает в качестве стратегий игроков): количество реализуемой или производимой продукции или ее цена. В первом случае используется модель Курно, во втором — модель Бертрана [26, 41, 69, 89, 109].

1) Модель Курно.

Рассмотрим эту модель на конкретном примере рынка электроэнергетических систем [ИЗ].

Как известно, электроэнергетика многих стран мира является дерегулируемой. Главной целью подобной организации рынка является уменьшение цен для потребителей путем создания конкуренции. Однако, в некоторых случах имеется возможность захвата рынка производящими компаниями. Такой рынок имеет свойства олигополии. Например, на рынке Англии и Уэльса в 90-е годы две крупные компании играли преобладающую роль на рынке электроэнергии, продавая ее по значительно более высокой цене, чем себестоимость. Следовательно, необходимо изучение свойств энергетического рынка, которое включает в себя установление оптимального поведения его участников по отношению к получаемой прибыли с учетом интересов потребителей, а также ограничений на передачу электроэнергии.

Рассмотрим случай двух производителей и одного потребителя, соединенных одинарной линией передач. Пусть себестоимость электроэнергии у первого и второго производителя равна соответственно at и за один МВт/ч, и обе электростанции равны по мощности, которая составляет w МВт. Предполагается, что потребитель имеет спрос d, который связан с рыночной ценой обратной кривой спроса [69]: p(d) = с — hd, где с > 0, h > 0 — некоторые заранее заданные константы. Функции выигрыша производителей зависят от рыночной цены р, себестоимости аь а2 и количества энергии qx, q2, предложенной ими на рынок:

Fl = (p-al)ql; F2 = (p-a2)q2. (0.0.1)

Предположим, что спрос равен предложению (d — 91+92)- Тогда рыночная цена будет определяться по формуле: р = с — h(qi + q2).

Несмотря на то, что введенные переменные имеют непрерывную природу, можно аппроксимировать процесс принятия решения рассмотрением только нескольких дискретных значений из отрезка [0, w] (реальная задача, как правило, дискретна). Посчитав прибыли игроков для каждой комбинации дискретных значений по формулам (0.0.1), получим матрицы А и В, которые можно интерпретировать как биматричную игру и исследовать соответствующими методами.

Подобным образом могут быть смоделированы более сложные случаи, когда в задаче присутствуют ограничения на передачу электроэнергии, ограничения потребителей и т. д. Все эти условия включаются в функции Fi и F2 и затем точно также строятся матрицы А и В. С помощью биматричных игр можно исследовать и более сложные системы, где производители соединены не одинарной линией передач, а двойной или тройной [113].

Модель Курно применима также для моделирования других рынков (не только для рынка электроэнергии), где в качестве стратегической переменной фирмы выбирают объемы продукции [26, 41, 69, 89,109].

2) Модель Бертрана.

Эту модель, в отличие от предыдущей, рассмотрим в более общем виде без привязки к конкретному продукту. Существуют различные варианты модели Бертрана. Опишем ее с использованием понятия эластичность спроса по цене [89].

Пусть две фирмы реализуют на рынке один и тот же товар, а у потребителя нет полной информации о ценах на рынке (он ориентируется только на цену конкретной фирмы). Задана функция спроса на этот товар d(p), зависящая от цены р. Эластичность спроса по цене (т.е. отношение процентного изменения величины спроса к процентному изменению цены, см., например, [69, 89]) вычисляется по формуле

Аллена [89]: e(p) = d'(p) Р d(Py

Пусть, далее, первая фирма устанавливает цену на товар pt=p — Ар, а вторая — р2 Ар, где р — средняя цена на данный товар. Тогда количество товара, которое будет реализовано первой фирмой, вычисляется по формуле = + (0-0.2)

2 Р а второй — по формуле = ^(1 - k(rtl^)- (0.0.3) 2 р

Функции выигрыша (прибыли) фирм имеют вид:

Fx = Piqi - txfa), F2 = piдг - h{q2), (0.0.4) где ii(-), £г(') — функции издержек, зависящие от количества реализуемого товара.

Следует отметить некоторые ограничения этой модели: возможные погрешности при больших различиях между ценами pi и р2, поскольку спрос и эластичность вычисляются в средней точке р.

Таким образом, выбирая несколько дискретных значений цен рх и р2 для первого и второго игроков из отрезка [р,р+] (минимальная и максимальная возможная цена) и вычисляя эластичность по формуле Аллена, а количество товара по формулам (0.0.2) и (0.0.3) соответственно, можно построить матрицы А и В. Элементы этих матриц представляют собой значения функций прибыли игроков Fi и F2, подсчитанные по формулам (0.0.4). Полученную биматричную игру можно исследовать соответствующими методами. #

Во всех вышеприведенных примерах для выработки оптимальных в некотором смысле стратегий поведения требуется найти по крайней мере равновесие по Нэшу, которое является одним из самых слабых, хотя и естественным понятием равновесия в бескоалиционных играх. Знаменитая теорема Нэша [126] гарантирует существование ситуаций равновесия в бескоалиционных играх. Однако, известно, что равновесие по Нэшу обладает рядом недостатков, таких как неединственность равновесной ситуации, ее неустойчивость относительно отклонений групп игроков, неэффективностью в смысле Парето и др. Поэтому исследования по различным уточнениям равновесия по Нэшу проводятся в разных странах мира.

Первым естественным уточнением этого равновесия является концепция сильного (строго сильного) равновесия [63, 84], которая подразумевает невыгодность произвольного отклонения каждой коалиции игроков от оптимальной ситуации, так как среди участников отклоняющейся коалиции обязательно найдется игрок, чей выигрыш при совместном отклонении не увеличивается (уменьшается). Оказывается, что строго сильное равновесие эффективно в смысле Парето [63, 88], которое существует в любой бескоалиционной игре [21].

С другой стороны, при допущении, что всегда существует малая положительная вероятность того, что игрок может выбрать любую (в том числе неоптимальную) стратегию по ошибке, вводится концепция так называемого совершенного равновесия [63, 136]. Совершенно равновесная стратегия оптимальна (в смысле определения Нэша) не только по отношению к набору оптимальных стратегий других игроков, но и по отношению к некоторым "слабым возмущениям" этих стратегий. Дальнейшее усиление этой концепции приводит к понятию собственного равновесия [63,106, 149]. Показано, что в любой бескоалиционной игре совершенное и собственное равновесия всегда существуют [63].

Вообще, для бескоалиционных игр известен целый ряд уточнений равновесия по Нэшу — строго собственное равновесие, изолированное равновесие, квазистрогое равновесие, регулярное равновесие и многие другие [63, 105,108, 123, 124, 125, 132, 133, 148,149,150]. Теорема Нэша и другие подобные результаты гарантируют существование равновесных ситуаций, но не дают никаких средств для их нахождения. Поэтому пока все эти понятия имеют скорее теоретический характер, и в настоящее время неизвестны общие способы нахождения в бескоалиционных играх даже простых ситуаций равновесия по Нэшу. Математически эта задача оказывается чрезвычайно сложной, однако для отдельных достаточно простых классов бескоалиционных игр (например для биматричных) она поддается решению.

Поэтому разумным представляется рассмотрение везде далее только конечных бескоалиционных игр двух лиц (биматричных), а также, если не оговорено особо, под словами "ситуация равновесия" или "равновесие" будет подразумеваться ситуация равновесия по Нэшу без дополнительных условий.

Проблема поиска ситуаций равновесия в биматричных играх рассматривается всеми исследователями в двух аспектах: поиск одной ситуации равновесия и поиск всех, ситуаций равновесия с целью выделения из множества оптимальных ситуаций тех, которые удовлетворяют дополнительным условиям (сильного равновесия, совершенного равновесия и др.).

Задачу численного поиска одной ситуации равновесия в биматричной игре можно считать достаточно хорошо изученной. Различные алгоритмы для определения ситуаций равновесия были предложены Н.Н. Воробьевым [20], X.Куном [111], О.Мангасаряном [119] и другими авторами (см., например, [92, 138, 151]), но все они представляют скорее теоретический интерес и малопригодны для практических вычислений. В основном, предлагаемые алгоритмы базируются на переборе крайних точек многогранника допустимых стратегий и при возрастании размерности задачи отыскание ситуаций равновесия становится практически невозможным (см. обзор в главе 1).

Единственным эффективным и используемым на практике методом является алгоритм Лемке-Хаусона [110,115,137] (см. §1.3). Он предназначен для поиска решения линейной задачи дополнительности (см. например [10]), с помощью которого мож-, но построить ситуацию равновесия по Нэшу в биматричной игре. Однако, исследования эффективности метода Лемке-Хаусона показывают [135], что для некоторого класса биматричных игр, количество точек, просматриваемых в процессе решения, экспоненциально зависит от размерности задачи. Ситуация аналогична положению симплекс-метода в линейном программировании, практическая эффективность которого не подвергается сомнению, однако построены контрпримеры, где число угловых точек, перебираемых в процессе решения, экспоненциально зависит от размерности. К тому же для отыскания решений, скажем, в играх с квадратичными функциями выигрыша или с квадратичными ограничениями метод Лемке-Хаусона уже неприменим. Кроме того, оценивание близости текущей точки к оптимальной здесь требует дополнительных вычислений и исследований, поскольку в задаче линейной дополнительности отсутствует целевая функция. Поэтому возникает вопрос о разработке новых методик численного поиска ситуаций равновесия, которые, возможно, будут эффективны для более сложных игр.

Ситуация с численным отысканием всех ситуаций равновесия, естественно, гораздо сложнее. Однако и на этом пути уже достигнуты некоторые успехи. Результаты решения этой проблемы можно отыскать в [85, 121, 152].

В данной работе изучается и применяется вариационный подход к нахождению одной ситуаций равновесия [40, 114, 120, 122]. Задача поиска равновесия по Нэшу в биматричной игре сводится к нахождению глобального решения в некоторой билинейной невыпуклой задаче математического программирования. Этот подход, в отличие от метода Лемке-Хаусона, непопулярен, поскольку упомянутая задача во многих случаях представляется неразрешимой. Удалось отыскать только одну попытку решения данной задачи в работе советского математика Б.М.Мухамедиева [40] (см. §1.4). Эта неразрешимость связана, с одной стороны, с тем, что известные методы выпуклой оптимизации (см. например [10], [16]) в невыпуклых задачах, вообще говоря, позволяют отыскать только критические (стационарные) точки, или, в лучшем случае, локальные решения, которые могут быть очень далеки от глобального решения даже по значению целевой функции.

С другой стороны, доминирующие в настоящее время в глобальной (невыпуклой) оптимизации методы ветвей и границ, отсечений, аппроксимаций и т. д., пришедшие из дискретной оптимизации, "страдают" от так называемого "проклятия размерности". Это означает, что с увеличением размерности объем вычислений по этим методам возрастает экспоненциально, что не позволяет найти именно глобальное решение.

Построенный в последнее время новый аппарат решения невыпуклых задач оптимизации, основанный на теории глобального экстремума [37], [71]—[80], [139]—[142], необходимые элементы которого будут описаны в главе 1, на наш взгляд, открывает более широкие возможности действительного поиска равновесных решений в конфликтных ситуациях. В главах 2 и 3 на примере биматричной игры будет продемонстрирована такая возможность.

А именно, отыскание ситуации равновесия по Нэшу здесь осуществляется по стратегии глобального поиска для задач d.c. максимизации (глава 1), где целевая функция представима в виде разности двух выпуклых функций. Такие функции в литературе принято называть d.c. функциями (the difference of two convex functions). Применение подобной стратегии обосновано, поскольку получающаяся при сведении биматричной игры билинейная задача математического программирования, как частный случай задачи квадратичного программирования, является d.c. задачей.

Задачи d.c. программирования являются одним из классов невыпуклых задач, которые рассматриваются в литературе. Хотя достаточно сложно в настоящий момент привести полную классификацию задач невыпуклой оптимизации, специалисты выделяют следующие четыре класса задач.

1. Выпуклая максимизация (или вогнутая минимизация): f{x) t max, хе D, (0.0.5) где /(•) — выпуклая функция на некотором открытом выпуклом множестве П С Мп, содержащем допустимое множество D.

2. Обратно-выпуклые задачи или задачи на дополнениях выпуклых множеств. Простейшей задачей подобного типа является следующая: ip(x) I min, х G S, д(х) > 0, (0.0.6) где д(-) — выпуклая функция на выпуклом открытом множестве П с JR71, содержащем множество S, с/з(-) — непрерывная функция на Rn.

3. D.c. максимизация:

F(x) = /(i) - д{х) | шах, х € D, (0.0.7) где /(•), д{-) — выпуклые функции на некотором открытом выпуклом множестве П с iRn, D eft, т.е. F(-) — d.c. функция.

4. Экстремальные задачи с d.c. ограничениями, простейшая из которых имеет следующий вид:

V?(x) | min, ж <Е 5, F(x) > 0, (0.0.8) где F(x) = f(x) — д(х), х € П, а /(•), д(-) являются выпуклыми функциями на выпуклом открытом множестве Q С содержащем множество S, <р(-) — непрерывная функция на Rn.

Нетрудно видеть, что при д(х) = 0 задача d.c. максимизации (0.0.7) обращается в задачу выпуклой максимизации (0.0.5), так что последняя является частным случаем (0.0.7). Аналогично задача с d.c. ограничениями (0.0.8) при /(ж) = 0 обращается в задачу (0.0.б) на дополнении выпуклого множества, которая, таким образом, оказывается частным случаем (0.0.8). Итак, можно сказать, что простейшие задачи d.c. программирования (0.0.7) и (0.0.8) согласно предложенной классификации являются основными.

Заметим, что любая невыпуклая экстремальная квадратичная задача (т.е. задача, в которой целевая функция и функции, задающие ограничения типа равенств и неравенств, являются квадратичными) может быть отнесена к одному из вышеперечисленных классов, поскольку любая квадратичная функция в зависимости от знаков своих собственных значений является либо выпуклой, либо вогнутой, либо d.c. функцией. Таким образом, можно сказать, что приведенная классификация является исчерпывающей на классе невыпуклых квадратичных задач оптимизации. Более того, задачи с d.c. структурой играют важную роль в невыпуклой оптимизации как с теоретической точки зрения, так и ввиду огромного количества приложений.

Пионером в изучении свойств d.c. функций является А.Д. Александров [1,2]. Этой проблемой также занимались Е.М. Ландис [38] и П. Хартман [97]. Некоторые более поздние работы по d.c. структурам можно найти в [100, 104, 131, 143, 145].

Что касается общепринятых методов решения задач d.c. программирования, как уже говорилось, они пришли из дискретной оптимизации и совершенно не учитывают специфику и структуру задачи. Другой подход к решению подобных задач был развит в работах А.С. Стрекаловского. На основе предложенных условий глобальной оптимальности для четырех приведенных выше классов задач [71], [74]—[78], им и его учениками были разработаны стратегии глобального поиска для решения многих актуальных теоретических и прикладных задач оптимизации [37, 72, 73, 79, 80]. Особо следует отметить работы А.А. Кузнецовой по решению NP-трудной задачи дискретной оптимизации — поиск максимальной клики в неориентированном графе [112], а также работу Т.В. Яковлевой по решению задач об одномерном и многомерном рюкзаках [82].

Настоящая диссертационная работа посвящена поиску ситуаций равновесия по

Нэшу в биматричных играх, который основан на равносильности задачи поиска равновесия и решения невыпуклой задачи d.c. максимизации. Актуальность данного направления исследований определяется необходимостью разработки математического аппарата поиска равновесных ситуаций, а также решения игровых задач посредством методов невыпуклой оптимизации с исследованием их сходимости и численной проверкой их эффективности. Опишем подробно содержание работы.

Диссертация состоит из введения, трех глав, заключения и приложения. В каждой главе используется своя нумерация параграфов, предложений, лемм, теорем, замечаний и формул.

Основные результаты, полученные в работе, заключаются в следующем:

1. Предложена новая модификация стратегии глобального поиска ситуаций равновесия в биматричной игре на основе вариационного подхода. На базе этой стратегии разработан оригинальный алгоритм отыскания таких ситуаций. Обоснованы все этапы нахождения глобального решения экстремальной задачи.

2. Предложена модификация метода Б.М. Мухамедиева для отыскания критической точки в билинейной задаче. Доказана ее сходимость, изучены свойства критической точки при приближенном решении вспомогательных задач.

3. Разработан программный комплекс для поиска ситуаций равновесия в биматричных играх, эффективность которого доказана вычислительным экспериментом.

Разработанный программный комплекс поиска ситуаций равновесия по Нэшу в биматричных играх может использоваться для решения проблем системного анализа и исследования операций, в частности, для решения широкого круга прикладных задач экономического (например, при исследовании рынка с несовершенной конкуренцией — олигополии) и экологического характера. Алгоритм, построенный на базе теоретических исследований и лежащий в основе данного комплекса, открывает возможности для разработки новых методов поиска равновесий в более широких классах игр, а также для численного решения задач, имеющих важные практические приложения как в экологии, так и в экономике (например, в задачах иерархического управления).

Заключение

В диссертационной работе произведена реализация вариационного подхода к поиску ситуаций равновесия в биматричных играх.

В первой главе работы представлен обзор некоторых подходов к решению биматричных игр и основы решения задач d.c. максимизации.

Во второй главе разработана новая теоретическая база решения биматричных игр. С одной стороны, она основана на равносильности задачи поиска точки равновесия по Нэшу и решения билинейной невыпуклой задачи оптимизации, с другой — базируется на теории условий глобального экстремума А.С.Стрекаловского и вытекающих из нее стратегиях глобального поиска. Этот подход является новым и оригинальным.

Последовательно, начиная с формулировки условий оптимальности, описываются все этапы глобального поиска решения в упомянутой невыпуклой билинейной задаче.

В третьей главе проведено обширное тестирование предложенной методики на достаточно большом спектре биматричных игр и дан подробный анализ всех численных экспериментов. Результаты численного эксперимента свидетельствуют об эффективности этой методики решения биматричных игр. Кроме того, представленный подход не обладает многими недостатками метода Лемке-Хаусона поиска ситуации равновесия в биматричной игре.

1. Александров А.Д. О поверхностях, представимых разностью выпуклых функции/Известия Академии Наук Казахской ССР. — 1949. — Серия математики и механики. — Вып.З. — С.3-20.

2. Александров А.Д. Поверхности, представимые разностями выпуклых функций // Доклады Академии Наук СССР. — 1950. — Т.72, №4. — С.613-616.

3. Алексеев В.М., Тихомиров В.М., Фомин С.В. Оптимальное управление. — М.: Наука, 1979. — 432 с.

4. Антипин А.С. О неградиентных методах оптимизации седловых функций // Вопросы кибернетики. Методы и алгоритмы анализа больших систем. — М.:АН СССР, 1987. — С.4-13.

5. Антипин А.С. Управляемые проксимальные дифференциальные системы для решения седловых задач // Дифференциальные уравнения. — 1992. — Т.28, №11.1. С.1846-1861.

6. Антипин А.С. Равновесное программирование: проксимальные методы // Журн. вычисл. матем. и матем. физики. — 1997. — Т.37, №11. — С. 13271339.

7. Антипин А.С. Методы решения вариационных неравенств со связанными ограничениями // Журн. вычисл. матем. и матем. физики. — 2000. — Т.40, № 9.1. С.1291-1307.

8. Антипин А.С. Градиентный и экстраградиентный подходы в билинейном равновесном программировании. — М.:ВЦ СО РАН, 2002.

9. Ашманов С.А. Линейное программирование. — М.: Наука, 1981. — 304 с.

10. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. — М.: Мир, 1982. — 583 с.

11. Безруков А.Б., Саитгараев С.С. Прикладная теория игр. Учебное пособие. — Челябинск: Изд-во Челябинского Госуниверситета, 2001. — 128 с.

12. Бердникова Е.А., Еремин И.И., Попов Л.Д. Распределенные фейеровские процессы для систем линейных неравенств и задач линейного программирования // Автоматика и телемеханика. — 2004. — №2. — С.16-32.

13. Бертсекас Д. Условная оптимизация и методы множителей Лагранжа. — М.: Радио и связь, 1987.

14. Васильев О.В. Лекции по методам оптимизации. — Иркутск: Изд-во Иркут. унта, 1994. — 344 с.

15. Васильев Ф.П. Методы оптимизации. — М.: Факториал Пресс, 2002.

16. Васильев Ф.П. Численные методы решения экстремальных задач. — М.: Наука, 1988. — 552 с.

17. Васильев Ф.П., Антипин А.С. Метод стабилизации для решения задач равновесного программирования с неточно заданным множеством // Журн. вычисл. матем. и матем. физики. — 1999. — Т.39, №11. — С. 1779-1786.

18. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. — М.: Факториал, 1998.

19. Воробьев Н.Н. Бескоалиционные игры. — М.: Наука, 1984.

20. Воробьев Н.Н. Ситуации равновесия в биматричных играх // Теория вероятностей и ее применения. — 1958. — 3 — С.318-331.

21. Воробьев Н.Н. Теория игр для экономистов и кибернетиков. — М.: Наука, 1985.

22. Габасов Р.Ф., Кириллова Ф.М. Методы оптимизации. — Минск: Изд-во БГУ, 1981. — 352 с.

23. Гермейер 10.Б. Введение в теорию исследования операций. — М.: Наука, 1976.

24. Гермейер Ю.Б. Игры с непротивоположными интересами. Теория принятия решения при неполном единстве. — М.: МГУ, 1972. — 183 с.

25. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985.509 с.

26. Горелик В.А., Кононенко А.Ф. Теоретико-игровые модели принятия решений в эколого-экономических системах. — М.: Радио и связь, 1982.

27. Давыдов Э.Г. Исследование операций. — М.: Высшая школа, 1990.

28. Даугавет В.А., Салих Т.М. О методе дополнительного базиса для задач выпуклого квадратичного программирования. // Журн. вычисл. матем. и матем. физики. — 1992. — Т.32, №12. — С.1981-1992.

29. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. — Новосибирск: Изд-во Новосибирского ун-та, 1996.

30. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. — М.: Наука, 1976. — 192 с.

31. Зангвилл И. Нелинейное программирование. Единый подход. — М.: Советское радио, 1973. — 312 с.

32. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. — М.: Наука, 1974.480 с.

33. Карлин С. Математические методы в теории игр, программировании и экономике. — М.: Мир, 1964.

34. Карманов В.Г. Математическое программирование. — М.: Наука, 1986. — 288 с.

35. Касинская Л.И. Алгоритм и программа решения общей задачи выпуклого программирования методом опорного конуса. — В кн.: Алгоритмы и программы. Вып. 1. — Иркутск, 1974.

36. Кузнецова А.А., Стрекаловский А.С., Цэвээндорж И. Об одном подходе к решению целочисленных задач оптимизации // Журн. вычисл. матем. и матем. физики. — 1999. — Т.39, № 1. — С.9-16.

37. Ландис Е.М. О функциях, представимых в виде разности двух выпуклых // Доклады Академии Наук СССР. — 1951. — Т.80, №1. — С.9-11.

38. Мину М. Математическое программирование. Теория и алгоритмы. — М.: Наука, 1990. — 488 с.

39. Мухамедиев Б.М. О решении задачи билинейного программирования и отыскании всех ситуаций равновесия в биматричных играх // Журн. вычисл. матем. и матем. физики. — 1978. — Т.18, №2. — С.351-359.

40. Нейман Дж., фон, Моргенштерн О., Теория игр и экономическое поведение. — М.: Наука, 1970.

41. Орлов А.В., Стрекаловский А.С. Поиск глобального решения в задаче выпуклой максимизации // Оптимизация. Управление. Интеллект. — 2000. — №5. — С.306-315.

42. Орлов А.В. Численное решение задач выпуклой максимизации // Тезисы докладов I школы-семинара молодых ученых "Математическое моделирование и информационные технологии" (12-17 октября 2001 г., Иркутск-Аршан). — Иркутск: ИДСТУ СО РАН, 2001. — С.14-15.

43. Орлов А.В. Один подход к решению биматричных игр // Материалы Российской конференции "Дискретный анализ и исследование операций", (24 июня-28 июня 2002 г., Новосибирск). — Новосибирск: Изд-во Института математики, 2002. — С.194.

44. Орлов А.В. О решении биматричных игр // Тезисы докладов II школы-семинара молодых ученых "Математическое моделирование и информационные технологии" (25-29 сентября 2002 г., Иркутск-Ангасолка). — Иркутск: ИДСТУ СО РАН,2002. — С.25-26.

45. Орлов А.В. О поиске равновесия в биматричных играх // Тезисы докладов конференции "Ляпуновские чтения и презентация информационных технологий" (25-27 ноября 2002 г., Иркутск). — Иркутск: ИДСТУ СО РАН, 2002. — С.29.

46. Орлов А.В. Алгоритм поиска точки равновесия по Нэшу в биматричных играх и его реализация // Материалы Всероссийской научной молодежной конференции "Под знаком Сигма". — Омск, 2003. — С. 13-14.

47. Орлов А.В. Алгоритм поиска точки равновесия по Нэшу в биматричных играх и его реализация // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения" (1-5 июля 2003 г., Омск). — Омск, 2003. — С.134.

48. Орлов А.В. О локальном поиске при решении биматричной игры // Тезисы докладов Всероссийской конференции "Алгоритмический анализ неустойчивых задач" (2-6 февраля 2004 г., Екатеринбург). — Екатеринбург: Изд-во Уральского университета, 2004. — С.289-290.

49. Орлов А.В. О решении биматричных игр с квадратными матрицами // Тезисы докладов IV школы-семинара молодых ученых "Математическоемоделирование и информационные технологии" (14-20 марта 2004 г., Иркутск-Ангасолка). — Иркутск: ИДСТУ СО РАН, 2004, с.25.

50. Орлов А.В., Стрекаловский А.С. О поиске ситуаций равновесия в биматричных играх // Автоматика и телемеханика. — 2004. — №2. — С.55-68.

51. Оуэн Г. Теория игр. — М.: Наука, 1971.

52. Партхасаратхи Т., Рагхаван Т. Некоторые вопросы теории игр двух лиц. — М.: Мир, 1974. — 296 с.

53. Полак Э. Численные методы оптимизации. Единый подход. — М.: Мир, 1974. — 376 с.

54. Поляк Б.Т. Введение в оптимизацию. — М.: Наука, 1983. — 384 с.

55. Петросян JI.A. Принципы оптимальности в многошаговых играх // Соросовский образовательный журнал. Математика. — 1996. — №10. — С.120-125.

56. Петросян JI.A., Зенкевич Н.А., Семина Е.А. Теория игр. — М.: Высшая школа, 1998. — 304 с.

57. Петросян JI.А., Кузютин Д.В. Игры в развернутой форме: оптимальность и устойчивость. — СпБ.: Изд-во Санкт-Петербургского университета, 2000.

58. Протасов И.Д. Теория игр и исследование операций. — М.: Гелиос АРВ, 2003.

59. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. — М.: Наука, 1980.320 с.

60. Пшеничный Б.Н. Метод линеаризации. — М.: Наука, 1983. — 136 с.

61. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах.1. М. Наука, 1975. — 320 с.

62. Рокафеллар Р. Выпуклый анализ. — М.: Мир, 1973. — 472 с.

63. Розанова Н.М., Авдашева С.Б. Теория организации отраслевых рынков. Учебник. — М.: ИЧП изд-во Магистр, 1998. — 320 с.

64. Стрекаловский А.С. Введение в теорию игр. Учебное пособие. — Иркутск: Изд-во ИГУ, 2003. — 124 с.

65. Стрекаловский А.С. Минимизация разности двух выпуклых функций // Иркутский государственный университет, серия: Оптимизация и управление. — Иркутск: Изд-во ИГУ, 2002. — Вып.5. — 52 с.

66. Стрекаловский А.С. О минимизации разности двух выпуклых функций на допустимом множестве // Журнал вычисл. матем. и матем. физики. — 2003. — Т.43, №3. — С.399-409.

67. Стрекаловский А.С. О поиске глобального максимума выпуклого функционала на допустимом множестве // Журнал вычисл. матем. и матем. физики. — 1993.1. Т.ЗЗ, №3. — С.349-364.

68. Стрекаловский А.С. Об экстремальных задачах с d.c. ограничениями // Журнал вычисл. матем. и матем. физики. — 2001. — Т.41, №12. — С.1833-1843.

69. Стрекаловский А.С. Теоретические основы выпуклой максимизации // Иркутский государственный университет, серия: Оптимизация и управление. — Иркутск: Изд-во ИГУ, 2001. — Вып.4. — 48 с.

70. Стрекаловский А.С. Теория и методы d.c. программирования // Информационный бюллетень Ассоциации матем.программирования. Приоритетные результаты в области матем.программирования. Ч. 1. — Екатеринбург: УрО РАН, 2001. — № 9. — С. 133-137.

71. Стрекаловский А.С. Условия глобальной оптимальности в задачах d.c. программирования // Иркутский государственный университет, серия: Оптимизация и управление. — Иркутск: Изд-во ИГУ, 1997. — Вып.1. — 64 с.

72. Стрекаловский А.С. Элементы невыпуклой оптимизации. — Новосибирск: Наука, 2003. — 352 с.

73. Стрекаловский А.С., Кузнецова А.А. О сходимости алгоритма глобального поиска в задаче выпуклой максимизации на допустимом множестве // Известия высших учебных заведений. Математика. — 1999. — №12.

74. Стрекаловский А.С., Кузнецова А.А., Яковлева Т.В. О численном решении задач невыпуклой оптимизации // Сибирский журн. вычисл. матем. — 2001. — Т.4, №2. — С. 185-199.

75. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. — М.: Наука, 1986. — 328 с.

76. Яковлева Т.В. Поиск глобального решения в задачах обратно-выпуклого программирования: Дис. на соискание уч. степ. канд. физ.-мат. наук. — Иркутск, 2003. — 145 с.

77. Aggarwal V. On the generation of all equilibrium points for bimatrix games through the Lemke-Howson algorithm // Mathematical programing. — 1973. — 4. — P.233-234.

78. Aumann R.J. Acceptable points in general cooperative n-person games // Contributions to the Theory of Games IV. Princeton: Princeton University Press, 1959. P.287-324.

79. Audet С., Hansen P., Jaumard B. and Savard G. Complete Enumeration of Equilibria for Two-Person Games in Strategic and Sequence Forms // Les Cahiers du GERAD G-98-59. — Montreal, 1998.

80. Balinski M.L. An algorithm for finding all vertices of convex polyhedral sets // Journal of the Society for Industrial and Applied Mathematics. — 1961. — 9. — P. 72-88.

81. Bastian M. Another note on bimatrix games // Mathematical programing. — 1976.11. — P.299-300.

82. Borm P.E., Jansen M.J.M., Potters J.A.M., Tijs S.H. Pareto equilibria for bimatrix games // Computers and mathematics with applications. — 1993. — V.25. — P.19-25.

83. Carlton D., Perloff J. Modern industrial organization. — Longman Science & Technology, 1999.

84. Dickhaut J. and Kaplan T. A program for finding Nash equilibria // The Mathematica Journal. — 1991. — № 1. — P.87-93.

85. Eaves B.C. The linear complemntarity problem // Management science. — 1971.1. V.17. — P.612-634.

86. Elzen van den A.H., Talman J.J. A procedure for finding Nash equilibria in bimatrix games // ZOR-methods and models of operation research. — 1991. — V.35. — P.27-43.

87. Gallo G., Ulkucu A. Bilinear programming: an exact algorithm // Mathematical programming. — 1977. — 12. — P.173-194.

88. Gibbons R. Game Theory for Applied Economists. — Princeton University Press, 1992.

89. Handbook of Game Theory/Ed.by R.J.Aumann and S.Hart. — 2002. — V.3.

90. Handbook of global optimization/Ed. by Horst. R., Pardalos P. — Dordrecht: Kluwer Academic Publishers, 1995.

91. Hartman P. On Functions Representable as a Difference of Convex functions // Pacific Journal of Mathematics. — 1959. — V.9 — P.707-713.

92. Heuer G.A. On completely mixed strategies in bimatrix games // The journal of the London Mathematical Society. — 1975. — 11. — P.17-20.

93. Heuer G.A. Uniqueness of equilibrium points in bimatrix games // International Journal of Game Theory. — 1979. — V.8, № 1. — P.13-25.

94. Hiriart-Urruty J.B. Generalized Differentiability, Duality and Optimization for Problem Dealing with differences of convex functions // Lecture Notes in Economics and Mathematical Systems. — Berlin: Springer Verlag, 1985. — V.256. — P.37-69.

95. Hiriart-Urruty J.B., Lemarshal C. Convex Analysis and Minimization Algorithms. — Berlin: Springer Verlag, 1993. — 1-2.

96. Horst R., Tuy H. Global Optimization. Deterministic Approaches. — Berlin: Springer-Verlag, 1993. — 698 p.

97. Horst R., Pardalos P., Thoai N.V. Introduction to global optimization. — Dordrecht-Boston-London: Kluwer Academic Publishers, 1995. — V.3. — 246 p.

98. Horst R., Thoai N. V. D.C. Programming: Overview // Journal of Optimization Theory and Applications. — 1999. — V.103, №1. — P. 1-43.

99. Isaacson K, Millham C.B. On a class of Nash-solvable bimatrix games and some related Nash subsets // Naval research logistics quarterly. — 1980. — 27. — P.407-412.

100. Jansen M. On the set of proper equilibria of a bimatrix game // International journal of game theory. — 1993. — V.22. — P.97-106.

101. Jansen M., Jurg A., Vermeulen A. On the set of equilibria of a bimatrix game. A survey //Chapters in Game Theory, in honor of Stef Tijs/Ed. by Borm P., Peters H. — Kluwer Academic Publishers, 2002. — P. 121-142.

102. Kohlberg E. Refinements of Nash equilibrium: The main Ideas // Game Theory and applications/Ed. by Ichiishi Т., Neyman A., Tauman Y. — San Diego Academic Press, 1990. — P.3-45.

103. Kreps D. Game Theory and Economic Modelling. Clarendon Lectures on Economics.

104. Oxford University Press, 1990.

105. Krohn I., Molizahn S., Rosenmuller J., Sudholter P., Wallmeier H.M. Implementing the modified Lemke-Howson algorithm // Applied math, and computation. — 1991.1. V.45. — P.31-72.

106. Kuhn H.W. An algorithm for equilibrium points in bimatrix games // Proc. Nat. Acad. Sci. USA. — 1961. — V.47. — P.1657-1662.

107. Kuznetsova A.A., Strekalovsky A.S. On solving the maximum clique problem // Journal of Global Optimization. — 2001. — V.21, №3. — P.265-288.

108. Lee K.-H., Baldick R. Tuning of discretization in bimatrix game approach to power system market analysis // IEEE preprint, 2002. — №8, PE-019PRS.

109. Lemke C.E. Bimatrix equilibrium points and mathematical programming // Management science. — 1965. — V. 11, №7. — P.681-689.

110. Lemke C.E., Howson J.J. Equilibrium points of bimatrix games // Journal of the Society for Industrial and Applied Mathematics. — 1964. — 12. — P.413-423.

111. Lucas W.F. An overview of the mathematical theory of games // Management science. — V.18, Appendix P. — P.3-19.

112. Luce R.D., Raiffa H. Games and decisions. — New York: John Whiley and Sons, 1957.

113. Luo Z.Q., Pang J.S., Ralph D. Mathematical programs with equilibrium constraints.

114. New York: Cambridge Univ. Press, 1996.

115. Mangasarian O.L. Equilibrium points in bimatrix games // Journal of the Society for Industrial and Applied Mathematics. — 1964. — 12. — P.778-780.

116. Mangasarian O.L., Stone H. Two-person nonzero games and quadratic programming // Journal of mathematical analisis and applications. — 1964. — №9. — P.348-355.

117. McKelvey R.D. and McLennan A. Computation of equilibria in finite games // Handbook of Computational Economics/Ed. by Amman H.M., Ivendrick D.A. and Rust J. — Amsterdam: Elseivier — 1996. — V.l — P.87-142.

118. Mills H. Equilibrium points in finite games // Journal of the Society for Industrial and Applied Mathematics. — 1960. — V.8, №2. — P.397-402.

119. Millham C.B. On the structure of equilibrium points in bimatrix games // SIAM review. — 1968. — V.10, №4. — P.447-448.

120. Millham C.B. On Nash subsets of bimatrix games // Naval research logistic quarterly. — 1974. — V.74. — P.307-317.

121. Myerson R.B. Refinements of the Nash equilibrium concept // International journal of game theory. — 1978. — V.7, №2. — P.73-80.

122. Nash J.F. Equilibrium points in n-person games // Proc. Nat. Acad. Sci. USA. — 1950. — V.36. — P.48-49.

123. Nash J.F. Noncooperative games // Annals of mathematics. — 1951. — V.54. — P.286-295.

124. Nikaido H., Isoda K. Note on noncooperative convex games // Pacific Journal of Mathematics. — 1955. — 5. — P.807-815.

125. Orlov A.V. On a solving of bimatrix games // The International Conference on Optimization and Optimal Control (August 13-17, 2002, Mongolia, Ulaanbaatar).

126. Ulaanbaatar, 2002. — P. 134-135.

127. Osborne M.J., Rubinstein A. A course in game theory. — London, Cambridge: The MIT PRESS, 1996.

128. Penot J.-P., Bougeard M.L. Approximation and decomposition properties of some classes of locally d.c. functions // Mathematical Programming. — 1988. — V.41.1. P. 195-227.

129. Raghavan T.E.S. Completely mixed strategies in bimatrix games // The Journal of the London mathematical Society. — 1970. — №2. — P.709-712. •

130. Raghavan T.E.S. Non zero-sum two person games // Handbook of Game Theory/Ed.by R.J.Aumann and S.Hart. — 2002. — V.3.

131. Rosen J.B. Existence and uniqueness of equilibrium points for concave N-person games // Econometrica. — 1965. — V.33, №3. — P.520-534.

132. Savani R., Stengel B. Long Lemke-Howson Paths // CDAM Research Report LSE-CDAM-2003-14.

133. Selten R. Reexamination of the perfectness concept for equilibrium points in extensive games // International Journal of Game Theory. — 1975. — V.4, № 1. — P.25-55.

134. Shapley L.S. A note on the Lemke-Howson algorithm // Mathematical programming study. — 1974. — 1. — P.174-189.

135. Stengel B.V. Computing equilibria for two person games // Handbook of Game Theory/Ed. by R.J.Aumann and S.Hart. — 2002. — V.3.

136. Strekalovsky A.S. Global Optimality Conditions for Nonconvex Optimization // Journal of global optimization. — 1998. — № 12. — P.415-434.

137. Strekalovsky A.S. On d.c. Minimization Problems // Оптимизация. Управление. Интеллект. — 2000. — №5. C.392-402.

138. Strekalovsky A.S., Tsevendorj I. Testing the 3?-strategy for a Reverse Convex Problem // Journal of global optimization. — 1998. — V.13". — P.61-74.

139. Thach P.T. D.C. sets, d.c. functions and nonlinear equations. // Mathematical Programming. — 1993. — V.58. — P.415-428.

140. Todd M.J. Bimatrix games. An appendum // Mathematical programming. — 1978.14. — P.112-115.

141. Tuy H. D. C. Optimization: Theory, Methods and Algorithms // Handbook of Global Optimization/Ed. by Horst. R., Pardalos P. — Dordrecht: Kluwer Academic Publishers, 1995. — P.149-216.

142. Quintas L.G. A note on polymatrix games // International journal of game theory.1989. — V.18. — P.261-272.

143. Vaish H., Shetty C.M. The bilinear programming problem // Naval research logistics quarterly. — 1976. — 23. — P.303-309.

144. Van Damme E. Refinements of Nash equilibrium // Advances in economic theory/Ed. by Laffont J.J. — London: Cambridge University Press. — 1992. — P.32-75.

145. Van Damme E. Stability and perfection of Nash equilibria. — Berlin-New-York: Springer-Verlag, 1996.

146. Vermeulen A.J., Jansen M.J.M. On the set of perfect equilibria of bimatrix games // Naval research logistics quarterly. — 1994. — V.41. — P.295-302.

147. Wilson R. Computing equilibria of two-person games from the extensive form // Management science. — 1972. — V.18, №7. — P.448-460.

148. Winkels H.M. An algorithm to determine all equilibrium points in bimatrix game // Game Theory and related topics/Ed. by Moeschlin O. and Pallaschke D. — Amsterdam-New-York-Oxford: North-Holland Publishing Company. — 1979. — P.137-148.