💻 computer science

Learning in Proportional Allocation Auctions Games

تثبت هذه الورقة وجود توازن ناش فريد في ألعاب تخصيص كيلي المتكررة ذات المنفعة اللوغاريتمية، وتثبت التقارب نحو هذا التوازن تحت خوارزميات التدرج عبر الإنترنت (Online Gradient Descent)، والمتوسط المزدوج (Dual Averaging)، وديناميكيات الاستجابة المثلى الحدسية (myopic best-response dynamics)، مع إثبات أن استراتيجيات الاستجابة المثلى تحقق أسرع تقارب وأعلى منفعة من خلال المحاكاة.

المؤلفون الأصليون: Younes Ben Mazziane, Cleque-Marlain Mboulou Moutoubi, Eitan Altman, Francesco De Pellegrini

نُشر 2026-03-27

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Younes Ben Mazziane, Cleque-Marlain Mboulou Moutoubi, Eitan Altman, Francesco De Pellegrini

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل بيتزا عملاقة لا نهاية لها، يجب تقاسمها بين مجموعة من الأصدقاء الجائعين. لكن إليك العقبة: الشخص الذي يقطع البيتزا لا يعرف مدى جوع كل صديق. بدلاً من ذلك، يتعين على الجميع الصراخ برقم (مزايدة) لقول: "أنا جائع حقاً، أعطني قطعة كبيرة!"

القاعدة بسيطة: كلما صرخت أكثر، حصلت على قطعة أكبر. إذا صرخت أنت "10" وصرخ صديقك "5"، فستحصل على ضعف كمية البيتزا التي حصل عليها هو. هذا ما يسمى بـ آلية كيلي (Kelly Mechanism).

هذه الورقة البحثية هي قصة عن كيفية تعلم هؤلاء الأصداء لعب هذه اللعبة مراراً وتكراراً، وكيف يكتشفون في النهاية التوازن المثالي.

طاقم الشخصيات (الخوارزميات)

اختبر الباحثون أربع "شخصيات" أو استراتيجيات مختلفة يمكن للأصدقاء استخدامها لتحديد الرقم الذي سيصرخون به في المرة القاد die:

لاعب "الاستجابة المثلى" (Best Response - BR):
- الاستعارة: هذا هو لاعب الشطرنج المحترف. بعد كل جولة، ينظر إلى ما صرخ به الجميع، ويقوم بعملية حسابية ذهنية سريعة، ثم يصرخ فوراً بالرد المثالي لمضاعفة حصته من البيتزا. هو لا يرتكب أخطاء؛ بل يستجيب فوراً للوضع الحالي.
- النتيجة: هم الأسرع في إيجاد التوازن المثالي ويحققون أفضل النتائج.
لاعب "النزول المتدرج" (Gradient Descent - OGD):
- الاستعارة: هذا هو المتنزه الذي يحمل بوصلة. هو لا يعرف الخريطة بأكملها، لكنه يستطيع الشعور بما إذا كانت الأرض منحدرة للأعلى أو للأسفل. إذا كان الصراخ بصوت أعلى قليلاً سيمنحه المزيد من البيتزا، فإنه يخطو خطوة صغيرة للأعلى. وإذا كان الصراخ بصوت أعلى سيضره، فإنه يتراجع للخلف. إنه يتحرك ببطء وثبات، مستشعراً طريقه نحو قمة التل.
- النتيجة: سيصلون في النهاية، لكن الأمر يستغرق منهم خطوات أكثر من لاعب الشطرنج المحترف.
لاعب "المتوسط المزدوج" (Dual Averaging - DAQ):
- الاستعارة: هذا هو المؤرخ. بدلاً من النظر فقط إلى الجولة الأخيرة، يحتفظ بسجل لكل صرخة أطلقها وكل نتيجة شهدها. إنه يأخذ متوسط تجاربه الماضية ليقرر ما سيفعله تالياً. إنه حذر جداً ولا يبالغ في رد الفعل تجاه جولة واحدة سيئة.
- النتيجة: هم موثوقون، لكنهم أبطأ وأكثر حذراً من الآخرين.
لاعب "روبنز-مون المنظم" (Regularized Robbins-Monro - RRM):
- الاستعارة: هذا هو الطالب الذي يحمل حقيبة ظهر ثقيلة. هو مشابه للمؤرخ، لكنه يحمل "وزناً" إضافياً (تنظيم رياضي) يبطئه لمنعه من القيام بتقلبات عشوائية.
- النتيجة: هم الأبطأ في التعلم، وغالباً ما ينتهي بهم الأمر بحصولهم على بيتزا أقل من الآخرين.

