Problema de matrimonio

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de junio de 2022; la verificación requiere 1 edición .

El problema del matrimonio o el problema de los matrimonios estables [1]  es un problema matemático del campo de los juegos cooperativos . Se requiere encontrar correspondencias estables entre elementos de dos conjuntos que tienen sus propias preferencias. En una formulación más simple: hacer parejas matrimoniales de novios y novias de tal manera que un esposo de una familia y una esposa de otra no se atraigan más el uno al otro que a sus cónyuges legales [2] . La solución al problema fue galardonada con el Premio Nobel de Economía 2012.

La solución al problema fue descrita en 1962 por los matemáticos David Gale y Lloyd Shapley [3] . El conjunto de reglas que siempre conduce a la formación de pares estables se denomina algoritmo de Gale-Shapley o "algoritmo de consentimiento retardado".

Muchos mecanismos prácticos basados ​​en el algoritmo de Gale-Shapley fueron desarrollados por el premio Nobel Alvin Roth . Estos mecanismos se han introducido en el reclutamiento de médicos [4] e internos [5] en hospitales , en las reglas de muchas asociaciones deportivas profesionales estadounidenses para el reclutamiento de atletas en equipos [6] . De acuerdo con los mecanismos institucionales propuestos, las empresas reclutan empleados para pasantías [7] , los tribunales contratan secretarios [8] , los padres encuentran escuelas adecuadas para los niños [9] . El modelo de matrimonio en su conjunto describe la secuencia de acciones de los individuos al formar parejas en “mercados de compañeros de viaje” para viajes conjuntos, en algunos deportes (patinaje artístico en pareja, baile deportivo), el comportamiento de los participantes en reality shows interactivos, etc. [10]

Redacción

El problema se puede formular de la siguiente manera:

Sean dados dos conjuntos M y Zh, y para cada elemento de M, los elementos de Zh se clasifican en algún orden. Es decir, podemos decir qué elementos de W para un elemento dado m de M son más preferibles y cuáles son menos. La clasificación, por supuesto, para cada elemento puede ser diferente. También se introducen preferencias similares para los elementos de M. La esencia del problema se reduce a dividir M y M en pares. Cada par toma un elemento de M y de Zh En este caso, como resultado, deberíamos obtener no solo una partición, sino la llamada partición estable. La estabilidad es un concepto general para la teoría de juegos, lo que en este caso particular significa que no hay pares (m, x) y (m', x') que tengan la siguiente propiedad: para m, el elemento x' es preferible a x , y para x', se prefiere el elemento m sobre m'.

Andrei Konyaev . Vamos a casarnos. // Lenta.ru 15/10/2012

Solución

Hay un método constructivo para encontrar una de las soluciones al problema.

El número máximo de pasos para implementar el algoritmo: pasos, donde  es el número de hombres y mujeres [11] .

Propiedades de la solución

Como resultado, es imposible comenzar un nuevo matrimonio: si el hombre A tiene a la mujer B en la lista y viceversa, al menos uno se casa. En consecuencia, si las listas están completas, todos los hombres se casan o todas las mujeres se casan.

Del mismo modo, las mujeres pueden caminar sobre los hombres. ¿Coinciden los matrimonios resultantes? No necesariamente, y el contraejemplo es simple. Supongamos que hay dos hombres y dos mujeres. Andrei prefiere a Vera, Boris prefiere a Galya. Las mujeres, por el contrario, son Vera Borisa, Galya Andrey (pero las cuatro no son reacias a casarse con otra o casarse con otra). Si los hombres persiguen a las mujeres, Andrey se casa con Vera, Boris se casa con Galya. Si las mujeres después de los hombres: Andrey en Gala, Boris en Vera.

Al mismo tiempo, si los hombres le proponen matrimonio a las mujeres, los hombres obtendrán el mejor resultado para sí mismos de todas las parejas estables: no hay pareja estable para que todos los hombres estén en la misma o mejor posición. Además, el algoritmo es débilmente resistente a las coaliciones masculinas : varios hombres no pueden cambiar las listas de preferencias de manera coordinada para mejorar estrictamente el resultado de todos los miembros de la coalición mediante la explotación de este algoritmo [12] . Una coalición a veces puede mejorar al menos uno y no empeorar el resto [13] .

Para las mujeres, por el contrario, el resultado será el peor: no existe un emparejamiento estable para que todas las mujeres estén en la misma o peor posición. El algoritmo no es resistente a las coaliciones de mujeres: si en el ejemplo anterior Vera rechaza a Andrey y Galya rechaza a Boris, las mujeres encontrarán una pareja óptima para ellas.

Tareas similares

Implementación en la programación

Ejemplo en lenguaje C:

