پیش‌نویس:بازی تصادفی

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

بازی‌های تصادفی فرآیندهای تصمیم مارکوف را به تصمیم‌گیرندگان چندگانه و همچنین بازی‌های استراتژیک را به موقعیت‌های پویا تعمیم می‌دهند که در آن محیط در پاسخ به انتخاب‌های بازیکنان تغییر می‌کند.

بازی های دو نفره

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

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

ما مفاهیم اولیه و سوالات الگوریتمی مورد مطالعه در این زمینه را معرفی کردیم و برخی از مسائل دیرینه در این زمینه را ذکر می کنیم. سپس، نتایج منتخب اخیر را ذکر می کنیم.

تئوری

اجزای یک بازی تصادفی عبارتند از: مجموعه محدودی از بازیکنان $I$ ; یک فضای حالت $M$ (یا یک مجموعه محدود یا یک فضای قابل اندازه گیری $(M,{\mathcal {A}})$ برای هر بازیکن $i\in I$ ، یک مجموعه عمل $S^{i}$ (یا یک مجموعه محدود یا یک فضای قابل اندازه گیری $(S^{i},{\mathcal {S}}^{i})$ ) یک احتمال انتقال $P$ از $M\times S$ ، جایی که $S=\times _{i\in I}S^{i}$ نشانه اکشن یا عمل به $M$ است، ، جایی که $P(A\mid m,s)$ احتمال اینکه حالت بعدی در A $A$ باشد با توجه به وضعیت فعلی $m$ و عمل فعلی $s$ است; و یک تابع پرداخت $g$ از $M\times S$ به $R^{I}$ ، جایی که $i$ -مین مختصات $g$ ، $g^{i}$ ، پاداش بازیکن $i$ است به عنوان تابعی از حالت $m$ و اکشن یا عمل $s$ .

بازی در برخی از حالت های اولیه $m_{1}$ شروع می شود . در مرحله $t$ ، بازیکنان ابتدا $m_{t}$$m_{t}$$m_{t}$$m_{t}$ را مشاهده می کنند ، سپس به طور همزمان $s_{t}^{i}\in S^{i}$$s_{t}^{i}\in S^{i}$$s_{t}^{i}\in S^{i}$ را انتخاب میکند، سپس عمل را مشاهده $s_{t}=(s_{t}^{i})_{i}$ میکند، و سپس به طور طبیعی $m_{t+1}$ را با توجه به احتمال $P(\cdot \mid m_{t},s_{t})$ انتخاب می کند . نمایشی از بازی تصادفی، $m_{1},s_{1},\ldots ,m_{t},s_{t},\ldots$ ، که دنباله ای از پاداش $g_{1},g_{2},\ldots$ ،را تعریف می کند جایی که $g_{t}=g(m_{t},s_{t})$ .

بازی با تخفیف $\Gamma _{\lambda }$ با فاکتور تخفیف $\lambda$

( $0<\lambda \leq 1$ ) بازی است که در آن پاداش به بازیکن $i$ ، $\lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}$ است . بازی $n$ مرحله ای بازی است که در آن پاداش بازیکن $i$ ،${\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}$ است .

ارزش $v_{n}(m_{1})$ ، به ترتیب $v_{\lambda }(m_{1})$ ، یک بازی تصادفی دو نفره با جمع صفر $\Gamma _{n}$ ، به ترتیب $\Gamma _{\lambda }$ ، با حالت ها و اکشن های بسیار زیادی وجود دارد و ترومن بیولی و الون کولبرگ (1976) ثابت کردند که $v_{n}(m_{1})$ به حدی همگرا می شود $n$ تا بی نهایت می رود و آن $v_{\lambda }(m_{1})$ به همان حد همگرا می شود از $\lambda$ تا $0$ .

بازی "بدون تخفیف". $\Gamma _{\infty }$ بازی است که در آن پاداش به بازیکن $i$، "حد" میانگین های پاداش های حالات است. برخی از اقدامات احتیاطی در تعریف ارزش یک مجموع صفر دو نفره $\Gamma _{\infty }$$\Gamma _{\infty }$ مورد نیاز است و در تعریف پاداش های های تعادلی حاصل جمع غیر صفر $\Gamma _{\infty }$ . مقدار یکنواخت $v_{\infty }$ یک بازی تصادفی دو نفره با جمع صفر $\Gamma _{\infty }$ وجود دارد اگر برای هر $\varepsilon >0$ یک عدد صحیح مثبت $N$وجود دارد و یک جفت استراتژی $\sigma _{\varepsilon }$ از بازیکن 1 و $\tau _{\varepsilon }$ از بازیکن 2 به طوری که برای هر $\sigma$ و $\tau$ و هر $n\geq N$ امید از ${\bar {g}}_{n}^{i}$ با توجه به احتمال در نمایشنامه تعریف شده توسط $\sigma _{\varepsilon }$ و $\tau$ حداقل است $v_{\infty }-\varepsilon$ ، و انتظار از ${\bar {g}}_{n}^{i}$ با توجه به احتمال در بازی تعریف شده توسط $\sigma$ و $\tau _{\varepsilon }$ حداکثر $v_{\infty }+\varepsilon$ است . ژان فرانسوا مرتنز و آبراهام نیمن (1981) ثابت کردند که هر بازی تصادفی دو نفره با مجموع صفر با تعداد محدودی از حالت ها و عمل ها دارای ارزش یکنواخت است.

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

