Lấy người mình yêu và… không bỏ được (Nobel kinh tế 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ú  () 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 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.