# Bài toán hôn nhân bền vững - Thuật toán Gale-Shapley

:::warning
**Lưu ý**: Hôn nhân nam nữ ở đây chỉ ẩn dụ cho các khía cạnh đối lập của vấn đề, một cách cụ thể và dễ hiểu là giữa “cung” và “cầu”. Thuật toán hoàn toàn không thể hiện câu chuyện tình yêu và hôn nhân trong xã hội, vốn là quyền tự do và sự tự nguyện giữa hai cá nhân bất kỳ. Các ví dụ cũng không cổ xúy cho việc sử dụng tình yêu để trục lợi, cũng như các thái độ không đứng đắn trong quan hệ.
:::

## Đặt vấn đề

Chúng ta có tình huống giả định như sau: Mai vì quá cô đơn nên vội vã đồng ý ngay lời cầu hôn của Đoàn. Cuộc hôn nhân của Đoàn và Mai tưởng chừng sẽ êm ấm và kéo dài, cho đến khi Thuận xuất hiện và ngỏ lời tỏ tình với cô. Vì Thuận đẹp trai, học giỏi, con nhà giàu, lại "hợp gu" với Mai hơn Đoàn, nên cặp hôn nhân Đoàn - Mai trở nên không bền vững và rạn nứt.

Bởi lẽ, trong cuộc sống, có rất nhiều vấn đề tương đồng với tình huống hôn nhân ở trên. Lấy ví dụ, việc xét tuyển Đại học - Cao đẳng ở nước ta hiện nay phải giải quyết vấn đề về thí sinh trúng tuyển vào các trường Đại học, sao cho mỗi sinh viên chỉ được trúng tuyển duy nhất một nguyện vọng trong danh sách đăng ký xét tuyển. Để đảm bảo quyền lợi của thí sinh toàn quốc, một thuật toán cần được đưa ra để đảm bảo nhu cầu của tất cả các thí sinh, qua đó hạn chế việc một thí sinh trúng tuyển một lúc nhiều nguyện vọng khác nhau, làm ảnh hưởng quyền lợi học tập của các sinh viên khác.

Khái quát hóa tình huống trên, ta có bài toán tổng quát như sau:

:::info
Cho hai tập hợp gồm $M$ - tập hợp của $n$ nam, và $F$ - tập hợp của $n$ nữ. Gọi $m$ là một phần tử thuộc tập hợp $M$ và $f$ là một phần tử thuộc tập hợp $F$, một cặp $(m,f)\in\mathcal M$ được gọi là một **cặp hôn nhân**, với $\mathcal M\subset M\times F$ là tập hợp các cặp hôn nhân tạo thành từ hai tập $M$ và $F$ (ta gọi đây là một **cuộc hôn nhân hoàn chỉnh**).

Một cặp hôn nhân $(m,f)$ được xem là *bền vững*, nếu **không cùng lúc** xảy ra hai điều kiện sau:
1. Tồn tại một cặp hôn nhân $(m',f')\in\mathcal M$ mà ==$m'$ thích $f$ hơn $f'$ ($f'$ thích $m$ hơn $m'$)== và
2. ==$f$ cũng thích $m'$ hơn $m$ ($m$ cũng thích $f'$ hơn $f$)==.

Bài toán hôn nhân bền vững giải quyết vấn đề như sau: Xác định một cuộc hôn nhân hoàn chỉnh $\mathcal M$ sao cho không tồn tại cặp hôn nhân $(m,f)$ không bền vững. Một cuộc hôn nhân như vậy được gọi là một **cuộc hôn nhân bền vững**.
:::

Để dễ bề hình dung, chúng ta đưa ra ví dụ cụ thể:
Cho hai tập hợp $M=\{m_1,m_2,m_3\}$ và $F=\{f_1,f_2,f_3\}$. Ta có danh sách các "nguyện vọng kết hôn" như sau:

|Nam|Nguyện vọng 1|Nguyện vọng 2|Nguyện vọng 3|
|-|-|-|-|
|$m_1$|$f_1$|$f_3$|$f_2$|
|$m_2$|$f_3$|$f_2$|$f_1$|
|$m_3$|$f_2$|$f_1$|$f_3$|

