I. GIỚI THIỆU

 

Mỗi năm, 75 ngàn học sinh khối lớp 8 ở New York đăng kí nhập học vào 1 trong 426 trường trung học công lập của thành phố. Cho đến gần đây, quy trình này đòi hỏi học sinh phải liệt kê 5 ngôi trường theo thứ tự ưu tiên. Những danh sách này được gửi đến những ngôi trường, nơi sẽ quyết định ai sẽ được nhận vào, ai sẽ ở danh sách chờ, hoặc ai sẽ bị từ chối. Học sinh được thông báo về tình hình của họ và chỉ được phép chấp nhận một lời mời (vào một trường) và một vị trí ở danh sách chờ. Sau khi những học sinh đã phản hồi lại bất cứ lời mời nào nhận được, những ngôi trường với những vị trí còn trống sẽ thực hiện đợt tuyển sinh thứ 2, và quá trình này sẽ tiếp diễn tới khi kết thúc đợt thứ 3.

 

Nhưng quy trình này có một vài sai sót nghiêm trọng. Vào lúc kết thúc đợt tuyển sinh thứ 3, gần một nửa số học sinh (thường là những học sinh đến từ những gia đình nghèo khó) không được nhận vào trường. Đa số những học sinh đó chờ đợi qua hết mùa hè chỉ để nhận ra được rằng họ đã bị đưa vào một ngôi trường không nằm trong danh sách 5 trường họ chọn.

 

Quy trình này cũng khuyến khích học sinh và bậc phụ huynh suy nghĩ một cách có chiến lược về danh sách các ngôi trường họ muốn đăng ký. Những học sinh bị từ chối bởi ngôi trường đứng đầu trong danh sách của họ có thể phát hiện được rằng ngôi trường ở lựa chọn thứ hai đã không còn chỗ trống ở đợt tuyển sinh thứ 2. Điều này sẽ làm cho nhiều học sinh khó có thể đưa ra những ưu tiên chọn trường theo đúng nguyện vọng của bản thân vì ẩn chứa nhiều rủi ro. Một quan điểm được các nhà Giáo dục học đưa ra cho các học sinh nên:“Xác định mình sẽ cạnh tranh với ai” trước khi đưa ra danh sách những ngôi trường ưa thích.

 

Sau cùng, những ngôi trường sẽ luôn cập nhật chỉ tiêu tuyển sinh khác với dự kiến để giữ chỗ những vị trí cho những học sinh không được nhận vào ngôi trường đầu tiên mà họ chọn.

 

Tóm lại, quy trình này không thể làm hài lòng nhiều học sinh bất chấp nó khuyến khích nhiều phía, cả học sinh lẫn nhà trường, nên tự đưa ra những chiến lược sai nhằm đạt được những kết quả đáng mong đợi mặc dù không khả thi cho lắm. Tính nghi ngờ phổ biến ở quy trình sắp xếp này là môt hệ quả hiển nhiên.

 

Với ý tưởng được miêu tả ở mục này, những nhà kinh tế học Atila Abdulkadiroglu, Parag Pathak và Alvil Roth đã thiết kế một phép nối giữa trường học và học sinh, thực hiện lần đầu tiên vào năm 2004. Thuật toán được số hóa mới này đã giúp khoảng 3000 học sinh mỗi năm và kết quả là những học sinh đã nhận được lời mời từ những ngôi trường nằm ở lựa chọn thứ 1 trong danh sách. Kết quả là bây giờ học sinh đưa ra những danh sách nói lên những ưu tiên thật sự của họ, điều này sẽ cung cấp chính thức cho những ngôi trường với những đầu vào công khai nhằm xác định ngôi trường nào sẽ đóng cửa hoặc cải cách. Về phía các trường học, những ngôi trường nhận thấy rằng việc đưa ra chỉ tiêu không đúng với khả năng thực sự không còn lợi ích gì nữa.

 

