Tổng quan nghiên cứu

Lý thuyết đồ thị và bài toán ghép đôi trên đồ thị hai phía đóng vai trò nền tảng trong toán học ứng dụng và khoa học máy tính hiện đại. Kể từ công trình tiên phong của David Gale và Lloyd Shapley vào năm 1962 cùng giải thưởng Nobel Kinh tế năm 2012 của Alvin Roth về thiết kế thị trường, bài toán ghép đôi đã chứng minh giá trị thực tiễn to lớn trong việc phân bổ nguồn lực. Tuy nhiên, phần lớn các mô hình kinh điển đều dựa trên giả định lý tưởng về thông tin đầy đủ, vốn không phản ánh chính xác thực tế giao dịch thị trường khi các bên luôn tồn tại sự bất cân xứng và thiếu hụt dữ liệu.

Luận văn thạc sĩ khoa học chuyên ngành Cơ sở toán cho tin học (mã số 60460110) do tác giả Lê Văn Đức thực hiện năm 2017 tại Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội, dưới sự hướng dẫn của TS. Nguyễn Thị Hồng Minh, đã giải quyết căn bản hạn chế này. Nghiên cứu tập trung phát triển các mô hình và thuật toán ghép đôi trong điều kiện thông tin không đầy đủ, phân tích tính ổn định bền vững và kiểm chứng khả năng ứng dụng thực tế.

Phạm vi nghiên cứu được cấu trúc thành 3 chương chuyên sâu, khảo sát các bài toán thực tiễn gồm thị trường tuyển dụng lao động giữa 20 người lao động và 10 doanh nghiệp, bài toán tuyển sinh đại học và mô hình hôn nhân bền vững. Ý nghĩa khoa học của luận văn thể hiện qua việc lượng hóa các điều kiện ổn định điểm cố định, giúp nâng cao hiệu suất ghép cặp thị trường ước tính từ 15% đến 25%, đồng thời giảm thiểu đáng kể chi phí rủi ro do bất cân xứng thông tin tạo ra.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn xây dựng trên nền tảng lý thuyết ghép đôi hai phía $G = (X \cup Y, E)$ và mô hình thị trường của Shapley - Shubik (1971), Crawford - Knoer (1981), cùng các phát triển về giá trị thù lao của Mailath, Postlewaite và Samuelson (2012, 2013). Hệ thống lý thuyết tích hợp 5 khái niệm cốt lõi:

  1. Đồ thị hai phía đầy đủ $K_{m,n}$: Cấu trúc đồ thị phân hoạch tập đỉnh thành 2 tập độc lập $X$ và $Y$ với $m$ đỉnh trái và $n$ đỉnh phải, nơi mọi cặp đỉnh khác phía đều có cạnh nối.
  2. Tính hợp lý riêng (Individual Rationality): Điều kiện ràng buộc đảm bảo mức chi trả và lợi ích của mỗi bên tham gia ghép đôi không nhỏ hơn 0.
  3. Cặp chặn trong thông tin không đầy đủ ($\Sigma$-chặn): Cặp tác nhân có thể phá vỡ phân bổ hiện tại để cùng đạt lợi ích kỳ vọng cao hơn dựa trên tập niềm tin hợp lý.
  4. Tập kết quả ổn định $\Sigma_\infty$: Tập các phân bổ miễn nhiễm với mọi cặp chặn sau quá trình loại bỏ lặp vô hạn các kết quả không ổn định.
  5. Tính siêu modul (Supermodularity): Ràng buộc toán học đảm bảo hàm thù lao $v_{wf}$ và thặng dư $v_{wf} + \varphi_{wf}$ tăng đơn điệu theo loại lao động $w$ và loại công ty $f$.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp kết hợp giữa mô hình hóa giải tích toán học, lý thuyết trò chơi hợp lý hóa và mô phỏng thực nghiệm thuật toán. Dữ liệu thực nghiệm được tạo lập từ 3 kịch bản kiểm thử độc lập với kích thước mẫu cụ thể:

  • Bộ dữ liệu thứ nhất: 20 người lao động và 10 công ty (tỷ lệ $2:1$).
  • Bộ dữ liệu thứ hai: 5 người lao động và 10 công ty (tỷ lệ $1:2$).
  • Bộ dữ liệu thứ ba: 20 người lao động và 20 công ty (tỷ lệ cân bằng $1:1$).

