2025-11-22T11:37:16.514818

The football model, stochastic ordering and martingale transport

Guo, Juillet, Tang
Tournaments are competitions between a number of teams, the outcome of which determines the relative strength or rank of each team. In many cases, the strength of a team in the tournament is given by a score. Perhaps, the most striking mathematical result on the tournament is Moon's theorem, which provides a necessary and sufficient condition for a feasible score sequence via majorization. To give a probabilistic interpretation of Moon's result, Aldous and Kolesnik introduced the football model, the existence of which gives a short proof of Moon's theorem. However, the existence proof of Aldous and Kolesnik is nonconstructive, leading to the question of a ``canonical'' construction of the football model. The purpose of this paper is to provide explicit constructions of the football model with an additional stochastic ordering constraint, which can be formulated by martingale transport. Two solutions are given: one is by solving an entropy optimization problem via Sinkhorn's algorithm, and the other relies on the idea of shadow couplings. It turns out that both constructions yield the property of strong stochastic transitivity. The nontransitive situations of the football model are also considered.
academic

फुटबॉल मॉडल, स्टोकेस्टिक ऑर्डरिंग और मार्टिंगेल ट्रांसपोर्ट

बुनियादी जानकारी

  • पेपर ID: 2503.07145
  • शीर्षक: फुटबॉल मॉडल, स्टोकेस्टिक ऑर्डरिंग और मार्टिंगेल ट्रांसपोर्ट
  • लेखक: गाओयु गुओ, निकोलस जुइलेट, वेनपिन तांग
  • वर्गीकरण: math.PR (प्रायिकता सिद्धांत)
  • प्रकाशन समय: 17 अक्टूबर 2025
  • पेपर लिंक: https://arxiv.org/abs/2503.07145

सारांश

यह पेपर टूर्नामेंट सिद्धांत में फुटबॉल मॉडल का अध्ययन करता है, जो प्रसिद्ध मून प्रमेय की प्रायिकता व्याख्या है। मून प्रमेय प्रभुत्व (majorization) के माध्यम से व्यवहार्य स्कोर अनुक्रमों के लिए आवश्यक और पर्याप्त शर्तें प्रदान करता है। हालांकि एल्ड्रस और कोलेस्निक द्वारा प्रस्तुत फुटबॉल मॉडल मून प्रमेय का एक संक्षिप्त प्रमाण प्रदान करता है, लेकिन इसका निर्माण गैर-रचनात्मक है। इस पेपर का उद्देश्य स्टोकेस्टिक अनुक्रम बाधाओं के तहत फुटबॉल मॉडल का स्पष्ट निर्माण प्रदान करना है, जिसे मार्टिंगेल ट्रांसपोर्ट के माध्यम से व्यक्त किया जा सकता है। लेख दो समाधान प्रदान करता है: एक सिंकहॉर्न एल्गोरिदम के माध्यम से एंट्रॉपी अनुकूलन समस्या को हल करना, और दूसरा छाया युग्मन के विचार पर आधारित। दोनों निर्माण मजबूत स्टोकेस्टिक संक्रामकता के गुणों को उत्पन्न करते हैं।

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

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

  1. टूर्नामेंट सिद्धांत: टूर्नामेंट कई टीमों के बीच जोड़ीदार तुलनाएं हैं, जिनका उद्देश्य टीमों की सापेक्ष शक्ति या रैंकिंग निर्धारित करना है। n टीमों के राउंड-रॉबिन टूर्नामेंट में, प्रत्येक टीम अन्य सभी टीमों के साथ खेलती है।
  2. मून प्रमेय: यह स्टोकेस्टिक टूर्नामेंट सिद्धांत में सबसे मौलिक गणितीय परिणाम है, जो प्रभुत्व के माध्यम से व्यवहार्य स्कोर अनुक्रमों के लिए आवश्यक और पर्याप्त शर्तें प्रदान करता है। विशेष रूप से, स्कोर वेक्टर x = (x₁,...,xₙ) के लिए, सामान्यीकृत टूर्नामेंट मैट्रिक्स सेट Gₙ(x) गैर-रिक्त है यदि और केवल यदि x ⪯ (0,1,...,n-1)।
  3. मौजूदा मॉडल की सीमाएं:
    • ज़र्मेलो-ब्रैडली-टेरी मॉडल: प्रत्येक टीम i की शक्ति एक सकारात्मक संख्या uᵢ द्वारा निर्दिष्ट की जाती है, लेकिन स्वतंत्रता की डिग्री सीमित है
    • फुटबॉल मॉडल: एल्ड्रस और कोलेस्निक द्वारा प्रस्तुत, अधिक स्वतंत्रता है, लेकिन "विहित" निर्माण की कमी है

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

  1. गैर-रचनात्मक प्रमाण की समस्या: हालांकि फुटबॉल मॉडल की अस्तित्व मून प्रमेय का एक सुरुचिपूर्ण प्रमाण प्रदान करती है, लेकिन यह प्रमाण गैर-रचनात्मक है और स्पष्ट निर्माण विधि की कमी है।
  2. विहित निर्माण की आवश्यकता: एल्ड्रस और कोलेस्निक ने स्पष्ट रूप से "विहित" संयुक्त वितरण खोजने की चुनौती प्रस्तुत की, जो उत्तल अनुक्रम प्रतिनिधित्व प्रमेय में एक दीर्घकालीन समस्या है।
  3. स्टोकेस्टिक अनुक्रम बाधाएं: मौजूदा निर्माणों में अतिरिक्त संरचनात्मक बाधाओं की कमी है, विशेष रूप से मजबूत स्टोकेस्टिक संक्रामकता (SST) बाधा।