بازی تصادفی با جمع غیر صفر $\Gamma _{\infty }$ پاداش تعادلی یکنواخت$v_{\infty }$ دارد اگر برای هر $\varepsilon >0$ یک عدد صحیح مثبت$N$ Nوجود داشته باشد،و یک استراتژی $\sigma$ به طوری که برای هر انحراف یک طرفه توسط یک بازیکن $i$ به عنوان مثال، یک استراتژی $\tau$ با $\sigma ^{j}=\tau ^{j}$ برای همه $j\neq i$ ، و هر $n\geq N$ امید از ${\bar {g}}_{n}^{i}$ با توجه به احتمال در بازی تعریف شده توسط $\sigma$ حداقل$v_{\infty }^{i}-\varepsilon$$v_{\infty }^{i}-\varepsilon$$v_{\infty }^{i}-\varepsilon$$v_{\infty }^{i}-\varepsilon$ است ، و امید از ${\bar {g}}_{n}^{i}$ با توجه به احتمال در بازی تعریف شده توسط $\tau$ حداکثر$v_{\infty }^{i}+\varepsilon$$v_{\infty }^{i}+\varepsilon$ است . Nicolas Vieille نشان داده است که تمام بازی‌های تصادفی دو نفره با فضاهای حالت محدود و عمل دارای یک بازده تعادلی یکنواخت هستند.

بازی تصادفی با جمع غیر صفر $\Gamma _{\infty }$ دارای بازده تعادلی محدود کننده$v_{\infty }$ است اگر برای هر $\varepsilon >0$ یک استراتژی$\sigma$ وجود داشته باشد به طوری که برای هر انحراف یک طرفه توسط یک بازیکن $i$ ، امید حد پایین تر از میانگین حالت های پاداش با توجه به احتمال بازی های تعریف شده توسط $\sigma$ حداقل$v_{\infty }^{i}-\varepsilon$ $v_{\infty }^{i}-\varepsilon$ است ، و امید حد بالاتر از میانگین حالت های پاداش با توجه به احتمال بازی های تعریف شده توسط $\tau$ حداکثر$v_{\infty }^{i}+\varepsilon$$v_{\infty }^{i}+\varepsilon$ است . Jean-François Mertens وAbraham Neyman (1981) ثابت کردند که هر بازی تصادفی دو نفره با مجموع صفر با حالت ها و اکشن های محدود دارای مقدار میانگین محدود کننده است، و نیکلاس ویله نشان داده است که همه بازی های تصادفی دو نفره با فضاهای حالت محدود و عمل دارای پاداش تعادلی محدودکننده هستند. به طور خاص، این نتایج حاکی از آن است که این بازی ها دارای یک ارزش و یک بازده تعادل تقریبی هستند که به آن بازده تعادل حد فاصل (به ترتیب، میانگین لنگر) نامیده می شود، زمانی که بازده کل حد پایین تر (یا حد برتر) از حد میانگین بازده حالات باشد.

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

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

بازی های تصادفی با بازی های بیزی ترکیب شده اند تا عدم اطمینان در مورد استراتژی های بازیکن را مدل سازی کنند. نتیجه مدل "بازی بیزی تصادفی" از طریق یک ترکیب بازگشتی از معادله تعادل بیزی نش و معادله بهینگی بلمن حل می شود .

برنامه های کاربردی

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

همچنین ببینید

• روند تصادفی

 

خواندن بیشتر

•  Neyman, A. & Sorin, S. (2003). Stochastic Games and Applications. Dordrecht: Kluwer Academic Press. ISBN 1-4020-1492-9.Filar, J. & Vrieze, K. (1997). Competitive Markov Decision Processes. Springer-Verlag. ISBN 0-387-94805-8.Yoav Shoham; Kevin Leyton-Brown (2009). Multiagent systems: algorithmic, game-theoretic, and logical foundations. Cambridge University Press. pp. 153–156. ISBN 978-0-521-89943-7.

لینک های خارجی

• سخنرانی درباره بازی های دو نفره تصادفی توسط آنتونین کوچرا