Khi kinh tế học nghiên cứu về cách "ghép đôi"

Phóng to

Lloyd Shapley (trái) và Alvin Roth, đồng chủ nhân Nobel kinh tế 2012 - Ảnh: Reuters

Vào năm 1962, khi Shapley mới 39 tuổi và là một nhà toán học làm ở Rand Corp - một think-tank đầy quyền lực - nơi chuyên nghiên cứu các dự án hạng nặng cho Bộ Quốc phòng Mỹ, ông và một nhà kinh tế khác thuộc Đại học Brown là D. Gale đăng công trình nghiên cứu “Tuyển sinh đại học và sự ổn định của hôn nhân” trên tạp chí American Mathematical Monthly. Lúc đó, Shapley chắc chắn không tưởng tượng ra 50 năm sau, ông được trao giải Nobel kinh tế nhờ các nghiên cứu khởi nguồn từ bài báo hết sức đơn giản đó.

Từ một thuật toán đơn giản...

Tất cả những gì Shapley và Gale hình dung ra là một thuật toán (algorithm). Nghiên cứu này bắt đầu bằng một quan sát: Trong một số vấn đề của xã hội và kinh tế, tương tác giữa các cá nhân và các tổ chức không đơn giản bằng việc gặp gỡ mua bán hoặc ký hợp đồng như mua bánh mì ở cửa tiệm hoặc thuê thợ sửa ống nước. Với các giao dịch kinh tế bình thường, người bán phát giá bán, người mua đến mặc cả, thỏa thuận giá, và nếu thỏa thuận thành công thì chuyện mua bán diễn ra.

Shapley và Gale quan sát thấy một số trường hợp, thí dụ như việc tuyển sinh ở các trường đại học hay việc tìm kiếm bạn đời của mỗi người, giao dịch liên quan đến một dạng tương tác mà sau này các nhà kinh tế học gọi là “ghép đôi” (matching).

Trong trường hợp tuyển sinh đại học, giả sử một cách đơn giản là có 10.000 sinh viên đầu vào và có 10 trường đại học, mỗi trường tuyển 1.000 sinh viên. Chuyện nghe đơn giản, nhưng nó phức tạp ở chỗ mỗi sinh viên lại có trình độ khác nhau, sở thích của các sinh viên này đối với các trường đại học cũng khác nhau. Như thế, giả sử một trường đại học bất kỳ nhận được 2.000 hồ sơ dự tuyển, thì họ phải loại đi bao nhiêu và giữ lại bao nhiêu hồ sơ khi biết rằng nhiều sinh viên trúng tuyển không tham gia học ở trường đó vì họ được nhận vào trường khác mà họ thích hơn?

Tương tự, trong vấn đề hôn nhân, giả sử số đàn ông và phụ nữ đến tuổi kết hôn nhưng còn độc thân bằng nhau. Vấn đề “ghép đôi” sẽ như thế nào? Mỗi người đàn ông sẽ có những tiêu chuẩn riêng, dẫn tới chuyện có những người phụ nữ mà anh ta muốn “ghép đôi”. Phụ nữ cũng thế, mỗi người có mẫu đàn ông mà họ muốn lập gia đình cùng.

Rõ ràng không thể có chuyện một người đàn ông nào cũng được ghép với người phụ nữ tuyệt vời nhất trên thế gian (vì người đó chỉ có một), và ngược lại, không thể có chuyện phụ nữ nào cũng cưới được người chồng lý tưởng nhất (vì anh chàng đó cũng chỉ có một). Câu hỏi đặt ra là trong các trường hợp đó, làm thế nào để việc ghép đôi có thể thực hiện được một cách hiệu quả?

Shapley và Gale đưa ra một khái niệm sau này được gọi là “ghép đôi ổn định” (stable matching). Một kết quả ghép đôi ổn định là trường hợp mà sau khi ghép đôi xong, không xảy ra chuyện nó có thể bị phá vỡ. Ngược lại, nếu kết quả ghép đôi tạo ra hai cặp vợ chồng (A, m) và (B, n) nhưng A lại muốn sống với B và B cũng muốn sống với A, tức là đối với cả hai người này nếu được ghép thành (A, B) thì sẽ tốt hơn cho cả hai, thì kết quả ghép đôi ban đầu sẽ bị coi là không ổn định. Theo Shapley và Gale, ghép đôi ổn định đòi hỏi không có bất cứ một cặp nào muốn phá vỡ kết quả ghép đôi đó để đến với nhau.

Đó là về mặt quan sát thực tiễn, nhưng làm thế nào để đưa ra một phương pháp ghép đôi mà kết quả của nó là ổn định, thậm chí tốt nhất - tức là kết quả vừa ổn định vừa tốt nhất trong số các kết quả ổn định? Shapley và Gale đưa ra một thuật toán mà sau này trở nên nổi tiếng với tên gọi thuật toán Gale-Shapley. Hai ông chứng minh được rằng nếu triển khai theo thuật toán này, thì mọi bài toán ghép đôi giống như các bài nêu trên sẽ luôn có lời giải là một kết quả ghép đôi ổn định và tốt nhất.

