Đến nội dung

Hình ảnh

Vấn đề về ổn định hôn nhân và chọn trường học

- - - - -

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
hoangtrong2305

hoangtrong2305

    Trảm phong minh chủ

  • Phó Quản lý Toán Ứng dụ
  • 861 Bài viết

I. GIỚI THIỆU

 

Hằng năm, 75000 học sinh khối lớp 8 của Tp. New York đăng kí nhập học vào 1 trong 426 trường trung học công lập của thành phố. Cho đến gần đây, quy trình này đòi hỏi học sinh phải liệt kê 5 ngôi trường theo thứ tự ưu tiên. Những danh sách này được gửi đến những ngôi trường, nơi sẽ quyết định ai sẽ được nhận vào, ai sẽ ở danh sách chờ, hoặc ai sẽ bị từ chối. Học sinh được thông báo về tình hình của họ và chỉ được phép chấp nhận một lời mời (vào một trường) và một vị trí ở danh sách chờ. Sau khi những học sinh đã phản hồi lại bất cứ lời mời nào nhận được, những ngôi trường với những vị trí còn trống sẽ thực hiện đợt tuyển sinh thứ 2, và quá trình này sẽ tiếp diễn tới khi kết thúc đợt thứ 3.

 

Nhưng quy trình này có một vài sai sót nghiêm trọng. Vào lúc kết thúc đợt tuyển sinh thứ 3, gần một nửa số học sinh (thường là những học sinh đến từ những gia đình nghèo khó) không được nhận vào trường. Đa số những học sinh đó chờ đợi qua hết mùa hè chỉ để nhận ra được rằng họ đã bị đưa vào một ngôi trường không nằm trong danh sách 5 trường họ chọn.

 

Quy trình này cũng khuyến khích học sinh và bậc phụ huynh suy nghĩ một cách có chiến lược về danh sách các ngôi trường họ muốn đăng ký. Những học sinh bị từ chối bởi ngôi trường đứng đầu trong danh sách của họ có thể phát hiện được rằng ngôi trường ở lựa chọn thứ hai đã không còn chỗ trống ở đợt tuyển sinh thứ 2. Điều này sẽ làm cho nhiều học sinh khó có thể đưa ra những ưu tiên chọn trường theo đúng nguyện vọng của bản thân vì ẩn chứa nhiều rủi ro. Một quan điểm được các nhà Giáo dục học đưa ra cho các học sinh nên:“Xác định mình sẽ cạnh tranh với ai” trước khi đưa ra danh sách những ngôi trường ưa thích.

 

Sau cùng, những ngôi trường sẽ luôn cập nhật chỉ tiêu tuyển sinh khác với dự kiến để giữ chỗ những vị trí cho những học sinh không được nhận vào ngôi trường đầu tiên mà họ chọn.

 

Tóm lại, quy trình này không thể làm hài lòng nhiều học sinh bất chấp nó khuyến khích nhiều phía, cả học sinh lẫn nhà trường, nên tự đưa ra những chiến lược sai nhằm đạt được những kết quả đáng mong đợi mặc dù không khả thi cho lắm. Tính nghi ngờ phổ biến ở quy trình sắp xếp này là môt hệ quả hiển nhiên.

 

Với ý tưởng được miêu tả ở mục này, những nhà kinh tế học Atila Abdulkadiroglu, Parag Pathak và Alvil Roth đã thiết kế một phép nối giữa trường học và học sinh, thực hiện lần đầu tiên vào năm 2004. Thuật toán được số hóa mới này đã giúp khoảng 3000 học sinh mỗi năm và kết quả là những học sinh đã nhận được lời mời từ những ngôi trường nằm ở lựa chọn thứ 1 trong danh sách. Kết quả là bây giờ học sinh đưa ra những danh sách nói lên những ưu tiên thật sự của họ, điều này sẽ cung cấp chính thức cho những ngôi trường với những đầu vào công khai nhằm xác định ngôi trường nào sẽ đóng cửa hoặc cải cách. Về phía các trường học, những ngôi trường nhận thấy rằng việc đưa ra chỉ tiêu không đúng với khả năng thực sự không còn lợi ích gì nữa.

 

Chìa khóa của giải thuật toán này nằm ở khái niệm ổn định, giới thiệu lần đầu tiên vào năm 1962 và được viết bởi Gale và Shapley. Chúng ta nói rằng một phép nối giữa học sinh và nhà trường là “ổn định” khi không có một học sinh hay một trường nào khác muốn được ghép với nhau hơn là cặp nối hiện tại của họ. Gale và Shapley đã giới thiệu một thuật toán, thường được gọi là thuật toán chấp nhận trì hoãn, sẽ giúp ta chắc chắn đưa ra được một phép nối ổn định. Sau đó, Roth cho thấy rằng khi áp dụng thuật toán chấp nhận trì hoãn, một học sinh không thể tăng nguyện vọng vào nhiều ngôi trường họ thích bằng cách đưa ra chiến lược sai lệch, không đúng với nguyện vọng thực sự của bản thân.

 

