تعادل کامل لغزش دست

**تعادل کامل لغزش دست** یک پالایشی از تعادل نش است که توسط راینهارد سیلتن ریاضی‌دان و اقتصاد دان برجسته آلمانی مطرح شد. تعادل کامل لغزش دست، تعادلی است که در آن برای کاربر (هرچند با احتمال ناچیز) این امکان را در نظر می‌گیرد که استراتژی‌های ناخواسته انتخاب کند. به عبارتی دیگر این احتمال برای بازکنان موجود است که استراتژی‌های ناخواسته داشته باشد. [پیوند=[پرونده:Reinhard Selten2.jpg|بندانگشتی|راینهارد سیلتن ریاضیدان و اقتصاددان مطرح آلمانی]]

## تعریف
در ابتدا به سراغ تعریف مجموعه استراتژی می‌رویم.

### مجموعه استراتژی و استراتژی مختلط
مجموعه استراتژی یک بازیکن تعیین می‌کند که برای این بازیکن، بازی کردن کدام استراتژی‌ها ممکن است. اگر برای یک بازیکن تعدادی استراتژی گسسته وجود داشته باشد، مجموعه استراتژی این بازیکن متناهی است. به عنوان نمونه در بازی سنگ، کاغذ، قیچی، هر بازیکن مجموعه استراتژی متناهی {سنگ، کاغذ، قیچی} را دارد. در غیر این صورت یک مجموعه استراتژی نامتناهی است. به عنوان مثال، در یک مزایده که میزان افزایش قیمت طبق یک قانون است، استراتژی‌ها گسسته هستند و مجموعه استراتژی نامتناهی است {۱۰ هزار تومان، ۲۰ هزار تومان، ۳۰ هزار تومان و…}. همچنین، بازی بریدن کیک دارای استراتژی‌های کراندار و پیوسته در مجموعه استراتژی‌ها است {بریدن هر جا بین ۰٪ تا ۱۰۰٪ از کیک}.

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

البته می‌توان یک استراتژی خالص را نوع خاصی از استراتژی مختلط دانست که در آن یک استراتژی خالص خاص با احتمال ۱ و بقیه استراتژی‌ها با احتمال ۰ انتخاب می‌شوند.

یک **استراتژی کاملاً مختلط**، استراتژی مختلطی است که در آن بازیکن یک احتمال اکیداً مثبت به هر استراتژی خالص می‌دهد. به عبارتی دقیق تر فرض کنید Gیک بازی متناهی است و \sigma _ {i}\in\Sigma _ {i}یک استراتژی کاملاً مختلط است اگر برای هر i عدد \sigma _ {i}(s _ {i})>0.

### تعادل نش چیست؟
به صورت بسیار خلاصه و مفهومی می‌توان گفت تعادل نش به حالت پایداری در یک بازی گفته می‌شود که با فرض ثابت بودن راهبرد سایر بازیکنان، یک بازیکن با تغییر بازی خود نتواند به شرایط بهتری دست یابد. با استفاده از مفاهیم نظریه بازی‌ها می‌توان این موضوع را به صورت رسمی بیان و مدل کرد. مجموعه (S,F) را به عنوان بازی با  n  بازیکن در نظر بگیرید، که در آن S_i مجموعه استراتژی‌ها برای بازیکن  i  است،  S=S_1*S_2... *S_n  مجموعه‌ای از فضای استراتژی آن است و F(x) تابع بهره‌مندی آن استX_{-i} را به عنوان فضای استراتژی همهٔ بازیکنان به جز بازیکنiدر نظر بگیرید. هر بازیکن به ازای هر i عضو مجموعه اعداد صحیح، استراتژی X_i را انتخاب کند، پروفایل استراتژی آن به صورت  x={x_1,... ,x_n} و تابع بهره‌مندی آن به صورت F(x_i) نتیجه داده می‌شود. قابل ذکر است که تابع بهره‌مندی به نمای استراتژی انتخابی وابسته است. به عنوان مثال، در استراتژی انتخاب شده توسط بازیکن i و همچنین استراتژی‌های انتخاب شده توسط تمام بازیکنان دیگر. نمای استراتژی x^*\in S یک تعادل نش (NE) است اگر هیچ انحراف یک سویی در استراتژی توسط هر بازیکن واحد با یکی دیگر از بازیکنان سودآور نمی‌باشد؛ که به این معنا خواهد بود که:

\forall i,x_i\in S_i, x_i \neq x^*_{i}: f_i(x^*_{i}, x^*_{-i}) \geq f_i(x_{i},x^*_{-i}).

