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”.
. Cho đến trước những năm 1940, thị trường tuyển dụng bác sỹ mới ra trường ở Mỹ 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:
- Ổ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.
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.
. Cho đến trước những năm 1940, thị trường tuyển dụng bác sỹ mới ra trường ở Mỹ 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:
- Ổ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.
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.
Theo
GS Toán học Hà Huy Khoái
Lớp Toán - Cơ K21 - ĐHTHHN sau 35 năm ra trường
