BÁo cáo sơ BỘ VỀ khả NĂng áp dụng thuật toán daa (deferred-acceptance algorithm) CỦa gale-shapley trong tuyển sinh đẠi họC

Thuật toán stable matching (kết duyên bền vững) Gale-Shapley được Lloyd Shapley và David Gale giới thiệu từ những năm 1960. Đến những năm 1980, Alvin Roth đã có những nỗ lực liên tục để sử dụng thuật toán này tìm ra các giải pháp thực tiễn nhằm giải quyết các vấn đề thực trong cuộc sống thường ngày.

Thành công của Alvin Roth mang lại cho Roth và Shapley giải Nobel kinh tế năm 2012.

Các ứng dụng từ Roth và Shapley có thể mở rộng từ phân công tân bác sĩ vào các bệnh viện, ghép các tú tài vào các trường đại học phù hợp và phân phối (theo cơ chế bao cấp) nội tạng đến các bệnh nhân cần ghép.

Thuật toán “xe duyên” Gale – Shapley có thể giải quyết được bài toán kinh tế truyền thống “cung và cầu gặp nhau” nhưng không cần cơ chế “giá”. Ví dụ phía cung (các trường đại học) sẽ kết duyên ổn định với phía cầu (các tân tú tài muốn học đại học) mà không cần có một cơ chế giá mua/bán.

Thuật toán này hoạt động trên một tiên đề chung (common notion) về tính ổn định của hệ thống và năng lực nhận thức thuần lý của người tham gia hệ thống bên cầu (thí sinh). Thí sinh  được giả định có lý tính tốt, biết rõ mình muốn gì và hành vi lựa chọn (chọn trường) của họ tuân theo lý tính. Thí sinh sẽ tham gia việc chọn và được chọn trường, được thay đổi lựa chọn của mình, cho đến khi họ có dược kết quả tốt nhất.  Tình trạng khi mà thí sinh  tiếp tục có thay đổi lựa chọn trường, nhưng không làm họ có kết quả tốt hơn, được gọi là ổn định (stable).

Trạng thái “kết duyên bền vững” (stable matching) sẽ đạt được “khi tất cả thí sinh vào được trường cao nhất có thể còn các trường chọn được số thí sinh tốt nhất có thể”. Lúc đó cung (các trường đại học) gặp cầu (thí sinh) ở trạng thái ổn định bền vững.

Giải pháp của Gale-Shapley, được biết với tên gọi thuật toán deferred acceptance”, là một bộ các quy tắc đơn giản luôn đi trực tiếp đến trạng thái kết duyên bền vững (stable matching) trong môt số điêu kiện nhất định. Có hai cách thiết kế thuật toán: phía cung (các trường đại học) chủ động chọn (thí sinh); hoặc phía cầu (các thí sinh) chủ động nộp đơn (tới các trường mình muốn học).

Triết lý giáo dục đại học của nhóm VED, như đã thể hiện trong Đề xuất cải cách đại học VED 2015, là ủng hộ tự do đại học trong đó đề cao tính tự chủ của đại học.

Các trường tự chủ trong tuyển sinh là một trong những đề xuất quan trọng của VED.

Như vậy một hệ thống xét tuyển tập trung có thể đi ngược với quan điểm và triết lý của VED, đồng thời tạo ra một e ngại là hệ thống xét tuyển tập trung sẽ làm mất đi tính cạnh tranh cần phải có giữa các đại học.

Bên cạnh đấy, việc sử dụng một hệ thống xét tuyển tập trung có thể sẽ làm các trường đại học nhỏ mất đi phần lớn cơ hội tuyển được thí sinh khá giỏi .

Về việc triển khai ứng dụng của thuật toán Gale-Shapley cho một hệ thống xét tuyển tập trung phục vụ thí sinh và các trường đại học trên toàn quốc chắc chắn sẽ có ảnh hưởng đến hàng triệu con người. Vì vậy rất cần những nghiên cứu khoa kỹ lưỡng trước khi đi đến một bản thiết kế tốt nhất để đem vào ứng dụng trong thực tiễn.

