قيمة شابلي

الموسوعة الحرة

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

تُحدد قيمة شابلي مساهمة كل لاعب من خلال النظر في مدى تغير النتيجة الإجمالية عند انضمامه إلى كل توليفة ممكنة من اللاعبين الآخرين، ثم حساب متوسط ​​هذه التغيرات. وبعبارة أخرى، تحسب متوسط ​​المساهمة الحدية لكل لاعب عبر جميع التحالفات الممكنة. [ 3 ] [ 4 ] وهي الحل الوحيد الذي يُحقق أربع خصائص أساسية: الكفاءة، والتناظر، والجمعية، وخاصية اللاعب الوهمي (أو اللاعب المحايد)، [ 5 ] وهي خصائص مقبولة على نطاق واسع لتحديد التوزيع العادل.

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

لويد شابلي في عام 2012

تعريف

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

قيمة شابلي هي إحدى طرق تقسيم القيمة الناتجة عن تحالف بين أعضائه. وهي توزيع "عادل" بمعنى أنها التوزيع الوحيد الذي يتمتع بخصائص مرغوبة معينة (مذكورة أدناه). وفقًا لقيمة شابلي، [ 6 ] فإن المبلغ الذي يحصل عليه اللاعبأنا{\displaystyle i}يتم تقديمها في لعبة ائتلافية(v،شمال){\displaystyle (v,N)}يكون

φأنا(v)=∑S⊆شمال∖{أنا}|S|!(ن-|S|-1)!ن!(v(S∪{أنا})-v(S)){\displaystyle \varphi _{i}(v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {|S|!\;(n-|S|-1)!}{n!}}(v(S\cup \{i\})-v(S))}
=1ن∑S⊆شمال∖{أنا}(ن-1|S|)-1(v(S∪{أنا})-v(S)){\displaystyle \quad \quad \quad ={\frac {1}{n}}\sum _{S\subseteq N\setminus \{i\}}{n-1 \choose |S|}^{-1}(v(S\cup \{i\})-v(S))}

أينن{\displaystyle n}يمثل العدد الإجمالي للاعبين، ويشمل المجموع جميع المجموعات الفرعية.S{\displaystyle S}لشمال{\displaystyle N}لا يحتوي على لاعبأنا{\displaystyle i}، بما في ذلك المجموعة الفارغة. لاحظ أيضًا أن(نك){\displaystyle {n \choose k}}هو معامل ذات الحدين . يمكن تفسير الصيغة على النحو التالي: تخيل أن التحالف يتشكل من خلال ممثل واحد في كل مرة، حيث يطالب كل ممثل بمساهمته.v(S∪{أنا})-v(S){\displaystyle v(S\cup \{i\})-v(S)}كتعويض عادل، ثم لكل جهة فاعلة يتم حساب متوسط ​​هذه المساهمة على التباديل المختلفة الممكنة التي يمكن من خلالها تشكيل التحالف.

الصيغة البديلة والمكافئة لقيمة شابلي هي:

