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

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

راینهارد سیلتن ریاضیدان و اقتصاددان مطرح آلمانی

تعریف

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

مجموعه استراتژی و استراتژی مختلط

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

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

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

یک استراتژی کاملاً مختلط، استراتژی مختلطی است که در آن بازیکن یک احتمال اکیداً مثبت به هر استراتژی خالص می‌دهد. به عبارتی دقیق تر فرض کنید $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$برقرار باشد.

مثال

	راست	چپ
بالا	۰, ۲	1, 1
پایین	2, 2	2, 0
تعادل کامل لغزش دست

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

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

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

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

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

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

$1+\xi >2\xi \Longleftrightarrow \xi <1$

که می‌دانیم درست است. پس برای بازیکن دوم مناسب تر خواهد بود که وزن انتخاب $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<\xi <1$است پس انتخاب $A$مناسب تر خواهد بود. پس به این علت که بازیکن اول علاقه دارد وزن $A$را بیشتر کند و وزن $B$ را کمتر به راحتی می‌توان دید که $\{B,D\}$یک تعادل کامل لغزش دست نیست.

تعریف رسمی با کمک بازی مبهم

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

تعریفی ساده از یک بازی مبهم

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

تعریف رسمی

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

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

که در آن داریم که ${\begin{aligned}(i\in I)\end{aligned}}$همچنین ${\begin{aligned}I\end{aligned}}$بیانگر مجموعه بازیکنان است و ${\begin{aligned}M_{i}\end{aligned}}$نشان دهنده مجموعه ای از استراتژی‌های ترکیبی مبتنی بر توزیع احتمالی استراتژی‌های خالص ${\begin{aligned}S_{i}\end{aligned}}$ است. ${\begin{aligned}P_{i}\end{aligned}}$نیز بیانگر اشتباهات احتمالی نفر ${\begin{aligned}i\end{aligned}}$است. برای هر بازیکن ${\begin{aligned}(i\in I)\end{aligned}}$در نظر بگیرید که ${\begin{aligned}n_{i}\end{aligned}}$استراتژی خالص که ${\begin{aligned}\epsilon _{i}=(\epsilon _{i}^{1},\epsilon _{i}^{2},...,\epsilon _{i}^{n})\end{aligned}}$بیانگر مجموعه ای از احتمال‌های بازی شده‌است داریم که ${\begin{aligned}\epsilon _{i}\gg 0\end{aligned}}$و همچنین:

$\sum \nolimits _{j=1}^{n_{i}}\epsilon _{i}^{j}<1$

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

${\begin{aligned}M_{i}^{\epsilon }=(m_{i}\in {M_{i}}|m_{i}^{k}\geq \epsilon _{i}^{k})\end{aligned}}$

که در آن می‌دانیم: ${\begin{aligned}k=(1,...,n_{i})\end{aligned}}$. این بدان معناست که بازیکن ${\begin{aligned}i\end{aligned}}$ام هر یک از استراتژی‌های خالص خود را حداقل باید با احتمال ${\begin{aligned}\epsilon _{i}^{k}\end{aligned}}$بازی کند تا در بازی مبهم داشته باشیم:

${\begin{aligned}G(\epsilon )=(I,(M_{i}^{\epsilon }),(P_{i}))\end{aligned}}$

که در آن می‌دانیم ${\begin{aligned}(i\in I)\end{aligned}}$است، یک تعادل نش بازی مبهم ${\begin{aligned}m^{*}(\epsilon )\end{aligned}}$ است و ${\begin{aligned}m^{*}\end{aligned}}$یک تعادل در بازی اصلی است. در این صورت می‌توان گفت تعریف رسمی مفهوم تعادل بازی لغزش دست به شکل زیر بیان می‌شود:

${\begin{aligned}\lim _{\epsilon \to 0}m^{*}(\epsilon )=m^{*}\end{aligned}}$

مثال

	راست	چپ
بالا	۰, ۰	۳, ۳
پایین	۰, ۰	۰, ۰
تعادل کامل لغزش دست

در ابتدا، بازی ای را در نظر بگیرید که جدول بازده آن به شکل روبرو باشد. در حالت بازی‌های معمول به وضوح مشخص است که در دو شرایط عادی (چپ، بالا) و (راست، پایین) تعادل نش هستند. حال به بررسی شرایط مسئله می‌پردازیم. اگر حتی احتمال ناچیزی مانند $\sigma$باشد که بازیکن دوم چپ بازی کند در این حالت بهترین پاسخ بازیکن اول برابر با بالا خواهد بود. حال در حالتی که بازی مبهم باشد بازیکن اول باید با احتمالی ناصفر پایین را نیز بازی کند! در این حالت باید کمترین میزان احتمال ممکن را در باید در نظر گرفت، پس می‌نویسیم که ${\begin{aligned}a_{2}=a_{2}^{min}\end{aligned}}$به طریق مشابه می‌توان تعریف کرد که ${\begin{aligned}b_{2}=b_{2}^{min}\end{aligned}}$. از طرفی دیگر با توجه به تعاریف بیان شده${\begin{aligned}(1-a_{2}^{min},a_{2}^{min}),(1-b_{2}^{min},b_{2}^{min})\end{aligned}}$یک تعادل خواهد بود. پس با توجه به استدلال‌های بالا می‌توان گفت:

$\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})$

که این بدان معناست که اگر احتمال خطا را به صفر برسانیم آنگاه تعادل بازی مبهم به سمت یک تعادل بازی اصلی خواهد رفت. به این تعادل، تعادل کامل لغزش دست می‌گوییم. پس ${\begin{aligned}(1-a_{2}^{min},a_{2}^{min}),(1-b_{2}^{min},b_{2}^{min})\end{aligned}}$یک تعادل کامل لغزش دست است.

قضیه‌های معروف و کاردبردی

برای بازی‌های دو نفره می‌توان دید که مجموعه تعادل کامل لغزش دست با مجموعه تعادل‌هایی که تشکیل شده از دو استراتژی غیر مغلوب هستند، متمایز هستند. همان‌طور که در بالا دیدیم استراتژی $\{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})$که حکم را نتیجه می‌دهد.

قضیه ۲

این قضیه بیان می‌کند که هر بازی متناهی حداقل یک استراتژی لغزش دست دارد. برای اثبات آن داریم:

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

فرض کنید $\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$ها برقرار است. پس حکم مسئله یا به عبارتی قضیه بالا اثبات شده‌است.

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

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