Ứng dụng thực tiễn nổi tiếng nhất của thuật toán phát triển lên từ Gale-Shapley là “xe duyên” các bác sĩ mới tốt nghiệp chọn bệnh viện để thực tập (bang NY).  Ứng dụng này khác với việc tuyển sinh nhiều mặt.

a) Thứ nhất đây là người đã trưởng thành, đi tìm việc, tâm lý thái độ khác với hs đi học đại học. Nếu để so sánh, thì so sánh chính xác phải là ứng dụng Gale-Shapley cho sinh viện sư phạm tốt nghiệp đi tìm việc ở Việt Nam.
b) Ngoải ra các bác sĩ đã được interview trước, nên biết khả năng mình sẽ được vào nhưng trường cỡ nào, nên việc lựa chọn bản thân nó đã tự chính xác.

Một năm việc tuyển sinh đại học ở Mỹ tốn kém chừng 10 tỷ dollar. Câu hỏi là sao họ không ứng dụng G-S vào việc tuyển sinh chung? Nhất là khi các trường ở Mỹ có xếp hạng (ranking) rất rõ ràng. Một lý do hiển nhiên là không trường nào muốn làm như thế cả vì có lẽ nó làm giảm tính cạnh tranh.

Nếu muốn ứng dụng Gale-Shapley vào xét tuyển chung cho Việt Nam, ta cần làm rõ giải pháp này để tối ưu hóa cái gì? Có thể tính ổn định không chưa phải là ưu tiên. Mục đích của giải pháp, nên chăng, là tối ưu hóa số lượng thí sinh thỏa mãn (hoặc gần thỏa mãn) với trường đại học mình được nhận vào. Tính ổn định và tối ưu hóa số lượng thí sinh thỏa mãn nguyện vọng của mình là những bài toán khác nhau, sẽ dẫn đến những kết quả khác nhau.

2.2 Từ thực tiễn tuyển sinh năm nay

Tuy nhiên với thực tiễn Việt Nam, có nhiều trường đại học vì nhiều lý do đã không tự tổ chức thi đầu vào riêng cho mình. Thay vào đó những trường này sử dụng kết quả của kỳ thi THPT quốc gia cho xét tuyển.

Kỳ thi quốc gia 2 trong 1 năm nay tuy có nhiều sự cố, nhưng lợi ích (chi phí) xã hội của kỳ thi này tương đối rõ: thi phân tán và sử dụng kết quả của một kỳ thi cho các mục đích khác nhau, dẫn đến giảm bớt phí tổn xã hội.

Như vậy một kỳ thi quốc gia với kết quả  được sử dụng như một công cụ tập trung hóa cao độ để xét tuyển đại học tuy trái ngược với chủ trương của VED, nhưng VED cố gắng thực hiện các thảo luận và tranh luận nội bộ để trả lời câu hỏi: nếu sử dụng các công cụ toán và kinh tế hiện đại vào hình thức tuyển sinh tập trung hiện nay có cải thiện được hiệu quả của hệ thống này hay không.

Việc tuyển sinh đã từng liên quan đến những cuộc thảo luận của VED trước đây. Khi so sánh với phương pháp tuyển sinh ở các nước phát triển, cũng có mức độ đa dạng đáng kể. Ở Mỹ hệ thống hoàn toàn phân tán (decentralized) và ngoại trừ khớp thời gian thì hoàn toàn không thống nhất (uncoordinated).

Nhưng ở một số nước châu Âu như Pháp lại có hệ thống thi cử quy mô lớn.

Tại sao các đại học Mỹ không áp dụng G-S?

Lý do đầu tiên là do Mỹ không có cơ quan quản lý và điều phối chung cho tất cả các trường đại hoc (không có Bộ giáo dục và đào tạo như ở Việt Nam). Để áp dụng G-S cần phải có một hệ thống đại học tập trung hóa (centralized) như VN hoặc các đại học phải có tính phối hợp (coordination) rất cao, cùng từ chối – nhận học (defer-offer) vào cùng một thời điểm.

