Trình giải Bài toán Hôn nhân Ổn định

Giới thiệu về Trình giải Bài toán Hôn nhân Ổn định

Trình giải Bài toán Hôn nhân Ổn định là một bản triển khai tương tác của thuật toán chấp nhận trì hoãn Gale-Shapley, thuật toán ghép đôi năm 1962 mà David Gale và Lloyd Shapley đã chứng minh luôn tạo ra một cặp đôi ổn định giữa hai nhóm có kích thước bằng nhau khi biết xếp hạng sở thích đầy đủ của mỗi thành viên đối với bên kia. Công cụ này tiếp nhận danh sách sở thích của bạn, chạy thuật toán từng bước và hiển thị kết quả dưới dạng ghép đôi ổn định, hoạt ảnh trực quan hai phía, bản đồ nhiệt sở thích và bằng chứng đã được xác minh rằng không tồn tại cặp ngăn chặn nào.

Bài toán hôn nhân ổn định là gì?

Cho hai tập hợp rời nhau có cùng kích thước — ví dụ: n nam và n nữ, hoặc n ứng viên và n vị trí — và một danh sách sở thích đầy đủ từ mọi thành viên xếp hạng mọi thành viên của bên kia, một phép ghép đôi là một sự kết hợp một-một giữa hai tập hợp. Việc ghép đôi được gọi là ổn định nếu không có cặp (a, b) nào nằm ngoài phép ghép đôi đó mà cả hai đều muốn ở bên nhau hơn là ở với đối tác đã được chỉ định của họ.

Về mặt toán học, một phép ghép đôi M là ổn định nếu không tồn tại cặp ngăn chặn — một cặp (a, b) với a được ghép với b' và b được ghép với a' sao cho:

Nếu cả hai điều kiện đều đúng, cả a và b sẽ rời bỏ đối tác hiện tại của họ, làm mất tính ổn định của phép ghép đôi. Một phép ghép đôi ổn định là phép ghép đôi không tồn tại cặp như vậy.

Thuật toán Gale-Shapley

Gale và Shapley đã chứng minh — bằng phương pháp xây dựng — rằng một phép ghép đôi ổn định luôn tồn tại cho bất kỳ tập hợp sở thích nào và họ đã đưa ra một thuật toán hiệu quả để tìm ra nó. Thuật toán chạy theo từng vòng:

1. Mọi người cầu hôn chưa được ghép đôi sẽ cầu hôn người nhận được xếp hạng cao nhất trong danh sách của họ mà chưa từ chối họ.
2. Mỗi người nhận được một hoặc nhiều lời cầu hôn sẽ chọn người mà họ thích nhất (so với bất kỳ người cầu hôn tạm thời hiện tại nào) và tạm thời chấp nhận; những người khác bị từ chối.
3. Những người cầu hôn bị từ chối sẽ trở nên tự do trở lại và chuyển sang lựa chọn tiếp theo của họ trong vòng tiếp theo.
4. Thuật toán kết thúc khi mọi người cầu hôn đều đã được ghép đôi — điều này được đảm bảo sẽ xảy ra trong tối đa n² lần cầu hôn.

Các tính chất lý thuyết chính

Sự tồn tại & Tính duy nhất

Một phép ghép đôi ổn định luôn tồn tại (Gale & Shapley, 1962), nhưng không nhất thiết là duy nhất. Đối với một tập hợp sở thích nhất định, có thể có nhiều phép ghép đôi ổn định và chúng tạo thành một cấu trúc lưới (lattice) được sắp xếp theo sở thích chung.

Tính tối ưu cho người đề nghị

Khi một bên thực hiện cầu hôn, Gale-Shapley tạo ra ghép đôi ổn định tối ưu cho người đề nghị: mọi người cầu hôn đều nhận được đối tác tốt nhất mà họ có thể được ghép đôi trong bất kỳ phép ghép đôi ổn định nào. Ngược lại, đây cũng là phép ghép đôi tệ nhất cho người nhận — bên nhận được đối tác ổn định kém nhất của họ. Việc đổi bên cầu hôn trong công cụ này thường làm thay đổi kết quả.

