Bài toán sân bay hỏi: nhiều loại máy bay dùng chung một đường băng, máy bay lớn cần đường băng dài hơn, vậy chi phí xây đường băng chia cho từng loại thế nào. Lời giải theo giá trị Shapley, được Stephen Littlechild và Guillermo Owen rút gọn năm 1973, đơn giản đến bất ngờ: cắt đường băng thành từng đoạn, mỗi đoạn chia đều cho những ai thật sự cần đến đoạn đó. Cùng quy tắc ấy cho ta cách chia tiền taxi đi chung khi mỗi người xuống ở một điểm khác nhau trên cùng tuyến đường.
Đường băng dài bao nhiêu là do chiếc lớn nhất quyết định
Giả sử một sân bay phục vụ ba loại máy bay: loại nhỏ chỉ cần đường băng đủ cho chi phí 30 tỉ đồng, loại vừa cần đường băng đắt 50 tỉ, loại lớn cần đường băng đắt 90 tỉ. Xây một đường băng 90 tỉ thì cả ba loại đều dùng được. Chi phí của bất kỳ nhóm nào cũng chỉ bằng chi phí đường băng cho chiếc lớn nhất trong nhóm đó.
Đây là cấu trúc mà Littlechild và Owen gọi tên trong bài báo đăng tạp chí Management Science năm 1973. Chi phí của một liên minh không phải tổng nhu cầu, mà là nhu cầu lớn nhất. Loại nhỏ không làm đường băng dài thêm mét nào, nhưng vẫn được dùng. Câu hỏi là nó nên trả bao nhiêu.
Lời giải: cắt đường băng thành đoạn, chia đều từng đoạn
Hãy nhìn đường băng như ba đoạn nối tiếp nhau:
- Đoạn 1, chi phí 30 tỉ: cả ba loại máy bay đều cần. Chia ba, mỗi loại 10 tỉ.
- Đoạn 2, chi phí 50 − 30 = 20 tỉ: chỉ loại vừa và loại lớn cần. Chia hai, mỗi loại 10 tỉ.
- Đoạn 3, chi phí 90 − 50 = 40 tỉ: chỉ loại lớn cần. Loại lớn trả trọn 40 tỉ.
| Loại máy bay | Đoạn 1 (30 tỉ) | Đoạn 2 (20 tỉ) | Đoạn 3 (40 tỉ) | Tổng phải trả |
|---|---|---|---|---|
| Nhỏ | 10 | – | – | 10 |
| Vừa | 10 | 10 | – | 20 |
| Lớn | 10 | 10 | 40 | 60 |
| Cộng | 30 | 20 | 40 | 90 |
Kết quả 10 – 20 – 60 chính là giá trị Shapley của bài toán. Littlechild và Owen chứng minh điều này đúng cho mọi bài toán có cấu trúc "chi phí bằng nhu cầu lớn nhất", với bao nhiêu loại người dùng cũng vậy. Thay vì liệt kê n! thứ tự, chỉ cần sắp người dùng theo nhu cầu tăng dần và chia từng đoạn. Với hàng nghìn lượt hạ cánh, đây là khác biệt giữa tính được và không tính được.
Kiểm tra lại bằng sáu thứ tự
Muốn chắc, lập bảng thứ tự như cách tính giá trị Shapley thông thường. Trong thứ tự Nhỏ → Vừa → Lớn, loại nhỏ vào trước làm chi phí từ 0 lên 30, loại vừa thêm 20, loại lớn thêm 40. Trong thứ tự Lớn → Nhỏ → Vừa, loại lớn vào trước gánh 90, hai loại sau thêm 0. Làm đủ sáu thứ tự: loại nhỏ chỉ gánh 30 khi vào đầu tiên (2 trong 6 thứ tự), trung bình 10. Loại vừa gánh 50 khi vào đầu (2 thứ tự), gánh 20 khi vào sau loại nhỏ mà trước loại lớn (1 thứ tự), còn lại 0, trung bình (100 + 20) / 6 = 20. Loại lớn nhận phần còn lại, 60. Khớp với cách chia đoạn.
Sân bay Birmingham: từ lý thuyết đến số liệu thật
Ý tưởng không dừng ở bảng giấy. Năm 1977, Littlechild và G. F. Thompson áp dụng cách tính này cho số liệu thật của sân bay Birmingham (Anh), với chi phí đường băng và số lượt hạ cánh của 11 loại máy bay trong niên độ 1968–1969. Họ tính phí hạ cánh theo giá trị Shapley và theo một nghiệm khác gọi là nucleolus, rồi so với biểu phí sân bay đang thu. Bài báo đăng tạp chí Bell Journal of Economics và trở thành ví dụ được trích nhiều nhất về việc dùng lý thuyết hợp tác để tính phí.
Điểm đáng chú ý trong nghiên cứu: khi mỗi loại máy bay có nhiều lượt hạ cánh, mỗi lượt được coi là một "người dùng". Đoạn đường băng đầu tiên, mà mọi chiếc cần, được chia cho tổng số lượt của mọi loại, nên phần mỗi lượt rất nhỏ. Đoạn cuối chỉ chia cho số ít lượt của các máy bay thân rộng, nên phần mỗi lượt lớn. Đó là lý do phí hạ cánh theo cách này tăng nhanh hơn tỉ lệ thuận với kích cỡ máy bay.
Chia tiền taxi đi chung theo cùng quy tắc
Ba người đồng nghiệp tan tiệc ở trung tâm Hà Nội, gọi chung một xe về hướng Long Biên. Xe chạy một tuyến thẳng, trả Lan trước, rồi Minh, cuối cùng là Hùng. Nếu đi riêng, cuốc của Lan hết 60 nghìn đồng, Minh 90 nghìn, Hùng 150 nghìn. Đi chung, đồng hồ chỉ hết 150 nghìn, vì xe chỉ chạy một lần tới nhà Hùng.
Đây đúng là bài toán sân bay: chi phí của nhóm bằng cuốc xa nhất. Cắt quãng đường thành đoạn:
| Đoạn đường | Chi phí đoạn | Ai còn ngồi trên xe | Mỗi người |
|---|---|---|---|
| Trung tâm → nhà Lan | 60 nghìn | Lan, Minh, Hùng | 20 nghìn |
| Nhà Lan → nhà Minh | 30 nghìn | Minh, Hùng | 15 nghìn |
| Nhà Minh → nhà Hùng | 60 nghìn | Hùng | 60 nghìn |
Lan trả 20 nghìn, Minh 20 + 15 = 35 nghìn, Hùng 20 + 15 + 60 = 95 nghìn. Tổng 150 nghìn. Cả ba đều trả ít hơn đi riêng: Lan tiết kiệm 40, Minh 55, Hùng 55.
So với chia theo quãng đường
Cách nhiều nhóm hay làm là chia tỉ lệ theo cuốc đi riêng, 60 : 90 : 150. Khi đó Lan trả 30, Minh 45, Hùng 75. Cách này nghe hợp lý nhưng có một điểm lạ: Lan phải góp vào đoạn từ nhà Minh tới nhà Hùng, một đoạn Lan không ngồi trên xe. Quy tắc chia đoạn trả lời rõ ràng: đoạn nào bạn không đi, bạn không trả.
| Cách chia 150 nghìn | Lan | Minh | Hùng |
|---|---|---|---|
| Chia đều | 50 | 50 | 50 |
| Theo tỉ lệ cuốc đi riêng | 30 | 45 | 75 |
| Chia đoạn (giá trị Shapley) | 20 | 35 | 95 |
Chia đều thì Lan trả 50 trong khi đi riêng chỉ 60, gần như không được lợi gì từ việc đi chung. Hùng thì được lợi 100 nghìn. Chia đoạn đẩy phần lợi về phía người làm cả nhóm phải đi xa ít nhất.
Đời thực phức tạp hơn một chút
Cước taxi ở Việt Nam thường có giá mở cửa cho quãng đầu, rồi giá theo km, đôi khi giá km giảm dần sau một ngưỡng. Khi đó chi phí từng đoạn không tỉ lệ đúng với chiều dài, nhưng quy tắc vẫn dùng được: lấy cước đi riêng của từng người làm mốc, hiệu giữa hai mốc liền nhau là chi phí đoạn. Giá mở cửa nằm trong đoạn đầu và được chia cho mọi người, đúng tinh thần ai cũng cần chiếc xe đến đón.
Nếu tuyến đường không thẳng, ví dụ phải vòng sang một ngõ để trả Minh rồi quay ra, chi phí nhóm không còn bằng cuốc xa nhất, và bài toán không còn là bài toán sân bay. Lúc ấy cần lập bảng chi phí cho từng nhóm con (Lan – Minh, Minh – Hùng…) rồi tính giá trị Shapley theo cách đầy đủ.
Những nơi khác có cùng cấu trúc
- Thang máy chung cư: người tầng 2 cần thang lên tầng 2, người tầng 20 cần thang lên tầng 20. Nếu muốn chia chi phí thang theo mức sử dụng, cách chia đoạn cho người tầng thấp trả phần nền, người tầng cao trả thêm phần đoạn trên.
- Đường ống dẫn nước dọc một con đường: hộ đầu đường chỉ cần đoạn ống đầu, hộ cuối đường cần cả tuyến.
- Dung lượng máy chủ dùng chung: nhóm cần đỉnh tải cao nhất quyết định cỡ máy; các nhóm nhỏ chia phần nền.
- Đường điện kéo vào một xóm: nhà gần trạm biến áp và nhà cuối xóm cùng dùng đoạn đầu.
Ở mọi trường hợp, dấu hiệu nhận biết là: nhóm phải xây theo nhu cầu của người cần nhiều nhất, và thứ xây ra phục vụ được luôn mọi người cần ít hơn.
Giá trị Shapley có phải lời giải duy nhất cho bài toán sân bay
Không. Các nhà nghiên cứu đã so nhiều cách. Nucleolus tìm cách chia sao cho nhóm con được lợi ít nhất (so với tự xây riêng) được lợi nhiều nhất có thể. Với ví dụ ba loại máy bay ở trên, nucleolus cho 15 – 17,5 – 57,5 tỉ: loại nhỏ trả nhiều hơn giá trị Shapley (10 tỉ), loại lớn trả ít hơn, vì nucleolus san phần tiết kiệm đều hơn giữa các nhóm thay vì dồn lợi cho người cần ít nhất. Cách chia theo tỉ lệ nhu cầu (30 : 50 : 90) cũng hay được dùng vì dễ giải thích. Điểm mạnh của giá trị Shapley là dựa trên bốn điều kiện công bằng rõ ràng và tính được bằng công thức đơn giản. Điểm yếu là nó đòi chi phí phải có đúng cấu trúc "nhu cầu lớn nhất" thì mới có công thức gọn.
Một tính chất quan trọng: kết quả chia đoạn luôn nằm trong lõi của bài toán sân bay. Nghĩa là không nhóm con nào trả nhiều hơn chi phí nếu tự xây riêng cho mình. Ba người đi taxi ở trên, không cặp nào có lý do tách ra gọi xe riêng.
Góc nhìn hôm nay: dùng quy tắc chia đoạn khi đi chung xe
Lần tới đi chung xe với bạn bè, thử ba bước:
- Mở ứng dụng gọi xe, xem cước ước tính nếu mỗi người đi riêng tới điểm của mình.
- Sắp các mức cước tăng dần. Đoạn đầu chia cho tất cả, đoạn thứ hai chia cho những người còn lại, cứ thế.
- Nếu cước thực tế khác ước tính, chia phần chênh lệch theo cùng tỉ lệ.
Muốn tìm hiểu sâu hơn, hãy tìm bài báo năm 1973 của Littlechild và Owen trên Management Science, và bài năm 1977 của Littlechild và Thompson về sân bay Birmingham; cả hai ngắn, dễ đọc với người biết đại số cơ bản.
Câu hỏi thường gặp
Bài toán sân bay trong lý thuyết hợp tác là gì?
Là bài toán chia chi phí một đường băng dùng chung cho nhiều loại máy bay có nhu cầu chiều dài khác nhau. Chi phí của mỗi nhóm bằng chi phí đường băng cho chiếc cần dài nhất. Littlechild và Owen năm 1973 chỉ ra giá trị Shapley của bài toán này tính được bằng cách chia đều từng đoạn đường băng cho những ai cần đoạn đó.
Đi taxi chung mỗi người xuống một chỗ thì chia tiền thế nào?
Nếu xe chạy một tuyến thẳng, cắt quãng đường theo các điểm xuống. Chi phí đoạn đầu chia cho tất cả, đoạn sau chia cho những người còn trên xe, đoạn cuối do người xuống sau cùng trả. Mỗi người không phải trả cho đoạn đường mình không đi.
Vì sao không chia tiền taxi theo tỉ lệ quãng đường?
Chia theo tỉ lệ khiến người xuống sớm phải góp vào cả những đoạn họ không ngồi trên xe. Cách chia đoạn tránh điều đó và trùng với giá trị Shapley. Tuy vậy, nếu cả nhóm đã thống nhất chia theo tỉ lệ thì đó cũng là một quy ước chấp nhận được.
Littlechild và Owen là ai?
Stephen Littlechild là nhà kinh tế học người Anh, sau này nổi tiếng với vai trò người đứng đầu cơ quan quản lý ngành điện Anh. Guillermo Owen là nhà toán học gốc Colombia, tác giả nhiều sách giáo khoa về lý thuyết hợp tác. Bài báo chung năm 1973 của họ ngắn nhưng được trích dẫn rất rộng.
Nucleolus khác giá trị Shapley thế nào trong bài toán sân bay?
Nucleolus chọn cách chia làm cho nhóm con được lợi ít nhất được lợi nhiều nhất có thể, còn giá trị Shapley lấy trung bình đóng góp biên. Với đường băng 30 – 50 – 90 tỉ, Shapley cho 10 – 20 – 60, nucleolus cho 15 – 17,5 – 57,5. Cả hai đều nằm trong lõi, tức không nhóm nào muốn tách ra xây riêng.