φأنا(v)=1ن!∑R[v(PأناR∪{أنا})-v(PأناR)]{\displaystyle \varphi _{i}(v)={\frac {1}{n!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right]}

حيث يمتد المجموع على جميعن!{\displaystyle n!}طلباتR{\displaystyle R}من اللاعبين وPأناR{\displaystyle P_{i}^{R}}هي مجموعة اللاعبين فيشمال{\displaystyle N}والتي تسبقأنا{\displaystyle i}بالترتيبR{\displaystyle R}.

من حيث التآزر

مخطط فين يوضح أوجه التآزر لقيم شابلي
مخطط فين لتقسيم أوجه التآزر التي مجموعها يساوي قيمة شابلي

من الدالة المميزةv{\displaystyle v}يمكن حساب التآزر ( عائد هارساني ) الذي توفره كل مجموعة من اللاعبين. التآزر هو دالة فريدةw:2شمال→R{\displaystyle w\colon 2^{N}\to \mathbb {R} }بحيث

v(S)=∑R⊆Sw(R){\displaystyle v(S)=\sum _{R\subseteq S}w(R)}

لأي مجموعة فرعيةS⊆شمال{\displaystyle S\subseteq N}من اللاعبين. بعبارة أخرى، "القيمة الإجمالية" للتحالفS{\displaystyle S}وينتج ذلك عن جمع أوجه التآزر لكل مجموعة فرعية ممكنة منS{\displaystyle S}.

بالنظر إلى دالة مميزةv{\displaystyle v}دالة التآزرw{\displaystyle w}يتم حسابها عبر

w(S)=∑R⊆S(-1)|S|-|R|v(R){\displaystyle w(S)=\sum _{R\subseteq S}(-1)^{|S|-|R|}v(R)}

باستخدام مبدأ الإدراج والاستبعاد .

يتم إعطاء قيم شابلي بدلالة دالة التآزر بواسطة [ 7 ] [ 8 ]

φأنا(v)=∑أنا∈S⊆شمالw(S)|S|{\displaystyle \varphi _{i}(v)=\sum _{i\in S\subseteq N}{\frac {w(S)}{|S|}}}

حيث يكون المجموع على جميع المجموعات الجزئيةS{\displaystyle S}لشمال{\displaystyle N}والتي تشمل اللاعبأنا{\displaystyle i}.

يمكن تفسير ذلك على النحو التالي

φأنا(v)=∑تحالفات تشمل أناتضافر جهود التحالفعدد الأعضاء في الائتلاف{\displaystyle \varphi _{i}(v)=\sum _{\text{coalitions including i}}{\frac {\text{synergy of the alliance}}{\text{number of members in the alliance}}}}

بمعنى آخر، يتم تقسيم التآزر بين كل تحالف بالتساوي بين جميع الأعضاء.

يمكن تفسير ذلك بصريًا باستخدام مخطط فين . في مخطط المثال الأول أعلاه، تم تمييز كل منطقة بمكافأة التآزر الخاصة بالتحالف المقابل. القيمة الإجمالية التي ينتجها التحالف هي مجموع مكافآت التآزر للتحالفات الفرعية المكونة له - في المثال، سيحقق تحالف اللاعبين المسميين "أنت" و"إيما" ربحًا قدره30+20+40=90{\displaystyle 30+20+40=90}بالدولار، مقارنة بأرباحهم الفردية البالغة30{\displaystyle 30}و20{\displaystyle 20}بالدولار على التوالي. ثم يتم تقسيم أوجه التآزر بالتساوي بين كل عضو في التحالف الفرعي الذي يساهم في هذا التآزر - كما هو موضح في الرسم البياني الثاني.

أمثلة

أمثلة تجارية

لنفترض وصفًا مبسطًا لمشروع تجاري. يوفر المالك، o ، رأس مال أساسيًا، إذ لا يمكن تحقيق أي مكاسب بدونه. يوجد m عامل ، w1 ، ...، wm ، يساهم كل منهم بمبلغ p في إجمالي الربح.

شمال={o،w1،...،wم}.{\displaystyle N=\{o,w_{1},\ldots ,w_{m}\}.}

دالة القيمة لهذه اللعبة الائتلافية هي

v(S)={(|S|-1)صلو o∈S،0خلاف ذلك.{\displaystyle v(S)={\begin{cases}(|S|-1)p&{\text{إذا كان }}o\in S\;,\\0&{\text{فيما عدا ذلك}}\;.\\\end{cases}}}

يؤدي حساب قيمة Shapley للعبة التحالف هذه إلى قيمة ⁠ mp / 2 ⁠ للمالك و ⁠ p / 2 ⁠ لكل واحد من العمال m .

يمكن فهم ذلك من منظور التآزر. وظيفة التآزرw{\displaystyle w}يكون

w(S)={ص،لو S={o،wأنا}0،خلاف ذلك{\displaystyle w(S)={\begin{cases}p,&{\text{if }}S=\{o,w_{i}\}\\0,&{\text{otherwise}}\\\end{cases}}}

لذا فإن التحالفات الوحيدة التي تولد التآزر هي التحالفات الفردية بين المالك وأي عامل فردي.

باستخدام الصيغة المذكورة أعلاه لحساب قيمة شابلي بدلالةw{\displaystyle w}نقوم بالحساب

φwأنا=w({o،wأنا})2=ص2{\displaystyle \varphi _{w_{i}}={\frac {w(\{o,w_{i}\})}{2}}={\frac {p}{2}}}

و

φo=∑أنا=1مw({o،wأنا})2=مص2{\displaystyle \varphi _{o}=\sum _{i=1}^{m}{\frac {w(\{o,w_{i}\})}{2}}={\frac {mp}{2}}}

يمكن فهم النتيجة أيضًا من منظور حساب المتوسط ​​لجميع الطلبات. ينضم عامل معين إلى التحالف بعد المالك (وبالتالي يساهم بمبلغ p ) في نصف الطلبات، وبالتالي يقدم مساهمة متوسطة قدرهاص2{\displaystyle {\frac {p}{2}}}عند الانضمام. عندما ينضم المالك، يكون نصف العمال قد انضموا بالفعل في المتوسط، لذا فإن متوسط ​​مساهمة المالك عند الانضمام هومص2{\displaystyle {\frac {mp}{2}}}.

لعبة القفازات

لعبة القفازات هي لعبة جماعية حيث يمتلك اللاعبون قفازات لليد اليسرى واليمنى، والهدف هو تشكيل أزواج.

شمال={1،2،3}،{\displaystyle N=\{1,2,3\},}

حيث يرتدي اللاعبان 1 و2 قفازات اليد اليمنى، بينما يرتدي اللاعب 3 قفاز اليد اليسرى.

دالة القيمة لهذه اللعبة الائتلافية هي

v(S)={1لو S∈{{1،3}،{2،3}،{1،2،3}}؛0خلاف ذلك.{\displaystyle v(S)={\begin{cases}1&{\text{إذا كان }}S\in \left\{\{1,3\},\{2,3\},\{1,2,3\}\right\};\\0&{\text{فيما عدا ذلك}}.\\\end{cases}}}

صيغة حساب قيمة شابلي هي

φأنا(v)=1|شمال|!∑R[v(PأناR∪{أنا})-v(PأناR)]،{\displaystyle \varphi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right],}

حيث يمثل R ترتيب اللاعبين وPأناR{\displaystyle P_{i}^{R}}هي مجموعة اللاعبين في N الذين يسبقون i في الترتيب R.

يعرض الجدول التالي المساهمات الهامشية للاعب رقم 1.

طلب Rمج11،2،3v({1})-v(∅)=0-0=01،3،2v({1})-v(∅)=0-0=02،1،3v({1،2})-v({2})=0-0=02،3،1v({1،2،3})-v({2،3})=1-1=03،1،2v({1،3})-v({3})=1-0=13،2،1v({1،3،2})-v({3،2})=1-1=0{\displaystyle {\begin{array}{|c|r|}{\text{Order }}R\,\!&MC_{1}\\\hline {1,2,3}&v(\{1\})-v(\varnothing )=0-0=0\\{1,3,2}&v(\{1\})-v(\varnothing )=0-0=0\\{2,1,3}&v(\{1,2\})-v(\{2\})=0-0=0\\{2,3,1}&v(\{1,2,3\})-v(\{2,3\})=1-1=0\\{3,1,2}&v(\{1,3\})-v(\{3\})=1-0=1\\{3,2,1}&v(\{1,3,2\})-v(\{3,2\})=1-1=0\end{array}}}

يراقب

φ1(v)=(16)(1)=16.{\displaystyle \varphi _{1}(v)=\!\left({\frac {1}{6}}\right)(1)={\frac {1}{6}}.}

يمكن إثبات ذلك من خلال حجة التناظر.

φ2(v)=φ1(v)=16.{\displaystyle \varphi _{2}(v)=\varphi _{1}(v)={\frac {1}{6}}.}

بسبب بديهية الكفاءة، فإن مجموع جميع قيم شابلي يساوي 1، مما يعني أن

φ3(v)=46=23.{\displaystyle \varphi _{3}(v)={\frac {4}{6}}={\frac {2}{3}}.}

ملكيات

تتمتع قيمة شابلي بالعديد من الخصائص المرغوبة، بما في ذلك استيفاء الخصائص الأربع للكفاءة والتناظر والخطية ولاعب الصفر (أو اللاعب الوهمي). [ 5 ]

كفاءة

مجموع قيم شابلي لجميع الوكلاء يساوي قيمة التحالف الكبير، بحيث يتم توزيع كل المكاسب بين الوكلاء:

∑أنا∈شمالφأنا(v)=v(شمال){\displaystyle \sum _{i\in N}\varphi _{i}(v)=v(N)}

دليل :∑أنا∈شمالφأنا(v)=1|شمال|!∑R∑أنا∈شمالv(PأناR∪{أنا})-v(PأناR){\displaystyle \sum _{i\in N}\varphi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\sum _{i\in N}v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})}=1|شمال|!∑Rv(شمال)=1|شمال|!|شمال|!⋅v(شمال)=v(شمال){\displaystyle ={\frac {1}{|N|!}}\sum _{R}v(N)={\frac {1}{|N|!}}|N|!\cdot v(N)=v(N)}

منذ∑أنا∈شمالv(PأناR∪{أنا})-v(PأناR){\displaystyle \sum _{i\in N}v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})}هو مجموع متداخل وهناك|شمال|!{\displaystyle |N|!}ترتيبات مختلفةR{\displaystyle R}.

