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

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

Решение задачи было описано в 1962 году математиками Дэвидом Гэйлом и Ллойдом Шепли[3]. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гэйла — Шепли или «алгоритма отложенного согласия».

Множество практических механизмов на основе алгоритма Гэйла — Шепли разработал нобелевский лауреат Элвин Рот. Эти механизмы были внедрены в деятельность больниц по набору врачей[4] и интернов[5], в правила многих американских профессиональных спортивных ассоциаций по набору спортсменов в команды[6]. В соответствии с предложенными институциональными механизмами фирмы набирают на стажировку сотрудников[7], суды нанимают секретарей[8], родители находят подходящие школы для детей[9]. Модель марьяжа в целом описывает последовательность действий индивидов при формировании пар на «рынках попутчиков» для совместных поездок, в некоторых видах спорта (парное фигурное катание, спортивные танцы), поведение участников в интерактивных реалити-шоу и пр[10].

Формулировка

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

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

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

Решение

Существует конструктивный метод нахождения одного из решений задачи.

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

Максимальное количество шагов для реализации алгоритма: шагов, где  — число мужчин и женщин[11].

Свойства решения

В результате невозможно завести новый брак — если у мужчины А в списке есть женщина Б и наоборот, хотя бы один женится. Соответственно, если списки полные, женятся все мужчины или все женщины.

Аналогично женщины могут ходить по мужчинам. Совпадают ли получившиеся браки? Не обязательно, и контрпример прост. Пусть есть два мужчины и две женщины. Андрей предпочитает Веру, Борис — Галю. Женщины наоборот — Вера Бориса, Галя Андрея (но и на другом жениться или выйти замуж все четверо не прочь). Если мужчины ходят по женщинам — Андрей женится на Вере, Борис на Гале. Если женщины по мужчинам — Андрей на Гале, Борис на Вере.

При этом, если мужчины делают предложения женщинам, мужчины получат самый лучший для себя результат из всех устойчивых паросочетаний: не существует устойчивого паросочетания, чтобы все мужчины оказались в том же или лучшем положении. Мало того, алгоритм слабо стоек к мужским коалициям: несколько мужчин не могут скоординированно изменить списки предпочтения, чтобы путём эксплуатации этого алгоритма строго улучшить результат всем членам коалиции[12]. Улучшить хотя бы одному и не ухудшить остальным коалиция иногда способна[13].

Для женщин результат, наоборот, будет наихудшим: не существует устойчивого паросочетания, чтобы все женщины оказались в том же или худшем положении. Алгоритм не стоек к женским коалициям: если в предыдущем примере Вера откажется от Андрея, а Галя от Бориса, женщины найдут себе оптимальную пару.

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

Реализация в программировании

Пример на язык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. Вирт Н. 3.6. Задача о стабильных браках // Алгоритмы и структуры данных. — М. : «ДМК Пресс», 2010. — С. 154. — 272 с. — ISBN 978-5-94074-584-6.
  2. Андрей Коняев. Давай поженимся. Нобелевскую премию по экономике дали за стабильность выбора // Lenta.ru 15.10.2012, 21:12:16
  3. D. Gale and L. S. Shapley: «College Admissions and the Stability of Marriage», American Mathematical Monthly 69, 9-14, 1962.
  4. Roth, Alvin E. and Peranson, Eliott. The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design // American Economic Review. — 1990. — № 89. — С. 748—780.
  5. Roth Alvin E. The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory // Journal of Political Economy. — 1984. — № 92. — С. 991—1016.
  6. Frechette, Guilaume; Alvin E. Roth; and M. Utku Unver. Unraveling Yields Inefficient Matchings: Evidence from Post-Season College Football Bowls // Rand Journal of Economics. — 2007. — № 38. — С. 967—982.
  7. Roth, Alvin E. A Natural Experiment in the Organization of Entry Level Labor Markets: Regional Markets for New Physicians and Surgeons in the UK // American Economic Review. — 1991. — № 81. — С. 415—440.
  8. Haruvy, Ernan; Alvin E. Roth, and M. Utku Unver. The Dynamics of Law Clerk Matching: An Experimental and Computational Investigation of Proposals for Reform of the Market // Journal of Economic Dynamics and Control. — 2006. — № 30(3). — С. 457—486.
  9. Ergin, Haluk and Tayfun Sonmez. Games of School Choice under the Boston Mechanism // Journal of Public Economics. — 2005. — № 90. — С. 215—237.
  10. Барбашин М. Ю. Институты и идентичность: методологические возможности теории институционального распада в современных социальных исследованиях // Журнал социологии и социальной антропологии. — 2014. — Т. XVII, № 4(75). — С. 178—188.
  11. Iwama, Kazuo (2008). “A Survey of the Stable Marriage Problem and Its Variants” (PDF). International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008): 131—136. DOI:10.1109/ICKS.2008.7.
  12. Dubins, L. E. (1981). “Machiavelli and the Gale–Shapley algorithm”. American Mathematical Monthly. 88 (7): 485—494. DOI:10.2307/2321753.
  13. Huang, Chien-Chung (2006). «Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings». 4168: 418–431, Springer. DOI:10.1007/11841036_39.

