Lập trình

Một giải pháp là ưu tiên các đỉnh trước khi cơ chế bắt đầu. Không mất tính tổng quát, giả sử rằng các đỉnh 1; 2; :::; n được sắp xếp theo thứ tự ưu tiên cao nhất đến thấp nhất.4 Sau đó, chúng tôi thực hiện bước (3) như sau:

(3a) Let M₀ denote the set of maximum matchings of G.

(3b) For i = 1; 2; : : : ; n:

 

(3b.i) Let Z_i denote the matchings in M_{i  1} that match vertex i.

(3b.ii) If Z_i =6 ;, set M_i = Z_i.

(3b.iii) Otherwise, set M_i = M_{i  1}.

(3c) Return an arbitrary matching of M_n.

Đó là, trong mỗi lần lặp i, chúng tôi hỏi liệu có sự phù hợp tối đa nào tôn trọng các cam kết trước đó và cũng phù hợp với đỉnh i. Nếu vậy, chúng tôi cũng cam kết phù hợp với i trong kết hợp nal. Nếu các cam kết trước đó loại trừ việc khớp i trong một kết hợp khớp thẻ tối đa, thì chúng ta bỏ qua i và chuyển sang đỉnh tiếp theo. Theo cảm ứng trên i, Mi là tập con không rỗng của các kết quả khớp tối đa của G. Mọi khớp của Mn khớp với cùng một tập đỉnh | các đỉnh i mà Zi không trống | vì vậy sự lựa chọn kết hợp trong bước (3c) là không liên quan.

Định lý 1.1 Với mọi bộ sưu tập fE_igⁿi= 1 bộ cạnh và mọi thứ tự của các đỉnh, cơ chế khớp ưu tiên ở trên là DSIC: không có tác nhân nFào có thể đi từ không khớp đến bằng cách báo cáo một tập hợp con nghiêm ngặt F_i của  E_i thay vì E_i.

Chúng tôi để lại bằng chứng cho bạn; xem bài tập

1.3 Những thách thức tiên tiến

Nghiên cứu hiện tại tập trung vào các vấn đề khuyến khích ở cấp độ bệnh viện, thay vì ở cấp độ của các cặp bệnh nhân - nhà tài trợ. Sự thay đổi này được thúc đẩy tốt bởi vì nhiều cặp người hiến tặng bệnh nhân được báo cáo cho các bệnh viện trao đổi thận quốc gia, chứ không phải bởi chính các cặp. Các mục tiêu của một bệnh viện (để phù hợp với càng nhiều bệnh nhân càng tốt) và của xã hội (để phù hợp với càng nhiều bệnh nhân càng tốt) thì không hoàn toàn phù hợp. Các vấn đề khuyến khích chính được giải thích tốt nhất thông qua các ví dụ.

 

Ví dụ 1.2 (Sự cần thiết phải báo cáo đầy đủ) Giả sử có hai bệnh viện, mỗi bệnh viện có ba bệnh nhân (Hình 7). Các cạnh thể hiện các cặp nhà tài trợ bệnh nhân tương thích lẫn nhau, như với cơ chế khớp ở trên. Mỗi bệnh viện có một cặp người hiến tặng bệnh nhân có thể khớp với nhau trong nội bộ mà không cần báo cáo họ với một cuộc trao đổi quốc gia. Chúng tôi chắc chắn không muốn các bệnh viện tham lam "thực hiện các trận đấu nội bộ này trong ví dụ này | nếu H1 khớp 1 và 2 trong nội bộ và chỉ báo cáo 3 cho trao đổi và H2 khớp với 5 và 6 nội bộ và chỉ báo cáo 4 cho trao đổi, sau đó trao đổi không thể khớp 3 và 4 để không có thêm kết quả khớp nào. Ngược lại, nếu cả H1 và H2 đều báo cáo đầy đủ 3 cặp nhà tài trợ bệnh nhân của họ với sàn giao dịch quốc gia, thì 1, 2 và 3 có thể được khớp với 4, 5 và 6, và do đó tất cả các bệnh nhân đều được khớp. Nói chung, mục tiêu là khuyến khích các bệnh viện báo cáo tất cả các cặp người hiến tặng bệnh nhân của họ, để cứu càng nhiều người càng tốt.

Figure 7: Example 1.2. Full reporting by hospitals leads to more matches than with only internal matches.

Figure 8: Example 1.3. Hospitals can have an incentive to hide patient-donor pairs

Figure 9: An instance of stable matching

Ví dụ 1.3 Xem xét lại hai bệnh viện, nhưng hiện có 7 bệnh nhân (Hình 8). Quan sát rằng, với một số đỉnh lẻ, mỗi khớp đều để lại ít nhất một bệnh nhân không thể so sánh được. Tuy nhiên, nếu H1 che giấu bệnh nhân 2 và 3 khỏi trao đổi (trong khi H2 báo cáo trung thực), thì H1 đảm bảo rằng tất cả các bệnh nhân của nó đều khớp. Kết hợp tối đa duy nhất trong biểu đồ báo cáo khớp với bệnh nhân 6 với 7 (và 4 với 5) và H1 có thể khớp với 2 và 3 trong nội bộ. Mặt khác, nếu H2 che giấu bệnh nhân 5 và 6 trong khi H1 báo cáo trung thực, thì tất cả các bệnh nhân của H2 đều được khớp. Trong trường hợp này, kết hợp tối đa duy nhất trong biểu đồ báo cáo khớp với bệnh nhân 1 với 2 và 4 với 3, trong khi H2 có thể khớp với bệnh nhân 5 và 6 bên trong.

Kết quả cuối cùng là có sự căng thẳng không thể hòa giải giữa các ưu đãi xã hội và bệnh viện: không thể có một cơ chế DSIC luôn tính toán khớp thẻ tối đa trong biểu đồ đầy đủ.

Theo ví dụ 1.3, mục tiêu được sửa đổi phải là tính toán mức độ phù hợp tối đa của tim để sao cho mỗi bệnh viện tham gia, số lượng bệnh nhân của họ được khớp tương đương với bất kỳ kết hợp nào, mức độ tối đa hoặc khác - khôn ngoan. Hiểu mức độ mà điều này là có thể, trong cả lý thuyết và thực tiễn, là một chủ đề nghiên cứu tích cực [2, 8].

2. Kết hợp ổn định

Kết hợp ổn định là ví dụ điển hình của thiết kế cơ chế mà không cần tiền. Ứng dụng sát thủ bao gồm phân công sinh viên tốt nghiệp trường y cho bệnh viện và học sinh vào trường tiểu học. Mô hình và thuật toán sau đây trực tiếp hữu ích cho các ứng dụng này và các ứng dụng khác với một vài cation modi đáng kinh ngạc.

Chúng tôi xem xét hai bộ U và V | \ nam "và \ nữ" | với n đỉnh mỗi. Mỗi đỉnh cũng có tổng thứ tự trên các đỉnh của tập khác. Ví dụ, trong Hình 9, tất cả đàn ông đều đồng ý về thứ hạng của phụ nữ, trong khi phụ nữ có những ý kiến rất khác nhau về đàn ông.

Định nghĩa 2.1 Một kết hợp ổn định là một kết hợp lưỡng cực hoàn hảo | tức là, mỗi đỉnh được khớp với chính xác một đỉnh từ bộ khác | sao cho không có cặp chặn \ ", nghĩa là:

(*) nếu u 2 U; v 2 V không khớp nhau, sau đó u thích người bạn đời của mình v0 trong trận đấu với v hoặc v thích người bạn đời của mình u0 trong trận đấu với u.

Một kết hợp hoàn hảo mà điều kiện không thành công (*) sẽ đánh vần rắc rối, vì cặp chặn u và v sẽ bị cám dỗ để chạy o với nhau.

Tiếp theo chúng ta sẽ thảo luận về thuật toán đề xuất nổi tiếng để tính toán một kết hợp ổn định. Gale và Shapley [3] đã chính thức hóa vấn đề khớp ổn định và đưa ra thuật toán này. Thật đáng kinh ngạc, sau đó người ta đã phát hiện ra rằng về cơ bản, thuật toán tương tự đã được sử dụng, kể từ những năm 1950, để chỉ định cư dân y tế cho các bệnh viện (như ngày nay) [4]!

Thuật toán đề xuất:

Trong khi có một người đàn ông không được chăm sóc u 2 U:

{u cầu hôn người phụ nữ yêu thích của mình, người chưa từ chối anh ta.

{Mỗi người phụ nữ chỉ giải trí tốt nhất của mình (theo quan điểm của cô ấy) cho đến nay.

 

Ví dụ 2.2 Hãy xem xét ví dụ trong Hình 9. Giả sử trong lần lặp đầu tiên, chúng tôi chọn người đàn ông C, người đã kịp thời đề xuất lựa chọn đầu tiên của anh ta, D. Woman D chấp nhận vì cô ấy hiện không có người khác. Nếu chúng ta chọn người đàn ông B trong lần lặp lại tiếp theo, anh ta cũng cầu hôn người phụ nữ D. Vì người phụ nữ D thích B hơn C, cô ta từ chối C để ủng hộ B. Nếu chúng ta chọn người đàn ông A tiếp theo, kết quả tương tự: D từ chối B trong ủng hộ A. Một quỹ đạo khả dĩ cho phần còn lại của thuật toán là: người đàn ông C hiện đề xuất lựa chọn thứ hai của mình, E; Người đàn ông B sau đó cũng đề xuất với E, và E sau đó từ chối C ủng hộ B; và cuối cùng, C đề xuất với lựa chọn cuối cùng của mình là F, người chấp nhận.

Một số ý kiến về thuật toán và các thuộc tính của nó. Đầu tiên, nó không được xác định rõ ràng, bỏ ngỏ cách người đàn ông không được chọn lựa được chọn. Thứ hai, lưu ý rằng mỗi người đàn ông có hệ thống đi qua danh sách sở thích của mình, từ trên xuống dưới. Thứ ba, những người đàn ông mà một người phụ nữ tham gia chỉ cải thiện trong quá trình thuật toán. Thứ tư, thuật toán duy trì sự bất biến mà mỗi người đàn ông được kết hợp với nhiều nhất một người phụ nữ và mỗi người phụ nữ được kết hợp với nhiều nhất một người đàn ông.

Các kết hợp ổn định và thuật toán đề xuất có một số lượng đáng kinh ngạc các thuộc tính thanh lịch. Chúng tôi bắt đầu với những cái cơ bản nhất.

Định lý 2.3 (Tính toán của kết hợp ổn định) Thuật toán đề xuất kết thúc ở hầu hết các lần lặp n² với kết hợp ổn định.

Figure 10: Example with multiple stable matchings

Hệ quả 2.4 (Sự tồn tại của một kết hợp ổn định) Đối với mỗi bộ sưu tập danh sách ưu tiên cho nam và nữ, tồn tại ít nhất một kết hợp ổn định.

 

Chúng tôi nhấn mạnh rằng Hệ quả 2.4 không rõ ràng là một tiên nghiệm. Thật vậy, có một số biến thể đơn giản của vấn đề đối sánh ổn định mà giải pháp không được đảm bảo.

 

Chứng minh Định lý 2.3: Ràng buộc về số lần lặp rất dễ chứng minh. Vì mỗi người đàn ông làm việc theo cách của mình xuống danh sách ưu tiên của mình, không bao giờ cầu hôn cùng một người phụ nữ hai lần, anh ta đưa ra tối đa n đề xuất. Điều này làm cho hầu hết các đề xuất n2 (và do đó lặp đi lặp lại) nói chung.

Tiếp theo, chúng tôi tuyên bố rằng thuật toán đề xuất luôn kết thúc với một kết hợp hoàn hảo. Vì nếu không, một số người đàn ông phải bị từ chối bởi tất cả n phụ nữ. Một người đàn ông chỉ bị một người phụ nữ từ chối ủng hộ để phù hợp với một người đàn ông tốt hơn, và một khi phụ nữ được kết hợp với một người đàn ông, cô ấy vẫn phù hợp với một người đàn ông trong phần còn lại của thuật toán. Vì vậy, tất cả n phụ nữ phải được kết hợp ở cuối thuật toán. Nhưng sau đó tất cả n người đàn ông cũng được kết hợp ở cuối thuật toán, một mâu thuẫn.

Cuối cùng, chúng tôi tuyên bố rằng tính toán khớp hoàn hảo là ổn định. Để xem tại sao, hãy xem xét một người đàn ông u 2 U và một người phụ nữ v 2 V không phù hợp với nhau. Điều này có thể xảy ra vì hai lý do di erent. Trong trường hợp đầu tiên, bạn không bao giờ đề xuất với v. Vì bạn đã tìm ra danh sách của mình bắt đầu từ đầu, điều này có nghĩa là cuối cùng bạn đã khớp với người mà anh ta thích v. Nếu bạn đã đề xuất với v tại một số điểm trong thuật toán , phải là v từ chối bạn vì một người đàn ông cô ấy thích (vào thời điểm bạn đề nghị, hoặc sau đó). Vì chuỗi những người đàn ông mà v được kết hợp chỉ cải thiện trong suốt quá trình thuật toán, nên cuối cùng cô ấy phù hợp với người mà cô ấy thích.

Chúng tôi đã lưu ý trước đó rằng thuật toán đề xuất không chỉ định cách chọn trong số những người đàn ông không bị ràng buộc trong một lần lặp. Có phải tất cả các lựa chọn có thể dẫn đến cùng một kết hợp ổn định? Trong Hình 9 chỉ có một kết hợp ổn định, vì vậy trong ví dụ đó, câu trả lời là có. Tuy nhiên, nói chung, có thể có nhiều hơn một kết hợp ổn định. Trong Hình 10, cả nam và nữ đều không đồng ý về thứ hạng của những người khác. Trong kết quả khớp được tính toán bởi thuật toán đề xuất, cả hai người đàn ông đều có lựa chọn đầu tiên, với A và B tương ứng với C và D. Cung cấp cho phụ nữ các lựa chọn đầu tiên của họ mang lại một kết hợp ổn định khác.

Chúng tôi chứng minh một tuyên bố mạnh mẽ hơn để giải quyết liệu đầu ra của thuật toán đề xuất có phải là duy nhất hay không. Đối với một người đàn ông u 2 U, hãy để h(u) là người phụ nữ được xếp hạng cao nhất (trong u danh sách ưu tiên) mà u được khớp với bất kỳ kết hợp ổn định nào. Sau đó:

Định lý 2.5 (Kết hợp ổn định tối ưu nam) Kết hợp ổn định được tính toán bằng thuật toán đề xuất khớp với mọi người từ 2 U đến h (u).

Định lý 2.5 ngay lập tức ngụ ý rằng đầu ra của thuật toán đề xuất là độc lập mà người đàn ông không được chọn được chọn trong mỗi lần lặp. Nó cũng ngụ ý rằng tồn tại một "kết hợp ổn định" tối ưu nam | một kết hợp ổn định trong đó mọi người đàn ông đồng thời đạt được \ kịch bản trường hợp tốt nhất của mình "| không có sự trao đổi giữa những người đàn ông khác nhau là cần thiết. Một tiên nghiệm, không có lý do gì để mong đợi sự khác biệt của h (u) và do đó tạo ra một kết hợp hoàn hảo.

 

Chứng minh Định lý 2.5: Gọi R = f (u; v) g biểu thị các cặp sao cho v từ chối u tại một thời điểm nào đó trong một thực thi xed của thuật toán đề xuất.

Vì mỗi người đàn ông làm việc một cách có hệ thống theo danh sách ưu tiên của mình, nếu u được khớp với v khi kết thúc thuật toán, thì (u; v0) 2 R cho mọi v0 mà bạn thích v. Do đó, yêu cầu sau đây sẽ ngụ ý Định lý: với mọi (u; v) 2 R, không có cặp kết hợp ổn định nào lên u và v.

Chúng tôi chứng minh yêu cầu bằng cách cảm ứng về số lần lặp của thuật toán đề xuất. Ban đầu, R =; và không có gì để chứng minh. Đối với bước quy nạp, hãy xem xét việc lặp lại thuật toán đề xuất trong đó v từ chối u ủng hộ u0 | do đó, một trong những u; u0 đề xuất với v trong lần lặp này.

Vì u0 hoạt động một cách có hệ thống theo danh sách ưu tiên của anh ấy, nên với mọi v0 mà u0 thích v, (u0; v 0) đã có trong bộ R các đề xuất bị từ chối hiện tại. Theo giả thuyết quy nạp, không có cặp kết hợp ổn định nào kết hợp u0 với người phụ nữ mà anh ta thích v | trong mọi kết hợp ổn định, u0 được ghép với v hoặc ai đó ít được ưu tiên hơn. Vì v0 thích u0 hơn u và u0 thích v hơn bất kỳ ai khác mà anh ta có thể được kết hợp trong một kết hợp ổn định, không có kết hợp ổn định nào mà cặp u với v (nếu không u0; v sẽ tạo thành một cặp chặn).

Cũng có thể chỉ ra rằng thuật toán đề xuất đưa ra kết quả khớp ổn định tồi tệ nhất có thể theo quan điểm của phụ nữ | thuật toán khớp với mỗi v 2 V với người đàn ông xếp hạng thấp nhất l (v) 2 U mà v được khớp với bất kỳ kết hợp ổn định nào.

Giả sử danh sách ưu tiên của các đỉnh là riêng tư | thuật toán đề xuất DSIC? Đó là, một người đàn ông hay phụ nữ có bao giờ kết bạn với một người bạn đời tốt hơn theo sở thích không được báo cáo đúng hơn là theo sở thích được báo cáo trung thực? Vì đặc tính tối ưu nam của kết hợp ổn định được tính toán có thể gợi ý, thuật toán đề xuất là DSIC cho nam nhưng không dành cho nữ. Thuộc tính trước không phải là nhỏ để chứng minh, trong khi thuộc tính sau có thể được xác minh trong các ví dụ đơn giản