Khi chia những món đồ không cắt được như tủ lạnh, máy giặt, chiếc quạt, không phải lúc nào cũng tránh được ghen tị: chỉ cần một món mà hai người cùng muốn là đủ. Vì vậy các nhà nghiên cứu dùng tiêu chuẩn nhẹ hơn, "không ghen tị trừ một món" (EF1): nếu tôi ghen với ai, bỏ bớt một món khỏi phần người đó là hết ghen. Cách luân phiên lần lượt chọn từng món luôn đạt EF1, còn cách chọn phân bổ làm tích mức hài lòng lớn nhất thì vừa đạt EF1 vừa không lãng phí.
Vì sao đồ không cắt được thì không thể đòi tuyệt đối
Hai người bạn trả lại căn hộ thuê chung, còn đúng một chiếc tủ lạnh mua chung, cả hai đều muốn giữ. Ai nhận tủ lạnh thì người kia ghen, ai không nhận cũng vậy. Không cách chia hiện vật nào cứu được. Lý thuyết chia bánh với các thuật toán như Selfridge–Conway dựa vào việc cắt nhỏ tuỳ ý; ở đây công cụ đó biến mất.
Có hai lối thoát. Thứ nhất là thêm tiền bù: người nhận tủ lạnh trả cho người kia một khoản, như phương pháp đấu thầu kín của Knaster. Thứ hai, khi không muốn hoặc không thể dùng tiền, là hạ tiêu chuẩn xuống mức luôn đạt được. Bài này đi theo lối thứ hai.
EF1: không ghen tị trừ một món
Định nghĩa: một cách chia đạt EF1 nếu với mọi cặp người i và j, hoặc i không ghen j, hoặc tồn tại một món trong phần của j mà nếu bỏ món đó đi, i hết ghen. Nói nôm na, mọi sự ghen tị đều "chỉ vì một món".
Ý tưởng xuất hiện trong bài của Richard Lipton, Evangelos Markakis, Elchanan Mossel và Amin Saberi năm 2004, và được Eric Budish đặt tên EF1 trong nghiên cứu năm 2011 về phân bổ lớp học cho sinh viên. Tiêu chuẩn này luôn đạt được, kể cả khi mỗi người đánh giá các món theo cách bất kỳ (miễn là có thêm đồ thì không tệ đi), nhờ thuật toán "phá chu trình ghen" của Lipton và các đồng tác giả: giao từng món cho một người không bị ai ghen; nếu ai cũng bị ghen, sẽ có một vòng người ghen nhau, cho cả vòng đổi phần theo chiều ghen thì tất cả cùng lợi, và vòng biến mất.
Luân phiên chọn: cách đơn giản nhất đạt EF1
Khi giá trị các món cộng được (hai món đáng bằng tổng hai món), cách luân phiên quen thuộc luôn đạt EF1:
- Xếp thứ tự người chọn, chẳng hạn An, Bình, Chi.
- Lần lượt mỗi người lấy món mình thích nhất trong số còn lại.
- Hết một vòng thì quay lại người đầu, cho tới khi hết đồ.
Vì sao đạt EF1: xét An và một người chọn sau An, như Chi. Mỗi vòng An chọn trước Chi, nên món An chọn ở mỗi vòng ít nhất bằng món Chi chọn cùng vòng, theo An. Cộng lại, An không ghen Chi. Ngược lại, Chi nhìn An: bỏ món đầu tiên An chọn, thì mỗi món còn lại của An được chọn sau một lượt của Chi ở vòng trước, nên theo Chi không hơn món Chi đã lấy ở lượt đó. Vậy Chi chỉ có thể ghen An vì đúng một món: món An lấy đầu tiên.
Ví dụ: ba bạn chia đồ khi trả căn hộ thuê chung
An, Bình, Chi ở ghép hai năm, góp tiền mua chung sáu món. Giờ mỗi người một nơi. Mỗi người chấm điểm sáu món, tổng 100:
| Món | An | Bình | Chi |
|---|---|---|---|
| Tủ lạnh | 35 | 30 | 40 |
| Máy giặt | 25 | 30 | 10 |
| Quạt đứng | 10 | 5 | 15 |
| Nồi cơm điện | 10 | 15 | 5 |
| Bàn học | 15 | 10 | 20 |
| Kệ sách | 5 | 10 | 10 |
Luân phiên theo thứ tự An – Bình – Chi
- Vòng 1: An lấy tủ lạnh (35). Bình lấy máy giặt (30). Chi, tủ lạnh đã mất, lấy bàn học (20).
- Vòng 2: An thấy quạt và nồi cơm cùng 10, lấy quạt. Bình lấy nồi cơm (15). Chi lấy kệ sách (10).
| Người | Nhận | Theo An | Theo Bình | Theo Chi |
|---|---|---|---|---|
| An | Tủ lạnh, quạt | 45 | 35 | 55 |
| Bình | Máy giặt, nồi cơm | 35 | 45 | 15 |
| Chi | Bàn học, kệ sách | 20 | 20 | 30 |
An và Bình không ghen ai. Chi thấy phần mình 30 nhưng phần An tới 55: Chi ghen An 25 điểm. Bỏ chiếc tủ lạnh khỏi phần An, phần An còn 15 theo Chi, thấp hơn 30. Vậy cách chia đạt EF1, đúng như lý thuyết, nhưng Chi vẫn chịu thiệt rõ: Chi chỉ được 30%, dưới một phần ba.
Làm tốt hơn: phân bổ có tích hài lòng lớn nhất
Một ý tưởng có gốc từ John Nash năm 1950: trong mọi cách chia, chọn cách làm cho tích số điểm của mọi người lớn nhất. Tích phạt nặng những cách để một người quá thấp: một người 0 điểm thì tích bằng 0. Năm 2016, nhóm Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel Procaccia, Nisarg Shah và Junxing Wang chứng minh trong bài "The Unreasonable Fairness of Maximum Nash Welfare" rằng với giá trị cộng được, phân bổ có tích lớn nhất luôn đạt EF1 và đồng thời hiệu quả Pareto, nghĩa là không thể chia lại để ai đó lợi hơn mà không ai thiệt.
Áp vào ví dụ: cách luân phiên cho 45 × 45 × 30 = 60.750. Thử hết 3 mũ 6 = 729 cách chia sáu món cho ba người, cách có tích lớn nhất là:
| Người | Nhận | Theo An | Theo Bình | Theo Chi |
|---|---|---|---|---|
| An | Tủ lạnh | 35 | 30 | 40 |
| Bình | Máy giặt, nồi cơm | 35 | 45 | 15 |
| Chi | Quạt, bàn học, kệ sách | 30 | 25 | 45 |
Tích 35 × 45 × 45 = 70.875. Đọc theo cột: An thấy phần mình 35, bằng phần Bình, hơn phần Chi. Bình 45, hơn cả hai. Chi 45, hơn tủ lạnh của An (40). Lần này không ai ghen cả, tốt hơn cả EF1. An "hi sinh" chiếc quạt, nhưng vẫn giữ món mình quý nhất; Chi không có tủ lạnh nhưng được ba món còn lại mình thích. Không phải lúc nào cũng may như vậy, nhưng phân bổ tích lớn nhất thường tìm ra những cách chia mà luân phiên bỏ qua.
Luân phiên kiểu rắn và các biến thể
Luân phiên thường bất lợi cho người chọn cuối. Một sửa đổi phổ biến là thứ tự kiểu rắn: An – Bình – Chi, rồi Chi – Bình – An, rồi lại An – Bình – Chi. Người chọn cuối vòng này được chọn đầu vòng sau. Trong ví dụ, với kiểu rắn, Chi lấy bàn học rồi được lấy luôn quạt ngay sau đó, trước khi An kịp chọn lại. Kiểu rắn không còn bảo đảm EF1 trong mọi trường hợp, nhưng thường làm chênh lệch nhỏ đi khi số món ít.
| Cách chia | Bảo đảm | Khi nào dùng |
|---|---|---|
| Luân phiên thường | EF1 (giá trị cộng được) | Nhóm nhỏ, chia nhanh tại chỗ, không cần máy tính |
| Luân phiên kiểu rắn | Không bảo đảm EF1, nhưng bù cho người chọn sau | Ít món, người chọn cuối hay thiệt |
| Phá chu trình ghen | EF1 với mọi kiểu đánh giá | Khi có món đi đôi mới có giá trị (bàn và ghế) |
| Tích hài lòng lớn nhất | EF1 và hiệu quả Pareto | Có bảng điểm và máy tính hoặc ít món |
Từ EF1 đến EFX: câu hỏi còn mở
EF1 cho phép bỏ món tốt nhất trong phần người kia. Một tiêu chuẩn chặt hơn gọi là EFX: bỏ bất kỳ món nào, kể cả món kém nhất, cũng hết ghen. Câu hỏi "EFX có luôn tồn tại không" là một trong những câu hỏi mở nổi tiếng nhất của ngành. Năm 2020, Bhaskar Ray Chaudhury, Jugal Garg và Kurt Mehlhorn chứng minh EFX luôn tồn tại với ba người khi giá trị cộng được; với bốn người trở lên, tính tới thời điểm viết bài, câu hỏi vẫn còn để ngỏ.
Góc nhìn hôm nay: dùng ở đâu
- Chia đồ khi tách nhà ở ghép, kết thúc hợp tác kinh doanh nhỏ. Luân phiên là cách nhanh nhất; nếu chênh lệch còn lớn, có thể bù bằng tiền ở bước cuối.
- Phân bổ lớp học. Trường Kinh doanh Wharton (Đại học Pennsylvania) dùng hệ thống Course Match dựa trên nghiên cứu của Budish từ năm 2013 để chia chỗ các lớp tự chọn có hạn cho sinh viên.
- Chia lượt dùng đồ chung, chia sách trong tủ sách gia đình cho các con, chia quà lưu niệm sau một chuyến đi tập thể.
Với tài sản lớn như nhà đất trong gia đình, nguyên lý toán học chỉ giúp gợi hướng thoả thuận; việc phân chia chính thức cần theo pháp luật và nên hỏi luật sư hoặc công chứng viên.
Đọc thêm: bài của Caragiannis và cộng sự (2016, bản đầy đủ đăng trên ACM Transactions on Economics and Computation năm 2019) có phần mở đầu dễ đọc; trang Spliddit có công cụ chia đồ theo tích hài lòng lớn nhất.
Câu hỏi thường gặp
EF1 là gì?
EF1, "không ghen tị trừ một món", là tiêu chuẩn chia đồ không cắt được: nếu một người ghen người khác, thì chỉ cần bỏ đi một món trong phần người đó là hết ghen. Tiêu chuẩn này luôn đạt được, khác với không ghen tị tuyệt đối.
Chia đồ luân phiên có công bằng không?
Luân phiên chọn từng món luôn đạt EF1 khi giá trị các món cộng được: người chọn sau chỉ có thể ghen người chọn trước vì đúng một món. Nhưng người chọn cuối thường thiệt, nên hay dùng thứ tự kiểu rắn hoặc bù thêm ở bước cuối.
Phân bổ Nash tối đa là gì?
Là cách chia làm cho tích số điểm hài lòng của mọi người lớn nhất. Caragiannis và cộng sự chứng minh năm 2016 rằng với giá trị cộng được, cách chia này luôn đạt EF1 và hiệu quả Pareto. Nó tránh để một người quá thấp vì tích sẽ tụt mạnh.
Vì sao không chia được đồ vật không ghen tị tuyệt đối?
Vì có thể có một món mà mọi người đều muốn nhất, và người không nhận được nó sẽ ghen người nhận. Không có cách chia hiện vật nào tránh được; chỉ có thể thêm tiền bù hoặc hạ tiêu chuẩn xuống EF1.
EFX khác EF1 thế nào?
EF1 chỉ cần bỏ một món nào đó, thường là món tốt nhất, để hết ghen. EFX đòi bỏ bất kỳ món nào cũng hết ghen, chặt hơn nhiều. EFX đã được chứng minh tồn tại cho ba người năm 2020, còn với bốn người trở lên vẫn là câu hỏi mở.