Mục này sẽ giới thiệu về kết quả lý thuyết trò chơi nằm trong bài viết gốc của Gale – Shapley cùng với những phân tích sau này của Roth. Pathak gọi thuật toán chấp nhận trì hoãn là “một trong những ý tưởng hay nhất của kinh tê” và Roth và Shaley đã được trao giải thưởng Nobel về kinh tế vào năm 2012 cho công trình này.

 

II. VẤN ĐỀ ỔN ĐỊNH HÔN NHÂN

 

Bên cạnh việc ghép nối những học sinh với những ngôi trường, thuật toán chấp nhận trì hoãn đã được áp dụng rộng rãi trong nhiều trường hợp, điển hình như việc ghép học sinh khoa Y với chương trình nội trú. Và theo đó, chúng ta sẽ cùng mô tả thuật toán này qua một ngữ cảnh độc đáo của Gale – Shaley, vấn đề về ổn định hôn nhân.

 

Giả sử ta có số lượng bằng nhau giữa đàn ông $M=\left\{ {{m}_{1}},\ldots ,{{m}_{n}} \right\}$ và phụ nữ $W=\left\{ {{w}_{1}},\ldots .,~{{w}_{n}} \right\}$. Mỗi người đàn ông đưa ra danh sách những người phụ nữ đang theo đuổi, theo thứ tự ưu tiên của họ, và tương tự mỗi người phụ nữ cũng sẽ đưa ra danh sách những người đàn ông mà cô ta thích theo thứ tự ưu tiên. Ta muốn sắp xếp những cuộc hôn nhân giữa những người đàn ông và người phụ nữ sao không có người đàn ông hay phụ nữ nào thích một người khác bạn đời của họ.

 

Trước khi ta đi xa hơn, hãy thống nhất rằng mục đích của chúng ta là mô hình hóa một vấn đề toán học. Chẳng hạn, chúng ta sẽ không xét đến thực tế về việc hôn nhân đồng tính nam hay nữ và không xét đến trường hợp phụ nữ sẽ thường cầu hôn với nam giới .Những vấn đề này đều dẫn đến những tình huống toán học khác hoàn toàn với vấn đề mà ta đang xét.

 

Hơn thế nữa, điều này liên quan trực tiếp đến việc mở rộng vấn đề sang những tình huống khi số lượng giữa đàn ông và phụ nữ khác nhau hoặc khi ta cho phép nối đa thê, khi những người trong một nhóm có thể được ghép với những người ở nhóm khác, tương tự như khi ta áp dụng những ngôi trường nhận vào nhiều hơn một học sinh.

 

Bằng một phép nối, chúng ta muốn nói về một phép tương đương một – với – một $x:M\to W$. Một phép nối $x$ là không ổn định khi có một người đàn ông $m$ và một người phụ nữ $w$ sao cho $m$ thích $w$ hơn $x\left( m \right)$ và $w$ thích $m$ hơn ${{x}^{-1}}\left( w \right)$ như hình minh họa bên dưới. Ngược lại phép nối sẽ được gọi là ổn định.

fcarc-march2015-instability.jpg

Ở bài viết vào năm 1962, Gale và Shapley chứng minh rằng sẽ luôn có một phép nối ổn định khi cho trước một tập ưu tiên của mỗi người đàn ông và phụ nữ. Hơn thế nữa, họ cho ta thấy được cách để tìm được phép nối ổn định bằng cách chấp nhận thuật toán chấp nhận trì hoãn, điều mà bây giờ ta sẽ cùng miêu tả.

 

Bước 1:

- Mọi người đàn ông đều cầu hôn với người phụ nữ đầu tiên trong danh sách những người mà họ cảm thấy thích.

- Tùy theo điều kiện mà một người phụ nữ sẽ nhận lời từ người đàn ông mà họ thấy có cảm tình hơn những người khác. Sau đó, họ sẽ từ chối những lời cầu hôn còn lại.

 

Bước k:

- Những người đàn ông chưa có điều kiện ngỏ lời cầu hôn một người phụ nữ mà anh ta thích nhất trong số người chưa từ chối anh.

- Những người phụ nữ sẽ xem xét ở bước này có người đàn ông nào khác ngỏ lời nữa không và bất kì người đàn ông nào trước đây cô ấy đã chấp nhận và chấp nhận lời cầu hôn từ người đàn ông mà cô ấy thích nhất, thậm chí điều đó cũng có nghĩa là từ chối người đàn ông trước đây cô ta đã chấp nhận.

 

