Vẫn gian hàng của An, Bình và Chi. Làm chung được 12 điểm. Có người đề nghị cho An 6 vì An mang đồ ăn. Có người bảo Chi đến bán cuối cùng nên lời về là nhờ Chi.
Nếu cứ cãi xem ai đến trước, thử cho mỗi người đến trước vài lần trên giấy.
Người đến sau bổ sung thêm bao nhiêu?
Dùng bảng cũ. Làm một mình được 0. Cặp An–Bình làm được 8, An–Chi được 6, Bình–Chi được 4. Cả ba được 12.
Xếp thứ tự An, Bình, Chi. An vào đầu tiên, nhóm đi từ 0 lên 0, phần tăng của An là 0. Bình vào, nhóm An–Bình đi từ 0 lên 8, phần tăng của Bình là 8. Chi vào, nhóm đi từ 8 lên 12, phần tăng của Chi là 4.
Nếu xếp Chi, Bình, An, Chi vào trước tăng 0. Bình vào làm nhóm được 4. An vào sau làm nhóm tăng từ 4 lên 12, tức thêm 8. Mức đóng góp của An khác hẳn dù vẫn là cùng một người. Nó phụ thuộc những ai đã có mặt.
Cho cả sáu thứ tự cơ hội như nhau
| Thứ tự vào nhóm | An thêm | Bình thêm | Chi thêm |
|---|---|---|---|
| An, Bình, Chi | 0 | 8 | 4 |
| An, Chi, Bình | 0 | 6 | 6 |
| Bình, An, Chi | 8 | 0 | 4 |
| Bình, Chi, An | 8 | 0 | 4 |
| Chi, An, Bình | 6 | 6 | 0 |
| Chi, Bình, An | 8 | 4 | 0 |
| Trung bình | 5 | 4 | 3 |
Các số 5, 4, 3 là giá trị Shapley của ba người trong bảng này. Ta lấy phần tăng trung bình qua mọi thứ tự. Mỗi hàng cộng đúng 12 vì cả nhóm đi từ 0 tới 12. Lấy trung bình vẫn chia hết 12.
Trong khoa học dữ liệu, ý tưởng đo phần tăng khi thêm một thành phần có thể dùng để giải thích một dự đoán. Chẳng hạn, thêm thông tin về quãng đường có thể làm dự báo thời gian giao hàng đổi ít hay nhiều tùy đã có thông tin về khu vực. Phép tính thực tế còn phải định nghĩa “thiếu một thông tin” có nghĩa gì. Ví dụ gian hàng chỉ dạy phần lấy trung bình qua thứ tự.
Tự thử
Cách chia Shapley (5, 4, 3) có nằm trong lõi của trò gian hàng không? Nếu bất kỳ cặp nào đều tự tạo được 9 và cả ba tạo được 12, phép chia Shapley sẽ ra gì?
Đáp án. Với bảng gốc, ba cặp nhận tổng 9, 8 và 7, đều đạt mức tự làm 8, 6 và 4. Vậy cách chia nằm trong lõi. Với bảng mới, ba người có vai trò đối xứng, nên Shapley chia (4, 4, 4). Mỗi cặp chỉ được 8 và có thể tách ra kiếm 9. Một cách chia theo phần đóng góp trung bình có thể khác một cách chia đứng vững trước việc tách nhóm.
Đọc tiếp trong series
- Bài trước. Bài 31 · Lõi hợp tác và cách chia thưởng để nhóm nhỏ muốn ở lại
- Bài sau. Bài 33 · Chỉ số Banzhaf và người có thể lật một cuộc biểu quyết
- Mục lục 35 bài Lý thuyết trò chơi
Bài liên quan
Tài liệu tham khảo
- Game Theory, Michael Maschler, Eilon Solan và Shmuel Zamir. Chương về giá trị Shapley.
Bình luận