NRMP (National Resident Matching Program) là chương trình ghép sinh viên y mới tốt nghiệp với các chương trình đào tạo bác sĩ nội trú ở Mỹ bằng thuật toán. Ứng viên và bệnh viện mỗi bên nộp bảng xếp hạng, máy chạy một phiên bản của thuật toán Gale–Shapley, kết quả công bố cùng một lúc vào "Ngày Match" giữa tháng Ba hằng năm. Hệ thống có từ năm 1952, được thiết kế lại năm 1998 theo đề xuất của Alvin Roth và Elliott Peranson để ứng viên là bên được lợi và để các cặp vợ chồng bác sĩ có thể nộp chung.
Bác sĩ nội trú ở Mỹ khác ở Việt Nam thế nào
Ở Việt Nam, bác sĩ nội trú là một chương trình chọn lọc: sinh viên y khoa giỏi thi tuyển ngay khi tốt nghiệp, số chỗ ít, học vài năm tại bệnh viện thực hành của trường. Ở Mỹ, "residency" là chặng gần như bắt buộc với mọi bác sĩ muốn hành nghề: tốt nghiệp trường y xong phải qua ba tới bảy năm đào tạo tại bệnh viện theo chuyên khoa mới được cấp phép hành nghề độc lập. Mỗi năm vì vậy có hàng chục nghìn người cùng tìm chỗ, và hàng nghìn chương trình cùng tìm người. Đây là một thị trường lao động khổng lồ, diễn ra trong một ngày, với mức lương do bệnh viện ấn định trước, không mặc cả.
Vì sao phải dùng thuật toán: thị trường vỡ sớm
Trước năm 1952, bệnh viện tự tuyển. Vì bác sĩ thực tập là lao động rẻ và quan trọng, các bệnh viện tranh nhau chốt người sớm hơn đối thủ. Vào thập niên 1940, có lúc lời mời được gửi khi sinh viên còn gần hai năm nữa mới tốt nghiệp, lúc chưa ai biết em đó giỏi chuyên khoa nào, và chính em cũng chưa biết mình thích gì.
Các trường y thử thoả thuận "không công bố hồ sơ trước ngày X". Bệnh viện chuyển sang gửi lời mời với hạn trả lời cực ngắn, có khi chỉ tính bằng giờ. Sinh viên được mời ở nơi mình xếp thứ ba, đang chờ nơi xếp thứ nhất, phải gật vội vì sợ mất. Các nhà kinh tế gọi hiện tượng này là thị trường vỡ sớm (unraveling) và lời mời nổ (exploding offer).
Năm 1952, các tổ chức y khoa lập một văn phòng ghép trung tâm. Sinh viên và bệnh viện nộp bảng xếp hạng, văn phòng chạy một quy trình và công bố kết quả cùng lúc. Tên gọi National Resident Matching Program có từ năm 1978.
Phát hiện của Roth năm 1984
Ba mươi năm sau, Alvin Roth đọc kỹ quy trình của NRMP và chứng minh nó tương đương thuật toán chấp nhận hoãn Gale–Shapley với bệnh viện là bên đề nghị. Những người làm nghề y đã tự tìm ra cách ghép ổn định từ năm 1952, mười năm trước bài báo của Gale và Shapley. Tính ổn định giải thích vì sao hệ thống sống được: không có bệnh viện và ứng viên nào cùng thích nhau hơn kết quả, nên không ai có lý do kéo nhau ra ngoài làm thoả thuận riêng.
Nhưng có hai vấn đề. Thứ nhất, bệnh viện đề nghị thì kết quả nghiêng về bệnh viện, và về lý thuyết ứng viên có thể có động cơ khai không thật. Thứ hai, ngày càng nhiều sinh viên y kết hôn với nhau và muốn làm nội trú cùng thành phố, thứ mà thuật toán gốc không được xây để xử lý.
Tính tay: bên nào đề nghị thì bên đó lợi
Bốn ứng viên Hưng, Khánh, Liên, Mỹ; hai chương trình: bệnh viện thứ nhất (gọi là B1) có 2 chỗ, bệnh viện thứ hai (B2) có 1 chỗ.
| Ứng viên | Xếp hạng | Bệnh viện | Xếp hạng |
|---|---|---|---|
| Hưng | B1, B2 | B1 (2 chỗ) | Hưng, Mỹ, Khánh, Liên |
| Khánh | B1, B2 | B2 (1 chỗ) | Hưng, Khánh, Mỹ, Liên |
| Liên | B1, B2 | ||
| Mỹ | B2, B1 |
Ứng viên đề nghị (kiểu NRMP từ 1998)
- Vòng 1: Hưng, Khánh, Liên nộp vào B1; Mỹ nộp vào B2. B1 xét ba người, giữ hai người mình xếp cao nhất là Hưng và Khánh, trả Liên. B2 giữ Mỹ.
- Vòng 2: Liên nộp B2. B2 so Mỹ với Liên, giữ Mỹ, trả Liên. Liên hết lựa chọn.
Kết quả: B1 – Hưng, Khánh; B2 – Mỹ; Liên không có chỗ.
Bệnh viện đề nghị (kiểu NRMP trước 1998)
- Vòng 1: B1 mời hai người đầu bảng là Hưng và Mỹ; B2 mời Hưng. Hưng có hai lời, thích B1 hơn: giữ B1, từ chối B2. Mỹ chỉ có lời của B1: giữ tạm.
- Vòng 2: B2 mời người kế tiếp là Khánh; Khánh giữ.
Kết quả: B1 – Hưng, Mỹ; B2 – Khánh; Liên không có chỗ.
| Ứng viên đề nghị | Bệnh viện đề nghị | |
|---|---|---|
| Mỹ | B2 (lựa chọn 1) | B1 (lựa chọn 2) |
| Khánh | B1 (lựa chọn 1) | B2 (lựa chọn 2) |
| B1 nhận | Hưng, Khánh (hạng 1 và 3) | Hưng, Mỹ (hạng 1 và 2) |
| B2 nhận | Mỹ (hạng 3) | Khánh (hạng 2) |
Cả hai kết quả đều ổn định. Đổi bên đề nghị, Mỹ và Khánh mỗi người lên một bậc, hai bệnh viện mỗi bên xuống một bậc. Liên trượt ở cả hai cách vì cả hai bệnh viện đều xếp Liên cuối và chỉ có 3 chỗ cho 4 người: việc ai đề nghị không cứu được người mà không ai muốn hơn người khác.
Trong thực tế chênh lệch lớn đến đâu
Khi Roth và Peranson chạy thử cả hai chiều trên dữ liệu thật của NRMP cuối thập niên 1990, số ứng viên có kết quả khác nhau giữa hai cách rất nhỏ, cỡ vài chục người trong hơn hai mươi nghìn. Lý do: bảng xếp hạng ngoài đời có nhiều điểm chung (chương trình danh tiếng được nhiều người thích, ứng viên mạnh được nhiều nơi thích), nên số cách ghép ổn định thường ít. Dù vậy, chuyển sang ứng viên đề nghị mang một thông điệp quan trọng: ứng viên có thể yên tâm xếp thật lòng.
Bài toán các cặp vợ chồng
Từ thập niên 1980, NRMP cho phép hai ứng viên đăng ký như một cặp và nộp bảng xếp hạng theo cặp chương trình, chẳng hạn "(nội khoa ở bệnh viện X, nhi ở bệnh viện Y cùng thành phố)" xếp trên "(nội khoa ở X, không nhận chỗ nào)". Nghe thì đơn giản, nhưng về toán, nó phá vỡ đảm bảo đẹp nhất của Gale–Shapley.
Roth chứng minh khi có các cặp như vậy, có thể không tồn tại cách ghép ổn định nào. Trực giác: một cặp được nhận vào thành phố A, khiến một người độc thân bị đẩy sang thành phố B; nhưng việc người độc thân đến B lại làm một bệnh viện ở B muốn thay một nửa của cặp kia, kéo cả cặp rời A, giải phóng chỗ cũ, và vòng lặp không dừng.
Thuật toán Roth–Peranson xử lý bằng cách cho các ứng viên lần lượt vào, khi có cặp chặn thì đẩy người bị ảnh hưởng ra và cho vào lại, kèm cơ chế phát hiện vòng lặp. Về lý thuyết không có gì bảo đảm; trên dữ liệu thật, thuật toán gần như luôn tìm được cách ghép ổn định. Các nghiên cứu sau này giải thích điều đó: khi thị trường đủ lớn và số cặp chiếm tỉ lệ nhỏ, xác suất không có cách ghép ổn định tiến về 0.
Một tuần tháng Ba
Lịch của Main Residency Match ổn định qua nhiều năm:
| Thời điểm | Việc diễn ra |
|---|---|
| Mùa thu năm trước | Nộp hồ sơ, phỏng vấn tại các chương trình |
| Cuối tháng Hai – đầu tháng Ba | Hạn chót nộp bảng xếp hạng (rank order list) của cả hai bên |
| Thứ Hai của tuần Match | Ứng viên biết mình có được ghép hay không, chưa biết ở đâu |
| Trong tuần | Người chưa có chỗ tham gia vòng bổ sung có tổ chức (SOAP) cho các chỗ còn trống |
| Thứ Sáu (thường là thứ Sáu thứ ba của tháng Ba) | Ngày Match: mọi người cùng mở phong bì hoặc email biết nơi mình sẽ đến |
Ở nhiều trường y, Ngày Match là một nghi lễ: sinh viên tập trung trong hội trường, đếm ngược, cùng mở phong bì giữa gia đình và thầy cô. Kết quả có tính ràng buộc: ứng viên và chương trình đã nộp xếp hạng cam kết chấp nhận kết quả. Chính sự ràng buộc này chặn đứng lời mời nổ: không ai được ép người khác nhận lời trước ngày công bố.
Góc nhìn hôm nay
NRMP là ví dụ kinh điển cho câu "thị trường cũng có thể được thiết kế". Nó cũng truyền cảm hứng cho hàng loạt hệ thống ghép khác ở Mỹ và nhiều nước: ghép bác sĩ chuyên khoa sâu, dược sĩ, nhà tâm lý lâm sàng, và các chương trình đào tạo bác sĩ ở Canada, Nhật Bản, Anh. Năm 2002, một vụ kiện tập thể cho rằng NRMP kìm lương bác sĩ nội trú; năm 2004 Quốc hội Mỹ thông qua điều khoản khẳng định chương trình ghép này không vi phạm luật chống độc quyền, và vụ kiện bị bác.
Người muốn đọc thêm có thể tìm bài "The Redesign of the Matching Market for American Physicians" (Roth và Peranson, tạp chí American Economic Review, 1999), hoặc trang thông tin công khai của NRMP, nơi công bố số liệu và báo cáo sau mỗi kỳ Match.
Câu hỏi thường gặp
NRMP là gì?
Là chương trình ghép quốc gia ở Mỹ, xếp sinh viên y mới tốt nghiệp vào các chương trình đào tạo bác sĩ nội trú. Hai bên nộp bảng xếp hạng, thuật toán ghép theo nguyên tắc ổn định, và kết quả công bố cùng lúc vào Ngày Match tháng Ba.
Ngày Match là ngày nào?
Thường là thứ Sáu thứ ba của tháng Ba hằng năm. Đầu tuần đó, ứng viên biết mình có được ghép hay không; đến thứ Sáu mới biết cụ thể chương trình nào.
NRMP dùng thuật toán gì?
Từ năm 1998, NRMP dùng thuật toán Roth–Peranson, một phiên bản của thuật toán chấp nhận hoãn Gale–Shapley với ứng viên là bên đề nghị, có thêm phần xử lý các cặp vợ chồng nộp chung. Trước đó, quy trình gốc từ năm 1952 tương đương Gale–Shapley với bệnh viện đề nghị.
Vì sao cặp vợ chồng làm bài toán ghép khó hơn?
Vì khi một cặp muốn được ghép cùng nhau, có thể không tồn tại cách ghép ổn định nào, điều Alvin Roth đã chứng minh. Trên dữ liệu thật, thuật toán vẫn gần như luôn tìm được kết quả ổn định vì số cặp chiếm tỉ lệ nhỏ trong thị trường lớn.
Ở NRMP có nên xếp chương trình dễ đỗ lên đầu không?
Không nên. Với thuật toán ứng viên đề nghị, xếp đúng thứ tự mình thích là cách tốt nhất; trượt chương trình xếp đầu không làm giảm cơ hội ở chương trình sau. Điều cần tính là có đủ chương trình trong danh sách để không bị trượt hết.