Chia không ghen tị là cách chia mà sau khi xong, không ai muốn đổi phần của mình lấy phần của bất kỳ người nào khác, xét theo chính cách đánh giá của người đó. Nó chặt hơn chia tương xứng, vốn chỉ đòi mỗi người trong n người thấy mình được ít nhất 1/n. Với hai người, hai tiêu chuẩn này trùng nhau; từ ba người trở lên, một người có thể được đủ một phần ba mà vẫn nhìn sang phần người bên cạnh và thấy thiệt.
Hai câu hỏi khác nhau: "tôi có đủ không" và "tôi có kém ai không"
Hãy tưởng tượng ba người bạn An, Bình, Chi chia một chiếc bánh sinh nhật. Mỗi người có khẩu vị riêng: An mê phần có nhiều kem, Bình thích phần có trái cây, Chi chỉ cần phần đế bông lan mềm. Vì khẩu vị khác nhau, cùng một miếng bánh có thể "đáng giá" khác nhau với từng người. Lý thuyết chia công bằng gọi đó là mỗi người có một hàm đánh giá riêng, và mọi tiêu chuẩn công bằng đều được đo bằng hàm của chính người đang xét, không phải bằng cân hay thước.
Từ đó có hai câu hỏi.
- Tương xứng (proportional): theo đánh giá của tôi, phần tôi nhận có đáng ít nhất 1/n cả chiếc bánh không? Đây là câu hỏi chỉ nhìn vào phần mình.
- Không ghen tị (envy-free): theo đánh giá của tôi, phần tôi nhận có ít nhất bằng phần của từng người còn lại không? Đây là câu hỏi nhìn sang hai bên.
Khái niệm không ghen tị được nhà kinh tế học Duncan Foley đưa vào kinh tế học năm 1967, rồi Hal Varian phát triển thành một định nghĩa "phân bổ công bằng" năm 1974: vừa không ai ghen, vừa hiệu quả. Trước đó, các nhà toán học Ba Lan quanh Hugo Steinhaus đã nghiên cứu chia tương xứng từ thập niên 1940.
Ví dụ tính tay: đủ một phần ba mà vẫn ghen
Chiếc bánh được cắt thành ba miếng X, Y, Z. Bảng dưới ghi mỗi người chấm mỗi miếng bao nhiêu phần trăm giá trị cả chiếc bánh theo khẩu vị của mình. Mỗi hàng cộng lại đúng 100.
| Người | Miếng X | Miếng Y | Miếng Z |
|---|---|---|---|
| An | 35 | 30 | 35 |
| Bình | 40 | 35 | 25 |
| Chi | 20 | 45 | 35 |
Cách chia thứ nhất: An lấy X, Bình lấy Z, Chi lấy Y.
- An được 35%, hơn một phần ba (33,3%). Đạt tương xứng.
- Bình được 25%. Không đạt.
- Chi được 45%. Đạt.
Cách chia thứ hai: An lấy Z, Bình lấy X, Chi lấy Y.
- An được 35%, đúng bằng miếng X của Bình theo An và hơn miếng Y (30%). Không ghen.
- Bình được 40%, hơn Y (35%) và Z (25%). Không ghen.
- Chi được 45%, hơn X (20%) và Z (35%). Không ghen.
Cách chia thứ ba: An lấy X, Bình lấy Y, Chi lấy Z.
- An 35% so với 30 và 35: không ghen.
- Bình 35% so với X 40%: ghen với An.
- Chi 35% so với Y 45%: ghen với Bình.
Ở cách thứ ba, Bình được 35% và Chi được 35%, cả hai đều vượt một phần ba, tức là đạt tương xứng trọn vẹn. Thế mà hai người vẫn không vui. Đây là điều cốt lõi: tương xứng chỉ bảo đảm "đủ", không bảo đảm "không kém ai".
Vậy với cùng ba miếng bánh, cách thứ hai không ai ghen, cách thứ ba ai cũng đủ phần nhưng hai người ghen, cách thứ nhất thì một người còn chưa đủ phần. Điểm mấu chốt của cách thứ hai là An chấm X và Z ngang nhau, nên An sẵn lòng nhường X. Nếu An chấm X hơn Z chỉ 1 điểm, cách đó đã có một chút ghen, và người ta phải cắt lại hoặc gọt bớt miếng X như trong thuật toán Selfridge–Conway.
Vì sao không ghen tị kéo theo tương xứng, mà chiều ngược lại thì không
Giả sử bánh được chia hết, không bỏ sót vụn nào, và giá trị cộng được (hai miếng ghép lại đáng bằng tổng hai miếng). Nếu tôi không ghen với ai, thì phần của tôi lớn hơn hoặc bằng phần của từng người trong n người, theo đánh giá của tôi. Cộng n phần lại được cả chiếc bánh, tức 100%. Phần lớn nhất trong n số có tổng 100 phải ít nhất là 100/n. Phần tôi lớn hơn hoặc bằng mọi phần, nên nó ít nhất là 100/n. Vậy không ghen tị suy ra tương xứng.
Chiều ngược lại sai, như ví dụ trên đã cho thấy. Riêng trường hợp hai người, hai tiêu chuẩn tương đương: tôi được ít nhất 50% thì phần người kia, theo tôi, nhiều nhất là 50%, nên tôi không ghen. Đó là lý do cách chia "một người cắt, một người chọn" xử lý trọn vẹn bài toán hai người, còn từ ba người trở đi phải có thuật toán riêng.
Bảng các tiêu chuẩn công bằng thường gặp
| Tiêu chuẩn | Mỗi người tự hỏi | Quan hệ với không ghen tị |
|---|---|---|
| Tương xứng | Phần tôi có đáng ít nhất 1/n không? | Yếu hơn; bị không ghen tị kéo theo |
| Không ghen tị | Phần tôi có ít nhất bằng phần từng người khác không? | Chính nó |
| Ngang bằng (equitable) | Tỉ lệ tôi nhận theo tôi có bằng tỉ lệ người khác nhận theo họ không? | Độc lập; có thể mâu thuẫn |
| Chính xác (exact) | Theo tôi, mọi phần có đúng bằng 1/n không? | Mạnh hơn cả hai; ai cũng thấy các phần y hệt nhau |
| Hiệu quả (Pareto) | Có cách chia khác làm ai đó lợi hơn mà không ai thiệt không? | Độc lập; kết hợp được |
Tiêu chuẩn ngang bằng đáng chú ý vì nó đá nhau với không ghen tị. Ở cách chia thứ hai trong ví dụ, An được 35%, Bình 40%, Chi 45%: không ai ghen, nhưng không ngang bằng, vì Chi thấy mình được nhiều hơn hẳn so với An thấy về phần An. Người ta đã chứng minh rằng với ba người trở lên, có những tình huống không cách chia nào vừa không ghen tị, vừa ngang bằng, vừa hiệu quả cùng lúc.
Có luôn tồn tại cách chia không ghen tị không
Với vật chia được liên tục như bánh, đất, thời gian, câu trả lời là có, và đó là một trong những kết quả đẹp nhất của ngành.
- Dubins và Spanier (1961), trong bài "How to cut a cake fairly" trên tạp chí American Mathematical Monthly, dùng định lý lồi của Lyapunov để chứng minh luôn tồn tại cách chia mà mọi người đều thấy mọi phần bằng đúng 1/n, nếu cho phép mỗi phần gồm nhiều mảnh rời. Cách chia chính xác như vậy hiển nhiên không ai ghen.
- Stromquist (1980) và Woodall (1980) chứng minh độc lập rằng có thể chia không ghen tị mà mỗi người nhận một miếng liền, nghĩa là chỉ cần n − 1 nhát cắt song song.
- Weller (1985) chứng minh luôn có cách chia vừa không ghen tị vừa hiệu quả Pareto.
Nhưng "tồn tại" khác với "tìm được bằng một quy trình hữu hạn". Năm 2008, Stromquist chứng minh không có quy trình hữu hạn nào luôn tìm ra cách chia không ghen tị với miếng liền cho ba người trở lên. Muốn có thuật toán thật, người ta phải chấp nhận miếng rời (như Selfridge–Conway cho ba người), dao di động liên tục, hoặc nới lỏng thành "gần như không ghen tị", sai lệch nhỏ hơn một ngưỡng cho trước.
Khi đồ vật không cắt được
Tất cả các định lý trên dựa vào việc bánh cắt nhỏ được tuỳ ý. Đổi sang một chiếc xe máy và hai người cùng muốn nó, thì không cách chia hiện vật nào tránh được ghen tị: ai không có xe sẽ ghen với người có. Có hai lối thoát quen thuộc.
- Thêm tiền bù. Người nhận xe trả cho người kia một khoản. Nếu khoản đó nằm đúng giữa hai mức định giá, cả hai đều thấy không thiệt. Chia tiền thuê nhà theo phòng là một dạng như vậy: phòng là đồ không cắt được, tiền thuê là phần bù chia được.
- Nới tiêu chuẩn. "Không ghen tị trừ một món" (EF1): nếu tôi ghen với ai, thì chỉ cần bỏ bớt một món khỏi phần của người đó là hết ghen. Chia luân phiên lần lượt chọn từng món luôn đạt tiêu chuẩn này khi giá trị cộng được.
Đo ghen tị bằng con số
Trong thực hành, người ta hay đo mức ghen thay vì chỉ hỏi có hay không. Với người i, mức ghen với người j là giá trị phần của j trừ giá trị phần của i, cả hai đều tính theo i; âm hoặc bằng 0 nghĩa là không ghen. Trong cách chia thứ ba ở trên:
| Người | Ghen với An | Ghen với Bình | Ghen với Chi |
|---|---|---|---|
| An (giữ X = 35) | — | 30 − 35 = −5 | 35 − 35 = 0 |
| Bình (giữ Y = 35) | 40 − 35 = 5 | — | 25 − 35 = −10 |
| Chi (giữ Z = 35) | 20 − 35 = −15 | 45 − 35 = 10 | — |
Mức ghen lớn nhất là 10 điểm, của Chi với Bình. Một cách chia "tốt hơn" theo nghĩa này là cách làm giảm con số lớn nhất ấy. Các chương trình chia tiền thuê nhà, chia đồ khi ở chung thường tối ưu chính xác những đại lượng như vậy: trước hết ép mức ghen về 0, sau đó trong các cách không ai ghen thì chọn cách người thiệt nhất được nhiều nhất.
Góc nhìn hôm nay: dùng khái niệm này ngoài bàn tiệc
Không ghen tị là thước đo hữu ích bất cứ khi nào người ta chia thứ mà mỗi người đánh giá khác nhau: chia ca trực Tết, chia phòng trong căn hộ thuê chung, chia đồ khi dọn ra ở riêng, chia khung giờ dùng phòng họp. Ba câu hỏi đặt ra trước khi chia giúp tránh cãi nhau về sau:
- Mỗi người có đánh giá giống nhau không? Nếu giống, chia đều theo cân, theo diện tích là đủ. Nếu khác, chia đều bề ngoài lại dễ sinh ghen.
- Thứ cần chia có cắt nhỏ được không? Nếu không, có dùng tiền bù được không?
- Mình cần "đủ phần" hay cần "không ai kém ai"? Nhóm đông người hay so bì thì nên nhắm tiêu chuẩn thứ hai.
Sách nên đọc: Fair Division: From Cake-Cutting to Dispute Resolution (1996) của Steven Brams và Alan Taylor; Cake-Cutting Algorithms: Be Fair If You Can (1998) của Jack Robertson và William Webb. Cả hai viết cho người có toán phổ thông, có nhiều ví dụ tính tay.
Câu hỏi thường gặp
Chia không ghen tị là gì?
Là cách chia mà mỗi người, theo cách đánh giá của chính mình, thấy phần mình ít nhất bằng phần của từng người khác, nên không ai muốn đổi. Tiêu chuẩn này do Duncan Foley đưa vào kinh tế học năm 1967. Nó không đòi các phần bằng nhau về cân nặng hay diện tích.
Chia không ghen tị khác chia tương xứng thế nào?
Tương xứng chỉ đòi mỗi người thấy mình được ít nhất 1/n, còn không ghen tị đòi không ai thấy phần người khác hơn phần mình. Không ghen tị luôn kéo theo tương xứng khi bánh được chia hết. Với hai người hai tiêu chuẩn trùng nhau; từ ba người trở lên thì không.
Có luôn chia được không ghen tị cho mọi số người không?
Với vật chia liên tục như bánh hay đất, luôn tồn tại cách chia không ghen tị, kể cả với miếng liền (Stromquist và Woodall, 1980). Tuy nhiên với ba người trở lên, không quy trình hữu hạn nào luôn tìm được cách chia miếng liền như vậy; thuật toán thật phải dùng miếng rời hoặc dao di động.
Chia đồ không cắt được thì có không ghen tị được không?
Không phải lúc nào cũng được: một chiếc xe hai người cùng muốn thì người không có sẽ ghen. Lối thoát là thêm tiền bù cho người không nhận, hoặc chấp nhận tiêu chuẩn "không ghen tị trừ một món", đạt được bằng cách luân phiên chọn.
Chia đều có phải là chia không ghen tị không?
Chỉ khi mọi người đánh giá giống nhau. Nếu khẩu vị khác nhau, ba miếng bằng nhau về cân nặng vẫn có thể làm một người thấy miếng của người kia ngon hơn hẳn. Ngược lại, một cách chia lệch về cân nặng vẫn có thể không ai ghen, vì ai cũng nhận đúng thứ mình thích.