Задача о марьяже

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Задача о марьяже — математическая задача из области кооперативных игр. Требуется найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. В более простой формулировке: составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам[1]. Решение задачи отмечено Нобелевской премией по экономике 2012 года.

Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly[2]. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия».

Множество практических механизмов на основе алгоритма Гейла-Шепли разработал нобелевский лауреат Элвин Рот.

Формулировка[править | править исходный текст]

Задачу можно сформулировать следующим образом:

Пусть даны два множества M и Ж, причем для каждого элемента из М элементы из Ж отсортированы в некотором порядке. То есть мы можем говорить, какие элементы Ж для данного элемента m из М являются более предпочтительными, а какие менее. Сортировки, конечно же, для каждого элемента могут быть свои. Аналогичные предпочтения введены и для элементов из Ж. Суть задачи сводится к разбиению M и Ж на пары. В каждую пару берется по одному элементу из M и из Ж. При этом в результате мы должны получить не просто разбиение, а так называемое стабильное разбиение. Стабильность — общее понятие для теории игры, которое в данном конкретном случае означает, что отсутствуют пары (m, ж) и (m', ж'), обладающие таким свойством: для m элемент ж' является предпочтительнее ж, а для ж' элемент m является предпочтительнее m'.

— Андрей Коняев. Давай поженимся. // Lenta.ru 15.10.2012

Решение[править | править исходный текст]

  • мужчины делают предложение наиболее предпочитаемой женщине;
  • каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»;
  • мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
  • если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
  • шаги повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.

Для алгоритма требуется порядка n² шагов, где n — число мужчин и женщин.

Подобные задачи[править | править исходный текст]

  • обобщение на неравное число партнёров;
  • задача о выборе учебного заведения (в одно заведение может поступить несколько студентов);
  • задача о соседях по комнате — вместо двух множеств (мужчин и женщин) имеется только одно множество.

Реализация в программировании[править | править исходный текст]

Пример на языкe Си:

#include"conio.h"
#include"stdio.h"
 
int make_offer(int);
 
const int n = 5 + 1; // dlya matritsy 5x5
 
int mass_index[n];  //massiv tekuschego indeksa muzhchin
int mass_offer[n];  // massiv tekuschih predlozheniy zhenschin
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;
 
	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, i;
 
		offer = massA[count][mass_index[count]];
		if (mass_offer[offer] == -1){
			mass_offer[offer] = count;
			return 0;
		}
		else{
			for (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; 
					}
					else{ 
						int x = mass_offer[offer];
						mass_index[mass_offer[offer]]++;
						mass_offer[offer] = count;
						return x; 
 
					}
			}
		}
}
// Coding: Anikin Dmitry

Примечания[править | править исходный текст]

  1. Андрей Коняев. Давай поженимся. Нобелевскую премию по экономике дали за стабильность выбора // Lenta.ru 15.10.2012, 21:12:16
  2. D. Gale and L. S. Shapley: «College Admissions and the Stability of Marriage», American Mathematical Monthly 69, 9-14, 1962.