Kararlı Evlilik Problemi

Kararlı Evlilik Problemi (Stable Marriage Problem), Gale - Shapley Algoritması ile ilk defa David Gale ve Lloyd Shapley tarafından ortaya konmuştur (1962). Buna göre n sayıda erkek ve yine n sayıda kadının evlenmek için bir oluşum içinde olduğunu farzedelim. Burada temel ilke n sayıda üyesi olan iki grubun da tercihlerini çelişkiye yer vermeyen belirli bir düzende yapabilmesine dayanır (strict preferences). Kararlılık (stability) esastır; burada kararlılık en az bir çiftin daha iyi bir seçenekle beraber olamayacağına, yani çiftlere mensup tarafların karşılıklı olarak kendileri için daha iyi bir birleşim (matching) yapamayacağı ilkesine dayanır. Örnek vermek gerekirse:

4 erkek (1, 2, 3, 4) ve 4 kadın (A, B, C, D) olsun. Bunlar tercihlerini aşağıdaki sıraya göre dizsinler:

P(1): (A, B, C, D) --- P(A): (3, 4, 2, 1)
P(2): (B, A, C, D) --- P(B): (1, 4, 3, 2)
P(3): (C, D, B, A) --- P(C): (1, 3, 2, 4)
P(4): (D, B, C, A) --- P(D): (3, 1, 4, 2)

Buna göre 1, ilk tercihi olan A'ya teklifte bulunur, eğer A'nın son tercihiyse reddedilir, aksi takdirde kabul (daha iyi teklifle karşılaşılana kadar) edilir. Aynı şekilde 2, B'ye teklif götürür ve 1 gibi o da reddedilir. 3, C'ye teklif götürdüğünde C, en son tercihi olmaması dolayısı ile kabul eder (daha iyi bir tercihle karşılaşana kadar). Nihayetinde 4 de D'ye teklif götürür ve aynı şekilde onay alır. İkinci basamakta 1, ikinci en iyi favorisine (B) teklif götürür ve B şimdiye kadar daha iyi teklif almadığı (aynı zamanda favorisi olduğu için) kabul eder. 2 de aynı şekilde A'ya teklif götürür ve A da kabul eder (daha iyi teklif almamıştır). Böylece M = [(1,B), (2,A), (3,C), (4,D)] kararlı evliliklerdir, çünkü hiçbir kadın - erkek çiftinin olası birlikteliği şimdiki durumlarından daha iyi değildir. Aynı mekanizma önce kadınların (A, B, C, D) erkeklere (1, 2, 3, 4) aynı teklifte bulunmasıyla da çalışır ve sonuçta kararlı evlilikler bulunur. Kararlı evlilikler aynı zamanda en uygun (optimal) evliliklerdir, çünkü birlikteliği olası bir çiftte iki taraf da şimdiki konumundan daha iyi durumda olamayacaktır. Algoritma (deferred acceptence algorithm) sayıları eşit olmayan iki grup için de geçerlidir fakat strategy - proof (bireylerin gerçek tercihlerini açıklama isteğinin herkes için baskın strateji olma durumu) değildir. Buna bağlı olarak "imkansızlık teoremi" de kararlı bir mekanizmanın strategy - proof olamayacağını vurgular.