### تعادل کامل لغزش دست
در ابتدا یک بازی مبهم را تعریف می‌کنیم. بازی مبهم دقیقاً گونه ای بازی پایه است با این تفاوت که بازیکن تنها مجاز به استفاده از استراتژی کاملاً مخلوط است. همان‌طور که گفته شد استراتژی کاملاً مخلوط به استراتژی ای گفته می‌شود که هر استراتژی با احتمال ناصفر بازی شود. یک بازیکن گاهی مواقع استراتژی متفاوتی را از استراتژی‌های قابل پیش‌بینی انتخاب می‌کند که این دقیقاً همان مفهوم لغزش دست است. حال یک مجموعه استرتژی Sرا در یک بازی پایه در نظر بگیرید. این مجموعه استراتژی را به عنوان تعادل کامل لغزش دست در نظر می‌گیریم اگر یک دنباله ای از بازی‌های مبهم که در بالا تعریف کردیم وجود داشته باشد که وابسته به بازی پایه هستند و مجموعه ای از تعادل‌های نش وجود داشته باشند که همگرا به  Sهستند. به بیانی دقیق تر می‌توان گفت، یک استراتژی پروفایل \sigmaرا تعادل کامل لغزش دست می‌گوییم اگر دنباله ای از تمام استراتژی پروفایل \sigma ^ {n}همگرا به خود \sigmaباشد به طوری که \sigma _ {i} \in B_{i}(\sigma _ {-i} ^{n})برای هر عدد nبرقرار باشد.

## مثال
بازی زیر را در نظر بگیرید، در این بازی نفر اول دارای مجموعه استراتژی \{A,B\}و نفر دوم دارای استراتژی‌های \{C,D\}است. جدول زیر بیانگر شرایط بازی خواهد بود. برای راحتی کار فرض کنید استراتژی‌های \{A,B\}همان بالا و پایین هستند و استراتژی \{C,D\}همان چپ و راست هستند.

فرض کنید بازیکن۱ به صورت ترکیبی بازی می‌کند و به احتمال \xi، Aرا بازی می‌کند و به احتمال 1 - \xi، Bرا بازی می‌کند. توجه کنید در اینجا بنابر تعریف لزوماً 0. حال با توجه به استراتژی بازیکن دوم سود این بازیکن را حساب خواهیم کرد. برای این منظور حالت بندی می‌کنیم. فرض کنید بازیکن دوم Cرا بازی کند در این صورت می‌دانیم که امید ریاضی سودش برابر خواهد شد با:

1(1-\xi) + 2\xi = 1 + \xi

حال حالت دیگر را در نظر بگیرید که بازیکن دوم Dرا بازی کند. در این حالت سود امیدریاضی سود بازیکن دوم برابر خواهد شد با:

0(1-\xi) + 2\xi = 2\xi

به‌طور مشخص بازیکن دوم در زمانی که  Cبازی کند سود بیشتری خواهد داشت و این موضوع به این علت است که:

1 + \xi > 2\xi \Longleftrightarrow \xi 

که می‌دانیم درست است. پس برای بازیکن دوم مناسب تر خواهد بود که وزن انتخاب C را بیشتر از Dقرار دهد. به طریق کاملاً مشابه اگر بازیکن اول بداند که وزن Cبرای بازکن دوم بیشتر از Dاست پس وزن کمی را برای انتخاب Bقرار می‌دهد. در این حالت می‌توان گفت که استراتژی \{A,C\}یک استراتژی لغزش دست است.

همین استدلال را برای بازیکن اول نیز می‌توان تکرار کرد. برای این منظور داریم:

فرض کنید نفر دوم استراتژی ترکیبی را انتخاب کند که در آن به احتمال \xi، Cرا بازی می‌کند و به احتمال 1 - \xi، Dرا بازی می‌کند. پس می‌خواهیم همانند قبل سود نفر اول را با توجه به استراتژی که دارد بدست آوریم. برای این منظور فرض کنید بازیکن اول استراتژی A(بالا) را انتخاب کرده باشد. پس در این حالت امید ریاضی سود بازیکن اول برابر خواهد بود با:

2(1-\xi) + 1\xi = 2-\xi

و در صورتی که Bبازی کند امید ریاضی سودش برابر خواهد بود با:

2(1-\xi) + 0\xi = 2-2\xi

پس با توجه به این نکته که 0است پس انتخاب Aمناسب تر خواهد بود. پس به این علت که بازیکن اول علاقه دارد وزن Aرا بیشتر کند و وزن B را کمتر به راحتی می‌توان دید که \{B,D\}یک تعادل کامل لغزش دست نیست.

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

