Многоагентные системы

Магистратура 2018/2019

Статус: Курс по выбору (Анализ больших данных в бизнесе, экономике и обществе)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Департамент математики

Где читается: Санкт-Петербургская школа физико-математических и компьютерных наук

Когда читается: 1-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Новиков Борис Асенович

Прогр. обучения: Анализ больших данных в бизнесе, экономике и обществе

Язык: русский

Кредиты: 4

Контактные часы: 64

Полная версия программы учебной дисциплины

Аннотация

Целью освоения дисциплины «Многоагентные системы» является формирование у студентов теоретических знаний и практических навыков обучения многоагентных систем. В результате изучения этой дисциплины студенты будут владеть теоретическими основами алгоритмов для обучения многоагентных систем, иметь практические навыки в создании алгоритмов обучения, методов и библиотек для обучения многоагентных систем. В рамках дисциплины изучаются такие разделы, как "Распределенные системы", "Многоагентные системы в теории игр", " Введение в обучение с подкреплением для многоагентных систем", "Протоколы для стратегий агентов. Дизайн механизмов" и "Команды эгоистичных агентов. Коалиции в теории игр".

Цель освоения дисциплины

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

Планируемые результаты обучения

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

Содержание учебной дисциплины

Распределенные системы.
Распределенные ограничения. Определение распределенных ограничений. Ограничения на домен. Эвристические алгоритмы поиска: асинхронный алгоритм обратного прохода. Задача четырех ферзей. Распределенная оптимизация. Распределенное динамическое программирование для нахождения оптимального пути. Асинхронное динамическое программирование. A* в реальном времени. Выбор действия для многоагентных марковских процессов принятия решений. Оптимизация аукционов.
Многоагентные системы в теории игр
Некооперативные игры. Эгоистичные агенты. Игры в нормальной форме. Определение игры в нормальной форме. Примеры игр в нормальной форме. Стратегии в играх в нормальной форме. Равновесие в играх. Оптимальность по Парето. Равновесие Нэша. Нахождение равновесия Нэша. Теорема Нэша: доказательство существования равновесия Нэша. Стратегии в играх в нормальной форме. Минимакс и максимин стратегии. Удаление доминируемых стратегий. Коррелированное равновесие. Эпсилон-Нэш равновесие.Вычисление решений для игр в нормальной форме. Вычисление равновесия Нэша в играх для двух игроков с нулевой суммой. Вычисление равновесия Нэша в некооперативных играх для двух игроков, n игроков. Сложность вычисления равновесия Нэша. Вычисление максимин и минимакс стратегий в играх для двух игроков. Определение доминируемых стратегий. Доминирование чистой стратегией. Доминирование смешанной стратегией.
Введение в обучение с подкреплением для многоагентных систем.
Обучение с подкреплением. Обучение с подкреплением в стохастических играх с нулевой суммой. Обучение с подкреплением в стохастических играх общего вида. Вероятностное обучение с подкреплением. Нацеленное обучение. Эволюционное обучение.
Протоколы для стратегий агентов. Дизайн механизмов.
Дизайн механизмов с неограниченными предпочтениями. Квазилинейные предпочтения. Дизайн механизмов в квазилинейной постановке. Эффективные механизмы. Механизм VCG. VCG и слабый баланс бюджета. Недостатки VCG. Баланс бюджета и эффективность. Механизм AGV. Применения дизайна механизмов в вычислительных системах. Создание расписания задач. Назначение пропускной способности в компьютерных сетях.
Команды эгоистичных агентов. Коалиции в теории игр.
Коалиционные игры – определение и примеры. Классы коалиционных игр. Анализ коалиционных игр. Вектор Шепли. Ядро. Компактные представления коалиционных игр. Игры со взвешенным большинством и игры со взвешенным голосованием. Взвешенные игры на графах. Нахождение синергий: представление в супераддитивных играх. Декомпозиционный подход.

Элементы контроля

Домашнее задание 1
Домашнее задание 2
Домашнее задание 3
Экзамен

Промежуточная аттестация

Промежуточная аттестация (4 модуль)
0.167 * Домашнее задание 1 + 0.166 * Домашнее задание 2 + 0.167 * Домашнее задание 3 + 0.5 * Экзамен

Программа дисциплины