2025-11-21T04:58:15.553839

Axiomatic and Probabilistic Foundations for the Hodge-Theoretic Shapley Value

Lim
This paper establishes a complete theoretical foundation for the Hodge-theoretic extension of the Shapley value introduced by Stern and Tettenhorst (2019). We show that a set of five axioms--efficiency, linearity, symmetry, a modified null-player condition, and an independency principle--uniquely characterize this value across all coalitions, not just the grand coalition. In parallel, we derive a probabilistic representation interpreting each player's value as the expected cumulative marginal contribution along a random walk on the coalition graph. These dual axiomatic and probabilistic results unify fairness and stochastic interpretation, positioning the Hodge-theoretic value as a canonical generalization of Shapley's framework.
academic

Hodge-सैद्धांतिक Shapley मान के लिए स्वयंसिद्ध और संभाव्य आधार

मूल जानकारी

  • पेपर ID: 2106.15094
  • शीर्षक: Axiomatic and Probabilistic Foundations for the Hodge-Theoretic Shapley Value
  • लेखक: Tongseok Lim (Purdue University)
  • वर्गीकरण: math.OC cs.GT econ.TH
  • प्रकाशन समय: 14 अक्टूबर, 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2106.15094

सारांश

यह पेपर Stern और Tettenhorst (2019) द्वारा प्रस्तावित Hodge सिद्धांत Shapley मान विस्तार के लिए संपूर्ण सैद्धांतिक आधार स्थापित करता है। लेखक ने पाँच स्वयंसिद्धों का एक समूह—दक्षता, रैखिकता, सममितता, संशोधित शून्य-खिलाड़ी स्थिति और स्वतंत्रता सिद्धांत—प्रदर्शित किया है जो सभी गठबंधनों (केवल बड़े गठबंधन नहीं) पर इस मान को विशिष्ट रूप से चिह्नित करता है। साथ ही, लेखक ने एक संभाव्य प्रतिनिधित्व प्राप्त किया है, जो प्रत्येक प्रतिभागी के मान की व्याख्या गठबंधन ग्राफ पर यादृच्छिक चलन के साथ अपेक्षित संचयी सीमांत योगदान के रूप में करता है। ये दोहरे स्वयंसिद्ध और संभाव्य परिणाम न्यायसंगतता और यादृच्छिक व्याख्या को एकीकृत करते हैं, Hodge सैद्धांतिक मान को Shapley ढांचे के विशिष्ट सामान्यीकरण के रूप में स्थापित करते हैं।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

शास्त्रीय Shapley मान सिद्धांत मानता है कि सभी प्रतिभागी अंततः एक बड़े गठबंधन का निर्माण करेंगे, और कुल मान v(N) के न्यायसंगत वितरण को निर्धारित करने के लिए चार स्वयंसिद्धों (दक्षता, सममितता, शून्य-खिलाड़ी, रैखिकता) का उपयोग करता है। हालांकि, यह सिद्धांत सीधे मूल्यांकन नहीं कर सकता कि जब खेल आंशिक गठबंधन स्थिति S ⊊ N पर समाप्त होता है तो प्रतिभागियों का योगदान क्या है।

अनुसंधान प्रेरणा

  1. सैद्धांतिक कमी: हालांकि Shapley सूत्र को प्रत्येक उप-खेल पर लागू किया जा सकता है, लेकिन यह विधि निहित रूप से मानती है कि गठबंधन केवल लक्ष्य S तक बढ़ता है, N में सभी प्रतिभागियों को शामिल करने वाले बड़े खेल की संपूर्ण संरचना को नहीं पकड़ता है।
  2. व्यावहारिक आवश्यकता: आधुनिक अनुप्रयोग (मशीन लर्निंग में डेटा मूल्यांकन, विशेषता आरोपण, चिकित्सा मॉडल व्याख्या आदि) को आंशिक गठबंधन में प्रतिभागियों के योगदान का मूल्यांकन करने की आवश्यकता है।
  3. सैद्धांतिक पूर्णता: Stern-Tettenhorst ढांचा, हालांकि नवीन है, दो महत्वपूर्ण समस्याओं से ग्रस्त है:
    • सभी आंशिक गठबंधन मानों को विशिष्ट रूप से चिह्नित करने के लिए संपूर्ण स्वयंसिद्ध आधार का अभाव
    • Shapley सूत्र के समान संभाव्य व्याख्या का अभाव

