پیش‌نویس:ارزش شیپلی

لوید شاپلی در سال 2012

"این مقاله در حال ترجمه از ویکی انگلیسی است. لطفا حذف نشود."

ارزش Shapley یک راه حل در نظریه بازی های گروهی است. این نام به افتخار لوید شاپلی ، که به خاطر معرفی این مفهوم در سال 2012 برنده جایزه نوبل در اقتصاد شد، تعیین شده است. این ارزش به هر بازی گروهی ، توزیع منحصربه‌فردی (در بین بازیکنان) از کل مازاد تولید شده توسط ادغام همه بازیکنان را اختصاص می‌دهد. مقدار Shapley با مجموعه ای از ویژگی های مطلوب مشخص می شود. هارت (1989) یک بررسی کلی از موضوع را ارائه داده است.

مقدمات مسئله به صورت مقابل است: ائتلافی از بازیکنان در صورت همکاری با یکدیگر یک مقدار سود کلی مشخص به دست می آورند. با توجه به این که برخی از بازیکنان ممکن است بیشتر از سایرین در ائتلاف نقش داشته باشند یا قدرت چانه زنی متفاوتی داشته باشند (برای مثال تهدید به نابودی کل مازاد)، چه توزیع نهایی مازاد تولید شده ای بین بازیکنان باید در هر بازی خاص ایجاد شود؟ یا به بیان دیگر: هر بازیکن چقدر برای همکاری کلی مهم است، و می‌تواند انتظار چه سود منطقی ای را داشته باشد؟ ارزش Shapley یک پاسخ برای این سوال ارائه می دهد.

برای بازی های اشتراک هزینه ای با توابع هزینه مقعر، قانون اشتراک هزینه ای که قیمت آشفتگی و به دنبال آن قیمت ثبات را بهینه می کند، همان قانون اشتراک هزینه ارزش Shapley است. ( متقارن همین عبارت به طور مشابه برای بازی های به اشتراک گذاری ابزار با توابع ابزار محدب نیز معتبر است.) در طراحی ساز وکار ، این بدان معنی است که مفهوم راه حل ارزش Shapley برای این مجموعه از بازی ها بهینه است.

تعریف رسمی

به طور رسمی، یک بازی ائتلافی به این صورت تعریف می شود: یک مجموعه N (از n بازیکن) و یک تابع $v$ وجود دارد که زیرمجموعه های بازیکنان را به اعداد طبیعی نگاشت می کند: $v\colon 2^{N}\to \mathbb {R}$ ، با $v(\emptyset )=0$ ، جایی که $\emptyset$ مجموعه تهی را نشان می دهد و تابع $v$ تابع مشخصه نامیده می شود.

تابع $v$ به این معنی است: اگر S ائتلافی از بازیکنان باشد، پس ( S )$v$ که ارزش ائتلاف S نامیده می شود، کل مجموع سود مورد انتظار اعضای این ائتلاف را نشان میدهد که می توانند با همکاری هم به دست آورند.

ارزش Shapley یکی از راه‌های توزیع کل سود بین بازیکنان است، با این فرض که همه آنها با هم همکاری می‌کنند. این یک توزیع "عادلانه" است به این معنا که تنها توزیع دارای ویژگی های مطلوب خاصی است که ویژگی های آن در زیر ذکر شده است. با توجه به ارزش Shapley، مبلغی که به بازیکن i در یک بازی ائتلافی داده می شود و با $(v,N)$ نمایش میدهیم، به شرح زیر است:

$\varphi _{i}(v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {|S|!\;(n-|S|-1)!}{n!}}(v(S\cup \{i\})-v(S))$

$\quad \quad \quad ={\frac {1}{n}}\sum _{S\subseteq N\setminus \{i\}}{n-1 \choose n-|S|-1}^{-1}(v(S\cup \{i\})-v(S))$

که در آن n تعداد کل بازیکنان و جمع روی تمام زیرمجموعه های S از N که شامل بازیکن i نیستند، از جمله مجموعه تهی، پخش می شود. همچنین توجه داشته باشید که ${n \choose k}$ ضریب دو جمله ای است. فرمول را می توان اینگونه تفسیر کرد: تصور کنید ائتلاف در هر لحظه فقط با یک بازیکن شکل میگیرد و هر بازیگری خواستار مشارکت خود $v(S\cup \{i\})-v(S)$ به عنوان یک غرامت عادلانه است، و سپس برای هر بازیکن میانگین این همکاری را بر جایگشت های مختلف ممکن که در آن ائتلاف می تواند تشکیل شود، در نظر بگیرید.

یک فرمول معادل جایگزین برای ارزش Shapley این است:

$\varphi _{i}(v)={\frac {1}{n!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right]$

که در آن مجموع روی بازه ی $n!$ ترتیب $R$ از بازیکنان پخش شده و $P_{i}^{R}$ مجموعه ای از بازیکنان در $N$ است که در ترتیب $R$، $i$ مقدم است. در نهایت می توان آن را به این صورت هم بیان کرد

$\varphi _{i}(v)={\frac {1}{n}}\sum _{S\subseteq N\setminus \{i\}}{\binom {n-1}{|S|}}^{-1}(v(S\cup \{i\})-v(S))$

که می تواند به صورت زیر تفسیر شود.

$\varphi _{i}(v)={\frac {1}{\text{number of players}}}\sum _{{\text{coalitions including }}i}{\frac {{\text{marginal contribution of }}i{\text{ to coalition}}}{{\text{number of coalitions excluding }}i{\text{ of this size}}}}$

از نظر هم افزایی

بوسیله تابع مشخصه $v$ می توان هم افزایی ای را که هر گروه از بازیکنان بدست می آورند محاسبه کرد. هم افزایی یک تابع منحصر به فرد است $w\colon 2^{N}\to \mathbb {R}$ ، به طوری که

$v(S)=\sum _{R\subseteq S}w(R)$

برای هر زیر مجموعه $S\subseteq N$ از بازیکنان. به عبارت دیگر، "ارزش کل" ائتلاف $S$ از جمع هم افزایی هر زیر مجموعه ممکن از $S$ بدست می آید.

بر اساس تابع مشخصه داده شده $v$ ، تابع هم افزایی $w$ از طریق محاسبه می شود

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

با استفاده از اصل عدم شمول. به عبارت دیگر، هم افزایی ائتلاف $S$ برابر با ارزش $v(S)$ است، که قبلاً در زیرمجموعه های آن محاسبه نشده است.

ارزش های Shapley بر حسب تابع هم افزایی برابراند با .

$\varphi _{i}(v)=\sum _{i\in S\subseteq N}{\frac {w(S)}{|S|}}$

که در آن جمع روی همه زیر مجموعه های $S$ از $N$ است که شامل $i$ هستند.

این را می توان چنین تفسیر کرد

$\varphi _{i}(v)=\sum _{\text{coalitions including i}}{\frac {\text{synergy of the coalition}}{\text{members in the coalition}}}$

به عبارت دیگر، میزان هم افزایی هر ائتلاف به طور مساوی بین همه اعضا تقسیم می شود.

مثال ها

مثال تجاری

یک توضیح ساده از یک کسب و کار را در نظر بگیرید. یک مالک، o ، سرمایه پایه را فراهم می کند به این معنا که بدون او، هیچ سودی وجود نخواهد داشت. m کارگر w ₁ ... , w _m ,وجود دارد که هر یک به اندازه p به سود کل کمک می کند. فرض میکنیم:

$N=\{o,w_{1},\ldots ,w_{m}\}.$

تابع ارزش برای این بازی ائتلافی برابر است با

$v(S)={\begin{cases}(|S|-1)p&{\text{if }}o\in S\;,\\0&{\text{otherwise}}\;.\\\end{cases}}$

محاسبه مقدار Shapley برای این بازی ائتلافی مقدار mp/2 برای مالک وp/2 برای هر یک از m کارگران را منجر می شود.

این را می توان از منظر هم افزایی درک کرد. تابع هم افزایی $w$ را در نظر بگیرید.

$w(S)={\begin{cases}p,&{\text{if }}S=\{o,w_{i}\}\\0,&{\text{otherwise}}\\\end{cases}}$

بنابراین تنها ائتلاف هایی که هم افزایی ایجاد می کنند، ائتلاف های یک به یک بین مالک و هر کارگر است.

با استفاده از فرمول بالا برای ارزش Shapley بر حسب $w$ محاسبه می کنیم

$\varphi _{w_{i}}={\frac {w(\{o,w_{i}\})}{2}}={\frac {p}{2}}$

و

$\varphi _{o}=\sum _{i=1}^{m}{\frac {w(\{o,w_{i}\})}{2}}={\frac {mp}{2}}$

نتیجه را می توان از زاویه میانگین گیری روی همه ترتیب ها نیز بررسی کرد. یک کارگر معین بعد از مالک به ائتلاف می‌پیوندد (و بنابراین در نیمی از ترتیب ها مشارکت می‌کند ) و بنابراین سهم متوسطی از ${\frac {p}{2}}$ هنگام پیوستن ایجاد میکند. هنگامی که مالک ملحق می شود، به طور متوسط نیمی از کارگران قبلاً پیوسته اند، بنابراین میانگین سهم مالک هنگام پیوستن برابر است با ${\frac {mp}{2}}$ .

در یادگیری ماشین

ارزش Shapley روشی اصولی برای توضیح پیش‌بینی‌های مدل‌های غیرخطی رایج در زمینه یادگیری ماشین ارائه می‌کند. ارزش شپلی با تفسیر یک مدل آموزش‌دیده بر روی مجموعه‌ای از ویژگی‌ها به‌عنوان یک تابع ارزش در ائتلافی از بازیکنان، راهی طبیعی برای محاسبه اینکه کدام ویژگی‌ها برای رسیدن به یک پیش‌بینی یا عدم قطعیت یک پیش‌بینی همکاری می‌کنند، ارائه می‌دهد. این روش چندین روش دیگر از جمله Locally Interpretable Model-Agnostic Explanations (LIME)، DeepLIFT، و Layer-Wise Relevance Propagation را یکسان می کند.

همچنین ببینید

• مسئله فرودگاه
• شاخص توان بنزاف
• شاخص قدرت Shapley-Shubik