Задача о марьяже или задача о стабильных браках — математическая задача из области кооперативных игр. Требуется найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. В более простой формулировке: составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругамАндрей Коняев. Давай поженимся. Нобелевскую премию по экономике дали за стабильность выбора // Lenta.ru 15.10.2012, 21:12:16. Решение задачи отмечено Нобелевской премией по экономике 2012 года.
Решение задачи было описано в 1962 году математиками Дэвидом Гэйлом и Ллойдом ШеплиD. Gale and L. S. Shapley: «College Admissions and the Stability of Marriage», American Mathematical Monthly 69, 9-14, 1962.. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гэйла — Шепли или «алгоритма отложенного согласия».
Множество практических механизмов на основе алгоритма Гэйла — Шепли разработал нобелевский лауреат Элвин Рот. Эти механизмы были внедрены в деятельность больниц по набору врачей и интернов, в правила многих американских профессиональных спортивных ассоциаций по набору спортсменов в команды. В соответствии с предложенными институциональными механизмами фирмы набирают на стажировку сотрудников, суды нанимают секретарей, родители находят подходящие школы для детей. Модель марьяжа в целом описывает последовательность действий индивидов при формировании пар на «рынках попутчиков» для совместных поездок, в некоторых видах спорта (парное фигурное катание, спортивные танцы), поведение участников в интерактивных реалити-шоу и пр.
Формулировка Задачу можно сформулировать следующим образом:
Пусть даны два множества M и Ж, причём для каждого элемента из М элементы из Ж отсортированы в некотором порядке. То есть мы можем говорить, какие элементы Ж для данного элемента m из М являются более предпочтительными, а какие менее. Сортировки, конечно же, для каждого элемента могут быть свои. Аналогичные предпочтения введены и для элементов из Ж. Суть задачи сводится к разбиению M и Ж на пары. В каждую пару берется по одному элементу из M и из Ж. При этом в результате мы должны получить не просто разбиение, а так называемое стабильное разбиение. Стабильность — общее понятие для теории игры, которое в данном конкретном случае означает, что отсутствуют пары (m, ж) и (m', ж'), обладающие таким свойством: для m элемент ж' является предпочтительнее ж, а для ж' элемент m является предпочтительнее m'.
Решение Существует конструктивный метод нахождения одного из решений задачи.
мужчины делают предложение наиболее предпочитаемой женщине; каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»; мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают; если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»; если женщине пришло наилучшее предложение, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «да» и далее предложений не принимает; шаги повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
Максимальное количество шагов для реализации алгоритма: шагов, где — число мужчин и женщин.
Свойства решения В результате невозможно завести новый брак — если у мужчины А в списке есть женщина Б и наоборот, хотя бы один женится. Соответственно, если списки полные, женятся все мужчины или выходят замуж все женщины.
Аналогично женщины могут ходить по мужчинам. Совпадают ли получившиеся браки? Не обязательно, и контрпример прост. Пусть есть два мужчины и две женщины. Андрей предпочитает Веру, Борис — Галю. Женщины наоборот — Вера Бориса, Галя Андрея (но и на другом жениться или выйти замуж за другого все четверо не прочь). Если мужчины ходят по женщинам — Андрей женится на Вере, Борис на Гале. Если женщины по мужчинам — Андрей на Гале, Борис на Вере.
При этом, если мужчины делают предложения женщинам, мужчины получат самый лучший для себя результат из всех устойчивых паросочетаний: не существует устойчивого паросочетания, чтобы все мужчины оказались в том же или лучшем положении. Мало того, алгоритм слабо стоек к мужским коалициям: несколько мужчин не могут скоординированно изменить списки предпочтения, чтобы путём эксплуатации этого алгоритма строго улучшить результат всем членам коалиции. Улучшить хотя бы одному и не ухудшить остальным коалиция иногда способна.
Для женщин результат, наоборот, будет наихудшим: не существует устойчивого паросочетания, чтобы все женщины оказались в том же или худшем положении. Алгоритм не стоек к женским коалициям: если в предыдущем примере Вера откажется от Андрея, а Галя от Бориса, женщины найдут себе оптимальную пару.
Подобные задачи обобщение на неравное число партнёров; задача о выборе учебного заведения (в одно заведение может поступить несколько студентов); задача о соседях по комнате — вместо двух множеств (мужчин и женщин) имеется только одно множество; когда среди врачей возникают браки, и супругам хочется работать в одной больнице.
Реализация в программировании Пример на языке Си:
#include"conio.h" #include"stdio.h"
int make_offer(int);
const int n = 5 + 1; // Для матрицы 5x5
int mass_index[n]; // Массив множества мужчин int mass_offer[n]; // Массив множества преложений женщин int massA[n][n], massB[n][n]; int global_i;
void main() { int i, j, offer, count, count_0 = 0;
for (i = 1; i < n; i++) { mass_index[i] = 1; mass_offer[i] = -1;
FILE* f = fopen("input.txt", "r"); for (i = 1; i < n; i++) for (j = 1; j < n; j++) fscanf(f, "%d", &massA[i][j]); for (i = 1; i < n; i++) for (j = 1; j < n; j++) fscanf(f, "%d", &massB[i][j]); fclose(f);
global_i = 1;
int x; while (count_0 != n-1) { x = make_offer(global_i); if (x == 0) { count_0++; global_i = count_0 + 1; } else global_i = x;
for (i = 1; i < n; i++) printf("%d - %d\n", i, mass_offer[i]); getch(); }
int make_offer(int count) { int offer = massA[count][mass_index[count]];
if (mass_offer[offer] == -1) { mass_offer[offer] = count; return 0;
for (int i = 1; i < n; i++) { if (massB[offer][i] == mass_offer[offer] || massB[offer][i] == count) { if (massB[offer][i] == mass_offer[offer]) { mass_index[count]++; return count;
int x = mass_offer[offer]; mass_index[mass_offer[offer]]++; mass_offer[offer] = count; return x;
См. также Задача о разборчивой невесте
Примечания
Литература
Ссылки Никита Калинин
Категория:Теория игр