التناظر

لوأنا{\displaystyle i}وج{\displaystyle j}هما ممثلان متكافئان بمعنى أن

v(S∪{أنا})=v(S∪{ج}){\displaystyle v(S\cup \{i\})=v(S\cup \{j\})}

لكل مجموعة جزئيةS{\displaystyle S}لشمال{\displaystyle N}الذي لا يحتوي على أي منهماأنا{\displaystyle i}ولاج{\displaystyle j}، ثمφأنا(v)=φج(v){\displaystyle \varphi _{i}(v)=\varphi _{j}(v)}.

وتسمى هذه الخاصية أيضاً بالمعاملة المتساوية للأقران .

الخطية

إذا تم وصف لعبتين تحالفيتين بدوال الربحv{\displaystyle v}وw{\displaystyle w}إذا تم دمجها، فإن المكاسب الموزعة يجب أن تتوافق مع المكاسب المستمدة منv{\displaystyle v}والمكاسب المستمدة منw{\displaystyle w}:

φأنا(v+w)=φأنا(v)+φأنا(w){\displaystyle \varphi _{i}(v+w)=\varphi _{i}(v)+\varphi _{i}(w)}

لكلأنا{\displaystyle i}في شمال{\displaystyle N}كذلك، لأي عدد حقيقيأ{\displaystyle a}،