### تعریفی ساده از یک بازی مبهم
بازی مبهم یک گونه ای از بازی پایه است، به طوری که در آن هر بازیکن باید تمام استراتژی‌های ناخالص را با احتمال مثبت بازی کند. به عبارتی دیگر می‌توان گفت به یک بازی پایه ای مبهم می‌گوییم اگر تمام استراتژی‌های بازی شده توسط بازیکن‌ها به صورت مخلوط بوده و در هر استراتژی مخلوط بازی شده تمام استراتژی‌های خالص با احتمال ناصفر بازی شده باشند. اگر بخواهیم این بیانمان را با استفاده از ریاضی دقیق تر کنیم می‌توان نوشت که در این بازی‌ها اگر برای بازیکن دلخواه A، بدانیم مجموعه استراتژی‌های خالص \{a_{1}, a_{2},...,a_{n}\}است و همچنین در استراتژی مخلوط Sکه این بازیکن بازی کرده بدانیم که، a_{i}به احتمال \delta_{i}بازی شده‌است، آنگاه داریم \delta_{i} > 0.

### تعریف رسمی
در ابتدا می‌دانیم که یک بازی استراتژیک به شکل زیر خواهد بود:

G=(I,(Mi),(Pi))

که در آن داریم که **<math>\begin{align} (i \in I) \end{align}</math>**همچنین **<math>\begin{align} I \end{align}</math>**بیانگر مجموعه بازیکنان است و **<math>\begin{align} M_i \end{align}</math>**نشان دهنده مجموعه ای از استراتژی‌های ترکیبی مبتنی بر توزیع احتمالی استراتژی‌های خالص **<math>\begin{align} S_i \end{align}</math>** است. **<math>\begin{align} P_i \end{align}</math>**نیز بیانگر اشتباهات احتمالی نفر **<math>\begin{align} i \end{align}</math>**است. برای هر بازیکن **<math>\begin{align} (i \in I) \end{align}</math>**در نظر بگیرید که **<math>\begin{align} n_i \end{align}</math>**استراتژی خالص که **<math>\begin{align} \epsilon_i = (\epsilon_i^1, \epsilon_i^2,...,\epsilon_i^n) \end{align}</math>**بیانگر مجموعه ای از احتمال‌های بازی شده‌است داریم که **<math>\begin{align} \epsilon_i \gg 0 \end{align}</math>**و همچنین:

 \sum\nolimits_{j=1}^{n_i} \epsilon_i^j 

پس در مورد مقدار استراتژی‌های مخلوط در بازی‌های مبهم داریم که:

## <math>\begin{align} M_i^\epsilon = (m_i \in {M_i}|m_i^k \ge \epsilon_i^k) \end{align}</math>
که در آن می‌دانیم: **<math>\begin{align} k = (1,...,n_i) \end{align}</math>**. این بدان معناست که بازیکن **<math>\begin{align} i \end{align}</math>**ام هر یک از استراتژی‌های خالص خود را حداقل باید با احتمال **<math>\begin{align} \epsilon_i^k \end{align}</math>**بازی کند تا در بازی مبهم داشته باشیم:

## <math>\begin{align} G(\epsilon) = (I,(M_i^\epsilon), (P_i)) \end{align}</math>
که در آن می‌دانیم **<math>\begin{align} (i \in I) \end{align}</math>**است، یک تعادل نش بازی مبهم **<math>\begin{align} m^* (\epsilon) \end{align}</math>** است و **<math>\begin{align} m^* \end{align}</math>**یک تعادل در بازی اصلی است. در این صورت می‌توان گفت تعریف رسمی مفهوم تعادل بازی لغزش دست به شکل زیر بیان می‌شود:

## <math>\begin{align} \lim_{\epsilon \to 0}m^*(\epsilon) = m^* \end{align}</math>
### مثال

در ابتدا، بازی ای را در نظر بگیرید که جدول بازده آن به شکل روبرو باشد. در حالت بازی‌های معمول به وضوح مشخص است که در دو شرایط عادی (چپ، بالا) و (راست، پایین) تعادل نش هستند. حال به بررسی شرایط مسئله می‌پردازیم. اگر حتی احتمال ناچیزی مانند \sigmaباشد که بازیکن دوم چپ بازی کند در این حالت بهترین پاسخ بازیکن اول برابر با بالا خواهد بود. حال در حالتی که بازی مبهم باشد بازیکن اول باید با احتمالی ناصفر پایین را نیز بازی کند! در این حالت باید کمترین میزان احتمال ممکن را در باید در نظر گرفت، پس می‌نویسیم که **<math>\begin{align} a_2 = a_2^{min} \end{align}</math>**به طریق مشابه می‌توان تعریف کرد که **<math>\begin{align} b_2 = b_2^{min} \end{align}</math>**. از طرفی دیگر با توجه به تعاریف بیان شده**<math>\begin{align} (1-a_2^{min},a_2^{min}) , (1-b_2^{min},b_2^{min}) \end{align}</math>**یک تعادل خواهد بود. پس با توجه به استدلال‌های بالا می‌توان گفت:

\lim_{a_2^{min},b_2^{min} \to 0}[(1-a_2^{min},a_2^{min}),(1-b_2^{min},b_2^{min})] = [(1,0),(1,0)] = (a_1,b_1)