Литература
  • Abdulkadiroglu, Atila and Tayfun Sonmez. School Choice: A Mechanism Design Approach. — American Economic Review, 2003. — Т. 93. — С. 729—747.
  • Dubins L.E. and Freedman D.A. Machiavelli and the Gale-Shapley Algorithm. — American Mathematical Monthly, 1981. — Т. 88. — С. 485—494.
  • Gusfield, Dan and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press.Immorlice, Nicole and Mohammad Mahdian. Marriage, Honesty and Stability. — SODA, 2005. — С. 53—62.
  • Irving R.W. Greedy Matchings. — University of Glasgow, Computing Science Department Research Report, 2003. — С. 136.
  • Kagel .J.H. and Roth A.E. The Dynamics of Reorganization in Matching Markets: A Laboratory Experiment, Motivated by a Natural Experiment. — Quarterly Journal of Economics, 2000. — Т. 115. — С. 201—235.
  • Kelso Alexander S. Jr., Crawford Vincent P. Job Matching, Coalition Formation, and Cross Substitutes. — Econometrica. — Т. 50. — С. 1483—1504.
  • Mongell S. Sorority Rush as a Two-Sided Matching Mechanism: A Game-Theoretic Analysis. — Department of Economics, University of Pittsburgh, 1988.
  • Niederle, Muriel and Alvin E. Roth. Unraveling Reduces Mobility in a Labor Market: Gastroenterology with and without a Centralized Match. — Journal of Political Economy, 2003. — Т. 111(6). — С. 1342—1352.
  • Roth A.E. and Sotomayor, M. The College Admissions Problem Revisited. — Economelrica. — Т. 57. — С. 559—570.
  • Roth Alvin E. and Xiaolin Xing. Turnaround Time and Bottlenecks in Market Clearing: Decentralized Matching in the Market for Clinical Psychologists. — Journal of Political Economy, 1997. — Т. 105.
  • Roth, Alvin E. On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets. — Econometrica, 1986. — Т. 54(2). — С. 425—427.
  • Roth, Alvin E. The National Residency Matching Program as a Labor Market. — Journal of the American Medical Association, 1996. — Т. 275. — С. 1054—1056.
  • Roth, Alvin E. Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions. — International Journal of Game Theory, Special Issue in Honor of David Gale on his 85th birthday. — Т. 36. — С. 537—569.
  • Roth, Alvin E. The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory. — Journal of Political Economy, 1984. — Т. 92. — С. 991—1026.
  • Roth, Alvin E. The Origins, History, and Design of the Resident Match. — Journal of American Medical Association, 2003. — Т. 289. — С. 909—912.
  • Wallis, C. Bradley, Kannan P. Samy, Alvin E. Roth, and Michael A. Rees. Kidney Paired Donation. — Nephrology Dialysis Transplantation, 2011. — Т. 26(7). — С. 2091—2099.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.