Cách phân phòng ký túc xá được giới nghiên cứu khuyên dùng nhiều nhất là bốc thăm thứ tự rồi lần lượt chọn: mỗi người bốc một số, người số 1 chọn phòng mình thích nhất, người số 2 chọn trong số còn lại, cứ thế đến hết. Cách này đơn giản, ai cũng nên chọn thật lòng, và kết quả không bỏ phí cơ hội đổi nào. Khó hơn là hai việc khác: xếp người đang ở cũ cùng người mới mà không ai thiệt, và ghép bạn cùng phòng, bài toán mà ngay từ năm 1962 Gale và Shapley đã chỉ ra có thể không có lời giải ổn định.
Ba bài toán khác nhau dưới cùng một chữ "phân phòng"
| Bài toán | Ai có gì | Cách làm hợp |
|---|---|---|
| Chia phòng trống cho người mới | Không ai có sẵn phòng, ai cũng có thứ tự ưa thích | Bốc thăm thứ tự, lần lượt chọn |
| Phân phòng khi có người ở cũ | Một số người đang giữ phòng, muốn đổi nếu được chỗ tốt hơn | Bốc thăm có bảo đảm cho người cũ (xem phần dưới) |
| Ghép bạn cùng phòng | Không ai có phòng; "món" để chia lại chính là con người | Thuật toán Irving, hoặc ghép theo tiêu chí rồi cho đổi |
Còn bài toán "phòng to phòng nhỏ thì chia tiền thuê thế nào" là chuyện chia tiền không ghen tị, thuộc một chủ đề khác; bài này chỉ bàn ai được phòng nào.
Bốc thăm thứ tự: tính tay xác suất
Ba sinh viên Giang, Hạnh, Khoa và ba phòng P1, P2, P3. Nguyện vọng:
- Giang: P1, P2, P3
- Hạnh: P1, P3, P2
- Khoa: P2, P1, P3
Ba người có 6 thứ tự bốc thăm, mỗi thứ tự xác suất 1/6. Liệt kê hết:
| Thứ tự | Người đầu chọn | Người thứ hai chọn | Người cuối nhận |
|---|---|---|---|
| Giang, Hạnh, Khoa | Giang: P1 | Hạnh: P3 | Khoa: P2 |
| Giang, Khoa, Hạnh | Giang: P1 | Khoa: P2 | Hạnh: P3 |
| Hạnh, Giang, Khoa | Hạnh: P1 | Giang: P2 | Khoa: P3 |
| Hạnh, Khoa, Giang | Hạnh: P1 | Khoa: P2 | Giang: P3 |
| Khoa, Giang, Hạnh | Khoa: P2 | Giang: P1 | Hạnh: P3 |
| Khoa, Hạnh, Giang | Khoa: P2 | Hạnh: P1 | Giang: P3 |
Cộng lại:
| Sinh viên | P1 | P2 | P3 | Được lựa chọn số 1 |
|---|---|---|---|---|
| Giang | 3/6 | 1/6 | 2/6 | 50% |
| Hạnh | 2/6 | 0 | 4/6 | 33% |
| Khoa | 0 | 5/6 | 1/6 | 83% |
Khoa thích P2, phòng ít người tranh, nên gần như luôn được. Hai người cùng muốn P1 thì chia nhau may rủi. Điều thú vị: Giang có 1/6 khả năng được P2 nhờ Khoa đứng sau, còn Hạnh không bao giờ được P2 vì Hạnh xếp P2 cuối cùng. Kết quả hoàn toàn đến từ nguyện vọng của chính mỗi người cộng với may rủi của lá thăm.
Vì sao nên chọn thật lòng
Đến lượt mình, bạn chọn trong số phòng còn lại; những người sau không ảnh hưởng tới bạn. Vậy chọn phòng mình thích nhất còn trống luôn là tốt nhất. Không có chỗ cho chiến thuật. Kết quả cũng hiệu quả: không có hai người nào cùng muốn đổi phòng cho nhau sau khi chọn xong, vì người chọn trước đã có phòng mình thích nhất trong số còn lại lúc đó.
So với "ai đăng ký trước được trước"
Nhiều nơi xếp phòng theo thứ tự thời gian đăng ký. Về toán, đó vẫn là "lần lượt chọn", chỉ khác thứ tự không do lá thăm quyết định mà do tốc độ: ai có mạng nhanh, rảnh đúng giờ mở cổng, có người nhà ngồi canh. Lợi thế ấy thường không liên quan gì tới việc ai cần phòng hơn. Bốc thăm, hoặc xếp theo đối tượng ưu tiên rõ ràng rồi bốc thăm trong cùng đối tượng, công bằng hơn và đỡ cảnh nghẽn hệ thống phút đầu.
Khi có người ở cũ: đừng để họ bỏ cuộc
Giả sử Tú đang ở phòng 1 từ năm trước. Năm nay có thêm hai bạn mới Uyên và Vy, và hai phòng trống là phòng 2, phòng 3. Nguyện vọng:
- Tú: phòng 2, phòng 1, phòng 3
- Uyên: phòng 1, phòng 2, phòng 3
- Vy: phòng 2, phòng 1, phòng 3
Nếu ban quản lý gom cả ba phòng lại cho bốc thăm thứ tự, Tú có thể bốc số cuối và bị đẩy xuống phòng 3, kém hơn chỗ đang ở. Biết vậy, Tú sẽ từ chối tham gia, giữ phòng 1. Nhưng Uyên lại thích phòng 1 nhất, Tú thì thích phòng 2 hơn phòng 1: một vụ đổi có lợi cho cả hai đã bị bỏ lỡ chỉ vì luật làm Tú sợ.
Atila Abdulkadiroğlu và Tayfun Sönmez (1999) đề xuất một luật tên rất dài mà dễ nhớ: "bạn xin phòng của tôi, tôi được lên lượt của bạn". Bốc thăm thứ tự như thường, nhưng khi ai đó muốn chọn đúng phòng của một người ở cũ chưa đến lượt, người ở cũ được đẩy lên chọn ngay trước người đó. Người ở cũ luôn có quyền giữ phòng mình, nên không bao giờ thiệt.
Chạy với thứ tự Uyên, Vy, Tú
- Uyên muốn phòng 1, đó là phòng của Tú. Tú được đẩy lên chọn trước: Tú chọn phòng 2 (vẫn trống).
- Phòng 1 giờ trống, Uyên nhận phòng 1.
- Vy muốn phòng 2, đã có người; phòng 1 cũng hết; Vy nhận phòng 3.
Kết quả: Tú phòng 2 (thích hơn chỗ cũ), Uyên phòng 1 (lựa chọn số một), Vy phòng 3.
Chạy với thứ tự Vy, Uyên, Tú
- Vy chọn phòng 2 (trống).
- Uyên muốn phòng 1 của Tú. Tú được đẩy lên: phòng 2 đã hết, Tú chọn giữ phòng 1.
- Uyên nhận phòng còn lại tốt nhất: phòng 3.
Lần này Tú chỉ giữ chỗ cũ, nhưng không bị đẩy xuống. Ở mọi thứ tự, Tú không bao giờ nhận phòng kém hơn phòng 1, nên Tú yên tâm tham gia, và nhờ Tú tham gia mà các vụ đổi có lợi mới có cơ hội xảy ra. Hai tác giả chứng minh luật này hiệu quả và không ai được lợi khi khai sai nguyện vọng; về bản chất, nó là sự kết hợp giữa bốc thăm thứ tự và thuật toán chu trình trao đổi đỉnh (top trading cycles).
Ghép bạn cùng phòng: khi không có lời giải ổn định
Ghép bạn cùng phòng khác ghép sinh viên với trường ở một điểm then chốt: không có hai phía. Ai cũng có thể ở với ai. Gale và Shapley đã nêu trong bài báo năm 1962 rằng với bài toán này, có thể không tồn tại cách ghép ổn định nào.
Ví dụ bốn bạn Tâm, Uy, Vĩnh, Xuân, cần ghép thành hai phòng đôi:
- Tâm: Uy, rồi Vĩnh, rồi Xuân
- Uy: Vĩnh, rồi Tâm, rồi Xuân
- Vĩnh: Tâm, rồi Uy, rồi Xuân
- Xuân: ai cũng được (cả ba người kia đều xếp Xuân cuối)
Chỉ có ba cách ghép. Thử từng cách:
| Cách ghép | Cặp muốn bỏ đi ở chung | Vì sao |
|---|---|---|
| Tâm–Uy, Vĩnh–Xuân | Uy và Vĩnh | Uy thích Vĩnh hơn Tâm; Vĩnh thích Uy hơn Xuân |
| Tâm–Vĩnh, Uy–Xuân | Tâm và Uy | Tâm thích Uy hơn Vĩnh; Uy thích Tâm hơn Xuân |
| Tâm–Xuân, Uy–Vĩnh | Vĩnh và Tâm | Vĩnh thích Tâm hơn Uy; Tâm thích Vĩnh hơn Xuân |
Ba người Tâm, Uy, Vĩnh thích nhau theo vòng tròn, và ai bị ghép với Xuân cũng có người sẵn lòng bỏ bạn cùng phòng hiện tại để về với mình. Không cách nào yên.
Thuật toán Irving
Năm 1985, Robert Irving công bố một thuật toán hai pha: pha đầu giống Gale–Shapley (mỗi người đề nghị, người nhận giữ tạm lời tốt nhất), pha sau lần lượt loại bỏ các "vòng xoay" trong bảng ưa thích. Thuật toán chạy nhanh và cho câu trả lời dứt khoát: hoặc tìm được một cách ghép ổn định, hoặc khẳng định không có cách nào. Với nhóm vài chục người, xác suất có lời giải ổn định thường khá cao, nhưng giảm dần khi nhóm rất lớn.
Ngoài đời người ta làm gì
Thực tế ít ký túc xá nào bắt sinh viên xếp hạng toàn bộ bạn cùng khoá. Những cách phổ biến hơn:
- Cho đăng ký theo nhóm bạn đã quen, rồi nhóm bốc thăm thứ tự chọn phòng như một người.
- Ghép theo vài tiêu chí sinh hoạt: giờ ngủ, hút thuốc hay không, mức gọn gàng, ngành học.
- Sau vài tuần mở "chợ đổi phòng": ai muốn đổi ghi danh, ban quản lý tìm các vòng đổi cùng có lợi.
Cách thứ ba chính là chu trình trao đổi đỉnh áp dụng ở quy mô nhỏ: một vòng ba, bốn người thường làm được điều mà không cặp đổi tay đôi nào làm được.
Góc nhìn hôm nay: gợi ý cho ban quản lý và cho nhóm thuê trọ
- Công bố luật trước. Ưu tiên theo đối tượng nào, bốc thăm thế nào, người ở cũ được bảo đảm gì. Luật rõ thì người ta mới yên tâm khai thật.
- Bảo đảm cho người ở cũ theo tinh thần "bạn xin phòng của tôi, tôi được lên lượt của bạn", để họ không ngại tham gia.
- Bốc thăm công khai, có người chứng kiến hoặc dùng số ngẫu nhiên có thể kiểm lại.
- Chấp nhận rằng ghép bạn cùng phòng không hoàn hảo và luôn có kênh đổi phòng sau đó.
Nhóm bạn thuê chung một căn nhiều phòng cũng làm được y hệt: bốc thăm thứ tự chọn phòng, còn chuyện phòng to trả nhiều hơn bao nhiêu thì tính riêng bằng một phương pháp chia tiền.
Câu hỏi thường gặp
Cách phân phòng ký túc xá công bằng nhất là gì?
Với phòng trống và người mới, cách được khuyên dùng là bốc thăm thứ tự rồi lần lượt chọn. Ai cũng có cơ hội như nhau trước lá thăm, chọn thật lòng là tốt nhất, và sau khi chọn không có hai người nào cùng muốn đổi phòng cho nhau.
Bốc thăm chọn phòng có nên chọn phòng ít người tranh để chắc ăn không?
Không cần. Đến lượt bạn thì chỉ còn những phòng chưa ai lấy, và người sau không ảnh hưởng tới bạn, nên cứ chọn phòng mình thích nhất còn trống. Chiến thuật né phòng "hot" chỉ có ý nghĩa ở các luật xét khác, không phải ở bốc thăm lần lượt chọn.
Người đang ở phòng cũ có bị thiệt khi tham gia bốc thăm lại không?
Có thể, nếu luật gom hết phòng để bốc lại từ đầu. Luật "bạn xin phòng của tôi, tôi được lên lượt của bạn" của Abdulkadiroğlu và Sönmez bảo đảm người ở cũ luôn được giữ phòng mình, nên họ chỉ có thể được đổi lên chứ không bị đẩy xuống.
Bài toán ghép bạn cùng phòng có luôn có lời giải không?
Không. Khác với ghép hai phía như sinh viên và trường, ghép bạn cùng phòng có thể không có cách ghép ổn định nào, như ví dụ bốn người thích nhau theo vòng tròn. Thuật toán Irving năm 1985 tìm được cách ghép ổn định nếu có, hoặc cho biết chắc là không có.
Đăng ký ký túc xá theo kiểu ai nhanh tay được trước có công bằng không?
Về toán, đó vẫn là lần lượt chọn, chỉ là thứ tự do tốc độ quyết định thay vì lá thăm. Lợi thế về mạng nhanh hay thời gian rảnh thường không liên quan tới nhu cầu, nên bốc thăm trong cùng nhóm ưu tiên thường được coi là công bằng hơn.