شکل گسترده بازی

در نظریه بازی‌ها، شکل گسترده، توصیفی از یک بازی است. ویژگی‌های مهم این توصیف عبارتند از: ترتیب دهی حرکت‌های ممکن بازیکنان، تصمیمات آن‌ها در هر نقطهٔ تصمیم، اطلاعات (شاید اطلاعات ناکامل) هر بازیکن دربارهٔ حرکت‌های بازیکن دیگر در هنگام تصمیم و دستاوردهای بازیکن برای همهٔ پیامدهای ممکن بازی. شکل گسترده همچنین اجازه می‌دهد که اطلاعات ناکامل در قالب اتفاقات شانسی (احتمالی) ارائه شود که توسط طبیعت صورت می‌گیرد.

شکل گستردهٔ بازی‌های محدود

یک بازی به شکل گسترده از موارد زیر تشکیل شده‌است:

۱. مجموعه‌ای محدود از n بازیکن (عقلایی)

۲. درختی ریشه دار به نام درخت بازی

۳. هر گره (برگ) انتهایی درخت بازی، یک دستاورد n تایی دارد یعنی برای هر بازیکن در انتهای هر بازی ممکنی یک دستاورد وجود دارد.

۴. بخشی از گره‌های غیر انتهایی درخت بازی در n+1 زیر مجموعه، یک زیر مجموعه برای هر بازیکن (عقلایی) و با زیر مجموعهٔ ویژه‌ای برای بازیکن ساختگی به نام احتمال (یا طبیعت). زیر مجموعهٔ گره‌های هر بازیکن به عنوان «گره‌های بازیکن» معرفی می‌شود (بنابراین یک بازی با اطلاعات کامل، مجموعهٔ تهی از گره‌های احتمال دارد).

۵. هر گرهٔ بازیکن احتمال (طبیعت) یک توزیع احتمال روی خروجی‌های خود دارد.

۶. هر مجموعه‌ای از گره‌های یک بازیکن عقلایی بیشتر در مجموعه‌های اطلاعات افراز می‌شود که انتخاب‌های معین غیرقابل تشخیصی را برای بازیکن هنگام حرکت به وجود می‌آورد از این جهت که:

  • یک رابطهٔ یک به یک بین شاخه‌های خروجی هر دو گرهٔ موجود در یک مجموعه ی اطلاعاتی وجود دارد – بنابراین مجموعهٔ همهٔ شاخه‌های خروجی یک مجموعهٔ اطلاعاتی در گروه‌های هم‌ارزی افراز می‌شوند که هر گروه ارائه دهندهٔ یک انتخاب ممکن برای حرکت یک بازیکن در همان نقطهٔ بازی است.
  • و هر مسیر (جهت دار) در درخت بازی از سمت ریشه به سمت گره انتهایی حداکثر می‌تواند یک بار از هر مجموعهٔ اطلاعاتی بگذرد.

۷. شرح کامل بازی تعریف شده توسط پارامترهای فوق، دانش مشترک میان بازیکنان است (یعنی همهٔ بازیکنان از آن مطلع اند).

بنابراین یک بازی، مسیری است از ریشه به سمت گره انتهایی در یک درخت بازی. در هر گره غیر انتهایی معین که متعلق به شانس (احتمال) است، یک شاخهٔ خروجی بر اساس توزیع احتمال انتخاب می‌شود. در هر گرهٔ بازیکن عقلایی، بازیکن باید یکی از گروه‌های هم ارز را انتخاب کند که دقیقاً شاخهٔ خروجی را مشخص می‌کند جز آنکه (در حالت کلی) بازیکن نمی‌داند به دنبال کدام یک است. (یک ناظر بیرونی با دانستن انتخاب‌های هر بازیکن دیگری در آن نقطه و تحقق حرکت‌های بازیکن طبیعت، می‌تواند به‌طور دقیق شاخه را مشخص کند). یک استراتژی محض برای بازیکن شامل یک انتخاب است (با انتخاب دقیق یک گروه هم ارز از شاخه‌های خروجی برای هر مجموعهٔ اطلاعاتی خودش).