|Nữ|Nguyện vọng 1|Nguyện vọng 2|Nguyện vọng 3|
|-|-|-|-|
|$f_1$|$m_1$|$m_3$|$m_2$|
|$f_2$|$m_3$|$m_1$|$m_2$|
|$f_3$|$m_1$|$m_2$|$m_3$|

Ta đề xuất cuộc hôn nhân hoàn chỉnh bất kỳ là $\mathcal M=\{(m_1,f_1);(m_2,f_2);(m_3,f_3)\}$.

Theo đó, cặp hôn nhân $(m_2,f_2)$ được xem là không bền vững vì $f_2$ thích $m_3$ hơn $m_2$ và đòng thời $m_3$ cũng thích $f_2$ hơn $f_3$. Vậy cuộc hôn nhân $\mathcal M$ không phải là cuộc hôn nhân bền vững mà chúng ta tìm kiếm.

## Thuật toán Gale-Shapley

Thuật toán được gọi theo tên của nhà kinh tế học David Gale và Lloyd Shapley, những người đã thành công chứng minh mệnh đề: "Với các bên tham gia có cùng số lượng, luôn tồn tại một cách ghép đôi sao cho ta có các cặp đôi bền vững" thông qua một bài nghiên cứu công bố vào năm 1962, và dạng thuật toán giải quyết đã được đề cập đến. Vào năm 1984, giáo sư kinh tế học Alvin E. Roth cho rằng dạng thuật toán tương tự từng được áp dụng vào thập niên 1950 bởi chính phủ Hoa Kỳ, dưới tên gọi "Thuật toán Boston Pool", phục vụ cho việc phân bổ các bác sĩ thực tập về các bệnh viện khác nhau trên khắp cả nước. Năm 2012, Shapley và Roth được vinh danh ở giải thưởng Nobel Kinh tế cho thành tựu trên.

Sau đây là đoạn mã giả hoàn chỉnh của thuật toán Gale Shapley:

:::info
**Đầu vào**: Tập hợp $M$ và $F$ của $n$ nam và nữ, cùng với danh sách nguyện vọng ưu tiên của từng cá nhân.
**Đầu ra**: Cuộc hôn nhân $\mathcal M\subset M\times F$ bền vững.
**Với mọi** $m\in M$ còn độc thân **tiến hành**:
- $m$ chọn $f$ nằm ở đầu danh sách ưu tiên của mình.
- **Nếu** không tồn tại $(m',f)\in\mathcal M$ **thì**:
- Thêm $(m,f)$ vào $\mathcal M$.
- **Nếu không**:
- **Nếu** $f$ thích $m$ hơn $m'$ **thì**:
- $m'$ trở nên độc thân.
- Thêm $(m,f)$ vào $\mathcal M$.
- **Nếu không**:
- Chạy lại vòng lặp với $m$ cùng $f$ nằm ở thứ tự ưu tiên kế tiếp.
- **Kết thúc điều kiện**
- **Kết thúc điều kiện**

**Kết thúc vòng lặp**
:::

**Bài tập ví dụ**: Ta có danh sách nguyện vọng ưu tiên tương ứng với mỗi giới như sau:

|Nam|Nguyện vọng 1|Nguyện vọng 2|Nguyện vọng 3|Nguyện vọng 4|
|-|-|-|-|-|
|Huy|Diệu|Hiền|Nguyệt|Loan|
|Minh|Hiền|Loan|Diệu|Nguyệt|
|Thịnh|Hiền|Loan|Diệu|Nguyệt|
|Thuận|Loan|Diệu|Hiền|Nguyệt|

|Nữ|Nguyện vọng 1|Nguyện vọng 2|Nguyện vọng 3|Nguyện vọng 4|
|-|-|-|-|-|
|Diệu|Minh|Huy|Thuận|Thịnh|
|Hiền|Thịnh|Minh|Thuận|Huy|
|Loan|Thuận|Huy|Minh|Thịnh|
|Nguyệt|Thịnh|Thuận|Huy|Minh|

Chúng ta sẽ tiến hành sử dụng thuật toán Gale-Shapley với sự ưu tiên theo chữ cái đứng trước tương ứng trong bảng chữ cái tiếng Việt:

:::success
|Đối tượng chọn|Đối tượng được chọn|Kết quả|Trạng thái cuộc hôn nhân|
|-|-|-|-|
|Huy|Diệu|Chấp nhận|Huy - Diệu|
|Minh|Hiền|Chấp nhận|Huy - Diệu, Minh - Hiền|
|Thịnh|Hiền|Chấp nhận (Hiền thích Thịnh hơn Minh)|Huy - Diệu, Thịnh - Hiền|
|Thuận|Loan|Chấp nhận|Huy - Diệu, Thịnh - Hiền, Thuận - Loan|
|Minh|Hiền|Từ chối (Hiền không thích Minh bằng Thịnh)|Không đổi|
|Minh|Loan|Từ chối (Loan không thích Minh bằng Thuận)|Không đổi|
|Minh|Diệu|Chấp nhận (Diệu thích Minh hơn Huy)|Minh - Diệu, Thịnh - Hiền, Thuận - Loan|
|Huy|Diệu|Từ chối (Diệu không thích Huy bằng Minh)|Không đổi|
|Huy|Hiền|Từ chối (Hiền không thích Huy bằng Thịnh)|Không đổi|
|Huy|Nguyệt|Chấp nhận|Minh - Diệu, Huy - Nguyệt, Thịnh - Hiền, Thuận - Loan|

Vậy: Cuộc hôn nhân bền vững ta có được là: Minh - Diệu, Huy - Nguyệt, Thịnh - Hiền, Thuận - Loan.
:::

### Các định nghĩa liên quan

:::info
**Đối tượng chọn**: Đối tượng của tập hợp được vòng lặp tiến hành để giải quyết bài toán hôn nhân bền vững. Đối tượng bên còn lại được gọi là **đối tượng được chọn**.
:::

:::info
Thuật toán được gọi là **thuật toán vị nam** nếu đối tượng chọn là nam giới, gọi là **thuật toán vị nữ** nếu đối tượng chọn là nữ giới.
:::

:::info
Cặp ghép được gọi là **cặp ghép hợp lệ** nếu tồn tại một cuộc hôn nhân bền vững bao gồm cặp ghép đó.
:::

## Các tính chất của thuật toán Gale-Shapley

### Tính kết thúc

:::info
Độ phức tạp về thời gian của thuật toán Gale-Shapley là $\mathcal O(n^2)$.
:::

**Chứng minh**:

Vòng lặp có thể chạy hết $n$ nguyện vọng trong danh sách ưu tiên được đưa ra. Vậy vòng lặp phải chạy tối đa $n$ vòng lặp cho một đối tượng chọn, tức độ phức tạp là $\mathcal O(n)$.

Vòng lặp phải lặp qua ít nhất 1 lần mỗi cá nhân trong đối tượng chọn, tức độ phức tạp tương ứng là $\Theta(n)$.

Vậy độ phức tạp của thuật toán là $\mathcal O(n).\Theta(n)=\mathcal O(n^2)$.

### Tính hợp lệ

:::info
Đầu ra của thuật toán Gale-Shapley luôn là một cuộc hôn nhân bền vững.
:::

**Chứng minh** (Phản chứng):

Gọi $\mathcal M\subset M\times F$ là kết quả đầu ra bất kỳ của thuật toán Gale-Shapley sao cho $\mathcal M$ không phải thuật toán hôn nhân bền vững. Điều này có nghĩa là tồn tại một cặp $(m,f)\in\mathcal M$ không bền vững. Vậy có thể xảy ra hai trường hợp sau:

1. **Tồn tại một cặp hôn nhân $(m',f')\in\mathcal M$ mà $m'$ thích $f$ hơn $f'$ và $f$ thích $m'$ hơn $m$**

Nếu $m'$ thích $f$ hơn $f'$, thì trong trường hợp vòng lặp lặp qua $m'$, $m'$ sẽ chọn $f$ trước $f'$, và $f'$ sẽ chấp nhận lời tỏ tình của $m'$ và trả $m$ về trạng thái độc thân ⇒ Trái với giả thiết ban đầu.

2. **Tồn tại một cặp hôn nhân $(m',f')\in\mathcal M$ mà $f'$ thích $m$ hơn $m'$ và $m$ thích $f'$ hơn $f$**

Nếu $m$ thích $f'$ hơn $f$, thì trong trường hợp vòng lặp lặp qua $m$, $m$ sẽ chọn $f'$ trước $f'$, và $f'$ sẽ chấp nhận lời tỏ tình của $m$ trước khi $m$ đến với lựa chọn $f'$ ⇒ Cũng trái với giả thiết ban đầu.

*Kết luận*: Thuật toán Gale-Shapley luôn đảm bảo đầu ra là một cuộc hôn nhân $\mathcal M$ bền vững.

### Định luật 1

:::info
Thuật toán Gale-Shapley thiên vị một giới tính cụ thể luôn trả ra một kết quả duy nhất.
:::

**Chứng minh** (Phản chứng):

Gọi $\mathcal M,\mathcal M'\subset M\times F$ là hai kết quả đầu ra khác nhau của thuật toán Gale-Shapley **vị nam** sao cho với một phần tử nam giới $m\in M$, $(m,f)\in\mathcal M$ và $(m,f')\in\mathcal M'$. Vậy thì, $\exists (m',f)\in\mathcal M'$, đồng nghĩa với việc $f$ thích $m'$ hơn $m$ hoặc $m$ thích $f'$ hơn $f$. Trường hợp $f$ thích $m'$ hơn $m$, cặp đôi $(m,f)$ lẽ ra không được hình thành trong $\mathcal M$ bởi $f$ sẽ từ chối $m$ nếu $m$ ở thứ tự vòng lặp sau $m'$ hoặc sẽ trả $m$ về độc thân nếu $m$ ở thứ tự vòng lặp trước. Trường hợp $m$ thích $f'$ hơn $m$ thì $m$ sẽ lặp $f'$ trước $f$ trong mọi tình huống. Vậy nên giả thiết này không xảy ra.

:::success
**Hệ quả 1**: Sự thay đổi thứ tự của vòng lặp không ảnh hưởng đến kết quả đầu ra của thuật toán Gale-Shapley thiên vị cho một giới tính bất kỳ.
:::

:::success
**Hệ quả 2**: Thuật toán Gale-Shapley chỉ đảm bảo tính công bằng và khách quan cho bên được thiên vị. Nói cách khác, thuật toán không đảm bảo sự công bằng cho tất cả các yếu tố tham gia.
:::

### Định luật 2

:::info
Có thể tồn tại nhiều hơn một cuộc hôn nhân bền vững cho một tình huống được đưa ra.
:::

|Nam|Nguyện vọng 1|Nguyện vọng 2|Nguyện vọng 3|
|-|-|-|-|
|X|A|B|C|
|Y|B|A|C|
|Z|A|B|C|

|Nữ|Nguyện vọng 1|Nguyện vọng 2|Nguyện vọng 3|
|-|-|-|-|
|A|Y|X|Z|
|B|X|Y|Z|
|C|X|Y|Z|

Sử dụng thuật toán Gale-Shapley vị nam, ta có kết quả: $\mathcal M_M=\{(X,A); (Y,B); (Z,C)\}$.

Sử dụng thuật toán Gale-Shapley vị nữ, ta có kết quả: $\mathcal M_F=\{(X,B); (Y,A); (Z,C)\}$.

Và ta có $\mathcal M_M\neq \mathcal M_F$.

:::success
**Hệ quả 1**: Một tình huống hôn nhân chỉ có tối đa 2 cuộc hôn nhân bền vững khác nhau ở đầu ra.
:::

:::success
**Hệ quả 2**: Nếu thuật toán vị nam và vị nữ cùng trả ra một kết quả đầu ra, đó được xem là cuộc hôn nhân bền vững duy nhất giải quyết tình huống hôn nhân.
:::

Hai hệ quả trên đều được suy ra từ hệ quả 1 của định luật 1.

## Ứng dụng: Giải quyết vấn đề tuyển sinh Đại học

Quay trở lại tình huống thực tiễn được nêu ở đoạn đầu tiên, bộ lọc ảo của Bộ Giáo dục và Đào tạo cần phải giải quyết vấn đề tuyển sinh Đại học trong cả nước, làm sao cho đảm bảo công bằng về quyền lợi cho tất cả các thí sinh ứng tuyển trong cả nước: mỗi người chỉ được trúng tuyển một nguyện vọng.

Để đơn giản hóa vấn đề, ta sẽ giả định đầu vào như sau:
- Mỗi nguyện vọng đều có số chỉ tiêu nhất định (được phép tuyển sinh quá chỉ tiêu trong trường hợp có các thí sinh bằng điểm nhau).
- Mỗi thí sinh có điểm số thi nhất định để các nguyện vọng xếp hạng. Với số thí sinh hằng năm thường rơi vào con số lớn hơn 500 ngàn người thì việc có thí sinh trùng điểm nhau là tất yếu sẽ xảy ra.
- Các nguyện vọng xếp hạng thí sinh theo điểm số, bên cạnh đó thí sinh xếp hạng các nguyện vọng theo thứ tự ưu tiên.

:::warning
Tình huống thực tiễn có phần khác với giả thiết ban đầu của thuật toán nguyên thủy là số nguyện vọng trong danh sách ưu tiên không giống nhau giữa các thí sinh, cũng như số nguyện vọng và số thí sinh chắc chắn không ngang nhau.

Vì vậy, sự ưu tiên trong việc lựa chọn thuật toán nhắm đến việc các nguyện vọng lấy vừa đủ chỉ tiêu của mình, và chấp nhận việc có các thí sinh không trúng tuyển nguyện vọng nào hoặc có các nguyện vọng tuyển sinh không đủ chỉ tiêu sau cùng.
:::

Ở đây chúng ta sẽ sử dụng thuật toán thiên vị nguyện vọng để giải quyết vấn đề trên (có đôi chút chỉnh sửa để phù hợp).

:::info
**Đầu vào**: Danh sách nguyện vọng và danh sách thí sinh
**Đầu ra**: Các điểm chuẩn đối với từng nguyện vọng
**Biến số**: Điểm chuẩn thấp nhất và số lượng trúng tuyển đối với từng nguyện vọng một.
**Với mọi** nguyện vọng xét tuyển chưa đủ chỉ tiêu nhưng còn thí sinh hoặc có thí sinh kế tiếp bằng số điểm với điểm chuẩn **tiến hành**:
- Nguyện vọng xem xét thí sinh kế tiếp.
- **Nếu** thí sinh chưa trúng tuyển **thì**:
- Tiếp nhận thí sinh và cập nhật số lượng trúng tuyển
- Cập nhật giá trị điểm chuẩn thấp nhất.
- **Nếu không**:
- **Nếu** nguyện vọng này được ưu thích hơn nguyện vọng trước **thì**:
- Loại bỏ thí sinh khỏi danh sách trúng tuyển của nguyện vọng trước.
- Tiếp nhận thí sinh và cập nhật số lượng trúng tuyển.
- Cập nhật giá trị điểm chuẩn thấp nhất.
- **Nếu không**:
- Loại bỏ thí sinh khỏi danh sách xem xét.
- **Kết thúc điều kiện**
- **Kết thúc điều kiện**

**Kết thúc vòng lặp**
:::

## Tham khảo

1. Tài liệu học học phần UL3IN025 - IA et Jeux của trường Đại học Sorbonne, Paris bởi Phó Giáo sư Nawal B.
2. [Đăng D. - *Bài toán Hôn nhân bền vững - từ tìm kiếm real love đến tuyển sinh đại học*](https://viblo.asia/p/bai-toan-hon-nhan-ben-vung-tu-tim-kiem-real-love-den-tuyen-sinh-dai-hoc-1VgZvMerKAw)
3. Wikipedia