Manželský problém

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. června 2022; ověření vyžaduje 1 úpravu .

Manželský problém neboli problém stabilních manželství [1]  je matematický problém z oblasti kooperativních her . Je nutné najít stabilní korespondence mezi prvky dvou množin, které mají své vlastní preference. V jednodušší formulaci: sestavit manželské páry ze snoubenců a nevěst tak, aby se manžel z jedné rodiny a manželka z druhé vzájemně nepřitahovali více než jejich zákonní manželé [2] . Řešení problému bylo oceněno v roce 2012 Nobelovou cenou za ekonomii.

Řešení problému popsali v roce 1962 matematici David Gale a Lloyd Shapley [3] . Sada pravidel, která vždy vede k vytvoření stabilních párů, se nazývá Gale-Shapleyho algoritmus nebo „algoritmus zpožděného souhlasu“.

Mnoho praktických mechanismů založených na Gale-Shapleyově algoritmu vyvinul nositel Nobelovy ceny Alvin Roth . Tyto mechanismy byly zavedeny do náboru lékařů [4] a stážistů [5] v nemocnicích , v pravidlech mnoha amerických profesionálních sportovních asociací pro nábor sportovců do týmů [6] . V souladu s navrženými institucionálními mechanismy firmy nabírají zaměstnance na stáže [7] , soudy najímají sekretářky [8] , rodiče hledají vhodné školy pro děti [9] . Model manželství jako celek popisuje sled akcí jednotlivců při vytváření párů na „spolucestovatelských trzích“ pro společné výlety, v některých sportech (párové krasobruslení, sportovní tanec), chování účastníků interaktivních reality show atd. [10]

Formulace

Problém lze formulovat následovně:

Nechť jsou dány dvě množiny M a Zh a pro každý prvek z M jsou prvky z Zh seřazeny v nějakém pořadí. To znamená, že můžeme říci, které prvky W pro daný prvek m z M jsou výhodnější a které méně. Řazení může být samozřejmě u každého prvku jiné. Podobné preference jsou také zavedeny pro prvky z M. Podstata problému se redukuje na rozdělení M a M do dvojic. Každý pár si vezme jeden prvek z M a ze Zh. V tomto případě bychom ve výsledku neměli dostat jen oddíl, ale takzvaný stabilní oddíl. Stabilita je obecný pojem pro teorii her, což v tomto konkrétním případě znamená, že neexistují žádné dvojice (m, x) a (m', x'), které by měly následující vlastnost: pro m je prvek x' vhodnější než x a pro x' je prvek m preferován před m'.

Andrej Konjajev . Pojdme se vzít. // Lenta.ru 15. 10. 2012

Řešení

Existuje konstruktivní metoda, jak najít jedno z řešení problému.

Maximální počet kroků k implementaci algoritmu: kroky, kde  je počet mužů a žen [11] .

Vlastnosti řešení

V důsledku toho je nemožné zahájit nové manželství - pokud má muž A na seznamu ženu B a naopak, alespoň jeden se ožení. V souladu s tím, pokud jsou seznamy úplné, vdávají se všichni muži nebo všechny ženy.

Podobně mohou ženy chodit po mužích. Odpovídají výsledná manželství? Ne nutně a protipříklad je jednoduchý. Předpokládejme, že jsou dva muži a dvě ženy. Andrei preferuje Veru, Boris preferuje Galyu. Ženy jsou naopak Vera Borisa, Galya Andrey (ale všechny čtyři nemají odpor k tomu, aby si vzaly jinou nebo si vzaly jinou). Pokud muži jdou po ženách, Andrey si vezme Veru, Boris si vezme Galyu. Když ženy po mužích - Andrey na Gala, Boris na Veru.

Zároveň, pokud muži navrhnou ženám návrh, muži pro sebe získají nejlepší výsledek ze všech stabilních párování: neexistuje žádné stabilní párování, aby všichni muži byli ve stejné nebo lepší pozici. Algoritmus je navíc slabě odolný vůči mužským koalicím : několik mužů nemůže koordinovaně měnit seznamy preferencí, aby striktně zlepšili výsledek všech členů koalice využitím tohoto algoritmu [12] . Koalice je někdy schopna alespoň jednu zlepšit a zbytek nezhoršit [13] .

U žen bude výsledek naopak nejhorší: neexistuje stabilní shoda, aby všechny ženy byly ve stejné nebo horší pozici. Algoritmus není odolný vůči ženským koalicím: pokud v předchozím příkladu Věra odmítne Andrey a Galya Borise, ženy si pro sebe najdou optimální shodu.