Hãy giả sử một trường hợp đơn giản là số nam và số nữ bằng nhau, theo thuật toán Gale – Shapley, cần tổ chức việc ghép đôi này thành nhiều vòng. Ở vòng một, mỗi chàng trai sẽ cầu hôn một cô gái mà anh ta thích nhất. Nếu cô nào có nhiều chàng cầu hôn sẽ phải thải loại gần hết và chỉ giữ lại một chàng mà cô ấy thích nhất (trong số các chàng cầu hôn với cô ấy). Chưa cô nào được phép cưới ngay, mà chỉ được ghi tên chàng trai đó vào danh sách dự bị.

Ở vòng hai, các chàng trai không được bất cứ cô gái nào đưa vào danh sách dự bị ở vòng 1 sẽ cầu hôn với cô gái mà anh ta thích thứ nhì. Các cô gái sẽ chọn trong số các chàng trai cầu hôn với mình ở vòng 2 và chàng trai mà cô ta đưa vào danh sách dự bị ở vòng một ra một chàng trai ưng ý nhất và ghi tên anh ta vào danh sách dự bị.

Vòng lặp này sẽ kết thúc khi cho đến khi tất cả các cô gái đều được cầu hôn. Khi đó, coi như quá trình tán tỉnh lẫn nhau kết thúc, và các cô gái buộc phải cưới chàng trai duy nhất trong danh sách dự bị của mình.

Dễ thấy là nếu làm đúng theo thuật toán này, kết quả của quá trình ghép đôi sẽ là một kết quả ổn định. Không khó để chứng minh. Hãy giả sử ngược lại là nếu có chàng John và nàng Mary không được cưới nhau nhưng John lại thích Mary hơn vợ của anh ấy. Nếu như thế, tên của Mary sẽ đứng trước tên của vợ John trong danh sách của chàng. Và như vậy John hẳn đã phải cầu hôn Mary ở một vòng lặp trước theo đúng thuật toán Gale-Shapley. Mà như thế, Mary hẳn đã loại thẳng cổ John khi cô chọn người vào danh sách dự bị của mình.

Vì người trong danh sách dự bị của Mary chỉ có thể ngày càng tốt hơn khi các vòng lặp được triển khai, chắc chắn Mary phải thích chồng của cô ấy hơn John. Điều đó có nghĩa là sẽ không có một John và một Mary nào mà cả hai cùng thích đến với nhau hơn là với người bạn đời mà vòng lặp Gale-Shapley gán cho họ. Nói cách khác, kết quả của thuật toán này là một kết quả gán ghép ổn định.

Thuật toán này cũng áp dụng hoàn hảo cho trường hợp tuyển sinh đại học, mặc dù lập luận áp dụng cho bài toán tuyển sinh phức tạp hơn đôi chút. Bạn đọc ham tìm hiểu có thể tự mày mò theo thuật toán Gale – Shapley để tìm ra.

Shapley và Gale đưa ra một thuật toán mà sau này trở nên nổi tiếng với tên gọi thuật toán Gale - Shapley. Hai ông chứng minh được rằng nếu triển khai theo thuật toán này thì mọi bài toán ghép đôi giống như các bài nêu trên sẽ luôn có lời giải là một kết quả ghép đôi ổn định và tốt nhất. Nét đẹp của thuật toán này là nó rất đơn giản và tạo ra một kết quả phi thường: thử tưởng tượng một xã hội mà tất cả mọi người đều tìm được người thích hợp nhất với mình, và không ai phải lựa chọn lại lần thứ hai.

...Đến sự ra đời của một ngành nghiên cứu mới

Từ việc sáng tạo ra một thuật toán khá đơn giản để giải một vấn đề khá phức tạp liên quan đến việc gán ghép trong vấn đề kết hôn và vấn đề tuyển sinh đại học, Gale và Shapley đã đặt viên gạch đầu tiên cho một ngành nghiên cứu mới là lý thuyết gán ghép (matching theory) trong kinh tế học. Lý thuyết này hiện nay được ứng dụng rộng rãi trong các ngành nghiên cứu khác của kinh tế học, từ vi mô (như lý thuyết về đấu thầu - auction theory) tới vĩ mô (như lý thuyết về tiền tệ - monetary theory), và là một cột trụ của lý thuyết trò chơi hợp tác (cooperative game theory).

Một trong những người tiên phong, và dũng cảm nhất, trong việc phát triển lý thuyết của Gale - Shapley là Alvin Roth, nhà kinh tế học của Trường đại học Harvard. Là một giáo sư cực kỳ uyên bác, Roth có bề ngoài nhìn rất mọt sách (nerdy), khi đó ông đang phát triển các nghiên cứu kinh tế học thí nghiệm - tức là mô phỏng các tương tác kinh tế trong môi trường có kiểm soát. Ông cùng một số giáo sư khác như giáo sư Dale Stalh tổ chức các trò chơi kinh tế nho nhỏ và có thưởng (vài chục đôla) để sinh viên tham gia.

Các ông sau đó thu thập và phân tích kết quả của các trò chơi này và mô hình hóa các tương tác giữa những người chơi với nhau dựa trên quan sát thực tế. Đây là một hướng nghiên cứu còn mới hơn nữa so với lý thuyết gán ghép.

Alvin Roth được nhận giải Nobel vì các công trình liên quan đến việc “thiết kế thị trường”. Lưu ý là thuật toán Dale - Shapley bản chất cũng là việc thiết kế một luật chơi cho một dạng thị trường, tuy nhiên, trong ví dụ về gán ghép áp dụng cho thị trường hôn nhân ở trên, khả năng áp dụng trên thực tế của nó hầu như không có mà chỉ có vẻ đẹp thuần túy về mặt lý thuyết. Alvin đi xa hơn bằng việc sáng tạo ra các luật chơi áp dụng được, và đã áp dụng trong thực tế. Nói cách khác, ông thiết kế ra các thị trường mà nếu không có các phát minh của ông thì đã không tồn tại hoặc tồn tại dưới một dạng rất không hiệu quả.

Trường hợp đầu tiên của Alvin Roth là thiết kế ra cơ chế giúp cho Chương trình quốc gia về phân bổ bác sĩ nội trú (NRMP) của Hoa Kỳ. Ở Mỹ, các bác sĩ sau khi tốt nghiệp trường y phải thực tập tại các bệnh viện và phòng khám nhiều năm trước khi hành nghề chính thức. Tuy nhiên, do tình trạng thiếu bác sĩ nghiêm trọng ở Mỹ trong nhiều năm, NRMP ra đời nhằm giúp các bệnh viện và phòng khám tìm các bác sĩ thực tập và tuyển dụng họ nhiều năm trước khi họ thật sự tốt nghiệp trường y.

Vấn đề mà NRMP gặp phải là các bác sĩ tương lai này nhiều khi chưa xác định được chuyên môn của họ cũng như nơi làm việc thích hợp nhất cho mình. Vì thế, các bác sĩ tương lai luôn có xu hướng câu giờ và nhiều khi muốn “khai bậy” mong muốn thật sự của họ để nhận được càng nhiều mời chào thực tập ở các cơ sở y tế càng tốt.

Kết quả là cùng với một số biến động khác trên thị trường y tế của Mỹ, NRMP gặp khủng hoảng nặng vào giữa những năm 1990. Alvin Roth và Elliott Peranson được mời thiết kế một cơ chế mới cho chương trình này vào năm 1995 và vào năm 1997 thì NRMP chính thức áp dụng cơ chế mới do hai ông phát minh. Từ đó tới nay, NRMP đã hoạt động thông suốt và mỗi năm giúp “gán ghép” được hơn 20.000 bác sĩ tập sự với các cơ sở y tế.

Trường hợp thứ hai là hệ thống trường công lập ở New York. Trước đây, các trường trung học của thành phố này tuyển đầu vào bằng cách yêu cầu thí sinh đăng ký năm nguyện vọng theo thứ tự. Các trường sẽ xét tuyển, và những thí sinh trượt vòng 1 được thêm hai vòng nữa để được tuyển theo nguyện vọng. Kết thúc ba vòng tuyển theo nguyện vọng thì Sở Giáo dục New York sẽ quyết định xếp trường cho thí sinh không cần theo nguyện vọng. Kết quả của cơ chế này là mỗi năm có tới 30.000 học sinh của thành phố này không được học theo nguyện vọng.

Alvin Roth đã thiết kế một cơ chế mới, dựa trên một phiên bản của thuật toán Dale - Shapley cho thành phố. New York đã áp dụng cơ chế mới này vào năm 2003 và từ đó số lượng học viên bị xếp vào trường trái nguyện vọng giảm xuống chỉ còn 10% so với số cũ. Sự thành công của New York đã khiến hàng loạt các thành phố khác ở khắp nơi trên nước Mỹ áp dụng theo.

Ủy ban Nobel cho rằng Lloyd Shapley và Alvin Roth đã làm việc độc lập với nhau, nhưng sự thành công trong nghiên cứu của họ là do sự kết hợp giữa các kết quả lý thuyết của Shapley với sự tinh tế của Roth khi đưa các kết quả lý thuyết này thành các áp dụng thực tiễn trong việc thiết kế thị trường. Lĩnh vực này còn tiếp tục phát triển và đang có nhiều hứa hẹn to lớn trong tương lai.