Lập trình

1.  Case Study: Kidney Exchange

Nhiều người yếu do suy thận và cần ghép thận. Hiện tại, danh sách chờ đợi của Mỹ cho thận có khoảng 100.000 người trên đó. Một ý tưởng cũ, cũng được sử dụng cho các cơ quan khác, là người hiến tặng đã chết | khi ai đó chết và là người hiến tạng đã đăng ký, nội tạng của họ có thể được ghép vào người khác. Một điểm đặc biệt của thận là một người khỏe mạnh có hai người trong số họ và có thể sống sót chỉ với một người trong số họ. Điều này tạo ra khả năng của những người hiến tạng sống, chẳng hạn như một thành viên gia đình của bệnh nhân có nhu cầu.

Thật không may, có một người hiến thận sống không phải lúc nào cũng đủ | đôi khi một cặp người hiến tặng không tương thích, có nghĩa là thận của người hiến không có khả năng hoạt động tốt ở bệnh nhân. Các loại máu và mô là thủ phạm chính cho sự không tương thích. Ví dụ, một bệnh nhân có nhóm máu O chỉ có thể nhận thận từ người hiến có cùng nhóm máu và tương tự, người hiến AB chỉ có thể hiến cho bệnh nhân AB.

Giả sử bệnh nhân P1 không tương thích với người hiến D1 vì họ có nhóm máu A và B tương ứng. Giả sử P2 và D2 ​​ở trong thuyền đối diện, có nhóm máu B và A tương ứng (Hình 1). Mặc dù (P1, D1) có thể chưa bao giờ gặp (P2, D2), trao đổi các nhà tài trợ có vẻ như là một ý tưởng khá hay | P1 có thể lấy thận từ D2 và P2 từ D1. Đây được gọi là trao đổi thận.

Một vài trao đổi thận đã được thực hiện, trên cơ sở ad hoc, vào khoảng đầu thế kỷ này. Những thành công biệt lập này cho thấy rõ sự cần thiết phải trao đổi thận trên toàn quốc, nơi các cặp người hiến tặng bệnh nhân không tương thích có thể đăng ký và được kết hợp với những người khác. Làm thế nào một trao đổi như vậy nên được thiết kế? Mục tiêu của một cuộc trao đổi như vậy là làm dày thị trường trao đổi thận để cho phép càng nhiều trận đấu càng tốt.

Trao đổi thận quốc gia mọc lên vào khoảng giữa thập kỷ trước. Chúng tôi sẽ đề cập đến một số ý tưởng thiết kế ban đầu cho các trao đổi này, cũng như các thách thức hiện tại. Những trao đổi này và các thuật toán cơ bản của họ đã khá thành công, cho phép hàng ngàn ca ghép thận thành công mỗi năm.

Hiện tại, bồi thường cho việc hiến tạng là bất hợp pháp tại Hoa Kỳ (và ở mọi quốc gia trừ Iran). Trao đổi thận là hợp pháp. Do đó, trao đổi thận là một ứng dụng lý tưởng cho thiết kế cơ điện tử mà không có tiền, cho bất kỳ vấn đề khuyến khích nào có liên quan (và có một vài). Thật thú vị khi suy đoán về việc liệu thị trường tiền tệ cho thận có tồn tại ở bất kỳ quốc gia phương Tây nào trong 10 năm hay không. (Iran không có danh sách chờ thận.)

1.1 Ý tưởng số 1: Sử dụng thuật toán chu kỳ giao dịch hàng đầu

• Phần này và phần tiếp theo bao gồm hai bài báo tương đối sớm của Roth, S • onmez và Unver [5, 6] đang trong các cơn bão não về việc thay đổi thận quốc gia tương thích khuyến khích có thể như thế nào. Trong bài báo đầu tiên [5], bao gồm nghiên cứu được thực hiện trước khi các tác giả nói chuyện nhiều với các bác sĩ, đã ủng hộ Thuật toán chu kỳ giao dịch hàng đầu (TTCA) từ bài giảng cuối cùng như một điểm khởi đầu. Ở dạng cơ bản nhất, sự tương ứng là giữa các cặp nhà ban đầu của tác nhân trong vấn đề nhà ở và các cặp nhà tài trợ bệnh nhân trong vấn đề trao đổi thận.

Ngôi nhà ban đầu của một đại lý tương ứng với nhà tài trợ sống không tương thích của nó. Vấn đề nhà ở giả định rằng mỗi đại lý có tổng đơn đặt hàng đối với nhà ở; trong trao đổi thận, việc đặt hàng các nhà tài trợ theo xác suất ước tính rằng thận của họ có thể được ghép thành công vào bệnh nhân là điều tự nhiên (dựa trên nhóm máu, loại mô, v.v.).

Mục tiêu của việc áp dụng TTCA là để thực hiện các chu kỳ như trong Hình 2, trong đó với các cặp người hiến tặng bệnh nhân như trong Hình 1, mỗi bệnh nhân chỉ đến nhà tài trợ của người khác như yêu thích của mình. Các nhà tài trợ định vị thực theo chu kỳ này là trao đổi thận thuận lợi xác định trước đó. Tổng quát hơn, các nhà tài trợ được phân bổ lại cho bệnh nhân để mọi người đều tập thể càng tốt càng tốt.

 Vấn đề trao đổi thận thực tế phức tạp hơn theo nhiều cách. Chúng tôi đầu tiên thảo luận về một phần mở rộng có thể được cung cấp theo cách tiếp cận TTCA, và sau đó hai

những thách thức thúc đẩy cải cách vấn đề. Việc mở rộng TTCA trong [5] xử lý, ngoài các cặp nhà tài trợ bệnh nhân không tương thích, bệnh nhân không có người hiến còn sống (một đại lý không có nhà ban đầu) và người hiến tặng đã chết (nhà không có chủ sở hữu ban đầu). Thuật toán mới phân bổ theo các chu kỳ như trong TTCA và cũng dọc theo các chuỗi phù hợp (nghĩa là, các đường dẫn). Các chuỗi được cung cấp được chọn theo đúng cách, thuật toán vẫn là DSIC | vì vậy không có bệnh nhân (hoặc bác sĩ của bệnh nhân) có thể nhập sai thông tin để tăng xác suất ước tính cho ca ghép thành công.1

Vấn đề tiếp theo với thuật toán TTCA là một công cụ giải quyết trong bối cảnh trao đổi thận: các chu kỳ mà việc phân bổ lại được thực hiện có thể kéo dài tùy ý. Ví dụ, trong lần lặp đầu tiên của TTCA, có thể các cung tương ứng với các nhà tài trợ được ưu tiên tạo thành một chu kỳ Hamilton trên các cặp nhà tài trợ bệnh nhân (Hình 3).

Tại sao chu kỳ dài là một vấn đề? Xem xét đầu tiên một chu kỳ có độ dài hai (Hình 2). Lưu ý điều này đã tương ứng với bốn ca phẫu thuật | hai để lấy thận của các nhà tài trợ và hai để cấy ghép chúng cho bệnh nhân. Hơn nữa, bốn cuộc phẫu thuật này phải xảy ra đồng thời. Ưu đãi là lý do: trong ví dụ trong Hình 1, nếu các ca phẫu thuật cho P1 và D2 ​​xảy ra đầu tiên, có nguy cơ D1 sẽ từ bỏ việc hiến thận của mình cho P2. Một vấn đề là P1 không công bằng có thận \ miễn phí; "vấn đề nghiêm trọng hơn nhiều là P2 vẫn bị bệnh như trước đây và vì người hiến tặng D2 đã hiến thận, P2 không thể tham gia trao đổi thận nữa. nguy cơ này, không ai muốn thử nghiệm các ca phẫu thuật không đồng thời trong trao đổi thận.2 Hạn chế của phẫu thuật đồng thời | với mỗi ca phẫu thuật cần phòng phẫu thuật riêng, đội phẫu thuật, v.v ... | thúc đẩy duy trì chu kỳ tái phân bổ càng nhỏ càng tốt.

Bài phê bình cuối cùng của chúng tôi về cách tiếp cận TTCA là việc ưu tiên mô hình hóa khi đặt hàng toàn bộ các nhà tài trợ còn sống là quá mức: theo kinh nghiệm, bệnh nhân không thực sự quan tâm đến quả thận nào miễn là phù hợp với họ. Do đó, sở thích nhị phân so với các nhà tài trợ là phù hợp hơn.

1.2 Ý tưởng 2: Sử dụng thuật toán so khớp

Cách tiếp cận thứ hai [6], được thúc đẩy bởi các mục tiêu song sinh của sở thích nhị phân và chu kỳ địa điểm thực ngắn, là sử dụng kết hợp. Hãy nhớ rằng một kết hợp của đồ thị vô hướng (V; E) là tập con của các cạnh F E sao cho không có hai cạnh nào của F chia sẻ một điểm cuối.

Biểu đồ liên quan để trao đổi thận có tập đỉnh V tương ứng với các cặp bệnh nhân - người hiến không tương thích (một đỉnh trên mỗi cặp) và cạnh không bị giới hạn giữa các đỉnh (P 1; D1) và (P 2; D2) khi và chỉ khi P1 và D2 tương thích và P2 và D1 tương thích. Do đó, ví dụ trong Hình 1 tương ứng với biểu đồ vô hướng đơn giản trong Hình 4. Chúng tôi đưa ra các giải pháp tối ưu để phù hợp với biểu đồ này có số lượng thẻ tối đa | đó là chúng tôi muốn sắp xếp càng nhiều ca ghép thận tương thích càng tốt. Bằng cách hạn chế tập hợp khả thi thành các đối sánh của biểu đồ này, chúng tôi đang hạn chế trao đổi thận theo cặp, và do đó \ chỉ "4 ca phẫu thuật đồng thời, như trong Hình 1.3

Mô hình của chúng tôi cho các tác nhân là mỗi đỉnh i có một Ei thực sự của các cạnh sự cố và có thể báo cáo bất kỳ tập hợp con Fi Ei nào cho một cơ chế. Trao đổi thận được đề xuất có thể bị từ chối bởi một bệnh nhân vì bất kỳ lý do gì, vì vậy một cách để thực hiện một báo cáo sai là từ chối trao đổi trong Ei nFi. Tất cả những gì một bệnh nhân quan tâm đang được kết hợp với một nhà tài trợ tương thích. Mục tiêu thiết kế cơ chế của chúng tôi là tính toán một giải pháp tối ưu (nghĩa là phù hợp với số lượng thẻ tối đa) và là DSIC, nghĩa là đối với mọi đại lý, báo cáo toàn bộ cạnh của nó là một chiến lược vượt trội.

Với mục tiêu thiết kế của chúng tôi, cơ chế phải có dạng sau.

1. Collect a report F_i from each agent i.

2. Form the edge setE = f(i; j) : (i; j) 2 F_i \ F_j g. That is, include edge (i; j) if and only if both endpoints agree to the exchange.

3. Return a maximum-cardinality matching of the graph G = (V; E), where V is the (known) set of patient-donor pairs.

Cơ chế chưa hoàn toàn cụ thể, vì có thể có nhiều lựa chọn cho một kết hợp maxi-mum trong bước (3). Bắt đúng tie-break là rất quan trọng để đạt được DSIC. Có hai giác quan trong đó sự kết hợp tối đa của đồ thị có thể không phải là duy nhất. Đầu tiên, di erent bộ cạnh có thể được sử dụng để khớp với cùng một đỉnh; xem hình 5

 

Vì một đỉnh không quan tâm đến việc nó khớp với ai, miễn là nó được khớp, không có lý do để phân biệt giữa các khớp di erent khớp với cùng một đỉnh. Nhiều dấu hiệu hơn - thường xuyên, di erent tối đa các kết quả cardinality có thể khớp với các tập con erent của các đỉnh. Ví dụ, trong ngôi sao (Hình 6), đỉnh 1 có trong mọi kết hợp tối đa, nhưng một và chỉ một trong số các nan hoa sẽ được chọn. Làm thế nào chúng ta nên chọn cái nào để trở về?

(còn tiếp)