Chìa khóa của giải thuật toán này nằm ở khái niệm ổn định, giới thiệu lần đầu tiên vào năm 1962 và được viết bởi Gale và Shapley. Chúng ta nói rằng một phép nối giữa học sinh và nhà trường là “ổn định” khi không có một học sinh hay một trường nào khác muốn được ghép với nhau hơn là cặp nối hiện tại của họ. Gale và Shapley đã giới thiệu một thuật toán, thường được gọi là thuật toán chấp nhận trì hoãn, sẽ giúp ta chắc chắn đưa ra được một phép nối ổn định. Sau đó, Roth cho thấy rằng khi áp dụng thuật toán chấp nhận trì hoãn, một học sinh không thể tăng nguyện vọng vào nhiều ngôi trường họ thích bằng cách đưa ra chiến lược sai lệch, không đúng với nguyện vọng thực sự của bản thân.

 

Mục này sẽ giới thiệu về kết quả lý thuyết trò chơi nằm trong bài viết gốc của Gale – Shapley cùng với những phân tích sau này của Roth. Pathak gọi thuật toán chấp nhận trì hoãn là “một trong những ý tưởng hay nhất của kinh tê” và Roth và Shaley đã được trao giải thưởng Nobel về kinh tế vào năm 2012 cho công trình này.

 

II. VẤN ĐỀ ỔN ĐỊNH HÔN NHÂN

 

Bên cạnh việc ghép nối những học sinh với những ngôi trường, thuật toán chấp nhận trì hoãn đã được áp dụng rộng rãi trong nhiều trường hợp, điển hình như việc ghép học sinh khoa Y với chương trình nội trú. Và theo đó, chúng ta sẽ cùng mô tả thuật toán này qua một ngữ cảnh độc đáo của Gale – Shaley, vấn đề về ổn định hôn nhân.

 

Giả sử ta có số lượng bằng nhau giữa đàn ông M={m1,…,mn} và phụ nữ W={w1,…., wn}Mỗi người đàn ông đưa ra danh sách những người phụ nữ đang theo đuổi, theo thứ tự ưu tiên của họ, và tương tự mỗi người phụ nữ cũng sẽ đưa ra danh sách những người đàn ông mà cô ta thích theo thứ tự ưu tiên. Ta muốn sắp xếp những cuộc hôn nhân giữa những người đàn ông và người phụ nữ sao không có người đàn ông hay phụ nữ nào thích một người khác bạn đời của họ.

 

Trước khi ta đi xa hơn, hãy thống nhất rằng mục đích của chúng ta là mô hình hóa một vấn đề toán học. Chẳng hạn, chúng ta sẽ không xét đến thực tế về việc hôn nhân đồng tính nam hay nữ và không xét đến trường hợp phụ nữ sẽ thường cầu hôn với nam giới .Những vấn đề này đều dẫn đến những tình huống toán học khác hoàn toàn với vấn đề mà ta đang xét.

 

Hơn thế nữa, điều này liên quan trực tiếp đến việc mở rộng vấn đề sang những tình huống khi số lượng giữa đàn ông và phụ nữ khác nhau hoặc khi ta cho phép nối đa thê, khi những người trong một nhóm có thể được ghép với những người ở nhóm khác, tương tự như khi ta áp dụng những ngôi trường nhận vào nhiều hơn một học sinh.

 

Bằng một phép nối, chúng ta muốn nói về một phép tương đương một – với – một x:M→W. Một phép nối x là không ổn định khi có một người đàn ông m và một người phụ nữ w  sao cho m thích w hơn x(m) và w thích m hơn x−1(w) như hình minh họa bên dưới. Ngược lại phép nối sẽ được gọi là ổn định.

Ở bài viết vào năm 1962, Gale và Shapley chứng minh rằng sẽ luôn có một phép nối ổn định khi cho trước một tập ưu tiên của mỗi người đàn ông và phụ nữ. Hơn thế nữa, họ cho ta thấy được cách để tìm được phép nối ổn định bằng cách chấp nhận thuật toán chấp nhận trì hoãn, điều mà bây giờ ta sẽ cùng miêu tả.

 

Bước 1:

– Mọi người đàn ông đều cầu hôn với người phụ nữ đầu tiên trong danh sách những người mà họ cảm thấy thích.

