Gale Array là gì
Deferred-Acceptance Algorithm (DAA - thuật toán chấp nhận trì hoãn) được đề xuất bởi David Gale và Lloyd Shapley nhằm giải quyết bài toán hôn nhân bền vững. Về sau những đóng góp lý thuyết về tính ổn định lời giải bài toán hôn nhân bền vững của Gale & Shapley và những nổ lực ứng dụng thực tiễn của Alvin Roth mang đến giải Nobel kinh tế học 2012. Show Trở lại vào năm 1962, khi hai nhà toán kinh tế học David Gale và Lloyd Shapley đặt ra câu hỏi: Liệu có thể thiết kế một quy trình tuyển sinh đại học, hoặc một quy trình tuyển dụng, sao cho các bên hợp tác tham gia trong một thị trường cung cầu hay không?. Bài toán này như một mô hình lý thuyết trò chơi có hợp tác, các bên tham gia hợp tác để tối đa lợi ích toàn cục. Hãy hình dung bài toán sau đây, việc tìm được việc làm mình yêu thích, việc tuyển được nhân viên tiềm năng là một bài toán cung cầu. Vấn đề nhân sự luôn là một bài toán hóc búa đối với nhà tuyển dụng. Hầu hết mọi công ty đều có chế độ thử việc, việc này nhằm giảm thiểu rủi ro tuyển người không phù hợp. Tuy nhiên hãy tưởng tượng một viễn cảnh sau đây xảy ra:
Thị trường lao động rơi vào mất kiểm soát, dường như trong viễn cảnh trên, cả ứng cử viên và nhà tuyển dụng đều không mấy vui vẻ, mọi thứ cứ trong tình trạng hỗn loạn. Trong một môi trường kinh tế bất ổn định như thế, việc tạo ra giá trị cho xã hội sẽ mất nhiều thời gian hơn, đó là một sự lãng phí về kinh tế. Trước những năm 1950, viễn cảnh trên không phải là ít, đặc biệt là trong môi trường tuyển dụng bác sĩ của các bệnh viện ở Mỹ. Mỗi bệnh viện đều mong muốn tuyển được bác sĩ giỏi:
Một thị trường lao động như thế, ắt hẳn sẽ không hiệu quả, quá nhiều biện pháp tiêu cực đầy máy móc được áp dụng. Nó là nguồn cảm hứng của bài toán mà chúng ta muốn giải quyết! 1. Phát biểu bài toán hôn nhân bền vữngĐể tiện cho việc phát biểu bài toán. Từ phần này trở về sau chúng ta sẽ phát biểu bài toán dưới dạng bài toán hôn nhân bền vững (Stable marriage problem). Giả sử có $n$ cặp nam và nữ, một cách rất tự nhiên, hôn nhân thì phải phù hợp, mà phù hợp lại phải dựa trên những quan điểm cá nhân. Mỗi người lại có những tiêu chí đánh giá khác nhau, không thể đề ra hàng loạt tiêu chí và bắt người khác đánh giá được. Tuy nhiên quy cho cùng những tiêu chí đánh giá đó có thể đưa về một dạng thông tin hữu ích hơn, danh sách xếp hạng yêu thích! Hôn nhân là một quan hệ hai ngôi giữa một nam và một nữ, bền vững là một khái niệm tương đối, trong bài toán này bền vững có nghĩa là yêu nhau mà khó lòng bỏ nhau được. Hãy xét ví dụ sau đây để hiểu rõ hơn: Hai cặp hôn nhân $\{ (m, w), (m, w) \}$ được gọi là không bền vững. Hiểu một cách nôm na hôn nhân không bền vững nghĩa là hai cặp hôn nhân có xu hướng rạn nứt bởi vì tồn tại một cặp không phải tình nhân nhưng họ yêu nhau hơn chính nhân tình của họ. Nói cách khác, $w$ kết hôn với $m$ nhưng lại thích $m$ hơn $m$, $m$ kết hôn với $w$ nhưng lại thích $w$ hơn $w$. Nếu như việc này xuất phát từ một phía thì chẳng sao cả, tất cả chỉ là trồng cây si mà thôi nhưng khi nó xuất phát từ hai phía hướng về nhau thì rõ ràng đây là hôn nhân không bền vững. Giả định rằng hai bên cung cấp thông tin cho chúng ta, mỗi người tham gia sẽ có một danh sách xếp hạng yêu thích. Để tiện cho việc giải bài toán, chúng ta phát biểu bài toán dưới dạng: Mong muốn xây dựng được một thuật toán: Đầu vào - INPUT:
Đầu ra - OUTPUT:
$$ |S| =n \\ \forall m \in M, \exists w \in W, (m,w) \in S \\ \forall w \in W, \exists m \in M, (m,w) \in S \\ \neg \exists_{(m, w) \notin S} \left( (m, w) \in S \land (m, w) \in S \land \left( P_{m}(w) < P_{m}(w) \right) \land \left( P_{w}(m) < P_{w}(m) \right) \right) $$ Nhìn có vẻ dài dòng nhưng nó đảm bảo chúng ta cùng hiểu một cách phát biểu như nhau. 2. Thuật toán chấp nhận trì hoãn (Gale-Shapley Algorithm)Thuật toán chấp nhận trì hoãn (Gale-Shapley Algorithm) được xây dựng trên ý tưởng
Thuật toán chấp nhận trì hoãn có thể được diễn giải như sau:
Mã giả thuật toán chấp nhận trì hoãn (Gale-Shapley Algorithm): FUNCTION DeferredAcceptanceAlgorithm$(M, W, P)$: Khởi tạo trạng thái ban đầu $\forall w \in W$ và $\forall m \in M$ độc thân While $\exists m$ độc thân chưa tỏ tình hết danh sách : $w \leftarrow$ bạn nữ xếp hạng cao nhất danh sách yêu thích mà $m$ chưa tỏ tình If $w$ đang độc thân: Thêm $(m, w)$ vào $S$ Else lúc này $w$ đang hẹn hò cùng $m'$: If $w$ thích $m$ hơn $m'$ hay $P_{w}(m) < P_{w}(m')$: $m'$ bị chia tay trở về độc thân, xóa $(m', w)$ ra khỏi $S$ Thêm (m, w) vào $S$ Else $w$ thích $m'$ hơn $m$: $m$ tiếp tục độc thân Endif Endif Endwhile RETURN $S$
3. Phân tích thuật toánThiết kế thuật toán để giải quyết bài toán hôn nhân bền vững có khó lắm không? Lấy người mình yêu và không bỏ được nghe thì rất dể, nhưng nếu bắt tay vào thiết kế thuật toán phân tích tính đúng đắn và phân tích độ phức tạp bạn sẽ thấy bài toán này thuộc dạng không phải dạng vừa đâu Vì sao vậy? Thiết kế một thuật toán hôn nhân bền vững nghĩa là nó phải tìm được $S \subseteq M \times W$ thỏa các điều kiện trên. Lưu ý là $M \times N$ có số phần tử rất lớn tận $n^2$ mà bài toán chúng ta cần làm là lấy ra tổ hợp các phần tử từ tập hợp $M \times N$ nghĩa là số cách chọn của $S$ rất lớn, thuật toán đưa ra lời giải cần phải có một chiến thuật đúng đắn trong không gian tìm kiếm rộng lớn để thỏa mãn ràng buộc. Trước Gale-Shapley, rất nhiều nghiên cứu giải bài toán này. Tiêu biểu là thuật toán của bác Philip Hall, tiếc thay thuật toán chỉ đảm bảo rằng tập trả về là một tập ghép hoàn hảo (tất cả đều kết hôn) tuy nhiên lại không đảm bảo hôn nhân bền vững. Gale-Shapley đưa ra một thuật toán khá đơn giản nhưng rất tinh tế, về sau rất nhiều biến thể được xây dựng dựa trên thuật toán gốc được ứng dụng vào các bài toán thực tiễn trong cuộc sống! 3.1 Tính đúng đắnQUAN SÁT 1 Một khi đã hẹn hò, $w$ không bao giờ trở về trạng thái độc thân. Nếu như một bạn nữ $w$ hẹn hò với một ai đó, tương lai chỉ hẹn hò với người mà mình thích hơn.
QUAN SÁT 2 Những người mà $m$ tỏ tình càng về sau càng ít được $m$ yêu thích hơn.
Chứng minh: Chứng minh phản chứng bằng nguyên lý chuồng bồ câu (nguyên lý ngăn kéo Dirichlet).
Chứng minh Định lý nhỏ 1.1: Giả sử điều ngược lại, tại một thời điểm nào đó tồn tại $m$ đang độc thân mà đã tỏ tình với tất cả bạn nữ $w \in W$. Quan sát 1 cho chúng ta thấy rằng trong trường hợp giả sử này tất cả $w$ đều đang hẹn hò. Vì sao vậy? Để xảy ra điều này, đơn giản là $m$ bị từ chối tỏ tình hoặc bị chia tay với tất cả $n$ bạn nữ, mà trường hợp từ chối hay chia tay thì trạng thái $w$ vẫn đứng yên là hẹn hò. Tuy nhiên từ khi hẹn hò là một cặp $1$ nam và $1$ nữ, có $n$ bạn nữ hẹn hò tuy nhiên lại có ít hơn $n$ bạn nam (bởi vì $m$ đang độc thân), theo nguyên lý chuồng bồ câu, chúng ta không thể làm điều này. Từ đó suy ra điều phải chứng minh.
Chứng minh Định lý nhỏ 1.2: Giả sử thuật toán dừng mà vẫn tồn tại một bạn nam chưa kết hôn. Theo mã giả, thuật toán chỉ dừng khi $m$ đã tỏ tình với tất cả bạn nữ $w$. Tuy nhiên ở định lý nhỏ 1.1 chúng ta thấy rằng: không thể tồn tại một $m$ đang độc thân mà đã tỏ tình với tất cả bạn nữ $w$. Hay nói cách khác, giả sử trên không thể xảy ra. Từ đó suy ra điều phải chứng minh. Vậy kết quả của thuật toán chấp nhận trì hoãn là một tập ghép cặp hoàn hảo. Định lý 2: Ghép cặp bền vững (Stable Matching)Kết quả của thuật toán chấp nhận trì hoãn là một tập ghép cặp bền vững, không tồn tại hai cặp có xu hướng rạn nứt: $$ \neg \exists_{(m, w) \notin S} \left( (m, w') \in S \land (m', w) \in S \land \left( P_{m}(w) < P_{m}(w') \right) \land \left( P_{w}(m) < P_{w}(m') \right) \right)$$Chứng minh: Giả định rằng $S$ không phải là tập ghép cặp bền vững. Nghĩa là $\exists (m, w) \notin S$ mà $m$ và $w$ yêu nhau hơn nhân tình của họ, vì thuật toán trả về một tập ghép cặp hoàn hảo:
Trong lúc chạy thuật toán để sinh ra $S$, nếu quan sát bạn sẽ thấy rằng lần tỏ tình cuối cùng của $m$ chính là $w$, khi đang hẹn hò thì $m$ không bao giờ bắt cá hai tay, $m$ chỉ tiếp tục tìm kiếm mảnh ghép mới khi bị chia tay. Bây giờ chúng ta đặt ra câu hỏi: Liệu $m$ đã tỏ tình với $w$ tại một giai đoạn nào đó trong lúc thực thi thuật toán không?
Thấy rõ chân trị của $P_{m}(w) < P_{m}(w) \land P_{w}(m) < P_{w}(m) $ luôn là một hằng sai. Nghĩa là giả sử ban đầu không bao giờ xảy ra. Suy ra không tồn tại hai cặp hôn nhân không bền vững có nguy cơ rạn nứt. Từ đó suy ra $S$ là tập ghép bền vững. Kết quả của thuật toán chấp nhận trì hoãn luôn đảm bảo hôn nhân bền vững! 3.2 Phân tích độ phức tạp thuật toánThuật toán chấp nhận trì hoãn có độ phức tạp $O(n^2)$, nhìn chung thuật toán lặp không quá $n^2$ vòng lặp tỏ tình, chi phí tính toán cho mỗi lần tỏ tình có thể thực hiện với độ phức tạp hằng số $O(1)$ (với điều kiện là hàm $P$ thiết kế hợp lí, tránh tính toán trong vòng lặp, chúng ta có thể tạo một mảng hai chiều $\mathtt{ranking}$ để làm việc này). 4. Cài đặt thuật toánThuật toán được ThetaLog cài đặt trên Python và Java, để tối ưu hóa việc cài đặt chúng ta nên lưu một mảng hai chiều $\mathtt{ranking}$ thay vì lập trình một hàm $P$ duyệt trên từng danh sách yêu thích để so sánh trong lúc chạy, lúc này tác vụ so sánh thứ hạng yêu thích sẽ là hằng số. Để đánh dấu $m$ đã tỏ tình với ai chúng ta có thể lưu danh sách yêu thích của $m$ dưới dạng cấu trúc dữ liệu động (Dynamic Data Structure) mỗi lần duyệt sẽ rút $w$ ra khỏi danh sách hoặc cấu trúc dữ liệu tỉnh (Static Data Structure) thì cần lưu thêm một mảng tạm để đánh dấu thứ tự duyệt. Nếu dùng Python, đồng thời bạn muốn tìm hiểu các biến thể của thuật toán này trong kinh tế định lượng, Collection of variations on the Gale-Shapley Deffered Acceptance Algorithm có thể là những gì bạn cần tìm, phần cài đặt thuật toán được mô tả trong MatchingMarkets (algorithms/DA.py) của QuantEcon một thư viện mã nguồn mở mô hình kinh tế định lượng mới nổi gần đây.
# _______________________________________________________________________
# |[] ThetaLogShell |X]|!"|
# |"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""|"|
# | > ThetaLog.com | |
# | > ENV: Python 3.6.5 Anaconda | |
# | > Deferred-Acceptance Algorithm | |
# |_____________________________________________________________________|/
def deferred_acceptance_algorithm(man_pref, woman_pref, n):
"""
Thuật toán chấp nhận trì hoãn (Gale-Shapley Algorithm)
# LƯU Ý: thuật toán cài đặt ở mã nguồn này đánh index từ 0
:param man_pref: list(list) - danh sách yêu thích của m thứ i là man_pref[i]
:param woman_pref: list(list) - danh sách yêu thích của w thứ i là woman_pref[i]
:param n: int - số lượng cặp đôi
:return stable_marriage: list(tuple) - mỗi một tuple(m, w) là một cặp hôn nhân
"""
# Người mà hiện tại w đang hẹn hò fall_in_love[w] = m
# Nếu đang trong độc thân fall_in_love[w] = -1
fall_in_love = [-1] * n
# Những người đàn ông độc thân
free_man = list(range(n))
# Hàm P: lưu thứ hạng w thích m rank[w][m]
ranking = [[0] * n for i in range(n)]
for i in range(n):
for j in range(n):
ranking[i][woman_pref[i][j]] = j
# chiến thuật tỏ tình bắt đầu
while free_man:
# xét một m độc thân
m = free_man[0]
# tỏ tình w mà hiện tại m thích nhất (không trả lại danh sách)
w = man_pref[m].pop(0)
# nếu w chưa hẹn hò
if fall_in_love[w] == -1:
# hẹn hò cùng m, m không còn độc thân
fall_in_love[w] = m
free_man.pop(0)
else:
# nếu w thích m hơn m'
if ranking[w][m] < ranking[w][fall_in_love[w]]:
# m hết độc thân, m' độc thân
free_man.pop(0)
free_man.append(fall_in_love[w])
# m và w hẹn hò
fall_in_love[w] = m
# Danh sách [(m,w),...] hôn nhân bền vững
stable_marriage = [(fall_in_love[i], i) for i in range(n)]
# trả về tập hôn nhân bền vững
return stable_marriageChạy thử thuật toán:n = 4
man_pref = [[1,0,2,3],
[3,0,1,2],
[0,2,1,3],
[1,2,0,3]]
woman_pref = [[0,2,1,3],
[2,3,0,1],
[3,1,2,0],
[2,1,0,3]]
result = deferred_acceptance_algorithm(man_pref, woman_pref, n)
print(result) // _______________________________________________________________________
// |[] ThetaLogShell |X]|!"|
// |"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""|"|
// | > ThetaLog.com | |
// | > ENV: Java 1.8.0_181 | |
// | > Deferred-Acceptance Algorithm | |
// |_____________________________________________________________________|/
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class DemoDeferredAcceptanceAlgo {
public static int[][] deferredAcceptanceAlgo(int[][] manPref, int[][] womanPref, int n) {
// Danh sách những người m độc thân
Queue 5. Ứng dụng thuật toánThuật toán này được ứng dụng rộng rãi trong rất nhiều lĩnh vực: y tế, giáo dục, viễn thông, kinh tế, Đặc biệt trong kinh tế, Alvin Roth cho rằng các nghiên cứu lý thuyết của Gale-Shapley có thể làm sáng tỏ hoạt động của thị trường. Alvin Roth và cộng sự đã chứng minh ổn định là chìa khóa để hiểu rõ sự thành công của một thể chế thị trường nhất định. Sự cống hiến về lý thuyết của Gale, Shapley đồng hành cũng nổ lực nghiên cứu thực nghiệm của Roth đã mang đến giải Nobel kinh tế học 2012. Một số ứng dụng tiêu biểu như sau:
Thuật toán ứng dụng vào thực tế sẽ gặp nhiều khó khăn hơn, bạn đọc có thể tìm hiểu thêm các biến thể thuật toán ở nghiên cứu A survey of the stable marriage problem and its variants. 6. Phần kếtThuật toán chấp nhận trì hoãn là một thuật toán giúp giải quyết bài toán hôn nhân bền vững. Kết quả trả về của thuật toán luôn luôn là một tập ghép bền vững. Thuật toán và các biến thể của nó ứng dụng rộng rãi vào nhiều bài toán thực tiễn: kinh tế, giáo dục, y tế, viễn thông, Tham khảo
|