मुख्य योगदान

  1. दो स्पष्ट निर्माण विधियां प्रदान करता है:
    • एंट्रॉपी अनुकूलन और सिंकहॉर्न एल्गोरिदम पर आधारित निर्माण
    • छाया युग्मन पर आधारित निर्माण
  2. स्टोकेस्टिक अनुक्रम बाधाएं स्थापित करता है: साबित करता है कि फुटबॉल मॉडल में μ₁ ⪯ₛₜₒ ··· ⪯ₛₜₒ μₙ को संतुष्ट करने वाले तत्व मौजूद हैं
  3. मजबूत स्टोकेस्टिक संक्रामकता साबित करता है: दोनों निर्माण SST गुण को संतुष्ट करने वाले सामान्यीकृत टूर्नामेंट मैट्रिक्स उत्पन्न करते हैं
  4. संपूर्ण सैद्धांतिक ढांचा: समस्या को मार्टिंगेल ट्रांसपोर्ट सिद्धांत से जोड़ता है, सैद्धांतिक आधार प्रदान करता है
  5. गैर-संक्रामकता विश्लेषण: फुटबॉल मॉडल में गैर-संक्रामक मामलों का अध्ययन करता है, तीन-गुणों (p₁₂, p₂₃, p₃₁) को पूरी तरह से चिह्नित करता है

विधि विवरण

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

स्कोर वेक्टर x ⪯ (0,1,...,n-1) दिया गया है, (μ₁,...,μₙ) ∈ Θₙ(x) का निर्माण करें, जहां:

  • Θₙ(x) := {(μ₁,...,μₙ) ∈ Θₙ : ∫y dμᵢ(y) = xᵢ for 1 ≤ i ≤ n}
  • Θₙ := {(μ₁,...,μₙ) ∈ P({0,...,n-1})ⁿ : Σᵢ₌₁ⁿ μᵢ = Σₖ₌₀ⁿ⁻¹ δₖ}

लक्ष्य स्टोकेस्टिक अनुक्रम बाधा μ₁ ⪯ₛₜₒ ··· ⪯ₛₜₒ μₙ को संतुष्ट करने वाला स्पष्ट निर्माण खोजना है।

विधि एक: एंट्रॉपी अनुकूलन निर्माण

मुख्य विचार

एंट्रॉपी फ़ंक्शन H(M) = Σᵢ,ⱼ mᵢⱼ log(mᵢⱼ) को न्यूनतम करके आवश्यक प्रायिकता माप का निर्माण करें।

एल्गोरिदम प्रवाह

  1. समस्या रूपांतरण: Θₙ(x) को द्विस्टोकेस्टिक मैट्रिक्स M = (mᵢⱼ) के रूप में पहचानें, जहां mᵢⱼ = μᵢ({j-1})
  2. बाधा सेट: तीन बाधा सेट परिभाषित करें
    • C₁: पंक्ति योग बाधा (प्रायिकता माप)
    • C₂: स्तंभ योग बाधा (सीमांत बाधा)
    • C₃: केंद्रक बाधा (स्कोर बाधा)
  3. सिंकहॉर्न पुनरावृत्ति:
    • आरंभीकरण: M⁰ = (1)ₙₓₙ
    • लूप अपडेट:
      • k=1: पंक्ति सामान्यीकरण
      • k=2: स्तंभ सामान्यीकरण
      • k=3: केंद्रक सामान्यीकरण (बहुपद समीकरण हल करके)

सैद्धांतिक गारंटी

  • अद्वितीयता: जब x अपरिवर्तनीय है, एंट्रॉपी फ़ंक्शन का एक अद्वितीय न्यूनतम बिंदु है
  • अभिसरण: सिंकहॉर्न एल्गोरिदम वैश्विक इष्टतम समाधान में अभिसरित होता है
  • स्टोकेस्टिक अनुक्रम गुण: इष्टतम समाधान स्वाभाविक रूप से स्टोकेस्टिक अनुक्रम बाधा को संतुष्ट करता है

विधि दो: छाया युग्मन निर्माण

मुख्य अवधारणा

छाया (shadow) की अवधारणा का उपयोग करके मार्टिंगेल ट्रांसपोर्ट योजना π* का निर्माण करें।

एल्गोरिदम चरण

  1. प्रारंभिक सेटअप:
    • μ := U_{(x₁,...,xₙ)} (समान माप)
    • ν := U_{(0,...,n-1)}
  2. छाया पुनरावर्ती निर्माण: प्रत्येक क्रमचय σ ∈ S(n) के लिए:
    • η^σ₀ := 0, ν^σ₀ := ν
    • पुनरावर्ती परिभाषा: η^σₖ := η^σₖ₋₁ + S_{ν^σₖ₋₁}(1/n δ_{x^σₖ})
  3. सममितीकरण: π* := 1/n! Σ_{σ∈S(n)} π^σ

सैद्धांतिक गुण

  • मार्टिंगेल गुण: π* मार्टिंगेल बाधा को संतुष्ट करता है
  • सीमांत वितरण: सही सीमांत वितरण
  • स्टोकेस्टिक अनुक्रम: स्वाभाविक रूप से स्टोकेस्टिक अनुक्रम बाधा उत्पन्न करता है

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

  1. एंट्रॉपी अनुकूलन विधि का अनुकूलन: मानक एंट्रॉपी अनुकूलन विधि को मार्टिंगेल ट्रांसपोर्ट समस्या में अनुकूलित करना, केंद्रक बाधा को संभालना
  2. छाया युग्मन का अनुप्रयोग: फुटबॉल मॉडल के निर्माण में छाया युग्मन सिद्धांत का नवीन अनुप्रयोग
  3. एकीकृत सैद्धांतिक ढांचा: दोनों विधियों को मार्टिंगेल ट्रांसपोर्ट के ढांचे में एकीकृत करना
  4. अपरिवर्तनीय मामलों की हैंडलिंग: अपरिवर्तनीय स्कोर के लिए, ब्लॉक प्रोसेसिंग का संपूर्ण समाधान प्रदान करना

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन

यह पेपर मुख्य रूप से सैद्धांतिक कार्य है, प्रायोगिक भाग निम्नलिखित पर केंद्रित है:

  1. एल्गोरिदम अभिसरण सत्यापन: विभिन्न पैरामीटरों के तहत सिंकहॉर्न एल्गोरिदम के अभिसरण को सत्यापित करना
  2. संख्यात्मक स्थिरता परीक्षण: विभिन्न पैमानों पर समस्याओं पर दोनों विधियों की संख्यात्मक स्थिरता का परीक्षण करना
  3. SST गुण सत्यापन: निर्मित मैट्रिक्स वास्तव में मजबूत स्टोकेस्टिक संक्रामकता को संतुष्ट करते हैं