#include "conio.h" #incluir "stdio.h" int hacer_oferta ( int ); const int n = 5 + 1 ; // matritsy dlya 5x5 int índice_masa [ n ]; //massiv tekuschego indeksa muzhchin int mass_offer [ n ]; // massiv tekuschih predlozheniy zhenschin int masaA [ n ][ n ], masaB [ n ][ n ]; int global_i ; vacío principal (){ int i , j , oferta , cuenta , cuenta_0 = 0 ; for ( i = 1 ; i < n ; i ++ ){ índice_masa [ i ] = 1 ; oferta_masa [ i ] = -1 ;}; ARCHIVO * f ; f = fopen ( "entrada.txt" , "r" ); para ( yo = 1 ; yo < norte ; yo ++ ) para ( j = 1 ; j < norte ; j ++ ) fscanf ( f , "%d" y masaA [ i ] [ j ] ); para ( yo = 1 ; yo < norte ; yo ++ ) para ( j = 1 ; j < norte ; j ++ ) fscanf ( f , "%d" y masaB [ i ] [ j ] ); fcerrar ( f ); global_i = 1 ; intx ; _ while ( contar_0 != n -1 ){ x = hacer_oferta ( global_i ); si ( x == 0 ){ cuenta_0 ++ ; global_i = cuenta_0 + 1 ; } más global_i = x ; } para ( yo = 1 ; yo < norte ; yo ++ ) printf ( "%d - %d \n " , i , mass_offer [ i ] ); obtener (); } int hacer_oferta ( int cuenta ){ oferta int , i ; oferta = masaA [ cuenta ][ índice_masa [ cuenta ]]; if ( masa_oferta [ oferta ] == -1 ){ mass_offer [ oferta ] = cuenta ; devolver 0 ; } más { para ( yo = 1 ; yo < norte ; yo ++ ){ if (( masaB [ oferta ][ i ] == oferta_masa [ oferta ]) | ( masaB [ oferta ][ i ] == cuenta )) if ( masaB [ oferta ][ i ] == oferta_masa [ oferta ]){ índice_masa [ recuento ] ++ ; recuento de retorno ; } else { int x = mass_offer [ oferta ]; índice_masa [ oferta_masa [ oferta ]] ++ ; mass_offer [ oferta ] = cuenta ; devuelve x ; } } } } // Codificación: Anikin Dmitry

Véase también

Notas

  1. ↑ With N. 3.6. El problema de los matrimonios estables // Algoritmos y estructuras de datos. - M.  : "DMK Press", 2010. - S. 154. - 272 p. - ISBN 978-5-94074-584-6 .
  2. ↑ Andréi Konyaev . Vamos a casarnos. El Premio Nobel de Economía se otorgó por la estabilidad de la elección Copia de archivo del 25 de diciembre de 2012 en Wayback Machine // Lenta.ru
  3. ↑ D. Gale y LS Shapley: "Admisión a la universidad y la estabilidad del matrimonio", American Mathematical Monthly 69, 9-14, 1962.
  4. ↑ Roth, Alvin E. y Peranson, Eliott. El rediseño del mercado de emparejamiento para médicos estadounidenses: algunos aspectos de ingeniería del diseño económico // American Economic Review. - 1990. - Nº 89 . - S. 748-780 .
  5. ↑ Roth Alvin E. La evolución del mercado laboral para médicos internos y residentes: un estudio de caso en teoría de juegos // Journal of Political Economy. - 1984. - Nº 92 . - S. 991-1016 .
  6. ↑ Frechette, Guilaume; Alvin E. Roth; y M.Utku Unver. Desentrañar rendimientos emparejamientos ineficientes: evidencia de bolos de fútbol americano universitario después de la temporada // Rand Journal of Economics. - 2007. - Nº 38 . - S. 967-982 .
  7. ↑ Roth, Alvin E. Un experimento natural en la organización de mercados laborales de nivel de entrada: mercados regionales para nuevos médicos y cirujanos en el Reino Unido // American Economic Review. - 1991. - Nº 81 . - S. 415-440 .
  8. ↑ Haruvy, Ernan; Alvin E. Roth y M. Utku Unver. La dinámica del emparejamiento de asistentes legales: una investigación experimental y computacional de propuestas para la reforma del mercado // Journal of Economic Dynamics and Control. - 2006. - Nº 30 (3) . - S. 457-486 .
  9. ↑ Ergin, Haluk y Tayfun Sonmez. Juegos de elección de escuela bajo el mecanismo de Boston // Journal of Public Economics. - 2005. - Nº 90 . - S. 215-237 .
  10. ↑ Barbashin M. Yu. Instituciones e identidad: posibilidades metodológicas de la teoría de la desintegración institucional en la investigación social contemporánea  // Revista de sociología y antropología social . - 2014. - T. XVII , N° 4 (75) . - S. 178-188 .
  11. ↑ Iwama, Kazuo (2008). “Una encuesta sobre el problema del matrimonio estable y sus variantes” (PDF) . Conferencia Internacional sobre Educación e Investigación en Informática para la Sociedad de la Circulación del Conocimiento (icks 2008) : 131-136. DOI : 10.1109/ICKS.2008.7 . Archivado (PDF) desde el original el 12 de agosto de 2021 . Consultado el 12 de agosto de 2021 . Parámetro obsoleto utilizado |deadlink=( ayuda )
  12. ↑ Dubins, LE (1981). "Maquiavelo y el algoritmo de Gale-Shapley". Mensual Matemático Americano . 88 (7): 485-494. DOI : 10.2307/2321753 .
  13. ↑ Huang, Chien-Chung (2006). “Hacer trampa por parte de los hombres en el algoritmo de coincidencia estable de Gale-Shapley”. En Azar, Yossi; Erlebach, Thomas. Algorithms - ESA 2006, 14th Annual European Symposium, Zúrich, Suiza, 11-13 de septiembre de 2006, Actas . Apuntes de clase en informática. 4168 . Saltador. páginas. 418-431. DOI : 10.1007/11841036_39 . MR  2347162 .

