ارائه روشی جدید جهت بهبود بازدهی تخصیص پهنای باند پویا ... |
برای حل بازیهای همکارانه، راهکارهای متعددی به عنوان روشهای تقسیم کل دارایی میان بازیکنان وجود دارد که در این جا به دو مورد از آنها پرداخته شده است. راهکارهای بازیهای همکارانه، مسئلهی چگونگی توزیع دارایی کلی میان بازیکنانی که در ائتلافهای مختلف با هم همکاری دارند را حل میکنند و نتیجهی هرکدام از این راهکارها، بردار تخصیصی است که هر عنصر از آن، سهم هرکدام از بازیکنان از دارایی کل را تعیین میکند.
۳-۴-۱- راهکار مقدار شپلی[۱۳۶]
تعریف: شپلی راهکاری اصولی پیشنهاد کرده است که برای هر بازی ائتلافی ، بردار تخصیصی منحصر به فرد به نام مقدار بازی (با مقدار ائتلاف تفاوت دارد) در نظر میگیرد. شپلی نشان داده است نگاشتِ منحصر به فردِ مقدار شپلی از فضای بازی ائتلافی به RN وجود دارد ( سهمی است که توسط مقدار شپلی، به بازیکن داده میشود) که چهار اصل زیر را برآورده میکند[۳۵]:
۱- اصل کارایی[۱۳۷]: براساس این اصل، همانطور که در معادله (۳-۱) نشان داده شده است، مجموع سهمهای تخصیص یافته به بازیکنان برابر با کل سود حاصل از ائتلاف بزرگ است.
(۳-۱)
۲- اصل تقارن[۱۳۸]: براساس این اصل، همانطور که در معادله (۳-۲) نشان داده شده است، اگر بازیکن و بازیکن به گونهای باشند که میزان تاثیرِ حضور آنها در ائتلافی مانند S یکسان باشد، آنگاه سهم این دو بازیکن از دارایی یکسان خواهد بود.
(۳-۲)
۳- اصل ساختگی[۱۳۹]: براساس این اصل، همانطور که در معادله (۳-۳) نشان داده شده است، اگر بازیکن به گونهای باشد که عضویت آن در ائتلاف S، تاثیری در آن ائتلاف نداشته باشد، سهمی از دارایی به آن تعلق نمیگیرد.
(۳-۳)
۴- اصل افزونگی[۱۴۰]: اگر و توابع مشخصه باشند، آنگاه معادله (۳-۴) برقرار است:
(۳-۴)
بنابراین برای هر بازی ، مقدار شپلی ، سهمی منحصر به فرد از RN به بازیکنان تخصیص میدهد که چهار اصل فوق را تضمین میکند. اصل کارایی در واقع همان عقلانیت گروهی است. اصل تقارن بیان میکند که وقتی دو بازیکن دارای تاثیری یکسان در یک ائتلاف میباشند باید سهم یکسانی در اثر شرکت در ائتلاف به آنها داده شود. اصل ساختگی هیچ سهمی را به بازیکنانی که تاثیر مثبتی در ائتلاف ندارند اختصاص نمیدهد و در نهایت، اصل افزونگی دو بازی مختلف و را بهم پیوند میدهد و اثبات میکند که نگاشتی منحصر به فرد از فضای تمامی بازیهای ائتلافی است. مقدار شپلی یک تفسیر دیگر نیز دارد که ترتیب ملحق شدن بازیکنان به ائتلاف بزرگِ N را به حساب میآورد. در صورت ملحق شدن بازیکنان به ائتلاف بزرگ با ترتیبی تصادفی، سهمی که توسط مقدار شپلی به بازیکن تخصیص داده میشود، برابر است با سهم مرزی این بازیکن وقتی به ائتلاف بزرگ میپیوندد. طبق این تفسیر، مقدار شپلی ، سهم را براساس معادلهی (۳-۵) به هر بازیکن تخصیص میدهد[۳۵].
(۳-۵)
در معادلهی (۳-۵) بدیهی است سهم مرزی بازیکن در ائتلاف برابر است با . وزنی که در مقابل استفاده شده است، احتمال مواجه شدن با ائتلاف است وقتی با ترتیبی تصادفی وارد میشود، برای مثال بازیکنان مقابل بازیکنانی هستند که کماکان در حضور دارند. |S|! راه برای چینش بازیکنان ائتلاف در ابتدای مرتب سازی و (N-|S|-1)! راه برای چینش بازیکنان باقیمانده به جز انتهای مرتب سازی وجود دارد. بنابراین احتمال رخداد دادن چنین ترتیبی (وقتی همهی ترتیبها دارای احتمال مساوی میباشند) برابر است با . در نتیجه سهم ، سهم مرزی مورد انتظار تحت الحاق بازیکنان با ترتیب تصادفی به منظور تشکیل ائتلاف بزرگ است. برای محاسبهی مقدار شپلی از معادلهی (۳-۵) استفاده میشود اگرچه برای بازیها با تعداد بازیکنان زیاد، پیچیدگی محاسباتی به شدت افزایش مییابد[۳۶]. جدول ۳-۱ مثالی از راهکار تخصیص شپلی را نمایش میدهد. در این مثال عددی سه حزب A، B و C میتوانند برای تولید یک درآمد قابل اندازهگیری با هم همکاری کنند. هر حزب به تنهایی میتواند ۴ واحد درآمد تولید کند و درآمد حاصل از ائتلافهای ممکنِ احزاب با یکدیگر در ستون سمت چپ آورده شده است. ابتدا سهم مرزی هر حزب محاسبه شده است، سهم مرزی بازیکن برابر است با تفاضل درآمد ائتلاف از درآمد همان ائتلاف بدون حضور بازیکن . سپس با بهره گرفتن از سهمهای مرزی هر بازیکن، مقدار شپلی آن محاسبه میشود. این مقدار برای بازیکن i برابر است با میانگین سهمهای مرزی بازیکن در ائتلافها با سایزهای مختلف.
جدول ۳-۱- مثالی از راهکار تخصیص شپلی [۳۷]
ائتلافها | درامد(ارزش) ائتلاف | سهم مرزی A | سهم مرزی B | سهم مرزی C |
A | ۴ | ۴ | ۰ | ۰ |
B | ۴ | ۰ | ۴ | ۰ |
C | ۴ | ۰ | ۰ | ۴ |
A,B |
فرم در حال بارگذاری ...
[یکشنبه 1400-08-02] [ 06:02:00 ق.ظ ]
|