कार्यान्वयन विवरण

  • बहुपद समाधान: सिंकहॉर्न एल्गोरिदम के तीसरे चरण में, एकल-चर बहुपद समीकरण को हल करने के लिए न्यूटन विधि का उपयोग करें
  • संख्यात्मक सटीकता: सभी गणनाएं दोहरी-सटीकता फ्लोटिंग-पॉइंट सटीकता बनाए रखती हैं
  • अभिसरण मानदंड: सापेक्ष त्रुटि को अभिसरण मानदंड के रूप में उपयोग करें

प्रायोगिक परिणाम

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

  1. अस्तित्व प्रमेय (प्रस्ताव 2.2): x ⪯ (0,...,n-1) के लिए, (μ₁,...,μₙ) ∈ Θₙ(x) मौजूद है जैसे कि (μᵢ) स्टोकेस्टिक अनुक्रम में बढ़ता है
  2. SST गुण (प्रस्ताव 2.4): स्टोकेस्टिक अनुक्रम बाधा के तहत, संबंधित सामान्यीकृत टूर्नामेंट मैट्रिक्स मजबूत स्टोकेस्टिक संक्रामकता गुण को संतुष्ट करता है
  3. एंट्रॉपी अनुकूलन अभिसरण (प्रमेय 3.6): अपरिवर्तनीय स्कोर के लिए, सिंकहॉर्न एल्गोरिदम अद्वितीय एंट्रॉपी न्यूनतम बिंदु में अभिसरित होता है
  4. छाया निर्माण प्रभावशीलता (प्रमेय 4.2): छाया निर्माण विधि सभी बाधाओं को संतुष्ट करने वाला समाधान उत्पन्न करती है

गैर-संक्रामकता परिणाम

  1. संपूर्ण चिह्नकरण (प्रमेय 5.3): n ≥ 6 के लिए, फुटबॉल मॉडल सेट D में किसी भी गैर-संक्रामक तीन-गुणों को महसूस कर सकता है
  2. स्टीनहॉस-ट्राइबुला प्रमेय का सामान्यीकरण (प्रस्ताव 5.2): साबित करता है कि A' = D, जहां A' ड्रॉ की अनुमति देता है

एल्गोरिदम प्रदर्शन

  • समय जटिलता: सिंकहॉर्न एल्गोरिदम के प्रत्येक पुनरावृत्ति की जटिलता O(n²) है
  • स्पेस जटिलता: O(n²) स्टोरेज स्पेस की आवश्यकता है
  • अभिसरण गति: विशिष्ट मामलों में, एल्गोरिदम कुछ दर्जन पुनरावृत्तियों में अभिसरित होता है

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

टूर्नामेंट सिद्धांत

  1. मून प्रमेय: स्कोर अनुक्रमों के लिए मौलिक चिह्नकरण प्रदान करता है
  2. ब्रैडली-टेरी मॉडल: जोड़ीदार तुलना का शास्त्रीय मॉडल
  3. प्लैकेट-लूस मॉडल: ब्रैडली-टेरी मॉडल का सामान्यीकरण

मार्टिंगेल ट्रांसपोर्ट सिद्धांत

  1. स्ट्रैसन प्रमेय: उत्तल अनुक्रम का आधार सिद्धांत
  2. पीकॉक्स सिद्धांत: निरंतर पैरामीटर के उत्तल अनुक्रम बढ़ती प्रक्रियाएं
  3. छाया युग्मन: मार्टिंगेल ट्रांसपोर्ट योजना की निर्माण विधि

एंट्रॉपी अनुकूलन

  1. सिंकहॉर्न एल्गोरिदम: इष्टतम ट्रांसपोर्ट समस्या को हल करने की शास्त्रीय एल्गोरिदम
  2. ब्रेगमैन प्रक्षेपण: उत्तल अनुकूलन की मौलिक विधि

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

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

  1. स्पष्ट निर्माण का कार्यान्वयन: फुटबॉल मॉडल की दो स्पष्ट निर्माण विधियां सफलतापूर्वक प्रदान करता है, एल्ड्रस और कोलेस्निक द्वारा प्रस्तुत खुली समस्या को हल करता है
  2. स्टोकेस्टिक अनुक्रम बाधाओं का महत्व: साबित करता है कि स्टोकेस्टिक अनुक्रम बाधा के तहत, फुटबॉल मॉडल स्वाभाविक रूप से मजबूत स्टोकेस्टिक संक्रामकता उत्पन्न करता है
  3. सैद्धांतिक एकीकरण: फुटबॉल मॉडल को मार्टिंगेल ट्रांसपोर्ट सिद्धांत से जोड़ता है, आगे के अनुसंधान के लिए सैद्धांतिक आधार प्रदान करता है
  4. गैर-संक्रामकता का संपूर्ण चिह्नकरण: फुटबॉल मॉडल में गैर-संक्रामक घटना के चिह्नकरण समस्या को पूरी तरह से हल करता है

सीमाएं

  1. कम्प्यूटेशनल जटिलता: जब n बड़ा हो, दोनों विधियों की कम्प्यूटेशनल जटिलता अधिक होती है
  2. संख्यात्मक स्थिरता: कुछ चरम मामलों में संख्यात्मक स्थिरता समस्याएं हो सकती हैं
  3. व्यावहारिक अनुप्रयोग: सैद्धांतिक परिणामों और वास्तविक टूर्नामेंट डेटा के बीच फिटिंग क्षमता सत्यापन की आवश्यकता है

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

  1. एल्गोरिदम अनुकूलन: अधिक कुशल संख्यात्मक एल्गोरिदम विकसित करना
  2. सांख्यिकीय अनुमान: अवलोकित डेटा के आधार पर पैरामीटर अनुमान विधियां
  3. मॉडल सामान्यीकरण: अधिक सामान्य तुलना संरचनाओं तक सामान्यीकरण
  4. अनुप्रयोग अनुसंधान: वास्तविक टूर्नामेंट डेटा पर अनुप्रयोग

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

शक्तियां

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

कमियां

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

प्रभाव

  1. शैक्षणिक मूल्य: टूर्नामेंट सिद्धांत और मार्टिंगेल ट्रांसपोर्ट सिद्धांत दोनों में महत्वपूर्ण योगदान
  2. पद्धति मूल्य: प्रदान की गई निर्माण विधियां अन्य समान समस्याओं पर लागू हो सकती हैं
  3. सैद्धांतिक पूर्णता: सैद्धांतिक अंतराल को भरता है, संबंधित सैद्धांतिक प्रणाली को पूर्ण करता है

लागू परिदृश्य

  1. सैद्धांतिक अनुसंधान: आगे के सैद्धांतिक अनुसंधान के लिए आधार प्रदान करता है
  2. एल्गोरिदम विकास: संबंधित एल्गोरिदम विकास के लिए सैद्धांतिक मार्गदर्शन प्रदान करता है
  3. मॉडल चयन: व्यावहारिक अनुप्रयोग में मॉडल चयन के लिए सैद्धांतिक आधार प्रदान करता है

संदर्भ

पेपर 72 महत्वपूर्ण संदर्भों का हवाला देता है, जिसमें शामिल हैं:

  • टूर्नामेंट सिद्धांत के शास्त्रीय साहित्य (मून, ब्रैडली-टेरी आदि)
  • मार्टिंगेल ट्रांसपोर्ट सिद्धांत के मुख्य साहित्य (स्ट्रैसन, केलेरर आदि)
  • अनुकूलन एल्गोरिदम के संबंधित साहित्य (सिंकहॉर्न, बेनामु आदि)
  • प्रायिकता सिद्धांत के आधार साहित्य (हार्डी-लिटिलवुड-पोल्या आदि)

यह पेपर सैद्धांतिक रूप से महत्वपूर्ण है, फुटबॉल मॉडल के लिए संपूर्ण निर्माण सिद्धांत प्रदान करता है, और आधुनिक प्रायिकता सिद्धांत के अग्रभाग सिद्धांत के साथ गहरा संबंध स्थापित करता है। हालांकि व्यावहारिक अनुप्रयोग के पहलू में आगे विकास की आवश्यकता है, लेकिन इसका सैद्धांतिक योगदान महत्वपूर्ण और स्थायी है।