Kết thúc: Quá trình này tiếp diễn cho đến khi mỗi người phụ nữ đã chính thức chấp nhận lời cầu hôn. Ở bước này, thuật toán kết thúc và $w=x\left( m \right)$ khi $w$ nhận $m$ làm bạn đời của mình.

Hãy cùng thực hiện dụng một ví dụ áp dụng thuật toán trên của Gale và Shapley để xem như thế nào. Giả sử có 4 người phụ nữ $\left\{ {{w}_{1}},{{w}_{2}},{{w}_{3}},{{w}_{4}} \right\}$ và 4 người đàn ông $\left\{ {{m}_{1}},~{{m}_{2}},~{{m}_{3}},~{{m}_{4}} \right\}$, thứ tự ưu tiên đã được chỉ ra ở phía dưới, theo thứ tự từ trên xuống.

hn1.png

 

Bước 1: Mỗi người đàn ông cầu hôn người phụ nữ họ thích nhất:

·         ${{m}_{1}}$ cầu hôn ${{w}_{1}}$

·         ${{m}_{2}}$ cầu hôn ${{w}_{1}}$

·         ${{m}_{3}}$ cầu hôn ${{w}_{2}}$

·         ${{m}_{4}}$ cầu hôn ${{w}_{4}}$

fcarc-march2015-example.step.1.a.jpg

Nhận thấy  rằng ${{w}_{1}}$ nhận được 2 lời cầu hôn từ ${{m}_{1}}$ và ${{m}_{2}}$. Cô ấy chọn lời cầu hôn từ ${{m}_{1}}$ vì cô ấy thích ${{m}_{1}}$ hơn ${{m}_{2}}$.

fcarc-march2015-example.step.1.b.jpg

Bước 2: Khi ${{m}_{2}}$ bị ${{w}_{1}}$ từ chối, anh ấy cầu hôn với người anh thích thứ hai là ${{w}_{4}}$.

fcarc-march2015-example.step.2.a.jpg

Và bây giờ khi ${{w}_{4}}$ đã có hai lời cầu hôn từ ${{m}_{2}}$ và ${{m}_{4}}$, cô ấy đã chọn lời cầu hôn đến từ ${{m}_{2}}$.

fcarc-march2015-example.step.2.b.jpg

Bước 3: ${{m}_{4}}$ cầu hôn ${{w}_{2}}$

fcarc-march2015-example.step.3.a.jpg

Khi đó ${{w}_{2}}$ đã chấp nhận ${{m}_{4}}$ và từ chối ${{m}_{3}}$.

fcarc-march2015-example.step.3.b.jpg

Bước 4:

fcarc-march2015-example.step.4.a.jpg

 

fcarc-march2015-example.step.4.b.jpg

Bước 5:

fcarc-march2015-example.step.5.a.jpg

 

fcarc-march2015-example.step.5.b.jpg

Bước 6:

fcarc-march2015-example.step.6.a.jpg

 

fcarc-march2015-example.step.6.b.jpg

Bây giờ chúng ta được ghép nối $x\left( {{m}_{1}} \right)={{w}_{3}},~x\left( {{m}_{2}} \right)={{w}_{4}},~x\left( {{m}_{3}} \right)={{w}_{1}},$ và $x\left( {{m}_{4}} \right)={{w}_{2}}$.

 

Chú ý rằng nếu $m$ cầu hôn $w$ tại một bước nào đó của thuật toán và $w'$ ở bước kế tiếp thì $m$ phải thích $w$ hơn $w'$. Điều này có nghĩa là $m$ không thể cầu hôn một người phụ nữ 2 lần vì sẽ làm cho thuật toán kết thúc.

fcarc-march2015-gs.implications.m.jpg

Ngoài ra, chúng ta cũng thấy rằng $m$ cầu hôn với mỗi người phụ nữ anh ấy thích nhiều hơn so với người tình của anh ấy là $x\left( m \right)$ trước khi cuối cùng cầu hôn $x\left( m \right)$. Điều này có nghĩa là nếu $m$ thích $w$ hơn $x\left( m \right)$ thì $w$ sẽ từ chối $m$ tại một số bước của thuật toán.

 

Ngược lại, nếu $w$ chấp nhận $m$ tại một bước của thuật toán và $m'$ ở bước sau thì có nghĩa là $w$ thích $m'$ hơn $m$. Điều này có nghĩa là người đàn ông cầu hôn $w$ đã bị từ chối ở dòng dưới ${{x}^{-1}}\left( w \right)$ trong danh sách yêu thích của cô ấy.

