Top Trading Cycles (chu trình trao đổi đỉnh, thường viết tắt TTC) là thuật toán đổi chác cho những nhóm mà mỗi người đang giữ một thứ (một căn phòng, một chỗ làm, một suất học) và muốn đổi lấy thứ mình thích hơn. Mỗi người chỉ tay vào món mình thích nhất trong số còn lại; trong đồ thị ấy luôn có ít nhất một vòng khép kín, những người trong vòng đổi cho nhau rồi rời đi, lặp lại với phần còn lại. Thuật toán xuất hiện trong bài báo của Lloyd Shapley và Herbert Scarf năm 1974, được ghi công ý tưởng cho David Gale, và là nền của ghép thận chéo lẫn một số hệ thống phân trường.
Bài toán: chợ đổi không dùng tiền
Shapley và Scarf gọi mô hình của mình là "thị trường nhà ở": n người, mỗi người đang ở một căn nhà, ai cũng có thứ tự ưa thích về mọi căn. Không ai được mua bán, chỉ được đổi. Câu hỏi: đổi thế nào để không ai bị thiệt so với giữ nguyên, và không nhóm nào có lý do tách ra tự đổi riêng với nhau?
Bài toán này có ở khắp nơi, dưới dạng không ai gọi là "nhà":
- Sinh viên ký túc xá đã được xếp phòng, đầu năm học muốn đổi phòng cho nhau.
- Nhân viên các chi nhánh muốn hoán đổi nơi làm việc cho gần nhà.
- Người bệnh có người hiến thận nhưng không hợp, muốn đổi người hiến với cặp khác.
- Đồng nghiệp đã được phân ca muốn đổi ca cho nhau.
Cách làm tự phát quen thuộc là "đổi tay đôi": hai người tìm nhau, cùng có lợi thì đổi. Nhưng như ví dụ dưới đây cho thấy, đổi tay đôi bỏ sót rất nhiều cơ hội, và có khi khoá chặt cả nhóm ở một kết quả kém hơn.
Thuật toán, bốn bước
- Mỗi người chỉ tay vào chủ của món mình thích nhất trong số món còn trên "chợ" (có thể là chính mình).
- Vì có hữu hạn người và ai cũng chỉ vào đúng một người, đi theo các mũi tên chắc chắn sẽ quay lại một người đã gặp: luôn có ít nhất một vòng.
- Mỗi người trong vòng nhận món mình đang chỉ vào. Cả vòng rời chợ cùng món của họ.
- Những người còn lại chỉ tay lại vào món tốt nhất trong số còn sót. Lặp tới khi hết người.
Một người chỉ vào chính mình là một vòng độ dài một: người đó giữ món của mình và rời chợ.
Tính tay: sáu giáo viên muốn đổi nơi công tác
Sáu giáo viên Hoa, Kiên, Lâm, Mai, Nhân, Oanh, mỗi người đang dạy ở một trường. Giả sử các bên được phép hoán đổi khi cùng đồng ý (thực tế còn cần cơ quan quản lý duyệt). Ta gọi "trường của Hoa" là trường Hoa đang dạy. Thứ tự ưa thích, những trường không ghi coi như kém hơn chỗ hiện tại:
| Giáo viên | Thích nhất | Thứ hai | Thứ ba | |
|---|---|---|---|---|
| Hoa | trường Lâm | trường Kiên | giữ chỗ cũ | |
| Kiên | trường Hoa | trường Mai | giữ chỗ cũ | |
| Lâm | trường Mai | giữ chỗ cũ | ||
| Mai | trường Kiên | giữ chỗ cũ | ||
| Nhân | trường Hoa | trường Oanh | giữ chỗ cũ | |
| Oanh | trường Lâm | trường Nhân | giữ chỗ cũ |
Vòng 1
Mỗi người chỉ vào chủ của trường mình thích nhất:
- Hoa → Lâm, Kiên → Hoa, Lâm → Mai, Mai → Kiên, Nhân → Hoa, Oanh → Lâm.
Đi theo mũi tên từ Hoa: Hoa → Lâm → Mai → Kiên → Hoa. Một vòng bốn người. Hoa sang trường Lâm, Lâm sang trường Mai, Mai sang trường Kiên, Kiên sang trường Hoa. Cả bốn được lựa chọn số một và rời chợ cùng bốn trường đó.
Nhân và Oanh cũng chỉ vào Hoa và Lâm, nhưng họ không nằm trong vòng; mũi tên của họ "treo" vào vòng mà không khép lại. Trường họ muốn đã được dùng.
Vòng 2
Còn lại Nhân và Oanh với hai trường của chính họ. Nhân chỉ vào Oanh (lựa chọn số hai còn sót), Oanh chỉ vào Nhân. Vòng hai người: hai người đổi trường cho nhau.
| Giáo viên | Kết quả | Là lựa chọn số |
|---|---|---|
| Hoa | trường Lâm | 1 |
| Kiên | trường Hoa | 1 |
| Lâm | trường Mai | 1 |
| Mai | trường Kiên | 1 |
| Nhân | trường Oanh | 2 |
| Oanh | trường Nhân | 2 |
So với đổi tay đôi
Trong chợ đổi tay đôi, kết quả tuỳ ai gặp ai trước. Nếu Hoa và Kiên gặp nhau trước: Kiên muốn trường Hoa nhất, Hoa xếp trường Kiên thứ hai, cả hai cùng lợi nên đổi ngay. Sau đó Lâm muốn trường Mai, nhưng Mai chỉ muốn trường Kiên (giờ là chỗ của Hoa), mà Hoa không muốn trường Mai. Không còn cặp nào cùng lợi; Lâm và Mai đứng yên, Hoa dừng ở lựa chọn số hai. Nếu Mai và Kiên gặp nhau trước thì Mai được trường Kiên, Kiên nhận lựa chọn số hai là trường Mai, và đến lượt Hoa, Lâm mắc kẹt. Cả hai kịch bản đều kém TTC, nơi cả bốn người được lựa chọn số một nhờ một vòng bốn người mà không cặp hai người nào nhìn thấy.
Những tính chất làm nên tên tuổi của TTC
| Tính chất | Nghĩa là | Ai chứng minh |
|---|---|---|
| Không ai thiệt so với giữ nguyên | Mỗi người luôn có thể chỉ vào chính mình, nên không bao giờ nhận món kém hơn món đang có | Hiển nhiên từ cách làm |
| Hiệu quả Pareto | Không có cách đổi lại nào làm ai đó khá hơn mà không làm người khác kém đi | Shapley và Scarf, 1974 |
| Ổn định theo nhóm (thuộc lõi) | Không nhóm nào tách ra tự đổi riêng mà tất cả cùng khá hơn; kết quả này là duy nhất | Shapley và Scarf; tính duy nhất do Roth và Postlewaite, 1977 |
| Khai thật là tốt nhất | Không ai được lợi khi khai sai thứ tự ưa thích | Roth, 1982 |
Năm 1994, Jinpeng Ma chứng minh thêm một điều mạnh hơn: trong thị trường nhà ở, TTC là cách làm duy nhất thoả đồng thời ba yêu cầu "không ai thiệt", "hiệu quả" và "khai thật là tốt nhất". Muốn cả ba, chỉ có TTC.
Vì sao người ở vòng đầu không thể được lợi khi khai sai
Trực giác: món bạn thích nhất hoặc đã được lấy trong một vòng trước khi bạn có cơ hội (và khai gì cũng không đổi được điều đó), hoặc vẫn còn trên chợ, khi đó chỉ vào nó là cách duy nhất để có nó. Chỉ vào món khác sớm chỉ khiến bạn rời chợ với món kém hơn.
Từ đổi nhà sang phân trường
Năm 2003, Atila Abdulkadiroğlu và Tayfun Sönmez mở rộng TTC cho bài toán phân học sinh vào trường. Lúc này trường không có "chủ", nhưng có thứ tự ưu tiên học sinh (theo khoảng cách, anh chị đang học cùng trường, điểm…). Mỗi học sinh chỉ vào trường mình thích nhất còn chỗ; mỗi trường chỉ vào học sinh có ưu tiên cao nhất của nó; vòng nào khép lại thì học sinh trong vòng nhận trường mình chỉ.
Thử với ba học sinh 1, 2, 3 và ba trường a, b, c, mỗi trường một chỗ. Ưu tiên ở trường a: 1, rồi 3, rồi 2; ở trường b: 2, rồi 1, rồi 3; ở trường c: 3 đứng đầu. Nguyện vọng: học sinh 1 thích b hơn a; học sinh 2 thích a hơn b; học sinh 3 thích a, rồi c.
- Chấp nhận hoãn (Gale–Shapley) cho: 1–a, 2–b, 3–c. Ổn định, nhưng 1 và 2 cùng muốn đổi chỗ cho nhau.
- TTC: 1 chỉ b, b chỉ 2, 2 chỉ a, a chỉ 1, vòng khép: 1–b, 2–a. Sau đó 3 vào c. Ai cũng thích kết quả này hơn hoặc bằng, nhưng học sinh 3 có ưu tiên ở a cao hơn học sinh 2 mà lại không được vào a.
Đó là đánh đổi cốt lõi: TTC hiệu quả nhưng có thể "vượt mặt" người có ưu tiên cao hơn; chấp nhận hoãn tôn trọng ưu tiên nhưng có thể bỏ phí những vụ đổi cùng có lợi. Không cơ chế nào có cả hai.
Trong thực tế, phần lớn các thành phố chọn chấp nhận hoãn. Khi Boston cân nhắc năm 2005, một lý do được nêu là việc học sinh "đổi ưu tiên" cho nhau khó giải thích với phụ huynh: ưu tiên vào trường gần nhà của con tôi lại được đem đổi cho người khác. New Orleans từng dùng TTC trong hệ thống tuyển sinh thống nhất năm đầu tiên rồi chuyển sang chấp nhận hoãn. Ở ghép thận chéo thì ngược lại: mỗi cặp thật sự "sở hữu" quả thận của người hiến đi cùng, nên tư duy chu trình trao đổi là tự nhiên.
Góc nhìn hôm nay: áp dụng cho nhóm của bạn
TTC rất hợp với những cuộc đổi chỗ nhỏ trong cơ quan, lớp học, ký túc xá, nơi mỗi người đã có sẵn một chỗ:
- Mỗi người ghi ra những chỗ mình thích hơn chỗ đang có, theo thứ tự.
- Vẽ mũi tên từ mỗi người tới người đang giữ chỗ mình thích nhất.
- Tìm vòng, cho cả vòng đổi, gạch họ khỏi bảng; vẽ lại mũi tên cho người còn lại.
Với dưới hai mươi người, làm trên một tờ giấy khổ lớn mất chừng mười lăm phút. Người muốn đọc thêm có thể tìm bài gốc "On Cores and Indivisibility" của Shapley và Scarf (Journal of Mathematical Economics, 1974), và "School Choice: A Mechanism Design Approach" của Abdulkadiroğlu và Sönmez (2003).
Câu hỏi thường gặp
Top Trading Cycles là gì?
Là thuật toán đổi chác trong đó mỗi người chỉ vào chủ của món mình thích nhất, những người tạo thành vòng khép kín đổi món cho nhau rồi rời đi, lặp lại với phần còn lại. Kết quả hiệu quả, không ai thiệt so với giữ nguyên, và khai thật thứ tự ưa thích là tốt nhất.
Ai nghĩ ra thuật toán Top Trading Cycles?
Thuật toán được công bố trong bài báo của Lloyd Shapley và Herbert Scarf năm 1974 về "thị trường nhà ở"; hai tác giả ghi công ý tưởng cho David Gale. Shapley nhận giải Nobel Kinh tế năm 2012, một phần vì các công trình này.
Top Trading Cycles khác Gale–Shapley thế nào?
TTC cho kết quả hiệu quả, không ai có thể khá hơn mà không làm người khác thiệt, nhưng có thể để người ưu tiên thấp vào trường mà người ưu tiên cao muốn. Gale–Shapley tôn trọng ưu tiên tuyệt đối nhưng đôi khi bỏ lỡ những vụ đổi cùng có lợi. Đây là đánh đổi không tránh được.
Vì sao trong TTC luôn có ít nhất một vòng?
Vì mỗi người chỉ vào đúng một người và số người là hữu hạn. Đi theo mũi tên mãi thì sớm muộn phải quay lại một người đã gặp, tạo thành vòng; người chỉ vào chính mình là vòng độ dài một.
TTC được dùng ở đâu ngoài đời?
Ý tưởng chu trình trao đổi là nền của ghép thận chéo, nơi các cặp người bệnh – người hiến đổi người hiến theo vòng. Nó cũng từng được dùng trong phân trường ở New Orleans và hợp với các cuộc đổi phòng, đổi chỗ làm, đổi ca trong nhóm nhỏ.