نظرية الألعاب التعاونية

في نظرية الألعاب ، تُعرَّف اللعبة التعاونية أو التحالفية بأنها لعبة تضم مجموعات من اللاعبين يشكلون "تحالفات" ملزمة، مع وجود آليات خارجية لفرض السلوك التعاوني (مثل قانون العقود ). ويختلف هذا عن الألعاب غير التعاونية التي إما لا توجد فيها إمكانية لعقد تحالفات، أو تتطلب فيها جميع الاتفاقيات أن تكون ذاتية التنفيذ (مثل التهديدات الموثوقة ). [ 1 ]

يتم تحليل الألعاب التعاونية بالتركيز على التحالفات التي يمكن تشكيلها، والإجراءات المشتركة التي يمكن للمجموعات اتخاذها، والعوائد الجماعية الناتجة عنها. [ 2 ] [ 3 ]

التعريف الرياضي

تُعرَّف اللعبة التعاونية بتحديد قيمة لكل تحالف. وبشكل رسمي، تتكون اللعبة التحالفية من مجموعة محدودة من اللاعبين.شمال{\displaystyle N}، والتي تُسمى التحالف الكبير ، ووظيفة مميزةv:2شمالR{\displaystyle v:2^{N}\to \mathbb {R} }[ 4 ] من مجموعة جميع التحالفات الممكنة للاعبين إلى مجموعة من المدفوعات التي تحققv()=0{\displaystyle v(\emptyset )=0}تصف هذه الدالة مقدار العائد الجماعي الذي يمكن أن تحققه مجموعة من اللاعبين من خلال تشكيل تحالف.

السمات الرئيسية

نظرية الألعاب التعاونية هي فرع من نظرية الألعاب يُعنى بدراسة الألعاب التي يُمكن للاعبين فيها تشكيل تحالفات، والتعاون فيما بينهم، وإبرام اتفاقيات مُلزمة. تُقدّم هذه النظرية أساليب رياضية لتحليل السيناريوهات التي يُطلب فيها من لاعبين أو أكثر اتخاذ خيارات تُؤثر على رفاهية اللاعبين الآخرين. [ 5 ]

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

الألعاب الفرعية

يتركSشمال{\displaystyle S\subsetneq N}أن يكون تحالفًا غير فارغ من اللاعبين. اللعبة الفرعيةvS:2SR{\displaystyle v_{S}:2^{S}\to \mathbb {R} }علىS{\displaystyle S}يُعرَّف بشكل طبيعي على أنه

vS(تي)=v(تي)، تيS.{\displaystyle v_{S}(T)=v(T),\forall ~T\subseteq S.}

بمعنى آخر، نحن ببساطة نقتصر اهتمامنا على التحالفات الموجودة فيS{\displaystyle S}. الألعاب الفرعية مفيدة لأنها تسمح لنا بتطبيق مفاهيم الحلول المحددة للتحالف الكبير على التحالفات الأصغر.

الخصائص الرياضية

خاصية الجمع الفائق

غالباً ما يُفترض أن الدوال المميزة فائقة الجمع ( أوين 1995 ، ص 213) . وهذا يعني أن قيمة اتحاد التحالفات المنفصلة لا تقل عن مجموع قيم التحالفات المنفصلة. 

v(Sتي)v(S)+v(تي){\displaystyle v(S\cup T)\geq v(S)+v(T)}حينماS،تيشمال{\displaystyle S,T\subseteq N}مُرضٍSتي={\displaystyle S\cap T=\emptyset }.

الرتابة

كلما زاد حجم التحالفات، زادت المكاسب:

Sتيv(S)v(تي){\displaystyle S\subseteq T\Rightarrow v(S)\leq v(T)}.

هذا يتبع من خاصية الجمع الفائق . أي إذا تم تطبيع العوائد بحيث يكون للتحالفات الفردية قيمة صفرية.

خصائص للألعاب البسيطة

تُعتبر لعبة التحالفات بسيطة إذا كانت العوائد إما 1 أو 0 ، أي أن التحالفات إما "رابحة" أو "خاسرة". [ 7 ]

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

  • تكون اللعبة البسيطة W رتيبة إذا كان أي تحالف يحتوي على تحالف فائز فائزًا أيضًا، أي إذاSدبليو{\displaystyle S\in W}وSتي{\displaystyle S\subseteq T}يعنيتيدبليو{\displaystyle T\in W}.
  • تكون اللعبة البسيطة W مناسبة إذا كان مكمل (معارض) أي ائتلاف فائز خاسراً، أي إذاSدبليو{\displaystyle S\in W}يشير إلىشمالSدبليو{\displaystyle N\setminus S\notin W}.
  • تكون لعبة W البسيطة قوية إذا كان مكمل أي تحالف خاسر هو التحالف الفائز، أي إذاSدبليو{\displaystyle S\notin W}يشير إلىشمالSدبليو{\displaystyle N\setminus S\in W}.
    • إذا كانت اللعبة البسيطة W لعبة مناسبة وقوية، فإن التحالف يفوز إذا وفقط إذا كان مكمله خاسراً، أيSدبليو{\displaystyle S\in W}إذا شمالSدبليو{\displaystyle N\setminus S\notin W}(إذا كانت v لعبة ائتلافية بسيطة مناسبة وقوية،v(S)=1-v(شمالS){\displaystyle v(S)=1-v(N\setminus S)}لأي S. )
  • في لعبة بسيطة، يُعتبر اللاعب الذي يملك حق النقض (لاعب الفيتو) لاعبًا ينتمي إلى جميع التحالفات الفائزة. بافتراض وجود لاعب فيتو، فإن أي تحالف لا يحتوي على لاعب فيتو يكون خاسرًا. تُسمى اللعبة البسيطة W ضعيفة ( جماعية ) إذا كان لديها لاعب فيتو، أي إذا كان التقاطعدبليو:=SدبليوS{\displaystyle \bigcap W:=\bigcap _{S\in W}S}جميع التحالفات الفائزة غير فارغة.
    • في لعبة بسيطة ، يُعتبر الديكتاتور لاعبًا ذا حق نقض، بحيث يكون أي تحالف يضم هذا اللاعب فائزًا. ولا ينتمي الديكتاتور إلى أي تحالف خاسر. ( لا علاقة لألعاب الديكتاتورية في الاقتصاد التجريبي بهذا الأمر).
  • حامل لعبة بسيطة W هو مجموعةتيشمال{\displaystyle T\subseteq N}بحيث يكون لدينا لأي تحالف SSدبليو{\displaystyle S\in W}إذاSتيدبليو{\displaystyle S\cap T\in W}عندما تحتوي لعبة بسيطة على حامل، يتم تجاهل أي لاعب لا ينتمي إليه. تُسمى اللعبة البسيطة أحيانًا لعبة منتهية إذا كان لها حامل منتهٍ (حتى لو كان N عددًا لانهائيًا).
  • عدد ناكامورا في لعبة بسيطة هو أقل عدد من التحالفات الرابحة ذات التقاطع الفارغ. ووفقًا لنظرية ناكامورا، يقيس هذا العدد درجة العقلانية؛ فهو مؤشر على مدى قدرة قاعدة التجميع على إنتاج خيارات محددة جيدًا.

