راهنمای نگارش پایان نامه و مقاله درباره ارائه روشی جدید جهت بهبود بازدهی تخصیص پهنای باند پویا در ... |
![]() |
بدیهی است تخصیصی که بتواند تضمین کند تمام بی عدالتیها(نارضایتیها) کمینه میشوند، راهکار جالبی است و همان انگیزهی اصلی راهکار هستک است. تصورکنید O(x) بردار تمامی بی عدالتیها (به جز بی عدالتی ائتلاف یزرگ)با ترتیبی غیر صعودی برای بازی ائتلافی باشد. گفته میشود بردار به طور الفبایی[۱۴۲] از بردار کمتر است، (y z) اگر کهy1=z1,y2=z2,…,yl-1=zl-1 , .تخصیص x یک تخصیص هستک است اگر برای هر تخصیص دیگر ?، داشته باشیم O(?) O(x). بنابراین راهکار هستک، تخصیص x است که بی عدالتیها را با ترتیبی غیر صعودی کمینه میکند. راهکار هستک برای یک بازی ائتلافی موجود و منحصر به فرد است. این راهکار به طور انفرادی و گروهی است و اصول ساختگی و تقارن در راهکار شپلی را تامین میکند. مهمترین اشکال این راهکار، پیچیدگی محاسباتی آن در برخی بازیهاست. فرایند محاسبهی هستک، بدین ترتیب شروع میشود که ابتدا تخصیصی را پیدا میکنیم که ارزش ائتلاف بزرگ را به گونهای توزیع کند که بیشترین بی عدالتی(نارضایتی) را کمینه کند. در این شرایط وقتی این کمینه سازی یک راهحل منحصر به فرد دارد، این راهحل هستک است. در غیر این صورت به دنبال تخصیصی میگردیم که دومین بزرگترین بی عدالتی را کمینه کند. این فرایند برای تمام بی عدالتیهای بعدی ادامه مییابد تا به یک تخصیص منحصر به فرد که همان هستک است، دست یابیم[۳۹]. برای مثال چگونه یک میزان دارایی باید میان طلبکارانی با مقادیر موردتقاضای ۱۰۰، ۲۰۰ و ۳۰۰ تقسیم شود؟
Aumann و Maschler الگوریتمی در [۴۰] برای راهکار هستک در دستهه ای خاصی از بازیهای همکارانه با بازیکن که در مسئلهی ورشکستگی[۱۴۳] به وجود میآیند، ارائه دادهاند.
۱- طلبها را از کمترین مقدار به بیشترین مقدار مرتب میکنیم.
۲- دارایی را به طور مساوی میان تمام طلبکاران تقسیم میکنیم تا زمانی که طلبکار با کمترین مقدار طلب، نصف تقاضای خود را دریافت نماید.
۳- دارایی باقیمانده را میان طلبکاران به جز طلبکاری که کمترین مقدار را طلب داشته، به طور مساوی تقسیم میکنیم تا زمانی که طلبکاری که دومین کمترین مقدار طلب را داشته به نصف مقدار مورد تقاضای خود دست یابد.
۴- به این روند ادامه میدهیم تا زمانی که به هر طلبکار نصف تقاضای اصلی، سهم تعلق بگیرد.
۵- در جهت برعکس حرکت میکنیم، به طلبکاری که بیشترین طلب را داشته، از دارایی سهم میدهیم تا خسارت آن برابر میزان خسارت طلبکاری شود که دومین بیشترین تقاضا را دارد. منظور از خسارت، تفاضل سهم تخصیص یافته از میزان طلب اولیه است.
۶- دارایی باقیمانده را میان طلبکارانی که بیشترین طلب را دارند به طور مساوی تقسیم میکنیم تا زمانی که خسارت هر طلبکار با بیشترین مقدار طلب برابر خسارت طلبکار بعدی با بیشترین مقدار طلب شود. جدول ۳-۲ مقادیر تخصیص یافته به هر یک از متقاضیان را با مقادیر متفاوت دارایی نمایش میدهد.
جدول ۳-۲- مثالی از روش تخصیص هستک [۴۱]
تقاضا | |||
مقادیر متفاوت دارایی | ۳۰۰ | ۲۰۰ | ۱۰۰ |
۵۰ | ۱۶٫۶۶ | ۱۶٫۶۶ | ۱۶٫۶۶ |
۱۰۰ | ۳۳٫۳۳ | ۳۳٫۳۳ | ۳۳٫۳۳ |
۱۵۰ | ۵۰ | ۵۰ | ۵۰ |
۲۰۰ | ۷۵ | ۷۵ | ۵۰ |
۲۵۰ |
فرم در حال بارگذاری ...
[چهارشنبه 1400-08-05] [ 01:23:00 ق.ظ ]
|