الگوریتمی چندجمله‌ای برای محاسبهٔ تعادل کامل در بازی‌های گستردهٔ دونفره

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

در تعریف مقاله از «کامل‌بودن»، هر کنش در یک مجموعهٔ اطلاعاتی نسبت به کنش بهتر جریمه می‌شود، درحالی‌که دیگر انتخاب‌های رفتاری محلی بازیکن، از جمله کنش‌های آیندهٔ خود او، ثابت می‌مانند. الگوریتم برای هر مجموعهٔ اطلاعاتی یک permutahedron هندسی از احتمال‌های مجاز کنش‌ها در نظر می‌گیرد و با نمایش مقیاس‌یافتهٔ دو‌استوکاستیک، این محدودیت‌ها را در یک چندوجهیِ sequence-form با اندازهٔ چندجمله‌ای جای می‌دهد. نقطهٔ زینی حاصل، نامساوی‌های محلی ε-properness را برآورده می‌کند.

برای رسیدن به تعادل دقیق، نه صرفاً راه‌حلی با اغتشاش عددی دلخواه‌کوچک، نویسندگان پایداری علامت یک دستگاه خطی پارامتری را اثبات می‌کنند، یک پایهٔ شدنیِ پایدار می‌سازند و حد نسبت‌های رفتاری را استخراج می‌کنند. احتمال‌های نهایی گویا هستند و طول کدگذاری چندجمله‌ای دارند؛ این ویژگی، به‌گفتهٔ چکیده، حتی در مجموعه‌های اطلاعاتی با احتمال تحقق صفر نیز برقرار است.