Thứ Tư, 22/10/2014
Xem

Blog / Trần Vinh Dự

Giải Nobel Kinh tế 2012 xuất phát từ một thuật toán đơn giản

Hai nhà kinh tế học người Mỹ Alvin Roth và Lloyd Shapley
Hai nhà kinh tế học người Mỹ Alvin Roth và Lloyd Shapley
Giải Nobel kinh tế năm nay được trao cho hai nhà kinh tế nghiên cứu về một lĩnh vực khá lạ lẫm, nhưng không vì thế mà không thú vị. Lloyd S. Shapley và Alvin E. Roth  giải vì các nghiên cứu của hai ông trong lĩnh vực lý thuyết “ghép đôi” và các phát minh về thiết kế thị trường có khả năng ứng dụng rộng rãi trên khắp thế giới.

Vào năm 1962, khi Shapley mới 39 tuổi và đang là một nhà toán học làm ở Rand Corp, một think-tank đầy quyền lực của Hoa Kỳ, nơi chuyên nghiên cứu các dự án hạng nặng cho Bộ Quốc phòng của nước này, ông và một nhà kinh tế khác thuộc Đại học Brown là D. Gale đăng một công trình nghiên cứu có tên “tuyển sinh đại học và sự ổn định của hôn nhân” trên một tạp chí hạng thường của giới nghiên cứu toán học mang tên American Mathematical Monthly.

Tạp chí American Mathematical Monthly là một tạp chí hướng vào đại chúng, với cách viết đơn giản không cầu kỳ, không quá kỹ thuật, và thường không dùng để đăng tải những công trình nghiên cứu hạng nặng. Khi đăng công trình nghiên cứu này, Shapley chắc chắn dù nằm mơ cũng không tưởng tượng ra vào một ngày đẹp trời của 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

Quay trở lại năm 1962, 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ư việc 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 nghìn sinh viên đầu vào, và có 10 trường đại học, mỗi trường tuyển một nghìn sinh viên. Câu 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 và 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 nghìn 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 sẽ có nhiều sinh viên chúng tuyển sẽ không tham gia vào học ở trường đó vì họ được nhận vào các trường khác mà họ thích hơn?

Tương tự như vậy, trong vấn đề hôn nhân, giả sử đơn giản là 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 anh ta có những người phụ nữ mà anh ta muốn “ghép đôi”. Tương tự như vậy, mỗi phụ nữ cũng có những người đà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 có 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  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. 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.(còn tiếp)

* Blog của Tiến sĩ Trần Vinh Dự là blog cá nhân. Các bài viết trên blog được đăng tải với sự đồng ý của Ðài VOA nhưng không phản ánh quan điểm hay lập trường của Chính phủ Hoa Kỳ.

Trần Vinh Dự

Trần Vinh Dự chuyên nghiên cứu, tư vấn, và viết về các vấn đề kinh tế của Việt Nam, Hoa Kỳ và thế giới. Ngoài lĩnh vực sở trường này, ông cũng thường xuyên viết về các vấn đề quan hệ quốc tế liên quan tới Á Châu. Trần Vinh Dự tốt nghiệp tiến sĩ kinh tế tại Đại học tổng hợp Texas ở Austin, làm chuyên gia tư vấn kinh tế cho tập đoàn ERS Group Inc., đồng sáng lập và là cố vấn cho Quỹ nghiên cứu Biển Đông.
Diễn đàn này đã đóng.
Trình bày ý kiến
Ý kiến
     
bởi: Bình Hòa
30.10.2012 10:58
Đỉnh cao của nhận thức và trình bày là sự đơn giản. Thuật toán "ghép đôi"ở thương mại gọi là thuận mua vừa bán; nghĩa là biết tương nhượng nhau thì chuyện gì cũng xong. Ở chỗ khác gọi là"uốn nắn" tức là làm cho hợp nhau, ơm nhau, chằm lấy nhau hay gọi "già giặn đi hơn", chuẩn hơn. Giữa Cộng Sản và Tư Bản khi đà già giặn đi hơn sẽ chung sống hòa bình mà chẳng còn tranh chấp nhau nữa. Đặt biệt phần "ghép đôi" này ai là người dùng đúng thuật toán? Vâng, trái đất rất xưa mà !