φأنا(أv)=أφأنا(v){\displaystyle \varphi _{i}(av)=a\varphi _{i}(v)}

لكلأنا{\displaystyle i}في شمال{\displaystyle N}.

لاعب فارغ

قيمة شابليφأنا(v){\displaystyle \varphi _{i}(v)}لاعب فارغأنا{\displaystyle i}في لعبةv{\displaystyle v}يساوي صفرًا. لاعبأنا{\displaystyle i}فارغ في​v{\displaystyle v}لوv(S∪{أنا})=v(S){\displaystyle v(S\cup \{i\})=v(S)}لجميع التحالفاتS{\displaystyle S}التي لا تحتويأنا{\displaystyle i}.

اختبار مستقل

لوv{\displaystyle v}هي دالة مجموعة شبه جمعية ، أي إذاv(S∪تي)≤v(S)+v(تي){\displaystyle v(S\cup T)\leq v(S)+v(T)}ثم لكل وكيلأنا{\displaystyle i}:φأنا(v)≤v({أنا}){\displaystyle \varphi _{i}(v)\leq v(\{i\})}.

وبالمثل، إذاv{\displaystyle v}هي دالة مجموعة فائقة الجمع ، أي إذاv(S∪تي)≥v(S)+v(تي){\displaystyle v(S\cup T)\geq v(S)+v(T)}لS∩تي=∅{\displaystyle S\cap T=\emptyset }ثم لكل وكيلأنا{\displaystyle i}: φأنا(v)≥v({أنا}){\displaystyle \varphi _{i}(v)\geq v(\{i\})}.

لذا، إذا كان التعاون ذا تآزر إيجابي، فإن جميع الأطراف تربح (بشكل ضعيف)، وإذا كان ذا تآزر سلبي، فإن جميع الأطراف تخسر (بشكل ضعيف). [ 9 ] : 147-156

إخفاء الهوية

لوأنا{\displaystyle i}وج{\displaystyle j}هما وكيلان، وw{\displaystyle w}هي دالة كسب مطابقة لـv{\displaystyle v}باستثناء أدوارأنا{\displaystyle i}وج{\displaystyle j}تم تبادلها، ثمφأنا(v)=φج(w){\displaystyle \varphi _{i}(v)=\varphi _{j}(w)}وهذا يعني أن تصنيف الوكلاء لا يلعب دوراً في تخصيص مكاسبهم.

التهميش

يمكن تعريف قيمة شابلي كدالة تستخدم فقط المساهمات الهامشية للاعبأنا{\displaystyle i}كما في الحجج.

قيمة أومان-شابلي

في كتابهما الصادر عام 1974، قام لويد شابلي وروبرت أومان بتوسيع مفهوم قيمة شابلي ليشمل الألعاب اللانهائية (المعرفة بالنسبة إلى مقياس غير ذري )، مما أدى إلى إنشاء الصيغة القطرية. [ 10 ] وقد تم توسيع هذا المفهوم لاحقًا بواسطة جان فرانسوا ميرتنز وأبراهام نيمان .

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

بصورة رمزية، إذا كانت v هي دالة قيمة التحالف التي تربط كل تحالف c بقيمته، وكان كل تحالف c عبارة عن مجموعة فرعية قابلة للقياس من المجموعة القابلة للقياس I لجميع اللاعبين، والتي نفترض أنهاأنا=[0،1]{\displaystyle I=[0,1]}دون الإخلال بعمومية المسألة، فإن القيمة(Sv)(دs){\displaystyle (Sv)(ds)}لاعب متناهي الصغر ds في اللعبة هو

(Sv)(دs)=∫01(v(تأنا+دs)-v(تأنا))دت.{\displaystyle (Sv)(ds)=\int _{0}^{1}(\,v(tI+ds)-v(tI)\,)\,dt.}

هنا ، يمثل tI عينة مثالية من مجموعة اللاعبين I التي تحتوي على نسبة t من جميع اللاعبين، وتأنا+دs{\displaystyle tI+ds}هو التحالف الذي يتم الحصول عليه بعد انضمام ds إلى tI . هذه هي الصيغة الاستدلالية للصيغة القطرية. [ 10 ]

