Problema del matrimoni estable

Animació que explica el "problema del matrimoni estable".

En matemàtiques, economia i informàtica, el problema del matrimoni estable (també problema de emparejamiento estable o SMP) és el problema de trobar un emparejamiento estable entre dos conjunts d'elements d'igual tamany donat un orde de preferències per a cada element. Una coincidència és una biyección dels elements d'un conjunt als elements de l'atre conjunt.

Formulació

El problema del matrimoni estable s'ha plantejat de la següent manera:

    Donats n hòmens i n dònes, a on cada persona ha classificat a tots els membres del sexe opost en orde de preferència, es tracta de casar als hòmens i dònes junts de modo que no hi haja dos persones del sexe opost que preferixquen tindre's l'u a l'atre més que a les seues parelles actuals. Quan no existixen tals parells de persones, el conjunt de matrimonis es considera estable.

Una coincidència no és estable si:

1.     Hi ha un element A de el primer conjunt emparellat que preferix algun element B donat del segon conjunt emparellat sobre l'element en el que A ya està emparellat, i
2.     B també preferix A sobre l'element en el que B ya està emparellat.

En atres paraules, una coincidència és estable quan no existix cap coincidència (A, B) en la que abdós es preferixquen entre sí a la seua parella actual baixe la coincidència.

L'existència de dos classes que deuen emparellar-se (hòmens i dònes heterosexuals en este eixemple) distinguix este problema del problema dels companyers d'habitació estables.

Aplicacions

Els algoritmes per a trobar solucions al problema del matrimoni estable tenen aplicacions en una gran cantitat de situacions del món real, potser la més coneguda d'elles és l'assignació d'estudiants de medicina graduats a les seues primeres tasques en l'hospital. En 2012, el Premie Nobel de Ciències Econòmiques va ser otorgat a Lloyd S. Shapley i Alvin E. Roth "per la teoria de assignació estables i la pràctica del disseny de mercat".

Una aplicació important i a gran escala del emparejamiento estable consistix en assignar usuaris a servidors en un gran servici d'Internet distribuït. Mils de millons d'usuaris accedixen a pàgines web, videos i atres servicis en Internet, lo que requerix que cada usuari siga emparellat en un dels (potencialment) centenars de mils de servidors en tot lo món que oferixen eixe servici. Un usuari preferix servidors que estiguen lo suficientment pròxims per a proporcionar un temps de resposta més ràpit per al servici solicitat, lo que resulta en un orde preferencial (parcial) dels servidors per a cada usuari. Cada servidor preferix servir als usuaris que puga en un cost menor, lo que resulta en un orde preferencial (parcial) d'usuaris per a cada servidor. Les rets d'entrega de contingut que distribuïxen gran part del contingut i els servicis del món resolen este gran i complex problema de matrimoni estable entre usuaris i servidors cada pocs segons per a permetre que mils de millons d'usuaris s'emparellen en els seus respectius servidors que poden proporcionar les pàgines web, videos solicitats o atres servicis.

Vore també

• Emparejamiento (teoria de grafos): emparejamiento entre diferents vèrtiços del gràfic; generalment no està relacionat en l'orde de preferències.

Bibliografia

• Kleinberg, J. i Tardos, E. (2005) Algorithm Design, Capítul 1, págs. 1-12. Consulte el lloc web complementari per al text [1] [2] archivat en Wayback Machine. .
• Knuth, D. E. (1996). Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms, American Mathematical Society.
• (1992).The Annals of Applied Probability.2(2)

358–401.doi:10.1214/aoap/1177005708.

• (1984).Journal of Political Economy.92(6)

991–1016.doi:10.1086/261272.

• Roth, A. E.; Sotomayor, {{{nom2}}} (1990). Two-sided matching: A study in game-theoretic modeling and analysis, Cambridge University Press.
• Shoham, Yoav; Leyton-Brown, {{{nom2}}} (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press. ISBN 978-0-521-89943-7.
• Schummer, J.; Vohra, R. V., {{{nom2}}} (2007). «Mechanism design without money», Nisan (ed.). Algorithmic Game Theory, pp. 255–262. ISBN 978-0521872829.