bởi: Thaile từ: Outspace
29.10.2012 16:32
Matching :Một từ thường gặp trong các bài tóan đơn giản khi chọn đáp án phù hợp nhất cho một vấn đề đặt ra Nhưng về mặt ứng dụng tóan học của Gale-Shapley vào các lãnh vực kinh tế xã hội thật là tuyệt vời nhất là thời đại của công nghệ thông tin Cám ơn TS đã bình dị hóa thuật Matching giúp cho mọi người dễ hiểu những suy tư cao siêu của những nhà Tóan Học

bởi: tricodon100 từ: Vietnam
28.10.2012 11:08
thuật toán của Lloyd S. Shapley và Alvin E. Roth nó rất tuyệt vời cho bản thân tôi, nhưng với những người thường thay đổi suy nghỉ về sự lựa chọn thì chỉ có luật đoán mới có thể biết được họ. Hy vọng vài năm nữa thế giới sẽ phát hiện và tặng giải Nobel cho những người này.

bởi: Tuấn Tô từ: Nữu Ước
25.10.2012 13:28
Nhờ bài viết của TS Dự, chúng ta có dịp động não và học hỏi thêm về thuật toán ít được biết đến này. Các ngài Roth và Shapley chỉ dùng ví dụ hôn nhân để diễn giải trình tự của thuật toán thêm rõ ràng. Thuật toán này nay đã được áp dụng tại Hoa Kỳ để giúp tối đa số người cần thay thận mà chỉ cần tối thiểu số người có thể hiến thận. Rất hay, TS Dự!

bởi: Nguyễn từ: Việt Nam
25.10.2012 06:43
Matching mà dịch "sính đôi" thì hay hơn "ghép đôi", ghép có khi có bắt buộc nhưng sính thì tự nguyện hơn. Tác giả giải thích kết quả việc lãnh giải Nobel thật gọn ghẻ, đơn giản, chứng tỏ có hiểu biết rất sâu về kinh tế khiến những người bình thường như chúng tôi cũng có thể hiểu dễ dàng những vấn đề phức tạp. Tiếc những người như vậy mà lại chỉ để viết blog cho chúng tôi đọc và ngưỡng mộ mà không phải là trợ lý cho thủ tướng bảnh trai và gan lỳ của chúng tôi!

bởi: Lê Thành từ: San Jose, California,USA
24.10.2012 18:36
Tôi thích cô A và cô A cũng thích tôi. Chúng tôi lấy nhau vài năm thì xung khắc và thấy rằng không thích hợp. Tôi hối hận và nghĩ rằng nếu cho tôi làm lại từ đầu, tôi sẽ xin cưới cô B. Còn A (vợ tôi) thì nói hồi xưa vì tôi ngu nên mới lấy ông...Cám ơn bài viết lý thú của Tiến Sĩ Trần Vinh Dự, nhưng theo tôi nếu áp dụng vào toán học hay kinh tế học thì được, còn trong chuyện tình cảm và hôn nhân thì sẽ rắc rối hơn nhiều. Lê Thành.
Trả lời

bởi: Nguyễn Xuân Triều từ: Australia
25.10.2012 00:23
Bài viết của Trần Vinh Dự rất hay, thú vị và có khả năng tạo ra nhiều bàn cãi cần thiết và tích cực. Rất cám ơn anh!

Dưới đây tôi chỉ xin có vài ý kiến riêng về việc ổn định trong hôn nhân một chút cho vui:

Tôi đồng ý với anh Lê Thành về việc áp dụng thuật toán đơn giản Gale-Shapley để giải quyết bài toán tâm sinh lý và xã hội nhân văn phức tạp là việc kết hợp ổn định giữa 2 cá thể nam-nữ để cùng sống còn và hơn nữa, duy trì nòi giống.

Thuật toán trên rõ ràng đã không tính toán đến ít nhất ba điều quan trọng:

1. Sự biến đổi cả thị hiếu tâm lý lẫn thể xác theo thời gian. Chính vì điều này mà anh Lê Thành sau này mới... xin cưới cô B đó :)