– Tùy theo điều kiện mà một người phụ nữ sẽ nhận lời từ người đàn ông mà họ thấy có cảm tình hơn những người khác. Sau đó, họ sẽ từ chối những lời cầu hôn còn lại.

 

Bước k:

– Những người đàn ông chưa có điều kiện ngỏ lời cầu hôn một người phụ nữ mà anh ta thích nhất trong số người chưa từ chối anh.

– Những người phụ nữ sẽ xem xét ở bước này có người đàn ông nào khác ngỏ lời nữa không và bất kì người đàn ông nào trước đây cô ấy đã chấp nhận và chấp nhận lời cầu hôn từ người đàn ông mà cô ấy thích nhất, thậm chí điều đó cũng có nghĩa là từ chối người đàn ông trước đây cô ta đã chấp nhận.

 

Kết thúc: Quá trình này tiếp diễn cho đến khi mỗi người phụ nữ đã chính thức chấp nhận lời cầu hôn. Ở bước này, thuật toán kết thúc và w=x(m) khi w nhận m làm bạn đời của mình.

Hãy cùng thực hiện dụng một ví dụ áp dụng thuật toán trên của Gale và Shapley để xem như thế nào. Giả sử có 4 người phụ nữ {w1,w2,w3,w4}và 4 người đàn ông {m1, m2, m3, m4} thứ tự ưu tiên đã được chỉ ra ở phía dưới, theo thứ tự từ trên xuống.

 

Bước 1: Mỗi người đàn ông cầu hôn người phụ nữ họ thích nhất:

·         m1 cầu hôn w1

·         m2 cầu hôn w1

·         m3 cầu hôn w2

·         m4 cầu hôn w4

Nhận thấy  rằng w1 nhận được 2 lời cầu hôn từ m1 và m2. Cô ấy chọn lời cầu hôn từ m1 vì cô ấy thích m1 hơn m2.

Bước 2: Khi m2 bị w1 từ chối, anh ấy cầu hôn với người anh thích thứ hai là w4.

Và bây giờ khi w4 đã có hai lời cầu hôn từ m2 và m4, cô ấy đã chọn lời cầu hôn đến từ m2.

Bước 3: m4 cầu hôn w2

Khi đó w2 đã chấp nhận m4 và từ chối m3.

Bước 4:

 

Bước 5:

 

Bước 6:

 

Bây giờ chúng ta được ghép nối x(m1)=w3, x(m2)=w4, x(m3)=w1), và x(m4)=w2

 

Chú ý rằng nếu m cầu hôn w tại một bước nào đó của thuật toán và w′′ ở bước kế tiếp thì m phải thích w hơn w′′. Điều này có nghĩa là m không thể cầu hôn một người phụ nữ 2 lần vì sẽ làm cho thuật toán kết thúc.

Ngoài ra, chúng ta cũng thấy rằng m cầu hôn với mỗi người phụ nữ anh ấy thích nhiều hơn so với người tình của anh ấy là x(m) trước khi cuối cùng cầu hôn x(m). Điều này có nghĩa là nếu m thích w hơn x(m) thì w sẽ từ chối m tại một số bước của thuật toán.

 

Ngược lại, nếu w chấp nhận m tại một bước của thuật toán và m′ ở bước sau thì có nghĩa là w thích m′ hơn m. Điều này có nghĩa là người đàn ông cầu hôn w đã bị từ chối ở dòng dưới x−1(w) trong danh sách yêu thích của cô ấy.

Bây giờ có thể dễ dàng thấy rằng phép nối được cung cấp bởi thuật toán Gale – Shapley là ổn định. Giả sử người đàn ông m thích người phụ nữ w hơn người tình của m là x(m), tại một số bước của thuật toán Gale – Shapley, m cầu hôn w. Vì w không phải là người tình cuối cùng của m, cô ấy phải từ chối m, nghĩa là cô ấy thích x−1(w) hơn m . Vì vậy thật không khả thi khi m và w thích nhau hơn người tình của họ.