بازی های تعاونی محدب [ ویرایش ]
معرفی شده توسط شپلی در ( شپلی 1971 ) ، بازی های تعاونی محدب خاصیت بصری را تصرف می کنند که برخی از بازی ها دارای "گلوله برفی" هستند. به طور خاص ، اگر عملکرد مشخصه آن باشد ، یک بازی محدب است
می توان نشان (نگاه کنید به عنوان مثال، بخش V.1 از ( Driessen 1988 )) که supermodularity از
یعنی "مشوقها برای پیوستن به ائتلاف با بزرگ شدن ائتلاف افزایش می یابد" ( شپلی 1971 ) ، که منجر به اثر فوق الذکر گلوله برفی شد. برای بازی های با هزینه ، نابرابری ها برعکس می شوند ، به طوری که می گوییم اگر عملکرد مشخصه فرعی باشد ، هزینه بازی محدب است .
خواص [ ویرایش ]
بازی های تعاونی محدب خواص بسیار خوبی دارند:
- Supermodularity بدیهی دلالت superadditivity .
- بازی های محدب کاملاً متعادل است : هسته اصلی یک بازی محدب خالی نیست و از آنجایی که هر زیر بازی یک بازی محدب محدب است ، هسته اصلی هر بازی فرعی نیز خالی است.
- یک بازی محدب دارای یک مجموعه پایدار و منحصر به فرد است که همزمان با هسته آن است .
- ارزش شپلی از یک بازی محدب مرکز ثقل آن است هسته .
- با استفاده از الگوریتم حریص : یک نقطه شدید (راس) هسته را می توان در زمان چند جمله ای یافت : اجازه دهی
یک جایگشت از بازیکنان، و اجازه دهید
مجموعه ای از بازیکنان سفارش داده شده باشد
از طریق
که در
، برای هرچی
، با
. سپس بازپرداخت
تعریف شده توسط
راس از است هسته از
شباهت ها و تفاوت ها با بهینه سازی ترکیبی [ ویرایش ]
Submodular و supermodular توابع مجموعه نیز در مورد مطالعه بهینه سازی ترکیبی . بسیاری از نتایج در ( Shapley 1971 ) دارای آنالوگ در ( Edmonds 1970 ) ، که در آن توابع submodular برای اولین بار به عنوان تعمیم ماتروید ارائه شد . در این زمینه ، هسته اصلی یک بازی هزینه محدب ، پایه چندضلعی نامیده می شود ، زیرا عناصر آن خواص پایه ماتروئیدها را تعمیم می دهند .
با این حال ، جامعه بهینه سازی به طور کلی توابع submodular را آنالوگ های مجزا از توابع محدب می داند ( Lovász 1983 ) ، زیرا به حداقل رساندن هر دو نوع توابع قابل محاسبه قابل تراکم است. متأسفانه ، این به طور مستقیم با تعریف اصلی شپلی از توابع فوق العاده به عنوان "محدب" در تضاد است .
در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.