Bài toán hôn nhân bền vững

Trong toán học và khoa học máy tính, bài toán hôn nhân bền vững (SMP) yêu cầu tìm một cặp ghép bền vững giữa các phần tử của hai tập hợp theo thứ tự ưu tiên của mỗi phần tử. Một cặp ghép là một ánh xạ từ các phần tử của tập hợp này tới các phần tử của tập hợp kia. Một cặp ghép là bền vững nếu hai điều kiện sau không đồng thời xảy ra:

1. Một phần tử A của tập hợp thứ nhất thích phần tử B của tập hợp thứ hai hơn phần tử được ghép với A, và
2. B cũng thích A hơn phần tử được ghép với B

Nói cách khác, một tổ hợp ghép là bền vững nếu không tồn tại cặp (A, B) trong đó cả A và B đều thích phần tử kia hơn phần tử được ghép với chúng.

Bài toán hôn nhân bền vững thường được phát biểu như sau:

Có n người đàn ông và n phụ nữ, trong đó mỗi người xếp hạng tất các mọi người khác giới từ 1 đến n theo thứ tự ưu tiên, cần tìm cách tổ thức hôn nhân sao cho không tồn tại hai người khác giới yêu nhau hơn vợ/chồng của họ. Nếu không tồn tại những người như vậy thì tất cả các cuộc hôn nhân được xem là "bền vững."

Thuật toán để tìm lời giải cho bài toán hôn nhân bền vững được áp dụng cho nhiều bài toán thực tế, nổi tiếng nhất là cho việc phân công các bác sĩ mới tốt nghiệp đến các bệnh viện.

Lời giải

Hình minh họa một ví dụ của thuật toán Gale-Shapley

Năm 1962, David Gale và Lloyd Shapley chứng minh rằng, với số lượng đàn ông và phụ nữ bằng nhau, luôn tồn tại lời giải bền vững cho SMP. Họ đưa ra một thuật toán để tìm lời giải đó.

Thuật toán Gale-Shapley bao gồm nhiều "lượt" trong đó mỗi người đàn ông chưa đính hôn "cầu hôn" người phụ nữ anh ta thích nhất mà trước đó chưa cầu hôn. Mỗi phụ nữ xem xét tất cả mọi người cầu hôn và trả lời người cô thích nhất "có thể" và từ chối tất cả những người còn lại. Tạm thời cô được "đính hôn" với người đàn ông được cô chọn và anh ta cũng tạm thời "đính hôn" với cô. Như vậy trong lượt đầu tiên, đầu tiên a) mỗi người đàn ông cầu hôn người phụ nữ anh thích nhất, rồi b) mỗi người phụ nữ trả lời "có thể" với người cô thích nhất và từ chối tất cả những người khác. Ở những lượt tiếp theo, đầu tiên a) mỗi người đàn ông chưa đính hôn cầu hôn người phụ nữ anh ta thích nhất mà anh ta chưa cầu hôn trước đó (bất kể người đó có đang đính hôn hay không), sau đó b) mỗi người phụ nữ trả lời "có thể" với người cầu hôn cô thích nhất (bất kể đó là người đính hôn tạm thời hay người khác) và từ chối tất cả những người khác (có thể bao gồm cả người đính hôn tạm thời). Việc đính hôn tạm thời cho phép người phụ nữ đã đính hôn có thể tìm được người ngày càng tốt hơn ở những lượt về sau.

Thuật toán này đảm bảo rằng:

Tất cả mọi người đều được kết hôn

Sau khi một phụ nữ đã đính hôn, cô luôn đính hôn với một người nào đó. Do đó cuối cùng không thể tồn tại một người đàn ông và một người phụ nữ đều chưa đính hôn vì anh ta nhất định cầu hôn với cô tại một thời điểm nào đó (vì một người đàn ông cuối cùng có thể cầu hôn với tất cả mọi phụ nữ nều cần thiết) và do cô chưa đính hôn, cô sẽ trả lời đồng ý.

Hôn nhân bền vững

Giả sử Alice là một phụ nữ và Bob là một người đàn ông đều đã đính hôn, nhưng không đính hôn với nhau. Tại thời điểm thuật toán kết thúc, không thể xảy ra trường hợp cả Alice và Bob đều thích người kia hơn vợ/chồng của họ. Nếu Bob thích Alice hơn vợ anh ta, anh ta nhất định đã cầu hôn Alice trước khi cầu hôn vợ mình. Nếu Alice chấp nhận lời cầu hôn đó nhưng cuối cùng không kết hôn với Bob, cô nhất định bỏ anh ta theo một người khác cô thích hơn. Nếu Alice từ chối lời cầu hôn, cô nhất định đã đính hôn với người cô thích hơn Bob.

Thuật toán

function stableMatching {
    Khởi tạo m ∈ M và w ∈ W bằng độc thân
    while ∃ người đàn ông độc thân m vẫn còn có người phụ nữ w để cầu hôn {
       w = người phụ nữ m thích nhất mà vẫn chưa cầu hôn
       if w độc thân
         (m, w) trở thành đã đính hôn
       else một cặp (m', w) đã đính hôn
         if w thích m to m'
           (m, w) trở thành đã đính hôn
           m' trở thành độc thân
         else
           (m', w) vẫn đã đính hôn
    }
}