Literatura

  • Abdulkadiroglu, Atila y Tayfun Sonmez. Elección de escuela: un enfoque de diseño de mecanismos. - American Economic Review, 2003. - T. 93. - S. 729-747.
  • Dubins LE y Freedman DA Maquiavelo y el Algoritmo de Gale-Shapley. - American Mathematical Monthly, 1981. - V. 88. - S. 485-494.
  • Gusfield, Dan y Robert W. Irving. El problema del matrimonio estable: estructura y algoritmos. Prensa del MIT Immorlice, Nicole y Mohammad Mahdian. Matrimonio, Honestidad y Estabilidad. - SODA, 2005. - S. 53-62.
  • Emparejamientos codiciosos de Irving RW . - Universidad de Glasgow, Informe de investigación del Departamento de Ciencias de la Computación, 2003. - P. 136.
  • Kagel .JH y Roth AE La dinámica de la reorganización en los mercados coincidentes: un experimento de laboratorio, motivado por un experimento natural. - Revista Trimestral de Economía, 2000. - V. 115. - S. 201-235.
  • Kelso Alexander S. Jr., Crawford Vincent P. Ajuste de trabajos, formación de coaliciones y sustitutos cruzados. — Econométrica. - T. 50. - S. 1483-1504.
  • Mongell S. Sorority Rush como un mecanismo de emparejamiento de dos caras: un análisis teórico del juego. — Departamento de Economía, Universidad de Pittsburgh, 1988.
  • Niederle, Muriel y Alvin E. Roth. El desmoronamiento reduce la movilidad en un mercado laboral: gastroenterología con y sin partido centralizado. - Revista de Economía Política, 2003. - T. 111(6). - S. 1342-1352.
  • Roth AE y Sotomayor, M. Revisión del problema de admisión a la universidad. — Economérica. - T. 57. - S. 559-570.
  • Roth Alvin E. y Xiaolin Xing. Tiempo de respuesta y cuellos de botella en la compensación del mercado: emparejamiento descentralizado en el mercado de psicólogos clínicos. - Revista de Economía Política, 1997. - T. 105.
  • Roth, Alvin E. Sobre la asignación de residentes a hospitales rurales: una propiedad general de los mercados de emparejamiento de dos lados. - Econométrica, 1986. - T. 54(2). - S. 425-427.
  • Roth, Alvin E. El Programa Nacional de Igualación de Residencia como Mercado Laboral. - Revista de la Asociación Médica Americana, 1996. - T. 275. - S. 1054-1056.
  • Roth, Alvin E. Algoritmos de aceptación diferida: historia, teoría, práctica y preguntas abiertas. — International Journal of Game Theory, número especial en honor a David Gale en su 85 cumpleaños. - T. 36. - S. 537-569.
  • Roth, Alvin E. La evolución del mercado laboral para médicos internos y residentes: un estudio de caso en teoría de juegos. - Revista de Economía Política, 1984. - T. 92. - S. 991-1026.
  • Roth, Alvin E. Los orígenes, la historia y el diseño del partido residente. - Revista de la Asociación Médica Americana, 2003. - T. 289. - S. 909-912.
  • Wallis, C. Bradley, Kannan P. Samy, Alvin E. Roth y Michael A. Rees. Donación Pareada de Riñón. - Nefrología Diálisis Trasplante, 2011. - T. 26(7). - S. 2091-2099.

Enlaces