मुख्य योगदान

  1. संपूर्ण स्वयंसिद्ध चिह्नांकन: पाँच स्वयंसिद्धों (A1-A5) का प्रस्ताव दिया गया है, जो केवल बड़े गठबंधन तक सीमित न होकर सभी गठबंधन स्थितियों में मान वितरण को विशिष्ट रूप से निर्धारित करते हैं।
  2. संभाव्य प्रतिनिधित्व प्रमेय: गठबंधन ग्राफ पर यादृच्छिक चलन के आधार पर संभाव्य सूत्र प्राप्त किया गया है, जो प्रतिभागी मान की व्याख्या अपेक्षित संचयी सीमांत योगदान के रूप में करता है।
  3. सैद्धांतिक एकीकरण: स्वयंसिद्ध विधि और संभाव्य व्याख्या के बीच समतुल्यता स्थापित की गई है, जो Hodge सैद्धांतिक Shapley मान के लिए दृढ़ सैद्धांतिक आधार प्रदान करती है।
  4. गणना विधि: प्रदर्शित किया गया है कि संभाव्य रूप से परिभाषित मान को रैखिक समीकरण समूह (3.3) को हल करके कुशलतापूर्वक गणना की जा सकती है।

विधि विवरण

कार्य परिभाषा

सहकारी खेल v ∈ G_N दिया गया है, प्रत्येक गठबंधन S ⊆ N और प्रत्येक प्रतिभागी i ∈ N के लिए मान Φ_i(v,S) निर्दिष्ट करें, जो न्यायसंगतता मानदंड को संतुष्ट करता है और संभाव्य व्याख्या रखता है।

मुख्य ढांचा

1. गठबंधन ग्राफ निर्माण

हाइपरक्यूब ग्राफ G = (V,E) का उपयोग करके गठबंधन स्थान का प्रतिनिधित्व करें:

  • शीर्ष समूह: V := 2^N = {S | S ⊆ N}
  • किनारा समूह: E := {(S, S ∪ {i}) ∈ V × V | S ⊆ N \ {i}, i ∈ N}

2. Poisson समीकरण

Stern-Tettenhorst द्वारा प्रस्तावित संतुलन समीकरण:

Φ_i(v,S) - (1/|N|)∑_{T~S} Φ_i(v,T) = (1/|N|)∑_{T~S} ∂_iv(T,S)

जहाँ ∂_iv प्रतिभागी i का सीमांत योगदान दर्शाता है।

3. पाँच स्वयंसिद्ध प्रणाली

  • A1 (दक्षता): v(S) = ∑_{i∈N} Φ_i(v,S)
  • A2 (रैखिकता): Φ_i(αv + α'v', S) = αΦ_i(v,S) + α'Φ_i(v',S)
  • A3 (सममितता): Φ_i(v^{ij}, S^{ij}) = Φ_j(v,S)
  • A4 (शून्य-खिलाड़ी): यदि ∂iv ≡ 0, तो Φ_j(v, S∪{i}) = Φ_j(v,S) = Φ_j(v{-i}, S)
  • A5 (स्वतंत्रता): सभी S ⊆ N{i} के लिए, Φ_i(v,S) + Φ_i(v, S∪{i})/2 एक स्थिरांक है

तकनीकी नवाचार बिंदु

1. स्वतंत्रता स्वयंसिद्ध (A5)

यह मुख्य नवाचार है, जो आवश्यकता रखता है कि प्रतिभागी i के गठबंधन के अंदर और बाहर की स्थितियों का औसत मान विशिष्ट गठबंधन S से स्वतंत्र हो। यह स्थिति:

  • शास्त्रीय Shapley स्वयंसिद्धों की कमियों को पूरक करती है
  • सभी आंशिक गठबंधनों पर मानों की विशिष्टता सुनिश्चित करती है
  • सहज न्यायसंगतता व्याख्या रखती है

