穩定婚配問題?

穩定婚姻系統中什麼時候存在多個解? 5分

話說在1962年，兩個數學家David Gale 和Lloyd Shapley提出了下面的問題：

給定若干個男生和同樣多的女生，他們每個人都對所有的異性有一個心理的偏好次序。是否存在一種男女配對組合構成一種穩定的組合關係？這裡穩定組合的意思是說，不存在兩個非伴侶的異性對彼此的評價比對各自伴侶的評價還要高。（可以理解，這樣的異性太容易紅杏出牆了，所以是某種不穩定因素。）進一步的問題是，在已知每個人對異性的偏好順序的情況下，怎樣求出這種穩定組合方式（如果它存在的話）？你可以理解為這是數學家們替月老問的問題：給定一群孤男寡女，尋找一種牽紅線的方式，以確保把紅杏扼殺在搖籃裡。

這一問題被稱為穩定婚姻問題。它有很多種可能的解法。為了讓大家相信數學家不是真得如此無聊，我要指出它確確實實是一個地道的組合數學問題，有其特定的數學價值。當然啦，它也有很多別的背景和應用，比如用來在若干個公司和應聘者之間進行招聘中介……但是數學家們怎麼會放過如此八卦的一個名字呢？於是它就這樣流傳下來了。

給定每個人關於異性的偏好排序，要尋找一種男女配對組合構成穩定的組合。Gale和Shapley不但提出了這個問題本身，而且給出了一種著名的解法。這個解法可以描述為如下的求偶過程：

首先，讓這些男生去向他們最心儀的女生求婚——這是數學家們的原本的用詞。如果你覺得太快了的話，讓我們暫時改成表白吧……

然後，等所有男生表白完畢後，所有的收到表白女生們都從自己的表白者中選擇自己最喜歡的人接受為男朋友。沒人表白的女生只能暫時等一等了，不要著急，表白會有的。

以上過程稱為“一輪”。之後的每一輪都按照類似的方式進行。首先由還處於單身狀態的男生們每個人再次向自己還沒有表白過的女生中自己最喜歡的人表白（無論人家是否已經有了男朋友），然後，等所有單身男生表白完畢後，所有的收到表白女生們都從自己的表白者中選擇自己最喜歡的人接受為男朋友。如果原來有男朋友而表白者中有自己更喜歡的，不要猶豫，換之。等到塵埃落定之後，再開始如上所述的新的一輪表白。

依此類推。可以證明的是，這個過程一定是會終止的，也就是說，不會陷入任何死迴圈。並且一旦終止，每個人都會找到一個伴侶。更關鍵的是，這個過程最終得到的一定是如前所述的“穩定組合”：不存在兩個非伴侶的異性對彼此的評價比對各自伴侶的評價還要高。——這幾個事實都不難證明，有興趣的話可以自己試試看。

所以這就得到了穩定婚姻問題的一個解（順便也證明了解的存在性）。但是真正有趣的部分還在後面。一般來說，給定若干個男生女生和他們之間的偏好關係，穩定組合存在不止一種。上述“演算法”只是給出了所有可能的穩定組合其中之一而已。但是這個特定的解具有某些特別的性質：可以證明（這一次證明不很容易了），上述方式得到的穩定組合和所有其他的可能的穩定組合相比，是對男生最優而對女生最劣的。

確切地說是這樣：

它是對男生最優的。也就是說，對每個男生來說，按照這種方式最後找到的伴侶，是在所有的穩定組合中自己可能具有的伴侶中自己評價最高的。——注意這並不等於說被個男生都能追到自己最喜歡的女生，而只是說，他一定能追到“有可能和他在穩定組合中在一起的女生”中自己最喜歡的。有些女生雖然很好，但是和他在一起是不可能形成穩定組合的。這就是人生啊……

另一方面，它是對女生最劣的。也就是說，對每個女生來說，按照這種方式最後找到的伴侶是在所有的穩定組合中自己可能具有的伴侶中自己評價最低的。同樣的，這也不等於說每個女生都只有和自己最不喜歡的男生在一起，而只是說她最後的男......餘下全文>>

時好時壞,若能穩定婚姻可成。是什麼意思

把問題描述清楚啊