تم الاعتراف على نطاق واسع ببعض العلاقات بين البديهيات المذكورة أعلاه، مثل ما يلي (على سبيل المثال، Peleg، 2002، القسم 2.1 [ 8 ] ):

  • إذا كانت اللعبة البسيطة ضعيفة، فهذا أمر طبيعي.
  • لعبة بسيطة تكون استبدادية إذا وفقط إذا كانت قوية وضعيفة.

وبشكل أكثر عمومية، تم إجراء تحقيق كامل في العلاقة بين البديهيات التقليدية الأربعة (الرتابة، والملاءمة، والقوة، وعدم الضعف)، والنهائية، وقابلية الحساب الخوارزمي [ 9 ] (كومابي وميهارا، 2011 [ 10 ] )، والتي تم تلخيص نتائجها في الجدول "وجود الألعاب البسيطة" أدناه.

وجود الألعاب البسيطة [ 11 ]
يكتبغير مكتمل محدودقابل للحساب المحدوداللانهائي غير المتكاملقابل للحساب اللانهائي
1111لانعمنعمنعم
1110لانعملالا
1101لانعمنعمنعم
1100لانعمنعمنعم
1011لانعمنعمنعم
1010لالالالا
1001لانعمنعمنعم
1000لالالالا
0111لانعمنعمنعم
0110لالالالا
0101لانعمنعمنعم
0100لانعمنعمنعم
0011لانعمنعمنعم
٠٠١٠لالالالا
٠٠٠١لانعمنعمنعم
0000لالالالا

كما دُرست القيود التي تفرضها مختلف البديهيات الخاصة بالألعاب البسيطة على عدد ناكامورا الخاص بها بشكلٍ مُستفيض. [ 12 ] وعلى وجه الخصوص، فإن اللعبة البسيطة القابلة للحساب والتي لا تحتوي على لاعب حق النقض يكون لها عدد ناكامورا أكبر من 3 فقط إذا كانت لعبة صحيحة وغير قوية .

العلاقة بنظرية عدم التعاون

لنفترض أن G لعبة استراتيجية (غير تعاونية). بافتراض أن التحالفات لديها القدرة على فرض سلوك منسق، توجد عدة ألعاب تعاونية مرتبطة بـ G. غالبًا ما يُشار إلى هذه الألعاب باسم تمثيلات G. التمثيلان القياسيان هما: [ 13 ]

  • تربط لعبة ألفا الفعالة كل تحالف بمجموع المكاسب التي يمكن لأعضائه "ضمانها" من خلال توحيد جهودهم. ويُقصد بـ"الضمان" أن القيمة هي الحد الأقصى الأدنى، أي القيمة القصوى للحد الأدنى الذي تم تحقيقه من خلال استراتيجيات الخصم.
  • تربط لعبة بيتا الفعالة كل تحالف بمجموع المكاسب التي يمكن لأعضائه "ضمانها استراتيجياً" من خلال توحيد جهودهم. ويُقصد بـ"الضمان الاستراتيجي" أن القيمة هي الحد الأدنى والحد الأقصى، أي القيمة الدنيا للحد الأقصى المتحقق من استراتيجيات الخصم.

مفاهيم الحلول