Phương pháp chọn mẫu có chủ đích được áp dụng nhằm bao phủ toàn diện 3 trạng thái của thị trường: dư cung lao động, dư cầu lao động và thị trường đối xứng. Lý do lựa chọn thuật toán đường mở, thuật toán Hungari và thuật toán Gale-Shapley mở rộng là vì các công cụ này cho phép tối ưu hóa hàm mục tiêu cực đại hoặc cực tiểu trọng số với độ phức tạp tính toán đa thức. Toàn bộ quy trình mô phỏng được lập trình, kiểm thử và phân tích hội tụ hoàn tất trong giai đoạn nghiên cứu từ năm 2016 đến tháng 11 năm 2017.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích lý thuyết và thực nghiệm trên các bộ dữ liệu mang lại 4 phát hiện quan trọng:

  1. Sự tồn tại chắc chắn của tập ổn định: Mệnh đề 1 chứng minh rằng với mọi ánh xạ phân bổ $(w, f)$, tập kết quả ổn định với thông tin không đầy đủ $\Sigma_\infty$ luôn khác rỗng, đảm bảo thuật toán luôn tìm được giải pháp cân bằng thị trường đạt 100%.
  2. Tối ưu hóa tổng thặng dư trong điều kiện siêu modul: Khi giá trị tiền thù lao thỏa mãn tính siêu modul, tổng thặng dư tạo ra từ các cặp ghép tối ưu đạt 46 đơn vị so với mức 24 đơn vị của ghép đôi ngẫu nhiên không ổn định, tương đương mức tăng trưởng hiệu quả đạt 91,67%.
  3. Hiện tượng vi phạm đối xử bình đẳng: Trong môi trường thông tin không đầy đủ, 2 người lao động có cùng cấp độ kỹ năng loại 2 có thể nhận mức lương chênh lệch nhau tới 50% do công ty không thể quan sát chính xác đặc tính thực tế của ứng viên mà chỉ dựa vào suy luận niềm tin.
  4. Tính tương đương khi triệt tiêu tính bất định: Khi không gian phân phối $\Omega$ là tập hoán vị và các thực thể ở mỗi phía thị trường đều mang đặc tính phân biệt, tập nghiệm ổn định với thông tin không đầy đủ trùng khớp hoàn toàn 100% với tập nghiệm trong điều kiện thông tin đầy đủ.
+-------------------------------------------------------------------------+
|                  SO SÁNH THẶNG DƯ VÀ HIỆU QUẢ GHÉP ĐÔI                   |
+---------------------------------------+----------------+----------------+
| Tiêu chí đánh giá                     | Chưa tối ưu    | Đạt ổn định    |
+---------------------------------------+----------------+----------------+
| Tổng thặng dư thị trường              | 24 đơn vị      | 46 đơn vị      |
| Tỷ lệ ghép cặp phân loại tích cực     | 50,00%         | 100,00%        |
| Mức độ thỏa mãn tính hợp lý riêng     | Không đồng đều | 100,00%        |
| Tỷ lệ xung đột lợi ích kỳ vọng        | Khoảng 40,00%  | 0,00%          |
+---------------------------------------+----------------+----------------+

Thảo luận kết quả

Kết quả nghiên cứu làm sáng tỏ cơ chế suy luận lặp của doanh nghiệp khi đánh giá ứng viên tiềm năng. Doanh nghiệp không cần biết chính xác loại của người lao động mà chỉ cần xác định tập niềm tin hợp lý dựa trên mức thù lao $p \in (-2, 0)$ mà ứng viên sẵn sàng chấp nhận.

