Chia không ghen tị cho bốn người trở lên là bài toán mở suốt hơn ba mươi năm sau lời giải ba người của Selfridge–Conway. Năm 1995, Steven Brams và Alan Taylor công bố quy trình hữu hạn đầu tiên cho số người bất kỳ, nhưng số bước có thể lớn không giới hạn tuỳ khẩu vị. Năm 2016, Haris Aziz và Simon Mackenzie đưa ra quy trình có giới hạn trên cho mọi số người, dù giới hạn ấy lớn tới mức chỉ có ý nghĩa lý thuyết.
Vì sao từ bốn người trở lên lại khó
Thuật toán Selfridge–Conway cho ba người dựa vào một mẹo: sau vòng chia đầu, người cắt có ưu thế không thể đảo ngược đối với người giữ miếng bị gọt. Theo người cắt, miếng gọt cộng toàn bộ phần vụn mới bằng miếng của mình, nên dù phần vụn chia thế nào, người cắt cũng không bao giờ ghen người kia. Nhờ đó, khi chia phần vụn chỉ còn phải lo cho ít quan hệ hơn.
Với bốn người, có 12 quan hệ "người này có ghen người kia không" (mỗi người nhìn sang ba người khác). Một vòng chia kiểu Selfridge–Conway chỉ tạo ra được một vài ưu thế như vậy, còn lại phần vụn mà nhiều cặp vẫn đang so bì. Chia phần vụn lại sinh ra phần vụn mới. Không có gì bảo đảm sau một số vòng cố định thì mọi quan hệ đã được "khoá".
Còn một rào cản sâu hơn: năm 2008, Walter Stromquist chứng minh rằng nếu đòi mỗi người một miếng liền, không có quy trình hữu hạn nào chia không ghen tị cho ba người trở lên. Mọi thuật toán rời rạc cho bài toán này phải chấp nhận miếng rời.
Đo bằng "câu hỏi": thước đo của dân khoa học máy tính
Để so sánh thuật toán, người ta dùng mô hình của Jack Robertson và William Webb (1998). Thuật toán chỉ được làm hai việc với người tham gia:
- Hỏi đánh giá: "đoạn từ a tới b đáng bao nhiêu theo bạn?"
- Hỏi cắt: "bắt đầu từ a, hãy đánh dấu điểm b sao cho đoạn a–b đáng đúng x theo bạn."
Độ phức tạp là số câu hỏi trong trường hợp xấu nhất. Một quy trình là có giới hạn nếu số câu hỏi chỉ phụ thuộc vào số người n, không phụ thuộc vào khẩu vị cụ thể của họ.
Brams–Taylor 1995: hữu hạn nhưng không giới hạn
Bài "An envy-free cake division protocol" của Brams và Taylor đăng trên American Mathematical Monthly năm 1995. Quy trình của họ, rút gọn tới mức có thể kể:
- Chạy một vòng "lõi": một người cắt bánh thành nhiều miếng mà mình thấy bằng nhau (nhiều hơn số người), những người khác lần lượt gọt bớt để tạo ra các miếng ngang nhau theo họ, rồi mọi người chọn theo thứ tự định sẵn. Sau vòng lõi, phần đã chia ra không ai ghen ai, nhưng còn lại phần vụn.
- Mỗi vòng lõi được thiết kế để tạo thêm ưu thế không thể đảo ngược: một người thấy mình hơn người kia một khoảng ít nhất bằng toàn bộ phần vụn còn lại.
- Lặp lại vòng lõi trên phần vụn. Khi mọi cặp cần thiết đã có ưu thế, phần vụn cuối cùng có thể chia bằng một bước đơn giản mà không phá vỡ sự không ghen tị.
Vấn đề nằm ở bước 3: bao nhiêu vòng thì đủ? Câu trả lời phụ thuộc vào việc khẩu vị của mọi người khác nhau thế nào. Nếu hai người có khẩu vị gần như trùng nhau, phần vụn co lại rất chậm theo cách họ đánh giá, và có thể phải lặp rất nhiều vòng. Với bất kỳ con số N nào, người ta dựng được những khẩu vị khiến quy trình cần hơn N bước. Vì vậy quy trình được gọi là hữu hạn nhưng không giới hạn: chắc chắn kết thúc, nhưng không biết trước lúc nào.
Ví dụ tính tay về ưu thế không thể đảo ngược
Bốn người An, Bình, Chi, Dũng chia một vật. Sau một vòng, phần đã chia và phần vụn được chấm theo đánh giá của An như sau (tổng 100):
| Theo An | Phần của An | Phần của Bình | Phần của Chi | Phần của Dũng | Phần vụn |
|---|---|---|---|---|---|
| Điểm | 28 | 16 | 25 | 23 | 8 |
- An hơn Bình 28 − 16 = 12 điểm. Phần vụn chỉ đáng 8. Dù Bình được trọn phần vụn, Bình cũng chỉ lên 24 theo An, vẫn dưới 28. An có ưu thế không thể đảo ngược với Bình.
- An hơn Chi 3 điểm, hơn Dũng 5 điểm. Cả hai khoảng cách đều nhỏ hơn 8. Nếu Chi hoặc Dũng được quá nhiều phần vụn, An có thể ghen. Chưa khoá.
Muốn khoá hết, phần vụn phải co lại dưới 3 điểm theo An, hoặc phải chia phần vụn sao cho Chi và Dũng mỗi người không được quá 3 và 5 điểm theo An. Mỗi vòng lõi làm phần vụn nhỏ đi; Brams–Taylor lặp lại cho tới khi đủ. Với An như bảng trên, chỉ cần vài vòng. Nhưng nếu An đánh giá phần của Chi chỉ kém phần mình 0,01 điểm, sẽ phải lặp cho tới khi phần vụn dưới 0,01, và đó là chỗ số vòng phình ra không kiểm soát.
Bốn người có giới hạn: Aziz–Mackenzie 2016
Năm 2016, Haris Aziz và Simon Mackenzie, khi đó làm việc ở Úc, công bố hai kết quả liên tiếp:
- Tại hội nghị STOC 2016: quy trình chia không ghen tị có giới hạn cho bốn người, dùng không quá khoảng 200 câu hỏi. Về sau một nhóm tác giả khác rút xuống còn 171 câu hỏi (2018).
- Tại hội nghị FOCS 2016: quy trình có giới hạn cho số người bất kỳ. Giới hạn là một tháp luỹ thừa sáu tầng của n: n mũ (n mũ (n mũ (n mũ (n mũ n)))).
Để hình dung tháp sáu tầng: với n = 2, tháp hai tầng 2 mũ 2 là 4, ba tầng là 2 mũ 4 = 16, bốn tầng là 2 mũ 16 = 65.536, năm tầng là 2 mũ 65.536, một con số có gần 20 nghìn chữ số. Tháp sáu tầng còn lớn hơn thế không thể tả. Với n = 4 thì càng khỏi nói. Không ai định chạy quy trình này ngoài đời; giá trị của nó là chứng minh rằng có giới hạn, đóng lại một câu hỏi mở từ thập niên 1960.
Ý tưởng then chốt của Aziz và Mackenzie là chủ động tạo ra ưu thế không thể đảo ngược một cách có hệ thống, không chờ khẩu vị "tình cờ" thuận lợi, và chứng minh rằng sau một số bước chỉ phụ thuộc n, mọi người đều có đủ ưu thế để phần vụn còn lại chia được một cách an toàn.
Cận dưới: không thể nhanh tuỳ ý
Ở chiều ngược lại, năm 2009 Ariel Procaccia chứng minh rằng mọi quy trình chia không ghen tị trong mô hình Robertson–Webb cần ít nhất bậc n bình phương câu hỏi trong trường hợp xấu nhất. So với chia tương xứng, vốn chỉ cần bậc n log n câu hỏi (thuật toán Even–Paz), thì không ghen tị đắt hơn hẳn về bản chất. Khoảng cách giữa cận dưới n bình phương và cận trên tháp sáu tầng là một trong những khoảng trống lớn nhất của ngành.
| Mốc | Kết quả | Số người |
|---|---|---|
| 1948 | Steinhaus, Banach, Knaster: chia tương xứng | n |
| Khoảng 1960 | Selfridge và Conway: không ghen tị, 5 nhát cắt | 3 |
| 1980 | Stromquist: không ghen tị, miếng liền, dao di động | 3 |
| 1995 | Brams và Taylor: không ghen tị, hữu hạn, không giới hạn | n |
| 1997 | Brams, Taylor, Zwicker: dao di động, tối đa 11 nhát | 4 |
| 2008 | Stromquist: miếng liền thì không có quy trình hữu hạn | từ 3 |
| 2009 | Procaccia: cận dưới bậc n bình phương câu hỏi | n |
| 2016 | Aziz và Mackenzie: có giới hạn | 4, rồi n |
Thực tế dùng gì thay thế
Vì quy trình chính xác quá cồng kềnh, ứng dụng thật thường chọn một trong ba hướng:
- Gần như không ghen tị. Chấp nhận mỗi người có thể ghen một lượng rất nhỏ, chẳng hạn dưới 1% giá trị. Chạy vài vòng lõi cho tới khi phần vụn đáng ít hơn ngưỡng đó với mọi người, rồi chia phần vụn tuỳ ý. Số bước khi đó bị chặn theo ngưỡng.
- Chia rời rạc hoá. Cắt vật thành nhiều mẩu nhỏ cố định trước (ví dụ 100 ô đất, 48 khung nửa giờ), hỏi mỗi người chấm từng mẩu, rồi giải bài toán tối ưu trên máy tính. Không ghen tị tuyệt đối khi đó có thể không đạt, nhưng chênh lệch không quá một mẩu.
- Thêm tiền. Nếu được bù tiền, chia không ghen tị trở nên dễ hơn rất nhiều, như trong bài toán chia tiền thuê nhà theo phòng.
Góc nhìn hôm nay
Câu chuyện chia bánh bốn người là ví dụ đẹp về việc một câu hỏi phát biểu được cho học sinh tiểu học có thể làm khó các nhà toán học suốt nửa thế kỷ. Nó cũng cho bài học thực dụng: khi nhóm từ bốn người trở lên phải chia thứ mà mỗi người đánh giá khác nhau, đừng mong một quy trình "cắt – chọn" vài bước mà ai cũng hài lòng tuyệt đối. Hoặc chấp nhận tiêu chuẩn yếu hơn (ai cũng đủ phần), hoặc chia thành nhiều mẩu nhỏ và nhờ máy tính, hoặc dùng tiền bù.
Đọc thêm: bài gốc của Brams và Taylor (1995) và chương chia bánh trong Handbook of Computational Social Choice (2016) do Procaccia viết. Bài của Aziz và Mackenzie có bản đọc tự do trên kho tiền ấn phẩm arXiv, dài và kỹ thuật, nhưng phần mở đầu giải thích lịch sử rất dễ theo.
Câu hỏi thường gặp
Có thuật toán chia không ghen tị cho bốn người không?
Có. Brams và Taylor đưa ra quy trình hữu hạn cho mọi số người năm 1995, nhưng số bước không bị chặn trước. Năm 2016, Aziz và Mackenzie đưa ra quy trình có giới hạn cho bốn người, khoảng 200 câu hỏi, sau được rút xuống 171.
Thuật toán Brams–Taylor là gì?
Là quy trình chia không ghen tị cho số người bất kỳ, công bố năm 1995 trên American Mathematical Monthly. Nó lặp lại các vòng chia tạo ra ưu thế không thể đảo ngược giữa các cặp người, cho tới khi phần vụn còn lại chia được an toàn. Số vòng phụ thuộc vào khẩu vị nên không có giới hạn chung.
Ưu thế không thể đảo ngược là gì?
Là khi một người thấy phần mình hơn phần người kia một khoảng ít nhất bằng toàn bộ phần chưa chia. Khi đó dù phần chưa chia về tay người kia hết, người thứ nhất cũng không ghen. Đây là chìa khoá của các thuật toán Selfridge–Conway, Brams–Taylor và Aziz–Mackenzie.
Vì sao thuật toán Aziz–Mackenzie không dùng được ngoài đời?
Vì giới hạn số bước của nó là một tháp luỹ thừa sáu tầng của số người, lớn hơn mọi con số có ý nghĩa vật lý. Giá trị của nó là chứng minh có tồn tại quy trình có giới hạn. Ngoài đời người ta dùng cách gần như không ghen tị, chia thành mẩu nhỏ, hoặc thêm tiền bù.
Chia không ghen tị cần ít nhất bao nhiêu bước?
Ariel Procaccia chứng minh năm 2009 rằng mọi quy trình chia không ghen tị cần ít nhất bậc n bình phương câu hỏi trong trường hợp xấu nhất, với n là số người. Chia tương xứng chỉ cần bậc n log n, nên không ghen tị khó hơn về bản chất.