الافتراض الرئيسي في نظرية الألعاب التعاونية هو أن التحالف الكبيرشمال{\displaystyle N}سيتشكل. [ 14 ] يكمن التحدي بعد ذلك في توزيع العائدv(شمال){\displaystyle v(N)}بين اللاعبين بطريقة ما. (هذا الافتراض ليس تقييديًا، لأنه حتى لو انقسم اللاعبون وشكلوا تحالفات أصغر، يمكننا تطبيق مفاهيم الحل على الألعاب الفرعية المحددة بأي تحالفات تتشكل فعليًا). مفهوم الحل هو متجه.xRشمال{\displaystyle x\in \mathbb {R} ^{N}}(أو مجموعة من المتجهات) التي تمثل التوزيع على كل لاعب. وقد اقترح الباحثون مفاهيم حلول مختلفة بناءً على مفاهيم مختلفة للعدالة. ومن بين الخصائص التي يجب البحث عنها في مفهوم الحل ما يلي:

  • الكفاءة: يقسم متجه العائد القيمة الإجمالية بدقة:أناشمالxأنا=v(شمال){\displaystyle \sum _{i\in N}x_{i}=v(N)}.
  • العقلانية الفردية: لا يحصل أي لاعب على أقل مما يمكنه الحصول عليه بمفرده:xأناv({أنا})، أناشمال{\displaystyle x_{i}\geq v(\{i\}),\forall ~i\in N}.
  • الوجود: مفهوم الحل موجود في أي لعبةv{\displaystyle v}.
  • التفرد: مفهوم الحل فريد من نوعه بالنسبة لأي لعبةv{\displaystyle v}.
  • الهامشية: يعتمد عائد اللاعب فقط على المساهمة الهامشية لهذا اللاعب، أي إذا كانت هذه المساهمات الهامشية متساوية في لعبتين مختلفتين، فإن العائد يكون متساوياً:v(S{أنا})=w(S{أنا})، Sشمال{أنا}{\displaystyle v(S\cup \{ i\})=w(S\cup \{ i\}),\forall ~S\subseteq N\setminus \{ i\}}يشير ذلك إلى أنxأنا{\displaystyle x_{i}}هو نفسه فيv{\displaystyle v}وفيw{\displaystyle w}.
  • الرتابة: يزداد عائد اللاعب إذا زادت مساهمته الحدية:v(S{أنا})w(S{أنا})، Sشمال{أنا}{\displaystyle v(S\cup \{ i\})\leq w(S\cup \{ i\}),\forall ~S\subseteq N\setminus \{ i\}}يشير ذلك إلى أنxأنا{\displaystyle x_{i}}أكبر بشكل طفيف فيw{\displaystyle w}أكثر من فيv{\displaystyle v}.
  • سهولة الحساب: يمكن حساب مفهوم الحل بكفاءة (أي في وقت متعدد الحدود بالنسبة لعدد اللاعبين).|شمال|{\displaystyle |N|}.)
  • التناظر: مفهوم الحلx{\displaystyle x}تخصيص مدفوعات متساويةxأنا=xج{\displaystyle x_{i}=x_{j}}للاعبين المتناظرينأنا{\displaystyle i}،ج{\displaystyle j}لاعبانأنا{\displaystyle i}،ج{\displaystyle j}تكون متناظرة إذاv(S{أنا})=v(S{ج})، Sشمال{أنا،ج}{\displaystyle v(S\cup \{i\})=v(S\cup \{j\}),\forall ~S\subseteq N\setminus \{i,j\}}أي أنه يمكننا استبدال لاعب بآخر في أي تحالف يحتوي على لاعب واحد فقط دون تغيير العائد.
  • خاصية الجمع: إن المبلغ المخصص للاعب في مجموع لعبتين يساوي مجموع المبالغ المخصصة له في كل لعبة على حدة. رياضياً، إذاv{\displaystyle v}وω{\displaystyle \omega }هي ألعاب، اللعبة(v+ω){\displaystyle (v+\omega )}ببساطة، يُخصص لكل تحالف مجموع العوائد التي سيحصل عليها في اللعبتين الفرديتين. أما مفهوم الحل الجمعي، فيُخصص لكل لاعب في(v+ω){\displaystyle (v+\omega )}مجموع ما سيحصل عليه فيv{\displaystyle v}وω{\displaystyle \omega }.
  • تخصيص صفر للاعبين غير النشطين: التخصيص المخصص للاعب غير النشط هو صفر. لاعب غير نشطأنا{\displaystyle i}يرضيv(S{أنا})=v(S)، Sشمال{أنا}{\displaystyle v(S\cup \{i\})=v(S),\forall ~S\subseteq N\setminus \{i\}}من الناحية الاقتصادية، فإن القيمة الحدية للاعب المحايد بالنسبة لأي تحالف لا يضمه هي صفر.

يُطلق على متجه العائد الفعال اسم الإسناد المسبق ، ويُطلق على الإسناد المسبق العقلاني الفردي اسم الإسناد . معظم مفاهيم الحلول هي إسناد.

المجموعة المستقرة

كانت المجموعة المستقرة للعبة (المعروفة أيضًا باسم حل فون نيومان-مورجنسترن ( فون نيومان ومورجنسترن 1944 ) ) أول حل مقترح للألعاب التي تضم أكثر من لاعبين.v{\displaystyle v}دعها تكون لعبة ودعهاx{\displaystyle x}،y{\displaystyle y}لنفترض وجود إسنادين لـv{\displaystyle v}. ثمx{\displaystyle x}يهيمنy{\displaystyle y}إذا كان هناك تحالف ماS{\displaystyle S\neq \emptyset }يرضيxأنا>yأنا، أناS{\displaystyle x_{i}>y_{i},\forall ~i\in S}وأناSxأناv(S){\displaystyle \sum _{i\in S}x_{i}\leq v(S)}بمعنى آخر، اللاعبون فيS{\displaystyle S}أفضل العوائد منx{\displaystyle x}إلى أولئك منy{\displaystyle y}ويمكنهم التهديد بالانسحاب من الائتلاف الكبير إذاy{\displaystyle y}يُستخدم هذا الأسلوب لأن العائد الذي يحصلون عليه بمفردهم لا يقل عن حجم المخصصات التي يتلقونها بموجبx{\displaystyle x}.

المجموعة المستقرة هي مجموعة من عمليات الإسناد التي تحقق خاصيتين:

  • الاستقرار الداخلي: لا يوجد متجه عائد في المجموعة المستقرة يهيمن عليه متجه آخر في المجموعة.
  • الاستقرار الخارجي: جميع متجهات العوائد خارج المجموعة يهيمن عليها متجه واحد على الأقل في المجموعة.