Tính kháng chiến thuật đối với người đề nghị

Theo Gale-Shapley, người cầu hôn không có động lực để báo cáo sai sở thích của mình: nói thật là chiến lược tối ưu cho họ. Tuy nhiên, người nhận đôi khi có thể hưởng lợi từ việc báo cáo sai chiến thuật — một trong những lý do khiến thị trường nội trú y tế tại Hoa Kỳ được thiết kế với sinh viên là bên cầu hôn.

Định lý Bệnh viện Nông thôn

Tập hợp các tác nhân không được ghép đôi là giống hệt nhau trong tất cả các phép ghép đôi ổn định. Vì vậy, nếu trường hợp của bạn có kích thước không cân bằng (ngoài phạm vi của công cụ cổ điển này), những người giống nhau sẽ không được ghép đôi trong mọi giải pháp ổn định.

Định dạng đầu vào

Trình giải này yêu cầu mỗi thành viên trên một dòng, với tên theo sau là dấu hai chấm và danh sách sở thích xếp hạng đầy đủ cách nhau bởi dấu phẩy:

Yêu cầu:

• Cả hai nhóm phải có chính xác cùng số lượng thành viên.
• Mọi thành viên phải xếp hạng mọi thành viên của nhóm kia — không chấp nhận danh sách một phần.
• Tên có thể sử dụng chữ cái, chữ số, dấu gạch dưới, dấu gạch nối, khoảng trắng và các ký tự Unicode thông thường.
• Hỗ trợ tối đa 15 thành viên mỗi bên để đảm bảo hoạt ảnh tương tác nhanh.

Cách sử dụng công cụ này

1. Nhập sở thích cho Nhóm A trong vùng văn bản bên trái — mỗi dòng một thành viên, danh sách xếp hạng đầy đủ.
2. Nhập sở thích cho Nhóm B trong vùng văn bản bên phải — định dạng tương tự.
3. Chọn bên cầu hôn. Chọn Nhóm A hoặc Nhóm B. Hãy thử cả hai để so sánh kết quả tối ưu cho A so với tối ưu cho B.
4. Nhấp vào "Giải quyết Ghép đôi Ổn định." Công cụ sẽ chạy Gale-Shapley và tạo ra các cặp ổn định, số liệu thống kê, hoạt ảnh và bằng chứng về tính ổn định.
5. Theo dõi hoạt ảnh bằng các nút điều khiển phát / bước / đặt lại để xem từng đề nghị, chấp nhận, thay đổi và từ chối theo thứ tự.
6. Kiểm tra bản đồ nhiệt. Mỗi ô hiển thị thứ hạng; các ô có viền vàng tạo thành phép ghép đôi cuối cùng — hãy xem các ô đó nằm cao hay thấp để biết mức độ "hạnh phúc" của mỗi bên.

Ví dụ minh họa — Cổ điển 3×3

Nam: Alex, Bryan, Chris. Nữ: Bea, Claire, Diana. Sở thích:

Chạy Gale-Shapley với nam là người cầu hôn sẽ mang lại kết quả Alex–Bea, Bryan–Claire, Chris–Diana ngay trong vòng đầu tiên (mỗi người đàn ông đều khớp với lựa chọn đầu tiên của họ và người phụ nữ đó cũng thích họ nhất hoặc không có xung đột). Phép ghép đôi này ổn định: không có cặp nam-nữ nào cả hai đều thấy tốt hơn nếu đổi đối tác, vì vậy không có cặp ngăn chặn.

Ứng dụng thực tế

Tại sao Lloyd Shapley giành giải Nobel

Năm 2012, Viện Hàn lâm Khoa học Hoàng gia Thụy Điển đã trao Giải Nobel Kinh tế cho Lloyd Shapley (về mặt lý thuyết, cùng với David Gale đã qua đời) và Alvin Roth (vì đã áp dụng lý thuyết vào các thị trường thực tế, bao gồm cả việc thiết kế lại hệ thống ghép đôi nội trú y tế Hoa Kỳ và mạng lưới trao đổi thận). Giải thưởng ghi nhận "lý thuyết về phân bổ ổn định và thực tiễn thiết kế thị trường."