در بازی با اطلاعات کامل، مجموعه‌های اطلاعاتی یگانه و تک هستند (یعنی فقط شامل یک گره‌اند). در بازی‌هایی با گره‌های شانسی (احتمالی) این موضوع که چگونه باید دستاوردها تفسیر شوند، نمود کمتری می‌یابد. این گونه فرض می‌شود که هر بازیکن یک تابع مطلوبیت ون نیومن مورگنسترن (به انگلیسی Von Neumann – Morgenstern utility) دارد که برای هر پیامد بازی تعریف شده‌است. این فرض شامل این است که هر بازیکن عقلایی یک نتیجهٔ تصادفی پیشین را بر اساس مطلوبیت انتظاری خود تعیین می‌کند. ارائهٔ بالا در حالی که به‌طور دقیق ساختار ریاضی را در بازی‌ها تعریف می‌کند اما از بحث فنی بیشتر در مورد این که چگونه بازی در حالتی که بازیکن نمی‌تواند بین گره‌ها در یک مجموعهٔ اطلاعاتی تمایز قایل شود، اجتناب می‌کند.

اطلاعات کامل و تمام

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

۱ بازیکنان یک بازی

۲ هر بازیکن در هر حرکت خود چه فرصت‌هایی برای حرکت دارد

۳ آنچه که هر بازیکن برای هر حرکت خود می‌داند

۴ دستاوردهای دریافتی توسط هر بازیکن برای هر ترکیب ممکنی از حرکت‌ها

بازی ترسیم شده در زیر دو بازیکن دارد: ۱ و ۲. اعداد هر گره غیر انتهایی نشان می‌دهد که آن گره تصمیم متعلق به کدام بازیکن است (یعنی نوبت حرکت کدام بازیکن است). اعداد در گره انتهایی، دستاوردها برای بازیکنان را به نمایش می‌گذارد. (مثلاً ۲ و ۱ نشانگر دستاورد ۲ برای بازیکن ۱ و دستاورد ۱ برای بازیکن ۲ است). برچسب متعلق به هر خروجی، نام اقدامی است که آن خروجی نشان می‌دهد. گره ابتدایی متعلق به بازیکن ۱ است که نشانگر آن است که بازیکن ۱ در ابتدا حرکت می‌کند. بازی طبق درخت بازی این گونه ادامه می‌یابد: بازیکن ۱ بین U و D انتخاب می‌کند، سپس بازیکن ۲ با مشاهدهٔ انتخاب بازیکن ۱ بین ’U و ’D اقدام به انتخاب می‌کند. دستاوردها در درخت بازی تعریف شده‌اند. ۴ پیامد توسط ۴ گره انتهایی درخت نمایندگی می‌شوند: (’D,D)، (’D,U)، (’U,D)و(’U,U). دستاوردهای مرتبط با هر نتیجه به ترتیب به صورت روبروست: (۳و۱)، (۲و۱)، (۱و۲)و(۰و۰). اگر بازیکن ۱، Dبازی کند، بازیکن ۲ برای حداکثر کردن دستاورد خود ’U را برمی‌گزیند بنابراین بازیکن ۱، تنها ۱ واحد دریافت می‌کند. گرچه اگر بازیکن ۱، U بازی کند، بازیکن ۲ برای حداکثر کردن دستاورد خود ’D را برمی‌گزیند و بازیکن ۱، ۲ واحد دریافت می‌کند؛ بنابراین چون بازیکن ۱، ۲ را به ۱ ترجیح می‌دهد، بازیکن 1 U بازی کرده و بازیکن ۲ ’D بازی خواهد کرد. این تعادل زیر بازی کامل است.

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

اطلاعات ناکامل

یک مزیت ارائهٔ بازی به شکل گسترده آن است که ترتیب بازی روشن و واضح است. درخت بازی به روشنی نشان می‌دهد که در ابتدا بازیکن ۱ حرکت می‌کند و بازیکن ۲ این حرکت را مشاهده می‌کند. گرچه در برخی بازی‌ها، بازی این گونه رخ نمی‌دهد. بازیکن همیشه انتخاب بازیکن دیگر را مشاهده نمی‌کند (برای مثال، حرکت‌ها ممکن است همزمان باشند یا ممکن است حرکتی آشکار نشود).