رأى فون نيومان ومورغنسترن أن المجموعة المستقرة هي مجموعة السلوكيات المقبولة في المجتمع: لا يُفضّل أي سلوك على آخر بشكل واضح، ولكن لكل سلوك غير مقبول بديل مفضل. هذا التعريف عام جدًا، مما يسمح باستخدام المفهوم في مجموعة واسعة من أشكال الألعاب.

ملكيات

  • قد توجد مجموعة مستقرة أو لا توجد ( لوكاس، 1969 ) ، وإذا وُجدت، فعادةً ما تكون غير فريدة ( لوكاس، 1992 ) . عادةً ما يصعب إيجاد المجموعات المستقرة. وقد أدت هذه الصعوبة، إلى جانب صعوبات أخرى، إلى تطوير العديد من مفاهيم الحلول الأخرى.
  • نسبة إيجابية من الألعاب التعاونية لها مجموعات مستقرة فريدة تتكون من النواة ( أوين 1995 ، ص 240) . 
  • نسبة إيجابية من الألعاب التعاونية تمتلك مجموعات مستقرة تميز بين المجموعات.ن-2{\displaystyle n-2}اللاعبون. في مثل هذه المجموعات على الأقلن-3{\displaystyle n-3}يتم استبعاد اللاعبين الذين تعرضوا للتمييز ( أوين 1995 ، ص 240) . 

الجوهر

يتركv{\displaystyle v}أن تكون لعبة. جوهرv{\displaystyle v}هي مجموعة متجهات العوائد

ج(v)={xRشمال:أناشمالxأنا=v(شمال)؛أناSxأناv(S)، Sشمال}.{\displaystyle C(v)=\left\{x\in \mathbb {R} ^{N}:\sum _{i\in N}x_{i}=v(N);\quad \sum _{i\in S}x_{i}\geq v(S),\forall ~S\subseteq N\right\}.}

بعبارة أخرى، يُمثل جوهر الأمر مجموعة التقديرات التي لا تتجاوز قيمة أي ائتلاف بموجبها مجموع عوائد أعضائه. وبالتالي، لا يوجد لدى أي ائتلاف حافز لمغادرة الائتلاف الأكبر والحصول على عائد أكبر.

ملكيات

  • قد يكون لب اللعبة فارغًا (انظر نظرية بونداريفا-شابلي ) . وتسمى الألعاب ذات اللب غير الفارغ بالألعاب المتوازنة .
  • إذا لم يكن فارغًا، فإن النواة لا تحتوي بالضرورة على متجه فريد.
  • يتم احتواء النواة في أي مجموعة مستقرة، وإذا كانت النواة مستقرة فهي المجموعة المستقرة الوحيدة؛ انظر ( دريسن 1988 ) للحصول على برهان.

جوهر لعبة بسيطة فيما يتعلق بالتفضيلات

