Bài toán cầu hôn và giải pháp cho Bộ Giáo dục

- Tại ngày hội “Một ngày với Toán học” diễn ra tại Viện Toán học hôm 10/10, GS. Hà Huy Khoái đã có bài giảng “Toán học với thị trường, tuyển sinh và gả chồng dựng vợ” trước đông đảo người yêu toán.

Bài toán gả chồng dựng vợ mà ông còn gọi là “bài toán cầu hôn” chính là thuật toán “chấp nhận trì hoãn” của Gale Shapley mà ứng dụng của GS. Alvin Roth vào lĩnh vực kinh tế đã giành giải Nobel Kinh tế năm 2012.

Thuật toán Gale Shapley được GS. Hà Huy Khoái giải thích bằng bài toán cầu hôn  như sau: Có 4 chàng trai là Adam, Bob, Charlie, Don và 3 cô gái là Mary, Jane và Kate. 4 chàng trai có cảm tình với 3 cô gái theo một thứ tự ưu tiên nhất định và ngược lại 3 cô gái cũng có cảm tình với 4 chàng trai theo một thứ tự ưu tiên khác.

Và thuật toán G. Shapley sẽ giải quyết vấn đề này bằng cách đưa ra phương án tốt nhất cho 4 chàng trai (hoặc 3 cô gái) dựa trên thứ tự ưu tiên của họ.

Giả sử thứ tự ưu tiên của 4 chàng trai như sau:

Giả sử thứ tự ưu tiên của 3 cô gái như sau:

Giả sử bài toán này sẽ ưu tiên quyền lợi của 4 chàng trai trước, nghĩa là để các chàng trai đưa ra lựa chọn của mình trước (nếu dựa trên ưu tiên quyền lợi của các cô gái, kết quả sẽ khác đôi chút).

Ngày đầu tiên, 4 chàng trai đi cầu hôn ưu tiên số 1 của mình, nghĩa là Bob cầu hôn Jane, và cả 3 chàng trai Adam, Charlie và Don đều cầu hôn Mary.

Mary vì có tới 3 sự lựa chọn nên sẽ chọn ưu tiên tốt nhất của mình trong số 3 chàng trai, đó là Don (ưu tiên số 1 của Mary).

Jane vì chỉ có Bob cầu hôn nên sẽ chọn Bob tạm thời (chấp nhận tạm thời). Kate chưa có ai cầu hôn trong ngày đầu tiên.

Sang ngày thứ hai, vì Mary đã chọn Don nên Adam và Charlie đi cầu hôn ưu tiên số 2 của mình. Adam cầu hôn Jane và Charlie cầu hôn Kate. Vì ưu tiên số 1 của Jane là Adam nên Jane chấp nhận Adam, loại Bob. Kate chỉ có duy nhất Charlie cầu hôn nên tạm thời chấp nhận Charlie.

Ngày thứ ba, chỉ còn Bob chưa được ai chấp nhận, Bob cầu hôn Kate. Bob là ưu tiên số 1 của Kate, trong khi Charlie là ưu tiên số 3 nên Kate chọn Bob, loại Charlie.

Như vậy, theo cách nói vui của GS. Hà Huy Khoái, cuối cùng Charlie “ế vợ”.

Quá trình “cầu hôn” và “chọn lựa” này có thể được biểu diễn bằng bảng sau:

Bài toán cầu hôn không có thực trong cuộc sống thực tiễn nhưng cách giải quyết vấn đề của thuật toán này có thể áp dụng ở nhiều lĩnh vực. Theo GS. Hà Huy Khoái, giai đoạn 1945-1951, thị trường tuyển dụng bác sĩ ở Mỹ bùng nổ do nhu cầu bác sĩ ở các bệnh viện quá lớn. Hậu quả của việc các bác sĩ tự ứng tuyển và các bệnh viện tự chọn lọc theo nhu cầu của riêng mình là các bệnh viện đưa ra thời hạn chấp nhận gấp, sinh viên y khoa nhận chỗ làm quá sớm… Vì thế, Chính phủ Mỹ đã thành lập một trung tâm điều phối có tên là National Resident Matching Program (NRMP) để tiếp nhận tất cả nguyện vọng của các bác sĩ cũng như các bệnh viện, từ đó điều phối sao cho phù hợp nhất. Năm 1984, nhà kinh tế Alvin Roth phát hiện ra thuật toán của NRMP áp dụng gần với thuật toán “chấp nhận trì hoãn” của Gale Shapley.

