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:
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:
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.[1]
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 đó.[2][3]
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:
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 } }