fcarc-march2015-gs.implications.w.jpg

Bây giờ có thể dễ dàng thấy rằng phép nối được cung cấp bởi thuật toán Gale – Shapley là ổn định. Giả sử người đàn ông $m$ thích người phụ nữ $w~$hơn người tình của $m$ là $x\left( m \right)$, tại một số bước của thuật toán Gale – Shapley, $m$ cầu hôn $w$. Vì $w$ không phải là người tình cuối cùng của $m$, cô ấy phải từ chối m, nghĩa là cô ấy thích ${{x}^{-1}}\left( w \right)$ hơn$~m$. Vì vậy thật không khả thi khi $m$ và $w$ thích nhau hơn người tình của họ.

hn2.jpg


Toán học là ông vua của mọi ngành khoa học.

Albert Einstein

(1879-1955)

Hình đã gửi


-------------------------------------------------------------------------------------------------------------------


Click xem Đạo hàm, Tích phân ứng dụng được gì?

và khám phá những ứng dụng trong cuộc sống


#2
hoangtrong2305

hoangtrong2305

    Trảm phong minh chủ

  • Phó Quản lý Toán Ứng dụ
  • 861 Bài viết

III. PHÉP NỐI ỔN ĐỊNH TỐI ƯU

 

Những người đàn ông và phụ nữ hài lòng bao nhiêu với phép nối $x$ được tạo bởi thuật toán Gale – Shapley? Ví dụ, có thể tìm thấy một phép nối ổn định $y$ khi một số người đàn ông thích người tình $y$ hơn $x$? Có một phép nối ổn định $y$ ở một số người phụ nữ thích người tình $y$ hơn là ở $x$?

 

Chúng ta sẽ nhìn thấy rằng không có người đàn ông nào thích người tình của họ ở trong một phép nối ổn định khác người tình trong $x$. Điều đó có nghĩa là nếu $y$ là một phép nối ổn định khác, thì hoặc là $y\left( m \right)=x\left( m \right)$ hoặc $m$ thích $x\left( m \right)$ hơn $y\left( m \right)$. Do đó chúng tôi gọi $x$ là một phép nối ổn định tối ưu của $M$. Tại một thời điểm nào đó sẽ thuyết phục bạn rằng chỉ có một phép nối ổn định tối ưu của $M$.

 

Hãy giả sử tồn tại phép nối $y$ khác và người đàn ông $m$ sao cho $m$ thích $y\left( m \right)$ hơn $x\left( m \right)$. Ta sẽ thấy rằng điều này là không thể nếu $y$ là phép nối ổn định.

 

Trong trường hợp này, chúng tôi sẽ cho rằng các bước của thuật toán Gale dần đến phép nối ổn định $x$. Vì $m$ thích $y\left( m \right)$ hơn $x\left( m \right)$ nên $y\left( m \right)$ phải từ chối $m$ tại một bước $k$ của thuật toán. Tất cả $m$ kiểu này, chọn một $m$ sao cho không có người đàn ông $m'$ nào bị $y\left( m \right)$ từ chối sớm hơn một bước ${k}'<k$.

fcarc-march2015-gs.optimal.1.jpg