که این بدان معناست که اگر احتمال خطا را به صفر برسانیم آنگاه تعادل بازی مبهم به سمت یک تعادل بازی اصلی خواهد رفت. به این تعادل، تعادل کامل لغزش دست می‌گوییم. پس **<math>\begin{align} (1-a_2^{min},a_2^{min}) , (1-b_2^{min},b_2^{min}) \end{align}</math>**یک تعادل کامل لغزش دست است.

## قضیه‌های معروف و کاردبردی
برای بازی‌های دو نفره می‌توان دید که مجموعه تعادل کامل لغزش دست با مجموعه تعادل‌هایی که تشکیل شده از دو استراتژی غیر مغلوب هستند، متمایز هستند. همان‌طور که در بالا دیدیم استراتژی \{B,D\}یک تعادل کامل لغزش دست نیست اما مشخصا هیچ استراتژی دیگری نمی‌تواند آن را مغلوب کند.

### قضیه ۱
هر تعادل کامل لغزش دست خود نیز یک تعادل نش است!

برای اثبات این قضیه فرض کنید \sigmaیک تعادل لغزش دست است. \sigma _ {i}\in\Sigma _ {i}حال در نظر بگرید \sigma ^ {'} _ {i}\in\Sigma_ {i}. با توجه به تعریف خواهیم داشت U _ {i}(\sigma _ {i}, \sigma _ {-i} ^ {n} ) - U _ {i}(\sigma ^ {'}, \sigma _ {-i} ^ {n}) \geq 0برای تمام مقادیر n. حال به راحتی می‌توان حکم را نشان داد. باید توجه کرد که این موضوع به این معناست که U _ {i}(\sigma _ {i}, \sigma _ {-i}) - U _ {i}(\sigma ^ {'}, \sigma _ {-i}) \geq 0پس \sigma  _ {i}بهنرین پاسخ به \sigma  _ {-i} است. به عبارتی دیگر \sigma _ {i} \in B_{i}(\sigma _ {-i})که حکم را نتیجه می‌دهد.

### قضیه ۲
این قضیه بیان می‌کند که هر بازی متناهی حداقل یک استراتژی لغزش دست دارد. برای اثبات آن داریم:[پیوند=[پرونده:Extensive-form tree with uncertainty.svg|قاب|نمایش گستردهٔ یک بازی]]

فرض کنید \sigma ^ {0}تمام استراتژی‌های میکس (مخلوط) باشد. دنباله همگرا به صفر \epsilon _ {i} ^{n} \in (0,1)را در نظر بگیرید. تعریف می‌کنیم u_{i}^{n}(s) := U_{i}((\epsilon_{i} ^ {n}\sigma_{i} ^{0} + (1-\epsilon_{i} ^ {n})s_{i})_{i \in I})برای هر s \in S. G ^{n}را طوری در نظر می‌گیریم که مشتق شده از G در زمانی که u_{i}^nبه جای u_{i}قرار گرفته‌است. می‌دانیم که طبق قضیه تعادل نش برای این بازی (به عبارتی بهتر برای هر بازیG ^{n}) یک تعادل نش مانند \sigma ^ {n}وجود دارد. از آنجایی که می‌دانیم \Sigma_ {i}پیوسته‌است پس زیر دنباله همگرا از \sigma ^ {n}وجود دارد. بدون کم شدن از کلیت مسئله فرض می‌کنیم زیر دنباله، همان خود دنباله است و \sigmaحدش است. در ادامه می‌خواهیم اثبات کنیم که برای N، داریم : \sigma  _ {i} \in B_{i}(\sigma  _ {-i} ^{n})برای هر i \in Iو هر n\geq N.

برای هر s_{i} به طوری که \sigma _{i}(s_{i})>0می‌دانیم عدد طبیعی N(s_i)وجود دارد به طوری که \sigma _{i}^{n}(s_{i})>0برای هر n\geq N(s_i). حال فرض کنید Nبیشترین مقدار در بین N(s_i)ها برای کل s_{i}ها است. پس برای هر s_{i}به طوری که \sigma _{i}(s_{i})>0 می‌دانیم که s  _ {i} \in B_{i}(\sigma  _ {-i} ^{n})برای تمام n\geq Nها برقرار است. پس حکم مسئله یا به عبارتی قضیه بالا اثبات شده‌است.

## جستارهای وابسته
* راینهارد سیلتن
* نظریه بازی‌ها
* تعادل نش
* شکل گسترده بازی
* تعادل نش زیربازی کامل
* بازی بهنجار
* فرایند برامز-تیلور
* تقسیم منصفانه کیک
* مسئله چانه‌زنی
* لم اسپرنر

## منابع

* 

رده:ایده‌های تعادل تئوری بازی
رده:بازی غیرمشارکتی
رده:نظریه بازی‌ها