Thuật toán Gale–Shapley là cách ghép hai nhóm người với nhau (sinh viên với trường, bác sĩ với bệnh viện, người với người) sao cho kết quả ổn định: không có cặp nào ở ngoài cùng muốn bỏ người đang được ghép để về với nhau. Một bên lần lượt đề nghị theo thứ tự mình thích, bên kia giữ tạm lời đề nghị tốt nhất và từ chối phần còn lại, lặp tới khi không ai còn bị từ chối. David Gale và Lloyd Shapley công bố cách làm này năm 1962 và chứng minh nó luôn dừng, luôn cho một cách ghép ổn định.
Bài toán: "ổn định" nghĩa là gì
Hình dung một khoa có bốn sinh viên làm khoá luận và bốn thầy cô hướng dẫn, mỗi thầy nhận đúng một em. Sinh viên nào cũng xếp hạng bốn thầy theo ý mình; thầy nào cũng xếp hạng bốn em. Văn phòng khoa cần ra một bảng phân công.
Bảng phân công bị coi là không ổn định nếu có một sinh viên X và một thầy Y thoả cả hai điều:
- X thích Y hơn người thầy X đang được phân;
- Y cũng thích X hơn em sinh viên Y đang được phân.
Cặp X–Y như thế gọi là cặp chặn (blocking pair). Nếu có cặp chặn, hai người đó có lý do để bỏ bảng phân công mà thoả thuận riêng với nhau, và cả hệ thống bắt đầu rạn từ chỗ ấy. Một cách ghép không có cặp chặn nào gọi là ghép cặp ổn định.
Lưu ý: ổn định không có nghĩa là ai cũng vui. Một người có thể nhận lựa chọn cuối bảng của mình mà cách ghép vẫn ổn định, miễn là mọi người họ thích hơn đều đang có người mà chính những người đó thích hơn họ.
Thuật toán chấp nhận hoãn, từng bước
Bài báo của Gale và Shapley có tên "College Admissions and the Stability of Marriage" (Tuyển sinh đại học và sự ổn định của hôn nhân), đăng trên tạp chí American Mathematical Monthly năm 1962. Hai ông kể bằng ngôn ngữ cầu hôn cho dễ hình dung, nhưng tên gọi chuyên môn hiện nay là thuật toán chấp nhận hoãn (deferred acceptance). Ba quy tắc:
- Đề nghị: mỗi người bên đề nghị chưa có chỗ gửi lời tới lựa chọn cao nhất trong danh sách mà mình chưa bị từ chối.
- Giữ tạm: mỗi người bên nhận xem tất cả lời đang có trong tay (kể cả lời đang giữ từ vòng trước), giữ lại lời tốt nhất theo bảng xếp hạng của mình, từ chối hết phần còn lại.
- Lặp: ai bị từ chối thì vòng sau đi tiếp xuống lựa chọn kế tiếp. Khi không còn ai bị từ chối, mọi lời đang giữ trở thành chính thức.
Chữ "hoãn" nằm ở bước 2: bên nhận không bao giờ nhận ngay. Lời đang giữ có thể bị thay nếu vòng sau có người tốt hơn tới. Chính việc không chốt sớm này làm nên toàn bộ sức mạnh của thuật toán.
Tính tay một ví dụ bốn người
Bốn sinh viên An, Bình, Chi, Dũng; bốn thầy cô ký hiệu P, Q, R, S. Bảng nguyện vọng (trái sang phải là thích nhất đến kém nhất):
| Sinh viên | Thứ tự thích | Thầy cô | Thứ tự thích |
|---|---|---|---|
| An | R, S, Q, P | P | Dũng, An, Bình, Chi |
| Bình | Q, R, P, S | Q | An, Chi, Dũng, Bình |
| Chi | R, S, P, Q | R | Dũng, Chi, Bình, An |
| Dũng | S, P, Q, R | S | Bình, Chi, Dũng, An |
Cho sinh viên là bên đề nghị.
| Vòng | Ai gửi lời tới đâu | Bên nhận quyết định | Đang giữ sau vòng |
|---|---|---|---|
| 1 | An → R, Chi → R, Bình → Q, Dũng → S | R có An và Chi, thích Chi hơn: giữ Chi, từ chối An | R–Chi, Q–Bình, S–Dũng |
| 2 | An → S | S có Dũng và An, thích Dũng hơn: từ chối An | không đổi |
| 3 | An → Q | Q có Bình và An, thích An hơn: giữ An, từ chối Bình | R–Chi, Q–An, S–Dũng |
| 4 | Bình → R | R có Chi và Bình, thích Chi hơn: từ chối Bình | không đổi |
| 5 | Bình → P | P chưa giữ ai: giữ Bình | R–Chi, Q–An, S–Dũng, P–Bình |
Hết người bị từ chối, thuật toán dừng sau 5 vòng: An–Q, Bình–P, Chi–R, Dũng–S.
Kiểm tra không có cặp chặn
Chỉ cần xét những thầy mà mỗi em thích hơn chỗ mình được:
- An thích R và S hơn Q. Nhưng R đang có Chi (R xếp Chi trên An), S đang có Dũng (S xếp Dũng trên An). Không chặn.
- Bình thích Q và R hơn P. Q đang có An (Q xếp An đầu bảng), R đang có Chi (R xếp Chi trên Bình). Không chặn.
- Chi và Dũng đều được lựa chọn số một, không có gì để chặn.
Kết quả ổn định, đúng như định lý hứa.
Đổi bên đề nghị thì kết quả đổi
Chạy lại, lần này để thầy cô là bên đề nghị. Vòng 1: P và R cùng gửi lời tới Dũng, Q tới An, S tới Bình. Dũng thích P hơn R nên giữ P, từ chối R. Vòng 2: R gửi tới lựa chọn thứ hai là Chi, Chi chưa giữ ai nên giữ. Dừng: An–Q, Bình–S, Chi–R, Dũng–P.
| Người | Khi sinh viên đề nghị | Khi thầy cô đề nghị |
|---|---|---|
| Bình | P (lựa chọn 3) | S (lựa chọn 4) |
| Dũng | S (lựa chọn 1) | P (lựa chọn 2) |
| Thầy P | Bình (lựa chọn 3) | Dũng (lựa chọn 1) |
| Thầy S | Dũng (lựa chọn 3) | Bình (lựa chọn 1) |
| An, Chi, Q, R | giống nhau ở cả hai lần chạy | |
Cả hai kết quả đều ổn định, và với bảng nguyện vọng này chỉ có đúng hai cách ghép ổn định (kiểm bằng cách thử hết 24 hoán vị). Điều đáng chú ý: bên nào đề nghị thì bên đó được lợi. Gale và Shapley chứng minh kết quả khi một bên đề nghị là cách ghép ổn định tốt nhất cho từng người bên đó, đồng thời là cách ghép ổn định tệ nhất cho từng người bên kia. Không phải tốt nhất "trung bình", mà tốt nhất cho từng người cùng lúc, một điều nghe tưởng không thể có.
Khi có nhiều cách ghép ổn định, chúng xếp thành một cấu trúc gọn gàng mà các nhà toán học gọi là dàn: một đầu là phương án tốt nhất cho bên này, đầu kia là phương án tốt nhất cho bên kia, các phương án khác nằm giữa. Donald Knuth trình bày kỹ cấu trúc này trong cuốn sách nhỏ "Mariages stables" năm 1976, ghi nhận ý tưởng của John Conway.
Vì sao thuật toán luôn dừng và luôn ổn định
Luôn dừng
Mỗi người bên đề nghị chỉ đi xuống danh sách, không bao giờ quay lại người đã từ chối mình. Với n người mỗi bên, mỗi người đề nghị tối đa n lần, nên tổng số lời đề nghị không vượt n². Phân tích kỹ hơn cho giới hạn n² − n + 1. Với 4 người là tối đa 13 lời; ví dụ trên dùng 8 lời. Với 1.000 người mỗi bên, máy tính xử lý trong chớp mắt.
Ai cũng có chỗ
Khi số người hai bên bằng nhau và ai cũng chấp nhận mọi người bên kia, không ai bị bỏ rơi. Lý do: một người bên nhận một khi đã giữ lời thì luôn giữ một lời nào đó, chỉ đổi sang lời tốt hơn. Nếu một sinh viên bị cả bốn thầy từ chối, nghĩa là cả bốn thầy đều đang giữ người khác, tức có bốn sinh viên khác, vô lý vì chỉ có ba người còn lại.
Không có cặp chặn
Giả sử sau cùng An thích thầy R hơn chỗ mình được. Vì An đề nghị theo thứ tự từ trên xuống, An chắc chắn đã gửi lời tới R trước và bị R từ chối. R chỉ từ chối An khi đang giữ người R thích hơn, và về sau R chỉ đổi lên chứ không đổi xuống. Vậy người R giữ cuối cùng được R thích hơn An, nên An–R không thể là cặp chặn. Lập luận này áp cho mọi cặp.
Có nên khai thật nguyện vọng
Với bên đề nghị, câu trả lời là có: không ai trong bên đề nghị có thể tự làm lợi cho mình bằng cách khai sai thứ tự, bất kể người khác khai gì. Kết quả này được Lester Dubins và David Freedman (1981) cùng Alvin Roth (1982) chứng minh. Đó là lý do các hệ thống xét tuyển hiện đại để thí sinh là bên "đề nghị": thí sinh chỉ việc xếp thật lòng.
Bên nhận thì khác. Trong ví dụ trên, giả sử thầy P khai rằng mình không nhận Bình. Năm vòng đầu y như cũ, nhưng ở vòng 5 Bình bị P từ chối. Vòng 6, Bình gửi lời tới S; S thích Bình hơn Dũng nên đổi, từ chối Dũng. Vòng 7, Dũng gửi tới lựa chọn thứ hai là P, và P có đúng người mình muốn nhất. Chỉ một lời khai sai, P chuyển từ lựa chọn số 3 lên số 1. Roth cũng chứng minh không có thuật toán ghép ổn định nào khiến cả hai bên đều không có động cơ khai sai. Phải chọn bảo vệ một bên, và thường người ta chọn bảo vệ bên yếu thế hơn, ít thông tin hơn: thí sinh, bác sĩ trẻ.
Một chuyện bên lề về chữ "hôn nhân"
Ví von cầu hôn khiến bài toán nổi tiếng là "bài toán hôn nhân bền vững". Nhưng ngay trong bài báo năm 1962, mối quan tâm thật của hai tác giả là tuyển sinh: một trường nhận nhiều sinh viên, gọi là ghép nhiều–một. Thuật toán mở rộng gần như nguyên vẹn: mỗi trường giữ tạm bấy nhiêu lời tốt nhất bằng chỉ tiêu của mình thay vì một lời. Đó chính là xương sống của các hệ thống xét tuyển theo nguyện vọng ngày nay.
Góc nhìn hôm nay: tự chạy thử
Thuật toán đủ đơn giản để làm trên giấy với một nhóm nhỏ. Vài gợi ý để hiểu sâu hơn:
- Lấy bảng nguyện vọng ở trên, đổi một dòng (chẳng hạn cho Chi thích S nhất) rồi chạy lại cả hai chiều. Xem số cách ghép ổn định tăng hay giảm.
- Thử bảng "vòng tròn" ba người: An xếp P, Q, R; Bình xếp Q, R, P; Chi xếp R, P, Q; còn P xếp Bình, Chi, An; Q xếp Chi, An, Bình; R xếp An, Bình, Chi. Sinh viên đề nghị thì sinh viên được hết lựa chọn số một; thầy đề nghị thì thầy được hết lựa chọn số một. Cách ghép ai cũng nhận lựa chọn thứ hai cũng ổn định.
- Đếm số lời đề nghị và so với giới hạn n² − n + 1.
Muốn đọc thêm: bài báo gốc chỉ 7 trang và dễ đọc; cuốn "Who Gets What — and Why" của Alvin Roth (2015) kể các ứng dụng thật bằng lời thường; giáo trình "Two-Sided Matching" của Roth và Marilda Sotomayor (1990) dành cho ai muốn chứng minh chặt chẽ.
Câu hỏi thường gặp
Thuật toán Gale–Shapley là gì?
Là thuật toán ghép hai nhóm theo nguyện vọng: một bên lần lượt đề nghị, bên kia giữ tạm lời tốt nhất và từ chối phần còn lại, lặp đến khi không ai bị từ chối. Kết quả luôn là một cách ghép ổn định, tức không có hai người nào cùng muốn bỏ chỗ hiện tại để đến với nhau.
Ghép cặp ổn định là gì?
Là cách ghép không có cặp chặn: không tồn tại hai người ở hai bên cùng thích nhau hơn người mình đang được ghép. Ổn định không có nghĩa ai cũng được lựa chọn số một, chỉ có nghĩa không ai có cả lý do lẫn đối tác để phá vỡ kết quả.
Gale và Shapley công bố thuật toán năm nào?
Năm 1962, trong bài "College Admissions and the Stability of Marriage" trên tạp chí American Mathematical Monthly. Lloyd Shapley nhận giải Nobel Kinh tế năm 2012 cùng Alvin Roth; David Gale đã mất năm 2008 nên không được trao.
Bên nào có lợi trong thuật toán Gale–Shapley?
Bên đề nghị. Kết quả là cách ghép ổn định tốt nhất cho từng người bên đề nghị và tệ nhất cho từng người bên nhận. Vì vậy các hệ thống xét tuyển thường để thí sinh là bên đề nghị.
Có nên khai sai thứ tự nguyện vọng để được lợi không?
Nếu bạn ở bên đề nghị thì không: khai thật là tốt nhất cho bạn dù người khác khai thế nào. Bên nhận về lý thuyết có thể được lợi nhờ khai sai, nhưng phải biết rất nhiều về nguyện vọng của người khác mới làm được.