Условия сходимости итеративных процессов в повторяющихся играх

ОГЛАВЛЕНИЕ
Введение..................и...................................... и...............4
Гдана I. Условия сходимости итерационного метода Брауна-Робинсон для биматричных игр.
1. Постановка проблемы...............................................................8
2. Определение игрового процесса ..................................................10
3. Игра двух лиц с нулевой суммой...................................................13
4. Теорема сходимости...............................................................14
5. Построение игрового процесса для биматричных игр.................................15
6. Условия сходимости игровых процессов для биматричных игр.........................22
7. Условия сходимости для биматричных игр, получаемые за счет эквивалентного преобразования бнматричной игры...................................................27
8. Рстулыаты........................................................................34
Глава II. Модели адаптивно-подражательного поведения .............................. 35
1. Постановка проблемы..............................................................35
2. Основные понятия и определения...................................................40
2.1. Популяционная игра и статические принципы оптимальности.....................40
2.2. Устойчивость решений модели динамики........................................44
2.3. Модель динамики репликаторов................................................45
2.4. Модель адаптивно-подражательного поведения..................................48
3. Связь статических принципов оптимальности с устойчивостью решений динамики МАПП..............................................................................54
2
лава III. Устойчивость смешанных равновесий модели адаптивно-
олражатсльного поведения ........................................... .............. 64
1. Постановка проблемы...............................................................64
2. Основные понятия и определения....................................................65
3. Связь статических принципов оптимальности с устойчивостью решений МАШ1............67
4. Исследование устойчивости смешанных равновесий....................................68
:рн ложен не. Устойчивость эффективных исходов в повторяющихся играх.................76
1. Постановка проблемы...............................................................76
2. Основные определения..............................................................81
3. Верхняя оценка необходимой величины залога........................................84
—--------------—---------------------——— ..............................мш91
итератора 93
3
Введение.
Некооператнвная теория игр рассматривает принятие решений ы конфликтных ситуациях, в которых участники независимо выбирают свои стратегии поведения. Известно два основных принципа оптимальности, относящихся к таким ситуациям: равновесие Наша и решение но доминированию. я
Итеративные процессы описывают последовательное изменение стратегий участников в повторяющихся конфликтных ситуациях. Такие процессы можно рассматривать с двух точек зрения: во-первых, как численные методы поиска оптимальных стратегий; во-вторых, как модели поведения участников, которые пытаются улучшить свои стратегии на основе предыдущего опыта взаимодействия. В обоих случаях представляет интерес исследование асимптотики процесса и выяснение условий его сходимости к упомянутым оптимальным решениям итры. описывающей однократное взаимодействие.
Данная проблема рассматривалась рядом исследователей, начиная с работ Брауна а Робинсон [41], которые исследовали процесс так называемого фиктивного эазыгрывапня и доказали его сходимость к ссдловой точке атгтагоиистнческой игры. Обобщения этого результата получены в работах Беленького. Волконского и др. (4) и Антипина [1,21. В »и* указаны достаточные условия на функции выигрыша, при зыполненин которых указанный процесс, а также некоторые процессы градиентного гипа, сходпея к равновесию Нэша игры п лиц. Известен, однако, пример довольно тростой игры двух лиц. для которой процесс фиктивного разыгрывания не сходится 'Jordan 25].
4
Отметим, что упомянутые достаточные условия сходимости включают условие ыпуклосги агрегированной специальным способом функции выигрыша. Они формулированы таким обратом, что их проверка для нсантагоннстических игр даже в лучас двух лиц представляет самостоятельную проблему. Этой проблеме и посвящена ервая глава диссертации, в которой получено простое описание класса игр двух лиц, довлетворяющнх упомянутым условиям сходимости.
Рассматриваемые в Главе 1 процессы соотоетствуют случаю, когда игра овторяется с одним и тем же составом участников, каждый из которых оптимизирует вою Стратегию, исходя из предыдущих стратегий партеров. Другое направление сслсдований в данной области связано с моделями, в которых множество игроков дновремеино участвует в одинаковых конфликтных ситуациях. В каждый период артнеры выбираются случайным образом. Изменение распределения по стратегиям осит коллективный характер и основано на механизмах адаптации и подражания, [роцессы такого рода изучаются в рамках математической теории коллективного оведепия, известной также как эволюционная теория игр (см. (Опойцсв 35),
Засин 50,51,54], р^ейшН 57], [Красношеков 29]). В упомянутых работах исследованы гдельные адаптивно-подражательные механизмы. В ряде случаев выяснена связь их симптотического поведения с равновесиями Нэша и решениями по доминированию. В о же время вопрос об условиях сходимости для моделей адаптивно-подражательного оведепия общего вида не был изучен. Во второй главе настоящей работы »осматриваются различные способы выбора игроками альтернатов»!ых стратегий и их равнения с текущими стратегиями и найдены условия, при выполиешш которых ходимость к указанным решениям имеет место.
5
В Главе 3 исследуется проблема сходимости к равновесиям Нэша п смешанных стратегиях. Получены результаты об отсутствии сходимости к таким равновесиям для адаптивно-подражательных процессов определенного типа.
Приложение посвящено повторяющимся играм с полкой информацией и аддитивными функциями выигрыша. Состав игроков является постоянным и в отличие от предыдущих моделей каждый игрок стремится максимизировать свой суммарный выигрыш за данное число повторений. Для таких игр известен ряд результатов, получивших название «народных теорем». (См. работы (Лшпапп 3), [Васин 52,56] и др.). Их общее содержание состоит в том, что всякий индивидуально-рациональный исход однократной игры может быть реализован как решение повторяющейся шры. При этом рассматриваются различпые понятия решения: ог равновесия по Иэшу до наиболее сильного понятия - решения но доминированию. Последний вариант получен в работе |Васин 56] для повторяющейся игры с конечным временем и возмущенными функциями выигрыша. Показано, что за счет возмущения, не превышающего выигрыша в одном повторении, можно обеспечить превращение любою исхода, доминирующего некоторое равновесие Нэша, в исход, соответствующий решению по доминированию повторяющейся игры.
Однако, предложенная конструкция решения не годится, если желаемый исход не может быть реализован в одном повторении, а является результатом чередования различных ситуаций, выгодных разным участникам игры. Соответствующая модель и сс экономическая интерпретация изложены в Приложении. В этой модели возмущение функций выигрыша имеет следующий смысл. Предполагается, что игроки сами стремятся обеспечить устойчивость соглашения с помощью залогов, которые вносятся до начала игры, а потом возвращаются им. если они соблюдали заключенное соглашение. При этом
6
еитается задача, как обеспечить устойчивость соглашения о реализации желаемого схода при минимальной величине вносимых залогов.
Таким образом, в Главах 1,2,3 дано обоснование сходимости широкого круга тсративных процессов к точкам равновесия и решениям по доминированию, (риложение показывает, как за счет малого возмущения функций выигрыша можно бсспечнть соответствие решения по доминированию желательному исходу овторяющейся игры. В Заключении сформулированы основные результаты работы.
Основные результазы диссертации были опубликованы в статьях: [Богданов 8,9).
7