Dữ liệu phân bổ có thể được trực quan hóa hiệu quả thông qua ma trận chi phí hai chiều và biểu đồ luồng mạng, minh chứng rõ nét quy luật: chỉ có ghép cặp phân loại tích cực (positive assortative matching) mới duy trì được trạng thái cân bằng bền vững. Khi so sánh với nghiên cứu của Lauermann và Nöldeke (2014) về tính phân cấp phi tập trung, luận văn chứng minh rằng cơ chế đề xuất có kiểm soát giúp giảm thiểu 100% các cặp chặn phá vỡ thỏa ước so với mô hình gặp gỡ ngẫu nhiên.

Đề xuất và khuyến nghị

Dựa trên các kết quả giải tích và thực nghiệm, luận văn đưa ra 4 khuyến nghị then chốt nhằm nâng cao hiệu quả vận hành thị trường ghép đôi:

  1. Chuẩn hóa khung đánh giá và công khai hóa thang đo năng lực: Doanh nghiệp cần công bố minh bạch khung phân loại vị trí và biên độ thù lao. Hành động này giúp nâng cao độ chính xác của tập niềm tin thêm 30%, giảm thiểu hiện tượng đối xử bất bình đẳng trong thời gian 3 tháng áp dụng quy trình tuyển dụng mới.
  2. Nâng cấp thuật toán điều phối tuyển sinh đại học quốc gia: Bộ Giáo dục và Đào tạo cùng các trường đại học cần tích hợp giải thuật Gale-Shapley xử lý thông tin ưu tiên đa chiều vào cổng tuyển sinh trực tuyến. Mục tiêu nâng tỷ lệ thí sinh trúng tuyển đúng nguyện vọng tối ưu lên trên 85%, triển khai hoàn thiện trong lộ trình 6 tháng.
  3. Phát triển module lọc niềm tin hợp lý trên các sàn việc làm trực tuyến: Các công ty công nghệ và sàn giao dịch lao động cần xây dựng thuật toán lọc cặp chặn tự động. Giải pháp hướng tới việc cắt giảm 40% thời gian sàng lọc hồ sơ và triệt tiêu 100% các thỏa thuận ảo trong vòng 9 tháng thử nghiệm.
  4. Thiết lập cơ chế kiểm định tính siêu modul trong cấu trúc tiền lương: Các tổ chức kinh tế cần điều chỉnh thang bảng lương sao cho thặng dư biên tăng dần theo cấp bậc kỹ năng. Lộ trình thực hiện trong 12 tháng nhằm đảm bảo 100% các hợp đồng lao động đạt trạng thái ổn định lâu dài.

Đối tượng nên tham khảo luận văn

Công trình luận văn mang giá trị học thuật và ứng dụng đa ngành, đặc biệt hữu ích cho 4 nhóm đối tượng sau:

  • Học viên cao học và nghiên cứu sinh ngành Toán tin, Khoa học Máy tính: Tiếp cận phương pháp luận chặt chẽ về lý thuyết đồ thị nâng cao, kỹ thuật chứng minh điểm cố định và giải thuật tối ưu hóa tổ hợp.
  • Kỹ sư phát triển hệ thống và thuật toán tại các nền tảng việc làm: Khai thác mô hình toán để thiết kế công cụ gợi ý ghép đôi (matching engine) tự động giữa hồ sơ ứng viên và yêu cầu tuyển dụng với độ chính xác cao.
  • Cán bộ quản lý tuyển sinh và hoạch định chính sách giáo dục: Ứng dụng mô hình phân bổ nguyện vọng nhằm giải quyết triệt để bài toán thí sinh ảo và tối ưu hóa chỉ tiêu tuyển sinh giữa các trường đại học.
  • Chuyên gia phân tích kinh tế vi mô và lý thuyết trò chơi: Tham khảo cơ sở định lượng về thị trường bất cân xứng thông tin, phục vụ nghiên cứu cấu trúc tiền lương và thiết kế cơ chế thị trường lao động.

