Tuyển sinh đại học và Sự ổn định của hôn nhân

“Gale-Shapley’s 1962 paper  on the stable marriage problem provides the first formal statement and proof of a problem that has far-reaching implications in many matching markets and is currently being applied in New York and Boston public school systems in assigning students to schools. In 2012 The Nobel Prize in Economics was awarded to Shapley for this work.”

Về việc áp dụng thuật toán DAA của Gale-Shapley trong xét tuyển

(Tác giả: Nhóm Đối Thoại Giáo Dục – Nguồn: hocthenao.vn)

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

I. Lý thuyết ‘xe duyên’ (matching) và thuật toán Gale-Shapley

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ể”. Lúc đó cung (các trường đại học) đáp ứng 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).

II. Ứng dụng vào kỳ Thi quốc gia ở Việt Nam

2.1 Một vài vấn đề cần cân nhắ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.

III. Một vài phân tích.

3.1 Về tính tự chủ của đại học

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.

3.2 Về tính cạnh tranh của toàn hệ thống đại học

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.

Ví dụ, trường A có thể có điểm chuẩn thấp hơn trường B, nhưng không phải vì A ít được ưa thích hơn so với B, mà lý do có thể là vì A nhận nhiều sinh viên hơn B, hoặc thậm chí cùng nhận 500 sinh viên, nhưng A nhận 400 em điểm trên 28 và 100 em điểm tầm 20 đến 21 (nên điểm chuẩn là 20), trong khi B nhận 400 em điểm từ 21 đến 22 (nên điểm chuẩn là 21). Đây không phải là cách duy nhất để xếp hạng các trường. Trước đây nhóm VED cũng đã bàn nhiều đến các cách xếp hạng dựa vào nội dung học, nhận xét của sinh viên, nhận xét của nhà tuyển dụng, khả năng sinh viên có việc vv. Ý tưởng ở đây là nguyện vọng được công bố (revealed preference) là một thông tin rất có giá trị cho việc đánh giá so sánh, nhất là về lâu dài, khi sinh viên có dự kiến và tự đánh giá tốt được vào mỗi trường sẽ như thế nào.

Lưu ý: để thực sự có được “revealed preference”, thì cách xe duyên (match) phải bảo đảm tính chất nói thật (truth telling), tức là thí sinh không can thiệp vào thứ tự nguyện vọng (manipulate preference order) của mình. Vì thế thuật toán DAA student-proposer lại có lợi thế nữa ở đây.

3.4 Tính ổn định và độ thỏa dụng xã hội của hệ thố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.

V. Nhóm Đối Thoại GIáo Dục

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

Năm 2014, từ thuật toán DAA, Đại học Thăng Long và Giáo Sư Hà Huy Khoái đã phát triển một thuật toán tuyển sinh và đã giới thiệu giải pháp này (đã được lập trình) tới Cục Khảo Thí.

HTN trích đăng phần giới thiệu giải pháp từ bản proposal của GS Hà Huy Khoái:

ĐỀ XUẤT MỘT PHƯƠNG ÁN TUYỂN SINH MỚI

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])

Cách tuyển sinh này có các điểm ưu việt sau:

Thí sinh được vào học trường tốt nhất có thể đối với kết quả thi của họ (được vào học trường cao nhất có thể theo thứ tự ưu tiên của họ, tương quan với số điểm mà họ có). Thí sinh có thể bày tỏ nguyện vọng thật sự của mình về việc chọn trường mà không cần thông tin về kết quả thi của mình và người khác;

Các trường có được danh sách trúng tuyển tốt nhất theo nguyện vọng của thí sinh;

Loại bỏ triệt để các trường hợp ‘ảo” (mỗi thí sinh chỉ trúng tuyển chính thức tối đa 1 nguyện vọng);

Tiết kiệm công sức của các trường và của thí sinh;

Tiết kiệm tiền cho gia đình thí sinh, giảm một khoản chi lớn cho xã hội;

Rút ngắn rất nhiều thời gian xét tuyển.

Theo phương án này, Ban tuyển sinh của Bộ sẽ chạy “chương trình xét tuyển” (mục 4) để xác định danh sách trúng tuyển cho từng “đơn vị xét tuyển” (mục 1) trên cơ sở công thức tính  “điểm xét tuyển” của các trường (mục 2), với dữ liệu từ “hồ sơ đăng ký tuyển sinh” của thí sinh (mục 3) và điểm thi của thí sinh.

