Giá trị Shapley là cách chia thành quả chung cho từng người theo mức đóng góp biên trung bình của họ: xếp mọi thứ tự có thể để từng người lần lượt "gia nhập" nhóm, ghi lại mỗi người làm tăng thêm bao nhiêu khi bước vào, rồi lấy trung bình trên tất cả các thứ tự. Lloyd Shapley đưa ra công thức này năm 1953 và chứng minh đó là cách chia duy nhất thoả bốn điều kiện công bằng rất tự nhiên. Ba người thì chỉ có sáu thứ tự, tính tay trong mười phút.
Bài toán: cùng làm thì lời hơn, nhưng lời thêm thuộc về ai
Ba người bạn ở Đà Nẵng nhận làm chung một hợp đồng quay video cho một khu nghỉ dưỡng. An quay phim, Bình dựng hình, Chi viết kịch bản và làm việc với khách. Nếu mỗi người tự nhận việc nhỏ lẻ trong cùng khoảng thời gian, An kiếm được 10 triệu, Bình 20 triệu, Chi 30 triệu. Hai người bắt cặp thì nhận được việc lớn hơn: An – Bình được 50 triệu, An – Chi 60 triệu, Bình – Chi 70 triệu. Cả ba cùng làm thì nhận trọn gói 120 triệu.
Tổng tự làm riêng là 60 triệu, cùng làm được 120 triệu. Phần dôi ra 60 triệu là nhờ hợp tác. Chia đều 40 triệu mỗi người? Chi sẽ thấy thiệt, vì một mình Chi đã kiếm được 30 triệu, còn An chỉ 10 triệu. Chia theo tỉ lệ tự làm riêng (10:20:30)? An lại thấy thiệt, vì An ghép với ai cũng làm tăng thu nhập rất mạnh. Giá trị Shapley trả lời câu này bằng một quy tắc thống nhất.
Ngôn ngữ của lý thuyết hợp tác: liên minh và hàm đặc trưng
Trong lý thuyết hợp tác, mỗi nhóm con được gọi là một liên minh. Bảng số ở trên, ghi mỗi liên minh làm ra bao nhiêu, gọi là hàm đặc trưng, thường kí hiệu v. Ta viết v(An) = 10, v(An, Bình) = 50, v(cả ba) = 120. Liên minh rỗng làm ra 0.
Lý thuyết này không hỏi ai mặc cả giỏi hơn, ai nói to hơn. Nó chỉ nhìn vào bảng v và hỏi: một cách chia "hợp lý" phải thoả những điều kiện gì. Đây là điểm khác với phần lý thuyết bất hợp tác (cân bằng Nash, thế lưỡng nan người tù), nơi người ta phân tích từng nước đi của từng người.
Cách tính tay: sáu thứ tự gia nhập
Tưởng tượng ba người đến văn phòng lần lượt từng người. Mỗi người khi bước vào làm tăng giá trị của nhóm đang có thêm một khoản, gọi là đóng góp biên. Ví dụ theo thứ tự An → Bình → Chi: An vào trước, nhóm từ 0 lên 10, An góp 10. Bình vào, nhóm từ 10 lên 50, Bình góp 40. Chi vào, nhóm từ 50 lên 120, Chi góp 70.
| Thứ tự gia nhập | An góp | Bình góp | Chi góp |
|---|---|---|---|
| An → Bình → Chi | 10 | 40 | 70 |
| An → Chi → Bình | 10 | 60 | 50 |
| Bình → An → Chi | 30 | 20 | 70 |
| Bình → Chi → An | 50 | 20 | 50 |
| Chi → An → Bình | 30 | 60 | 30 |
| Chi → Bình → An | 50 | 40 | 30 |
| Cộng | 180 | 240 | 300 |
| Trung bình (chia 6) | 30 | 40 | 50 |
Kết quả: An 30 triệu, Bình 40 triệu, Chi 50 triệu. Tổng đúng 120. Mỗi hàng của bảng cũng cộng đúng 120, vì mỗi thứ tự chỉ là một cách "kể lại" quá trình nhóm lớn dần từ 0 đến 120.
Nhìn lại: mỗi người nhận phần tự làm riêng cộng thêm 20 triệu. Đây không phải trùng hợp ngẫu nhiên của mọi bài toán, mà do bảng số này có cấu trúc khá đều. Với bảng lệch hơn, phần cộng thêm sẽ khác nhau giữa từng người.
Công thức tổng quát
Với n người, có n! thứ tự (4 người 24 thứ tự, 5 người 120, 10 người hơn 3,6 triệu). Công thức gộp cho người i là: lấy mọi liên minh S không chứa i, nhân đóng góp biên v(S ∪ {i}) − v(S) với trọng số |S|! × (n − |S| − 1)! / n!, rồi cộng lại. Trọng số đó chính là xác suất để đúng nhóm S đã có mặt trước khi i bước vào, nếu thứ tự được chọn ngẫu nhiên. Tính tay thì cách liệt kê thứ tự dễ hiểu hơn; công thức gộp hữu ích khi viết chương trình.
Bốn điều kiện làm nên giá trị Shapley
Điều làm giá trị Shapley nổi tiếng không phải công thức, mà là định lý đi kèm. Shapley chứng minh rằng chỉ có đúng một cách chia thoả đồng thời bốn điều kiện:
- Hiệu quả: chia hết, không thừa không thiếu. Tổng phần của mọi người bằng v(cả nhóm).
- Đối xứng: hai người có vai trò y hệt nhau (thay người này bằng người kia, mọi liên minh vẫn làm ra như cũ) thì nhận như nhau. Tên tuổi, thâm niên không được tính.
- Người thừa nhận 0: ai không làm tăng giá trị của bất kỳ liên minh nào thì không được chia gì.
- Cộng tính: nếu nhóm cùng làm hai việc độc lập, phần mỗi người trong tổng bằng tổng phần của từng việc. Chia từng hợp đồng rồi cộng lại cũng ra như chia gộp.
Ba điều đầu gần như ai cũng đồng ý. Điều thứ tư là chỗ người ta tranh luận nhiều nhất, vì nó mang tính kỹ thuật hơn là đạo lý. Nhưng nếu chấp nhận cả bốn, kết luận không còn chỗ thương lượng: cách chia phải là giá trị Shapley. Về sau, H. Peyton Young (1985) đưa ra một bộ điều kiện khác, thay cộng tính bằng tính "đơn điệu mạnh" (đóng góp biên của bạn tăng thì phần của bạn không được giảm), và vẫn thu được đúng giá trị Shapley.
Lloyd Shapley và bài báo năm 1953
Lloyd Stowell Shapley (1923–2016) là nhà toán học Mỹ, từng phục vụ trong quân đội Mỹ thời Thế chiến thứ hai rồi học tiếp ở Harvard và Princeton. Công thức chia lợi ích ra đời trong bài báo năm 1953 của ông, in trong một tuyển tập của Đại học Princeton (loạt Annals of Mathematics Studies, số 28) do Harold Kuhn và Albert Tucker biên tập. Ông làm việc nhiều năm ở RAND Corporation rồi Đại học California, Los Angeles.
Năm 2012, Shapley cùng Alvin Roth nhận giải Nobel Kinh tế "cho lý thuyết về phân bổ ổn định và thực tiễn thiết kế thị trường". Phần được nhắc nhiều trong giải thưởng là thuật toán ghép cặp Gale–Shapley; giá trị Shapley là một thành tựu khác, không kém phần ảnh hưởng, của cùng một người.
Giá trị Shapley khác chia đều và chia theo tỉ lệ thế nào
| Cách chia 120 triệu | An | Bình | Chi | Nhận xét |
|---|---|---|---|---|
| Chia đều | 40 | 40 | 40 | Bỏ qua chênh lệch năng lực tự làm riêng |
| Theo tỉ lệ tự làm riêng 10:20:30 | 20 | 40 | 60 | Bỏ qua việc An ghép vào làm tăng giá trị rất mạnh |
| Phần riêng + chia đều phần dôi | 30 | 40 | 50 | Trùng Shapley ở ví dụ này, không phải luôn luôn |
| Giá trị Shapley | 30 | 40 | 50 | Trung bình đóng góp biên trên mọi thứ tự |
Với hai người, giá trị Shapley luôn là: mỗi người nhận phần tự làm riêng, phần dôi ra chia đôi. Hai người tự làm được 10 và 20, cùng làm được 50, thì phần dôi 20 chia đôi, An 20 và Bình 30. Từ ba người trở lên, hai cách này bắt đầu tách nhau, và đó là lúc giá trị Shapley thật sự có ích.
Những chỗ giá trị Shapley hay bị hiểu sai
Không phải lúc nào cũng "bền"
Giá trị Shapley công bằng theo nghĩa bốn điều kiện trên, nhưng không bảo đảm không ai muốn bỏ đi. Có những bảng số mà hai người trong nhóm, nếu tách riêng, kiếm được nhiều hơn tổng phần Shapley của họ. Khái niệm đo độ "bền" là lõi (core), một chủ đề riêng của lý thuyết hợp tác. Trong ví dụ quay video, kiểm tra nhanh: An + Bình nhận 70, tự tách được 50; An + Chi nhận 80, tách được 60; Bình + Chi nhận 90, tách được 70. Không cặp nào muốn bỏ đi, nên cách chia này nằm trong lõi.
Cần biết giá trị của mọi nhóm con
Muốn tính, phải ước được v của mọi liên minh, kể cả những nhóm chưa từng làm việc cùng nhau. Ngoài đời, các con số này thường là ước đoán. Giá trị Shapley chính xác đến đâu phụ thuộc vào bảng v trung thực đến đâu. Nếu ai đó thổi phồng "một mình tôi cũng kiếm được 50 triệu", kết quả lệch theo.
Bùng nổ số phép tính
Số liên minh tăng gấp đôi mỗi khi thêm một người: 10 người có 1.024 liên minh, 30 người hơn một tỉ. Vì vậy khi dùng cho dữ liệu lớn, như giải thích mô hình học máy, người ta phải dùng phương pháp ước lượng thay vì tính đủ.
Giá trị Shapley được dùng ở đâu hôm nay
- Chia chi phí hạ tầng dùng chung: đường băng sân bay, đường ống nước liên xã, trạm xử lý chung. Bài toán sân bay của Littlechild và Owen (1973) là ví dụ kinh điển.
- Đo quyền lực lá phiếu: chỉ số Shapley–Shubik (1954) là giá trị Shapley áp vào biểu quyết có trọng số, như đại hội cổ đông.
- Giải thích mô hình học máy: phương pháp SHAP chia "công" của một dự đoán cho từng biến đầu vào.
- Phân bổ công cho kênh quảng cáo: khi khách hàng thấy quảng cáo ở nhiều kênh rồi mới mua, một số công cụ phân tích dùng giá trị Shapley để chia công cho từng kênh.
- Chia lợi nhuận nhóm: góp vốn, góp công, chia hoa hồng giữa các bên giới thiệu.
Muốn đọc tiếp, giáo trình của Michael Maschler, Eilon Solan và Shmuel Zamir (Nhà xuất bản Đại học Cambridge, 2013) có các chương về giá trị Shapley, lõi và nucleolus viết rất kỹ, kèm nhiều bài tập. Cách luyện tốt nhất vẫn là tự lập bảng v cho một nhóm thật của mình, ba người là đủ, rồi lập bảng sáu thứ tự như trên.
Câu hỏi thường gặp
Giá trị Shapley là gì nói ngắn gọn?
Là phần chia cho mỗi người bằng trung bình đóng góp biên của họ trên mọi thứ tự gia nhập nhóm. Mỗi lần một người bước vào, ghi lại họ làm tổng tăng thêm bao nhiêu, rồi lấy trung bình. Đây là cách chia duy nhất thoả bốn điều kiện hiệu quả, đối xứng, người thừa nhận 0 và cộng tính.
Cách tính giá trị Shapley cho ba người thế nào?
Liệt kê sáu thứ tự gia nhập, mỗi thứ tự ghi đóng góp biên của từng người, cộng theo cột rồi chia 6. Mỗi hàng phải cộng đúng giá trị của cả nhóm, đó là cách tự kiểm tra nhanh. Cần biết trước giá trị của bảy liên minh: ba người lẻ, ba cặp và cả nhóm.
Giá trị Shapley do ai đưa ra, năm nào?
Do nhà toán học Mỹ Lloyd Shapley đưa ra năm 1953. Ông nhận giải Nobel Kinh tế năm 2012 cùng Alvin Roth. Giải thưởng nhắc nhiều tới lý thuyết ghép cặp ổn định, nhưng giá trị Shapley cũng là một đóng góp lớn của ông.
Giá trị Shapley có phải lúc nào cũng công bằng không?
Nó công bằng theo bốn điều kiện toán học, nhưng không phải định nghĩa công bằng duy nhất. Nó có thể không nằm trong lõi, nghĩa là một nhóm con có lợi hơn nếu tách ra. Nó cũng chỉ đúng khi bảng giá trị các liên minh được ước lượng trung thực.
Giá trị Shapley khác chia đều phần dôi ra thế nào?
Với hai người, hai cách cho cùng kết quả: mỗi người nhận phần tự làm riêng cộng nửa phần dôi. Từ ba người trở lên, giá trị Shapley còn tính đến việc mỗi người làm tăng giá trị của từng cặp, từng nhóm con bao nhiêu, nên kết quả thường khác chia đều phần dôi.