2. यादृच्छिक चलन मॉडल

गठबंधन स्थान पर परिभाषित मार्कोव श्रृंखला:

  • संक्रमण संभावना: p_{S,T} = 1/|N| यदि T ~ S
  • प्रतिभागियों को गठबंधन में शामिल होने और छोड़ने की अनुमति देता है
  • प्रारंभिक स्थिति: X_0 = ∅

3. पथ समाकलन प्रतिनिधित्व

प्रतिभागी i के गठबंधन S तक पहुँचने का अपेक्षित कुल योगदान:

Ψ_i(v,S) = E[∑_{t=1}^{τ_S} ∂_iv(X_{t-1}, X_t)]

मुख्य सैद्धांतिक परिणाम

प्रमेय 4.1 (विशिष्टता चिह्नांकन)

एक अद्वितीय मानचित्र Φ मौजूद है जो स्वयंसिद्ध A1-A5 और प्रारंभिक स्थिति Φ(v,∅) = 0 को संतुष्ट करता है, और यह मानचित्र ठीक Poisson समीकरण (3.3) का समाधान है।

प्रमेय 5.1 (संभाव्य समतुल्यता)

Φ = Ψ, अर्थात् स्वयंसिद्ध रूप से परिभाषित मान और संभाव्य पथ समाकलन द्वारा परिभाषित मान पूरी तरह से समान हैं।

प्रायोगिक सत्यापन

दस्ताने खेल उदाहरण

3-व्यक्ति दस्ताने खेल के लिए (प्रतिभागी 1 के पास बाएँ दस्ताने हैं, प्रतिभागी 2, 3 के पास दाएँ दस्ताने हैं):

  • शास्त्रीय Shapley मान: ϕ_1(v) = 2/3, ϕ_2(v) = ϕ_3(v) = 1/6
  • Hodge सैद्धांतिक मान सभी आंशिक गठबंधनों के लिए संपूर्ण मान तालिका प्रदान करता है

दो-व्यक्ति खेल प्रत्यक्ष गणना

लेखक ने दो-व्यक्ति खेल में Ψ मान की प्रत्यक्ष गणना प्रक्रिया को विस्तार से प्रदर्शित किया है, जो Poisson समीकरण समाधान के साथ सामंजस्य को सत्यापित करता है।

संबंधित कार्य

शास्त्रीय सैद्धांतिक आधार

  • Shapley (1953) की मूल चार-स्वयंसिद्ध प्रणाली
  • सहकारी खेल सिद्धांत की स्वयंसिद्ध विधि परंपरा

आधुनिक विस्तार

  • खेल सिद्धांत में संयोजी Hodge सिद्धांत का अनुप्रयोग (Candogan et al., 2011)
  • ग्राफ Poisson समीकरण की खेल-सैद्धांतिक व्याख्या (Jiang et al., 2011)
  • Stern-Tettenhorst (2019) का अग्रणी कार्य

अनुप्रयोग क्षेत्र

  • मशीन लर्निंग में विशेषता आरोपण और डेटा मूल्यांकन
  • चिकित्सा मॉडल व्याख्या
  • टिकाऊ ऊर्जा लागत वितरण
  • सामाजिक नेटवर्क विश्लेषण

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. संपूर्ण चिह्नांकन: पाँच-स्वयंसिद्ध प्रणाली Hodge सैद्धांतिक Shapley मान को विशिष्ट रूप से निर्धारित करती है
  2. संभाव्य व्याख्या: यादृच्छिक चलन मॉडल प्रत्यक्ष संभाव्य अर्थ प्रदान करता है
  3. सैद्धांतिक एकीकरण: स्वयंसिद्ध और संभाव्य विधियों के बीच समतुल्यता स्थापित की गई है
  4. गणना व्यवहार्यता: रैखिक समीकरण समूह समाधान व्यावहारिक गणना विधि प्रदान करता है

सैद्धांतिक महत्व

  • ग्राफ पर Poisson समीकरण समाधान के लिए पहली बार संपूर्ण चिह्नांकन
  • Shapley सिद्धांत को बड़े गठबंधन से संपूर्ण गठबंधन जाली तक विस्तारित करना
  • न्यायसंगतता सिद्धांतों और यादृच्छिक प्रक्रिया व्याख्या का एकीकरण

