Մասնակից:Araqsya Manukyan/Սևագրություն

Մաթեմատիկայում և համակարգչային գիտության մեջ կայուն ամուսնության խնդիրը (SMP) յուրաքանչյուր տարրի համար տրված մի շարք նախասիրությունների պայմաններում տարրի երկու խմբերի միջև կայուն համապատասխանություն գտնելն է: Համապատասխանությունը մի խմբի տարրերի քարտեզագրումն է մյուս խմբի տարրերի հետ: Համապատասխանությունը կայուն է բոլոր դեպքերում, բացի հետևյալ երկուսից.

1. Առաջինը ընտրված խմբի տրված A տարրերից որոշները ավելի նախապատվությունը տալիս են երկրորդը ընտրված խմբի տրված B տարրերից որոշներին, քան մի տարրի, որին արդեն A-ն համապատասխանեցրած է, և
2. B-ն նույնպես գերադասում է A-ն, քան այն տարրը, որին B-ն արդեն համապատասխանում է

Այսինքն, համապատասխանությունը կայուն է, երբ գոյություն չունի որևէ այլընտրանքային զույգ (A, B), որում և A-ն և B-ն անհատապես կլինեն ավելի լավը, քան կլինեին այն տարրի հետ, որին նրանք իրականում համապատասխանում են:

Կայուն ամուսնության խնդիրը սովորաբար ձևակերպվում է հետևյալ կերպ. Տրված են n տղամարդ և n կին, որտեղ յուրաքանչյուր ոք ըստ նախասիրության համարակալել է հակառակ սեռի բոլոր անդամներին եզակի թվերով 1-ից մինչև n , ամուսնացրել տղամարդկանց և կանանց այնպես, որ չլինեն հակառակ սեռի երկու մարդ, որոնք ավելի կնախընտրեին մեկ ուրիշի, քան իրենց զուգընկերոջը: Եթե չկան այդպիսի մարդիկ, բոլոր ամուսնությունները "կայուն" են:

Կայուն ամուսնության խնդրի լուծման ալգորիթմները լուծում են գտնում իրական աշխարհի տարբեր իրավիճակներում, որոնցից ամենահայտնին հանդիսանում է բժիշկ շրջանավարտների նշանակումը իրենց առաջին հիվանդանոցում:

Լուծում

Animation showing an example of the Gale-Shapley algorithm

1962 թվականին Դավիթ Գեյլը և Լոյդ Շեպլին ապացուցեցին, որ ցանկացած հավասար թվով կանանց և տղամարդկանց համար միշտ հնարավոր է լուծել Կայուն Ամուսնության Խնդիրը և բոլոր ամուսնությունները դարձնել կայուն: Դրա համար նրանք ներկայացրեցին ալգորիթմ:

Գեյլ-Շեպլի ալգորիթմը ներառում է մի շարք "փուլեր" (կամ "կրկնողություններ"), որտեղ յուրաքանչյուր չնշանված տղամարդ "ամուսնության առաջարկություն է անում" ամենանախընտրելի կնոջը: Հետո յուրաքնչյուր կին քննարկում է իր բոլոր երկրպագուներին և նրան, ում նա ավելի է նախընտրում, ասում է "Հնարավոր է", իսկ մնացածներին` "Ոչ": Դրանից հետո նա պայմանականորեն "նշանվում է" այն երկրպագուի հետ, ում նա ավելի է նախընտրում: Առաջին փուլում նախ ա) յուրաքանչյուր չնշանված տղամարդ առաջարկություն է անում այն կնոջը, ում նա ավելի է նախընտրում, և հետո բ) յուրաքանչյուր կին պատասխանում է "հնարավոր է" այն երկրպագուին, ոմ նա ավելի է նախընտրում և "Ոչ"` մնացած երկրպագուներին: Յուրաքանչյուր հաջորդ փուլում նախ ա) յուրաքանչյուր չնշանված տղամարդ առաջարկություն է անում ամենանախընտրելի կնոջը, ում նա դեռ առաջարկություն չի արել (անկախ նրանից` կինը արդեն նշանված է, թե ոչ), և հետո բ) յուրաքանչյուր կին պատասխանում է "հնարավոր է" այն երկրպագուին, ում նա ավելի է նախընտրում (կամ իր գոյություն ունեցող պայմանական զուգընկերը կամ մեկ ուրիշը) և մերժում է մնացածներին (այդ թվում նրա ներկա պայմանական զուգընկերը):

Այս ալգորիթմը երաշխավորում է,որ.

Բոլորը ամուսնանում են

Երբ կինը նշանվում է, նա միշտ նշանված է ինչ-որ մեկի հետ: Այսպիսով, վերջում չի կարող լինել չնշանված կին և տղամարդ, քանի որ նա ինչ-որ պահի պետք է նրան առաջարկություն արած լինի (քանի որ տղամարդը, անհրաժեշտության դեպքում, առաջարկություն է անում բոլորին):

Ամուսնությունները կայուն են

Ենթադրենք Ալիսը և Բոբը նշանված են, բայց ոչ իրար հետ: Ալգորիթմի ավարտից հետո ոչ Ալիսը, ոչ Բոբը չեն կարող ավելի նախընտրել մեկը մյուսին, քան իրենց ներկա զուգընկերոջը: Եթե Բոբը նախընտրում է Ալիսին, քան իր զուգընկերուհուն, ապա նա պետք է նախքան իր ներկա զուգընկերուհուն առաջարկություն անելը Ալիսին առաջարկություն արած լիներ: Եթե Ալիսը ընդուներ նրա առաջարկը քանի դեռ չէր ամուսնացել, նա պետք է լքեր նրան այն մարդու համար, ում նա ավելի շատ է սիրում, այդ պատճառով կարող ենք ասել, որ նա չի սիրում Բոբին ավելի շատ քան իր ներկա զուգընկերոջը: Եթե Ալիսը մերժեց նրա առաջարկը, դա նշանակում է, որ նա այն մարդու հետ է, ում սիրում է ավելի շատ, քան Բոբին:

Ալգորիթմ

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked such woman to whom he has not yet proposed
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    }
}

Լուծման օպտիմալություն

Մինչ լուծումը կայուն է այն պարտադիր կերպով օպտիմալ չէ բոլոր անհատների տեսանկյունից: Ալգորիթմի ավանդական ձևը օպտիմալ է առաջարկներ նախաձեռնողի համար: Օրինակ.

Կան երեք երկրպագու (A,B,C) և երեք գրախոս (X,Y,Z), որոնք ունեն հետևյալ նախապատվությունները.

 A: YXZ  B: ZYX  C: XZY  X: BAC  Y: CBA  Z: ACB

Կա երեք կայուն լուծում.

 երկրպագուները ստանում են իրենց առաջին ընտրությունը, իսկ գրախոսները` երրորդ (AY, BZ, CX)
 բոլոր մասնակիցները ստանում են իրենց երկրորդ ընտրությունը (AX, BY, CZ)
 գրախոսները ստանում են իրենց առաջին ընտրությունը, իսկ երկրպագուները` երրորդ (AZ, BX, CY)

Դրանք բոլորը կայուն են, որովհետև անկայունությունը պահանջում է, որ բոլոր մասնակիցները ուրախ լինեն այլընտրանքային համապատասխանությունից: Յուրաքանչյուրին իրենց երկրորդ ընտրությունը տալը երաշխավորում է, որ որևէ այլ համապատասխանություն կողմերից մեկի համար կլիներ անցանկալի: Ալգորիթմը համընկնում է օպտիմալ լուծման մի կետում, որովհետև յուրաքանչյուր գրախոս ուղղակի ստանում է մեկ առաջարկ, ուստի ընտրում է այդ առաջարկը որպես լավագույն ընտրություն` երաշխավորելով, որ յուրաքանչյուր երկրպագու ունի ընդունված առաջարկ` ավարտելով համապատասխանությունը: Օպտիմալության այս անհամաչափությունը պայմանավորված է նրանով, որ երկրպագուներն ունեն մի ամբողջ շարք ընտրելու համար, բայց գրախոսները ընտրում են երկրպագուների սահմանափակ ենթաբազմությունից ժամանակի ցանկացած պահի:

Նմանատիպ խնդիրներ

Կշռված համապատասխանության խնդիրը (weighted matching problem) փորձում է գտնել համապատասխանություն կշռված երկմասնյա գրաֆում, որն ունի առավելագույն կշիռ: Առավելագույն կշռված համապատասխանությունները պարտադիր չէ, որ լինեն կայուն, բայց որոշ ծրագրերում առավելագույն կշռված համապատասխանությունը ավելի լավն է, քան կայունը:

Կայուն հարևանների խնդիրը (stable roommates problem) նման է կայուն ամուսնության խնդրին,բայց տարբերվում է նրանով, որ բոլոր մասնակիցները պատկանում են միևնույն տեսակին (հավասար թվով "տղամարդկանց" և "կանանց" բաժանված լինելու փոխարեն):

Հիվանդանոցներ/բնակիչներ խնդիրը (hospitals/residents problem) — նաև հայտնի որպես քոլեջի ընդունելության խնդիր — տարբերվում է կայուն ամուսնության խնդրից նրանով, որ "կանայք" կարող են ընդունել "առաջարկություններ" ավելի քան մեկ "տղամարդուց" (օրինակ, հիվանդանոցը կարող է ընդունել բազմաթիվ բնակիչներ, կամ քոլեջը կարող է ընդունել մեկից ավելի ուսանող): Ալգորիթմը, որը լուծում է հիվանդանոցներ/բնակիչներ խնդիրը կարող է լինել հիվանդանոցի կողմնորոշում ունեցող (իգական օպտիմալ) կամ բնակիչների կողմնորոշում ունեցող (արական օպտիմալ):

Հիվանդանոցներ/բնակիչներ խնդիրը զույգերով (hospitals/residents problem with couples) թույլ է տալիս բնակիչների մեծամասնությանը կազմել զույգեր, ովքեր պետք է միասին նշանակված լինեն կամ նույն հիվանդանոցում, կամ զույգի կողմից ընտրված որոշակի զույգ հիվանդանոցներում (օրինակ, ամուսնացած զույգը ցանկանում է երաշխավորել, որ նրանք կմնան միասին և չեն մնա այն ծրագրերում, որոնք գտնվում են իրարից հեռու): Զույգերի ավելացումը հիվանդանոցներ/բնակիչներ խնդրին ներկայացնում է NP-խնդիրը ամբողջությամբ:

Տես նաև

• Assignment problem
• Stable roommates problem a similar problem, but with one set of size n and n-1 preferences

Հղումներ

Դասագրքեր և այլ կարևոր հղումներ, որոնք չեն մեջբերվել տեքստում

• Dubins, L., and Freedman, D. (1981). Machiavelli and the Gale-Shapley algorithm. The American Mathematical Monthly, 88(7), 485–494.
• Knuth, D. E. (1976). Marriages stables. Montreal: Les Presses de I'Universite de Montreal.
• Roth, A. E. (1984). The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92, 991–1016.
• Roth, A. E., and Sotomayor, M. A. O. (1990). Two-sided matching: A study in game-theoretic modeling and analysis. Cambridge University Press.
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press. ISBN 978-0-521-89943-7. See Section 10.6.4; downloadable free online.
• Schummer, J., and Vohra, R. V. (2007). Mechanism design without money. In Nisan, N., Roughgarden, T., Tardos, E., and Vazirani, V. (Eds.). (2007). Algorithmic game theory. Cambridge, UK: Cambridge University Press, chapter 10, 243–265.
• Kleinberg, J., and Tardos, E. (2005) Algorithm Design, Chapter 1, pp 1–12. See companion website for the Text [1].

Արտաքին հղումներ

• Interactive Flash Demonstration of SMP
• http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
• http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
• Gale-Shapley JavaScript Demonstration
• SMP Lecture Notes

Category:Game theory Category:Cooperative games Category:Mathematical problems Category:Matching hy:Կայուն ամուսնության խնդիրը