Problema căsătoriei

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 28 iunie 2022; verificarea necesită 1 editare .

Problema căsătoriei sau problema căsătoriilor stabile [1]  este o problemă matematică din domeniul jocurilor cooperative . Este necesar să se găsească corespondențe stabile între elementele a două mulțimi care au propriile lor preferințe. Într-o formulare mai simplă: a face cupluri de nunți de miri și mirese în așa fel încât un soț dintr-o familie și o soție din alta să nu fie atrași unul de celălalt mai mult decât de soții lor legali [2] . Soluția problemei a fost distinsă cu Premiul Nobel pentru economie în 2012.

Soluția problemei a fost descrisă în 1962 de către matematicienii David Gale și Lloyd Shapley [3] . Setul de reguli care duce întotdeauna la formarea de perechi stabile se numește algoritmul Gale-Shapley sau „algoritmul de consimțământ întârziat”.

Multe mecanisme practice bazate pe algoritmul Gale-Shapley au fost dezvoltate de laureatul Nobel Alvin Roth . Aceste mecanisme au fost introduse în recrutarea de medici [4] și stagiari [5] în spitale , în regulile multor asociații sportive profesionale americane pentru recrutarea sportivilor în echipe [6] . În conformitate cu mecanismele instituționale propuse, firmele recrutează angajați pentru stagii [7] , instanțele angajează secretare [8] , părinții găsesc școli potrivite pentru copii [9] . Modelul de căsătorie în ansamblu descrie succesiunea acțiunilor indivizilor atunci când formează perechi în „piețele colegilor de călătorie” pentru călătorii comune, în unele sporturi (patinaj artistic în pereche, dans sportiv), comportamentul participanților la reality show-uri interactive etc. [10]

Formulare

Problema poate fi formulată astfel:

Să fie date două mulțimi M și Zh și pentru fiecare element din M, elementele din Zh sunt sortate într-o anumită ordine. Adică, putem spune care elemente ale lui W pentru un element dat m din M sunt mai preferabile și care sunt mai puține. Sortarea, desigur, pentru fiecare element poate fi diferită. Preferințe similare sunt introduse și pentru elementele din M. Esența problemei se reduce la împărțirea M și M în perechi. Fiecare pereche ia un element de la M și de la Zh. În acest caz, ca rezultat, ar trebui să obținem nu doar o partiție, ci așa-numita partiție stabilă. Stabilitatea este un concept general pentru teoria jocurilor, ceea ce în acest caz particular înseamnă că nu există perechi (m, x) și (m', x') care să aibă următoarea proprietate: pentru m, elementul x' este de preferat pentru x , iar pentru x', elementul m este preferat în locul m'.

Andrei Konyaev . Hai sa ne casatorim. // Lenta.ru 15.10.2012

Soluție

Există o metodă constructivă pentru găsirea uneia dintre soluțiile problemei.

Numărul maxim de pași pentru implementarea algoritmului: pași, unde  este numărul de bărbați și femei [11] .

Proprietăți soluție

Ca urmare, este imposibil să începi o nouă căsătorie - dacă bărbatul A are femeia B pe listă și invers, cel puțin unul se căsătorește. În consecință, dacă listele sunt complete, toți bărbații se căsătoresc sau toate femeile se căsătoresc.

În mod similar, femeile pot merge pe bărbați. Se potrivesc căsătoriile rezultate? Nu neapărat, iar contraexemplul este simplu. Să presupunem că sunt doi bărbați și două femei. Andrei o preferă pe Vera, Boris o preferă pe Galya. Femeile, dimpotrivă, sunt Vera Borisa, Galya Andrey (dar toate patru nu sunt contrarii să se căsătorească cu alta sau să se căsătorească cu alta). Dacă bărbații merg după femei, Andrei se căsătorește cu Vera, Boris se căsătorește cu Galya. Dacă femeile după bărbați - Andrey pe Gala, Boris pe Vera.

În același timp, dacă bărbații le cere femeilor, bărbații vor obține cel mai bun rezultat pentru ei înșiși din toate potrivirile stabile: nu există potriviri stabile pentru ca toți bărbații să fie în aceeași poziție sau mai bună. Mai mult, algoritmul este slab rezistent la coalițiile masculine : mai mulți bărbați nu pot schimba listele de preferințe într-o manieră coordonată pentru a îmbunătăți strict rezultatul tuturor membrilor coaliției prin exploatarea acestui algoritm [12] . O coaliție este uneori capabilă să îmbunătățească cel puțin una și să nu înrăutățească restul [13] .

Pentru femei, dimpotrivă, rezultatul va fi cel mai rău: nu există o potrivire stabilă pentru ca toate femeile să fie în aceeași poziție sau mai proastă. Algoritmul nu este rezistent la coalițiile de femei: dacă în exemplul anterior Vera îl refuză pe Andrey, iar Galya îl refuză pe Boris, femeile își vor găsi o potrivire optimă.

Sarcini similare

Implementarea în programare

Exemplu în limbajul C:

#include „conio.h” #include „stdio.h” int make_offer ( int ); const int n = 5 + 1 ; // dlya matritsy 5x5 int indice_masă [ 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 , ofer , count , count_0 = 0 ; pentru ( i = 1 ; i < n ; i ++ ){ indice de masă [ i ] = 1 ; ofertă_masă [ i ] = -1 ;}; FIȘIER * f ; f = fopen ( "input.txt" , "r" ); pentru ( i = 1 ; i < n ; i ++ ) pentru ( j = 1 ; j < n ; j ++ ) fscanf ( f , "%d" , & massA [ i ][ j ]); pentru ( i = 1 ; i < n ; i ++ ) pentru ( j = 1 ; j < n ; j ++ ) fscanf ( f , "%d" , & massB [ i ][ j ]); fclose ( f ); global_i = 1 ; int x ; în timp ce ( count_0 != n -1 ){ x = make_offer ( global_i ); dacă ( x == 0 ){ count_0 ++ ; global_i = count_0 + 1 ; } else global_i = x ; } pentru ( i = 1 ; i < n ; i ++ ) printf ( "%d - %d \n " , i , ofertă_masă [ i ] ); getch (); } int make_offer ( număr int ){ int ofertă , i ; oferta = masaA [ count ][ index_masa [ count ]]; daca ( oferta_masa [ oferta ] == -1 ){ ofertă_masă [ ofertă ] = numărare ; returnează 0 ; } else { pentru ( i = 1 ; i < n ; i ++ ){ dacă (( massB [ ofertă ][ i ] == mass_offer [ ofertă ]) | ( massB [ ofertă ][ i ] == numără )) if ( masaB [ ofertă ][ i ] == ofertă_masă [ oferta ]){ indice_masă [ număr ] ++ ; număr de întoarcere ; } else { int x = ofertă_masă [ oferta ]; index_masa [ oferta_masa [ oferta ]] ++ ; ofertă_masă [ ofertă ] = numărare ; întoarce x ; } } } } // Codificare: Anikin Dmitry

Vezi și

Note

  1. ↑ Wirth N. 3.6. Problema căsătoriilor stabile // Algoritmi și structuri de date. - M.  : „DMK Press”, 2010. - S. 154. - 272 p. - ISBN 978-5-94074-584-6 .
  2. ↑ Andrei Konyaev . Hai sa ne casatorim. Premiul Nobel pentru economie a fost acordat pentru stabilitatea alegerii Copie de arhivă din 25 decembrie 2012 la Wayback Machine // Lenta.ru
  3. ^ D. Gale și LS Shapley: „College Admissions and the Stability of Marriage”, American Mathematical Monthly 69, 9-14, 1962.
  4. ↑ Roth, Alvin E. și Peranson, Eliott. Reproiectarea pieței de potrivire pentru medicii americani: unele aspecte de inginerie ale designului economic // American Economic Review. - 1990. - Nr. 89 . - S. 748-780 .
  5. ↑ Roth Alvin E. Evoluția pieței muncii pentru stagiari și rezidenți medicali: un studiu de caz în teoria jocurilor // Journal of Political Economy. - 1984. - Nr. 92 . - S. 991-1016 .
  6. ↑ Frechette, Guilaume; Alvin E. Roth; şi M. Utku Unver. Dezlegarea generează potriviri ineficiente: dovezi din post-season College Football Bowls // Rand Journal of Economics. - 2007. - Nr. 38 . - S. 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. - Nr. 81 . - S. 415-440 .
  8. ↑ Haruvy, Ernan; Alvin E. Roth și M. Utku Unver. Dinamica potrivirii funcționarilor de drept: o investigație experimentală și computațională a propunerilor de reformă a pieței // Journal of Economic Dynamics and Control. - 2006. - Nr. 30 (3) . - S. 457-486 .
  9. ↑ Ergin, Haluk și Tayfun Sonmez. Games of School Choice under the Boston Mechanism // Journal of Public Economics. - 2005. - Nr. 90 . - S. 215-237 .
  10. ↑ Barbashin M. Yu. Institutions and Identity: Methodological Possibilities of the Theory of Institutional Disintegration in Contemporary Social Research  // Journal of Sociology and Social Anthropology . - 2014. - T. XVII , Nr. 4 (75) . - S. 178-188 .
  11. ↑ Iwama, Kazuo (2008). „Un studiu asupra problemei căsătoriei stabile și a variantelor sale” (PDF) . Conferința Internațională privind Educația și Cercetarea în Informatică pentru Societatea de Circulație a Cunoașterii (icks 2008) : 131-136. DOI : 10.1109/ICKS.2008.7 . Arhivat (PDF) din original pe 2021-08-12 . Extras 2021-08-12 . Parametrul depreciat folosit |deadlink=( ajutor )
  12. ↑ Dubins, L.E. (1981). „Machiavelli și algoritmul Gale-Shapley”. American Mathematical Monthly . 88 (7): 485-494. DOI : 10.2307/2321753 .
  13. ↑ Huang, Chien-Chung (2006). „Înșelarea de către bărbați în algoritmul de potrivire stabilă Gale-Shapley”. În Azar, Yossi; Erlebach, Thomas. Algoritmi - ESA 2006, al 14-lea Simpozion European anual, Zurich, Elveția, 11-13 septembrie 2006, Proceedings . Note de curs în informatică. 4168 . Springer. pp. 418-431. DOI : 10.1007/11841036_39 . MR  2347162 .