الاكتشاف الكبير: "النقطة المثالية"

أراد الباحثون معرفة: هل سيتفق هؤلاء اللاعبون في النهاية على طريقة عادلة ومستقرة لتقاسم البيتزا؟

في نظرية الألعاب، تسمى هذه النقطة المستقرة توازن ناش (Nash Equilibrium). وهي حالة لا يرغب فيها أحد في تغيير صرخته لأنهم، بالنظر إلى ما يصرخ به الآخرون، يحصلون بالفعل على أفضل صفقة ممكنة.

تثبت الورقة البحثية أن:

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

المفاجأة: خلط اللاعبين

ماذا يحدث إذا تم خلط اللاعبين؟ ماذا لو كان بعضهم لاعبين محترفين في الشطرنج والبعض الآخر متنزّهين؟

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

لماذا يهم هذا في العالم الحقيقي؟

الأمر لا يتعلق بالبيتزا فقط. بل يتعلق بـ عرض نطاق الإنترنت (Internet Bandwidth).

تخيل أن الشبكة اللاسلكية (مثل 5G) هي طريق سريع. "مالك المورد" هو مزود الشبكة. و"الأصدقاء" هم شركات مختلفة (مثل Netflix أو Zoom أو خادم ألعاب) تحاول إرسال البيانات.

هم يزايدون على مساحة الطريق.
تقسم الشبكة عرض النطاق الترددي بناءً على من يزايد أكثر.
"المنفعة اللوغاريتمية" تمثل الرغبة في العدالة. الشركات لا تريد فقط سرعة أكبر؛ بل تريد سرعة تشعر بأنها عادلة مقارداً بالآخرين.

تخبرنا الورقة أنه إذا استخدمت هذه الشركات خوارزميات تعلم ذكية (مثل تلك التي تم اختبارها)، فسيتمكنون بشكل طبيعي من إيجاد طريقة عادلة لمشاركة الإنترنت دون الحاجة إلى تدخل مزود الشبكة لإدارتهم. إنه نظام ذاتي التصحيح حيث يؤدي السلوك الأناني في الواقع إلى نتيجة عادلة.

الخلاصة

إذا لعب الجميع نفس اللعبة الذكية: فسيجدون بسرعة توازناً مثالياً وعادلاً.
استراتيجية "الاستجابة المثلى" (التفاعل الفوري): هي الأسرع والأكثر كفاءة.
حتى لو لعبوا بطرق مختلفة: قد لا يصلون إلى التوازن المثالي، لكنهم سيظلون في وضع جيد جداً.
الرياضيات: أثبت الباحثون ذلك باستخدام رياضيات معقدة، لكن النتيجة بسيطة: الوكلاء الأنانيون، الذين يتعلمون من أخطائهم، يمكنهم إنشاء نظام عادل وفعال دون وجود "رئيس" يملي عليهم ما يفعلونه.

إليك ملخص تقني مفصل لورقة البحث بعنوان "التعلم في ألعاب تخصيص الموارد التناسبية" (Learning in Proportional Allocation Auctions Games) للباحثين يونس بن مزيان وآخرون.

1. بيان المشكلة

تتقصى الورقة البحثية آلية كيلي المتكررة (المعروفة أيضاً بآلية التخصيص التناسبي)، وهي نظام مزاد لا مركزي يتم فيه تخصيص مورد قابل للتجزئة للوكلاء بشكل يتناسب مع عطاءاتهم.

السياق: في الإعدادات القياسية، يُفترض أن الوكلاء يعرفون قاعدة التخصيص ومنفعة الآخرين، مما يشكل لعبة ثابتة ذات توازن ناش (Nash Equilibrium) معروف. ومع ذلك، في السيناريوهات الواقعية (مثل تقسيم الشبكات اللاسلكية أو الحوسبة السحابية)، غالباً ما يفتقر الوكلاء إلى المعرفة بمنفعة الآخرين وميزانياتهم.
التحدي: يجب على الوكلاء تكييف استراتيجيات العطاء الخاصة بهم عبر جولات متكررة بناءً على التغذية الراجعة فقط (مثل إجمالي العطاءات) لتعظيم متوسط منفعتهم عبر الزمن.
التركيز المحدد: تركز الورقة على الوكلاء الذين يمتلكون دوال منفعة لوغاريتمية ( $V_i(x) = a_i \ln(x) + d_i$ )، والتي تنشأ طبيعياً من مشكلات تخصيص النطاق الترددي التي تهدف إلى موازنة الإنتاجية والعدالة (العدالة التناسبية). تحلل الورقة ما إذا كان اللعب المتكرر تحت ديناميكيات تعلم مختلفة يؤدي إلى التقارب نحو توازن ناش الفريد للعبة المرحلة.

