chương 1 đã trình bày tổng quan một số vấn đề liên quan tới đồ thị vô hướng, đồ thị hai phía. Đây là những kiến thức cơ sở chuẩn bị cho nhưng nghiên cứu tiếp theo của luận văn này. Phần đầu của chương giới thiệu những khái niệm cơ bản về đồ thị vàđồ thị hai phía, một số dạngđồ thị. Tiếp theo là các bài toán ghép đôi trên đồ thị hai phía.
Sau đó, trình bày về thuật toán ghép đôi với thông tin đầy đủ, áp dụng thuật toán ghép đôi với bài toán hôn nhân bền vững, thuật toán này rất quan trọng trong phần phân tích tính không đầy đủ của chương sau. 17 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 2. GHÉP ĐÔI VỚI THÔNG TIN KHÔNG ĐẦY ĐỦ Trong chương này, sẽ trình bày các khái niệm của thông tin không đầy đủ trong bài toán ghép đôi, tiếp theo chúng tôi tập trung chính vào tính ổn định cho các vấn đề ghép đôi với điều kiện thông tin không đầy đủ. Trong điều kiện chung, các kết quả ổn định với thông tin không đầy đủ tồn tại trong môi trường thông tin không được cân xứng [16].1 Giới thiệu bài toán Ghép đôi với thông tin không đầy đủ là một bài toán ghép đôi sử dụng thuật toán Gale-Shapley để giải quyết.
Cho hai tập rời nhauX và Y. Mỗi phần tử của X có thể ghép với một số phần tử của Y. Tìm cách ghép mỗi phần tử của X với một số phần tử của Y sao cho số cặp ghép là lớn nhất. Trong bài toán ghép đôi này thông tin không đầy đủ bao gồm các dạng sau: - Lực lượng ghép đôi hai bên của hai tậpX và Ykhông bằng nhau - Lực lượng ghép đôi hai bên của hai tậpX và Y bằng nhau nhưng thông tin lựa chọn giữa các phần tử trong X và Ykhông đầy đủ và thiếu thông tin.
- Lực lượng ghép đôi hai bên X và Ykhông bằng nhau và thông tin lựa chọn giữa các phần tử trong X và Ykhông đầy đủ và thiếu thông tin. Hiện nay có khá nhiều ứng dụng mô hình ghép đôi được giới thiệu bởi Gale - Shapley (1962) và Shapley-Shubik (1971)([8], [17]) vào phân tích thị trường với hai bên không đồng nhất, nghiên cứu các vấn đề như ghép đôi giữa sinh viên với trường đại học, vợ với chồng, người lao động với công ty. Phân tích điển hình trong luận văn này giả định rằng các phần tử có đầy đủ thông tin, và kiểm chứng, xem xétkết quả ổn đinh của các cặp ghép này. Cặp ghép dự kiến được coi là ổn định khi ghép đôi từng công ty với một người lao động dựa trên cùng một tiêu chí ghép (ví dụ như tiêu chí về số tiền thù lao) sao cho không có một cặp đôi không cân xứng nào kết hợp với nhau để tạo ra mức thù lao chấp nhận được và làm tăng lợi ích của cả hai bên.
18 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Giả định thông tin đầy đủ làm cho việc phân tích dễ xử lý nhưng không kém phần chặt chẽ. Bài luận kiểm định các mô hình ghép đôi trong đó các phần tử ở một bên thị trường sẽ không thể quan sát được các đặc tính của các phần tử khác ở phía bên kia thị trường, việc này dẫn đến các câu hỏi: Ý nghĩa của một cặp ghép ổn định trong điều kiện thông tin không đầy đủ là gì? Đâu là các đặc tính của các cặp ghép ổn định? Trong chừng mực nào đó việc cung cấp thông tin không đầy đủ trong vấn đề ghép đôi làm thay đổi kết quả tương ứng như thế nào? 2.1 Các đặc trưng của bài toán Coi như mỗi người lao động và công ty trong bài toán ghép đôi người lao động- công ty có những phẩm chất riêng biệt và mỗi cặp ghép phù hợp tạo ra giá trị thặng dư giúp tăng lợi ích của cả hai đối tượng tham gia. Giả sử rằng các giá trị của các công ty thì dễ dàng nhận biết còn giá trị của người lao động thì không. Mỗi công ty biết rõ chất lượng của người lao động mà họ được ghép cùng, biết thù lao của các nhóm ghép khác nhưng lại không biết chất lượng của người lao động trong các nhóm này.
Trong mô hình thông tin đầy đủ, có thể nói rằng kết hợp được coi là không ổn định nếu như có một cặp đôi không cân xứng kết hợp với nhau tạo ra sự sai lệch và làm tăng lợi ích cho nhau. Nhưng làm thế nào mà các công ty ước tính được mức thù lao hợp lý khi có kết hợp sai lệch với người lao động không rõ chất lượng. Họ nên dùng cơ sở nào để tính toán mức thù lao kì vọng? Chúng tôi bắt đầu bằng việc nhận diện sự tin tưởng mà công ty có thể loại trừ, cung cấp cho họ kiến thức về sự phân phối và giả thiết rằng sự phân phối đó không bị chặn. Đặc biệt, công ty có thể tạo ra các suy luận về các kiểu người lao động mà họ muốn chặn từ các cặp ghép khuyết thiếu.
Từ suy luận này lại suy ra nhiều suy luận khác. Chúng tôi dựng lên một quy trình khởi tạo niềm tin có tính lặp lại, hợp lý hóa, và ghi nhận tất cả các kết luận mà công ty có thể làm. Nhìn chung, điều đó tạo ra một bộ niềm tin hợp lý cho công ty. Sau đó chúng tôi lại thấy phân bổ không đạt ổn định nếu như có những cặp ghép người lao động – công ty tạo ra lợi ích cho một bên.
19 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Phần tiếp chúng tôi muốn phân biệt giữa góc nhìn của công ty và nhà phân tích. công ty có một số niềm tin riêng, xuất phát từ một hệ các niềm tin đang tin cậy, các niềm tin này có thể là thành phần tham gia vào việc tạo nên các cản trở trong ghép đôi, khi mà chính những niềm tin này đem lại cho công ty một mức hời kỳ vọng. Tuy vậy, chẳng có một cấu trúc kinh tế hay một phân phối các ứng viên ổn định nào có thể cung cấp cho nhà phân tích những dẫn chứng đâu là những niềm tin hợp lý của công ty. Mục đích của chúng tôi là xác định các điều kiện cần của tính ổn định chỉ dựa trên 2 yếu tố duy duy nhất là cấu trúc kinh tế và giả thuyết về tính ổn định, và do đó chúng tôi chỉ bỏ qua một phân phối nếu nó chắc chắn chặn thành công [16].2 Điều kiện cần giải bài toán Chúng tôi không đề cập đến việc làm thế nào để tạo ra các kết quả ổn định.
Chúng tôi coi khái niệm sự ổn định của thông tin không đầy đủ như được áp dụng để nhận diện một bộ khả thi các kết quả thông tin không đầy đủ, không phân biệt chúng được tạo ra như nào, giống như vô số cách mà nghiên cứu để trực tiếp xác định một bộ kết quả khả thi. Việc xác định kết quả ổn định nào sẽ xuất hiện đòi hỏi phải có thêm thông tin về thể chế giống như việc xác định kết quả nào sẽ được thực hiện cần thông tin về cơ chế gián tiếp thực tế. Phương pháp tiếp cận sự ổn định của thông tin không đầy đủ này giúp nhắc lại nghiên cứu về lõi được hợp thức hóa bởi Gillies (1959) [10] và được sử dụng để xác định thí sinh cho sự ổn định trước quy trình được xác định chắc chắn tạo ra kết quả lõi (Perry và Reny 1994) [14]. Ngược lại, khái niệm tính ổn định và thuật toán tập trung để tính toán các phân phối ổn định cũng đồng thời xuất hiện trong nghiên cứu ghép đôi thông tin đầy đủ của Gale và Shapley (1962) [8].
Có thể tưởng tượng là quá trình phần cấp sẽ tạo ra các kết quả ổn định trong môi trường thông tin đầy đủ - Các phần tử chưa được ghép đôi lại tiếp tục ngẫu nhiên gặp nhau rồi đưa ra đề nghị, quá trình ghép đôi dừng lại khi không có có một cặp ghép không cân xứng nào có thể cải thiện điều kiện có nó thông qua ghép đôi. Tuy nhiên năm 2014 Lauren và Nöldeke [18] lại chứng minh rằng chỉ trong môi trường các giả định nghiêm ngặt thì quá trình trên mới tạo ra được kết quả ổn định. Trong điều kiện thông tin không đầy 20 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com đủ các kết quả của quá trình ghép đôi thậm chí còn ít rõ ràng hơn bởi vì các phần tử đưa ra kết luận từ các kết quả trung gian trong quá trình ghép đôi, vì vậy mà tập hợp các kết quả thông tin không đầy đủ ổn định lại trở thành mục tiêu động. Việc cung cấp nền tảng phi tập trung cho ghép đôi ổn định thông tin đầy đủ và không đầy đủ là một vấn đề rất mở và thú vị.
Quan niệm của chúng ta về sự ổn định ngăn chặn được những sai lệch xảy ra với các cặp ghép sinh lời, nhưng lại không tính đến những sai lệch của một nhóm tác nhân lớn hơn. Trong điều kiện thông tin đầy đủ, các cặp ghép có thể chặn bất kì kết quả nào đã bị chặn bởi một cặp chặn lớn hơn do đó có thể ngăn chặn việc hy sinh các cặp ổn định không có tính phổ quát. Điều này cũng không nhất thiết phải áp dụng cho trường hợp thông tin không đầy đủ. Với giả định của chúng tôi về một cặp ghép được đề xuất, các công ty biết chất lượng của lao động họ được ghép đôi, một liên minh nhiều công ty có khả năng có nhiều thông tin hơn một cặp tiềm năng đơn lẻ, tiềm năng bởi vì mỗi công ty đều phải chi tiết quy trình của họ và họ có thể trao đổi cho nhau, hòng thu về phần lợi, và để cụ thể hóa các thông tin trong đề nghị của họ.
Trong nhiều trường hợp, chúng tôi thấy nên sớm chặn các cặp ghép liên minh. Chúng ta nhìn đơn thuần là một lao động tìm kiếm một công việc hay một công ty đang có chèo lái một lao động của họ, nhưng cũng ko loại bỏ được trường hợp các công ty liên kết với nhau để phân phối lại lực lượng lao động giữa họ. Thêm nữa, nếu vẫn cho phép các cặp chỉ được sai lệch để tránh những khó khăn trong chia sẻ thông tin thì sẽ dẫn đến các liên minh lớn hơn nữa.2 Phát biểu bài toán, các khái niệm 2.1 Đặt bài toán Trước hết tổng hợp về mô hình ghép đôi với thông tin đầy đủ được nghiên cứu bởi Shapley, Shubik (1971)[17] và Crawford, Knoer (1981) [7]. Cho hai tập rời nhau X và Y Một tập các người lao động hữu hạn X, với mỗi người lao động có ký hiệu là i ∈ X.