Кооперативная теория игр и теория паросочетаний - Лекция 1 часть 1

Денис Соколов, ФКН, Boston College Теория игр использует математические методы в изучении взаимодействия двух и более агентов (например экономических) в тех случаях, когда выбранные ими стратегии влияют на конечный результат этого взаимодействия. Эта дисциплина “родилась” в 1944 году в Принстоне после публикации классической книги Джона фон Неймана и Оскара Моргенштерна “Теория игр и экономическое поведение”. В этом исследовании авторы разделили общую теорию игр (ТИ) на две подтемы: некооперативную и кооперативную ТИ. Основное отличие первой подтемы от второй состояло в том, что в не кооперативной ТИ игрокам запрещается “сговариваться” (каждый преследует сугубо личные интересы), в то время как в кооперативной ТИ все наоборот: исход игры определяется тем, на какие коалиции разобьются участники игры. Хотя мотивация для разделения и была благородной (упростить модели кооперации двух и более игроков), в результате, в силу своей абстрактности, кооперативная ТИ уже на протяжении десятков лет является намного менее популярным направлением, чем ее “старшая сестра”. Однако в рамках этой теории было получено множество интересных, красивых и важных результатов, часть из которых мы рассмотрим на первой лекции мини-курса. Более того, некоторые идеи и концепции кооперативной теории игр (честность, стабильность, ядро и т.д.) были положены в фундамент бурно развивающейся по сей день “теории паросочетаний”. Эта дисциплина изучает наиболее эффективные сочетания агентов с агентами или агентов с объектами в рамках заданной модели. На второй лекции будут представлены модель “Марьяжа” или задача о парах мужчина-женщина (marriage problem), а также задача распределения студентов по университетам (school choice). Наконец, на последней лекции мы поговорим о задаче распределения неделимых объектов (house allocation) и проблеме построения эффективного механизма пересадки почек (kidney exchange).