نظریه بازی تعاونی

توسط علی رضا نقش نیلچی | یکشنبه یکم تیر ۱۳۹۹ | 16:15

مفاهیم راه حل [ ویرایش ]

فرض اصلی در تئوری بازی تعاونی این است که ائتلاف بزرگ $ن$ شکل خواهد گرفت [14] پس از آن چالش تخصیص بازپرداخت است $v (N)$ در بین بازیکنان به طریقی منصفانه. (این فرض است که محدود است، چرا که حتی اگر بازیکنان تقسیم کردن و به شکل ائتلاف کوچکتر، ما می توانیم مفاهیم راه حلی برای subgames تعریف شده توسط اعمال هر ائتلاف در واقع تشکیل می دهد.) یک مفهوم راه حل یک بردار است $x \ in \ mathbb {R}} ^ {N}$ که نشان دهنده اختصاص به هر بازیکن است. محققان مفاهیم راه حل مختلف را بر اساس عقاید مختلف انصاف پیشنهاد کرده اند. برخی از خواص برای جستجوی مفهوم راه حل عبارتند از:

بهره وری: وکتور بازپرداخت دقیقاً مقدار کل را تقسیم می کند: $\ sum _ {{i \ in N}} x_ {i} = v (N)$ .
عقلانیت فردی: هیچ بازیکنی کمتر از آنچه ممکن است به تنهایی دریافت کند دریافت نمی کند: $x_ {i} \ geq v (\ {i \})، \ forall ~ i \ in N$ .
وجود: مفهوم راه حل برای هر بازی وجود دارد $v$ .
منحصر به فرد بودن: مفهوم راه حل برای هر بازی بی نظیر است $v$ .
حاشیه بودن: بازپرداخت یک بازیکن فقط به سهم حاشیه ای این بازیکن بستگی دارد ، یعنی اگر این سهم حاشیه ای در دو بازی مختلف یکسان باشد ، بازپرداخت یکسان است: $\ displaystyle v (S \ cup \ {i \}) = w (S \ cup \ {i \})، \ forall S \ subseteq N \ setminus \ {i \}}$ دلالت دارد $x_ {من}$ همان است که در $v$ و در $W$ .
یکنواختی: در صورت افزایش سهم حاشیه ای این بازیکن ، بازپرداخت یک بازیکن افزایش می یابد: $\ displaystyle v (S \ cup \ {i \}) \ leq w (S \ cup \ {i \})، \ forall ~ S \ subseteq N \ setminus \ {i \}}$ دلالت دارد $x_ {من}$ از نظر ضعیف بیشتر است $W$ از در $v$ .
سهولت محاسباتی: مفهوم راه حل می تواند به صورت کارآمد محاسبه شود (یعنی در زمان چند جمله ای با توجه به تعداد بازیکنان $| ن |$ .)
تقارن: مفهوم راه حل $ایکس$ پرداختهای برابر را اختصاص می دهد $x_i = x_j$ به بازیکنان متقارن $ج$ . دو بازیکن $ج$ متقارن هستند اگر $v (S \ cup \ {i \}) = v (S \ cup \ {j \}) ، \ forall ~ S \ subseteq N \ setminus \ {i، j \$ ؛ یعنی ما در هر ائتلافی که فقط یکی از بازیکنان را در اختیار داشته باشد می توانیم یک بازیکن را برای دیگری مبادله کنیم و بازپرداخت را تغییر ندهیم.
افزودنی: اختصاص به بازیکن در مجموع دو بازی ، مبلغ اختصاصی به بازیکن در هر بازی اختصاصی است. از نظر ریاضی ، اگر $v$ و $\ امگا$ بازی ها هستند ، بازی $(v + \ امگا)$ مبلغ پرداختی را که ائتلاف در دو بازی انفرادی دریافت می کند ، به هر ائتلاف اختصاص می دهد. یک مفهوم راه حل افزودنی به هر بازیکن موجود در آن اختصاص می یابد $(v + \ امگا)$ مبلغ آنچه او دریافت می کند $v$ و $\ امگا$ .
صفر تخصیص به بازیکنان تهی: اختصاص به یک بازیکن تهی صفر است. یک بازیکن تهی $من$ ارضا می کند $v (S \ cup \ {i \}) = v (S) ، \ forall ~ S \ subseteq N \ setminus \ {i \$ . از نظر اقتصادی ، ارزش نهایی یک بازیکن تهی برای هر ائتلافی که او را در اختیار ندارد صفر است.

بردار بازده کارآمد است که به نام از پیش نسبت دادن ، و عقلانی پیش نسبت دادن یک نام نسبت دادن . اکثر مفاهیم راه حل ، ضربه ها هستند.

مجموعه پایدار [ ویرایش ]

مجموعه پایدار یک بازی (همچنین به عنوان راه حل von Neumann-Morgenstern شناخته می شود ( فون نویمان و مورگنسترن 1944 )) اولین راه حل پیشنهادی برای بازی هایی با بیش از 2 بازیکن بود. اجازه دهید $v$ یک بازی باشید و بگذارید $ایکس$ ، $ی$ شود دو imputations از $v$ . سپس $ایکس$ تسلط دارد $ی$ اگر برخی ائتلاف $S \ neq \ vacetset$ ارضا می کند $x_ {i}> y_ {i} ، \ forall ~ i \ in S$ و $\ sum _ {{i \ in S}} x_ {i} \ leq v (S)$ . به عبارت دیگر ، بازیکنان در $س$ بازپرداختها را ترجیح می دهید $ایکس$ به کسانی که از $ی$ ، و در صورت تهدید می توانند ائتلاف بزرگ را ترک کنند $ی$ استفاده می شود زیرا بازپرداختی که به دست می آورند به خودی خود حداقل به اندازه تخصیصی که در زیر دریافت می کنند است $ایکس$ .

مجموعه ای پایدار مجموعه ای از است imputations که ارضا دو ویژگی:

پایداری داخلی: هیچ بردار بازپرداخت در مجموعه پایدار توسط یک بردار دیگر در مجموعه حاکم است.
پایداری خارجی: تمام بردارهای بازپرداخت خارج از مجموعه ، حداقل یک بردار در مجموعه حاکم است.

فون نویمان و مورگنسترن مجموعه پایدار را مجموعه ای از رفتارهای قابل قبول در یک جامعه می دانند: هیچکدام به وضوح نسبت به دیگران ارجح نیستند ، اما برای هر رفتار غیرقابل قبول یک جایگزین ارجح است. تعریف بسیار کلی است که اجازه می دهد تا از مفهوم در طیف گسترده ای از قالب های بازی استفاده شود.

خواص [ ویرایش ]

یک مجموعه پایدار ممکن است وجود داشته باشد یا نباشد ( لوکاس 1969 ) ، و اگر وجود داشته باشد ، معمولاً بی نظیر نیست ( لوکاس 1992 ). پیدا کردن مجموعه های پایدار معمولاً دشوار است. این و سایر مشکلات منجر به توسعه بسیاری از مفاهیم راه حل دیگر شده است.
بخش مثبت بازی های تعاونی دارای مجموعه های پایدار و منحصر به فردی هستند که از هسته تشکیل شده اند ( اوون 1995 ، ص 240).
بخش مثبت بازی های تعاونی دارای مجموعه های پایدار و تبعیض آمیز است $n-2$ بازیکنان حداقل در چنین مجموعه هایی $n-3$ از بازیکنان تبعیض آمیز حذف شده است ( اوون 1995 ، ص 240).

هسته [ ویرایش ]

مقاله اصلی: هسته (اقتصاد)

اجازه دهید $v$ یک بازی باشید هسته از $v$ مجموعه ای از بردارهای بازپرداخت است

$\ displaystyle C (v) = \ left \ {x \ in \ mathbb {R} ^ {N}: \ sum _ {i \ in N} x_ {i} = v (N)؛ \ quad \ sum _ i \ in S} x_ {i} \ geq v (S)، \ forall ~ S \ subseteq N \ Right \}.}$

به عبارت ، هسته اصلی مجموعه تعلقات است که تحت آن هیچ ائتلاف ارزش بیشتری از مبلغ پرداختی اعضای خود ندارد. بنابراین ، هیچ ائتلاف انگیزه ای برای ترک ائتلاف بزرگ و دریافت بازپرداخت بزرگتر ندارد.

خواص [ ویرایش ]

هسته از یک بازی ممکن است خالی (را ببینید قضیه بونداروا-شپلی ). بازی هایی با هسته های غیر خالی متعادل نامیده می شوند .
اگر خالی باشد ، هسته لزوماً حاوی یک بردار منحصر به فرد نیست.
هسته است که در هر مجموعه ای پایدار موجود است، و اگر هسته پایدار است آن را مجموعه ای پایدار منحصر به فرد است. برای اثبات به ( دریسسن 1988 ) مراجعه کنید.

هسته اصلی یک بازی ساده با توجه به ترجیحات [ ویرایش ]

برای بازی های ساده ، تصور دیگری از هسته وجود دارد ، هنگامی که فرض می شود هر بازیکن نسبت به یک مجموعه ترجیح دارد $ایکس$ از گزینه های دیگر. یک پروفایل یک لیست است $p = (\ succ_i ^ p) _ {i \ in N$ ترجیحات شخصی $\ succ_i ^ پ$ بر $ایکس$ . اینجا $x \ succ_i ^ py$ یعنی اون فرد $من$ جایگزین را ترجیح می دهد $ایکس$ به $ی$ در پروفایل $پ$ . با توجه به یک بازی ساده $v$ و یک پروفایل $پ$ ، یک رابطه غالب است $\ succ _ {v} ^ {p$ در تعریف شده است $ایکس$ توسط \ displaystyle x \ succ _ {v} ^ {p} y} $x \ succ _ {v} ^ {p} y$ اگر و تنها اگر ائتلاف برنده وجود دارد $س$ (یعنی ، $v (S) = 1$ ) رضایت بخش $x \ succ_i ^ py$ برای همه $من در S$ . هسته $C (v ، p)$ از بازی ساده $v$ با توجه به مشخصات $پ$ تنظیمات ترجیحی مجموعه گزینه های جایگزین نشده است $\ succ _ {v} ^ {p$ (مجموعه عناصر حداکثر $ایکس$ با توجه به $\ succ _ {v} ^ {p$ ):

$x \ در C (v ، p)$ اگر و فقط اگر وجود ندارد $y \ in X$ به طوری که $y \ succ _ {v} ^ {p} x$ .

تعداد ناکامورا از یک بازی ساده تعداد حداقل ائتلاف های برنده با تقاطع خالی است. قضیه ناکامورا بیان می کند که هسته $C (v ، p)$ برای همه پروفایل ها خالی است $پ$ از بدون دور (معادل آن، متعدی تنظیمات) اگر و تنها اگر $ایکس$ متناهی و تعداد کاردینال (تعداد عناصر) از آن است $ایکس$ کمتر از تعداد ناکامورا است $v$ . گونه ای از کومبه و میهارا می گوید هسته اصلی $C (v ، p)$ برای همه پروفایل ها خالی است $پ$ از موارد برگزیده که حداکثر عنصر حداکثر را دارند و اگر فقط تعداد کاردینال باشد $ایکس$ کمتر از تعداد ناکامورا است $v$ . ( برای جزئیات بیشتر به شماره ناکامورا مراجعه کنید .)

هسته قوی اپسیلون [ ویرایش ]

از آنجا که هسته ممکن است خالی باشد ، کلیاتی در آن وارد شد ( Shapley & Shubik 1966 ). قوی $\ varepsilon$ نمره برای برخی از شماره $\ varepsilon \ in \ mathbb {R}$ مجموعه ای از بردارهای بازپرداخت است

$C _ {\ varepsilon} (v) = \ left \ {x \ in {\ mathbb {R}} ^ {N}: \ sum _ {{i \ in N}} x_ {i} = v (N)؛ \ quad \ sum _ {{i \ in S}} x_ {i} \ geq v (S) - \ varepsilon، \ forall S \ subseteq N \ Right \.$

از نظر اقتصادی ، قوی $\ varepsilon$ - امتیاز مجموعه ای از پیش تعویض هاست که هیچ ائتلاف نمی تواند با ترک ائتلاف بزرگ ، بازپرداخت خود را بهبود بخشد ، در صورت نیاز به پرداخت مجازات $\ varepsilon$ برای ترک توجه داشته باشید که $\ varepsilon$ ممکن است منفی باشد ، در این صورت این یک امتیاز برای خروج از ائتلاف بزرگ است. واضح است که فارغ از اینکه هسته خالی باشد ، قوی است $\ varepsilon$ -نمره برای مقدار کافی بزرگ غیر خالی خواهد بود $\ varepsilon$ و برای مقدار کم به اندازه کافی (احتمالاً منفی) خالی باشد $\ varepsilon$ . به دنبال این استدلال ، کمترین هسته ای که در ( Maschler ، Peleg & Shapley 1979 ) وارد شده است ، تقاطع همه افراد غیر خالی است. $\ varepsilon$ -cores. همچنین می توان آن را قوی دانست $\ varepsilon$ نمره برای کوچکترین مقدار $\ varepsilon$ که این مجموعه را خالی می کند ( بیلبائو 2000 ).

مقدار Shapley [ ویرایش ]

مقاله اصلی: مقدار شاپلی

ارزش شپلی بردار بازده منحصر به فرد است که کارآمد، متقارن و ارضا یکنواختی است. [15] توسط لوید شپلی ( شپلی 1953 ) معرفی شد که نشان داد این وکتور برآورد منحصر به فرد است که کارآمد ، متقارن ، افزودنی است و بازپرداخت صفر را به بازیکنان ساختگی اختصاص می دهد. ارزش Shapley از یک بازی فوق العاده منحصر به فرد منطقی است ، اما این به طور کلی صحیح نیست. ( درسن 1988 )

هسته [ ویرایش ]

اجازه دهید $v: 2 ^ {N} \ به {\ mathbb {R}}$ یک بازی ، و اجازه دهید $x \ in \ mathbb {R}} ^ {N}$ یک بردار بازده کارآمد باشد. حداکثر مازاد از بازیکن من بیش از بازیکن J با توجه به X است

$s _ {{ij}} ^ {v} (x) = \ max \ left \ {v (S) - \ sum _ {{k \ in S}} x_ {k}: S \ subseteq N \ setminus \ {j \} ، من \ در S \ درست \ ،$

بازیکن مقدار حداکثر من می توانید بدون همکاری بازیکن به دست آوردن J با خروج از ائتلاف بزرگ N تحت بازده بردار X ، فرض کنید که بازیکنان دیگر در من " خروج ائتلاف بازدید کنندگان با بازده خود را تحت راضی X . حداکثر مازاد روشی برای اندازه گیری قدرت چانه زنی یک بازیکن نسبت به دیگری است. هسته از $v$ مجموعه ای از imputations x است که راضی کننده است

$(s _ {{ij}} ^ {v} (x) -s _ {{ji}} ^ {v} (x)) \ بار (x_ {j} -v (j)) \ leq 0$ و
$(s _ {{ji}} ^ {v} (x) -s _ {{ij}} ^ {v} (x)) \ بار (x_ {i} -v (i)) \ leq 0$

برای هر جفت بازیکن من و ج . به طور مستقیم ، بازیکن i از قدرت چانه زنی بیشتری نسبت به بازیکن j در رابطه با imputation x در صورت وجود استفاده می کند $s _ {{ij}} ^ {v} (x)> s _ {{ji}} ^ {v} (x)$ اما اگر بازیکن j از تهدیدات بازیکن من مصون باشد ، اگر $x_ {j} = v (j)$ زیرا او می تواند این بازپرداخت را به تنهایی بدست آورد. هسته شامل همه تعلقات است که هیچ بازیکنی این قدرت چانه زنی را نسبت به دیگری ندارد. این مفهوم راه حل برای اولین بار در ( دیویس و ماسلر 1965 ) معرفی شد.

هسته [ ویرایش ]

اجازه دهید $v: 2 ^ {N} \ به {\ mathbb {R}}$ یک بازی ، و اجازه دهید $x \ in \ mathbb {R}} ^ {N}$ یک وکتور بازپرداخت باشید. بیش از $ایکس$ برای ائتلاف $S \ subseteq N$ کمیت است $v (S) - \ sum _ {{i \ in S}} x_ {i$ ؛ این همان سود است که بازیکنان ائتلاف می کنند $س$ در صورت انصراف از ائتلاف بزرگ ، می توانند بدست آورند $ن$ تحت بازپرداخت $ایکس$ و در عوض پاداش را بگیرید $در مقابل)$ .

حالا بگذار $\ theta (x) \ in \ mathbb {R}} ^ {{2 ^ {N}}}$ بردار زیاده خواهی ها باشد $ایکس$ ، ترتیب به ترتیب غیر فزاینده به عبارت دیگر، $\ theta _ {i} (x) \ geq \ theta _ {j} (x)، \ forall ~ i <j$ . توجه کنید که $ایکس$ در هسته از $v$ اگر و فقط اگر پیش از مجازات باشد و $\ theta _ {1} (x) \ leq 0$ . برای تعریف هسته ، ترتیب واژگونی بردارها را در نظر می گیریم $\ mathbb {R}} ^ {{2 ^ {N}}}$ : برای دو بردار بازپرداخت $x ، y$ ، ما میگوییم $\مالیات)$ از نظر لغوی کوچکتر از است $\ تتا (y)$ اگر برای برخی از فهرست $ک$ ، ما داریم i $\ تتا _ {i} (x) = \ تتا _ {i} (y) ، \ forall ~ i <k$ و $\ theta _ {k} (x) <\ theta _ {k} (y)$ . (ترتیب است به فرهنگ نویسی نامیده می شود زیرا آن را تقلید ترتیب الفبایی استفاده به ترتیب کلمات در یک فرهنگ لغت است.) هستک از $v$ براساس این ترتیب ، مجازات حداقل واژگان از نظر لغوی است . این مفهوم راه حل برای اولین بار در ( Schmeidler 1969 ) معرفی شد.

اگرچه تعریف هسته به نظر انتزاعی است ، ( Maschler، Peleg & Shapley 1979 ) توضیحی شهودی تر داد: با شروع با کمترین هسته ، ائتلاف هایی را که سمت راست نابرابری در آن تعریف می شود ، ثبت کنید $C _ {\ varepsilon (v)$ بدون خالی کردن مجموعه نمی تواند بیشتر کاهش یابد. ادامه حرکت سمت راست برای ائتلاف های باقی مانده ، تا زمانی که بدون خالی کردن مجموعه ، کاهش نمی یابد. مجموعه جدید ائتلاف هایی را که نابرابریها برابری در آن برگزار می کنند ، ضبط کنید. به کاهش سمت راست ائتلاف های باقیمانده ادامه دهید و این روند را هر چند بار که لازم باشد تکرار کنید تا اینکه تمام ائتلاف ها ثبت نشده اند. بردار بازپرداخت حاصل هسته است.

خواص [ ویرایش ]

اگرچه تعریف صریحاً آن را بیان نمی کند ، هسته هسته همیشه بی نظیر است. ( برای اثبات به بخش II.7 از (درسسن 1988 ) مراجعه کنید.)
اگر هسته غیر خالی باشد هسته در هسته است.
هسته‌ی هسته همیشه در هسته است و از آنجایی که این هسته در مجموعه معامله قرار دارد ، همیشه در مجموعه معاملات است ( برای جزئیات بیشتر به (نگاه کنید به ( درایسن 1988 )).

منبع

https://en.wikipedia.org/wiki/Cooperative_game_theory

مشخصات وب

در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.
09132003030

ریاضیات

آموزش ریاضی