موضوع مقاله: الگوریتم لمکه-هاوسون | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم لمکه-هاوسون | مقدمه: الگوریتم لمکه-هاوسون الگوریتمی برای محاسبه تعادل نش در بازی دوماتریسی (ماتریسی که در هر خانه‌اش دو عنصر دارد) است گفته می‌شود که این الگوریتم بهترین الگوریتم ترکیبیاتی برای یافتن تعادل نش است. | ## بخش 1: الگوریتم لمکه-هاوسون | بازی G به صورت دو ماتریس n × m با نام A و B داده می‌شود که هر کدام از آنها شامل نتایج نهایی برای یکی از بازیکنان شماره ۱ و ۲ است که هر کدام به ترتیب، m و n استراتژی خالص دارند. در ادامه فرض می‌کنیم که نتایج مثبت هستند (هر بازی با تغییر مقیاس می‌تواند به بازی برابری از نظر استراتژی با نتایج مثبت تبدیل شود). بازی G دو چند وجهی متناظر دارد (که بهترین پاسخ بین چند وجهی‌ها نامیده می‌شوند)، به اسم‌های P۱ و P۲ که هر کدام به ترتیب m و n بعد دارند. ماتریس P۱ نشان‌دهنده مجموعه توزیع‌های احتمالاتی نُرمالایز نشده برای m استراتژی بازیکن اول است، هنگامی که نتیجه مورد انتظار بازیکن دوم حداکثر یک باشد. برای برقراری m شرط اول باید احتمالات نامنفی باشند و هر یک از n شرط بعد هم باعث می‌شود که n استراتژی خالص بازیکن دوم نتایجی با مقدار حداکثر یک داشته باشند. هر رأس w از از ماتریس P۲ با مجموعه‌ای از برچسب‌ها از مجموعه {۱، …, m + n}، در ارتباط است. فرض کنید که P۲ غیر تبهگن باشد، هر رأس بر m بعد از ماتریس P۲ واقع است و m برچسب دارد دقت کنید که ریشه که خود یک رأس از P۲ می‌باشد، برچسب‌های {m + ۱، …, m + n} را دارد. عمل محوری شامل گرفتن زوج مرتبی مانند (v, w)، و عوض کردن v با یکی از همسایه‌هایش در P۱ است یا عوض کردن w با یکی از همسایه‌هایش در P۲. | ## بخش 2: الگوریتم لمکه-هاوسون | مثلاً اگر طی یک عمل محوری یک رأس از P۱ جایگزین v شود، به اصطلاح می‌گوییم «v رها می‌شود». به ازای هر مقدار از v، می‌شود با انتقال به یک رأس همسایه که شامل ابرصفحه مرتبط با آن برچسب نباشد، آن برچسب را رها کرد. الگوریتم از زوج (v, w) شروع می‌شود که کاملاً برچسب‌گذاری (مقدار دهی) شده است که این زوج شامل زوج ریشه‌ها می‌باشد. در نتیجه زوج مرتب ما به زوج تقریباً برچسب‌گذاری شدهٔ (’v’, w) تبدیل می‌شود (زوجی که تنها یک عنصر برچسب‌گذاری نشده دارد). هر زوج تقریباً برچسب‌گذاری شده (زوج مرتبی که تنها یک عنصر برچسب‌گذاری نشده دارد) دو عمل محوری می‌پذیرد که این عمل متناظر با رها کردن یک عنصر یا ایجاد یک کپی از برچسب‌های تکراری آن زوج می‌باشد. هر یک از این اعمال سرانجام به یک زوج کاملاً یا تقریباً برچسب‌گذاری شده ختم می‌گردد. در نهایت الگوریتم زوج مرتب کاملاً برچسب‌گذاری شدهٔ (*v*, w) را بدست می‌آورد که مخالف ریشه است. زوج مرتب (*v*, w) با یک زوج مرتب از توزیع‌های احتمالاتی نُرمالایز نشده متناظر است که در آن هر استراتژیِ بازیکن شماره یک مانند «i»، یا به بازیکن شماره یک می‌پردازد یا باید کمتر از یک واحد بپردازد و بازی با احتمال ۰ توسط آن بازیکن (بازیکن شماره یک) انجام می‌شود (برای بازیکن شماره دو نیز به همین ترتیب). | ## بخش 3: الگوریتم لمکه-هاوسون | با نُرمالایز کردن این مقادیر به توزیع‌های احتمال، تعادل نش بدست می‌آید (که در آن مقدار پرداختی به بازیکنان برابر وارون عوامل نرمال سازی می‌باشد). هر برچسبی که در مرحله اولیه برای رها شدن انتخاب شود، تعیین کننده تعادل نشی است که الگوریتم می‌یابد. بازیِ G را اینگونه تغییر می‌دهیم که یک استراتژی خالص دلخواه مانند g را انتخاب می‌کنیم و به بازیکنی که آن استراتژی را داشت مقدار زیاد «B» را می‌پردازیم تا حتماً آن را بازی کند. در این بازی تغییر یافته، می‌دانیم که استراتژی g با احتمال ۱ به وقوع می‌پیوندد و بازیکن مقابل نیز در جواب با احتمال ۱ بهترین بازی ممکن خود را انجام می‌دهد. زنجیره‌ای از بازی را در نظر بگیرید که در آن B به طور مداوم کاهش می‌یابد و به صفر میل می‌کند. یک مسیر تعادل نش وجود دارد که تعادل نش منحصربه‌فرد بازی جدید را به تعادلی در بازی اصلی G می‌رساند. استراتژی خالص انتخاب شدهٔ g برای دریافت جایزهٔ B، به برچسبی که در ابتدا رها می‌شود بستگی داردP. | ## جمع‌بندی | در حالی که این الگوریتم در عمل بهینه و کارآمد است، در بدترین حالت تعداد عملیات محوری لازم ممکن است تابعی نمایی از تعداد تمام استراتژی‌های خالص بازی باشدR.