Ba bạn chọn câu lạc bộ. Có Robot, Mỹ thuật và Truyền thông. Mỗi câu lạc bộ chỉ còn một chỗ. Cả ba bạn đều có thứ tự thích riêng. Câu lạc bộ cũng xếp danh sách ưu tiên theo tiêu chí đã công bố.
Nếu cứ bốc thăm ghép cho đủ, có thể xảy ra chuyện An thích Robot hơn chỗ hiện tại, Robot cũng thích An hơn người đang giữ chỗ. Hai bên có lý do tự tìm đến nhau. Cặp như thế gọi là cặp chặn.
Cho phép giữ chỗ mà chưa chốt ngay
Thứ tự của các bạn, từ thích nhất xuống.
| Bạn | 1 | 2 | 3 |
|---|---|---|---|
| An | Robot | Truyền thông | Mỹ thuật |
| Bình | Robot | Mỹ thuật | Truyền thông |
| Chi | Mỹ thuật | Truyền thông | Robot |
Robot ưu tiên Bình, An, Chi. Mỹ thuật ưu tiên Chi, An, Bình. Truyền thông ưu tiên An, Chi, Bình.
Lượt đầu, An và Bình cùng xin Robot. Robot giữ chỗ tạm cho Bình và từ chối An. Chi xin Mỹ thuật và được giữ chỗ. Lượt hai, An xin lựa chọn kế tiếp là Truyền thông và được giữ chỗ. Không còn ai cần xin tiếp. Chốt Bình–Robot, Chi–Mỹ thuật, An–Truyền thông.
Đây là chấp nhận trì hoãn, hay thuật toán Gale–Shapley. Chỗ được giữ tạm vì vòng sau có thể có người ưu tiên hơn đến xin. Người bị từ chối chuyển xuống lựa chọn kế tiếp. Mỗi người chỉ xin một nơi một lần, nên số lượt xin có giới hạn.
Tại sao không có cặp chặn?
Bình và Chi đã vào nơi mình thích nhất, nên không muốn tự đi tìm nơi tốt hơn. An thích Robot hơn Truyền thông. An đã xin Robot rồi bị từ chối để Robot giữ Bình. Robot thích Bình hơn An. Vì thế An và Robot không thể cùng muốn bỏ kết quả hiện tại.
Lập luận cũng dùng được cho bảng dài hơn. Nếu bạn thích câu lạc bộ nào hơn chỗ cuối cùng của mình, bạn đã thử xin nơi ấy trước. Lúc bị từ chối, nơi đó giữ một người họ thích hơn. Qua các vòng, người được giữ chỉ có thể lên ưu tiên, nên đến cuối nơi ấy vẫn không muốn đổi sang bạn. Ổn định nghĩa là không có cặp chặn theo bảng ưu tiên. Muốn bàn công bằng, ta còn phải xem danh sách ưu tiên được lập thế nào và bên nào được quyền xin trước.
Tự thử
Giữ mọi thứ, nhưng Robot đổi danh sách ưu tiên thành An, Bình, Chi. Chạy lại các vòng.
Đáp án. Lượt đầu Robot giữ An và từ chối Bình. Mỹ thuật giữ Chi. Bình xin Mỹ thuật ở lượt kế tiếp nhưng Mỹ thuật ưu tiên Chi hơn. Bình chuyển sang Truyền thông và được nhận. Kết quả là An–Robot, Chi–Mỹ thuật, Bình–Truyền thông. Chỉ đổi ưu tiên ở Robot đã đổi luôn người vào Truyền thông.
Đọc tiếp trong series
- Bài trước. Bài 28 · Cơ chế VCG qua một hội trường ba câu lạc bộ cùng muốn dùng
- Bài sau. Bài 30 · Nghịch lý Condorcet khi cả lớp biểu quyết ba phương án
- Mục lục 35 bài Lý thuyết trò chơi
Bình luận