Khái niệm “đơn vị xét tuyển”

Trong một kỳ tuyển sinh (theo phương thức “ba chung”), một cơ sở tuyển sinh (đại học, trường đại học, trường cao đẳng) sẽ được chia thành một hay nhiều “đơn vị xét tuyển” sao cho:

Mỗi đơn vị xét tuyển

chỉ tuyển sinh theo một khối thi duy nhất (có thể có nhiều ngành);

có một chỉ tiêu tuyển sinh chung, không quy định riêng cho từng ngành;

có cách tính điểm xét tuyển chung (xem phần sau), không phân biệt theo ngành.

Ví dụ 1: Trường X tuyển sinh 6 ngành: a, b, c, d, e và g. Ngành a thi khối A với  chỉ tiêu tuyển sinh là 100; ngành  b thi khối A với  chỉ tiêu tuyển sinh là 150; ngành c thi khối A với  chỉ tiêu tuyển sinh là 200; ngành d thi khối B với chỉ tiêu tuyển sinh là 100; ngành e thi khối B với chỉ tiêu tuyển sinh là 150; ngành g thi khối C với chỉ tiêu tuyển sinh là 200.

Hội đồng tuyển sinh trường quyết định tuyển sinh chung cho cả 3 ngành thi khối A với tổng chỉ tiêu là 450 rồi phân ngành sau, còn 2 ngành thi khối B thì tuyển riêng. Khi đó trường X sẽ được chia thành 4 đơn vị xét tuyển: đơn vị 1 phụ trách khối A của ba ngành a, b, c; đơn vị 2 phụ trách khối B của ngành d; đơn vị 3 phụ trách khối B của ngành e; đơn vị 4 phụ trách khối C của ngành g.

Ví dụ 2: Trường Y tuyển sinh 3 ngành: a, b và c. Ngành a nhận 200 thí sinh thi khối A và 200 thí sinh thi khối D1; ngành b nhận 150 thí sinh thi khối A và 250 thí sinh thi khối D1; ngành c nhận 300 thí sinh thi khối D1 và 100 thí sinh thi khối C.

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.

Chú ý: Đơn vị xét tuyển là “ảo” về mặt nhân sự. Nói cách khác, không cần có nhân sự nào cho các đơn vị xét tuyển.

Khái niệm “Điểm xét tuyển”

Mỗi đơn vị xét tuyển có một cách tính “Điểm xét tuyển” theo quy định của Hội đồng tuyển sinh trường.

Điểm xét tuyển là tổng của điểm thi  và một số điểm cộng.

Điểm thi là tổng điểm các môn thi tuyển sinh của thí sinh (có thể có môn được nhân hệ số).

Các điểm cộng gồm: điểm ưu tiên khu vực (bắt buộc), điểm ưu tiên đối tượng (bắt buộc), điểm ưu tiên nguyện vọng 1 (không bắt buộc). Sau này, khi điều kiện thuận lợi hơn, một số trường có thể đưa thêm các điểm cộng mới như: điểm thành tích học tập ở bậc trung học. điểm thành tích về thể thao, hoạt động xã hội…

Ví dụ 1: Điểm thi của đơn vị xét tuyển α của trường X được tính như sau:

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

Ví dụ 2: Điểm thi của đơn vị xét tuyển β của trường Y được tính như sau:

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

Việc đăng ký nguyện vọng của thí sinh

Trước kỳ thi tuyển sinh 3 – 4 tháng, các trường đại học công bố các ngành tuyển sinh, các khối thi, chỉ tiêu tuyển sinh và cách xác định điểm xét tuyển của các đơn vị xét tuyển của trường trên các phương tiện thông tin đại chúng và chuyển các dữ liệu đó cho Ban Tuyển sinh của Bộ GD và ĐT.

Trên cơ sở các thông tin của các trường, điều kiện và nguyện vọng của bản thân, mỗi thí sinh sẽ đăng ký dự thi tuyển sinh.

Phương án 1

