Kinh tế, toán học và tuyển sinh
Những thành tựu của Alvin Roth và Lloyd Shapley (hai đồng chủ nhân giải Nobel Kinh tế 2012) có thể được ứng dụng vào thực tiễn Việt Nam như thế nào, từ việc thiết kế cơ chế điều phối hiến tặng nội tạng đến cơ chế tuyển sinh?
– Năm 1975, L. Kontorovich – nhà toán học Nga – nhận giải nhờ những nghiên cứu trong lý thuyết tối ưu, cụ thể là vấn đề phân bổ nguồn lực một cách tối ưu.
– Năm 1994, nhà toán học Mỹ J. Nash cùng với J. Harsanyi và R. Selten được trao giải nhờ những kết quả về cân bằng trong trò chơi bất hợp tác.
– Năm 2005, R. Aumann, Th. Schelling được vinh danh nhờ những nghiên cứu về xung đột và hợp tác trong lý thuyết trò chơi.
– Năm 2007, L. Hurwicz, E. Maskin, R. Myerson, bằng công cụ toán học xây dựng nên cơ sở cả lý thuyết thiết kế cơ chế.
– Năm 2012, A. Roth và L. Shapley, dựa trên những nghiên cứu về thuật toán chấp nhận trì hoãn đã đưa ra và kiểm nghiệm trên thực tế Lý thuyết phân phối ổn định và thiết kế thị trường.
Ngoài ra còn có thể kể đến những giải Nobel Kinh tế khác mà trong đó những phương pháp toán học đóng vai trò chính yếu: G. Debreu (1983 – Lý thuyết cân bằng tổng quát); V. Smith (2002 – Phân tích thực nghiệm trong nghiên cứu thị trường), R. Engle (2003 – Phân tích chuỗi thời gian).
Dưới đây, chúng tôi chủ yếu trình bày những thành tựu của Roth và Shapley, đồng thời đề xuất một số khả năng ứng dụng của những nghiên cứu đó vào thực tiễn Việt Nam.
Đây không phải là những nghiên cứu mới của tác giả, mà chỉ là giới thiệu một số thành tựu mới cho những độc giả không chuyên.
Chi tiết hơn có thể tìm thấy trong những tài liệu liệt kê ở phần Tài liệu tham khảo.
Tiền đề thực tiễn của lý thuyết Roth và Shapley
Trong kinh tế, nhiều vấn đề được giải quyết bằng hệ thống giá cả. Tuy nhiên, cũng có nhiều lĩnh vực mà cơ chế giá cả không thể giải quyết trọn vẹn vấn đề, nhất là khi đụng chạm đến phạm trù đạo đức. Ví dụ như việc hiến tặng nội tạng, hay phân phối học sinh vào các trường công lập. Đặc điểm chung của những lĩnh vực đó là các “sản phẩm” không hoàn toàn đồng nhất, hoặc thị trường rất “mỏng”.
Năm 1984, Roth nghiên cứu thị trường tuyển dụng bác sĩ mới ra trường ở Mỹ. Cho đến trước những năm 1940, thị trường này còn “mỏng” và không tập trung. Thời gian sau đó bắt đầu chứng kiến sự bùng nổ của thị trường, dẫn đến hiện tượng tắc nghẽn. Để có thể tuyển dụng được, các bệnh viện phải đưa ra những quyết định tuyển người rất sớm, vì nếu từ chối ứng viên nào đó, rất có thể là đã quá muộn để có một ứng viên khác nộp đơn. Tình hình đó buộc các bệnh viện đưa ra những thời hạn chót cho ứng viên rất gấp. Điều này kéo theo việc sinh viên phải nhận chỗ làm tương lai thậm chí ngay từ khi chưa quyết định mình sẽ theo chuyên ngành gì.
Tình hình tương tự cũng được quan sát thấy ở các nước khác như Anh và Canada.
Để giải quyết tình trạng trên, khoảng những năm 1950 ở Mỹ đã thành lập những trung tâm điều phối, nhằm giúp cho thị trường bác sĩ mới tránh được hiện tượng “tắc nghẽn”. Năm 1984, Roth phát hiện ra rằng, thuật toán mà các trung tâm điều phối ở Mỹ áp dụng thực chất gần với thuật toán chấp nhận trì hoãn của Gale và Shapley, xây dựng trong một bài báo đăng trên tạp chí American Mathematical Monthly năm 1962.
Một hiện tượng khác cho thấy sự cần thiết phải có thuật toán điều phối tương tự là vấn đề tuyển sinh vào các trường công lập ở New York. Học sinh có thể chọn trường mình muốn theo học, nhà trường có thể ưu tiên theo những tiêu chí riêng của họ, như học lực, khả năng thể thao, văn nghệ,… Cho đến trước năm 2003, việc phân phối học sinh vào các trường theo nguyên tắc sau: mỗi học sinh đưa ra năm nguyện vọng theo thứ tự ưu tiên, các trường lấy từ trên xuống cũng theo thứ tự ưu tiên của họ. Nếu học sinh nào mà cả năm nguyện vọng đều không được thỏa mãn (hết chỗ) thì buộc phải theo sự sắp xếp của thành phố. Quy tắc này giống với cách tuyển sinh đại học (theo thứ tự điểm) áp dụng hiện nay ở Việt Nam. Tạm gọi đó là thuật toán chấp nhận tức khắc. Theo quy tắc này, hằng năm ở New York có khoảng 30.000 học sinh không được theo học ở trường nào trong năm trường có nguyện vọng.
Roth phát hiện ra rằng, những vấn đề nêu trên đối với thị trường bác sĩ cũng như tuyển sinh, và nhiều vấn đề khác của thực tiễn có thể giải quyết nhờ thuật toán chấp nhận trì hoãn.
Thuật toán chấp nhận trì hoãn
Những vấn đề của thị trường bác sĩ và tuyển sinh có nét chung: đó là cần đến sự “ghép cặp” (giữa nhà tuyển dụng và ứng viên, giữa học sinh và nhà trường). Việc ghép cặp này phải bảo đảm ba yêu cầu:
 |
 |