2. Về mặt sinh học, nam nữ hấp dẫn nhau và gắn bó thể xác được với nhau là tùy vào họ có những sex pheromones thích hợp với nhau (một loại hoá chất tương tự như mùi rất nhẹ của cơ thể tiết ra. Sex pheromones có thể khác nhau tùy theo người).

Nếu không tương hợp về sex pheromones, sự kết hợp (matching) đó sẽ không ổn định về mặt sinh học (nghĩa là khả năng hai người bị hấp dẫn bởi người khác phái thích hợp hơn sẽ rất lớn).

Chính vì điều này mà chúng ta thường quan sát được trong đời sống những cặp nam nữ rất tốt, rất quý trọng và nể phục nhau nhưng không hề có hạnh phúc nếu họ lấy nhau...và ngược lại, có những cặp nam nữ nhìn thấy chẳng có gì 'xứng đôi' hay chẳng hề tôn trọng nhau chút nào mà họ lại rất hạnh phúc khi là vợ chồng.

Điều này ít người bàn đến, vì nó có vẻ như 'làm gì mà lúc nào cũng nghĩ đến sex vậy?' :)

3. Những ổn định trong hôn nhân biểu kiến (nghĩa là chỉ ở mặt hình thức thôi - apparently stable marriage) mà chúng ta hay thấy ở thế hệ cha mẹ ông bà mình (khi bị ép gả), thật ra là đã bị kềm hãm bởi vô vàn vòng rào luân lý và sức ép xã hội lẫn tôn giáo khiến chúng không 'đổ bể' được, tuy vậy bản thân mỗi cá thể trong sự kết hợp gượng gạo đó đã bị biến đổi rồi.

Tôi nghĩ rằng, giải pháp cho việc thật sự có những ổn định trong hôn nhân là áp dụng thuật toán Gale-Shapley một cách thực hành:

Mỗi vòng lặp mà anh Trần Vinh Dự nói trên đây nên là một thời kỳ sống thử với nhau khoảng 3 -6 tháng, chứ không phải chỉ nhìn bề ngoài rồi quyết định mình thích ai nhất (vì sẽ có quá nhiều sai số trong chọn lựa kiểu này).

Chúng ta có thể mất thêm một vài năm để lựa chọn, nhưng chúng ta sẽ ít phải ân hận vì đã vô tình làm khổ cả hai người mà cứ tưởng mình đang mang lại hạnh phúc cho nhau!

Cuối cùng, nếu có ai đó cho rằng vì tôi là nam giới nên ngụy biện theo cách...có lợi về mặt sex thì có lẽ sẽ không đúng lắm với thực tế đâu, bởi vì nhu cầu thoả mãn tính dục của hai phái là ngang bằng nhau về cường độ. Phái nữ chỉ bị 'điều kiện hoá' để không bày tỏ công khai như phái nam được mà thôi.

Blog

Tại sao lại đi đêm?

Cuộc gặp bí mật giữa 2 đoàn đại biểu đảng CSVN và TQ ở Thành Đô tháng 9, 1990 đang là đề tài nóng ở trong nước
Thêm

Dân chủ hoá: Một tiến trình đầy nhọc nhằn

Ở vào thời điểm hiện nay, các học giả cũng ghi nhận nhân loại đang ở giữa cuộc thoái trào của dân chủ
Thêm

Nobel kinh tế 2014 và vấn đề quản lý thị trường

Tại sao EVN liên tục kêu lỗ dù người tiêu dùng luôn cho rằng giá điện ở VN đắt đỏ? Tại sao giá xăng giảm ít tăng nhiều?
Thêm

Người ‘đẹp’ nhất trong Đèn Cù

Cuốn Đèn Cù của Trần Đĩnh đang được phổ biến ngày càng rộng trong và ngoài nước. Với tôi cuốn sách giúp nhớ lại biết bao cảnh cũ người xưa
Thêm
Các bài viết khác

Bạn đọc làm báo

‘Đảng ta’ đã ‘giải phóng con người’ như thế nào?

Các phương tiện truyền thông trong tay Đảng vẫn tuyên truyền, kêu gọi nhân dân nêu cao tinh thần 'cảnh giác cách mạng' trước các 'thế lực thù địch'
Thêm

