استنتاج معکوس

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

استنتاج معکوس اولین بار توسط بنیان‌گذاران نظریه بازی‌ها، جان فون نیومن و اسکار مورگنشترن در سال ۱۹۹۶ به کار برده شد.

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

روند اجرای استنتاج معکوس

روند استنتاج معکوس به صورت تجزیه و تحلیل یک بازی از آخرین مرحله به ابتدای آن است و در هر مرحله استراتژی که مغلوب است، حذف می‌شود و استراتژی برنده در گام بعدی بازی تحلیل می‌شود. در واقع در هر مرحله فرض می‌شود، هر بازیکن با انتخاب عقلانی استراتژی که سود بیشتری دارد را انتخاب می‌کند. برای مثال شکل فرم گسترده بازی دونفره زیر را در نظر بگیرید:

شکل اول

بازی از سه مرحله تشکیل شده و در مرحله اول، بازیکن اول بین دو استراتژی X و W باید یکی را انتخاب کند، در مرحله دوم بازیکن دوم با انتخاب در دو راس ۲ و ۳ مواجه است که در راس دوم دو استراتژی C و D و در راس سوم دو استراتژی A , B را دارد. در صورتی که بازیکن اول در مرحله اول W و بازیکن دوم در مرحله دوم C را انتخاب کند، بازیکن اول در مرحله سوم حق انتخاب بین دو استراتژی Y و Z را دارد. سود هر بازیکن در رأس‌های نهایی درخت ذکر شده‌است که اولین عدد (عدد سمت راست) سود بازیکن اول و دومین عدد، سود نفر دوم است.

برای به دست آوردن تعادل نش زیربازی کامل در این بازی، که تعادلی است که هر بازیکن بهترین پاسخ را در هر مرحله به اقدام حریف انجام می‌دهد، از این استنتاج به این صورت استفاده می‌کنیم که از آخرین راس (راس با ارتفاع بیشتر از ریشه) شروع می‌کنیم. بازیکن اول در این مرحله با انتخاب استراتژی Y، سود ۴ و با دیگری ۱ را می‌برد. پس با انتخاب عقلانی، استراتژی اول را انتخاب می‌کند و استراتژی Z مغلوب این استراتژی است. پس بازی به شکل زیر کاهش پیدا می‌کند.

شکل دوم

در نتیجه استراتژی پروفایل (۴٬۲) به استراتژی‌های نفر دوم در راس ۳ اضافه می‌شود. در مرحله دوم، بازیکن دوم در دو راس باید تصمیم گیرد، در راس دوم، بیشترین سود این بازیکن انتخاب B است و در راس اول C. پس دو استراتژی دیگر متناظرا مغلوب این دو استراتژی می‌شوند. پس شکل کاهش یافته سوم به دست‌می‌آید.

شکل سوم

در این مرحله بازیکن اول، بین دو استراتژی که استراتژی پروفایل هرکدام با فرض انتخاب عقلانی در گام‌های قبلی به دست آمده، حق انتخاب دارد و با انتخاب استراتژی که بیشترین سود را می‌برد، یعنی استراتژی W برای بازیکن اول خاتمه می‌باید و بازیکن اول با استنتاج به این نتیجه می‌رسد که بهترین انتخابی که در این مرحله با استفاده از بهترین نتایج که در مراحل قبلی برای هر بازیکن به دست آمده‌است، انتخاب W است.

گام‌های اجرای استنتاج معکوس

هدف ما داشتن مقادیر نتیجه (سود یا ضرر) احتمالی برای هر بازیکن در هر راس می‌باشد، در ابتدا به هیچ راس میانی مقداری اختصاص نیافته و برگ‌های درخت (راس‌های نهایی) نیز دارای مقدار نتیجه برای تمام بازیکنان (استراتژی پروفایل) هستند. گام‌های زیر را انجام می‌دهیم:

1. راسی که مقداری ندارد و تمام رأس‌های فرزند و تابع‌اش در درخت مقدار گرفته‌اند، را انتخاب می‌کنیم و V می‌نامیم. (در هر مرحله حتماً همچنین راسی وجود دارد)
2. بازیکن متناظر این راس برای مثال بازیکن شماره n می‌باشد. از بین رأس‌های فرزند این راس، که مقدار نتیجه (سود یا ضرر) بازیکنان به آن اختصاص یافته، راسی که بیشترین سود را برای بازیکن n دارد را می‌یابیم.
3. مقدار نتیجه تخصیص داده شده به این راس را مقدار نتیجه راس V قرار می‌دهیم. (در واقع بازیکن n این استراتژی متناظر راس با بیشترین سود برای خود را انتخاب می‌کند)
4. در صورتی که راس V، راس ریشه درخت می‌باشد بازی تمام شده و این مقدار تخصیص داده شده به V، تعادل کامل زیر بازی می‌باشد و در غیر اینصورت دوباره به ترتیب گام‌های بالا را انجام می‌دهیم.

محدودیت‌های استفاده از این روش

استفاده از این روش برای برخی بازی‌ها کاربرد ندارد. در برخی نتیجه درست نمی‌دهد و در برخی نمی‌توان آن را اعمال کرد.

بازی‌های نامتناهی

این روش استنتاج تنها برای بازی‌های محدود و متنهایی کاربرد دارد. یک بازی پویا (ترتیبی)، محدود است، اگر درخت بازی آن که شکل فرم گسترده بازی است، تعداد راس محدودی داشته باشد.

برای مثال این بازی را در نظر بگیرید:

بازی ترتیبی بین دو بازیکن داریم که در هر مرحله یک بازیکن ۱ یا ۲ انگشت را بالا می‌آورد. یک بازیکن می‌بازد در صورتی که به تعدادی که بازیکن دیگر در مرحله قبل بالا آورده، انگشت بالا بیاورد. نتیجه نهایی ۱- برای بازیکن بازنده و ۱ برای بازیکن برنده است. این بازی با جمع صفر با درنظرگیری انتخاب عقلانی در هر مرحله، هیچگاه به انتها نمی‌رسد، پس در درخت فرم گسترده آن، تعداد نامتناهی مرحله و راس خواهیم داشت. پس متناهی نیست و نمی‌توانیم از این استنتاج استفاده کنیم.

بازی‌های تکراری

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

طبق استنتاج معکوس، بازیکن دوم هر طوری‌که بازیکن اول تقسیم کند و برای او بیشتر از ۱ واحد پول در نظر بگیرد را قبول می‌کند (چون سودش از صفر که از رد کردن تقسیم‌بندی به دست می‌آید، بیشتر است) بازیکن اول نیز برای به دست آوردن بیشترین سود، از بین انتخاب ۰ تا k - 1، مسلماً k - 1 را انتخاب می‌کند. در حالی که با اجرای ۹۹ بار این بازی، حالت تعادل تقسیم‌بندی به صورت k/2, k/2 است.

بازی‌هایی که تعداد حالات برد زیادی دارند

همچنین در بازی‌هایی مثل شطرنج یا چکرز که تعداد حالت نهایی برد فراوانی دارد، استفاده از این روش کارایی ندارد و تنها در صورتی که یک حالت نهایی و ممکن برای برد وجود داشته باشد، کارایی دارد.

مثال‌هایی از کاربرد استنتاج معکوس

از استنتاج معکوس در حل بسیاری از مسائل که به بازی قابل مدل کردن هستند، می‌توان استفاده کرد.

کاربردی در سیاست

در سال ۱۹۶۲، اتحادیه جماهیر شوروی تصمیم گرفت که موشک‌های هسته‌ای خود را در کوبا قرار دهید، رئیس‌جمهور وقت ایالت متحده آمریکا، جان اف کندی در برابر این اقدام، سه اقدام می‌توانست انجام دهد. ۱- عملی انجام ندهد. ۲- به صورت هوایی به موشک‌ها حمله کند. ۳- یا کوبا را محاصره دریایی کند. کندی سومین اقدام را انتخاب کرد. خروشچف در برابر اقدام آمریکا، تهدید به تشدید وضعیت کرد ولی در نهایت شوروی راضی به خارج کردن موشک‌ها از کوبا شد و آمریکا نیز کوبا را از محاصره خارج کرد. مدل شده این بازی به صورت شکل مقابل است:

مثالی برای کاربرد استنتاج معکوس در سیاست

با استفاده از استنتاج بازگشتی، در مرحله آخر در انتخاب شوروی، شوروی با موافقت با خروج موشک‌ها نسبت به تشدید آن‌ها سود بیشتری می‌برد، پس موافقت می‌کند. در مرحله دوم و در نیز آمریکا از بین سودهای انتخابی این مرحله که برای حمله هوایی ۴، برای محاصره دریا ۵ و بدون اقدام، ۲ است، محاصره دریا را انتخاب می‌کند و در مرحله اول، نیز شوروی اقدام قرار دادن موشک‌ها در کوبا را که بیشترین سودش در آن است، را انتخاب می‌کند.

کاربردی در نظریه بازی‌ها

بازی دونفره‌ای را در نظر بگیرید که با شمارش اعدادی از ۱ تا ۵۰ هر بازیکن که مجاز به گفتن عدد ۵۰ بود و آن را گفت، برنده است. منوال بازی به این صورت است که برای شروع نفر اول یک عدد بین ۱ تا ۱۰ می‌گوید مثلاً a، بازیکن دوم نیز باید عدد بین a تا a + 10 بگوید. سپس نفر اول نیز عددی بین ۱۰ عدد پس از عدد انتخابی بازیکن قبلی انتخاب می‌کند، تا یکی ۵۰ بگوید. در این بازی اگر بازیکن شروع‌کننده، با کمک استنتاج معکوس، بازی را تحلیل کند، برنده بازی می‌تواند باشد.

اگر بازیکن اول با تحلیل اینکه باید بازیکن دوم را ملزم به انتخاب عددی بین ۴۰ تا ۴۹ کند، چرا که با انتخاب هر یک از این اعداد، در دور بعدی می‌تواند ۵۰ را بگوید، عدد ۳۹ را باید انتخاب کند. برای انتخاب عدد ۳۹، باید بازیکن دوم را مجبور کند عددی بین ۲۹ تا ۳۸ را انتخاب کند، تا دور بعدی مجاز به انتخاب ۳۹ شود. برای مجبور کردن بازیکن دوم به این کار، باید ۲۸ را انتخاب کند. باز هم به صورت بازگشتی در دور قبلی باید بازیکن دوم عددی از ۱۸ تا ۲۷ انتخاب کند، برای الزام بازیکن دوم باید ۱۷ را انتخاب کند و برای انتخاب ۱۷، باید نفر دوم عددی بین ۷ تا ۶ را انتخاب کند، که برای این کار بازیکن اول در دور اول بازی ۶ را انتخاب می‌کند.

پس بازیکن اول با انتخاب به ترتیب ۶، ۱۷، ۲۸، ۳۹ و ۵۰ در هر مرحله بازی قادر به بردن این بازی است.

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

• بهینه‌سازی در ریاضیات
• استقرا یا استدلال استقرائی
• بازی‌های پویا
• تعادل نش زیربازی کامل