Khi $y\left( m \right)~$từ chối $m$, cô ấy phải thích một người đàn ông $m'$ đã cầu hôn cô ấy ở bước $k$. Khi $m'$ được $y\left( m \right)$ chấp nhận ở bước $k$ và chưa bị $y\left( m' \right)$ từ chối ở bước trước $k$, $m'$ phải thích $y\left( m \right)$ hơn $y\left( {{m}'} \right)$.

Vì thế $y\left( m \right)$ thích $m'$ hơn $m$ và $m'$ thích $y\left( m \right)$ hơn $y\left( {{m}'} \right)$, nghĩa là $y$ không phải là sự kết hợp ổn định.

hn3.png

Bằng cách này, chúng ta thấy rằng $x$ là một phép nối ổn định tối ưu của $M$, mọi người đàn ông ít nhất hài lòng với người tình $x$ cũng như phép nối ổn định $y$

 

Ví dụ đơn giản cho thấy phép nối $x$ không phải luôn tối ưu cho phụ nữ. Tuy nhiên, có một phép nối ổn định tối ưu W, chúng ta chỉ cần áp dụng thuật toán Gale – Shapley với vai trò thay đổi cho nhau, tức để phụ nữ cầu hôn nam giới.

 

IV. TIẾT LỘ SỞ THÍCH THẬT SỰ

 

Ta có thể tạo ra phép nối ổn định với thuật toán Gale-Shapley và những phép nối này là tốt nhất có thể cho một tập người. Cho đến nay, chúng ta đã giả định rằng mỗi người thể hiện trung thực sở thích thật sự của mình. Tuy nhiên, có khả năng một người đàn ông có thể cố lấy một người tình hấp dẫn hơn bằng cách miêu tả sai sở thích thật sự của mình.

 

Chúng tôi sẽ cho thấy rằng tiết lộ sở thích thật sự của một người, theo lý thuyết trò chơi, là một chiến lược trội cho nam giới. Điều này có nghĩa rằng, giả sử tất cả những người đàn ông và phụ nữ khác giữ sở thích như nhau, một người đàn ông không thể có được một người tình hấp dẫn hơn bằng cách miêu tả sai sở thích của mình.

 

Đặt $P$ là tập hợp các sở thích của tất cả những người đàn ông và phụ nữ, ta giả định đó là sở thích thật sự của họ. Ta muốn xem xét tập các sở thích $P'$, giống $P$ ngoại trừ một người đàn ông ${{m}_{m}}$, người mà ta gọi là "kẻ gian dối."

 

Ngoài ra, ta sẽ sử dụng $x~=~GS~\left( P \right)$ để biểu thị các phép nối ổn định là kết quả của thuật toán Gale - Shapley áp dụng với các sở thích thật sự $P$, trong khi $y=~GS~\left( P~' \right)$ là phép nối ổn định từ các sở thích gian dối. Mục tiêu của ta là để cho $m$ không thể lợi dụng bạn tình của mình; nói cách khác, ta sẽ cho thấy rằng hoặc là $y~\left( m \right)~=~x~\left( m \right)$ hoặc $m$ thích $x\left( m \right)$ hơn $y\left( m \right)$ dựa theo sở thích thật sự của mình.

 

Đầu tiên, ta thấy rằng ta chỉ cần phải xem xét một trường hợp cụ thể của việc miêu tả sai. Luôn nhớ rằng $y~=~GS~\left( P \right)$, chúng ta sẽ xem xét tương đương miêu tả sai đơn giản $P''$ có những tính chất mà kẻ gian dối ${{m}_{m}}$ thích $y\left( {{m}_{m}} \right)$ hơn tất cả người phụ nữ khác, theo danh sách sở thích của ông trong $P''$. Đó là, kẻ gian dối ${{m}_{m}}$ lấy $P''$ từ $P$ bằng cách di chuyển người tình của mình trong $y$ để lên đầu danh sách. Ta ký hiệu $z~=~GS~\left( P'' \right)$ là phép nối ổn định có kết quả từ việc miêu tả sai đơn giản $P''$.

 

Ta quan sát các điều sau:

 

1.$y\left( {{m}_{m}} \right)~=~z~\left( {{m}_{m}} \right).$ Điều này có nghĩa rằng miêu tả sai $P''$ dẫn đến cùng một người tình cho ${{m}_{m}}$ như miêu tả sai $P'$. Đây là lý do tại sao ta nói rằng $P'$ và $P''$ là miêu tả sai tương đương. Nếu ${{m}_{m}}$ không có được một người tình hấp dẫn trong $z$, anh ta sẽ không có $y$ và ngược lại.

 

Điều này rất dễ hiểu. Hãy nhớ rằng $y$ là ổn định đối với các sở thích của $P'$ vì ta sử dụng thuật toán Gale – Shapley để thu được $y$. Điều này có nghĩa rằng không có người đàn ông $m$ cũng như người phụ nữ $w$ thích nhau (trong $P'$) hơn người tình của họ trong $y$. Tuy nhiên, điều này hàm ý rằng $y$ là ổn định trong $P'$, người duy nhất có sở thích đã thay đổi là ${{m}_{m}}$ , từ khi ông ta di chuyển $y\left( {{m}_{m}} \right)$ lên đầu danh sách của mình trong $P''$, ông tìm thấy người tình của mình dưới $y$ theo $P''~$với mức độ mong muốn như trong $P'$.

 

Cần nhớ rằng bây giờ $z~$là phép nối ổn định tối ưu $M$ theo $P''$. Vì $y$ ổn định đối với $P''$ nên ${{m}_{m}}$ thích $z\left( {{m}_{m}} \right)$ ít nhất là như tình cảm của anh ta đối với $y\left( {{m}_{m}} \right)$. Tuy nhiên, ông vẫn thích $y\left( {{m}_{m}} \right)$ (trong $P''$) hơn bất kỳ người phụ nữ khác, vì vậy $z\left( {{m}_{m}} \right)~=~y\left( {{m}_{m}} \right).$

 

2. Bây giờ chúng ta sẽ cho rằng $P'$.  đại diện đơn giản cho kẻ gian dối ${{m}_{m}}$ và $y~=~GS\left( {{P}'} \right).$ Ta cũng giả định rằng ${{m}_{m}}$ trình bày sai sở thích thật sự của mình để có được người tình $y\left( {{m}_{m}} \right)$ mà anh thích ít nhất cũng như $x\left( {{m}_{m}} \right)$, dựa theo sở thích thật sự $P$ của anh ta. Với những giả thiết này, không có người đàn ông nào trong $y$ tồi tệ hơn anh ta trong $x$, dựa theo sở thích thật sự của anh ta. Điều này có nghĩa đối với mỗi người đàn ông $m$, hoặc là $y\left( m \right)~=~x\left( m \right)$ hoặc $m$ thích $y\left( m \right)$ hơn$~x\left( m \right)$.

 

Chú ý, chúng ta giả sử rằng mức độ chi phí gian dối không quá tệ đối với $y$. Trên thực tế, ông ta đã trình bày sai nhằm hi vọng người tình trong mộng đồng ý yêu ông.

 

Bây giờ giả sử có một người đàn ông $m$ có chi phí tệ trong $y$ hơn trong $x$, tức là giả sử $m$ thích $x\left( m \right)$ hơn $y\left( m \right)$ như hình vẽ. Vì $m$ không phải là kẻ gian dối, $m$ thích cả $P$ và $P'$. Do đó $m$ đã bị $x\left( m \right)$ từ chối tại một số bước trong $GS\left( {{P}'} \right)$.

fcarc-march2015-gs.misrep.1.jpg

Đặt $k$ là bước đầu tiên, trong đó một số người đàn ông $m$ bị $x\left( m \right)$ từ chối trong $GS\left( {{P}'} \right)$. Cụ thể hơn, giả sử $m$ bị $x\left( m \right)$ từ chối và tạo ưu thế cho $m'$ ở bước $k$, điều này có nghĩa là $x\left( m \right)$ thích $m'$ hơn $m$, do đó không thể có chuyện $m$ cầu hôn $x\left( m \right)$ trong $GS\left( P \right)$. Do đó $m'$ thích $x\left( {{m}'} \right)$ hơn $x\left( m \right)$.

hn4.png

Vì $m'$ cầu hôn $x\left( m \right)$ ở bước $k$ trong $GS\left( P' \right)$ nên $m$ phải nhận được lời từ chối từ $x\left( {{m}'} \right)$ ở một bước trước đó trong $GS\left( {{P}'} \right)$. Tuy nhiên, điều này là không thể vì ta giả sử $k$ là bước đầu tiên mà $m$ bị $x\left( m \right)$ từ chối trong $GS\left( {{P}'} \right)$. Do đó $m$ thích $y\left( m \right)$ ít nhất cũng như thích $x\left( m \right)$.

 

3. Vì mọi người đàn ông $m$ đều hài lòng với $y\left( m \right)$ cũng như $x\left( m \right)$, ta rút ra kết luận rằng: Nếu $m$ cầu hôn một người phụ nữ $w$ trong $GS\left( P' \right)$ thì anh ta phải cầu hôn cô trong $GS\left( P \right)$.

 

Từ quan sát này ta rút ra một thực tế rất hữu dụng rằng nếu $w~$chỉ nhận được một lời đề nghị trong $GS\left( P \right)$ thì cô ta cũng chỉ nhận được một đề nghị trong $GS\left( {{P}'} \right)$. Nếu đề xuất này là của $m$, thì $x\left( m \right)=y\left( m \right)=w$.

fcarc-march2015-gs.optimal.1.jpg

Bây giờ ta sắp xếp tất cả mọi thứ ta cần nhằm giải thích lí do vì sao nói ra sở thích thật sự là chiến lược trội cho nam giới. ta giả sử rằng các người đàn ông và phụ nữ còn lại đều có sở thích như nhau, và chúng ta sẽ thấy kẻ gian dối không thể thu hút người tình mà anh ta thích, khi đó hoặc $y\left( {{m}_{m}} \right)=x\left( {{m}_{m}} \right)$ hoặc $m$ thích $x\left( {{m}_{m}} \right)$ hơn $y\left( {{m}_{m}} \right)$.

 

Chúng ta sẽ bắt đầu bằng giả thiết rằng đối với kẻ gian dối, hoặc là $y\left( {{m}_{m}} \right)=x\left( {{m}_{m}} \right)$ hoặc $m$ thích $y\left( m \right)$ hơn $x\left( {{m}_{m}} \right)$ vì kết quả này chắc chắn đúng nếu như ${{m}_{m}}$ thích $x\left( {{m}_{m}} \right)$ hơn $y\left( {{m}_{m}} \right)$.

 

Với giả thiết này, chúng ta thấy rằng, trong $y$ không có người đàn ông nào tệ hơn $x$, như đã giải thích ở trên. Ngoài ra nếu như $m$ cầu hôn một phụ nữ $w$, người chỉ nhận được một lời cầu hôn, khi đó $y\left( m \right)=x\left( m \right)$.

 

Nhìn vào các bước của $GS\left( P \right)$, kẻ gian dối sẽ cầu hôn với người phụ nữ $x\left( {{m}_{m}} \right)$ anh ta muốn làm người tình ở bước $r$ nào đó. Chiến lược của tôi sẽ cho thấy rằng, mọi người đàn ông $m$ cầu hôn $x\left( m \right)$ ở bước $r$ hay trễ hơn sẽ có $y\left( m \right)=~x\left( m \right)$. Khi đó suy ra được rằng: $y\left( {{m}_{m}} \right)=~x\left( {{m}_{m}} \right)$.

 

Chúng ta tiến hành bằng cách, đầu tiên nhìn vào người đàn ông $m$, người đàn ông này cầu hôn $x\left( m \right)=w$ trong bước cuối cùng $t$ của $GS\left( P \right)$.

fcarc-march2015-numberline.1.jpg

Khi đó $m$ là người duy nhất cầu hôn $w$. Nếu không, $w$ phải từ chối người đàn ông trước kia cô đã chấp nhận, và người đàn ông đó sẽ thực hiện lời cầu hôn khác trong bước tiếp theo. Do vậy $y\left( m \right)=x\left( m \right)$

 

Bây giờ, chúng ta xét đến người đàn ông đã cầu hôn $x\left( m \right)=w$ là người phụ nữ phù hợp với mình ở bước $r\le s<t$, và ta sử dụng giả thiết quy nạp rằng bất kì người đàn ông nào tỏ tình với người tình của mình ở bước $s+1$ thì thỏa mãn $y\left( m \right)=x\left( m \right)$.

fcarc-march2015-numberline.2.jpg

Sau đó chúng ta nhìn vào tập các người đàn ông $\bar{M}$ mà bị $w$ từ chối trước khi chấp nhận lời cầu hôn của $m$. Nếu không có ai bị $w$ từ chối, khi đó $m$ là người đàn ông duy nhất cầu hôn $w$, do đó $y\left( m \right)=x\left( m \right).$

 

Nếu có một người nào đó bị $w$ từ chối, kí hiệu $m'$ là người đàn ông cô thích nhất trong nhóm người đã cầu hôn với cô. Người đàn ông $m'$ này đã bị cô từ chối ở bước $s$ đề chấp nhận $m$. Vì vậy $m'$ cầu hôn với người tình khác ở một bước sau $s$, theo giả thiết quy nạp thì $y\left( {{m}'} \right)=x\left( {{m}'} \right)$.

fcarc-march2015-gs.step.r.jpg

Vì $m'$ cầu hôn với người tình tại một bước sau đó, $m'$ không phải là kẻ dối trá, do vậy $m'$có sở thích giống nhau ở cả $P$ và $P'$. Điều này có nghĩa là, khi ${m}'$ cầu hôn $w~$trong $GS\left( P' \right)$ và bị từ chối, nên $w$ có nhận được một lời cầu hôn khác trong $GS\left( {{P}'} \right)$.

 

Ta thấy rằng nếu $m$ cầu hôn với người phụ nữ trong $GS\left( {{P}'} \right)$ thì anh ta cũng làm điều tương tự trong $GS\left( P \right)$ . Vì lời cầu hôn khác duy nhất mà $w$ nhận được trong $GS\left( P \right)$ là từ $m$, khi đó lời cầu hôn cuối cùng mà cô ấy nhận được trong $GS\left( {{P}'} \right)$ cũng từ $m$. Vì vậy, ta kết luận rằng $y\left( m \right)=x\left( m \right)$.

 

Do đó bất kì người đàn ông nào ngỏ lời với người tình của mình ở bước $s$ thì $y\left( m \right)=x\left( m \right)$. Theo quy nạp cho thấy rằng, nếu người đàn ông nào đó cầu hôn với người tình của mình ở bước $r$ hoặc sau bước $r$ thì phải thỏa mãn $y\left( m \right)=x\left( m \right).$  Vì kẻ dối trá cầu hôn với người tình ở bước $r,~$điều này có nghĩa là $y\left( {{m}_{m}} \right)=x\left( {{m}_{m}} \right)$. Nói cách khác, kẻ dối trá không thể cải thiện độ ấn tượng của người tình về mình khi hắn không thật lòng.

fcarc-march2015-gs.step.r.b.jpg

Lạ thật, ví dụ cho thấy rằng, những người đàn ông khác cầu hôn với người tình của họ trước bước $r$ có thể cải thiện độ ấn tượng của người tình về họ. Tính cách không thật lòng của kẻ dối trá ${{m}_{m}}$ không thể cải thiện độ ấn tượng của người tình về mình mà còn giúp cải thiện ấn tượng của cô ta cho người đàn ông khác.

 

V. TÓM TẮT

 

Trở lại câu hỏi về phép nối giữa học sinh với trường học. Chúng ta nên hỏi nhóm sẽ đưa ra nguyện vọng (hay lời cầu hôn trong ví dụ trên). Chạy thuật toán với trường hợp học sinh đưa ra nguyện vọng khiến cho các học sinh không có động lực để đưa ra nguyện vọng trái với ý muốn bản thân mặc dù trường học khuyến khích như vậy. Tuy nhiên, chúng ta mong đợi rằng việc nhà trường đưa ra chỉ tiệu không đúng với chỉ tiêu thật sự sẽ được áp dụng chung cho các học sinh, khi đó học sinh sẽ dễ dàng xác định. Trường học có thể bị khống chế phải thông qua các yêu cầu rõ ràng hoặc các điều luật khác nhằm ngăn chặn đưa ra chỉ tiêu không đúng, ví dụ như phân biệt chủng tộc.

 

Trên thực tế, một trong những cộng tác viên của Roth là Atila Abdulkadiroglu nói rằng ông đã nhận được các cuộc gọi từ các bậc cha mẹ muốn nghe lời khuyên của ông nhằm chuẩn bị tốt hơn cho việc chọn trường của con họ. Câu trả lời của ông rất đơn giản:” Sắp xếp các trường theo đúng thứ tự ưu tiên”.

 

Tính ổn định là một điều kiện trực quan cần thiết khi áp dụng trên hệ phép nối, như quy trình tuyển sinh ở trường Thành phố New York. Trong một phép nối ổn định, không có một tổ chức nào khuyến khích tìm kiếm các phép nối khác nhau; Ví dụ như: Nếu một người đàn ông có tình cảm với một người phụ nữ hơn vợ của anh ta, thì anh ta không có cơ hội đâu vì cô ấy còn có tình cảm với chồng mình hơn anh ta.

 

Tuy nhiên, người ta có thể hỏi có chứng cứ nào ủng hộ tính quan trọng của vai trò ổn định trong hệ phép nối. Trên thực tế, Roth và công sự của ông đã nghiên cứu trên nhiều thị trường khác nhau để giải đáp cho câu hỏi này. Ví dụ, quy trình các sinh viên y khoa Mỹ được nối với các chương trình cư trú đã được sửa đổi trong những năm 1950 và trở nên gần giống với thuật toán chấp nhận trì hoãn. Và thuật toán này đã được chứng minh rất thành công, kết quả là Ủy ban Hoàng gia Anh (British Royal Commission) đã đề nghị từng phân khu của Dịch vụ Y tế  Quốc gia Anh (British National Health Service) đưa vào sử dụng một hệ tương tự.

 

Đúng như mong đợi, mỗi phân khu đã sử dụng thuật toán phép nối khác nhau một chút vì các chi tiết trong hệ ở Mỹ không được miêu tả trong các tài liệu y khoa nước Mỹ. Hệ này ở một số phân khu được phát triển tốt trong khi một số khu khác lại thất bại. Roth và các cộng sự của ông xác định rằng thuật toán chỉ thành công khi có tính ổn định, còn không có tính ổn định thì thất bại.

 

Về việc áp dụng lý thuyết trò chơi vào kinh tế, Roth đã viết: “Kiểm tra thực tế thành công của chúng tôi không chỉ đơn thuần là việc chúng tôi hiểu rõ những nguyên tắc chung để điều khiển tương tác kinh tế tốt như thế nào, mà còn cho thấy rằng ta có thể áp dụng những kiến thức này rất tốt vào các câu hỏi thiết thực trong kĩ thuật kinh tế vi mô”. Thật vậy, các ví dụ như quy trình tuyển sinh vào trường trung học Thành phố New York là một bằng chứng quan trọng thể hiện sự thành công của thuật toán này.

 

Nguồn: http://www.ams.org/s...lumn/fc-2015-03

 

Bài viết do thành viên Chuyên san EXP dịch.


Toán học là ông vua của mọi ngành khoa học.

Albert Einstein

(1879-1955)

Hình đã gửi


-------------------------------------------------------------------------------------------------------------------


Click xem Đạo hàm, Tích phân ứng dụng được gì?

và khám phá những ứng dụng trong cuộc sống





0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh