Введение 3
Глава 1. Сетевые игры 5
Глава 2. Модель Лагераса и Зайна 7
2.1. Особенности игры 7
2.2. Ограничения на функцию выигрыша 8
2.3. Равновесие по Нэшу в чистых стратегиях 9
2.4. Пороговый граф 12
2.5. Многошаговая игра 15
Глава 3. Программная реализация модели Лагераса и Зайна 22
3.1. Формат представления данных 22
3.2. Реализованные функции 23
3.3. Примеры 27
Глава 4. Кооперативный вариант игры 32
4.1. Теоретико-игровая модель кооперативной игры 32
4.2. Проверка непустоты c-ядра 34
Список литературы 38
Приложение 39
Данная работа посвящена анализу моделей сетевых игр в динамике и процессу их формирования.
Andreas Lageras, David Seim [1] предлагают модель сетевой игры с одновременным и независимым выбором стратегий и этапом формирования сети.
Авторы накладывают условия на функцию выигрыша, обеспечивающие существование и единственность равновесия по Нэшу в чистых стратегиях для сетей общего вида. Далее рассматривается класс графов, называемых пороговыми графами. Общее множество сетей сужается до этого класса, что позволяет сделать некоторые качественные утверждения о ситуации равновесия. Для строгого описания и последующего применения сведений из теории графов были изучены материалы из учебных пособий [4], [5]. Примечательно то, что свойства пороговых графов согласуются с литературой по социологии. В заключительной части статьи рассматривается многошаговая игра, в ходе которой помимо выбора игроками стратегий, влияющих на функцию выигрыша, случайно выбранный игрок должен изменить структуру сети. Доказывается, что, во-первых, при эндогенном формировании сети класс пороговых графов является поглощаемым, т.е. сеть не сможет покинуть этот класс. Во- вторых, любая сеть, при вероятности формирования связи большей, чем некоторая наперед заданная величина ", сходится к пороговому графу с вероятностью единица.
В ходе данной работы был реализован программный алгоритм формирования сети по свойствам функции выигрыша, при которых игроки под действием внешнего процесса принимают решения об оптимальном создании или удалении связей.
Для некооперативного варианта игры доказана непустота c-ядра для игр на полных сетях. К сожалению, построить как само c-ядро, так и получить значения характеристической функции не представляется возможным из-за общего вида ограничений, накладываемых на функции выигрыша.
В результате проделанной работы была проанализирована модель сетевой игры Лагераса и Зайна с одновременным и независимым выбором стратегий и этапом формирования сети под действием внешнего случайного процесса, выбирающего игрока и соответствующее для него действие — добавить или удалить связь.
Была разработана программная реализация процесса формирования сети для любого количества игроков и любой начальной матрицы сопряженности сети. С ростом числа игроков и случайной начальной матрицей сопряженности скорость сходимости графа игры к классу пороговых графов закономерно снижалась. Однако при любом количестве игроков и начальном графе сети, принадлежащему к классу пороговых графов, граф уже не покидал этот класс. Это подтверждает выводы, сделанные в работе Лагераса и Зайна.
В конце работы был проведен анализ c-ядра кооперативной модели данной игры. Было установлено, что для игры на полном графе -ядро не пусто, а характеристическая функция супермодулярна.
В ходе дальнейшей работы планируется построить модели игр с другими методами формирования сети, исключающими внешний случайный процесс или уменьшающими его влияние на игру, тем самым позволяя игрокам взаимодействовать с меньшей долей неопределенности. Также интерес вызывает разработка кооперативных моделей многошаговых игр на основе этой модели, и их возможная визуализация и дальнейший анализ программным алгоритмом.
