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

تعریف ریاضی [ ویرایش ]

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

برعکس ، یک بازی تعاونی نیز می تواند با یک تابع هزینه مشخصه تعریف شود $c: 2 ^ {N} \ به {\ mathbb {R}}$ رضایت بخش $c (\ vacyset) = 0$ . در این تنظیم ، بازیکنان باید وظیفه و عملکرد مشخصی را انجام دهند $ج$ نشان دهنده هزینه مجموعه ای از بازیکنان است که با هم وظیفه را انجام می دهند. یک بازی از این نوع به عنوان یک بازی هزینه شناخته می شود . اگرچه بیشتر تئوری بازی تعاونی مربوط به بازی های سود است ، اما همه مفاهیم را می توان به راحتی به تنظیم هزینه ترجمه کرد.

سود سهام هرسانی [ ویرایش ]

هارسانی سود سهام (به نام بعد از جان هارسانی ، کسی که آن را تعمیم دهند ارزش شپلی در سال 1963 [5] ) شناسایی مازاد است که توسط ائتلافی از بازیکن در یک بازی تعاونی ایجاد شده است. برای مشخص کردن این مازاد ، ارزش این ائتلاف با مازادی که از قبل توسط زیرمجموعه‌ها ایجاد شده ، اصلاح می شود. برای این منظور ، سود سهام ${\ displaystyle d_ {v} (S)$ از ائتلاف $س$ در بازی $v$ به صورت بازگشتی توسط

${\ displaystyle {\ آغاز {تراز شده} d_ {v} (\ {i \}) & = v (\ {i \}) \\ d_ {v} (\ {i، j \}) & = v (\ {i، j \}) - d_ {v} (\ {i \}) - d_ {v} (\ {j \}) \\ d_ {v} (\ {i، j، k \}) & = v (\ {i، j، k \}) - d_ {v} (\ {i، j \}) - d_ {v} (\ {i، k \}) - d_ {x} (\ {j، k \}) - d_ {v} (\ {i \}) - d_ {v} (\ {j \}) - d_ {v} (\ {k \}) \\ & \ vdots \\ d_ {v } (S) & = v (S) - \ sum _ {T \ subsetneq S} d_ {v} (T) \ end {تراز شده}}$

فرمول صریح برای سود سهام توسط داده شده است $\ textstyle d_ {v} (S) = \ sum _ {T \ subsetneq S} (- 1) ^ {| S \ setminus T |} v (T)$ . کارکرد $\ displaystyle d_ {v}: 2 ^ {N} \ به \ mathbb {R}$ همچنین به عنوان شناخته شده معکوس موبیوس از\ $\ displaystyle v: 2 ^ {N} \ to \ mathbb {R}$ . [6] در واقع ، ما می توانیم بهبود یابیم $v$ از جانب $d_ {v$ با کمک فرمول $\ textstyle v (S) = d_ {v} (S) + \ sum _ {T \ subseteq S} d_ {v} (T)$ .

سود سهام هرسانی برای تجزیه و تحلیل هر دو بازی و مفاهیم راه حل مفید است ، به عنوان مثال با توزیع سود سهام هر ائتلاف بین اعضای خود ، ارزش Shapley بدست می آید ، یعنی ارزش $\ phi _ {i} (v)$ بازیکن $من$ در بازی $v$ با جمع کردن سهم یک بازیکن از سود سهام همه ائتلاف های متعلق به او ، $\ textstyle \ phi _ {i} (v) = \ sum _ {S \ زیرمجموعه N: i \ in S} {d_ {v} (S) / {| S |}$ .

دوگانگی [ ویرایش ]

اجازه دهید $v$ یک بازی سودمند باشید بازی دوگانه از $v$ بازی هزینه است $v ^ {*}$ که تعریف میشود

$\ displaystyle v ^ {*} (S) = v (N) -v (N \ setminus S) ، \ forall S \ subseteq N.$

به طور شهودی ، بازی دوگانه هزینه فرصت برای ائتلاف را نشان می دهد $س$ از پیوستن به ائتلاف بزرگ نیست $ن$ . یک بازی سود دوگانه $c ^ {*$ برای یک بازی هزینه می تواند به صورت یکسان تعریف شود $ج$ . یک بازی همکاری و دوتایی آن به نوعی معادل آن است و بسیاری از خواص آنها را به اشتراک می گذارد. برای مثال هسته اصلی یک بازی و دوتایی آن برابر است. برای اطلاعات بیشتر در مورد دوگانگی بازی های تعاونی ، به عنوان مثال مراجعه کنید ( Bilbao 2000 ).

زیرمجموعه ها [ ویرایش ]

اجازه دهید $S \ subsetneq N$ یک ائتلاف خالی از بازیکنان باشید. نام فرعی $v_ {S}: 2 ^ {S} \ to {\ mathbb {R}}$ بر $س$ به طور طبیعی به عنوان تعریف می شود

${\ displaystyle v_ {S} (T) = v (T) ، \ forall T \ subseteq S.$

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

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

سوپرادتی [ ویرایش ]

توابع مشخصه غالباً فرض برانگیز است ( اوون 1995 ، ص 213). این بدان معنی است که ارزش اتحادیه ائتلافهای جداگانه از مجموع ارزشهای جداگانه ائتلافها کمتر نیست:

$v (S \ cup T) \ geq v (S) + v (T)$ هر زمان که $S ، T \ subseteq N$ راضی کردن $S \ cap T = \ blanketet$ .

یکنواختی [ ویرایش ]

ائتلاف های بزرگتر بیشتر کسب می کنند:

$S \ subseteq T \ Rightarrow v (S) \ leq v (T)$ .

این ناشی از ابرقدرت است . یعنی اگر بازپرداخت ها عادی شده باشند ، بنابراین ائتلاف های تک قلو دارای ارزش صفر هستند.

ویژگی های بازی های ساده [ ویرایش ]

بازی ائتلافی V در نظر گرفته شده ساده اگر پاداش را 0 یا 1، ائتلاف یعنی هم "برنده" و یا "از دست دادن". [7]

به طور برابر ، یک بازی ساده را می توان به عنوان مجموعه W ائتلاف ها تعریف کرد ، جایی که اعضای W به عنوان ائتلاف برنده شناخته می شوند ، و بقیه ائتلاف ها را از دست می دهند . بعضی اوقات فرض بر این است که یک بازی ساده بدون حرکتی است یا شامل یک مجموعه خالی نیست. با این حال ، در سایر زمینه های ریاضیات ، بازی های ساده ای نیز به نام هایپرگراف یا توابع بولی (توابع منطقی) گفته می شوند.

یک بازی ساده W است یکنواخت در صورت هر گونه ائتلاف حاوی یک ائتلاف برنده است، برنده، این است که، اگر $S \ در W$ و $S \ subseteq T$ دلالت $T \ در W$ .
یک بازی ساده W است مناسب اگر مکمل (مخالفان) از هر ائتلاف برنده از دست دادن است، این است که، اگر $S \ در W$ دلالت دارد $N \ setminus S \ notin W$ .
یک بازی ساده W است قوی اگر مکمل هر ائتلاف از دست دادن برنده است، این است که، اگر دلالت دارد .
- اگر یک بازی W مناسب و صحیح و مناسب باشد ، در صورت پیروزی اگر مکمل آن از دست می رود ، ائتلافی پیروز می شود ، $S \ در W$ اگر $N \ setminus S \ notin W$ . (اگر v یک بازی ساده colional است که مناسب و قدرتمند است ، $v (S) = 1-v (N \ setminus S)$ برای هر S. )
بازیکن حق وتو (vetoer) در یک بازی ساده یک بازیکن است که متعلق به همه ائتلاف برنده است. به فرض اینکه بازیکن وتو وجود داشته باشد ، هر ائتلافی که حاوی بازیکن وتو نباشد ، ضرر می کند. یک بازی ساده W است ضعیف ( دانشگاهی ) اگر آن را تا یک بازیکن حق وتو، این است که اگر در تقاطع از همه ائتلاف های برنده غیر منتخب است.
- یک دیکتاتور در یک بازی ساده یک بازیکن حق وتو دارد به گونه ای که هر ائتلاف حاوی این بازیکن برنده می شود. دیکتاتور متعلق به هیچ ائتلاف بازنده نیست. ( بازی های دیکتاتور در اقتصاد آزمایشی با این ارتباط ندارند.)
حامل از یک بازی ساده W مجموعه ای است $T \ subseteq N$ به گونه ای که برای هر ائتلاف S داریم $S \ در W$ اگر $S \ cap T \ در W$ . وقتی یک بازی ساده دارای حامل باشد ، هر بازیکنی که متعلق به آن نباشد نادیده گرفته نمی شود. اگر یک حامل محدود (حتی اگر N نامتناهی باشد) یک بازی ساده گاهی محدود نامیده می شود .
تعداد ناکامورا از یک بازی ساده حداقل تعداد است برنده ائتلاف با تقاطع خالی است. طبق قضیه ناکامورا ، این عدد میزان عقلانیت را اندازه می گیرد. این یک شاخص از میزان حکم یک قانون تجمیع می تواند گزینه های مناسبی را ارائه دهد.

چند رابطه در بین بدیهیات فوق بطور گسترده شناخته شده است ، مانند موارد زیر (به عنوان مثال ، پله ، 2002 ، بخش 2.1 [8] ):

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

به طور کلی ، یک تحقیق کامل در مورد رابطه بین چهار بدیهی متعارف (یکنواختی ، قدرت ، استحکام و عدم ضعف) ، ظرافت و محاسبه الگوریتمی [9] انجام شده است (کومبه و میهارا ، 2011 [10] ) که نتایج در جدول "وجود بازیهای ساده" در زیر خلاصه شده است.

+ نوشته شده در سه شنبه سوم تیر ۱۳۹۹ ساعت 0:40 توسط علی رضا نقش نیلچی |

ریاضیات

آموزش ریاضی