Skip to content

Lấy người mình yêu và… không bỏ được (Nobel kinh tế 2012)

Tháng Mười Một 13, 2012

Giải Nobel kinh tế năm nay vừa được trao cho hai cho hai nhà kinh tế Mỹ A. Roth and L. Shapley. Ông Shapley (cũng như một số kinh tế gia lỗi lạc khác) là một nhà toán học (Ph.D in Math). Một công trình nối tiếng của ông (cùng với D. Gale) là lời giải cho bài toán rất khó “Stable Marriage” (tức là lấy vợ hoặc chống và không thể nào bỏ được). Bài toán này đã được nghiên cứu qua nhiều thế hệ bởi những nhân vật xuất sắc (trong đó có chị Thanh Tâm của Việt Nam), nhựng lời giải của ông Gale và Shapley được coi là có uy tín nhất và nó góp phần mang lại giải thưởng Nobel. (Tất nhiên trong ứng dụng thì vợ/ chồng là những đối tác kinh tế.)

Để nghiên cứu vấn đề “Lấy người mình yêu và… không bỏ được”, trước hết ta quay lại một bài toán dễ hơn là “Lấy người mình yêu”, đã đươc trình bầy trên blog này. Giả sử ta có một tập gồm n chàng trai tuấn tú  (1,2,3...) và n cô gái đẹp (A, B, C...). Một số cặp trai tài gái sắc này có cảm tình với nhau, chẳng hạn 1A, 1B, 2A, 2C, 3A, 3C, 3D, 4D vv. Mục đích của bà mối là tìm ra một cách gép đôi sao cho ai cũng lấy được người mình có cảm tình. Bài toán này đã được giải bời nhà toán học M. Hall (Hall marriage theorem), như ở blog trên.

Thuật toán của bác Hall tuy hay, và làm cho ai cũng lấy được (một trong những)  người mình yêu. Nhưng đáng tiếc, nó không đảm bảo sự bền vững của các mối quan hệ. Ví dụ, một lời giải cho tình huống ở trên là 1B, 2A, 3C, 4D. Nhưng nếu chẳng may nếu chàng số 1 thích cô A hơn cô B, và cô A thích anh 1 hơn anh 2, thì khả năng họ sẽ đến với nhau khá cao, và khi đó tình huống sẽ rất củ chuối vì chàng số 2 và cô B không “rổ rá cạp lại” được vì đôi này ghét nhau từ hồi còn đi vỡ lòng.

Bác Gale và Shapley của chúng ta đã rất tài tình tìm ra được một thuật toán làm cho tình huống éo le trên không xẩy ra được. Trước hết, họ lên điểm các mối quan hệ, ví dụ

1—>A:  6 diểm  (nhanh nhẹn , xinh vừa vừa,  nấu ăn ngon nhưng lại không chịu rửa bát, nghiện phim Hàn Quốc khóc thút thít)

A—->1: 5.5 (Cao to khoẻ mạnh, học hơi dốt nhưng khéo tay, tất nhiên không biết nấu ăn và cũng không thích rửa bát, thích nhảy Gang Nam style)

D—–>4 -2 (Lười tắm)

Cuộc hôn nhân được coi là bền vững (stable mariage)  nếu ta không tìm được hai cặp, chăng hạn như 1B và 2A ở trên khi  1 đánh giá A cao hơn B và A đánh giá 1 cao hơn 2.  Gale và Shapley đưa ra một thuật toán khá đơn giản để tìm ra stable marriage.

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.

Thuật toán này đảm bảo tất cả mọi người đều lập gia đình. Một cô gái nếu một khi đã có hẹn ước, thì từ thời điểm đó trở đi, sẽ liên tục có hẹn ước (có thể với những chàng trai khác nhau), va sẽ nhất định lấy được chồng. Một chàng trai nếu chưa tán được cô nào thì sẽ tiếp tục ngỏ lời với tất cả những ai có thể. Như vậy, đến cuối thuật toán, không thể tồn tại một cập nam nữ mà chưa ai có hẹn ước.

Bài tập:

Chứng minh rằng kết quả của thuật toán là bền vững.

From → Khác

17 phản hồi
  1. RongChoi permalink

    Hồi bé mình có cảm tình với nhiều cô một lúc, lâu nay cứ tưởng tội lỗi, hóa ra nó là đề tài nghiên cứu nghiêm túc🙂

    Điều kiện bền vững này không thể hiện được sự thay đổi tình cảm theo thời gian nhỉ? Chẳng hạn ban đầu đạt trạng thái bền vững, nhưng sau 1 tuần 1 anh tự dưng lên cơn thích 1 cô mà trước đó anh ta rất ghét. Liệu sự thay đổi tình cảm của 1 anh chàng sẽ dẫn đến sự đổ vỡ kết cấu bên vững chung đến đâu nhỉ (khoảng cách ngắn nhất đến một sự bền vững mới)…

      • RongChoi permalink

        dạ vâng, hồi bé, cũng phải có 1 cái mốc nào đó để khỏi lần với hiện tại chứ ạ😉

    • Thuật toán này phải chạy vài lần mới tới điểm ổn định mà anh RC, thêm trục thời gian vào cũng không sao

      Tuy nhiên trong xã hội thực thì còn các lực mạnh khác ảnh hưởng (luật hôn nhân, quy chuẩn đạo đức, vân vân) nên chương trình này là chưa toàn vẹn. Có lẽ thuật toán này chỉ có ý nghĩa trong y sinh học giải phẫu chứ xã hội học thì không có ứng dụng cụ thể

      • RongChoi permalink

        Thuật toán gồm nhiều bước hay vòng lặp chứ sao lại phải thực hiện nhiều lần? Đưa vào cho máy chay, rồi các gia đình quyết định theo đầu ra của máy chứ chả lẽ mỗi bước máy chạy lại rục rịch tổ chức đám cưới😉

        Ý anh là tập các trạng thái bền vững tương ứng với 1 điều kiện ban đầu tạo thành 1 không gian. Thay đổi trạng thái ban đầu cho ta 1 không gian khác. Tính khoảng cách giữa 2 không gian (khoảng cách ngắn nhất giữa hai trạng thái nào đó của 2 tập) với 1 sự thay đổi rất nhỏ ban đầu (khoảng cách thích định nghĩa thế nào cũng được, chẳng hạn “số các cặp nhà tan cửa nát”). Có lẽ bài toán quyết định khoảng cách lớn hơn hay nhỏ hơn $d$ là NP-hard… (đoán bừa, ngại suy nghĩ)

        Ko liên quan gì đến trục thời gian, nói cho vui thôi🙂

      • Em lại tưởng anh định biến các giá trị bằng số kia thành các hàm phụ thuộc thời gian, kiểu sớm nắng chiều mưa, nay thích mai ghét rồi cho chạy máy giải cả hệ theo thời gian

  2. Anonymous permalink

    Stable marriage và lấy nhau không bỏ được là hai khác niệm khác nhau ạ. 2 điểm!

  3. Kimmi permalink

    Em cũng đồng ý là định lý này chả liên quan gì đến đoạn “không bỏ được” ạ. Mí cả, tình cảm có bền vững đâu.

  4. mitca permalink

    Không bỏ được vì nó dọa tự tử hả anh?😀

  5. Anonymous permalink

    The stable marriage problem really has nothing about leaving each other, Professor.

    • Tất nhiên là không ! Thực tế hơn ta có thể nghĩ tới cơ sở sản xuất bánh phở và quán phở.

  6. kimmi permalink

    Bây giờ mới đọc kỹ lại những gì anh Văn viết. Chỉ hỏi anh Văn là anh có đảm bảo hiểu mình hiểu đúng những người bạn của anh không?😀

  7. Bùi Dung permalink

    Hay thầy ạ.

  8. Hay qua! Em dang hoc ve thuat toan nay ma ong thay cu lay bai toan khac (firm vs creditors) ra lam vi du, nhu the nay co phai de hieu hon nhieu khong a. Cam on prof.

Trackbacks & Pingbacks

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

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: