Tài liệu Thuật toán chấp nhận trì hoãn và thiết kế thị trường

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC —————— NGUYỄN TIẾN HUY THUẬT TOÁN CHẤP NHẬN TRÌ HOÃN VÀ THIẾT KẾ THỊ TRƯỜNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên, năm 2014 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC —————— NGUYỄN TIẾN HUY THUẬT TOÁN CHẤP NHẬN TRÌ HOÃN VÀ THIẾT KẾ THỊ TRƯỜNG Chuyên ngành: Toán ứng dụng Mã số: 60.46.01.12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: GS. TSKH. HÀ HUY KHOÁI Thái Nguyên, năm 2014 1 Mục lục Lời cảm ơn 3 Lời mở đầu 4 Chương 1. Thuật toán chấp nhận trì hoãn 7 1.1 1.2 Tuyển sinh đại học và hôn nhân bền vững . . . . . . . . . 7 1.1.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Các tiêu chí về phân bổ . . . . . . . . . . . . . . . 8 1.1.3 Hôn nhân bền vững . . . . . . . . . . . . . . . . . . 10 Thuật toán chấp nhận trì hoãn . . . . . . . . . . . . . . . 11 1.2.1 Định lý về sự tồn tại phân bổ ổn định với vấn đề hôn nhân . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Phân bổ ổn định với vấn đề tuyển sinh . . . . . . . 14 1.2.3 Phân bổ ổn định tối ưu . . . . . . . . . . . . . . . . 15 Chương 2. Thiết kế thị trường 2.1 Sự minh bạch: Những Thị trường bác sĩ 16 . . . . . . . . . . 16 2.1.1 Thị trường cho những bác sĩ mới ở Mỹ . . . . . . . 17 2.1.2 Thị trường y tế địa phương tại Vương quốc Anh . . 18 2 2.1.3 2.2 Bằng chứng thử nghiệm . . . . . . . . . . . . . . . 20 Thiết kế thị trường . . . . . . . . . . . . . . . . . . . . . . 21 2.2.1 Thiết kế lại thị trường bác sĩ . . . . . . . . . . . . . 21 2.2.2 Tuyển sinh đại học . . . . . . . . . . . . . . . . . . 23 2.2.3 Trao đổi thận . . . . . . . . . . . . . . . . . . . . . 25 Kết luận 28 Tài liệu tham khảo 29 3 Lời cảm ơn Trước khi trình bày nội dung chính của luận văn, tôi xin được bày tỏ lòng biết ơn sâu sắc tới GS. TSKH. Hà Huy Khoái, người đã tận tình hướng dẫn, giúp đỡ, động viên tôi hoàn thành được luận văn này. Tôi cũng xin gửi lời cảm ơn chân thành tới các thầy cô giáo thuộc Khoa Toán - Tin, Trường Đại học Khoa học, Đại học Thái Nguyên, bạn bè, đồng nghiệp, người thân đã tạo điều kiện, động viên, giúp đỡ tôi trong suốt quá trình học tập và thực hiện luận văn. 4 Lời mở đầu Khi nghiên cứu về sự tắc nghẽn của việc phân bổ lao động của một số thị trường tại Mỹ, Alvin Roth đã nhận thấy sự tương đồng của những thị trường này với mô hình toán học đã được Lloyd Shapley nghiên cứu từ cách đây 50 năm. Sau đó, ông đã nghiên cứu và thiết kế lại những thị trường này dựa trên thuật toán chấp nhận trì hoãn được đưa ra bởi D. Gale và Lloyd Shapley năm 1962. Những đóng góp to lớn của Roth đã được ghi nhận, tháng 10 năm 2012 Alvin Roth và Lloyd Shapley vinh dự nhận Giải Nobel Kinh tế về Lý thuyết phân bổ ổn định và thiết kế thị trường. Câu chuyện bắt đầu vào năm 1962, David Gale (người đã qua đời năm 2008) và Shapley, hiện 89 tuổi, đã cho công bố bài báo mang tên "Tuyển sinh đại học và Sự ổn định của hôn nhân" (College Admissions and the Stability of Marriage). Hai ông cho rằng sự tương đồng giữa tuyển sinh đại học, trong đó sinh viên và trường đại học đang tạo thành cặp đôi với sự cố gắng làm cả hai bên hài lòng, và thị trường hôn nhân, trong đó một số cố định nam giới và nữ giới đang cố gắng tìm kiếm hôn nhân. Trong các vở kịch lãng mạn, từng người đàn ông và đàn bà đều kết hôn với tình yêu đích thực của mình. Trong cuộc sống thực tế, một số người miễn cưỡng chấp nhận "nhân vật hạng hai" một việc làm có thể dẫn đến rất nhiều rắc rối. Nếu John và Mary yêu nhau nhưng đã kết hôn với những người khác, rất có thể họ sẽ bỏ người bạn đời hiện tại và cưới nhau. Nhưng nếu John yêu Mary, trong khi Mary yêu chồng cô hơn John, cả hai sẽ không có thay đổi nào trong cuộc hôn nhân của họ. Gale và Shapley nghĩ ra một thuật toán để ghép một số lượng bằng nhau nam giới và nữ giới. Từng nam giới và nữ giới sẽ xếp hạng đối tác yêu thích của họ. Từng nam giới cầu hôn người phụ nữ được anh ta xếp hạng cao nhất. Mỗi người nữ giới từ chối toàn bộ những lời cầu hôn chị ta nhận được ngoại 5 trừ người được xếp hạng cao nhất. Nhưng người phụ nữ này không chấp nhận lời cầu hôn, nếu người đàn ông chị ta yêu thích thậm chí lại cầu hôn vào lần tới. Thuật toán này được lặp lại cho đến khi toàn bộ số phụ nữ có được lời cầu hôn vừa ý. Trên thực tế thì lý thuyết ổn định và thuật toán chấp nhận trì hoãn không có cơ hội để biến đổi thị trường hôn nhân. Nhưng Roth đã đưa ứng dụng thực tiễn của thuật toán vào những lĩnh vực khác. Trong những năm 1940, cuộc cạnh tranh giành bác sĩ đôi khi đã chứng kiến việc các bệnh viện thậm chí "chào mời" sinh viên nhiều năm trước khi họ tốt nghiệp, trước khi biết rõ bằng cấp và khả năng chuyên môn của họ. Chương trình quốc gia về lựa chọn bác sĩ phù hợp (The National Resident Matching Programme) được đưa ra nhằm lựa chọn bác sĩ phù hợp cho các bệnh viện theo phương thức tối đa hóa sự hài lòng của cả 2 bên. Chương trình này Roth đã viết trong một tài liệu năm 1984, là ví dụ đời thực về thuật toán "chấp nhận trì hoãn" (deferred-acceptance) của 2 ông Gale và Shapley. Những hệ thống khác hoạt động ít hiệu quả hơn. Cả hệ thống trường công New York và Boston được sử dụng để chỉ định sinh viên theo sự lựa chọn yêu thích của họ, nhưng sinh viên thường phải quyết định trước khi biết toàn bộ quyền lựa chọn của họ. Hàng nghìn người học xong phổ thông mà không bày tỏ sự yêu thích nào. Ông Roth giúp thiết kế thuật toán cho cả 2 trường trên và giúp giảm đáng kể những lựa chọn sai lầm. Roth cũng áp dụng kiến thức của mình vào hoạt động hiến nội tạng. Một người sẽ không hiến thận trong nhiều tình huống và hoàn cảnh, nhưng lại có thể hiến thận nếu vợ anh ta cần. Nếu nhóm máu của họ không phù hợp, họ có thể được ghép đôi với những cặp đôi khác tương tự. Chương trình Trao đổi Thận của New England, được sáng lập một phần nhờ ông Roth, tích hợp nhiều chuỗi những người hiến tặng và người tiếp nhận và tăng nguồn cung cấp thận bằng cách làm cho người hiến tặng tự tin hơn rằng người yêu dấu của họ cũng sẽ tìm được một quả thận phù hợp. Ngày nay internet có thể giúp hệ thống đối xứng phù hợp trở nên khả thi. Tuy nhiên, không phải lúc nào cũng có thể cải tiến những hệ thống hiện có. Utku Ünver tại Đại học Boston, người đã cùng ông Roth phát triển chương trình trao đổi thận, chỉ rõ việc sắp xếp sinh viên luật vào vị trí thư ký cho thẩm phán liên bang. Các thẩm phán có quyền kiểm soát toàn bộ đối với 6 những người họ thuê làm, và những sinh viên mà họ chọn, do vậy, hệ thống lựa chọn phù hợp mang lại ít lợi ích hơn. Khi các khoa kinh tế học thuê mới tiến sĩ đến làm việc, hệ thống lựa chọn phù hợp sẽ giúp các giao dịch trở nên thuận lợi hơn vì rất khó để gian lận trong hệ thống này. Ông Utku Ünver cùng cộng sự đang phát triển phương thức giới thiệu những đứa trẻ phù hợp đến các giai đình muốn nhận con nuôi ở Pennsylvania, tuy vậy, quyết định cuối cùng lại tùy thuộc vào nhân viên xã hội và các gia đình. Trong bài viết năm 1962, Gale và Shaply lưu ý rằng thuật toán của họ không quá phức tạp, minh họa một quan điểm về nguyên tắc của họ: "bất kỳ tranh luận nào được tiến hành với độ chính xác đầy đủ đều mang tính toán học". Sự công nhận công trình của ông Shapley và ông Roth cũng là sự khẳng định rằng đối với những tin tức xấu mà kinh tế học nhận được từ cuộc khủng hoảng, nguyên tắc trên vẫn đủ hiệu quả để giúp giải quyết những vấn đề đời thực. Trong luận văn này, tôi xin trình bày về thuật toán chấp nhận trì hoãn cũng như những đóng góp của Giáo sư Roth trong việc ứng dụng thuật toán trên vào việc thiết kế thị trường. Bố cục của luận văn bao gồm 2 chương: Chương 1 trình bày về thuật toán Gale-Shapley (thuật toán chấp nhận trì hoãn) và những lý thuyết về phân bổ ổn định. Chương 2 luận văn xin được đưa ra ứng dụng của thuật toán chấp nhận trì hoãn vào thiết kế thị trường cũng như những đóng góp của Giáo sư Roth. Do thời gian nghiên cứu có hạn, luận văn không tránh khỏi những thiếu sót, tác giả rất mong nhận được những ý kiến đóng góp của các thầy và các bạn để luận văn được hoàn thiện hơn. Xin chân thành cảm ơn! Thái Nguyên, tháng 5 năm 2014 Người thực hiện Nguyễn Tiến Huy 7 Chương 1 Thuật toán chấp nhận trì hoãn 1.1 1.1.1 Tuyển sinh đại học và hôn nhân bền vững Giới thiệu Bài toán mà chúng ta quan tâm liên quan tới tình huống điển hình sau: Một trường đại học đang xem xét một tập n thí sinh (đơn xin nhập học) trong đó chỉ có nhận q chỉ tiêu. Qua việc đánh giá khả năng trình độ của họ, phòng tuyển sinh phải quyết định những thí sinh nào được nhận. Phương thức tuyển sinh chỉ q− thí sinh đủ năng lực trình độ sẽ không được thỏa đáng, không thể giả định rằng tất cả những người được nhập học sẽ chấp nhận. Theo đó, để trường đại học nhận đủ q− chấp thuận, trường đó thường phải đưa ra chấp nhận nhiều hơn q− thí sinh. Bài toán xét xem có bao nhiêu người và những người nào trong số họ đồng ý cần thiết hơn là sự phỏng đoán. Có thể không biết được liệu một thí sinh ở trên cũng nộp đơn ở những trường khác hay không; nếu biết được điều này thì cũng có thể không thể biết được thí sinh đó xếp hạng những trường đại học thí sinh đó đã nộp đơn như thế nào; thậm chí nếu điều này được biết thì cũng sẽ không biết được có những trường khác chấp nhận nhập học cho anh ta. Kết quả của những điều không chắc chắn này là những trường đó chỉ có thể trông đợi ở những lớp nhập học với số sinh viên hợp lý gần đạt đến chỉ tiêu mong muốn, và chất lượng tốt nhất có thể đạt được. Một vấn đề khó khăn đó là việc đưa ra "danh sách đợi", theo đó một thí 8 sinh không được nhận nhưng có thể được nhận sau đó nếu trường đó vẫn chưa tuyển đủ. Việc này nảy sinh thêm vấn đề mới, giả sử một thí sinh được nhận vào một trường và có tên trong danh sách đợi của một trường khác mà anh ta thích hơn. Anh ta có nên lựa chọn an toàn bằng việc chấp nhận vào học trường đã nhận mình hay chờ đợi một cơ hội rằng trường anh ta thích hơn sẽ nhận anh ta? Chúng ta nên cố gắng để những vấn đề khó khăn được nêu ra ở trên đây có thể tránh được. Chúng ta sẽ mô tả một phương thức gán một thí sinh với một trường đại học mà có thể thỏa mãn cả đôi bên trong đó chúng ta loại bỏ hết sự không chắc chắc trong các trường hợp và giả sử rằng có đủ thí sinh vào mỗi trường theo đủ chỉ tiêu. 1.1.2 Các tiêu chí về phân bổ Một tập n thí sinh được phân giữa m trường đại học, với qi là chỉ tiêu của trường thứ i. Mỗi thí sinh xếp hạng trường theo thứ tự ưu tiên của người đó, chỉ bỏ sót những trường mà người đó không bao giờ chấp nhận vào học dưới mọi trường hợp. Để thuận tiện hơn, chúng ta giả sử giữa thí sinh và trường không có quan hệ nào, theo đó một thí sinh vô tư giữa hai hay nhiều trường mà người đó không cần thiết sắp xếp theo trật tự nào đó. Mỗi trường đại học tương tự cũng xếp hạng thí sinh đã nộp đơn theo tiêu chí của mình, loại những thí sinh mà không đáp ứng yêu cầu dưới mọi trường hợp, thậm chí kể cả không tuyển đủ chỉ tiêu. Từ những dữ kiện trên, bao gồm cả chỉ tiêu tuyển sinh của các trường và hai tập hợp sắp xếp đó, chúng ta muốn xác định một sự phân bổ của thí sinh vào các trường dựa vào sự thỏa thuận dựa trên tiêu chí công bằng nhất. Phát biểu như cách ở trên nghe có vẻ không sâu sắc, lời giải có thể sẽ rõ ràng. Việc này đơn thuần tạo nên sự phân bổ theo những tiêu chí đã được đưa ra. Nhưng chỉ một vài sự việc đối ngược nảy sinh cũng làm cho việc phân bổ trở lên khó khăn. Một ví dụ trong trường hợp đơn giản giữa 2 trường A và B , và hai thí sinh α và β trong đó α thích trường A hơn và β thích trường B hơn, nhưng trường A thích thí sinh β hơn và trường B thích thí sinh α hơn. Và ở đây không có sự phân bố nào có thể thỏa mãn tất cả tiêu chí trên. Phải quyết định làm thế nào đó trong trường hợp như thế này. Theo triết 9 lý thì trường đại học tồn tại là để cho sinh viên học, vì vậy hợp lý hơn nếu phân thí sinh α vào trường A và thí sinh β vào trường B . Vấn đề chốt lại ở đây đó là phải quyết định như thế nào trong trường hợp ở bên trên. Định nghĩa 1.1. Một sự phân bổ giữa các thí sinh và các trường đại học được gọi là không ổn đinh (không bền vững) nếu có hai thí sinh α và β lần lượt được phân vào trường A và trường B , mặc dù β thích trường A hơn trường B và trường A cũng muốn có được sinh viên α hơn β . Giả sử tình huống mô tả ở trên không xảy ra. Thí sinh β không được phân vào trường A, trường mà thí sinh đó muốn được vào học. Khi đó trường A có thể thay đổi lại bằng việc không nhận thí sinh α và giành chỉ tiêu đó cho sinh viên β . Sự phân bổ lúc này được gọi là không ổn định với nghĩa là nó có thể bị phá bỏ bởi việc một trường có thể nhận thí sinh mình thích hơn. Yêu cầu đầu tiên của chúng ta trong sự phân bổ trên có vể như không ổn. Điều này ngay lập tức nảy sinh câu hỏi: Liệu có khả năng tìm được một sự phân bổ? Một câu trả lời khẳng định cho câu hỏi này được đưa ra ở phần tiếp theo. Giả sử lúc này phân bổ ổn định tồn tại, chúng ta vẫn phải quyết định xem trong những khả năng phân bổ ổn định đó, đâu là tốt nhất. Định nghĩa 1.2. Một sự phân bổ ổn định được gọi là tối ưu nếu mỗi thí sinh ít nhất đều được vào trường mình ưng ý hơn so với bất kỳ sự phân bổ ổn định nào khác. Thậm chí cho rằng sự tồn tại của sự phân bổ ổn định khác xa so với sự phân bố ổn tối ưu. Tuy nhiên, một điều rõ ràng sự phân bổ ổn định tối ưu nếu có tồn tại thì sẽ duy nhất. Thực sự nếu có hai sự phân bổ, trong đó ít nhất một thí sinh sẽ được chấp nhận vào trường tốt hơn trong trường hợp còn lại; vì vậy một trong sự phân bổ đó sẽ không là tối ưu. Vì vậy nguyên tắc về ổn định và tối ưu sẽ xảy ra, khi câu hỏi tồn tại đã được giải quyết, dẫn dắt chúng ta tới một sự phân bổ tốt nhất. 10 1.1.3 Hôn nhân bền vững Một vấn đề có nhiều nét tương đồng với vấn đề tuyển sinh đại học đó là vấn đề hôn nhân bền vững. Trong một cộng đồng nhất định bao gồm n người đàn ông và m người phụ nữ. Mỗi người xếp hạng những người trong giới đối lập với họ theo một thứ tự ưu tiên nhất định để chọn người phù hợp để kết hôn. Chúng ta tìm kiếm cách phù hợp để có thể tạo nên hôn nhân cho tất cả các thành viên trong cộng đồng người đó. Theo như định nghĩa trước, chúng ta gọi một tập những hôn nhân không bền vững nếu có một người đàn ông và một người phụ nữ không kết hôn với nhau mặc dù họ rất thích nhau. Câu hỏi: Với bất kỳ tiêu chí ưu tiên đưa ra, liệu có thể tìm được một tập hôn nhân bền vững hay không? Trước khi đưa ra câu trả lời cho câu hỏi này, chúng ta hãy xem ví dụ sau. Ví dụ 1.1. Dưới đây là "ma trận xếp hạng" của 3 người đàn ông α, β và γ với 3 người phụ nữ A, B và C . A B C α 1,3 2,2 3,1 β 3,1 1,3 2,2 γ 2,2 3,1 1,3 Số đầu tiên trong mỗi cặp trong ma trận trên cho ta biết sự xếp hạng người phụ nữ của người đàn ông, và số thứ hai cho ta biết sự xếp hạng đàn ông của người phụ nữ. Theo đó ta có α xếp hạng A trước tiên, thứ hai là B và cuối cùng là C , trong khi người đàn ông A lại chọn phụ nữ β là sự lựa chọn số một, γ là thứ hai và cuối cùng mới chọn α... Có 6 khả năng kết hôn, trong đó có 3 là bền vững. Một kết hôn trong số đó được thực hiện bằng việc mỗi người đàn ông sẽ cưới người phụ nữ mà anh ta thích nhất, tức là α kết hôn với A, β kết hôn với B và γ kết hôn với C . Chú ý rằng mỗi người phụ nữ cưới được người đàn ông đều là những người đàn ông thứ ba trong số 3 người đàn ông mà họ được chọn. Sự sắp xếp như trên tuy thế mà bền vững. Ngoài ra còn một cách kết hôn đó là mỗi người phụ nữ cưới người đàn ông mà họ thích nhất, α cưới C , β cưới A và γ cưới B . Cách kết hôn bền vững thứ ba đó là cho họ cưới người mà họ chọn thứ 11 hai trong số 3 người, ta có α cưới B , β cưới C và γ cưới A. Chúng ta hoàn toàn có thể chỉ ra rằng các cách kết hôn còn lại khác là không bền vững. Ví dụ 1.2. Ma trận xếp hạng được cho như sau: A B C D α 1,3 2,3 3,2 4,3 β 1,4 4,1 3,3 2,2 γ 2,2 1,4 3,4 4,1 δ 4,1 2,2 3,1 1,4 Chỉ có duy nhất một hôn nhân bền vững được chỉ ra bởi những ô được đóng khung trong ma trận trên. Chú ý rằng trong tình huống trên không người nào có thể cưới được người mình thích nhất nếu đạt được sự bền vững. Ví dụ 1.3. Một vấn đề tương tự với vấn đề hôn nhân, đó là vấn đề "bạn cùng phòng". Một số chàng trai muốn được chia thành các cặp để ở cùng phòng với nhau. Một tập các cặp như trên được gọi là ổn định nếu không có hai anh chàng nào không cùng phòng và lại thích ở với người bạn khác hơn là ở với người cùng phòng với mình hiện tại. Một ví dụ đơn giản chỉ ra rằng có tình huống mà không tìm được cặp ổn định. Cụ thể là, xét bốn anh chàng α, β, γ và δ . α thích ở với β nhất, β chọn γ là người muốn ở chung phòng nhất, γ chọn người mình muốn ở cùng phòng nhất là α, và cả ba người α, β, γ đều xếp δ vào vị trí cuối cùng trong số những người mình muốn chung phòng. Do đó bất kể sự lựa chon của δ là như thế nào đi nữa thì cũng không thể có được cặp chung phòng ổn định vì bất cứ ai được xếp ở cùng phòng với δ đều muốn dọn đi và một trong hai chàng còn lại sẵn sàng để cho người đó vào ở chung phòng với mình. 1.2 1.2.1 Thuật toán chấp nhận trì hoãn Định lý về sự tồn tại phân bổ ổn định với vấn đề hôn nhân Trong các ví dụ ở phần trên, lời giải với bài toán phân bổ ổn định còn chưa rõ ràng, và chúng ta luôn quan tâm đến câu hỏi phân bổ ổn định có 12 luôn luôn tồn tại hay không. Để trả lời câu hỏi này, trong bài báo năm 1962 (xem [5]), D. Gale và L. Shapley đã chỉ ra rằng: Định lý 1.1. Luôn luôn tồn tại một hôn nhân bền vững. Chứng minh. D. Gale và L. Shapley đã chứng minh định lý trên bằng việc đưa ra thuật toán, mang tên Thuật toán Gale-Shapley hay còn gọi là "Thuật toán chấp nhận trì hoãn". Thuật toán chấp nhận trì hoãn được mô tả như sau: Bước 1: cho mỗi chàng trai đưa ra lời cầu hôn tới người con gái mà anh ta thích nhất. Mỗi người con gái nhận được nhiều hơn một lời cầu hôn sẽ từ chối tất cả và chỉ giữ lại lời cầu hôn của người con trai mà cô ta thích. Tuy nhiên cô ta chưa đồng ý ngay, nhưng giữ lại lời cầu hôn của người con trai đó và chờ đợi lời cầu hôn từ người mà cô ta mong muốn hơn. Bước 2: Những người con trai bị từ chối ở lần cầu hôn đầu tiên, tiếp tục cầu hôn với người con gái mà anh ta thích thứ hai. Mỗi cô gái nhận được lời cầu hôn sẽ chọn lời cầu hôn từ nhóm bao gồm những lời cầu hôn mới và lời cầu hôn của người con trai mà cô ta đã giữ lại trước đó. Cô ta tiếp tục từ chối và chỉ giữ lại lời cầu hôn từ người mà cô ta còn phân vân. Bước k: Những người con trai bị từ chối ở lần cầu hôn thứ trước đó tiếp tục cầu hôn với cô gái trong lựa chọn tiếp theo của mình, các cô gái từ chối tất cả các lời cầu hôn và chỉ giữ lại lời cầu hôn từ người con trai mà cô ta thích nhất trong số những lời cầu hôn đó. Cuối cùng, mọi cô gái đều nhận được lời cầu hôn cho đến khi bất kỳ cô gái nào không được cầu hôn sẽ bị từ chối và nhận lời cầu hôn mới, nhưng vì không có anh chàng nào có thể cầu hôn tới cùng một cô gái hơn một lần, nên mọi cô gái chắc chắn sẽ nhận được lời cầu hôn. Ngay sau khi các cô gái nhận được những lời "tán tỉnh" như trên, mỗi cô gái bây giờ cần thiết phải chấp nhận những chàng trai trong danh sách đợi của cô gái đó. D. Gale và L. Shapley đã chỉ ra rằng thuật toán trên tối đa sẽ phải thực hiện n2 − 2n + 2 bước lặp. Chúng ta khẳng định rằng cách thiết lập hôn nhân này là bền vững. Thật vậy, giả sử John và Mary đều chưa kết hôn với nhau nhưng John thích Mary hơn vợ của anh ấy. Theo đó, John đã phải cầu hôn Mary ở một bước nào đó và bị Mary từ chối bởi vì Mary nhận được lời cầu hôn từ một người mà cô 13 ấy thích hơn. Rõ ràng là Mary phải thích chồng của cô ấy hơn John và do đó sẽ không có hôn nhân bền vững. Chú ý: +) Điều kiện về số con trai và con gái bằng nhau là không cần thiết. Nếu có b chàng trai và g cô gái với b < g , quá trình sẽ dừng lại ngay khi b cô gái được cầu hôn. Nếu b > g thì quá trình trên sẽ kết thúc mọi chàng trai đều nằm trong danh sách đợi của các cô gái hoặc bị tất cả các cô gái từ chối. Trong những trường hợp này thì hôn nhân đều bền ổn định bền vững. +) Rõ ràng, còn có một cách ngược lại đó là việc các cô gái đi cầu hôn con trai, và cũng dẫn đến hôn nhân bền vững. Hai lời giải của bài toán hôn nhân bền vững này không giống nhau. Trong trường hợp khi người con trai cầu hôn thì kết quả nhận được là tối ưu đối với người con trai, và ngược lại với lời cầu hôn của các cô gái thì kết quả nhận được là tối ưu với các cô gái. Lời giải trong hai trường hợp trên là giống nhau chỉ khi có một hôn nhân bền vững duy nhất. Ta xét ví dụ sau: Ví dụ 1.4. A B C D α 1,3 2,2 3,1 4,3 β 1,4 2,3 3,2 4,4 γ 3,1 1,4 2,3 4,2 δ 2,2 3,1 1,4 4,1 Sử dụng thuật toán chấp nhận trì hoãn với lời cầu hôn của người đàn ông ta thu được: A B C Bước 1 α, β γ δ Bước 2 α β, γ δ Bước 3 α β γ, δ Bước 4 α, δ β γ Bước 5 δ α, β γ D 14 Bước 6 δ α γ, β Bước 7 δ, γ α β Bước 8 γ α, δ β Bước 9 γ δ α, β Bước 10 γ δ α β Qua 10 bước, ta nhận được hôn nhân bền vững: α kết hôn với C , β kết hôn với D, γ kết hôn với A và δ kết hôn với B . Sử dụng thuật toán chấp nhận trì hoãn với lời đề nghị của người phụ nữ ta được: α β γ δ Bước 1 C A B, D Bước 2 C A, D B A B A B Bước 3 C, D Bước 4 C D Qua 4 bước ta nhận được hôn nhân bền vững: A kết hôn với γ , B kết hôn với δ , C kết hôn với α và D kết hôn với β . 1.2.2 Phân bổ ổn định với vấn đề tuyển sinh Mở rộng của cách làm "chấp nhận trì hoãn" với vấn đề tuyển sinh đại học. Để thuận tiện, ta giả sử nếu một trường đại học không có ý muốn nhận một sinh viên nào đó với bất kỳ điều kiện nào, như đã trình bày ở mục 2, theo đó thí sinh đó không nộp đơn vào trường đó. Với ý hiểu như vậy, cách làm được trình bày như sau: Đầu tiên, các sinh viên nộp đơn vào trường mà người đó ưu tiên đầu tiên. Một trường thì có số chỉ tiêu tuyển sinh là q nên sẽ đặt vào danh sách đợi q thí sinh mà trường đó đã xếp hạng cao nhất, hoặc tất cả các thí sinh nếu như số thí sinh ít hơn q chỉ tiêu, và từ chối những thí sinh còn lại. Những thí sinh bị từ chối, tiếp tục nộp đơn vào trường mà người đó lựa chọn tiếp theo, và một lần nữa trường đó sẽ chọn q thí sinh đứng đầu trong số các thì sinh mới nộp đơn và những thí sinh đã được đưa vào danh 15 sách đợi trước đó, và đặt vào danh sách đợi mới, và từ chối những thí sinh còn lại. Quá trình trên dừng khi khi mọi thí sinh được nằm trong danh đợi của các trường hoặc bị từ chối bởi mọi trường anh ta đã nộp đơn vào. Tại thời điểm này, mỗi trường tuyển mọi thí sinh trong danh sách đợi của trường đó và khi đó đạt được phân bổ ổn định. Việc chứng minh sự phân bổ trên là ổn định hoàn toàn tương tự việc chứng minh đã được trình bày trong vấn đề hôn nhân bền vững. 1.2.3 Phân bổ ổn định tối ưu Bây giờ chúng ta sẽ chỉ ra rằng cách làm "chấp nhận trì hoãn" vừa mô tả ở trên không những là cách phân bổ ổn định mà còn là một cách phân bổ tối ưu. Định lý 1.2. Mọi thí sinh ít nhất đều thỏa mãn dưới sự phân bổ được cho bởi cách làm chấp nhận trì hoãn dưới bất kỳ sự phân bổ ổn định khác. Chứng minh. Ta gọi một trường "có thể được" cho riêng một thí sinh nếu có một sự phân chia ổn định đưa anh ta vào học trường này. Giả sử rằng đến một điểm cho trước trong phương cách trên mà không có thí sinh nào bỏ đi khỏi trường mà có thể cho anh ta vào học. Tại điểm này, giả sử trường A đã nhận được những thí sinh đủ chỉ tiêu từ những thí sinh được đánh giá cao hơn β1 , β2 , ..., βq và từ chối thí sinh α. Chúng ta cần chỉ ra rằng trường A là không thể được cho thí sinh α. Chúng ta biết rằng mỗi thí sinh βi thích vào trường A hơn những thí sinh còn lại khác, ngoại trừ những trường đã không chấp nhận họ vào học, và vì vậy theo giả thiết bên trên thì trường đó là có thể cho thí sinh βi . Ta xét một giả thuyết phân bổ mà với phân bổ này thì sẽ đưa α vào học trường A và mọi thí sinh khác sẽ vào học trường mà có thể được cho họ. Ít nhất một trong số các thí sinh βi sẽ phải vào học trường mình không mong muốn hơn trường A. Nhưng sự sắp xếp này là không ổn định, vì βi và A có thể phá hỏng vì lợi ích của cả hai. Theo đó sự phân bổ theo giả thuyết trên là không ổn định và trường A là có thể được cho thí sinh α. Ta kết luận rằng cách làm trong thuật toán của chúng ta chỉ loại ra những thí sinh từ những trường mà họ không thể có khả năng được nhận dưới bất kỳ sự phân bổ nào. Vì vậy cách phân bổ này là tối ưu. 16 Chương 2 Thiết kế thị trường 2.1 Sự minh bạch: Những Thị trường bác sĩ Làm việc về sự phân bổ ổn định và những thuật toán về ổn định đã được nhận ra là một lý thuyết vô cùng quan trọng trong thập niên 60 và 70 của thế kỷ 20, nhưng nó chưa được biết đến nhiều cho đến đầu những năm 80 khi những đóng góp thực tế liên quan tới được khám phá. Đóng góp quan trọng là Roth (xem [4]), những dẫn chứng về sự phát triển của thị trường bác sĩ mới tại Mỹ và những tranh luận thuyết phục rằng một thuật toán về sự ổn định cải thiện được chức năng của thị trường. Việc làm này đã mở ra cánh cửa cho sự tham gia của Roth vào những thiết kế thị trường thực tế, bắt đầu vào những năm 1990. Roth đã tiến hành nghiên cứu thực nghiệm về những thị trường y tế khác nhau, đưa ra dẫn chứng và phân tích một vài khu vưc ở Anh thông qua những thuật toán khác nhau (xem [2]). Tập chung vào các cơ chế phù hợp, chẳng hạn như thị trường bác sĩ mới tại Mỹ, đã xác định được "quy tắc của trò chơi" được biết đến bởi chính họ và những nhà kinh tế nghiên cứu về thị trường. Những kiến thức về những nguyên tắc này làm cho nó có thể thử tiên đoán lý thuyết trò chơi, trong lĩnh vực thử nghiệm trong phòng thí nghiệm. Hơn nữa, những nguyên tắc này có thể thiết kế lại nhằm cải thiện thị trường. Theo đó những lý thuyết này đã được nghiên cứu sâu rộng và ngày nay đã được hiểu rõ ràng. Những thị trường khác với nguyên tắc định nghĩa rõ ràng cũng là những đối tượng để nghiên cứu, ví dụ thị trường bán đấu giá. 17 Trong mục này tôi xin giới thiệu hai thị trường mà Roth đã nghiên cứu và đưa ra những dẫn chứng cụ thể: thị trường cho những bác sỹ mới ở Mỹ và thị trường y tế địa phương ở Anh. 2.1.1 Thị trường cho những bác sĩ mới ở Mỹ Roth đã nghiên cứu sự phát triển của thị trường ở Mỹ cho những bác sỹ mới (xem [4]). Những sinh viên tốt nghiệp từ những trường Y tại mỹ thường được làm việc như những người cư trú tại các bệnh viện, nơi mà họ được coi như là một lực lượng lao động quan trọng nhất. Những năm đầu của thế kỷ 20, thị trường cho những bác sĩ mới được phân cấp rộng rãi. Trong suốt thập niên 40, việc cạnh tranh để giành được những sinh viên ngành y giữa các bệnh viện tăng lên nhanh chóng, thậm trí họ còn chọn sinh viên trước vài năm sinh viên ra trường. Việc này dẫn đến nhiều hậu quả tiêu cực. Việc thỏa thuận giữa sinh viên và bệnh viện trước khi sinh viên chứng tỏ khả năng của bản thân mình, và thậm chí trước khi họ biết mình sẽ làm việc tốt và chuyên về ngành y khoa nào. Thị trường sẽ hứng chịu sự bế tắc: khi một lời đề nghị bị từ chối, thường sẽ quá muộn để sinh viên có thể đi tìm kiếm một bệnh viên khác cũng như bệnh viện đó sẽ khó khăn trong việc tìm kiếm sinh viên khác để thay thế. Một thị trường sai lầm, bế tắc xảy ra, không đủ thời gian để đưa ra những lời đề nghị mà có thể bảo đảm được lợi ích của cả đôi bên. Để có thể giải quyết việc này, các bệnh viện buộc phải ép sinh viên đưa ra những quyết định của mình mà không cần biết đến họ có thể sẽ có cơ hội làm việc ở những bệnh viện tốt hơn và hợp với chuyên môn của mình hơn. Theo nghiên cứu của Roth, vấn đề này cũng xảy ra như bệnh dịch với nhiều thị trường khác, bao gồm cả cấp nhập cảnh hợp pháp, trường học kinh doanh và thị trường lao động ý tế ở Mỹ, Canada và Anh, những thị trường cho tâm lý học lâm sàng, nha khoa ở Mỹ, thị trường cho những sinh viên tốt nghiệp đại học ở Nhật. Khi mà những hàng hóa không đồng nhất và không tách rời được giao dịch, như là trong những thị trường lao động tay nghề cao ở trên, những lời đề nghị phải được đưa ra với từng cá nhân cụ thể hơn là với thị trường. Vấn đề của việc phối hợp thời gian của những lời đề nghị có thể gây ra một thị trường phân cấp hoàn toàn trở lên tắc nghẽn và tách ra từng, và kết quả là không ổn định. Trong một nghiên cứu năm 1994 (xem 18 [3]) Roth và Xing đã mô tả những thị trường hình thành từ những thất bại đó và giải thích những tìm kiếm mới của họ trong một mô hình lý thuyết. Trong phản ứng tới những sự thất bại của thị trường Mỹ cho những bác sỹ mới, một trung tâm tập trung đã được giới thiệu vào đầu những năm 1950. Cơ quan này ngày nay được gọi là Chương trình Quốc gia về lựa chọn bác sĩ phù hợp (NRMP). Roth đã chỉ ra rằng NRMP kết hợp các bác sĩ và các bệnh viện bằng cách sử dụng một thuật toán về bản chất là tương đương với thuật toán chấp nhận trì hoãn của Gale-Shapley. Roth đã lập luận rằng sự thành công của NRMP là do thực tế thuật toán ổn định. Nếu thuật toán đưa ra kết quả không ổn định, các bác sĩ và những bệnh viện đó sẽ có thể có động cơ để bỏ qua thuật toán bằng cách hình thành sự ghép đôi ưu tiên (một bác sĩ có thể dễ dàng liên lạc với bệnh viên mà cô ta thích để hỏi xem liệu họ có quan tâm tới việc thuê cô ấy hay không). Khi một thị trường được thiết kế thành công, nhiều phần tử được thuyết phục để tham gia, do đó cần tạo một thị trường "dày" với nhiều cơ hội giao dịch hơn. Cách mà trong đó sự thiếu ổn định có thể tạo ra sự không thỏa mãn và làm giảm tỷ lệ tham gia như đã minh họa trong ví dụ. Một thuật toán không ổn định có thể gán sinh viên 1 vào khoa nhi. Nhưng nếu khoa da liễu tìm ra rằng người sinh viên nằm trong tốp đầu mà họ chọn lại được nhận vào khoa mà sinh viên đó không thích bằng khoa da liễu thì, họ có thể đưa ra những lý do chính đáng về sự không bằng lòng đó. Một thuật toán ổn định không cho phép những tình huống này xảy ra (xem [2]). 2.1.2 Thị trường y tế địa phương tại Vương quốc Anh Roth đã nhận ra rằng Thị trường Y tế địa phương tại Anh cũng bị vấn đề tương tự vào những năm 1960 như đã xảy ra tại Mỹ những năm 1940. Mỗi khu vực giới thiệu thuật toán ghép đôi của riêng mình. Một vài nơi ổn định, một vài nơi khác thì không. Đặc biệt, tại Edinburg và Cardiff đã thực hiện thuật toán giống với thuật toán chấp nhận trì hoãn, và đã thành công trong nhiều thập kỷ. Mặt khác, Birmingham, Newcastle và Sheffied đã nhanh chóng bỏ thuật toán không mang lại ổn định cho họ.