How We Learn

Lý thuyết cầu hôn hay Lấy người mình yêu và không bỏ được, tập 2

the-lovers-1928(1).jpg!Large

Đặt dấu phẩy đúng chỗ là vô cùng quan trọng. Lấy người mình yêu và không bỏ được, tập 2, đáng tiếc, không có nghĩa là

–Lấy người mình yêu và không bỏ được tập 2,

và cũng không có nghĩa

–Lấy người mình yêu, tập 2, và không bỏ được.

Tình thế  không éo le và lãng mạn  như hai tình huống trên. Đơn giản, nó là tập hai của môt câu chuyện đã đăng cách đây vài năm…

Giải Nobel kinh tế năm 2012  đượ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 vô số nhà toán học xuất sắc,  một số có vợ/chồng, một số không, nhựng lời giải của ông Gale và Shapley được coi là có uy tín nhấ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 cá nhân của tác giả bài viết này. Giả sử ta có một tập gồm N chàng trai tuấn tú  () và N cô gái đẹp (). 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  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à . Nhưng  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ọ cho đ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  không chịu rửa bát, nghiện phim Hàn Quốc hay khóc thút thít, chụp ảnh selfie hay dơ ngón tay chữ V)

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, nghiền chuyện chưởng)

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, với 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ẽ cầu hôn với cô gái mà anh ta thích nhất.  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 trong thực tế rất hiệu quả.)  Về phần các cô gái,  nếu được môt anh chàng mới ngỏ lời, lẽ dĩ nhiên, 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), và 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ể.  Gale và Shapley chứng minh rằng nếu sô nam và nữ bằng nhau, thì cuối cùng tất cả mọi người đều lập gia đình, và hôn nhân này là bền vững. Happy End ?

Nhưng chuyện chưa kết thúc ở đây. Câu hỏi thât sự day dứt của tât cả các  cô gái là:

-Trong cái danh sách (dài) của mình, mình sẽ lấy được anh chàng thứ mấy ?

(Danh sách thường bắt đầu bằng George Clooney hoặc Bratt Pit và kết thúc bằng thằng-nhóc-lùn-tì-bàn-bên-cạnh-hồi-đi-học-nó-hay-chọc-thước-kẻ-vào-người-bà.)

Câu trả lời thật sự gây bất ngờ !

Để trả lời câu hỏi sống còn trên, ta cần có một mô hình toán học. Tất cả các mô hình toán học liên quan đến đời sống đều có yếu tố ngẫu nhiên, cũng như bản thân cuộc sống vậy.

Giả sử trong thành phố có N chàng trai và N cô gái, để đơn giản, mỗi người xếp hạng tất cả N nhân vật phía bên kia. Ta giả sử các xếp hạng này là ngẫu nhiên, phải chăng vẻ đẹp trong mắt mỗi con người là khác nhau, chẳng hạn rất nhiều người   quan niệm là phụ nữ quyến rũ là phải hơi béo.

Môt đồng nghiệp người Nga, cụ Pittel, chừng 30 năm trước,  chứng minh rằng trung bình các chàng trai sẽ lấy được cô gái đứng cỡ  trong list của anh ấy. Chảng hạn  thi . Tức là bạn sẽ có khả năng cao là lấy được một hoa hậu top ten (trong danh sách của mình).

Điều trớ trêu là lời giải này không đối xứng: các cô gái sẽ  không lấy được các chàng trai top ten trong list của họ !! Pittel chứng minh rằng, trung bình,  họ sẽ lấy các anh xếp hạng cỡ . Trong trường hợp , các nàng sẽ phải xuống tận thứ 1000 để tìm ý trung nhân.  Hiện tượng  bất đối xứng này đã được các nhà văn hoá Viêt Nam tổng kết với hình tượng  gợi cảm  liên quan tới  hoa nhài và trâu, mà chúng tôi không tiện trích dẫn ở đây.

Bí mật ở đây là thuật toán của Gale-Shapley không đối xứng cho nam và nữ, bởi các chàng trai luôn là người cầu hôn.  Thế mạnh của kẻ chủ động. Phụ nữ đã nghĩ một cách rất ngây thơ là càng được nhiều người cầu hôn càng có giá, và, thật đáng tiếc,  đã không đọc bài của Pittel !

Thế nhưng, lưới trời lồng lộng. Sự bất đối xứng này được giải quyết bởi sự bất đối xứng khác. Cũng bởi nam giới có một số lợi thế, nên ở  các nước châu Á, nam thường nhiều hơn nữ. Giả sử có thêm môt anh chàng vào cuộc chơi, tức là  nam và  nữ, và ta cho chạy lại thuật toán cầu hôn như cũ. Tất nhiên cuối cùng sẽ có môt anh chàng không lấy được vợ. Nhưng  đáng ngạc nhiên thay, với sự kỳ diêu của toán học (qua một công trình khá mới mẻ của Ashlagi, Kanoria, and Leshno, 2015, và follow-up work của Pittel, 2018),  số phận chúng ta   thay đổi  180 độ,

-Các chàng trai sẽ lấy các cô thứ  trong list của mình.

-Các cô gái sẽ lấy các anh top ten (chính xác hơn, top , nhưng dĩ nhiên bạn không quan tâm  là gì).

Hỡi ơi, người tính không bằng trời tính. Dù ai có dầy công chuẩn bị một (số) cuộc cầu hôn công phu, nhưng chỉ cần một anh phá thối thì công sức cũng ra biển mà thôi.

Ngày Valentine đang đến. Và cái sự cầu hôn kia, rất có thể sẽ thành sự thật. Khi bữa tối đã gần xong, ánh nến đã lung linh,  hoa hồng đã cầm tay, và chàng trai khốn khổ đã run run cất tiếng, bạn hãy hít môt hơi dài, nhìn  vào mắt chàng, sâu thẳm, và thầm thì câu hỏi quan trọng nhất của đời mình:

Vậy danh sách của anh có bao nhiêu người ?

Vũ Hà Văn

Một số ký tự toán học của bài viết của GS Vũ Hà Văn bị “biến mất” khi chuyển qua Học Thế Nào. Các bạn có thể xem bản hiển thị đầy đủ ở blog GS Văn theo đường link này.

 

 

 

 

 

Tagged as:

1 Response »

  1. Blog hay nhưng mà nhiều kí tự toán học không hiển thị được, blog vui long kiểm tra lại giúp ạ.

    Số lượt thích

Trả lờ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 Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s

Nhập địa chỉ email để nhận thông báo có bài mới từ Học Thế Nào.

%d bloggers like this: