Александр Филатов «Мэтчинги»

Лекция 5 курса «Популярная экономика», прочитанная 22 октября 2020 года в Кавказском математическом центре АГУ Экономический империализм означает применение экономических (а на деле теоретико-игровых) методов к широкому кругу социальных проблем. Одной из таких проблем является задача о стабильных браках, или, как это любят называть теоретико-игровики, о «марьяжах». Представим себе высокогорное село, в котором проживает N парней и M девушек. Будем считать, что парень – есть профиль предпочтений на множестве девушек (эту люблю сильнее всех, эту меньше, эту еще меньше, а остальные вообще не нужны, лучше один останусь). Девушка – симметрично – профиль предпочтений на множестве парней. Главный на селе аксакал хочет перед своей смертью их всех переженить, причем так, чтобы никто не захотел разводиться. Это означает, что нужен алгоритм, дающий разбиение на пары, при котором нельзя, разбив и перемешав одну или две из них, сделать новую пару более счастливой. Задачу решили Дэвид Гейл и Ллойд Шепли в 1962 году.