Thư ngỏ về việc chính quyền VN 'vi phạm quyền tự do đi lại của công dân'

Vào ngày 17/10/2014, tôi bị một số nhân viên an ninh thuộc Công an TP HCM ngăn chặn bất hợp pháp
Thêm

Đối sách của TQ với các cuộc biểu tình ở Hồng Kông

Đối sách của Bắc Kinh với các cuộc biểu tình của tuổi trẻ Hồng Kông có thể tạm gọi là 'câu giờ, mềm nắn, rắn buông để hạ nhiệt, triệt đầu não'
Thêm

Thử ngược dòng TPP

Đến nay Chính phủ Mỹ vẫn chưa thực hiện được bước tiến nào cho thấy vòng đàm phán TPP sẽ kết thúc trước cuối năm 2014
Thêm

Thưa Thầy Lần Cuối

Với độc giả, Thầy là Nhà Văn Nguyễn Xuân Hoàng. Với riêng em, Thầy là thầy dạy văn chương
Thêm
Các bài viết khác
JavaScript của bạn đang tắt hoặc bạn có phiên bản Flash Player cũ của Adobe. Hãy trang bị Flash player mới nhất.
Điếu Cày tới Mỹ - Phỏng vấn nhà báo độc lập Phạm Chí Dũngi
X
22.10.2014
Tin tức: http://www.facebook.com/VOATiengViet, http://www.youtube.com/VOATiengVietVideo, http://www.voatiengviet.com. Nếu không vào được VOA, xin các bạn hãy vào http://vn3000.com để vượt tường lửa. Sau khi blogger Điếu Cày được Hà Nội trả tự do và tức tốc tống xuất ra khỏi Việt Nam, Ban Việt ngữ - VOA đã tiếp xúc với các nhà báo độc lập ở trong nước để tìm hiểu phản ứng của giới tranh đấu cho dân chủ ở nước nhà. Trong một cuộc phỏng vấn dành cho Ban Việt ngữ-VOA, Chủ tịch Hội Nhà báo Độc lập Việt Nam, Tiến sĩ Phạm Chí Dũng cho rằng việc Điếu Cày được thả khỏi nhà tù là một tin vui, không những cho ông, mà còn cho Phong trào Dân chủ nói chung.
Video

Video Điếu Cày tới Mỹ - Phỏng vấn nhà báo độc lập Phạm Chí Dũng

Chủ tịch Hội Nhà báo Độc lập Việt Nam, Tiến sĩ Phạm Chí Dũng cho rằng việc Điếu Cày được thả khỏi nhà tù là một tin vui, không những cho ông, mà còn cho Phong trào Dân chủ nói chung
Video

Video Trợ Lý Ngoại trưởng Mỹ Tom Malinowski đến Việt Nam

Tại Việt Nam, Trợ Lý Ngoại trưởng Hoa Kỳ đặc trách Dân chủ, Nhân quyền và Lao động Tom Malinowski sẽ thảo luận với các quan chức Việt Nam và các đại diện xã hội dân sự
Video

Video Mỹ hoan nghênh việc trả tự do cho blogger Điếu Cày

Chính phủ Hoa Kỳ hoan nghênh việc Hà Nội trả tự do cho blogger Điếu Cày, tức Nguyễn Văn Hải, người sáng lập Câu Lạc Bộ Nhà báo Tự Do, tù nhân lương tâm Việt Nam được thế giới biết tiếng
Video

Video Đàm phán giữa chính quyền, người biểu tình Hồng Kông bế tắc

Một cuộc họp kéo dài hai giờ tại Hồng Kông giữa những người ủng hộ cải cách chính trị và giới chức chính quyền đã kết thúc mà không có tiến bộ nào, khiến học sinh sinh viên biểu tình băn khoăn liệu họ có nên tiếp tục đàm phán hay không
Video

Video Bắc Triều Tiên phóng thích một công dân Mỹ

Bắc Triều Tiên cho hay một người Mỹ bị họ bắt giữ đã được trả tự do sau 'những yêu cầu liên tục' của Tổng thống Hoa Kỳ Barack Obama