Literatură

  • Abdulkadiroglu, Atila și Tayfun Sonmez. Alegerea școlii: o abordare de proiectare a mecanismelor. - American Economic Review, 2003. - T. 93. - S. 729-747.
  • Dubins LE și Freedman DA Machiavelli și algoritmul Gale-Shapley. - American Mathematical Monthly, 1981. - V. 88. - S. 485-494.
  • Gusfield, Dan și Robert W. Irving. Problema căsătoriei stabile: structură și algoritmi. MIT Press. Immorlice, Nicole și Mohammad Mahdian. Căsătorie, onestitate și stabilitate. - SODA, 2005. - S. 53-62.
  • Irving RW Greedy Matchings. - Universitatea din Glasgow, Computing Science Department Research Report, 2003. - P. 136.
  • Kagel .JH și Roth AE Dinamica reorganizării în piețele de potrivire: un experiment de laborator, motivat de un experiment natural. - Revista trimestrială de economie, 2000. - V. 115. - S. 201-235.
  • Kelso Alexander S. Jr., Crawford Vincent P. Potrivirea locurilor de muncă, formarea coaliției și înlocuitori încrucișați. — Econometrica. - T. 50. - S. 1483-1504.
  • Mongell S. Sorority Rush ca un mecanism de potrivire bilaterală: o analiză teoretică a jocului. — Departamentul de Economie, Universitatea din Pittsburgh, 1988.
  • Niederle, Muriel și Alvin E. Roth. Dezlegarea reduce mobilitatea pe piața muncii: Gastroenterologie cu și fără potrivire centralizată. - Journal of Political Economy, 2003. - T. 111(6). - S. 1342-1352.
  • Roth AE și Sotomayor, M. Problema admiterii la colegiu revizuită. — Economerica. - T. 57. - S. 559-570.
  • Roth Alvin E. și Xiaolin Xing. Timp de răspuns și blocaje în compensarea pieței: potrivire descentralizată pe piață pentru psihologi clinici. - Revista de Economie Politică, 1997. - T. 105.
  • Roth, Alvin E. Despre alocarea rezidenților la spitalele rurale: O proprietate generală a piețelor de potrivire pe două fețe. - Econometrica, 1986. - T. 54(2). - S. 425-427.
  • Roth, Alvin E. Programul național de potrivire a rezidenței ca piață a muncii. - Journal of the American Medical Association, 1996. - T. 275. - S. 1054-1056.
  • Roth, Alvin E. Algoritmi de acceptare amânată: istorie, teorie, practică și întrebări deschise. — International Journal of Game Theory, număr special în onoarea lui David Gale cu ocazia împlinirii sale de 85 de ani. - T. 36. - S. 537-569.
  • Roth, Alvin E. Evoluția pieței muncii pentru stagiari și rezidenți medicali: un studiu de caz în teoria jocurilor. - Revista de Economie Politică, 1984. - T. 92. - S. 991-1026.
  • Roth, Alvin E. Originile, istoria și designul meciului rezident. - Journal of American Medical Association, 2003. - T. 289. - S. 909-912.
  • Wallis, C. Bradley, Kannan P. Samy, Alvin E. Roth și Michael A. Rees. Donație pereche de rinichi. - Nefrology Dialysis Transplantation, 2011. - T. 26(7). - S. 2091-2099.

Link -uri