بافتراض بعض الانتظام لدالة القيمة، على سبيل المثال، بافتراض أن v يمكن تمثيلها كدالة قابلة للتفاضل لمقياس غير ذري على I ، μ ،v(ج)=و(μ(ج)){\displaystyle v(c)=f(\mu (c))}باستخدام دالة الكثافةφ{\displaystyle \varphi }، معμ(ج)=∫1ج(u)φ(u)دu،{\displaystyle \mu (c)=\int 1_{c}(u)\varphi (u)\,du,}أين1ج(∙){\displaystyle 1_{c}(\bullet )}هي الدالة المميزة لـ c . في ظل هذه الظروف

μ(تأنا)=تμ(أنا){\displaystyle \mu (tI)=t\mu (I)}،

كما يمكن إثبات ذلك بتقريب الكثافة بدالة متدرجة مع الحفاظ على النسبة t لكل مستوى من مستويات دالة الكثافة، و

v(تأنا+دs)=و(تμ(أنا))+و′(تμ(أنا))μ(دs).{\displaystyle v(tI+ds)=f(t\mu (I))+f'(t\mu (I))\mu (ds).}

وبالتالي فإن الصيغة القطرية تأخذ الشكل الذي طوره أومان وشابلي (1974).

(Sv)(دs)=∫01وتμ(أنا)′(μ(دs))دت{\displaystyle (Sv)(ds)=\int _{0}^{1}f'_{t\mu (I)}(\mu (ds))\,dt}

يمكن أن تكون القيم الأعلى من μ متجهة (طالما أن الدالة معرفة وقابلة للتفاضل على مدى μ ، فإن الصيغة أعلاه منطقية).

في الحجة أعلاه، إذا كان المقياس يحتوي على ذراتμ(تأنا)=تμ(أنا){\displaystyle \mu (tI)=t\mu (I)}لم يعد هذا صحيحًا - ولهذا السبب تنطبق الصيغة القطرية في الغالب على الألعاب غير الذرية.

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

(Sv)(دs)=ليمε→0،ε>01ε∫01-ε(و(ت+εμ(دs))-و(ت))دت{\displaystyle (Sv)(ds)=\lim _{\varepsilon \to 0,\varepsilon >0}{\frac {1}{\varepsilon }}\int _{0}^{1-\varepsilon }(f(t+\varepsilon \mu (ds))-f(t))\,dt}

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

التعميم على التحالفات

تُخصص قيمة شابلي قيمًا للعناصر الفردية فقط. وقد تم تعميمها [ 14 ] لتطبيقها على مجموعة من العناصر C على النحو التالي:

φج(v)=∑تي⊆شمال∖ج(ن-|تي|-|ج|)!|تي|!(ن-|ج|+1)!∑S⊆ج(-1)|ج|-|S|v(S∪تي).{\displaystyle \varphi _{C}(v)=\sum _{T\subseteq N\setminus C}{\frac {(n-|T|-|C|)!\;|T|!}{(n-|C|+1)!}}\sum _{S\subseteq C}(-1)^{|C|-|S|}v(S\cup T)\;.}

من حيث وظيفة التآزرw{\displaystyle w}أعلاه، يقرأ هذا [ 7 ] [ 8 ]

φج(v)=∑ج⊆تي⊆شمالw(تي)|تي|-|ج|+1{\displaystyle \varphi _{C}(v)=\sum _{C\subseteq T\subseteq N}{\frac {w(T)}{|T|-|C|+1}}}

حيث يشمل المجموع جميع المجموعات الجزئيةتي{\displaystyle T}لشمال{\displaystyle N}التي تحتويج{\displaystyle C}.

تشير هذه الصيغة إلى تفسير مفاده أن قيمة شابلي للتحالف تُعتبر قيمة شابلي القياسية للاعب منفرد، إذا كان التحالفج{\displaystyle C}يتم التعامل معه كلاعب واحد.

قيمة اللاعب بالنسبة للاعب آخر

قيمة شابليφأنا(v){\displaystyle \varphi _{i}(v)}تم تحليلها بواسطة هاوسكن وماتياس [ 15 ] إلى مصفوفة من القيم

φأناج(v)=∑S⊆شمال(|S|-1)!(ن-|S|)!ن!(v(S)-v(S∖{أنا})-v(S∖{ج})+v(S∖{أنا،ج}))∑ت=|S|ن1ت{\displaystyle \varphi _{ij}(v)=\sum _{S\subseteq N}{\frac {(|S|-1)!\;(n-|S|)!}{n!}}(v(S)-v(S\setminus \{i\})-v(S\setminus \{j\})+v(S\setminus \{i,j\}))\sum _{t=|S|}^{n}{\frac {1}{t}}}

كل قيمةφأناج(v){\displaystyle \varphi _{ij}(v)}يمثل قيمة اللاعبأنا{\displaystyle i}إلى اللاعبج{\displaystyle j}هذه المصفوفة تحقق ما يلي:

φأنا(v)=∑ج∈شمالφأناج(v){\displaystyle \varphi _{i}(v)=\sum _{j\in N}\varphi _{ij}(v)}

أي قيمة اللاعبأنا{\displaystyle i}بالنسبة للعبة بأكملها، فإن مجموع قيمتها بالنسبة لجميع اللاعبين الأفراد هو ما يمثل مجموع قيمتها بالنسبة لهم.

من حيث التآزرw{\displaystyle w}كما هو موضح أعلاه، هذا ما يلي:

φأناج(v)=∑{أنا،ج}⊆S⊆شمالw(S)|S|2{\displaystyle \varphi _{ij}(v)=\sum _{\{i,j\}\subseteq S\subseteq N}{\frac {w(S)}{|S|^{2}}}}

حيث يشمل المجموع جميع المجموعات الجزئيةS{\displaystyle S}لشمال{\displaystyle N}التي تحتويأنا{\displaystyle i}وج{\displaystyle j}.

يمكن تفسير ذلك على أنه مجموع جميع المجموعات الفرعية التي تحتوي على لاعبينأنا{\displaystyle i}وج{\displaystyle j}، حيث لكل مجموعة جزئيةS{\displaystyle S}أنت

  • استغل التآزرw(S){\displaystyle w(S)}من تلك المجموعة الفرعية
  • اقسمه على عدد اللاعبين في المجموعة الفرعية|S|{\displaystyle |S|}فسر ذلك على أنه اللاعب الذي يحقق فائض القيمةأنا{\displaystyle i}المكاسب من هذا التحالف
  • ثم اقسم هذا على|S|{\displaystyle |S|}للحصول على دور اللاعبأنا{\displaystyle i}القيمة المنسوبة إلى اللاعبج{\displaystyle j}

بمعنى آخر، يتم تقسيم قيمة التآزر لكل تحالف بالتساوي بين الجميع|S|2{\displaystyle |S|^{2}}أزواج(أنا،ج){\displaystyle (i,j)}من اللاعبين في ذلك التحالف، حيثأنا{\displaystyle i}يُنتج فائضًا لـج{\displaystyle j}.

انحدار قيمة شابلي

يُعدّ تحليل انحدار قيمة شابلي أسلوبًا إحصائيًا يُستخدم لقياس مساهمة كل مُتنبئ في نموذج الانحدار. في هذا السياق، تُمثّل "المُتنبئات" المُتنبئات أو المُتغيرات الفردية في النموذج، بينما يُمثّل "الربح" إجمالي التباين المُفسّر أو القدرة التنبؤية للنموذج. يضمن هذا الأسلوب توزيعًا عادلًا للربح الإجمالي بين المُتنبئات، حيث يُخصّص لكل مُتنبئ قيمة تُمثّل مساهمته في أداء النموذج. [ 16 ]

تُعرف مساهمات قيمة شابلي بتوازنها بين الثبات والقدرة على التمييز، مما يجعلها مناسبة لقياس أهمية سمات الخدمة بدقة في أبحاث السوق. [ 17 ] وقد طبقت العديد من الدراسات انحدار قيمة شابلي على تحليل المحركات الرئيسية في أبحاث التسويق. استخدمت بوكريشيفسكايا وأنتيبوف (2012) هذه الطريقة لتحليل نوايا العملاء عبر الإنترنت في تكرار الشراء، مما يدل على فعاليتها في فهم سلوك المستهلك. [ 18 ] وبالمثل، طبق أنتيبوف وبوكريشيفسكايا (2014) انحدار قيمة شابلي لتفسير الاختلافات في معدلات التوصية للفنادق في جنوب قبرص، مما يسلط الضوء على فائدتها في قطاع الضيافة. [ 19 ] كما قدم فريينز وفيدن وبوش (2021) مزيدًا من التأكيد على فوائد قيمة شابلي في تحليل المحركات الرئيسية، حيث أكدوا على مزاياها في تحليلات التسويق التطبيقية. [ 20 ]

في مجال التعلم الآلي

تُقدّم قيمة شابلي طريقةً منهجيةً لشرح تنبؤات النماذج غير الخطية الشائعة في مجال التعلّم الآلي . فمن خلال تفسير نموذج مُدرّب على مجموعة من الميزات كدالة قيمة على تحالف من اللاعبين، تُوفّر قيم شابلي طريقةً طبيعيةً لحساب الميزات التي تُساهم في التنبؤ [ 21 ] أو تُساهم في عدم اليقين فيه [22]. وهذا يُوحّد العديد من الطرق الأخرى، بما في ذلك التفسيرات المحلية القابلة للتفسير والمستقلة عن النموذج (LIME) [ 23 ] ، و DeepLIFT [ 24 ] ، ونشر الصلة على مستوى الطبقات [ 25 ] [ 26 ] .

تُعد القيم التوزيعية امتدادًا لقيمة شابلي وعوامل القيمة ذات الصلة المصممة للحفاظ على المخرجات الاحتمالية للنماذج التنبؤية في التعلم الآلي، بما في ذلك مصنفات الشبكات العصبية ونماذج اللغة الكبيرة . [ 27 ]

لا يزال الفهم الإحصائي لقيم شابلي موضوعًا بحثيًا مستمرًا. وقد حققت نسخة سلسة منها، تُسمى منحنيات شابلي [ 28 ] ، معدل الحد الأدنى الأقصى ، وثبت أنها تقترب من التوزيع الغاوسي في بيئة غير بارامترية . ويمكن الحصول على فترات الثقة للعينات المحدودة باستخدام طريقة التمهيد العشوائي .

انظر أيضاً

مراجع

  1. ↑ شابلي، لويد س. (21 أغسطس 1951). "ملاحظات حول لعبة اللاعبين المتعددين - الجزء الثاني: قيمة لعبة اللاعبين المتعددين" (ملف PDF) . سانتا مونيكا، كاليفورنيا: مؤسسة راند.
  2. ↑ روث، ألفين إي.، محرر. (1988). قيمة شابلي: مقالات تكريمًا للويد إس. شابلي . كامبريدج: مطبعة جامعة كامبريدج. doi : 10.1017/CBO9780511528446 . ISBN 0-521-36177-X.
  3. ↑ هارت، سيرجيو (1989). "قيمة شابلي". في إيتويل، ج.؛ ميلجيت، م.؛ نيومان، ب. (محررون). بالغراف الجديد: نظرية الألعاب . نورتون. ص 210-216 . doi : 10.1007/978-1-349-20181-5_25 . ISBN  978-0-333-49537-7.
  4. ↑ هارت، سيرجيو (12 مايو 2016). "قائمة مراجع الألعاب التعاونية: نظرية القيمة" .
  5. 1 2 شابلي، لويد س. (1953). "قيمة لألعاب ن من اللاعبين". في: كون، هـ. و.؛ تاكر، أ. و. (محرران). مساهمات في نظرية الألعاب . حوليات دراسات الرياضيات . المجلد 28. مطبعة جامعة برينستون. الصفحات 307-317 . doi : 10.1515/9781400881970-018 . ISBN   978-1-4008-8197-0.{{cite book}}عدم توافق رقم ISBN / التاريخ ( مساعدة )
  6. ↑ للاطلاع على برهان الوجود الفريد، انظر: إيتشيشي، تاتسورو (1983). نظرية الألعاب للتحليل الاقتصادي . نيويورك: أكاديميك برس. الصفحات 118-120 . ISBN  0-12-370180-5.
  7. 1 2 غرابيش، ميشيل (أكتوبر 1997). "تمثيلات بديلة للمقاييس الضبابية المنفصلة لاتخاذ القرارات". المجلة الدولية للغموض والضبابية وأنظمة المعرفة . 5 (5): 587-607 . doi : 10.1142/S0218488597000440 . ISSN 0218-4885 . 
  8. 1 2 غرابيش، ميشيل (1 ديسمبر 1997). "مقاييس ضبابية منفصلة جمعية من الرتبة k وتمثيلها". مجموعات وأنظمة ضبابية . 92 (2): 167-189 . doi : 10.1016/S0165-0114(97)00168-1 . ISSN 0165-0114 . 
  9. ↑ هيرفيه مولان (2004). التقسيم العادل والرفاهية الجماعية . كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 9780262134231.
  10. 1 2 أومان، روبرت جيه؛ شابلي، لويد إس. (1974). قيم الألعاب غير الذرية . برينستون: مطبعة جامعة برينستون. ISBN 0-691-08103-4.
  11. ↑ ميرتنز، جان فرانسوا (1980). "القيم والمشتقات". رياضيات بحوث العمليات . 5 (4): 523-552 . doi : 10.1287/moor.5.4.523 . JSTOR 3689325 . 
  12. ↑ ميرتنز، جان فرانسوا (1988). "قيمة شابلي في الحالة غير التفاضلية". المجلة الدولية لنظرية الألعاب . 17 (1): 1-65 . doi : 10.1007/BF01240834 . S2CID 118017018 . 
  13. ↑ نيمان، أ.، 2002. قيمة الألعاب ذات عدد لا نهائي من اللاعبين، "دليل نظرية الألعاب مع التطبيقات الاقتصادية"، دليل نظرية الألعاب مع التطبيقات الاقتصادية، إلسيفير، الطبعة 1، المجلد 3، العدد 3، 00. آر جيه أومان وإس هارت (محرران).
  14. ↑ غرابيش، ميشيل؛ روبنز، مارك (1999). "مقاربة بديهية لمفهوم التفاعل بين اللاعبين في الألعاب التعاونية". المجلة الدولية لنظرية الألعاب . 28 (4): 547-565 . doi : 10.1007/s001820050125 . S2CID 18033890 . 
  15. ↑ هاوسكن، كيل؛ موهر، ماتياس (2001). " قيمة اللاعب في الألعاب متعددة اللاعبين". الاختيار الاجتماعي والرفاهية . 18 (3): 465-483 . doi : 10.1007/s003550000070 . JSTOR 41060209. S2CID 27089088 .  
  16. ↑ ليبوفيتسكي إس، كونكلين إم (2001). "تحليل الانحدار في منهج نظرية الألعاب". النماذج العشوائية التطبيقية في الأعمال والصناعة . 17 (4): 319-330 . doi : 10.1002/asmb.446 .
  17. ↑ بوكريشيفسكايا إي، أنتيبوف إي (2014). "مقارنة بين الطرق المستخدمة لقياس أهمية سمات الخدمة". المجلة الدولية لأبحاث السوق . 56 (3): 283-296 . doi : 10.2501/IJMR-2014-020 .
  18. ↑ بوكريشيفسكايا إي بي، أنتيبوف إي إيه (2012). "التحليل الاستراتيجي لنوايا العملاء عبر الإنترنت في تكرار الشراء". مجلة الاستهداف والقياس والتحليل للتسويق . 20 : 203-211 . doi : 10.1057/jt.2012.13 .
  19. ↑ أنتيبوف إي إيه، بوكريشيفسكايا إي بي (2014). "تفسير الاختلافات في معدلات التوصية: حالة فنادق جنوب قبرص". النشرة الاقتصادية . 34 (4): 2368-2376 .
  20. ↑ فريينز م، فيدن س، بوش ن (2021). "فوائد قيمة شابلي في تحليل المحركات الرئيسية". تحليلات التسويق التطبيقية . 6 (3): 269-278 .
  21. ↑ لوندبيرغ، سكوت م.؛ لي، سو-إن (2017). "نهج موحد لتفسير تنبؤات النموذج" . التقدم في أنظمة معالجة المعلومات العصبية . 30 : 4765-4774 . arXiv : 1705.07874 . تاريخ الاسترجاع : 30 يناير 2021 .
  22. ↑ واتسون، ديفيد؛ أوهارا ، جوشوا؛ تاكس، نيك؛ مود، ريتشارد؛ جاي، إيدو (2023). "شرح عدم اليقين التنبؤي باستخدام شابلي في نظرية المعلومات". التقدم في أنظمة معالجة المعلومات العصبية . 37. arXiv : 2306.05724 .
  23. ^ ريبيرو، ماركو توليو. سينغ، سمير. جوسترين ، كارلوس (2016/08/13). ""لماذا يجب أن أثق بك؟"وقائع المؤتمر الدولي الثاني والعشرين لجمعية ACM SIGKDD حول اكتشاف المعرفة واستخراج البيانات . نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 1135-1144 . doi : 10.1145/2939672.2939778 . ISBN  978-1-4503-4232-2.
  24. ↑ شريكومار، أفانتي؛ جرينسايد، بيتون؛ كونداجي، أنشول (17 يوليو 2017). "تعلم السمات المهمة من خلال نشر اختلافات التنشيط" . PMLR : 3145-3153 . ISSN 2640-3498 . تاريخ الاسترجاع: 30 يناير 2021 . 
  25. ↑ باخ، سيباستيان؛ بيندر، ألكسندر؛ مونتافون، غريغوار؛ كلاوشين، فريدريك؛ مولر، كلاوس-روبرت ؛ ساميك، فويتش (10 يوليو 2015). سواريز، أوسكار دينيز (محرر). "حول التفسيرات على مستوى البكسل لقرارات المصنفات غير الخطية من خلال نشر الصلة على مستوى الطبقات" . PLOS ONE . 10 (7) e0130140. مكتبة العلوم العامة (PLoS). Bibcode : 2015PLoSO..1030140B . doi : 10.1371/journal.pone.0130140 . ISSN 1932-6203 . PMC 4498753. PMID 26161953 .   
  26. ↑ أنتيبوف، إي. أ.؛ بوكريشيفسكايا، إي. ب. (2020). "التعلم الآلي القابل للتفسير لنمذجة الطلب باستخدام بيانات عالية الأبعاد باستخدام آلات تعزيز التدرج وقيم شابلي". مجلة إدارة الإيرادات والتسعير . 19 (5): 355-364 . doi : 10.1057/s41272-020-00236-4 .
  27. ↑ فرانشيسكي إل، دونيني إم، أرتشامبو سي، سيجر إم (2024). "شرح النماذج الاحتمالية باستخدام القيم التوزيعية". وقائع المؤتمر الدولي الحادي والأربعين للتعلم الآلي (ICML 2024) . arXiv : 2402.09947 .
  28. ↑ ميفتشوف، راتمير؛ كيلبار، جورج؛ هاردل، وولفغانغ (2025). "منحنيات شابلي: منظور التنعيم" . مجلة الأعمال والإحصاءات الاقتصادية . 43 (2): 312-323 . doi : 10.1080/07350015.2024.2365781 .

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