Podobné úkoly

Implementace v programování

Příklad v jazyce C:

#include "conio.h" #include "stdio.h" int nabídka_nabídky ( int ); const int n = 5 + 1 ; // dlya matritsy 5x5 int hmotnostní_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 , nabídka , počet , počet_0 = 0 ; for ( i = 1 ; i < n ; i ++ ){ index hmotnosti [ i ] = 1 ; hromadná_nabídka [ i ] = -1 ;}; SOUBOR * f ; f = fopen ( "vstup.txt" , "r" ); pro ( i = 1 ; i < n ; i ++ ) pro ( j = 1 ; j < n ; j ++ ) fscanf ( f , "%d" & massA [ i ] [ j ]); pro ( i = 1 ; i < n ; i ++ ) pro ( j = 1 ; j < n ; j ++ ) fscanf ( f , "%d" a hmotnostB [ i ] [ j ]); fclose ( f ); global_i = 1 ; int x ; while ( počet_0 != n -1 ){ x = make_offer ( global_i ); if ( x == 0 ){ počet_0 ++ ; global_i = pocet_0 + 1 ; } else global_i = x ; } pro ( i = 1 ; i < n ; i ++ ) printf ( "%d - %d \n " , i , hromadná_nabídka [ i ] ); getch (); } int make_offer ( int count ){ int nabídka , i ; nabídka = hmotnostA [ počet ][ index_masy [ počet ]]; if ( hromadná_nabídka [ nabídka ] == -1 ){ hromadná_nabídka [ nabídka ] = počet ; návrat 0 ; } jinak { for ( i = 1 ; i < n ; i ++ ){ if (( massB [ nabídka ][ i ] == hromadná_nabídka [ nabídka ]) | ( massB [ nabídka ][ i ] == počítat )) if ( hmotnostB [ nabídka ][ i ] == hromadná_nabídka [ nabídka ]){ index_masy [ počet ] ++ ; vrátit počet ; } else { int x = hromadná_nabídka [ nabídka ]; mass_index [ hromadná_nabídka [ nabídka ]] ++ ; hromadná_nabídka [ nabídka ] = počet ; návrat x ; } } } } // Kódování: Anikin Dmitry

Viz také

Poznámky

  1. ↑ Wirth N. 3.6. Problém stabilních manželství // Algoritmy a datové struktury. - M.  : "DMK Press", 2010. - S. 154. - 272 s. - ISBN 978-5-94074-584-6 .
  2. ↑ Andrej Konjajev . Pojdme se vzít. Nobelova cena za ekonomii byla udělena za stabilitu volby Archivní kopie z 25. prosince 2012 na Wayback Machine // Lenta.ru
  3. ↑ D. Gale a LS Shapley: „Přijetí na vysokou školu a stabilita manželství“, American Mathematical Monthly 69, 9-14, 1962.
  4. ↑ Roth, Alvin E. a Peranson, Eliott. Redesign odpovídajícího trhu pro americké lékaře: Některé technické aspekty ekonomického designu // American Economic Review. - 1990. - č. 89 . - S. 748-780 .
  5. ↑ Roth Alvin E. Vývoj trhu práce pro lékařské stážisty a rezidenty: Případová studie z teorie her // Journal of Political Economy. - 1984. - č. 92 . - S. 991-1016 .
  6. ↑ Frechette, Guilaume; Alvin E. Roth; a M. Utku Unver. Odhalení výnosů neefektivní shody: Důkazy z posezónních vysokoškolských fotbalových mís // Rand Journal of Economics. - 2007. - č. 38 . - S. 967-982 .
  7. ↑ Roth, Alvin E. Přirozený experiment v organizaci trhů práce na základní úrovni: Regionální trhy pro nové lékaře a chirurgy ve Spojeném království // American Economic Review. - 1991. - č. 81 . - S. 415-440 .
  8. ↑ Haruvy, Ernan; Alvin E. Roth a M. Utku Unver. The Dynamics of Law Clerk Matching: Experimentální a výpočetní zkoumání návrhů na reformu trhu // Journal of Economic Dynamics and Control. - 2006. - č. 30 (3) . - S. 457-486 .
  9. ↑ Ergin, Haluk a Tayfun Sonmez. Games of School Choice v rámci Bostonského mechanismu // Journal of Public Economics. - 2005. - č. 90 . - S. 215-237 .
  10. ↑ Barbashin M. Yu Instituce a identita: Metodologické možnosti teorie institucionální dezintegrace v současném sociálním výzkumu  // Časopis pro sociologii a sociální antropologii . - 2014. - T. XVII , č. 4 (75) . - S. 178-188 .
  11. ↑ Iwama, Kazuo (2008). „Průzkum problému stabilního manželství a jeho variant“ (PDF) . International Conference on Information Education and Research for Knowledge-Circulating Society (icks 2008) : 131-136. DOI : 10.1109/ICKS.2008.7 . Archivováno (PDF) z originálu dne 2021-08-12 . Staženo 2021-08-12 . Použitý zastaralý parametr |deadlink=( nápověda )
  12. ↑ Dubins, L. E. (1981). „Machiavelli a Gale-Shapleyho algoritmus“ . Americký matematický měsíčník . 88 (7): 485-494. DOI : 10.2307/2321753 .
  13. ↑ Huang, Chien-Chung (2006). "Podvádění mužů ve stabilním párovacím algoritmu Gale-Shapley." V Azar, Yossi; Erlebach, Thomas. Algorithms - ESA 2006, 14th Annual European Symposium, Curych, Švýcarsko, 11.-13. září 2006, Proceedings . Poznámky z přednášek z informatiky. 4168 . Springer. str. 418-431. DOI : 10.1007/11841036_39 . MR  2347162 .