Câu hỏi thường gặp

Bài toán hôn nhân ổn định là gì?

Bài toán hôn nhân ổn định đặt câu hỏi: cho hai nhóm có kích thước bằng nhau, trong đó mỗi thành viên xếp hạng tất cả các thành viên của nhóm kia từ thích nhất đến ít thích nhất, liệu chúng ta có thể ghép đôi mọi người sao cho không có hai người nào đều muốn rời bỏ đối tác hiện tại của họ để đến với nhau? Một cách ghép đôi như vậy được gọi là ghép đôi ổn định. Thuật toán Gale-Shapley giải quyết vấn đề này trong thời gian O(n²) và luôn tìm thấy một kết quả ghép đôi ổn định.

Thuật toán Gale-Shapley hoạt động như thế nào?

Thuật toán chấp nhận trì hoãn Gale-Shapley tiến hành theo từng vòng. Trong mỗi vòng, mỗi người cầu hôn hiện đang tự do sẽ cầu hôn người nhận được xếp hạng cao nhất trong danh sách của họ mà chưa từ chối họ. Mỗi người nhận sẽ tạm thời chấp nhận đề nghị tốt nhất nhận được cho đến nay và từ chối những người còn lại; bất kỳ người cầu hôn nào bị thay thế sẽ trở nên tự do trở lại. Thuật toán kết thúc khi không còn người cầu hôn nào tự do, điều này xảy ra trong tối đa n² lần cầu hôn.

Kết quả ghép đôi ổn định có duy nhất không?

Không. Một trường hợp bài toán hôn nhân ổn định có thể có nhiều cách ghép đôi ổn định. Tuy nhiên, khi một bên cầu hôn, Gale-Shapley luôn tạo ra kết quả ghép đôi ổn định tối ưu cho bên cầu hôn: mọi người cầu hôn đều có được đối tác tốt nhất mà họ có thể có được trong bất kỳ cách ghép đôi ổn định nào. Theo tính đối xứng, đây cũng là kết quả ghép đôi tệ nhất cho bên nhận. Việc đổi bên cầu hôn thường mang lại một kết quả ghép đôi ổn định khác.

Cặp ngăn chặn là gì?

Cặp ngăn chặn là một cặp (a, b) hiện không được ghép đôi trong đó a thích b hơn đối tác hiện tại của họ VÀ b cũng thích a hơn đối tác hiện tại của họ. Nếu tồn tại bất kỳ cặp ngăn chặn nào, việc ghép đôi đó là không ổn định vì hai người đó thà kết đôi với nhau hơn. Một kết quả ghép đôi ổn định không có cặp ngăn chặn, điều mà công cụ này xác minh tự động sau mỗi lần giải.

Các ứng dụng thực tế của ghép đôi ổn định là gì?

Thuật toán Gale-Shapley vận hành Chương trình Ghép đôi Nội trú Quốc gia tại Hoa Kỳ, hệ thống lựa chọn trường học ở Boston và New York, tuyển sinh đại học ở một số quốc gia, và các hệ thống trao đổi thận hoặc phân bổ bạn cùng phòng. Lloyd Shapley và Alvin Roth đã giành giải Nobel Kinh tế năm 2012 một phần nhờ công trình này.

Cả hai nhóm có cần cùng kích thước không?

Trong công thức bài toán hôn nhân ổn định cổ điển, là có. Cả hai bên phải có cùng số lượng thành viên và mỗi người phải cung cấp bảng xếp hạng đầy đủ về bên kia. Các biến thể không cân bằng hiện có nhưng yêu cầu thuật toán sửa đổi. Trình giải này bắt buộc kích thước bằng nhau và danh sách sở thích đầy đủ.

Đọc thêm

• Bài toán hôn nhân ổn định — Wikipedia
• Thuật toán Gale-Shapley — Wikipedia
• Chương trình Ghép đôi Nội trú Quốc gia — Wikipedia
• Giải Nobel Kinh tế 2012 — Shapley & Roth