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

نموذج كرة القدم والترتيب العشوائي ونقل المارتينجيل

المعلومات الأساسية

  • معرّف الورقة: 2503.07145
  • العنوان: The Football Model, Stochastic Ordering and Martingale Transport
  • المؤلفون: Gaoyue Guo, Nicolas Juillet, Wenpin Tang
  • التصنيف: math.PR (نظرية الاحتمالات)
  • تاريخ النشر: 17 أكتوبر 2025
  • رابط الورقة: https://arxiv.org/abs/2503.07145

الملخص

تدرس هذه الورقة نموذج كرة القدم في نظرية البطولات، وهو تفسير احتمالي للنظرية الشهيرة لـ Moon. توفر نظرية Moon من خلال الهيمنة (majorization) الشروط الضرورية والكافية لتسلسلات الدرجات الممكنة. على الرغم من أن نموذج كرة القدم الذي قدمه Aldous و Kolesnik يوفر إثباتاً قصيراً لنظرية Moon، إلا أن بناؤه غير بنّاء. الهدف من هذه الورقة هو توفير بناء صريح لنموذج كرة القدم تحت قيود الترتيب العشوائي، والذي يمكن صياغته من خلال نقل المارتينجيل. تقدم المقالة حلين: أحدهما من خلال حل مشكلة التحسين الإنتروبي باستخدام خوارزمية Sinkhorn، والآخر يعتمد على فكرة الاقتران الظلي. ينتج عن كلا البناءين خصائص الانتقالية العشوائية القوية.

الخلفية البحثية والدافع

خلفية المشكلة

  1. نظرية البطولات: البطولة هي مقارنات زوجية بين فرق متعددة، بهدف تحديد القوة النسبية أو الترتيب. في دوري دائري بـ n فريق، يلعب كل فريق مع كل فريق آخر.
  2. نظرية Moon: هذه هي النتيجة الرياضية الأساسية في نظرية البطولات العشوائية، وتوفر من خلال الهيمنة الشروط الضرورية والكافية لتسلسلات الدرجات الممكنة. بشكل محدد، لمتجه الدرجات x = (x₁,...,xₙ)، مجموعة مصفوفات البطولة المعممة Gₙ(x) غير فارغة إذا وفقط إذا كان x ⪯ (0,1,...,n-1).
  3. قيود النماذج الموجودة:
    • نموذج Zermelo-Bradley-Terry: يتم تحديد قوة كل فريق i برقم موجب uᵢ، لكن درجات الحرية محدودة
    • نموذج كرة القدم: قدمه Aldous و Kolesnik، يتمتع بدرجات حرية أكثر، لكن يفتقر إلى بناء "قانوني"

دافع البحث

  1. مشكلة الإثبات غير البنّاء: على الرغم من أن وجود نموذج كرة القدم يوفر إثباتاً أنيقاً لنظرية Moon، إلا أن هذا الإثبات غير بنّاء ويفتقر إلى طرق البناء الصريحة.
  2. الحاجة إلى البناء القانوني: طرح Aldous و Kolesnik بوضوح تحدي البحث عن التوزيع المشترك "القانوني"، وهي مشكلة موجودة منذ فترة طويلة في نظريات تمثيل الترتيب المحدب.
  3. قيود الترتيب العشوائي: البناءات الموجودة تفتقر إلى قيود هيكلية إضافية، خاصة قيود الانتقالية العشوائية القوية (SST).

المساهمات الأساسية

  1. توفير طريقتي بناء صريحتين:
    • البناء القائم على التحسين الإنتروبي وخوارزمية Sinkhorn
    • البناء القائم على الاقتران الظلي
  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. تكرار Sinkhorn:
    • التهيئة: M⁰ = (1)ₙₓₙ
    • التحديث الدوري:
      • k=1: تطبيع الصفوف
      • k=2: تطبيع الأعمدة
      • k=3: تطبيع مركز الثقل (من خلال حل معادلة متعددة الحدود)

الضمانات النظرية

  • الفرادة: عندما تكون x غير قابلة للاختزال، تتمتع دالة الإنتروبيا بنقطة حد أدنى فريدة
  • التقارب: تتقارب خوارزمية Sinkhorn إلى الحل الأمثل العام
  • خاصية الترتيب العشوائي: يحقق الحل الأمثل بشكل طبيعي قيود الترتيب العشوائي

الطريقة الثانية: بناء الاقتران الظلي

المفهوم الأساسي

استخدام مفهوم الظل (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. التحقق من تقارب الخوارزمية: التحقق من تقارب خوارزمية Sinkhorn تحت معاملات مختلفة
  2. اختبارات الاستقرار العددي: اختبار الاستقرار العددي للطريقتين على مشاكل بأحجام مختلفة
  3. التحقق من خاصية SST: التحقق من أن المصفوفات المبنية تحقق بالفعل الانتقالية العشوائية القوية

تفاصيل التنفيذ

  • حل المعادلات متعددة الحدود: في الخطوة الثالثة من خوارزمية Sinkhorn، استخدام طريقة Newton لحل معادلات متعددة الحدود أحادية المتغير
  • الدقة العددية: الحفاظ على دقة الفاصلة العائمة المزدوجة في جميع الحسابات
  • معيار التقارب: استخدام الخطأ النسبي كمعيار تقارب

نتائج التجارب

النتائج النظرية الرئيسية

  1. نظرية الوجود (الاقتراح 2.2): لـ x ⪯ (0,...,n-1)، يوجد (μ₁,...,μₙ) ∈ Θₙ(x) بحيث تكون (μᵢ) متزايدة بالترتيب العشوائي
  2. خاصية SST (الاقتراح 2.4): تحت قيود الترتيب العشوائي، مصفوفات البطولة المعممة المقابلة تحقق الانتقالية العشوائية القوية
  3. تقارب التحسين الإنتروبي (النظرية 3.6): للدرجات غير القابلة للاختزال، تتقارب خوارزمية Sinkhorn إلى نقطة الحد الأدنى الفريدة للإنتروبيا
  4. فعالية البناء الظلي (النظرية 4.2): طريقة البناء الظلي تنتج حلاً يحقق جميع القيود

نتائج عدم الانتقالية

  1. التوصيف الكامل (النظرية 5.3): لـ n ≥ 6، يمكن لنموذج كرة القدم تحقيق أي ثلاثية غير متعدية في المجموعة D
  2. تعميم نظرية Steinhaus-Trybula (الاقتراح 5.2): إثبات أن A' = D، حيث A' يسمح بحالات التعادل

أداء الخوارزمية

  • التعقيد الزمني: التعقيد الزمني لكل تكرار من خوارزمية Sinkhorn هو O(n²)
  • التعقيد المكاني: يتطلب مساحة تخزين O(n²)
  • سرعة التقارب: في الحالات النموذجية، تتقارب الخوارزمية في عشرات التكرارات

الأعمال ذات الصلة

نظرية البطولات

  1. نظرية Moon: توفر التوصيف الأساسي لتسلسلات الدرجات
  2. نموذج Bradley-Terry: نموذج المقارنة الزوجية الكلاسيكي
  3. نموذج Plackett-Luce: تعميم نموذج Bradley-Terry

نظرية نقل المارتينجيل

  1. نظرية Strassen: النظرية الأساسية للترتيب المحدب
  2. نظرية Peacocks: الترتيب المحدب المتزايد للعمليات ذات المعاملات المستمرة
  3. الاقتران الظلي: طريقة بناء خطط نقل المارتينجيل

التحسين الإنتروبي

  1. خوارزمية Sinkhorn: الخوارزمية الكلاسيكية لحل مشاكل النقل الأمثل
  2. إسقاط Bregman: الطريقة الأساسية للتحسين المحدب

الخلاصة والنقاش

الاستنتاجات الرئيسية

  1. تحقيق البناء الصريح: نجح في توفير طريقتي بناء صريحتين لنموذج كرة القدم، مما يحل المشكلة المفتوحة التي طرحها Aldous و Kolesnik
  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 مرجعاً مهماً، تغطي:

  • الأدبيات الكلاسيكية لنظرية البطولات (Moon, Bradley-Terry وغيرهم)
  • الأدبيات الأساسية لنظرية نقل المارتينجيل (Strassen, Kellerer وغيرهم)
  • الأدبيات ذات الصلة بخوارزميات التحسين (Sinkhorn, Benamou وغيرهم)
  • أدبيات نظرية الاحتمالات الأساسية (Hardy-Littlewood-Pólya وغيرهم)

تتمتع هذه الورقة بقيمة نظرية مهمة، حيث توفر نظرية بناء شاملة لنموذج كرة القدم، وتنشئ روابط عميقة مع نظريات الاحتمالات الحديثة. على الرغم من أن هناك حاجة إلى مزيد من التطوير في جوانب التطبيق العملي، إلا أن مساهماتها النظرية كبيرة ودائمة.