Literatura

  • Abdulkadiroglu, Atila a Tayfun Sonmez. Výběr školy: Přístup k návrhu mechanismu. - American Economic Review, 2003. - T. 93. - S. 729-747.
  • Dubins LE a Freedman DA Machiavelli a Gale-Shapleyho algoritmus. - Americký matematický měsíčník, 1981. - V. 88. - S. 485-494.
  • Gusfield, Dan a Robert W. Irvingovi. Problém stabilního manželství: Struktura a algoritmy. MIT Press Immorlice, Nicole a Mohammad Mahdian. Manželství, poctivost a stabilita. - SODA, 2005. - S. 53-62.
  • Irving RW Greedy Matchings. - University of Glasgow, Zpráva o výzkumu oddělení výpočetní vědy, 2003. - S. 136.
  • Kagel .JH a Roth AE Dynamika reorganizace na odpovídajících trzích: Laboratorní experiment motivovaný přirozeným experimentem. - Quarterly Journal of Economics, 2000. - V. 115. - S. 201-235.
  • Kelso Alexander S. Jr., Crawford Vincent P. Job Matching, tvorba koalice a křížoví náhradníci. — Ekonometrie. - T. 50. - S. 1483-1504.
  • Mongell S. Sorority Rush jako oboustranný párovací mechanismus: herně teoretická analýza. — Katedra ekonomie, University of Pittsburgh, 1988.
  • Niederle, Muriel a Alvin E. Roth. Unraveling snižuje mobilitu na trhu práce: Gastroenterologie s centralizovanou shodou a bez ní. - Journal of Political Economy, 2003. - T. 111(6). - S. 1342-1352.
  • Roth AE a Sotomayor, M. Problém s přijímáním na vysokou školu znovu. — Ekonomika. - T. 57. - S. 559-570.
  • Roth Alvin E. a Xiaolin Xing. Doba obratu a úzká místa při zúčtování trhu: Decentralizované párování na trhu pro klinické psychology. - Journal of Political Economy, 1997. - T. 105.
  • Roth, Alvin E. O alokaci rezidentů do venkovských nemocnic: Obecná vlastnost oboustranných párovacích trhů. - Econometrica, 1986. - T. 54(2). - S. 425-427.
  • Roth, Alvin E. The National Residency Matching Program jako trh práce. - Journal of the American Medical Association, 1996. - T. 275. - S. 1054-1056.
  • Roth, Alvin E. Algoritmy odloženého přijetí: Historie, teorie, praxe a otevřené otázky. — International Journal of Game Theory, zvláštní vydání na počest Davida Galea k jeho 85. narozeninám. - T. 36. - S. 537-569.
  • Roth, Alvin E. Vývoj trhu práce pro lékařské stážisty a rezidenty: Případová studie v teorii her. - Journal of Political Economy, 1984. - T. 92. - S. 991-1026.
  • Roth, Alvin E. Původy, historie a design domácího zápasu. - Journal of American Medical Association, 2003. - T. 289. - S. 909-912.
  • Wallis, C. Bradley, Kannan P. Samy, Alvin E. Roth a Michael A. Rees. Párové dárcovství ledvin. - Nefrologická dialyzační transplantace, 2011. - T. 26(7). - S. 2091-2099.

Odkazy