Lõi (core) là tập hợp mọi cách chia thành quả chung mà không nhóm con nào có lý do bỏ đi làm riêng: mỗi nhóm con nhận được ít nhất bằng số họ tự làm ra được. Cách chia nằm trong lõi thì liên minh bền; lõi rỗng thì dù chia kiểu gì cũng có một nhóm muốn tách ra. Kiểm tra một cách chia có nằm trong lõi hay không chỉ cần cộng và so sánh, ba người thì bảy phép so.
Câu hỏi của lõi khác câu hỏi của giá trị Shapley
Giá trị Shapley hỏi: chia thế nào cho công bằng theo đóng góp. Lõi hỏi một câu thực dụng hơn: chia thế nào để không ai bỏ đi. Một cách chia có thể rất công bằng trên giấy nhưng vẫn khiến hai người trong nhóm thấy họ tách ra làm riêng thì được nhiều hơn. Khi đó liên minh lớn sẽ vỡ, dù chẳng ai làm gì sai.
Hai câu hỏi thường cho cùng đáp án, nhưng không phải lúc nào cũng vậy. Có bài toán mà giá trị Shapley nằm ngoài lõi, có bài toán mà lõi chỉ gồm một điểm duy nhất trông rất "bất công", và có bài toán mà lõi trống trơn.
Định nghĩa bằng ví dụ ba cửa hàng nhập hàng chung
Ba cửa hàng tạp hoá nhỏ trong một khu phố ở Cần Thơ bàn nhau nhập hàng chung để được chiết khấu và chia tiền xe. Mỗi cửa hàng nhập riêng thì không tiết kiệm được gì. Hai cửa hàng bất kỳ góp đơn tiết kiệm được 70 triệu một năm. Cả ba góp thì tiết kiệm 120 triệu. Gọi số tiết kiệm ba cửa hàng nhận lần lượt là a, b, c.
Một cách chia (a, b, c) nằm trong lõi khi thoả hai nhóm điều kiện:
- Chia hết: a + b + c = 120.
- Không nhóm nào thiệt: mỗi cửa hàng nhận ít nhất 0 (bằng số tự làm được), mỗi cặp nhận ít nhất 70: a + b ≥ 70, a + c ≥ 70, b + c ≥ 70.
Chia đều 40 – 40 – 40: mỗi cặp nhận 80 ≥ 70. Nằm trong lõi. Chia 60 – 40 – 20: cặp thứ hai và thứ ba nhận 60 < 70, họ sẽ rủ nhau đi riêng. Nằm ngoài lõi. Chia 50 – 35 – 35: các cặp nhận 85, 85, 70. Vẫn nằm trong lõi, vừa sát mép.
Từ ba bất đẳng thức cặp, cộng lại được 2(a + b + c) ≥ 210, tức tổng phải ít nhất 105. Ta có 120, dư 15. Phần dư 15 đó là "khoảng thương lượng": lõi ở đây là một tam giác quanh điểm chia đều, với ba đỉnh 20 – 50 – 50, 50 – 20 – 50 và 50 – 50 – 20. Mỗi cửa hàng nhận từ 20 đến 50 triệu, và không ai được quá 50, vì cặp còn lại luôn đòi ít nhất 70.
Khi lõi rỗng: không cách chia nào giữ được cả nhóm
Đổi số một chút. Giả sử hai cửa hàng bất kỳ góp đơn đã tiết kiệm được 90 triệu, trong khi cả ba góp chỉ được 120 (vì xe chở không hết, phải thuê thêm chuyến). Điều kiện cặp đòi 2(a + b + c) ≥ 270, tức tổng ít nhất 135. Nhưng chỉ có 120 để chia. Không có cách chia nào thoả: lõi rỗng.
Ngoài đời, lõi rỗng hiện ra như một vòng xoay không dứt. Cửa hàng 1 và 2 rủ nhau đi riêng, chia 45 – 45. Cửa hàng 3 bị bỏ lại, liền ra giá cho cửa hàng 2: "Đi với tôi, anh lấy 50, tôi lấy 40". Cửa hàng 1 bị bỏ lại, lại ra giá cho cửa hàng 3. Không có điểm dừng.
| Mỗi cặp làm ra | Cả ba làm ra | Tổng tối thiểu để giữ mọi cặp | Lõi |
|---|---|---|---|
| 60 | 120 | 90 | Rộng, nhiều cách chia |
| 70 | 120 | 105 | Tam giác quanh 40 – 40 – 40 |
| 80 | 120 | 120 | Đúng một điểm: 40 – 40 – 40 |
| 90 | 120 | 135 | Rỗng |
Ngưỡng ở đây là khi giá trị của một cặp vượt hai phần ba giá trị cả nhóm. Bài học đọc được: liên minh lớn chỉ bền khi nó thật sự làm ra nhiều hơn hẳn những liên minh nhỏ bên trong. Nếu hai người đã gần đủ, người thứ ba trở thành gánh nặng mà không cách chia nào bù được.
Bài toán găng tay: lõi có thể rất "phũ"
Một ví dụ kinh điển cho thấy lõi không quan tâm tới cảm giác công bằng. Một người có một chiếc găng tay trái, hai người khác mỗi người có một chiếc găng tay phải. Một chiếc lẻ không bán được, một đôi bán được 100 nghìn đồng.
Lõi ở đây chỉ có một điểm: người giữ găng trái nhận cả 100, hai người giữ găng phải nhận 0. Lý do: nếu người giữ găng trái bắt cặp với người phải thứ nhất và chia cho anh ta bất kỳ khoản dương nào, người phải thứ hai sẽ nhảy vào chào giá thấp hơn. Cạnh tranh giữa hai người phải đẩy phần của họ về 0.
Giá trị Shapley cho kết quả khác: người giữ găng trái 66,7 nghìn, mỗi người giữ găng phải 16,7 nghìn. Shapley thưởng cho việc "có mặt", còn lõi phản ánh sức mạnh của cạnh tranh: bên nào khan hiếm thì bên đó nắm trọn phần lợi. Hai khái niệm đo hai thứ khác nhau, và chỗ chúng vênh nhau chính là chỗ đáng suy nghĩ khi đàm phán.
Nhân rộng ra một chợ găng tay có 100 chiếc trái và 101 chiếc phải, lõi vẫn dồn toàn bộ lợi ích về phía găng trái. Chỉ một chiếc dư cũng đủ lật thế mặc cả. Đây là cách lý thuyết hợp tác nói về cung và cầu.
Lịch sử: từ Edgeworth đến Bondareva và Shapley
- 1881: Francis Ysidro Edgeworth, trong cuốn Mathematical Psychics, mô tả "đường hợp đồng" giữa hai bên trao đổi hàng hoá và nhận xét rằng khi số người tham gia tăng lên, vùng thoả thuận co lại về giá thị trường cạnh tranh. Đây là tiền thân của khái niệm lõi.
- 1953 – 1959: Donald B. Gillies định nghĩa lõi một cách hình thức trong luận án ở Princeton (1953), công bố năm 1959. Lloyd Shapley cũng góp phần hình thành khái niệm trong cùng thời kỳ.
- 1963 – 1967: Olga Bondareva (Liên Xô, 1963) và Lloyd Shapley (Mỹ, 1967) độc lập chứng minh điều kiện cần và đủ để lõi khác rỗng, gọi là điều kiện "cân bằng". Kết quả nay mang tên định lý Bondareva–Shapley.
- 1963: Gerard Debreu và Herbert Scarf chứng minh rằng trong nền kinh tế trao đổi được "nhân bản" nhiều lần, lõi co dần về đúng các trạng thái cân bằng thị trường cạnh tranh, biến nhận xét của Edgeworth thành định lý.
- 1969: David Schmeidler đưa ra nucleolus, cách chia luôn nằm trong lõi mỗi khi lõi khác rỗng.
Điều kiện cân bằng nói gì, bằng lời thường
Hãy hình dung mỗi người có một ngày công để phân bổ cho các liên minh con. Ví dụ, mỗi người dành nửa ngày cho mỗi cặp mình thuộc về. Ba cặp, mỗi cặp làm nửa ngày, tạo ra tổng 1,5 lần giá trị cặp. Điều kiện cân bằng đòi: không có cách phân bổ thời gian nào như vậy làm ra nhiều hơn cả nhóm làm chung trọn ngày. Với ví dụ cửa hàng, 1,5 × 70 = 105 ≤ 120, lõi khác rỗng; 1,5 × 90 = 135 > 120, lõi rỗng. Đúng như đã tính tay ở trên.
Lõi rỗng thì làm gì
Lõi rỗng không có nghĩa là không hợp tác được. Nó có nghĩa là liên minh lớn cần thêm một thứ gì đó ngoài lợi ích thuần tuý để đứng vững:
- Hợp đồng ràng buộc: ký cam kết dài hạn, có phạt khi rút, làm cho chuyện tách ra tốn kém hơn.
- Chi phí chuyển đổi: nếu tìm đối tác mới mất thời gian, các liên minh nhỏ bớt hấp dẫn, lõi "nới" ra. Giới nghiên cứu gọi đây là ε-lõi: chấp nhận rằng nhóm con chỉ tách ra khi được lợi hơn một ngưỡng ε.
- Thiết kế lại liên minh: có khi ba người không nên đi cùng nhau, hai người là cấu hình tự nhiên. Biết lõi rỗng giúp tránh tốn công giữ một nhóm không giữ được.
- Thêm giá trị cho cả nhóm: tìm việc chỉ cả ba cùng làm mới làm được (một hợp đồng lớn, một đơn hàng đủ chuyến xe), đẩy giá trị cả nhóm lên vượt ngưỡng.
Góc nhìn hôm nay: tự kiểm một liên minh của mình
Bất kỳ nhóm nào cũng có thể làm bài kiểm này trong nửa giờ: nhóm mua chung, nhóm chạy chung một gian hàng hội chợ, ba hộ chung tiền kéo đường nước.
- Ghi giá trị mỗi người tự làm được, mỗi cặp làm được, cả nhóm làm được. Ước lượng thật thà.
- Đề xuất một cách chia. Kiểm từng người, từng cặp xem có ai nhận ít hơn số họ tự làm ra được không.
- Nếu có, hoặc sửa cách chia, hoặc chấp nhận rằng cấu hình nhóm cần xem lại.
Muốn đọc sâu, chương về lõi trong giáo trình của Maschler, Solan và Zamir (Cambridge, 2013) trình bày đủ định lý Bondareva–Shapley kèm chứng minh; cuốn Mathematical Psychics của Edgeworth (1881) nay đã thuộc phạm vi công cộng và đọc được bản số hoá.
Câu hỏi thường gặp
Lõi (core) trong lý thuyết hợp tác là gì?
Lõi là tập hợp các cách chia thành quả chung sao cho không nhóm con nào nhận ít hơn số họ tự làm ra được. Nếu một cách chia nằm trong lõi, không ai có động cơ tách ra làm riêng. Lõi có thể rộng, chỉ có một điểm, hoặc rỗng.
Lõi rỗng nghĩa là gì?
Lõi rỗng nghĩa là mọi cách chia đều để lại ít nhất một nhóm con muốn bỏ đi. Ví dụ ba người, mỗi cặp làm ra 90 mà cả ba chỉ làm ra 120: tổng cần để giữ mọi cặp là 135, không đủ. Liên minh lớn khi đó chỉ đứng vững nhờ hợp đồng hoặc chi phí chuyển đổi.
Lõi khác giá trị Shapley thế nào?
Giá trị Shapley là một cách chia cụ thể dựa trên đóng góp biên trung bình, luôn tồn tại và duy nhất. Lõi là một tập các cách chia dựa trên điều kiện không ai muốn bỏ đi. Giá trị Shapley có thể nằm trong hoặc ngoài lõi tuỳ bài toán.
Định lý Bondareva–Shapley nói gì?
Định lý cho biết lõi khác rỗng khi và chỉ khi bài toán thoả điều kiện cân bằng: không có cách phân bổ thời gian của mỗi người cho các nhóm con nào làm ra nhiều hơn cả nhóm làm chung. Olga Bondareva (1963) và Lloyd Shapley (1967) chứng minh độc lập với nhau.
Vì sao trong bài toán găng tay, bên khan hiếm nhận hết?
Vì những người ở bên dư thừa cạnh tranh với nhau: ai đòi phần dương thì người khác cùng phía sẵn sàng nhận ít hơn. Cạnh tranh đẩy phần của bên dư về 0, và lõi chỉ còn một điểm dồn hết lợi ích cho bên khan hiếm. Giá trị Shapley thì vẫn chia một phần cho bên dư.