2. المنهجية

استخدم المؤلفون مزيجاً من نظرية الألعاب، التحسين الكوني عبر الإنترنت (OCO)، وتحليل النقطة الثابتة.

أ. صياغة المشكلة

الآلية: يقدم الوكلاء عطاءات $b_{i,t}$ . يقوم مالك المورد بتخصيص حصة $x_{i,t} = \frac{w_i(b_{i,t})}{\sum w_j(b_{j,t}) + \delta}$ . بالنسبة لآلية كيلي الكلاسيكية، تكون $w_i$ هي دالة الهوية.
المنفعة: منفعة الوكيل $i$ هي $\phi_i = V_i(x_{i,t}) - b_{i,t}$ .
التحويل: تمت إعادة صياغة المشكلة باستخدام تغيير للمتغير $z_{i,t} = w_i(b_{i,t})$ لتبسيط قاعدة التخصيص ودالة المنفعة، ومعاملة $z$ كعطاء فعال.
الافتراضات: دوال التقييم $V_i$ متزايدة تماماً، ومقعرة، وقابلة للاشتقاق مرتين. دوال الدفع محدبة ومتزايدة.

ب. الإطار النظري

وحدانية توازن ناش (NE): أثبت المؤلفون شروط وجود توازن ناش فريد. استخدموا خاصية التحدب الصارم القطري لروزين (DSC) (وتحديداً $r$ -DSC). وقد اشتقوا شرطاً كافياً قابلاً للتطبيق (النظرية 2) يقلل من عملية التحقق من DSC من فحص مصفوفة بتعقيد $O(n^3)$ إلى فحص دالة قياسية بتعقيد $O(n)$ .
خوارزميات التعلم: تم تحليل أربع استراتيجيات للعطاء:
- الانحدار الكوني عبر الإنترنت (OGD): خوارزمية قياسية لتقليل الندم تستخدم تحديثات التدرج.
- المتوسط المزدوج مع المنظم التربيعي (DAQ): نسخة من خوارزمية "اتبع القائد المنظم" (FTRL).
- روبينز-مونرو المنظم (RRM): إجراء موزع لحساب توازن ناش.
- أفضل استجابة عيانياً (Myopic Best Response - BR): يلعب الوكلاء أفضل استجابة لإجمالي العطاء في الجولة السابقة.
تحليل التقارب:
- بالنسبة لـ OGD و DAQ، تم إثبات التقارب باستخدام خاصية $r$ -monotonicity المستمدة من شرط DSC. وسّع المؤلفون هذه النتائج للسماح بـ معدلات تعلم شخصية (غير متجانسة).
- بالنسبة لـ BR، تم نمذجة النظام كعملية تكرار نقطة ثابتة. أثبت المؤلفون أن مؤثر الاستجابة المثلى هو تطبيق تقليص (Contraction Mapping) تحت شروط محددة على الحد الأدنى للعطاء، مما يضمن التقارب الخطي.

ج. المحاكاة العددية

أُجريت محاكاة واسعة النطاق للتحقق من النتائج النظرية واستكشاف الديناميكيات غير المتجانسة (حيث يستخدم وكلاء مختلفون خوارزميات تعلم مختلفة في آن واحد). شملت المقاييس سرعة التقارب (بقايا النقطة الثابتة) ومتوسط المنفعة عبر الزمن.

3. المساهمات الرئيسية