सीमाएँ

  1. गणना जटिलता: बड़े पैमाने के खेलों के लिए, रैखिक समीकरण समूह समाधान गणना चुनौतियों का सामना कर सकता है
  2. मॉडल मान्यताएँ: समान संक्रमण संभावना सभी व्यावहारिक परिस्थितियों के लिए उपयुक्त नहीं हो सकती है
  3. अनुप्रयोग सत्यापन: सैद्धांतिक ढांचे की प्रभावशीलता को सत्यापित करने के लिए अधिक व्यावहारिक अनुप्रयोग सत्यापन की आवश्यकता है

भविष्य की दिशाएँ

  1. बड़े पैमाने के खेलों के लिए कुशल गणना एल्गोरिदम विकसित करना
  2. ढांचे को व्यावहारिक समस्याओं (अर्थशास्त्र, राजनीति विज्ञान, मशीन लर्निंग) पर लागू करना
  3. गैर-समान संक्रमण संभावना के विस्तार का अनुसंधान करना
  4. अन्य ग्राफ संरचनाओं पर समान सिद्धांत की खोज करना

गहन मूल्यांकन

लाभ

  1. सैद्धांतिक पूर्णता: Stern-Tettenhorst ढांचे की कमियों के लिए संपूर्ण सैद्धांतिक आधार प्रदान करता है
  2. विधि नवाचार: स्वतंत्रता स्वयंसिद्ध A5 मुख्य नवाचार है, जिसका गहरा सैद्धांतिक महत्व है
  3. दोहरी दृष्टिकोण: स्वयंसिद्ध और संभाव्य विधि का एकीकरण सिद्धांत की विश्वसनीयता बढ़ाता है
  4. कठोर प्रमाण: संयोजी Hodge सिद्धांत उपकरणों का उपयोग करके कठोर गणितीय प्रमाण

कमियाँ

  1. व्यावहारिक सत्यापन: बड़े पैमाने के व्यावहारिक अनुप्रयोगों का सत्यापन अभाव
  2. गणना दक्षता: बड़े पैमाने की स्थितियों में गणना जटिलता पर पर्याप्त चर्चा नहीं
  3. मॉडल सीमाएँ: समान यादृच्छिक चलन मान्यता अत्यधिक सरलीकृत हो सकती है

प्रभाव

  1. सैद्धांतिक योगदान: सहकारी खेल सिद्धांत के लिए महत्वपूर्ण सैद्धांतिक विस्तार
  2. अंतः-विषयक मूल्य: मशीन लर्निंग, अर्थशास्त्र आदि क्षेत्रों में अनुप्रयोग संभावना
  3. पद्धति महत्व: दिखाता है कि कैसे अमूर्त गणितीय उपकरणों को खेल-सैद्धांतिक समस्याओं पर लागू किया जाए

लागू परिस्थितियाँ

  • आंशिक गठबंधन योगदान का मूल्यांकन करने की आवश्यकता वाले सहकारी खेल
  • मशीन लर्निंग में मॉडल व्याख्या और विशेषता आरोपण
  • नेटवर्क विश्लेषण में नोड महत्व मूल्यांकन
  • अर्थशास्त्र में लागत/लाभ वितरण समस्याएँ

संदर्भ

  • Shapley, L. S. (1953). A value for n-person games.
  • Stern, A. & Tettenhorst, A. (2019). Hodge decomposition and the shapley value of a cooperative game. Games and Economic Behavior.
  • Candogan, O. et al. (2011). Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research.

यह पेपर Hodge सैद्धांतिक Shapley मान के लिए संपूर्ण सैद्धांतिक आधार प्रदान करता है, नवीन स्वयंसिद्ध विधि और संभाव्य व्याख्या के माध्यम से, शास्त्रीय Shapley सिद्धांत को संपूर्ण गठबंधन स्थान तक सफलतापूर्वक विस्तारित करता है, जिसका महत्वपूर्ण सैद्धांतिक मूल्य और व्यापक अनुप्रयोग संभावनाएँ हैं।