| David Gale (trái) và Lloyd Shapley, hai đồng tác giả của thuật toán chấp nhận trì hoãn được công bố lần đầu vào năm 1962. |
– Ổn định: không xảy ra “nguyện vọng chéo”, tức là không xảy ra việc ứng viên A muốn vào X thì bị ghép vào Y, ngược lại ứng viên B muốn vào Y thì bị ghép vào X. Nếu có tình trạng đó, các ứng viên sẽ có nguyện vọng trao đổi, và hệ thống mất ổn định.
– Khuyến khích sự thành thật: các ứng viên cần đưa ra thứ tự ưu tiên thật sự của mình. Thuật toán cần đảm bảo sao cho sự thành thật làm lợi cho ứng viên, tránh tình trạng người gian dối được hưởng lợi.
– Thuật toán phải đơn giản, dễ áp dụng.
Điều đáng ngạc nhiên là một thuật toán đáp ứng cả ba yêu cầu đó đã được hai nhà toán học Gale và Shapley đưa ra năm 1962 ([3]), nhưng chính các tác giả không hề biết về khả năng áp dụng thuật toán.
Thuật toán chấp nhận trì hoãn (deferred acceptance algorithm) có thể mô tả như sau.
Xét một thị trường hai phía, gồm nhà tuyển dụng và ứng viên (ví dụ nhà trường và sinh viên). Các trường và sinh viên gửi danh sách thứ tự ưu tiên của mình đến một trung tâm thông tin.
Bước 1: Trung tâm xếp các sinh viên vào các trường theo “nguyện vọng 1” của họ. Các trường nhận (tạm thời) theo thứ tự ưu tiên. Khi đã đủ số cần thiết, những ứng viên còn lại bị từ chối.
Quá trình trên được lặp lại, cụ thể là:
Ở bước thứ k, mỗi sinh viên bị từ chối ở các bước 1 đến k-1 sẽ được đưa vào trường tiếp theo trong danh sách các nguyện vọng của sinh viên đó. Các trường sẽ lại xét theo danh sách mới (bao gồm các sinh viên đã được chấp nhận tạm thời ở những bước trước và những sinh viên vừa được đưa vào) và đưa ra danh sách chấp nhận tạm thời mới. Những sinh viên còn lại bị từ chối.
Quá trình kết thúc khi không còn đơn nhập học nào bị từ chối, hoặc khi chỉ còn lại những sinh viên đã bị từ chối ở tất cả các bước.
Có thể minh họa thuật toán một cách đơn giản như sau (theo cách trình bày của Shapley).
Giả sử có bốn chàng trai Adam, Bob, Charlie và Don, cùng “theo đuổi” ba cô gái Mary, Jane và Kate.
Thứ tự ưu tiên của các chàng trai được cho bởi bảng sau đây:
|
Adam |
Bob |
Charlie |
Don |
|
Mary |
Jane |
Mary |
Mary |
|
Jane |
Mary |
Kate |
Kate |
|
Kate |
Kate |
Jane |
Jane |
Thứ tự ưu tiên của các cô gái:
|
Mary |
Jane |
Kate |
|
Adam |
Adam |
Don |
|
Bob |
Charlie |
Charlie |
|
Charlie |
Don |
Bob |
|
Don |
Bob |
Adam |
Ngày thứ nhất, các chàng trai cầu hôn các cô gái mà mình thích nhất. Trong những người đến cầu hôn, mỗi cô gái chấp nhận (tạm thời) người đứng thứ tự cao nhất trong bảng ưu tiên của mình, từ chối những người còn lại.
Các chàng trai bị từ chối sẽ tiếp tục cầu hôn cô gái thứ hai trong “bảng ưu tiên”. Các cô gái sẽ xét những lời cầu hôn mới, kết hợp với người đã “lựa chọn tạm thời” để chấp nhận (vẫn chỉ là tạm thời) người có thứ tự cao nhất trong bảng ưu tiên.
Quá trình tiếp tục cho đến khi những chàng trai chưa được ghép cặp đã bị từ chối bởi tất cả các cô gái.
Với trường hợp cụ thể trên đây, quá trình diễn ra như sau:
|
|
Ngày 1 |
Ngày 2 |
Ngày 3 |
Ngày 4 |
Ngày 5 |
|
Mary |
Adam (Charlie và Don bị từ chối) |
Adam (không có lời cầu hôn mới) |
Adam (không có lời cầu hôn mới) |
Adam (từ chối Bob) |
Adam (không có lời cầu hôn mới) |
|
Kate |
Không có lời cầu hôn nào |
Don (Charlie bị từ chối) |
Don (không có lời cầu hôn mới) |
Don (không có lời cầu hôn mới) |
Don (Bob bị từ chối) |
|
Jane |
Bob |
Bob (không có lời cầu hôn mới) |
Charlie (Bob bị từ chối) |
Charlie (không có lời cầu hôn mới) |
Charlie (không có lời cầu hôn mới) |
Như vậy, với Thuật toán chấp nhận trì hoãn, kết quả “ghép cặp” sẽ là: Mary-Adam; Kate-Don; Jane-Charlie.
Gale và Shapley đã chứng minh chặt chẽ về mặt toán học những kết luận sau đây:
– Thuật toán kết thúc sau hữu hạn bước, và cho một lời giải ổn định
– Lời giải là tốt nhất có thể đối với các chàng trai. Nếu các cô gái được chủ động kén rể, thì kết quả sẽ tốt nhất cho các cô gái. Trong ví dụ trên đây, kết quả ghép cặp không thay đổi, tuy nhiên trong trường hợp tổng quát, kết quả có thể sẽ khác. Tức là, thuật toán nhằm ưu tiên quyền lợi cho “ứng viên”.
– Thuật toán áp dụng được cho cả những trường hợp số chàng trai và số cô gái khác nhau.
Cho đến những năm 1970, thuật toán chấp nhận trì hoãn của Gale và Shapley chỉ có ý nghĩa lý thuyết.
Lý thuyết thiết kế thị trường
Alvin Roth là người phát hiện ra khả năng ứng dụng to lớn của thuật toán chấp nhận trì hoãn. Roth chỉ ra rằng quan điểm “ổn định” giúp ta hiểu được khi nào thị trường hoạt động tốt, khi nào thì không. Cùng với các cộng sự, Roth đã kết hợp giữa những nghiên cứu thực tế với những thí nghiệm kiểm soát được trong phòng thí nghiệm, với việc sử dụng tương tự trên máy tính để kiểm tra cơ chế hoạt động của thị trường. Họ đã hoàn thiện và phát triển thuật toán của Gale và Shapley, áp dụng chúng để đề xuất những cơ chế giúp thị trường hoạt động tốt hơn. Những nghiên cứu này đã tạo nên một lĩnh vực mới trong kinh tế, được gọi là thiết kế thị trường. Trong lý thuyết của mình, Roth sử dụng cả những thành tựu của lý thuyết trò chơi hợp tác và bất hợp tác.
Từ năm 2003, những phương án do Roth và các cộng sự đề xuất cũng được áp dụng vào việc tuyển sinh của các trường công lập ở New York. Kết quả thật ấn tượng: con số khoảng 30.000 học sinh không được học đúng nguyện vọng hằng năm giảm xuống còn khoảng 3.000. Nhiều thành phố khác cũng bắt đầu áp dụng thuật toán đó, chẳng hạn Boston bắt đầu áp dụng từ 2005.
Những nghiên cứu về thiết kế thị trường của Roth cũng được áp dụng rộng rãi ở nhiều nước khác, như Anh, Canada, Nhật, vì những vấn đề đặt ra ở đó là hoàn toàn tương tự.
Những công trình về thiết kế thị trường của Roth và Shapley không chỉ liên quan đến những thị trường hai phía, mà còn cả những thị trường một phía. Năm 1974, Shapley và Scarf nghiên cứu những thị trường một phía, trong đó người tham gia có những tài sản nào đó (chẳng hạn những lô đất) mà họ muốn trao đổi với nhau không thông qua việc trả tiền. Mô hình này còn được cải tiến cho trường hợp có những người tham gia mà không có tài sản gì! Shapley và Scarf chứng minh rằng, thuật toán chu trình thương mại hàng đầu (top-trading cycle algorithm) của Gale sẽ đưa ra được một phân phối ổn định. Có thể mô tả thuật toán đó như sau.
Xét một tập hợp những đối tượng tham gia trao đổi. Ta vẽ một mũi tên xuất phát từ mỗi đối tượng A và đi đến đối tượng B đang nắm giữ tài sản mà A thích nhất. Làm như vậy, về mặt toán học, ta được một đồ thị hữu hạn có hướng. Trong mỗi đồ thị như vậy đều tồn tại ít nhất một chu trình. Khi đó những đối tượng nằm trong chu trình sẽ trao đổi với nhau, và họ được loại ra ngoài hệ thống. Quá trình tiếp tục cho đến khi không còn đối tượng nào. Roth và Postlewaite (1977) chứng minh rằng tồn tại duy nhất một phân phối ổn định.
Thuật toán trên đây được áp dụng rất hiệu quả ở Anh trong vấn đề điều phối việc hiến tặng nội tạng. Ví dụ, một người nào đó muốn hiến thận cho người thân của mình, nhưng nhóm máu của họ không hợp. Khi đó, họ sẵn sàng hiến cho người khác, với điều kiện người thân của mình nhận được quả thận thích hợp. Nếu chỉ có hai cặp như vậy chỉ cần tiến hành bốn ca mổ đồng thời. Tuy nhiên, vấn đề phức tạp hơn nhiều nếu không tìm ngay được một cặp thích hợp. Điều này dẫn đến việc phải thành lập những trung tâm điều phối, hoạt động trên cơ sở thuật toán vừa mô tả.
Kết luận
Giải Nobel 2012 của Roth và Shapley là thành tựu của việc kết hợp giữa lý thuyết toán học (thuật toán chấp nhận trì hoãn của Gale-Shapley và thuật toán chu trình thương mại hàng đầu của Gale) với những nghiên cứu trong phòng thí nghiệm và thực tiễn thị trường (Roth và các cộng sự). Điều này một lần nữa minh chứng cho tiềm năng ứng dụng của những nghiên cứu toán học trừu tượng, và những thành tựu đạt được với sự phối hợp những nghiên cứu đa ngành, một xu hướng tất yếu của khoa học hiện đại.
Sự đơn giản và hiệu quả của thuật toán chấp nhận trì hoãn cho chúng ta hy vọng có thể tìm thấy những ứng dụng của nó trong thực tiễn Việt Nam. Ví dụ như trong việc thiết kế cơ chế tuyển sinh thế nào cho phù hợp với xã hội; thiết kế cơ chế hoạt động của Trung tâm Điều phối hiến tặng nội tạng được thành lập cách đây không lâu.
Cũng cần nhấn mạnh rằng, thực tiễn luôn đặt ra rất nhiều vấn đề phải giải quyết, và thị trường Việt Nam chắc chắn không giống với thị trường của bất kỳ nước nào. Vì thế, những thành tựu của Roth và Shapley, nếu có thể ứng dụng vào Việt Nam, chắc chắn cần nhiều cải tiến cho phù hợp.
Viết thêm
Sau khi Bộ Giáo dục và Đào tạo có chủ trương dùng kết quả của kỳ thi tốt nghiệp THPT để xét tuyển đại học, tôi cùng với TS Phan Huy Phú (trường ĐH Thăng Long) đã đề xuất một phương án tuyển sinh dựa trên thuật toán chấp nhận trì hoãn, có một số cải tiến để phù hợp với điều kiện Việt Nam. Với phương án này, mỗi thí sinh chỉ cần đưa một danh sách nguyện vọng của mình theo thứ tự ưu tiên, mà không cần quan tâm đến kết quả thi của các thí sinh khác. Các trường có thể đưa ra những ưu tiên xét chọn phù hợp với trường mình (điểm thi, năng khiếu, hình thể,…) Vấn đề còn lại là máy tính sẽ sắp xếp sao cho mỗi thí sinh có thể vào trường cao nhất theo thứ tự ưu tiên, tùy thuộc vào điểm thi và những điều kiện khác của bản thân.
Phương án này đã được trường ĐH Thăng Long trình lên Bộ Giáo dục và Đào tạo tháng 10/2014; cùng với một thử nghiệm trên máy tính. Mô hình thử nghiệm được xây dựng trên giả định có một triệu thí sinh (gần với con số thực tế), và thuật toán cho kết quả “xét tuyển” ổn định sau hai giờ chạy máy.
———————–
TÀI LIỆU THAM KHẢO
[1] I. Ashlagi and A. Roth. New challenges in multi-hospital kidney exchange. American Economic Review, 102, 2012, pp. 354-359.
[2] R.J. Aumann and L.S Shapley. Values of non-atomic games. Princeton Univ. Press, 1974.
[3] D. Gale and L. S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69, 1962, pp.9-15.
[4] A. Roth. The economics of matching: stability and incentives. Mathematics of Operations Research, 7, 1982, pp. 617-628.
[5] A. Roth. What have we learned from market design? Economic Journal, 118, 2008, pp. 285-310.
[6] A. Roth. Deferred acceptance algorithm: History, theory, practice, and open question. International Journal of game theory, 36, 2008, pp. 537-569.
[7] Stable allocations and the practice of market design. Economic Science Prize Committee of the Royal Swedish Academy of Sciences., 2012., 44 p.
Đọc thêm:
Không thể quay lại kiểu thi cũ
http://www.tiasang.com.vn/Default.aspx?tabid=113&CategoryID=6&News=9157http://tiasang.com.vn/Default.aspx?tabid=113&CategoryID=6&News=9157