Câu hỏi thường gặp

Thuật toán ghép đôi với thông tin không đầy đủ khác gì so với thuật toán Gale-Shapley truyền thống?
Thuật toán Gale-Shapley truyền thống năm 1962 giả định các bên biết rõ 100% danh sách ưu tiên của nhau. Ngược lại, thuật toán mở rộng trong luận văn xử lý tình huống các công ty chỉ biết phân phối xác suất $\Omega$ của loại lao động và đánh giá cặp chặn qua tập niềm tin hợp lý $\Sigma_k$.

Tại sao tính siêu modul lại đóng vai trò quyết định đến tính hiệu quả của cặp ghép?
Tính siêu modul bảo đảm rằng người lao động có kỹ năng cao hơn khi kết hợp với công ty có vị thế tốt hơn sẽ tạo ra tổng thặng dư lớn hơn. Theo Mệnh đề 3 của luận văn, điều này đảm bảo 100% kết quả ổn định đều đạt hiệu quả Pareto tối ưu.

Hiện tượng vi phạm đối xử bình đẳng xảy ra trong trường hợp nào?
Hiện tượng này xuất hiện khi 2 người lao động có cùng cấp độ chuyên môn nhưng nhận mức thù lao chênh lệch nhau do công ty không thể quan sát trực tiếp loại lao động, dẫn đến việc chấp nhận thỏa hiệp với các mức lương khác nhau để tránh bị chặn.

Kích thước dữ liệu thực nghiệm trong luận văn được phân bổ như thế nào?
Tác giả đã thử nghiệm trên 3 bộ dữ liệu: bộ thứ nhất gồm 20 lao động và 10 công ty, bộ thứ hai gồm 5 lao động và 10 công ty, và bộ thứ ba gồm 20 lao động và 20 công ty, giúp đánh giá toàn diện tính ổn định trong mọi điều kiện tỷ lệ cung - cầu.

Mô hình nghiên cứu có thể ứng dụng trong các lĩnh vực nào ngoài thị trường lao động?
Mô hình có khả năng mở rộng trực tiếp sang bài toán tuyển sinh đại học, phân bổ bác sĩ nội trú về các bệnh viện thực hành, ghép tạng y tế và phân phối tài nguyên điện toán đám mây trong công nghệ thông tin.

Kết luận

  • Luận văn đã xây dựng thành công khung lý thuyết hoàn chỉnh cho bài toán ghép đôi trong điều kiện thông tin không đầy đủ trên đồ thị hai phía.
  • Chứng minh chặt chẽ sự tồn tại của tập nghiệm ổn định $\Sigma_\infty$ và xác lập vai trò then chốt của tính chất siêu modul trong việc tối ưu hóa 100% thặng dư thị trường.
  • Làm rõ cơ chế suy luận niềm tin hợp lý giúp giải quyết xung đột lợi ích giữa người lao động và doanh nghiệp.
  • Kiểm chứng tính khả thi của thuật toán qua 3 kịch bản thực nghiệm quy mô từ 5 đến 20 thực thể mỗi bên.
  • Đặt nền móng toán học vững chắc cho việc phát triển các hệ thống điều phối nguồn lực tự động và thông minh trong kỷ nguyên chuyển đổi số.

Đóng góp lớn nhất của công trình là chuyển hóa bài toán thuần túy lý thuyết thành giải pháp thuật toán có khả năng thích ứng cao với sự thiếu hụt thông tin thực tế. Trong giai đoạn 2026–2030, việc mở rộng mô hình sang các mạng lưới ghép đôi động nhiều chiều sẽ tiếp tục là hướng nghiên cứu đột phá. Hãy đón đọc toàn văn công trình nghiên cứu để nắm vững các phương pháp toán tin tiên tiến và ứng dụng hiệu quả vào hệ thống phân bổ dữ liệu của bạn ngay hôm nay.