بالنسبة للألعاب البسيطة، هناك مفهوم آخر للجوهر، حيث يُفترض أن لكل لاعب تفضيلات على مجموعةX{\displaystyle X}من البدائل. الملف التعريفي عبارة عن قائمةص=(أناص)أناشمال{\displaystyle p=(\succ _{i}^{p})_{i\in N}}تفضيلات الأفرادأناص{\displaystyle \succ _{i}^{p}}علىX{\displaystyle X}. هناxأناصy{\displaystyle x\succ _{i}^{p}y}يعني ذلك الفردأنا{\displaystyle i}يفضل البديلx{\displaystyle x} لy{\displaystyle y}في الملف الشخصيص{\displaystyle p}. بالنظر إلى لعبة بسيطةv{\displaystyle v}وملف تعريفيص{\displaystyle p}علاقة هيمنةvص{\displaystyle \succ _{v}^{p}}يتم تعريفها علىX{\displaystyle X}بواسطةxvصy{\displaystyle x\succ _{v}^{p}y}إذا وفقط إذا كان هناك ائتلاف فائزS{\displaystyle S} (أي،v(S)=1{\displaystyle v(S)=1}مُرضٍxأناصy{\displaystyle x\succ _{i}^{p}y}للجميعأناS{\displaystyle i\in S}الجوهرج(v،ص){\displaystyle C(v,p)}لعبة بسيطةv{\displaystyle v}فيما يتعلق بالملف الشخصيص{\displaystyle p}مجموعة التفضيلات هي مجموعة البدائل التي لا يهيمن عليهاvص{\displaystyle \succ _{v}^{p}} (مجموعة العناصر القصوى لـX{\displaystyle X}بالنسبة إلىvص{\displaystyle \succ _{v}^{p}}):

xج(v،ص){\displaystyle x\in C(v,p)}إذا وفقط إذا لم يكن هناكyX{\displaystyle y\in X}بحيثyvصx{\displaystyle y\succ _{v}^{p}x}.

عدد ناكامورا للعبة بسيطة هو أقل عدد من التحالفات الفائزة ذات التقاطع الفارغ. تنص نظرية ناكامورا على أن النواةج(v،ص){\displaystyle C(v,p)}لا يكون فارغًا لجميع الملفات الشخصيةص{\displaystyle p}من التفضيلات غير الدورية (أو المتعدية ) إذا وفقط إذاX{\displaystyle X}هي مجموعة محدودة والعدد الأصلي (عدد العناصر) لـX{\displaystyle X}وهو أقل من رقم ناكامورا لـv{\displaystyle v}. تنص إحدى الصيغ المعدلة التي وضعها كومابي وميهارا على أن الجوهرج(v،ص){\displaystyle C(v,p)}لا يكون فارغًا لجميع الملفات الشخصيةص{\displaystyle p}من التفضيلات التي لها عنصر أقصى إذا وفقط إذا كان العدد الأصلي لـX{\displaystyle X}وهو أقل من رقم ناكامورا لـv{\displaystyle v}(انظر رقم ناكامورا لمزيد من التفاصيل.)

النواة إبسيلون القوية

نظرًا لأن النواة قد تكون فارغة، فقد تم تقديم تعميم في ( شابلي وشوبيك 1966 ) . القويε{\displaystyle \varepsilon }-core لرقم ماεR{\displaystyle \varepsilon \in \mathbb {R} }هي مجموعة متجهات العوائد

جε(v)={xRشمال:أناشمالxأنا=v(شمال)؛أناSxأناv(S)-ε، Sشمال}.{\displaystyle C_{\varepsilon }(v)=\left\{x\in \mathbb {R} ^{N}:\sum _{i\in N}x_{i}=v(N);\quad \sum _{i\in S}x_{i}\geq v(S)-\varepsilon ,\forall ~S\subseteq N\right\}.}

من الناحية الاقتصادية، القويε{\displaystyle \varepsilon }-core هي مجموعة الإسنادات المسبقة التي لا يمكن لأي ائتلاف أن يحسن عائده فيها بالانسحاب من الائتلاف الكبير، إذا كان عليه دفع غرامة قدرهاε{\displaystyle \varepsilon }للمغادرة.ε{\displaystyle \varepsilon }قد يكون الأمر سلبياً، وفي هذه الحالة يمثل مكافأةً لمغادرة التحالف الكبير. من الواضح أنه بغض النظر عما إذا كان المركز خالياً أم لا، فإن الأقوياءε{\displaystyle \varepsilon }ستكون قيمة -core غير فارغة لقيمة كبيرة بما يكفي منε{\displaystyle \varepsilon }وتكون فارغة لقيمة صغيرة بما يكفي (ربما سالبة) منε{\displaystyle \varepsilon }وبناءً على هذا المنطق، فإن النواة الأصغر ، التي تم تقديمها في ( ماشلر، بيليج وشابلي 1979 ) ، هي تقاطع جميع المجموعات القوية غير الفارغةε{\displaystyle \varepsilon }-النوى. ويمكن اعتبارها أيضًا قويةε{\displaystyle \varepsilon }-core لأصغر قيمة لـε{\displaystyle \varepsilon }وهذا يجعل المجموعة غير فارغة ( بيلباو 2000 ) .

قيمة شابلي

قيمة شابلي هي متجه العوائد الوحيد الذي يتسم بالكفاءة والتناظر والرتابة. [ 15 ] وقد قدمها لويد شابلي ( شابلي، 1953 ) الذي أثبت أنها متجه العوائد الوحيد الذي يتسم بالكفاءة والتناظر والجمعية، ويُخصص عوائد صفرية للاعبين الوهميين. قيمة شابلي في لعبة فوق الجمعية تكون عقلانية فرديًا، ولكن هذا لا ينطبق على العموم. ( دريسن، 1988 )

النواة

يتركv:2شمالR{\displaystyle v:2^{N}\to \mathbb {R} }دعها تكون لعبة، ودعهاxRشمال{\displaystyle x\in \mathbb {R} ^{N}}ليكن متجه العائد الفعال. أقصى فائض للاعب i على اللاعب j بالنسبة إلى x هو

sأناجv(x)=الأعلى{v(S)-كSxك:Sشمال{ج}،أناS}،{\displaystyle s_{ij}^{v}(x)=\max \left\{v(S)-\sum _{k\in S}x_{k}:S\subseteq N\setminus \{j\},i\in S\right\},}

أقصى مبلغ يمكن أن يحصل عليه اللاعب i دون تعاون اللاعب j بالانسحاب من التحالف الكبير N في ظل متجه العوائد x ، بافتراض أن اللاعبين الآخرين في التحالف المنسحب من i راضون عن عوائدهم في ظل x . يُعدّ الفائض الأقصى طريقة لقياس قوة التفاوض لدى لاعب على آخر. نواةv{\displaystyle v}هي مجموعة الإسنادات x التي تحقق

  • (sأناجv(x)-sجأناv(x))×(xج-v(ج))0{\displaystyle (s_{ij}^{v}(x)-s_{ji}^{v}(x))\times (x_{j}-v(j))\leq 0}، و
  • (sجأناv(x)-sأناجv(x))×(xأنا-v(أنا))0{\displaystyle (s_{ji}^{v}(x)-s_{ij}^{v}(x))\times (x_{i}-v(i))\leq 0}

لكل زوج من اللاعبين i و j . وبشكل بديهي، يتمتع اللاعب i بقوة تفاوضية أكبر من اللاعب j فيما يتعلق بالتعويض x إذاsأناجv(x)>sجأناv(x){\displaystyle s_{ij}^{v}(x)>s_{ji}^{v}(x)}لكن اللاعب j محصن ضد تهديدات اللاعب i إذاxج=v(ج){\displaystyle x_{j}=v(j)}لأنه يستطيع الحصول على هذا العائد بنفسه. تحتوي النواة على جميع الاحتمالات التي لا يمتلك فيها أي لاعب هذه القدرة التفاوضية على لاعب آخر. وقد طُرح مفهوم الحل هذا لأول مرة في ( ديفيس وماشلر ، 1965 ) .

توزيعات أرباح هارساني

يُحدد مُعامل هارساني (نسبةً إلى جون هارساني ، الذي استخدمه لتعميم قيمة شابلي عام 1963 [ 16 ] ) الفائض الناتج عن تحالف لاعبين في لعبة تعاونية. ولتحديد هذا الفائض، تُصحح قيمة هذا التحالف بطرح الفائض الذي سبق أن حققته التحالفات الفرعية. ولهذا الغرض، يُحسب مُعامل هارساني.دv(S){\displaystyle d_{v}(S)}ائتلافS{\displaystyle S}داخل اللعبةv{\displaystyle v}يتم تحديدها بشكل متكرر بواسطة

دv({أنا})=v({أنا})دv({أنا،ج})=v({أنا،ج})-دv({أنا})-دv({ج})دv({أنا،ج،ك})=v({أنا،ج،ك})-دv({أنا،ج})-دv({أنا،ك})-دv({ج،ك})-دv({أنا})-دv({ج})-دv({ك})دv(S)=v(S)-تيSدv(تي){\displaystyle {\begin{aligned}d_{v}(\{i\})&=v(\{i\})\\d_{v}(\{i,j\})&=v(\{i,j\})-d_{v}(\{i\})-d_{v}(\{j\})\\d_{v}(\{i,j,k\})&=v(\{i,j,k\})-d_{v}(\{i,j\})-d_{v}(\{i,k\})-d_{v}(\{j,k\})-d_{v}(\{i\})-d_{v}(\{j\})-d_{v}(\{k\})\\&\vdots \\d_{v}(S)&=v(S)-\sum _{T\subsetneq S}d_{v}(T)\end{aligned}}}

تُعطى الصيغة الصريحة للأرباح الموزعة على النحو التالي:دv(S)=تيS(-1)|Sتي|v(تي){\textstyle d_{v}(S)=\sum _{T\subseteq S}(-1)^{|S\setminus T|}v(T)}الوظيفةدv:2شمالR{\displaystyle d_{v}:2^{N}\to \mathbb {R} }يُعرف أيضًا باسم معكوس موبيوس لـv:2شمالR{\displaystyle v:2^{N}\to \mathbb {R} }[ 17 ] في الواقع، يمكننا التعافيv{\displaystyle v}مندv{\displaystyle d_{v}}بمساعدة الصيغةv(S)=دv(S)+تيSدv(تي){\textstyle v(S)=d_{v}(S)+\sum _{T\subsetneq S}d_{v}(T)}.

تُعدّ أرباح هارساني مفيدة لتحليل كل من الألعاب ومفاهيم الحلول، على سبيل المثال، يتم الحصول على قيمة شابلي من خلال توزيع أرباح كل ائتلاف بين أعضائه، أي قيمة شابلي.ϕأنا(v){\displaystyle \phi _{i}(v)}لاعبأنا{\displaystyle i}داخل اللعبةv{\displaystyle v}يتم حسابها عن طريق جمع حصة اللاعب من أرباح جميع التحالفات التي ينتمي إليها،ϕأنا(v)=Sشمال:أناSدv(S)/|S|{\textstyle \phi _{i}(v)=\sum _{S\subset N:i\in S}{d_{v}(S)}/{|S|}}.

النوية

يتركv:2شمالR{\displaystyle v:2^{N}\to \mathbb {R} }دعها تكون لعبة، ودعهاxRشمال{\displaystyle x\in \mathbb {R} ^{N}}ليكن متجه العائد . فائضx{\displaystyle x}من أجل ائتلافSشمال{\displaystyle S\subseteq N}الكميةv(S)-أناSxأنا{\displaystyle v(S)-\sum _{i\in S}x_{i}}أي المكاسب التي يحققها اللاعبون في التحالفS{\displaystyle S}ويمكنهم الحصول على ذلك إذا انسحبوا من التحالف الكبيرشمال{\displaystyle N}أقل من السدادx{\displaystyle x}وبدلاً من ذلك، خذ المكافأةv(S){\displaystyle v(S)}النواةv{\displaystyle v}هو الإسناد الذي يكون فيه متجه التجاوزات لجميع التحالفات (متجه فيR2شمال{\displaystyle \mathbb {R} ^{2^{N}}}) هو الأصغر في ترتيب الليكسيمين . تم إدخال النوية في ( شمايدلر 1969 ) .

( ماشلر، بيليغ وشابلي 1979 ) قدموا وصفًا أكثر سهولة: بدءًا من الأقل قوة، سجل التحالفات التي يكون فيها الجانب الأيمن من عدم المساواة في تعريفجε(v){\displaystyle C_{\varepsilon }(v)}لا يمكن تقليصها أكثر من ذلك دون إفراغ المجموعة. استمر في تقليل الطرف الأيمن للتحالفات المتبقية، حتى يتعذر تقليصها دون إفراغ المجموعة. سجّل المجموعة الجديدة من التحالفات التي تتحقق فيها المتباينات عند التساوي؛ استمر في تقليل الطرف الأيمن للتحالفات المتبقية وكرر هذه العملية حسب الحاجة حتى يتم تسجيل جميع التحالفات. متجه العائد الناتج هو النواة.

ملكيات

  • على الرغم من أن التعريف لا ينص على ذلك صراحةً، إلا أن النواة تكون فريدة دائمًا. (انظر القسم II.7 من ( دريسن 1988 ) للاطلاع على البرهان).
  • إذا لم يكن اللب فارغًا، فإن النواة تكون في اللب.
  • النواة موجودة دائمًا في النواة، وبما أن النواة موجودة في مجموعة المساومة، فإنها دائمًا ما تكون في مجموعة المساومة (انظر ( دريسن 1988 ) لمزيد من التفاصيل).

ألعاب تعاونية محدبة

تُجسّد الألعاب التعاونية المحدبة، التي قدمها شابلي في ( شابلي 1971 ) ، الخاصية البديهية التي تتمتع بها بعض الألعاب والمتمثلة في "تراكم الضرر". وبالتحديد، تكون اللعبة محدبة إذا كانت دالتها المميزةv{\displaystyle v}هي فائقة الوحدات النمطية :

v(Sتي)+v(Sتي)v(S)+v(تي)، S،تيشمال.{\displaystyle v(S\cup T)+v(S\cap T)\geq v(S)+v(T),\forall ~S,T\subseteq N.}

يمكن إثبات (انظر، على سبيل المثال، القسم الخامس.1 من ( دريسن 1988 ) ) أن خاصية التفرع المعياري لـv{\displaystyle v}يعادل

v(S{أنا})-v(S)v(تي{أنا})-v(تي)، Sتيشمال{أنا}، أناشمال؛{\displaystyle v(S\cup \{i\})-v(S)\leq v(T\cup \{i\})-v(T),\forall ~S\subseteq T\subseteq N\setminus \{i\},\forall ~i\in N;}

أي أن "الحوافز للانضمام إلى ائتلاف تزداد مع نمو الائتلاف" ( شابلي، 1971 ) ، مما يؤدي إلى تأثير كرة الثلج المذكور آنفًا. أما في ألعاب التكلفة، فتنعكس المتباينات، فنقول إن لعبة التكلفة محدبة إذا كانت الدالة المميزة شبه معيارية .

ملكيات

تتمتع الألعاب التعاونية المحدبة بالعديد من الخصائص الجيدة:

  • يستلزم التفرع المعياري بشكل بديهي التفرع الجمعي .
  • الألعاب المحدبة متوازنة تمامًا : جوهر اللعبة المحدبة غير فارغ، وبما أن أي لعبة فرعية من لعبة محدبة هي محدبة، فإن جوهر أي لعبة فرعية غير فارغ أيضًا.
  • تتميز اللعبة المحدبة بمجموعة مستقرة فريدة تتطابق مع جوهرها .
  • قيمة شابلي للعبة المحدبة هي مركز ثقل جوهرها .
  • يمكن إيجاد نقطة قصوى (رأس) للمركز في وقت متعدد الحدود باستخدام الخوارزمية الجشعة : ليكنπ:شمالشمال{\displaystyle \pi :N\to N}ليكن تبديلاً للاعبين، وليكنSأنا={جشمال:π(ج)أنا}{\displaystyle S_{i}=\{j\in N:\pi (j)\leq i\}}ليكن مجموعة اللاعبين مرتبة1{\displaystyle 1}خلالأنا{\displaystyle i}فيπ{\displaystyle \pi }، لأيأنا=0،...،ن{\displaystyle i=0,\ldots ,n}، معS0={\displaystyle S_{0}=\emptyset }ثم تأتي المكافأةxRشمال{\displaystyle x\in \mathbb {R} ^{N}}محدد بواسطةxأنا=v(Sπ(أنا))-v(Sπ(أنا)-1)، أناشمال{\displaystyle x_{i}=v(S_{\pi (i)})-v(S_{\pi (i)-1}),\forall ~i\in N}هو رأس من رؤوس مركزv{\displaystyle v}يمكن إنشاء أي رأس من رؤوس النواة بهذه الطريقة عن طريق اختيار تبديل مناسب.π{\displaystyle \pi }.

أوجه التشابه والاختلاف مع التحسين التوافقي

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

مع ذلك، يعتبر مجتمع التحسين عمومًا الدوال شبه المعيارية نظائر منفصلة للدوال المحدبة ( لوفاس، 1983 ) ، لأن تصغير كلا النوعين من الدوال قابل للمعالجة حسابيًا. لسوء الحظ، يتعارض هذا بشكل مباشر مع تعريف شابلي الأصلي للدوال فوق المعيارية بأنها "محدبة".

العلاقة بين نظرية الألعاب التعاونية والشركة

يمكن للقرارات الاستراتيجية للشركات أن تتطور وتخلق قيمة من خلال نظرية الألعاب التعاونية. [ 18 ] وهذا يعني أن نظرية الألعاب التعاونية يمكن أن تصبح النظرية الاستراتيجية للشركة، وأن حلول نظرية الألعاب التعاونية المختلفة يمكنها محاكاة مؤسسات مختلفة.

انظر أيضاً

مراجع

  1. شور، مايك. "لعبة غير تعاونية - نظرية الألعاب.نت" . www.gametheory.net . تاريخ الاسترجاع: 15 سبتمبر 2016 .
  2. تشاندراسيكاران، ر. "نظرية الألعاب التعاونية" (PDF) .
  3. براندنبورغر، آدم. "نظرية الألعاب التعاونية: الدوال المميزة، والتخصيصات، والمساهمة الحدية" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 27-05-2016.
  4. 2شمال{\displaystyle 2^{N}}يشير إلى مجموعة القوى لـشمال{\displaystyle N}.
  5. خافيير موروس، فرانسيسكو (2019). أدوات نظرية الألعاب التعاونية في شبكات التحكم الائتلافية ( الطبعة الأولى). سبرينغر تشام. الصفحات 9-11 . ISBN   978-3-030-10488-7.
  6. بيترز، هانز، محرر (2008)، "الألعاب التعاونية ذات المنفعة القابلة للتحويل" ، نظرية الألعاب: منهج متعدد المستويات ، برلين، هايدلبرغ: سبرينغر، ص 121-131 ، doi : 10.1007/978-3-540-69291-1_9 ، ISBN  978-3-540-69291-1تم الاطلاع عليه بتاريخ 2026-04-09
  7. جورجيوس تشالكياداكيس؛ إديث إلكيند؛ مايكل ج. وولدريدج (25 أكتوبر 2011). الجوانب الحسابية لنظرية الألعاب التعاونية . دار مورغان وكلايبول للنشر. ISBN 978-1-60845-652-9.
  8. بيليج، ب. (2002). "الفصل 8: تحليل نظرية الألعاب للتصويت في اللجان". دليل الاختيار الاجتماعي والرفاهية ، المجلد 1. المجلد 1. الصفحات 395-423 . doi : 10.1016/S1574-0110(02)80012-1 . ISBN   9780444829146.
  9. انظر إلى قسم نظرية رايس لتعريف اللعبة البسيطة القابلة للحساب. على وجه الخصوص، جميع الألعاب المنتهية قابلة للحساب.
  10. كومابي، م.؛ ميهارا، هـ. ر. (2011). "قابلية حساب الألعاب البسيطة: دراسة شاملة للاحتمالات الأربعة والستين" (ملف PDF) . مجلة الاقتصاد الرياضي . 47 (2): 150-158 . arXiv : 1102.4037 . Bibcode : 2011arXiv1102.4037K . doi : 10.1016/j.jmateco.2010.12.003 . S2CID 775278 . 
  11. مُعدّل من الجدول 1 في كومابي وميهارا (2011). تُعرَّف الأنواع الستة عشر وفقًا للبديهيات الأربع التقليدية (الرتابة، والتوافق، والقوة، وعدم الضعف). على سبيل المثال، يشير النوع 1110 إلى ألعاب رتيبة (1)، وتوافقية (1)، وقوية (1)، وضعيفة (0، لأنها ليست غير ضعيفة). من بين ألعاب النوع 1110 ، لا توجد ألعاب محدودة غير قابلة للحساب، وتوجد ألعاب محدودة قابلة للحساب، ولا توجد ألعاب غير لانهائية غير قابلة للحساب، ولا توجد ألعاب لانهائية قابلة للحساب. لاحظ أن الأعمدة الثلاثة الأخيرة متطابقة باستثناء النوع 1110 .
  12. كومابي، م.؛ ميهارا، هـ. ر. (2008). "أعداد ناكامورا للألعاب البسيطة القابلة للحساب" . الاختيار الاجتماعي والرفاهية . 31 (4): 621. arXiv : 1107.0439 . doi : 10.1007/s00355-008-0300-5 . S2CID 8106333 . 
  13. أومان، روبرت ج. " جوهر لعبة تعاونية بدون مدفوعات جانبية ." معاملات الجمعية الرياضية الأمريكية (1961): 539-552.
  14. بيترز، هانز (2008). نظرية الألعاب: منهج متعدد المستويات . سبرينغر . ص 123. doi : 10.1007/978-3-540-69291-1_17 . ISBN  978-3-540-69290-4.
  15. يونغ، إتش بي (1985-06-01). "حلول رتيبة للألعاب التعاونية". المجلة الدولية لنظرية الألعاب . 14 (2): 65-72 . doi : 10.1007/BF01769885 . ISSN 0020-7276 . S2CID 122758426 .  
  16. هارساني، جون سي. (1982). "نموذج تفاوض مبسط للعبة التعاونية ذات n من الأشخاص". أوراق في نظرية الألعاب . مكتبة النظرية والقرار. سبرينغر، دوردريخت. ص 44-70 . doi : 10.1007/978-94-017-2527-9_3 . ISBN  9789048183692.
  17. دوال المجموعات، والألعاب، والسعات في صنع القرار | ميشيل غرابيش | سبرينغر . مكتبة النظرية والقرار، سبرينغر. 2016. ISBN 9783319306889.
  18. روس، ديفيد جاديس (2018-08-01). "استخدام نظرية الألعاب التعاونية للمساهمة في بحوث الاستراتيجية". مجلة الإدارة الاستراتيجية . 39 (11): 2859-2876 . doi : 10.1002/smj.2936 . S2CID 169982369 . 

للمزيد من القراءة

  • ديفيس، م.؛ ماشلر، م. (1965)، "جوهر اللعبة التعاونية"، مجلة البحوث اللوجستية البحرية الفصلية ، 12 (3): 223-259 ، doi : 10.1002/nav.3800120303
  • إدموندز، جاك (1970)، "الدوال شبه المعيارية، والماترويدات، وبعض المجسمات متعددة السطوح"، في جاي، ر.؛ حناني، هـ.؛ ساوير، ن.؛ شونهايم، ج. (محررون)، الهياكل التوافقية وتطبيقاتها ، نيويورك: جوردون وبريتش، ص 69-87 
  • لوفاس، لازلو ( 1983)، "الدوال شبه المعيارية والتحدب"، في باشم، أ.؛ غروتشل، م .؛ كورت، ب. (محررون)، البرمجة الرياضية - أحدث ما توصل إليه العلم ، برلين: سبرينغر، ص 235-257 
  • Lucas، William F. (1992)، “Von Neumann-Morgenstern Stable Sets”، في Aumann، Robert Jهارت، سيرجيو (محرران)، دليل نظرية اللعبة، المجلد الأول ، أمستردام: إلسفير ، الصفحات من 543 إلى 590 
  • Schmeidler, D. (1969), "The nucleolus of a characteristic function game", SIAM Journal on Applied Mathematics , 17 (6): 1163– 1170, doi : 10.1137/0117107 .
  • شابلي، لويد س. (1953)، "قيمة لـن{\displaystyle n}ألعاب اللاعبين"، في كون ، هـ.؛ تاكر، أ.و. (محرران)، مساهمات في نظرية الألعاب II ، برينستون، نيو جيرسي: مطبعة جامعة برينستون، ص 307-317 
  • يونغ، ديفيد دبليو كيه وليون أ. بتروسيان. ألعاب تفاضلية عشوائية تعاونية (سلسلة سبرينغر في بحوث العمليات والهندسة المالية)، سبرينغر، 2006. غلاف ورقي - رقم ISBN 978-1441920942.
  • يونغ، ديفيد دبليو كيه وليون أ. بتروسيان. التحسين الاقتصادي المتسق مع الألعاب الفرعية: تحليل متقدم للألعاب الديناميكية التعاونية (نظرية الألعاب الثابتة والديناميكية: الأسس والتطبيقات)، بيركهاوزر بوسطن؛ 2012. ISBN 978-0817682613