Thí sinh thực hiện đăng ký dự thi tuyển sinh trên giấy theo mẫu mới của Bộ Giáo dục và Đào tạo. Điểm khác cơ bản của mẫu mới so với mẫu cũ là thí sinh có thể đăng ký tới 10 nguyện vọng theo thứ tự ưu tiên từ 1 đến 10 (số 10 là số tạm đề xuất, có thể thay bởi 1 số khác lớn hơn hay nhỏ hơn). Thí sinh không nhất thiết phải đăng ký đủ 10 nguyện vọng, nhưng bắt buộc phải đăng ký nguyện vọng 1. Nơi tiếp nhận hồ sơ đăng ký dự thi của thí sinh có trách nhiệm kiểm tra và xác nhận tính chính xác của các dữ liệu thí sinh kê khai trong hồ sơ, đặc biệt là các dữ liệu liên quan đến việc cộng điểm.

Cũng như trước đây, hồ sơ đăng ký dự thi của thí sinh được chuyển về trường nơi thí sinh sẽ dự thi để trường đó nhập vào máy tính và chuyển dữ liệu cho Bộ GD và ĐT.

Phương án 2

Thí sinh thực hiện đăng ký dự thi tuyển sinh như trước đây. Sau khi các trường công bố kết quả chấm thi, thí sinh sẽ đăng ký các nguyện vọng bổ sung theo thứ tự ưu tiên từ 2 đến 10 (cũng như trên, số 10 là số tạm đề xuất, và thí sinh không bắt buộc phải điền đủ cả 9 nguyện vọng bổ sung). Cách đăng ký nguyện vọng bổ sung cần phải nghiên cứu kỹ thêm, có thể qua các trường trung học phổ thông và các Sở Giáo dục và Đào tạo, hoặc qua đường bưu điện, hay qua mạng máy tính …

So sánh 2 phương án:

Phương án 1 thuận tiện trong việc đăng ký các nguyện vọng bổ sung và không làm tăng thời gian xét tuyển, tuy nhiên phương án này có nhược điểm: thí sinh thiếu dữ liệu quan trọng là điểm thi để lựa chọn các nguyện vọng bổ sung.

Phương án 2 gặp phải rắc rối trong việc đăng ký các nguyện vọng bổ sung và làm tăng thời gian xét tuyển nhưng lại có ưu điểm là thí sinh đã biết  điểm thi khi lựa chọn các nguyện vọng bổ sung.

Như sẽ thấy sau đây, việc biết điểm thi không quá quan trọng đối với thí sinh để đưa ra nguyện vọng. Điều cốt yếu là thí sinh phải đưa đúng nguyện vọng THẬT, không phụ thuộc kết quả của mình so với người khác. Nếu thí sinh không nêu đúng nguyện vọng thật của mình thì chính họ là người bị thiệt thòi. Vì thế có thể chỉ cần Phương án 1.

—————–&&——————

Bài toán tuyển sinh trong Mechanism Design và Game Theory

(Tác giả: Nguyễn An Nguyên – Nguồn: hocthenao.vn)

***

1. Vấn đề thiết kế cơ chế tuyển sinh thuộc lớp bài toán kinh điển (1), đã giải xong từ những năm 1960s.

Lời giải cho bài toán này khá đơn giản, và đã được áp dụng thành công ở các tình huống tương tự. Chẳng hạn như chương trình tuyển bác sỹ nội trú ở Mỹ (2).

Đúng ra, đây phải là điểm khởi đầu của đề án cải cách tuyển sinh của Bộ GD, và trung tâm của cuộc tranh luận. Vì thế, tôi ngạc nhiên vì các bên quan tâm vẫn chưa đề cập tới.

***

2a. Phương án tối ưu là thu thập thông tin về thứ tự ưu tiên từng trường (school preference) của các học sinh, và đưa về một trung tâm xử lý cho cả nước (3).

Ví dụ, Bộ, thông qua các trường THCS, phát phiếu đăng ký tuyển sinh đến từng học sinh, với 10 – 20 lựa chọn theo thứ tự ưu tiên (ví dụ, 1. ĐH Quốc gia HN, ngành Máy tính; 2. Đại học Bách khoa HN, ngành Tự động hoá .v.v.). Các phiếu đăng ký này được gom về trung tâm xử lý.

Trung tâm này nhập liệu, kết hợp với thông tin về chỉ tiêu của từng bộ môn của các trường, dùng thuật toán để sắp xếp học sinh vào các trường.

Phương án này là công bằng và tối ưu (xem chú thích 1), đồng thời tiết kiệm nhất, vì chỉ cần khớp tuyển một lần (xem chú thích 2).

2b. Phương án hiện nay không hiệu quả là vì cả Bộ và các trường ĐH không biết thông tin về sở thích trường của học sinh (private information), cho đến khi họ nộp và rút đơn nhiều lần.

Tình trạng nộp/rút nhiều lần (“unstable marriage”) không những là kết quả, mà còn là cơ chế để hệ thống tìm ra thông tin về sở thích trường của các em học sinh.

Ngoài việc tốn kém, thì kết quả chung cuộc của cơ chế này vẫn không tối ưu.

Đấy là điều đáng tiếc.

***

3. Tuy thế, tôi vẫn trân trọng việc Bộ Giáo dục nhận thức được việc cần thay đổi cơ chế tuyển sinh, và đã thử nghiệm.

Học kỹ để làm nhanh thì tất nhiên là tốt hơn. Nhưng làm trước học sau, gắng chịu búa rìu dư luận để sửa chữa thì vẫn hơn là không làm gì.

Xin chia sẻ với các vị phụ huynh và các em học sinh phải chạy đôn chạy đáo trong những ngày hè nóng nực này. Hi vọng là từ 2016, chuyện này sẽ chỉ còn là một ký ức, như thời xếp hàng mua gạo.

—————————————

(1) Bài toán Tuyển sinh có thể được quy về Stable Marriage Problem, một chủ đề yêu thích của sinh viên ngành Mechanism Design và Game Theory.

Đề bài như sau: cho tập N trường học với chỉ tiêu c1, …, cN. Mỗi trường đều ưu tiên học sinh có điểm cao. Cho tập M học sinh i với thứ tự ưu tiên i1 > i2 >… > iM. Hãy ghép học sinh với các trường sao cho không tồn tại:
– học sinh H không được nhập học, hoặc thích trường T mà không vào được, trong khi
– trường T vẫn còn thừa chỗ, hoặc là đang nhận học sinh H’ có điểm thấp hơn H.

Tiêu chí này chính là tối ưu Pareto trong bài toán này.

Bạn nào hứng thú tìm lời giải thì có thể đọc từ Gale & Shapley-1962 (College Admissions and the Stability of Marriage) trở đi. Tiếc là tôi không chuyên về Mechanism Design, và từ lâu không nghiên cứu Kinh tế học nên không còn cập nhật.

Các bạn sinh viên ngành toán và computer science thì nên tự giải.

P/S: Các bạn giải xong thì nên nói chuyện với Trusting Social. smile emoticon Đây là startup dùng Big Data để giải quyết bài toán giúp người nghèo vay tiền, do tôi đồng sáng lập.

(2) https://goo.gl/B9AguK. Bài toán này còn đơn giản hơn là National Resident Matching Program như ví dụ trên, vì hiện tại các trường ĐH ở Việt Nam chỉ dựa trên điểm thi để nhận học sinh mà không cần xét tuyển từng học sinh. Trung tâm Xử lý có thể khớp học sinh/trường ĐH không cần đợi điểm chuẩn từ các trường.

(3) Trung tâm có thể là một công ty tư nhân, như https://natmatch.com/

——————-&&——————

TS Lương Hoài Nam đề xuất dùng thuật toán tuyển sinh

(Tác giả: Lương Hoài Nam – Nguồn: vnexpress.net)

Trong một kỳ tuyển sinh đại học, cao đẳng, dù ở nước ta hay các nước khác, số lượng thí sinh luôn lớn, từ hàng chục nghìn đến hàng trăm nghìn, thậm chí hàng triệu. Trong thâm tâm, mỗi thí sinh có nhiều nguyện vọng đại học, mỗi nguyện vọng lại có mức độ ưu tiên khác nhau, kiểu như “Tôi ao ước nhất là được vào trường này để học ngành này, còn bét ra thì vào trường kia để học ngành kia”. Có nguyện vọng cao nhất, có nguyện vọng thấp nhất và giữa chúng là các nguyện vọng khác.

Trong một kỳ tuyển sinh, số lượng trường tuyển sinh cho các ngành đào tạo cũng là một số lớn, với số lượng các cặp “trường – ngành” từ hàng trăm đến hàng nghìn, thậm chí đến hàng chục nghìn. Trường nào cũng muốn thu hút được học sinh giỏi cho các ngành đào tạo để có chất lượng đầu ra tốt và tạo được uy tín đào tạo đại học tốt.