Trước năm 2004, quá trình tuyển sinh vào các trường công ở New York áp dụng lý thuyết “chấp nhận tức khắc” cũng dẫn tới tình trạng học sinh không đăng ký nguyện vọng thật của mình. Do đó, cần có một phương án giải quyết những vấn đề trên nhằm đảm bảo tính ổn định cũng như khuyến khích sự thành thật trong việc đăng ký nguyện vọng.

GS. Hà Huy Khoái khẳng định, Bộ Giáo dục có thể áp dụng kết quả của thuật toán này vào công tác xét tuyển nguyện vọng đại học, cao đẳng để tránh tình trạng rút ra rút vào hồ sơ, gây mệt mỏi cho thí sinh như mùa tuyển sinh vừa qua.

Giống như bài toán cầu hôn, vẫn là quá trình rút ra rút vào nhưng tất cả được thực hiện bởi máy móc, phần mềm. Việc của các thí sinh là đưa ra danh sách thứ tự ưu tiên của mình, các trường cũng đưa ra thứ tự ưu tiên của mình: điểm thi, học bạ, hạnh kiểm… Với các trường đặc thù có thể là chiều cao, cân nặng, năng khiếu… Sau đó máy móc sẽ thực hiện toàn bộ quá trình rút ra rút vào đó và đưa ra một kết quả tốt nhất cho các thí sinh, đảm bảo rằng sẽ không có thí sinh nào điểm thấp hơn mình vào được trường đó mà mình không vào được.

Theo GS. Hà Huy Khoái, đây là giải pháp duy nhất cho vấn đề tuyển sinh hiện nay. Giải pháp này đảm bảo các yếu tố: cho phép các trường đề ra thứ tự ưu tiên cho mình, đảm bảo quyền lợi của học sinh: nêu nguyện vọng thật, học sinh được theo học tại trường ưu tiên cao nhất có thể theo thứ tự ưu tiên tùy thuộc kết quả của thí sinh, loại bỏ được yếu tố “ảo” và tiết kiệm chi phí.

“Chúng tôi đã thử nghiệm và cho kết quả tốt. Chỉ trong vòng 2 tiếng xứ lý được dữ liệu của 1 triệu thí sinh. Làm tất cả chỉ trong vòng 1 ngày là xong” – GS. Hà Huy Khoái khẳng định.

Ông cũng cho biết Cục Khảo thí cũng tỏ ra rất tâm đắc với phương án này và có mời ông tới nói chuyện với các trường. “Các trường tốp đầu hiểu rất nhanh và thích phương án này nhưng không hiểu sao lãnh đạo nhiều trường khác thì không muốn áp dụng. Họ bảo cứ để họ tự làm theo cách truyền thống” – ông nói.

“Tôi cũng rất tiếc vì năm vừa rồi Bộ không áp dụng. Có lẽ Bộ còn lo ngại các trường”.

GS. Hà Huy Khoái cũng cho rằng cái khó trong vấn đề này không phải là vấn đề kỹ thuật mặc dù để áp dụng vào tuyển sinh cần phải cải tiến đôi chút, mà khó nhất là thuyết phục được xã hội, làm thế nào để các phụ huynh, các em học sinh, các trường hiểu được và đồng tình. Ban đầu, giải pháp NRMP ở Mỹ cũng không phải bác sĩ nào cũng tham gia nhưng sau đó họ nhận ra không tham gia thì bị thiệt.

Ông cũng cho biết các nhà khoa học cũng đã gợi ý Bộ trước mắt dùng 80% chỉ tiêu để áp dụng thuật toán này. “ Tôi rất hy vọng năm sau Bộ sẽ áp dụng. Theo tôi đây là giải pháp duy nhất” – ông nói.

Nguyễn Thảo