Lý do thứ hai là các đại học Mỹ tuyển sinh dựa vào nhiều tiêu chí chứ không chỉ dựa vào duy nhất điểm thi đại học như VN. Nhiều tiêu chí phi định lượng (non-quantitative) nên không thể/khó có thể thực hiện nhiều vòng từ chối – nhận học (defer-offer) vì sẽ rất tốn kém và mất thời gian cho cả đại học lẫn thí sinh.

Trong hệ thống của Pháp (hệ thống Trường Lớn), thí sinh thi rất nhiều môn, có cả thi vấn đáp và phỏng vấn, để sau đó được đánh giá bởi một điểm tổng hợp (composite) các thành tích gộp lại. Sau khi hình thành điểm composite thì trường không còn tự chủ nữa: họ tự động nhận thí sinh từ trên xuống dưới cho đến khi đủ số. Trong nhiều trường hợp, vì không có hệ thống matching tốt, có những trường cuối cùng phải chọn thí sinh yếu hơn, vì thí sinh giỏi đã trót nhận trường khác, v.vv.

Nhìn ở tầm dài hạn hơn, việc tuyển sinh Đại học ở Mỹ (chủ yếu theo triết lý giáo dục liberal arts) nhằm vào một *lớp/class* chứ không phải chỉ là mức ưu tiên trên mỗi cá nhân (preference over individuals). Nghĩa là họ muốn đảm bảo trong class phải có sinh viên đa dạng, mang lại trải nghiệm đại học (college experience) đặc sắc cho các bạn. Theo triết lý này thì các phương pháp như DAA của Gale-Shapley không có chỗ ứng dụng: Triết lý này đánh giá cao ngoại tác qua lại (externalities) giữa sinh viên với nhau, và dựa vào xếp hạng mức ưu tiên (preference ranking) giữa các tập sinh viên (sets of students) chứ không phải chỉ là so sánh giữa các cá nhân. Trong khi phương pháp như DAA hoàn toàn dựa vào preference giữa các cá nhân (thậm chí còn phải là ưu tiên chặt chẽ strict preference nữa). Đây là điểm mấu chốt để nhận xét xem môi trường nào thích hợp cho DAA, môi trường nào không.

Câu hỏi là, Việt Nam nên theo triết lý này của các Đại học ở Mỹ, hay theo một triết lý khác, ví dụ đi theo các trường lớn ở Pháp?

Trả lời câu hỏi này rất quan trọng nhưng cần lưu ý rằng hiện nay Việt Nam phần nào vẫn đang thực hiện theo triết lý Pháp, xét tuyển chỉ dựa vào điểm thi đại học (ngoại trừ một số trường hợp nhỏ được ưu tiên bằng hình thức cộng điểm). Vấn đề là hệ thống hiện nay (kỳ tuyển sinh 2015 vừa rồi) có nhiều điểm bất cập mà chỉ cần áp dụng G-S thuần tuý cũng đã cải thiện thêm nhiều.

Hệ thống “xe duyên” tập trung (matching system) có thể sẽ không làm hỏng tính cạnh tranh của đại học. Trong hệ thống matching, các trường vẫn cạnh tranh để được nhiều thí sinh tốt chọn mức ưu tiên (prefer). Chuyện này trong hệ thống nào cũng có, và vẫn được đề cao. Thực chất là khi thí sinh được thoải mái ghi ra toàn bộ nguyện vọng (list of preference) của mình, chứ không phải chỉ chọn ra một vài trường, thì sức ép về competition còn cao hơn trước.

Song song với mối lo mất tính cạnh tranh là mối lo các trường nhỏ bị thiệt.

Sử dụng  G-S hay một hệ thống tuyển sinh tập trung hóa (centralized) nào khác chưa chắc đã làm hỏng tính cạnh tranh giữa các trường, nhưng có thể sẽ làm giảm đa dạng hóa (diversification) giữa các trường và trong nội bộ từng trường, ví dụ vấn đề công bằng (equality). Ví dụ như thí sinh giỏi vào hết trường ở tốp đầu..

Đây là mối lo hợp lý, chủ yếu là do cạnh tranh (theo nghĩa trường nào tốt hơn sẽ được nhiều thí sinh tốt hơn) luôn là việc phải đánh đổi (trade-off) với công bằng. Các trường nhỏ, yếu cũng mong có thí sinh tốt. Một hệ thống xếp hạng dựa vào danh hiệu và uy tín (meritocratic) nặng hơn (giữa các trường) có thể dẫn đến việc các trường yếu hơn chịu thiệt hơn.

Đối nghịch với một hệ thống cạnh tranh ác liệt sẽ là một hệ thống thiên về công bằng, san sẻ toàn bộ: thí sinh chọn ngẫu nhiên vào các trường, bất kể là trường tốt hay yếu.

Như vậy có thêm một câu hỏi: về dài hạn, hệ thống nào sẽ tốt hơn cho sự phát triển của xã hội?

Về lâu dài, sự cạnh tranh bắt các trường phải tự cải thiện để thu hút thí sinh. Họ cũng có thể đưa ra chính sách nhắm vào một nhóm học sinh giỏi đặc biệt bằng cách đưa ra đối xử tốt hơn, không chỉ dựa vào điểm thi. Việc này có thể đưa vào hệ thống matching được. Ví dụ, trường A thuộc loại làng nhàng, những thí sinh trên 27 điểm sẽ được thêm tiền học bổng nếu chọn vào A. Như thế vẫn có thể ảnh hưởng lên nguyện vọng (preference) của thí sinh giỏi, và có thể thu hút một nhóm thí sinh giỏi có cảm tình với trường.

Hơn nữa, nguyện vọng (nhìn từ phía các trường đại học ở Việt Nam) từ trước đến giờ tương đối đơn giản (chỉ dựa theo điểm thi), nên có thể dự đoán là “kết quả tệ nhất” cho các trường cũng sẽ không quá tệ.

3.3 Nguyện vọng của thí sinh và chiến lược chọn trường

Mỗi thí sinh đưa ra danh sách nguyện vọng cá nhân của mình, hoàn toàn không phụ thuộc vào cơ hội trúng tuyển hay không. Nói cách khác, danh sách này là nguyện vọng của thí sinh nếu như được nhận tất cả các trường.

Nếu sử dụng thuật toán DAA của Gale Shapley với hướng thí sinh là bên “cầu hôn” (student proposer) thì cũng đồng nghĩa chiến lược chọn trường tốt nhất (best strategy) mà mỗi thí sinh nên làm là nộp danh sách nguyện vọng thực sự của mình. Đây là đặc tính nói thật (truth telling), hay là manipulation-proof, của phương pháp này.

Nếu chọn phương pháp khác, thì không đảm bảo đấy là best strategy, nên các thí sinh có thể chọn cách nộp danh sách không phải là nguyện vọng thực sự để tìm cách can thiệp (manipulate) vào kết quả cuối cùng. Đây cũng là một điểm quan trọng để chọn phương pháp “xe duyên”.

Việc mỗi thí sinh đưa ra một danh sách các trường theo nguyện vọng thực của mình còn tạo ra một sản phẩm phái sinh có ích. Đó là xếp hạng (ranking) các trường đại học dựa vào nguyện vọng được công bố (revealed preference).

Việc so sánh trực tiếp được 2 trường với nhau (bao nhiêu thí sinh thích trường A hơn B, so với bao nhiêu thí sinh thích trường B hơn A) có thể làm thước đo trực tiếp để các trường, khoa giống nhau có thể cạnh tranh và phấn đấu. Hiện giờ cũng có thể nhìn chút ít vào điểm chuẩn, nhưng thông tin từ đây rất ít so với dang sách nguyện vọng.

Đúng là không có phương pháp lựa chọn có được tất cả các yếu tố ưu việt nhưng trong trường hợp này DAA có vẻ như có nhiều yếu tố ưu việt quan trọng.

Vệc chọn kết quả tối ưu cho phe “cầu hôn” (thí sinh) là tương đối hợp lý nhìn từ quan điểm tối ưu cho người đề xuất (suitor-optimal) và bất lợi cho bên xét duyệt đề xuất (reviewer-pessimal). Trong ngữ cảnh các trường đại học công, phía thí sinh vào vai suitor sẽ không có vấn đề gì nghiêm trọng. Đại học công phục phụ cộng đồng, không phải là ngược lại.

Ví dụ gần với tuyển sinh cho đại học công của  Việt Nam nhất là đóng góp của Roth trong việc chọn trường trung học ở New York.  Xem thêm:http://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html

Tính ổn định (stability) là một yếu tố rất quan trọng, vì nó quyết định tính khả thi trong thực tế. Nếu không có tính ổn định, thì sẽ có những thí sinh  không chấp nhận mối kết duyên (match) của mình. Ví dụ thí sinh chỉ được nhận vào trường B, trong khi thích trường A hơn, mà có các bạn khác điểm thấp hơn vẫn được vào trường A. Đây là yếu tố có thể dẫn đến chuyện sụp đổ hoàn toàn hệ thống, dù cho có nhiều thí sinh được nguyện vọng số 1.

Về thỏa dụng xã hội (social utility). Rất khó để định nghĩa rõ ràng các lựa chọn xã hội (social choices). Có thể nhìn thấy rất nhiều trạng thái kết duyên không ổn định (non-stable matches) có giá trị hơn trạng thái cân bằng khi sử dụng DAA (student-proposer). Dựa vào trật tự Pareto (Pareto-order) trong các thí sinh  với nhau: trạng thái cân bằng DAA (student-proposer) chính là tối ưu Pareto. Có thể có nhiều trạng thái kết duyên không ổn định cũng là tối ưu Pareto, nhưng giữa các kết duyên ổn định thì  cân bằng DAA (student-proposer) hoàn toàn vượt trội.

Một đặc tính ưu việt của DAA (student-proposer) đó là việc thí sinh không thể can thiệp được vào kết quả. Đây là một tính chất rất đáng cân nhắc. Hiện nay rất nhiều thí sinh ở Việt Nam lựa chọn trường chỉ dựa vào khả năng được trường đó nhận học (thi đỗ) mà không quan tâm nhiều đến giá trị của ngành mình sẽ học, trường mình sẽ học. Hệ thống xét tuyển sử dụng DAA sẽ hiệu quả nếu các thí sinh nộp đơn với danh sách nguyện vọng thực tâm của mình.

IV. Đề xuất: Một số ý kiến

Nếu ứng dụng DAA vào xét tuyển đại học tập trung cho toàn quốc, cần phải có một trung tâm xét tuyển tập chung (centralized matching maker), tốt nhất là một cơ quan độc lập.

Hệ thống matching hoàn toàn có thể chỉ là một dạng định chế (institution), tức là một hệ quy tắc (system of rules) để thực hiện theo cách phi tập trung (decentralized). Tính ổn định của hệ thống giúp việc thực hiện phi tập trung hóa).

Yếu tố quan trọng nhất là  công bố thông tin trung thực (reveal truthful information) toàn bộ nguyện vọng của thí sinh. Trong dài hạn, đây là điểm cải thiện tính minh bạch trong xã hội.

Đề xuất các bước tiến hành:

a) Tìm hiểu xem liệu chính phủ và Bộ GD ĐT có mong muốn và có khả năng cải hiện hệ thống matching hiện nay giữa các đại học và thí sinh.

b) Nếu câu trả lời là có, mời thêm các nhà nghiên cứu đầu ngành về “matching markets” và các lĩnh vực liên quan để thành lập một nhóm nghiên cứu (study group) để nghiên cứu kỹ lưỡng các khả năng khác nhau. Mở rộng thảo luận ra nhiều đối tượng khác nhau, kể cả ra xã hội, về các ưu tiên của một hệ thống được coi là tốt.