یک مجموعهٔ اطلاعاتی، مجموعه‌ای از گره‌های تصمیم است طوری که:

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

در شکل گسترده بازی، مجموعهٔ اطلاعاتی توسط یک خط چین که همهٔ گره‌ها در آن مجموعه را به هم وصل می‌کند یا گاهی توسط یک حلقه که به دور تمامی گره‌های آن مجموعه کشیده می‌شود، مشخص می‌گردد. اگر یک بازی دارای مجموعهٔ اطلاعاتی با بیش از یک گره باشد، آنگاه به آن، بازی با اطلاعات ناکامل گفته می‌شود. یک بازی با اطلاعات کامل طوری است که در هر مرحلهٔ بازی، هر بازیکن دقیقاً آنچه را که قبلاً اتفاق افتاده است را می‌داند. یعنی هر مجموعهٔ اطلاعاتی، یک عضوی (دارای تنها یک گره) است. هر بازی بدون اطلاعات کامل، یک بازی با اطلاعات ناکامل است.

بازی ترسیم شده در زیر همان بازی قسمت قبل است جز آنکه بازیکن ۲ آنچه که بازیکن ۱ در شروع بازی انجام داده است را نمی‌داند. این بازی با اطلاعات ناکامل است. اگر هر دو بازیکن عقلایی باشند و هر دو بدانند که هر دو عقلایی اند و بازیکنان نسبت به آنچه که بازیکن دیگر می‌داند آگاهی داشته باشد (یعنی بازیکن ۱ می‌داند که بازیکن ۲ می‌داند که بازیکن ۱ عقلایی است و بازیکن ۲ هم این موضوع را می‌داند و به همین ترتیب تا آخر ادامه پیدا می‌کند) بازی قبلی به صورت زیر خواهد بود: بازیکن ۱ می‌داند که اگر او U بازی کند، بازیکن ۲ ’D بازی خواهد کرد (زیرا برای بازیکن ۲، دستاورد ۱ به دستاورد صفر ترجیح دارد) و بنابراین بازیکن ۱، ۲ واحد دریافت می‌کند. حال اگر بازیکن 1 D بازی کند، بازیکن ۲ ’U بازی می‌کند (زیرا برای او دستاورد ۲ به دستاورد ۱ ترجیح دارد) و بنابراین بازیکن ۱، ۱ واحد دریافت می‌کند؛ بنابراین در بازی اول، تعادل (’U,D) خواهد بود زیرا بازیکن ۱، دستاورد ۲ واحدی را به دستاورد ۱ واحدی ترجیح می‌دهد و در نهایت بازیکن ۱، U و بازیکن ۲، ’D بازی می‌کند.

در بازی دوم این موضوع وضوح کمتری دارد. بازیکن ۲ نمی‌تواند حرکت بازیکن ۱ را مشاهده کند. بازیکن ۱ دوست دارد که بازیکن ۲ را فریب دهد بطوری که بازیکن ۲ تصور کند که بازیکن 1 U بازی کرده است در حالی که واقعاً او D بازی کرده است بنابراین بازیکن ۲ ’D بازی می‌کند و بازیکن ۱، ۳ واحد دریافت می‌کند. در حقیقت، در بازی دوم، یک تعادل بازی کامل وجود دارد طوری که بازیکن ۱، D بازی می‌کند و بازیکن ۲ ’U بازی می‌کند و بازیکن ۲ باور دارد که بازیکن ۱ قطعاً D بازی می‌کند. در این تعادل هر استراتژی با توجه به باورها عقلایی است و هر باور با استراتژی که بازی انجام می‌شود سازگار است. توجه کنید که چگونه ناکامل بودن اطلاعات، پیامد بازی را تغییر می‌دهد.

نمایش گستردهٔ یک بازی با اطلاعات ناکامل

اطلاعات ناتمام

مواردی وجود دارد که بازیکن از دستاوردهای بازی به طور دقیق اطلاع ندارد یا نوع رقیب خود را نمی‌داند. این نوع بازی دارای اطلاعات ناتمام است. در شکل گسترده این بازی را به عنوان بازی تمام با اطلاعات ناکامل با استفاده از آنچه تبدیل جان هارسانی (به انگلیسی John Harsanyi) نامیده می‌شود، ارائه می‌دهند. این تبدیل مفهوم «انتخاب طبیعت» یا «انتخاب خدا» را به بازی می‌آورد. یک بازی متشکل از یک کارفرما را در نظر بگیرید که به دنبال استخدام فرد جویای کار است. توانایی فرد جویای کار می‌تواند یکی از دو مورد زیر باشد: بالا یا پایین. سطح توانایی این فرد تصادفی است. او با احتمال ۳/۱ توانایی پایین و با احتمال ۳/۲ توانایی بالا دارد. در این مورد مناسب است تا طبیعت را به عنوان بازیکن دیگری وارد مدل کنیم که توانایی فرد جویای کار را طبق احتمالات موجود انتخاب می‌کند. گرچه برای طبیعت هیچ گونه دستاوردی مد نظر نیست . انتخاب طبیعت در درخت بازی توسط یک گره خالی نمایش داده می‌شود.

بازی نمایش داده شده در زیر یکی از بازی‌های تمام (همهٔ بازیکنان و دستاوردها برای همه مشخص است) اما با اطلاعات ناکامل (کارفرما از انتخاب طبیعت اطلاعی ندارد) است. گره ابتدایی توخالی است، بنابراین طبیعت در ابتدا حرکت می‌کند. طبیعت با همان احتمال نوع باریکن ۱، حرکت اول را انجام می‌دهد t1 یا تی t2. بازیکن ۱، مجموعه‌های اطلاعاتی متمایزی دارد یعنی بازیکن ۱، نوع خود را می‌داند. با این حال بازیکن ۲ انتخاب طبیعت را مشاهده نمی‌کند. بازیکن ۲، نوع بازیکن ۱ را نمی‌داند. با این حال بازیکن ۲، اقدامات بازیکن ۱ را مشاهده می‌کند یعنی اطلاعات کامل وجود دارد. در واقع اکنون فرصت مناسبی است تا تعریف بالا از اطلاعات تمام را تغییر دهیم: در هر مرحله از بازی، هر بازیکن آنچه توسط بازیکنان دیگر انجام شده‌است را می‌داند. در مورد اطلاعات خصوصی، هر بازیکن آنچه توسط طبیعت صورت گرفته‌است را می‌داند. مجموعه‌های اطلاعات همانند قبل با خطوط خط چین نمایش داده می‌شوند. در این بازی اگر طبیعت t1 را به عنوان نوع بازیکن ۱ انتخاب کند، بازی شبیه بازی که در ابتدا توصیف شد، خواهد بود جز آنکه بازیکن ۲ اطلاعی از نوع بازیکن ۱ ندارد. یک تعادل بیزی کامل جداگانه (به انگلیسی seperating) وجود دارد یعنی تعادلی که در آن انواع مختلف بازیکنان، اقدامات متفاوتی انتخاب می‌کنند. اگر هر دو نوع بازیکن، یک اقدام انتخاب کنند (تعادل درهم (به انگلیسی (pooling)) تعادل نمی‌تواند ایجاد شود.

نمایش گستردهٔ یک بازی تمام با اطلاعات ناکامل

مقایسهٔ شکل گسترده و بهنجار بازی
  • شکل بهنجار برخلاف شکل گسترده، به خودی خود دارای تصویر (شکل) نیست و بازی را از طریق یک ماتریس ارائه می‌کند.
  • شکل بهنجار بازی در تعریف استراتژی‌های (اکیداً) مغلوب، نسبت به شکل گسترده، کاربردی تر است و غالباً در درک این مفهوم اهمیت دارد.
  • شکل بهنجار تنها بازی‌هایی را نمایش می‌دهد که انتخاب‌ها در آن‌ها همزمان (یا به‌طور کلی اطلاعات ناکامل) باشند. از این رو عموماً در

نمایش بازی‌های ترتیبی از شکل گسترده استفاده می‌شود.

جستارهای وابسته

منابع

    Andreu Mass-Collel, Michael D.whinstone and jerry R.green .(1995).Game theory. Oxford university press. ISBN 0-19-507340-1

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.