اشتقاق المنفعة اللوغاريتمية: اشتققت الورقة رسمياً شكل المنفعة اللوغاريتمية من سيناريو عملي لـ تقسيم الشبكات اللاسلكية، مما يربط آلية كيلي بتحسين العدالة التناسبية.
شرط الوحدانية القابل للتطبيق: قدم المؤلفون شرطاً جديداً وفعالاً حاسوبياً (النظرية 2) للتحقق من وحدانية توازن ناش لألعاب كيلي ذات المنفعة اللوغاريتمية والقيود على الميزانية. هذا الشرط يسري على مجموعات إجراءات محدبة تعسفية.
التقارب مع المعدلات الشخصية: على عكس الأعمال السابقة التي تتطلب معدلات تعلم مشتركة، أثبت المؤلفون أن OGD و DAQ يتقاربان نحو توازن ناش الفريد حتى عندما يستخدم الوكلاء معدلات تعلم شخصية (تعتمد على الندم الأمثل)، بشرما كانت المنافع تختلف فقط بعوامل ضربية (تغاير أفيني).
تقارب أفضل استجابة: أثبتوا أن ديناميكيات أفضل استجابة عيانياً تتقارب خطياً نحو توازن ناش، بشرط أن يكون الحد الأدنى للعطاء كبيراً بما يكفي بالنسبة لعدد الوكلاء ومعلمات المنفعة.
تحليل الديناميكيات غير المتجانسة: من خلال المحاكاة، أظهروا أنه بينما تؤدي الديناميكيات المتجانسة إلى التقارب نحو توازن ناش، فإن الديناميكيات غير المتجانسة (خلط BR، OGD، و DAQ) قد تفشل في التقارب نحو نقطة توازن ناش، رغم أنها غالباً ما تستقر في نظام مستقر بمنفعة قريبة من توازن ناش.

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

الوحدانية: تسمح لعبة المرحلة ذات المنافع اللوغاريتمية بوجود توازن ناش فريد.
سرعة التقارب (المتجانسة):
- أفضل استجابة (BR): تحقق أسرع تقارب وأعلى منفعة متوسطة عبر الزمن.
- OGD: تتقارب بشكل أبطأ من BR ولكن أسرع من DAQ.
- DAQ/RRM: تتقارب ببطء ملحوظ.
- ملاحظة: سرعة تقارب BR تزداد مع زيادة عدد الوكلاء ( $n$ )، بينما تقل سرعة OGD/DAQ.
التقارب مع المعدلات غير المتجانسة: تؤكد البراهين النظرية أن OGD و DAQ يتقاربان نحو توازن ناش حتى مع اختلاف معدلات التعلم لكل وكيل.
الخوارزميات غير المتجانسة: عندما يخلط الوكلاء الاستراتيجيات (مثلاً، بعضهم يستخدم BR والبعض الآخر DAQ):
- غالباً ما يفشل النظام في التقارب إلى نقطة توازن ناش الدقيقة (تحدث تذبذبات).
- ومع ذلك، تظل المنافع المتوسطة عبر الزمن قريبة من منفعة توازن ناش.
- يحقق وكلاء BR باستمرار عوائد أعلى قليلاً من مستوى توازن ناش، بينما قد يحصل وكلاء OGD/DAQ على عوائد أقل قليلاً، خاصة عندما يكونون هم الأقلية.
الندم: بينما تفتقر BR إلى ضمانات رسمية لـ "عدم الندم"، إلا أنها تتفوق تجريبياً على خوارزميات عدم الندم (OGD/DAQ) من حيث سرعة التقارب ومتوسط العائد في هذا النوع المحدد من الألعاب.

5. الأهمية

الأهمية العملية: يربط هذا العمل بين نظرية الألعاب النظرية وتخصيص الموارد العملي في شبكات 5G/6G (تقسيم الشبكات)، حيث يتعين على الوكلاء (المستأجرين) تعلم كيفية تقديم العطاءات دون معلومات كاملة.
الرؤية الخوارزمية: تتحدى الورقة الافتراض القائل بأن خوارزميات "عدم الندم" هي دائماً الأفضل. في هذا النوع المحدد من الألعاب، تعتبر أفضل استجابة عيانياً أبسط حاسوبياً ومتفوقة تجريبياً من حيث سرعة التقارب والمنفعة.
المتانة: تظهر النتائج أن النظام متين تجاه التغاير؛ فحتى لو استخدم الوكلاء قواعد تعلم مختلفة، فإن النتيجة الجماعية تظل فعالة (قريبة من توازن ناش)، مما يمنع الفشل الكارثي في الأنظمة اللامركزية.
التقدم النظري: يوفر اشتقاق شرط قياسي لـ DSC في ألعاب كيلي تبسيطاً لتحليل الوحدانية والتقارب لمجموعة واسعة من آليات التخصيص، مما يوسع النتائج السابقة التي كانت تقتصر على المنافع الخطية أو قيود محددة.

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