c) Về chuyên gia, VED có thể mời sang cùng làm việc với MoET và Chính phủ: Giáo sư Parag Pathak (MIT) , Giáo sư Alvin Roth (Stanford, Giải Nobel Kinh Tế). Những cá nhân như Parag Pathak có kinh nghiệm vượt trội trong việc thiết kế một hệ thống matching cho thế giới thực cũng như đánh giá được hệ thống hiện tại. Có thể kể thêm một số nhà kinh tế khác đang nghiên cứu về matching markets: Fuhito Kojima (Stanford), Mihai Manea (MIT), Alfred Galichon (Sciences Po).

d) Chính phủ và MOET tổ chức hội thảo khoa học với các diễn giả quốc tế nói trên, để đánh giá hệ thống hiện tại và các cách tiếp cận để cải thiện hệ thống này. .

Ý kiến đề xuất trên đây chỉ có thể thực hiện được nếu nó gắn liền với mong muốn và trở thành một phần trong sáng kiến của MOET về cải cách xét tuyển chung. Nếu những nghiên cứu có thể đi đến một kết luận (nội bộ) cụ thể, MOET có thể sử dụng kết luận nội bộ này để xây dựng một nhóm chuyên trách trách (special team) bao gồm các chuyên gia của nhóm nghiên cứu.

Nhóm chuyên trách sẽ nghiên cứu thiết kế tốt nhất (best design) và trình lên MOET để đưa vào triển khai thử nghiệm (pilot), cũng như kiểm tra với dữ liệu (backtest) của kết quả thi 2015.

Quá trình thực hiện trong thực tế cần được theo dõi (monitor) và đánh giá (evaluation). Thành công trong dài hạn phụ thuộc nhiều vào việc đánh giá triển khai.

1. Đỗ Quốc Anh (Học viện Nghiên cứu Chính trị Sciences Po, Paris, Pháp)

2. Ngô Bảo Châu (Đại học Chicago, Hoa Kỳ và Viện nghiên cứu cao cấp về toán, Việt Nam)

3. Lê Hồng Giang (Brisbane, Úc)

4. Ngô Quang Hưng (Đại học bang New York ở Buffalo, Hoa Kỳ)

5. Vũ Hà Văn (Đại học Yale, Hoa Kỳ)

và các thành viên khác trong nhóm Đối Thoại Giáo Dục

 

Phụ Lục

Việc xét tuyển sẽ được thực hiện trên máy tính, theo một chương trình có nền tảng là thuật toán CHẤP NHẬN TRÌ HOÃN (DEFERED ACCEPTANCE ALGORITHM) do Gale và Shapley đưa ra năm 1964 [1] . (GS A. Roth.đã phát triển thuật toán này và áp dụng trong việc tuyển sinh các trường trung học ở Mỹ, điều tiết thị trường bác sĩ mới tại Mỹ, Anh và nhiều nước khác; nhờ đó đã được nhận giải Nobel về kinh tế năm 2012 cùng với  Shapley [2])

Hội đồng tuyển sinh trường quyết định tuyển chung 450 chỉ tiêu khối D1 cho cả 2 ngành a, b; tuyển riêng 200 chỉ tiêu khối A cho ngành a, 150 chỉ tiêu khối A cho ngành b, 300 chỉ tiêu khối D1 cho ngành c và 100 chỉ tiêu khối C cho ngành c. Khi đó trường X sẽ được chia thành 5 đơn vị xét tuyển: đơn vị 1 phụ trách khối D1 của hai ngành a, b; đơn vị 2 phụ trách khối A của ngành a; đơn vị 3 phụ trách khối A của ngành b; đơn vị 4 phụ trách khối D1 của ngành c, đơn vị 5 phụ trách khối C của ngành c.

Điểm thi = 2*Điểm môn Toán + Điểm môn Lý + Điểm môn Hóa.

Điểm thi = Điểm môn Toán + Điểm môn Lý + Điểm môn Hóa.