Tuyển sinh đại học là một việc khó. Để làm tốt nó, phải sử dụng các thuật toán để biến nó từ khó trở nên dễ.

Trong lịch sử tuyển sinh đại học, nước ta từng sử dụng một thuật toán rất đơn giản nhưng khá được việc. Đó là cho phép mỗi thí sinh đăng ký duy nhất một ngành ở duy nhất một trường và xét chọn theo điểm từ trên xuống dưới, cho đến khi lấy đủ chỉ tiêu vào ngành đó của trường đó. Các thí sinh không được nhận vào trường duy nhất đó mặc nhiên trượt đại học. Thuật toán này dễ hiểu, dễ dùng, có thể làm bằng tay, không cần có phần mềm tuyển sinh. Excel đã là xa xỉ.

Nhưng thuật toán tuyển sinh đơn giản đó bất cập ở chỗ làm cho không ít thí sinh giỏi bị trượt đại học vì đăng ký thi vào cặp trường – ngành có mức cạnh tranh cao (mà thí sinh không thể biết trước). Trong khi đó, các học sinh yếu hơn lại đậu đại học vào các cặp trường – ngành có điều kiện tuyển sinh dễ hơn. Một số em giỏi hơn bị trượt đại học có thể vui vẻ vào học ở các trường – ngành tuyển sinh dễ hơn, nhưng thuật toán tuyển sinh áp dụng đã loại bỏ cơ hội của em ngay từ đầu.

Để giải quyết bất cập trên, hầu hết các nước đã cho phép thí sinh đăng ký nhiều nguyện vọng xét tuyển đại học trong một kỳ tuyển sinh. Việc tuyển sinh đại học trở nên phức tạp hơn nhiều và phải dùng thuật toán khác. Đó là thuật toán “Hôn nhân ổn định” (Stable Marriage) do Gale và Shapley (Mỹ) đưa ra vào năm 1962. Đối với cách tuyển sinh tập trung (Bộ Giáo dục chủ trì) và cách tuyển sinh phân tán (mỗi trường tự thực hiện), thuật toán này được sử dụng theo các cách khác nhau.

Trong trường hợp tuyển sinh tập trung, tôi xin mượn bảng tính Excel để mô tả một cách trực quan khả năng sử dụng thuật toán của Gale và Shapley, theo hình dung của tôi, như sau:

Ký hiệu một cặp “trường – ngành” là TxNy, trong đó T là mã trường, N là mã ngành. Trên một hàng của bảng Excel, điền tất cả cặp TxNy cho tất cả các trường, ngành tuyển sinh trong kỳ. Phía trên mỗi cặp TxNy, ghi tất cả điều kiện tuyển sinh vào cặp “trường – ngành” đó (khối thi, điểm thi tối thiểu của từng môn thi, tổng điểm thi tối thiểu của các môn thi, tổng số chỉ tiêu tuyển sinh…). Cho tất cả thí sinh cùng với kết quả thi của họ, tất cả nguyện vọng tuyển sinh của họ và thứ tự ưu tiên của mỗi nguyện vọng vào một “Đám mây thí sinh”. Kết thúc việc nhập thông tin đầu vào ở đây.

Chạy một bộ lệnh trên Nguyện vọng thứ nhất để “nhặt” từ Đám mây thí sinh vào mỗi một cột và tất cả các cột TxNy các thí sinh đạt điều kiện tuyển sinh, theo kết quả thi từ cao xuống thấp, cho đến khi mỗi cột đạt đủ chỉ tiêu tuyển sinh (hoặc cho đến khi không tìm được thêm thí sinh đạt điều kiện tuyển sinh theo Nguyện vọng thứ nhất nữa). Lập một Danh sách trúng tuyển sơ bộ cho mỗi cột TxNy, đồng thời, đánh đấu “Từ chối” tất cả các thí sinh khác có Nguyện vọng thứ nhất vào các cột.

Chạy một bộ lệnh trên Nguyện vọng thứ hai của Những người bị từ chối ở Nguyện vọng thứ nhất theo cách tương tự như trên và điều chỉnh Danh sách trúng tuyển sơ bộ ở mỗi cột trên cơ sở Danh sách trúng tuyển sơ bộ được lập theo Nguyện vọng thứ nhất và các thí sinh mới đạt điều kiện tuyển sinh theo Nguyện vọng thứ hai, xếp theo kết quả thi của các thí sinh từ cao xuống thấp, cho đến khi mỗi cột đạt đủ chỉ tiêu tuyển sinh (hoặc cho đến khi không tìm được thêm thí sinh đạt điều kiện tuyển sinh theo Nguyện vọng thứ hai trong số Những người bị từ chối ở Nguyện vọng thứ nhất).

Tiếp tục làm tương tự theo Nguyện vọng thứ ba, Nguyện vọng thứ tư,… và kết thúc ở nguyện Nguyện vọng thứ “n”. Đó là khi mà mỗi một thí sinh hoặc là đã nằm ở các Danh sách trúng tuyển sơ bộ, hoặc đã bị tất cả các cặp TxNy, mà thí sinh đó đăng ký đánh dấu “Từ chối”. Sau bước thứ “n”, các Danh sách trúng tuyển sơ bộ ở các cột sẽ trở thành các Danh sách trúng tuyển chính thức. Tất cả các thí sinh còn lại trong Đám mây thí sinh là những thí sinh trượt đại học trong kỳ tuyển sinh.

Để kiểm tra tính chính xác của việc tuyển sinh, cần “chạy” chương trình nhiều lần và đối chiếu kết quả giữa các lần. Về nguyên tắc, kết quả tuyển sinh trong tất cả các lần thực hiện phải tuyệt đối giống nhau. Mặc dù vậy, khi sử dụng thuật toán tuyển sinh này, vẫn có thể phát sinh một số trường hợp ngoại lệ, cần sự cân nhắc và can thiệp của con người.

Trong trường hợp tuyển sinh phân tán (các trường tự tuyển sinh, Bộ Giáo dục không can thiệp), việc áp dụng thuật toán này phức tạp hơn. Lý do là mỗi trường biết việc thí sinh đăng ký vào một hoặc một số cặp TxNy của trường mình, nhưng lại không biết thí sinh còn đăng ký tuyển sinh vào những trường khác, cũng không biết mức độ ưu tiên của từng nguyện vọng của thí sinh. Việc tuyển sinh trong trường hợp đó không thể kết thúc ngay trong một đợt, mà phải qua nhiều đợt.

Tôi xin sử dụng ngôn ngữ mô tả rất sinh động và thú vị của GS Vũ Hà Văn trong bài viết “Lấy người mình yêu và… không bỏ được”: “Trong bước thứ nhất, mỗi anh chàng sẽ ngỏ lời với cô gái mà anh ta thích nhất. Tất nhiên, cô nào sáng giá sẽ có nhiều cây si. Mỗi cô gái sẽ trả lời một cách lửng lơ “Để tớ xem!”, với anh chàng sáng giá nhất trong những cây si, và đá đít thẳng thừng những chàng còn lại. Sau bước này, nàng coi như có hẹn ước với cây si cao nhất đó, và chàng cũng coi như có hẹn ước với nàng.

Trong những vòng tiếp theo, mỗi chàng trai chưa có hẹn ước sẽ ngỏ lời với cô gái mà anh ta thích nhất vẫn còn nằm trong danh sách những cô chưa đá đít anh ấy. Anh chàng sẽ không quan tâm là cô gái đó đã có hẹn ước hay chưa. (Chiến thuật mặt dày này được ứng dụng tương đối hiệu quả sau khi thuật toán “bố mẹ đặt đâu con ngồi đấy” trở nên lỗi thời trong một số năm gần đây.) Về phần các cô gái, nếu được một anh chàng mới ngỏ lời, nàng sẽ cân nhắc so sánh với cây si hiện có (nếu có), và sẽ giữ lại cây cao điểm hơn”.

Chúng ta có thể thay các chàng bằng các thí sinh, còn các nàng bằng các trường đại học. Tất nhiên, trong trường hợp tuyển sinh phân tán, các trường đại học còn sử dụng các phương pháp tuyển sinh khác. Do trường toàn quyền quyết định việc tuyển sinh, họ hoàn toàn có thể xét và xác nhận kết quả tuyển sinh với từng thí sinh đăng ký vào trường mình, mà không quá phụ thuộc vào thuật toán tuyển sinh như trong trường hợp tuyển sinh tập trung.

——————–&&——————-

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

%d bloggers like this: