Ghép đôi bền vững

Tiếng anh gọi là stable matching. Đây là một mô hình kinh tế và khoa học máy tính rất nổi tiếng và nhiều ứng dụng. Lớp thuật toán tôi đang dạy mở đầu bằng  bài toán  này.

Tại rất nhiề nơi trên thế giớ họ dùng mô hình và lời giải này để tuyển sinh đại học.  Không hiểu tại VN bác Nhân chưa được học qua bài toán này hay là do một lý do khác mà không thấy áp dụng? 

——–

Tuyển sinh: Thị trường.

Tuyển sinh không chỉ đơn thuần là chọn thóc giống, tuyển sinh là một thị trường. Các trường đại học cạnh tranh nhau chọn học sinh giỏi, và các thí sinh tranh nhau những tấm vé vào những ngành học mà mình yêu thích. Ở Việt Nam sự cạnh tranh thiên về phía thí sinh hơn, cả trăm người thi mới có một hai người đỗ vào đại học. Hệ thống tuyển sinh tốt là hệ thống mà không chỉ chọn lựa được những thí sinh giỏi vào đại học mà còn có thể chọn lựa những thí sinh giỏi vào những đại học thích hợp.  

Bỏ đi nhiều chi tiết lặt vặt, người ta có thể hiểu kiểu thị trường này như sau: Thị trường kiểu này có hai mặt A(các trường đại học) và B (thí sinh dự thi). Mỗi thành viên trong A có thể sắp sếp các thành viên B riêng theo sở thích riêng, ví dụ khoa tin học đại học tự nhiên thích các thí sinh giỏi môn toán trong khi trường xây dựng lại thích học sinh giỏi vật lý…Các thành viên trong B cũng có sở thích riêng về các đối tác A, ví dụ các thí sinh đều muốn đỗ đại học, nhưng có người thich học tin học hơn xây dựng và ngược lại. Giả sử ta có danh sách các thành viên A , B và sở thích của họ, mục tiêu là tìm ra một kết nối giữa A và B (tát nhiên có thể có những thành viên không được kết nối) sao cho các thành viên của cả A và B đều thỏa mãn với lời giải. Thế nào là thỏa mãn? Ví dụ không có hai cặp a1-b1, a2-b2 được kết nối trong khi a1 thích b2 hơn b1, a2 thích b1 hơn b2, tương tự b2 thích a1 hơn a2, b1 thích a2 hơn a1. Bởi vì nếu ta kết nối a1-b2 và a2-b1 thì tất cả mọi người sẽ hạnh phúc hơn.

Với những người học kinh tế, kiểu mô hình này được gọi là two sided market, hay two sided matching, stable matching v.v.. David Gale đưa ra mô hình này vào những năm 60 sau khi đọc bài báo trên New York Times về những vấn đề trong tuyển sinh tại đại học Yale. Kể từ đó người ta đã cải tiến về mặt mô hình và thuật toán cho những bài toán tương tự và nó được sử sụng trong nhiều bài toán thực tế như sắp xếp các sinh viên y tế vào thực tập tại các bệnh viện; sắp xếp việc hiến thận; sắp xếp sinh viên vào ký túc xá và tất nhiên trong việc tuyển sinh. Alvin Roth là nhà kinh tế học tại Harvard có khá nhiều kinh nghiệm trong việc đưa ra những phương pháp kinh tế trong thị trường kiểu này, ông đã được chính phủ mời tham gia xây dựng khá nhiều hệ thống như vậy, bạn đọc có thể xem trang web của Roth.

http://kuznets.fas.harvard.edu/~aroth/alroth.html#MarketDesign

Nếu nhìn dưới con mắt kinh tế, người ta có thể thấy vài điểm sai trong cách tuyển sinh của Việt Nam.

Các thí sinh chỉ được đăng ký vào một trường, nếu trượt sẽ được xét tuyển đợt 2, 3 ở những trường kém hơn nếu họ thiếu học sinh, và điểm xét tuyển cao hơn so với điểm sàn khá nhiều. Hệ thống này có thể gây nên khá nhiều vấn đề cần suy nghĩ. Ví dụ có khả năng với suy nghĩ những trường nổi tiếng khó vào, nên thí sinh sẽ ngần ngại khi đăng ký, kết quả những trường yếu hơn sẽ có nhiều thí sinh, và điểm sét tuyển của họ có thể sẽ cao hơn. Trường nổi tiếng không những không tuyển được học sinh giỏi mà các thi sinh có thể có đủ điểm vào trường nổi tiếng và thich trường đó hơn nhưng cuối cùng cũng phải học trường kém, và thậm chí bị trượt đại học. (Tôi biết có nhiều trường hợp như vậy đã sảy ra.)

Làm sao để xây dưng hệ thống tuyển sinh tốt hơn? Thứ nhất việc thí sinh chỉ đăng ký vào một trường duy nhất là có hại. Điều này có thể gây ra những phản ứng dây truyền, thí sinh nhiều khi không đăng ký vào trường mà họ muốn học nhất. Hãy để thí sinh được bày tỏ ý muốn theo các nguyện vọng một cách trung thực. Điều này còn tạo ra thông tin về cung cầu trong các ngành học. Các ngành học xét tuyển chỉ theo tổng số điểm của ba môn thi cũng chưa phải là tối ưu. Mỗi ngành riêng biệt trong một khối đã có những đặc thù khác nhau, người ta cần có thêm những câu hỏi riêng, hay cách tính điểm khác để đưa ra được thông tin chính xác hơn, tổng số điểm chỉ nói lên được một thông số.