Lớp A0 – Khóa 9

They came, they saw and they ….

TOÁN HỌC và GIẢI NOBEL KINH TẾ 2012


Lời dẫn: Sau một thời gian im hơi, lặng tiếng, Việt Dũng đã quyết định “tái xuất giang hồ” trên Blog với bài giới thiệu về  một thuật toán “tối ưu hóa” cái  công việc rất chi là may rủi là hôn nhân và gia đình!  BBT trân trọng đăng lại toàn văn và mới các bạn cùng “xúm vào giúp Dũng”  đặng “chữa lợn lành thành lợn què luôn”! 

Tư liệu nguồn:

http://www.businessinsider.com/this-is-the-math-that-won-two-people-the-nobel-prize-for-economics-2012-10

Alvin Roth, giáo sư danh dự của đại học UCLA, và Lloyd Shapley, giáo sư của đại học Havard vừa cùng nhau nhận giải Nobel kinh tế 2012. Hai ông đã có những ảnh hưởng to lớn trong lý thuyết cũng như trong những ứng dụng thực tiễn mang tính kinh tế trong đời sống thực, đã cứu sinh mạng hàng ngàn người.

 Lloyd Shapley được trao giải trên hết là nhờ công trình của ông về lý thuyết hẹn hò và cưới xin. Ông quan tâm đến bài toán hôn nhân ổn định, có thể phát biểu như sau:

 Giả sử tỷ lệ giữa nam và nữ trong dân số một vùng nào đó là như nhau. Mỗi người đều hẹn hò với một một người nào đó và đều muốn cưới một bạn tình lý tưởng. Mỗi người sẽ xếp tất cả những người khác giới theo một thứ tự ưu tiên của riêng mình. Mục tiêu của bài toán là đưa ra một cách dàn xếp các cuộc hôn nhân ổn định cho tất cả mọi người. Ta coi là tìm được lời giải cho bài toán này nếu mỗi người đều chọn được một người để kết hôn và không có hai người khác giới nào lại thích nhau hơn (theo thứ tự riêng của họ) người chồng/vợ của họ. Chẳng hạn nếu theo một cách sắp xếp hôn nhân, anh Hùng lấy chị Lan, anh Cường lấy chị Ngọc, trong khi theo thứ tự ưu tiên của mình, anh Cường và chị Lan muốn cưới nhau hơn là cưới người vợ/chồng hiện tại, thì hai cuộc hôn nhân đó là không ổn định.

 Lloyd Shapley cùng với David Gale đã đưa ra một thuật toán giải quyết vấn đề này vào năm 1962. Đây là thuật toán lặp, tức là phải được thực hiện nhiều lần trước khi nhận được lời giải. Kết quả của thuật toán là tất cả mọi người đều được kết hôn và mọi cuộc hôn nhân đều ổn định.

Thuật toán này được mô tả như sau:

  1. Bắt đầu, theo thuật toán mỗi chàng trai sẽ ngỏ lời với cô gái có thứ hạng cao nhất trong danh sách ưu tiên của anh ta (mà anh chưa từng ngỏ lời).
  2. Nếu cô gái vẫn còn tự do, hai người họ sẽ hứa hôn với nhau.  Nếu cô gái không còn tự do, thuật toán sẽ kiểm tra xem cô có thích người yêu hiện tại của cô hơn chàng trai mới theo đuổi cô hay không.
  3. Nếu cô thích chàng trai mới hơn, anh người yêu hiên tại của cô sẽ lại trở về trạng thái độc thân và cô sẽ hứa hôn với chàng trai mới đến.
  4. Nếu cô vẫn thích người yêu hiện tại của mình hơn người mới đến, họ vẫn tiếp tục hứa hôn với nhau và chàng trai mới đến phải hạ tiêu chuẩn, ngỏ lời với cô gái có thứ hạng tiếp theo trong danh sách của anh ta.

 Quá trình này lặp lại với mọi chàng trai và cuối cùng mọi người đều hứa hôn và mọi cặp hứa hôn đều ổn định.

Cần nhớ là kết quả đạt được của thuật toán là tính ổn định chứ không phải sự hoàn hảo.

 Tuy việc “tráo vợ” trong thuật toán của Shapley và Gale nghe có vẻ nhẫn tâm, lời giải cho thuật toán của họ đã được Roth mở rộng và ứng dụng trong việc sắp xếp người hiến tặng-người nhận trong việc ghép thận[1], sắp xếp học sinh vào các trường cho các trường trung học của thành phố New York[2] và việc sắp xếp các sinh viên nội trú năm đầu của ngành Y vào các bệnh viện muốn nhận họ[3].

 Vì những đóng góp này, hai nhà khoa học đã được nhận giải Nobel.

 Công trình của Shapley về bài toán matching trong lý thuyết trò chơi và công trình của Roth về việc sử dụng lý thuyết này vào đời sống là một ví dụ hoàn hảo của kinh tế học thực tiễn.


[1] Hàng năm ở Mỹ có 60.000 người cần ghép thận, nhưng chỉ có 15.000 người được ghép từ thận của người chết hoặc của người hiến tặng. Để giúp những người kém may mắn còn lại, Roth và các cộng sự đã phát triển lý thuyết matching, xây dựng một hệ thống với cơ sở dữ liệu khổng lồ nhằm tối ưu hóa quá trình tìm kiếm người hiến thận sống – bệnh nhân, qua đó cứu được sinh mạng cho hàng ngàn người. Xem thêm

http://www.nsf.gov/discoveries/disc_summ.jsp?cntn_id=104404&org=NSF

[2] Roth và cộng sự đã đưa ra một cơ chế sắp xếp học sinh vào các trường trung học ở tp New York, dựa trên thuật toán matching ổn định, qua đó giúp thành phố chưa cần tăng số trường học cũng vẫn nhận được nhiều học sinh hơn. Xem thêm

http://kuznets.fas.harvard.edu/~aroth/papers/nycAEAPP.pdf

[3] Matching design của Roth và các cộng sự đã giúp phân bổ 20.000 chỗ làm việc trong các bệnh viện trên toàn nước Mỹ cho các sinh viên nội trú năm đầu ngành Y. Các ví dụ tính toán bằng số cho thấy mô hình của Roth là thực sự hiệu quả. Xem thêm

http://www.bepress.com/cgi/viewcontent.cgi?article=1016&context=wilson

Tháng Mười 24, 2012 - Posted by | Tổng hợp

16 phản hồi »

  1. Tôi cũng có đọc về Giải Nobel kinh tế 2012 và công trình của 2 ông này song chưa được tường tận như bài viết này giới thiệu. Bài viết bổ ích quá !
    1. Về lý thuyết hôn nhân của Lloyd Shapley : theo dân gian Việt Nam thì các cụ đã có câu ” vợ chồng là duyên số” rồi : “cái duyên cái số nó vồ lấy nhau”, v.v… Không biết lý thuyết ” duyên số’ của các cụ nhà ta và lý thuyết của Lloyd Shapley cái nào hơn cái nào ???
    2. Về “lợn lành , lợn què” trong lời dẫn của bài này làm tôi nhớ tới câu chuyện Tái Ông ngã ngựa nên có khi “què ” lại hơn “lành” không biết chừng !

    Phản hồi bởi phuongnguyentm | Tháng Mười 24, 2012 | Trả lời

  2. Chào V. Dũng và tất cả các bạn! Lâu lắm rồi Blog mới lại có bài viết hấp dẫn đến thế. Về “lợn lành và lợn què” thì tớ nghĩ thế này:
    1. Các tác giả nhận giải Nobel kinh tế đã đưa ra được thuật toán giúp xã hội chữa “lợn què thành lợn lành” đấy ạ, hoặc chính xác hơn là chữa “lợn què nặng thành lợn què nhẹ hơn”. Vì thế mà xã hội “ổn định” hơn. Không biết có phải như vậy không?
    2. Hơn nữa, trước khi có thuật toán đó thì nhiều người trong dân gian ta từ xưa đến nay vẫn tự đi tìm cách để chữa “lợn què thành lợn lành” đấy ạ. Cũng không biết có phải như vậy không?

    Phản hồi bởi Đỗ Thiên Kính | Tháng Mười 25, 2012 | Trả lời

  3. Nếu mình không nhầm thì hôm nay là sinh nhật bạn Hùng Thao lớp mình. Thay mặt cho tất cả các zai và gái A0khoa9 xin chúc bạn Thao của chúng ta luôn trẻ mãi không già, luôn thành công hạnh phúc trong cuộc sống và luôn có cá chỉ vàng để chiêu đãi bọn mình.

    Phản hồi bởi nguyenvietdung | Tháng Mười 25, 2012 | Trả lời

    • Chào cả nhà! Lâu lắm, trên Blog mới có bài viết mới, mặc dù hàng ngày vẫn có 40-50 lần truy cập! Trước hết, cám ơn V.Dũng và các bạn vẫn trung thành mà âm thầm với Blog!
      @V.Dũng: Trong bài giới thiệu thuật toán trên, tớ thấy có sự “bất đối xứng” trong quan hệ: chỉ có hội đàn ông (the men) mới có quyền “đề xuất” còn các chị em chỉ có quyền “gật hay lắc” thôi! Vậy thì vấn đề “Bình đẳng giới tính” e rằng chưa dc giải quyết?
      @ M.Phương: Chào M.Phương! Theo tôi, khái niệm “lợn lành, lợn què” ở đây hoàn toàn mang tính cảm nhận chủ quan. Đại khái là, như các cụ nói, “văn mình, vợ người”, hoặc diễn nôm ra thì “lợn nhà mình” có vẻ “què” hơn của nhà hàng xóm! Vậy nên trong “dân gian mạng” mới có câu:
      Vợ mình “cơm nguội”-nhà ta
      Lại là “phở tái”-thằng cha láng giềng!😀 😀😀

      Phản hồi bởi V. Thành | Tháng Mười 25, 2012 | Trả lời

      • TBT không thấy là bài báo đó có từ ngày 15/10 mà mình phải đợi đến sau ngày 20/10 mới gửi à. Để tránh làm nặng thêm cái “bất đối xứng” ấy đấy.

        Phản hồi bởi nguyenvietdung | Tháng Mười 26, 2012

      • Chào Văn Thành,
        Văn Thành viết bao giờ cũng rất vui !
        1. Cám ơn Văn Thành luôn chú ý đến quyền lợi của các chị em và v/d bình đẳng giới. Ý của Văn Thành rất hay : lý thuyêt của 2 ông được Giải Nobel kinh tế 2012 chưa hoàn thiện vì lý do như Văn Thành đã nêu trên. Đó là cơ hội vô cùng tốt cho bạn phát triển thêm lý thuyết này với việc thêm vào các giả thiết về bình đẳng giới , ví dụ chị A lấy anh B, chị E lấy anh F (tức là lúc này phái đẹp chủ động trước)…, v.v… cứ thế phát triển lên. Tôi chắc là sẽ có rất nhiều kết luận thú vị, bất ngờ, có khi thay đổi cả thế giới ! Sau đó thì Văn Thành gửi đến Uỷ ban xét Giải Nobel để yêu cầu họ chia Giải 2012 cho 3 người chứ không phải 2 như hiện nay, bọn tôi sẽ ủng hộ hết mình ! Biết đâu đây lại là Giải Nobel mới cho Việt Nam (sau cái Giải Nobel Hoà Binh 1973 cho ông Lê Đức Thọ và Kissinger) ?
        2. Quay lại với v/d bình đảng giới thì các cụ nhà ta lại tiến bộ hơn 2 ông kia hàng mấy trăm năm rồi : mọi người chắc thuộc lòng Truyện Kiều đều nhớ Cụ Nguyễn Du đã cho cô Kiều xinh đẹp đêm trăng một mình xé rào phăng phăng sang nhà anh Kim Trọng trước ! Thế nên tôi vẫn ủng hộ lý thuyết “duyên số” của các cụ nhà ta hơn.
        3. Vê “lành” và “què” thì lại thuyết minh thế này vậy : “què” nhà mình vẫn ăn đứt “lành” nhà người ! Chả thế mà các cụ bà xưa nay đã có câu ” Chồng em đói rách em thương, chồng người đội gấm xông hương mặc người ” !?

        Phản hồi bởi phuongnguyentm | Tháng Mười 26, 2012

      • Hi M.Phương,
        1.Viễn cảnh được “chia giải Nobel” thật là hấp dẫn!
        Nếu vậy, tại sao ta không làm cho “tới bến” ? Thế này nhé: Khái niệm “bình đẳng giới tính” trong thời hiện đại phải được thể hiện đối với mọi giới tính của nhân loại đang tồn tại một cách khách quan! Như vậy, ngoài 2 giới quá phổ biến (Nam và Nữ), ta phải xét đến các trường hợp “chuyển đổi giới tính” từ Nam->Nữ và từ Nữ->Nam! Nếu ta giải dc “bài toán tổng quát” của cả 4 “giới tính” nêu trên, thì giải Nobel kia phải chia thành 4 phần, 2 cụ Roth và Shapley chỉ được 1 phần thôi!😀😀😀
        2. Riêng trường hợp của cô Kiều tôi có đánh giá hơi khác M.Phương! Tôi thấy, cụ Tiên Điền rất “thâm thúy”, lúc đầu cho cô Thúy Kiều “phăng phăng xé rào” rất hoành tráng để rồi phải trả giá bằng 15 năm lưu lạc… Cho nên đến các đời sau, tuy ai ai cũng thương cảm thân phận nàng Kiều nhưng nhất nhất chưa có ai kêu gọi “sống và học tập” theo “tấm gương” ấy cả!😀😀😀

        Phản hồi bởi V. Thành | Tháng Mười 28, 2012

  4. 1. Xin đính chính lại câu ca dao trong phần phản hồi của tôi là : ” Chồng em áo rách em thương ( tương ứng với “què”, Chồng người đội gấm xông hương mặc người” (tương ứng với “lành”)),
    2. Về câu chuyện “tổng quát hoá” để được chia Giải Nobel Kinh tế 2012 có lẽ ta cần thêm cả v/đ “đồng tính” cho đầy đủ nhỉ ???
    3. Về câu chuyện tôi dẫn đến cô Kiều ở trên thì tôi không cho rằng Kiều phải trải qua “15 năm lưu lạc” với “trăm cuộc bể dâu” không phải là sự trả giá cho việc “phăng phăng xé rào”. Đơn giản là Cụ Nguyễn Du rất yêu chị em, rất thấu hiểu nên từ thời xa xưa ấy đã để Kiều “được sống, được yêu” hết mình.

    Phản hồi bởi phuongnguyentm | Tháng Mười 28, 2012 | Trả lời

    • Hi M.P
      1. Tôi hiểu là câu ca dao này có rất nhiều phiên bản khác nhau. Tuy vậy, “phương án” của M.Phương có hành vi “đội gấm” nghe có vẻ hơi lạ? Thôi thì cứ cho ông chồng nhà người ta mặc “áo gấm xông hương” cho nó lành!😀😀😀
      2. Nhất trí với M.Phương, ta bổ sung thêm 2 giới tính mới liên quan đến v/đ đồng tính! Khi nào “bài toán tổng quát” được giải quyết trọn vẹn với cả 6 trường hợp đã kể, thì 2 bác kia chỉ còn dc nhận 1/6 giải Nobel thôi!
      3.😀😀

      Phản hồi bởi V. Thành | Tháng Mười 29, 2012 | Trả lời

  5. Trước hết xin cám ơn Việt Dũng, I know we can count on you! Cũng rất vui được “gặp lại” Minh Phương, Văn Thành, Kính ở đây. It’s been a long time!

    VT có thể sửa 1 chút thông tin, Roth là GS trường Kinh doanh Harvard, hiện đang thỉnh giảng tại ĐH Stanford, còn nhà toán học Shapley là GS hưu trí của UCLA.

    Đây không phải lần đầu tiên một nhà toán học được giải Nobel về kinh tế. Còn nhớ John Nash với Game Theory cũng được trao gỉai này vài năm trước và có bộ phim nổi tiếng “A beautiful Mind”.

    Toán học gắn liền với kinh tế hơn ta tưởng rất nhiều và là một phần quan trọng của môn KT. Và rất nhiều mô hình của Kt được áp dụng rất hữu hiệu trong các v/đ xã hội. Nói cụ thể về sự “ổn định” thì “hôn nhân ổn định” và “liên doanh liên kết ổn định” có thể dùng chung một mô hình, chỉ có tham số đưa vào là khác nhau.

    Có vẻ như dân gian đã biết đến thuyết matching của Shapley từ lâu qua câu “nồi nào vung nấy”. Nếu ta chạy phần mềm “hôn nhân ổn định” dựa trên nguyên tắc này thì chắc sẽ ra kết quả tối ưu (tức là sống lâu được với nhau).

    Mình nhớ đã xem 1 bộ phim trong đó có cô gái đến chơi với người yêu vô tình phát hiện trong máy tính của anh ta đang chạy chương trình so sánh cô với một cô gái khác để xem ai là tối ưu để kết hôn. Cô cho anh ta 1 cái tát và cắt đứt. Tất nhiên sau đó anh ta tìm được cách làm lành.

    MP à, mình nhớ 2 câu thơ kia là
    “Chồng em áo rách em thương
    Chồng người áo gấm xông hương mặc người”
    Cái này nó gần nghĩa với “nồi nào vung nấy” hơn là què-lành với ta-người. MP nghĩ sao?

    Mình không tin hôn nhân hoàn toàn do duyên số (khách quan), nó còn quyết định bởi chính mình (chủ quan).

    Về việc chọn đối tác, khi còn đi học mình có học về mô hình này thấy hay và có viết lại để đăng báo, các bạn có thể tham khảo ở đây:
    http://tuanvietnam.vietnamnet.vn/mo-hinh-chon-lua-doi-tac

    Phản hồi bởi chausatran | Tháng Mười Một 12, 2012 | Trả lời

    • Tranh luận với Châu Sa và Minh Phương chút nhỉ.
      Trong kho tàng ca dao VN còn có hai câu này

      Một ngày tựa mạn thuyền rồng
      Còn hơn muôn kiếp ngồi trong thuyền chài.

      Hai bạn nghĩ sao về 2 câu này. Có lễ đó là cũng nguyên nhân (chủ quan) dẫn đến tính bất ổn định của hôn nhân chăng?

      Phản hồi bởi nguyenvietdung | Tháng Mười Một 17, 2012 | Trả lời

      • Cuộc sống luôn có nhiều lựa chọn và khi người ta chọn cái người ta cho là tốt nhất với mình thì đương nhiên phải chấp nhận trả giá (trade-off). Khi chọn sự ổn định tức là chọn đồ thị không có đỉnh và không có đáy. Cách này loại trừ được đáy nhưng cũng làm mất cơ hội có đỉnh. Còn những ai ước vọng có được đỉnh thì phải chấp nhận có lúc phải trải qua đáy.

        Khi người ta lựa chọn tức là có sự chủ quan rồi, vì vậy quan điểm của câu thơ trên đúng là phản ánh sự chủ quan dẫn đến sự “bất ổn định” của hôn nhân của ai đó (“tựa mạn thuyền rồng” là đỉnh, nó có thể được trả giá không chỉ bằng “ngồi trong thuyền chài” mà thậm chí bị hất ra ngoài đường đói rét).

        Tất nhiên khái niệm đỉnh, đáy cũng tương đối vì đôi khi đỉnh của người này cũng không bằng đáy của người kia. Cho nên mình mới nói hôn nhân phụ thuộc cả yếu tố khách quan và chủ quan.

        @ Kính & VT: mình rất tâm đắc với thuyết “hai mặt của vấn đề”. Kính có nhất trí đây là đề tài hấp dẫn mà bọn mình có thể tranh luận trong dịp tới không?

        Phản hồi bởi chausatran | Tháng Mười Một 20, 2012

    • Mình “đóng góp” thêm tư liệu cho cuộc tranh luận sắp tới giữa VDũng, CSa và MPhương nhé:
      Theo các nhà nghiên cứu văn hóa dân gian, hình như đối với rất nhiều vấn đề, nhiều thứ trong xã hội, bao giờ người ta cũng tìm được 2 loại văn bản ngôn ngữ “đối lập nhau” về cùng một thứ thì phải?

      Phản hồi bởi Đỗ Thiên Kính | Tháng Mười Một 17, 2012 | Trả lời

      • Chào C.Sa, Kính và các bạn.
        Tớ thấy “luận đề” của Kính khá hấp dẫn:
        “…
        Theo các nhà nghiên cứu văn hóa dân gian, hình như đối với rất nhiều vấn đề, nhiều thứ trong xã hội, bao giờ người ta cũng tìm được 2 loại văn bản ngôn ngữ “đối lập nhau” về cùng một thứ thì phải?
        …”
        Để chứng minh “luận đề” này, nhờ Kính và các bạn đưa ra bằng chứng, tư liệu từ các câu cao dao, tục ngữ VN, sau đó chúng ta cùng phân tích và chứng minh nhé!

        Tớ sẽ tìm lại cuốn “Kho tàng Ca dao, Tục ngữ Việt nam” của cụ Vũ Ngọc Phan, may ra có thể “góp gạo thổi cơm chung” với các bạn!

        Phản hồi bởi V. Thành | Tháng Mười Một 27, 2012

  6. C.Sa: Nhất trí với C.Sa đây là đề tài hấp dẫn mà mọi người có thể tranh luận trong dịp tới. Nhưng CSa lưu ý cho là hãy “nhẹ tay” để nâng dậy “đối thủ” trong những tình huống cụ thể nhé!

    Phản hồi bởi Đỗ Thiên Kính | Tháng Mười Một 21, 2012 | Trả lời

    • Nhất trí với Kính! Chỉ có một thắc mắc là các “đối thủ” của mình thường là các bậc tài năng tinh hoa, mình vốn “thấp cổ bé họng” mà lại còn “nhẹ tay” nữa chắc biến thành “mít ướt” quá! Hic!

      Phản hồi bởi chausatran | Tháng Mười Một 22, 2012 | Trả lời


Gửi phản hồ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 Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: