الگوریتم لمکه-هاوسون

الگوریتم لمکه-هاوسون^[۱] الگوریتمی برای محاسبه تعادل نش در بازی دوماتریسی (ماتریسی که در هر خانه‌اش دو عنصر دارد) است گفته می‌شود که این الگوریتم بهترین الگوریتم ترکیبیاتی برای یافتن تعادل نش است.^[۲]

الگوریتم[ویرایش]

ورودی الگوریتم یک بازی دو نفره G است. بازی G به صورت دو ماتریس n × m با نام A و B داده می‌شود که هر کدام از آنها شامل نتایج نهایی برای یکی از بازیکنان شماره ۱ و ۲ است که هر کدام به ترتیب، m و n استراتژی خالص دارند. در ادامه فرض می‌کنیم که نتایج مثبت هستند (هر بازی با تغییر مقیاس می‌تواند به بازی برابری از نظر استراتژی با نتایج مثبت تبدیل شود).

بازی G دو چند وجهی متناظر دارد (که بهترین پاسخ بین چند وجهی‌ها نامیده می‌شوند)، به اسم‌های P_۱ و P_۲ که هر کدام به ترتیب m و n بعد دارند. در ادامه به تعریف این دو ماتریس می‌پردازیم.

ماتریس P_۱ در R^m است. فرض کنید {x_۱,... ,x_m} مختصات را نشان می‌دهد. P_۱ به وسیله m نامساوی x_i ≥ ۰ برای همه {i ∈ {۱، ... , m و n نامساوی B_۱،jx_۱+... +B_m,jx_m ≤ ۱ برای همه {j ∈ {۱، ... , n تعریف می‌شود.

ماتریس P_۲ در Rⁿ است. فرض کنید {x_m+۱, ... , x_m+n} مختصات را نشان می‌دهد. P_۲ به وسیله n نامساوی xm+i ≥ ۰ برای همه {i ∈ {۱، ... , n و m نامساوی A_i،۱x_m+۱+... +A_i,nx_m+n ≤ ۱ برای همه {i ∈ {۱، ... , m تعریف می‌شود.

ماتریس P_۱ نشان‌دهنده مجموعه توزیع‌های احتمالاتی نُرمالایز نشده برای m استراتژی بازیکن اول است، هنگامی که نتیجه مورد انتظار بازیکن دوم حداکثر یک باشد. برای برقراری m شرط اول باید احتمالات نامنفی باشند و هر یک از n شرط بعد هم باعث می‌شود که n استراتژی خالص بازیکن دوم نتایجی با مقدار حداکثر یک داشته باشند. اگر نقش دو بازیکن را با هم عوض کنیم، ماتریس P_۲ نیز به همین ترتیب تعریف می‌شود.

هر رأس v از ماتریس P_۱، با مجموعه‌ای از برچسب‌ها (مقادیر) از مجموعه {۱،... ,m + n}، در ارتباط است. برای هر {i ∈ {۱، ... , m رأس v برچسب «i» را می‌پذیرد در صورتی که در رأس v شرط «xi = ۰» برقرار باشد. برای هر j ∈ {۱، …, n}، v برچسب «m + j» را می‌پذیرد در صورتی که شرط «B_۱،jx_۱ + ... + B_m,jx_m = ۱» برقرار باشد. فرض کنید که P_۱ غیر تبهگن (nondegenerate) باشد، هر رأس بر m بعد از ماتریس P_۱ واقع است و m برچسب دارد. دقت کنید که ریشه که خود یک رأس از P_۱ می‌باشد، برچسب‌های {۱، …, m} را دارد.

هر رأس w از از ماتریس P_۲ با مجموعه‌ای از برچسب‌ها از مجموعه {۱، …, m + n}، در ارتباط است. برای هر {j ∈ {۱، …, n رأس w برچسب «m + j» را می‌پذیرد در صورتی که در رأس w شرط « xm+j = ۰» برقرار باشد. برای هر i ∈ {۱، …, m}، w برچسب «i» را می‌پذیرد در صورتی که شرط «A_i،۱x_m+۱ + ... + A_i,nx_m+n = ۱» برقرار باشد. فرض کنید که P_۲ غیر تبهگن باشد، هر رأس بر m بعد از ماتریس P_۲ واقع است و m برچسب دارد دقت کنید که ریشه که خود یک رأس از P_۲ می‌باشد، برچسب‌های {m + ۱، …, m + n} را دارد.

عمل محوری شامل گرفتن زوج مرتبی مانند (v, w)، و عوض کردن v با یکی از همسایه‌هایش در P_۱ است یا عوض کردن w با یکی از همسایه‌هایش در P_۲. در عمل محوری رأسی که عوض می‌شود را رها شده می‌نامیم. مثلاً اگر طی یک عمل محوری یک رأس از P_۱ جایگزین v شود، به اصطلاح می‌گوییم «v رها می‌شود». به ازای هر مقدار از v، می‌شود با انتقال به یک رأس همسایه که شامل ابرصفحه مرتبط با آن برچسب نباشد، آن برچسب را رها کرد.

الگوریتم از زوج (v, w) شروع می‌شود که کاملاً برچسب‌گذاری (مقدار دهی) شده است که این زوج شامل زوج ریشه‌ها می‌باشد. برچسب دلخواه g را به دلخواه با انجام یک عمل محوری رها می‌کنیم. در نتیجه زوج مرتب ما به زوج تقریباً برچسب‌گذاری شدهٔ (’v’, w) تبدیل می‌شود (زوجی که تنها یک عنصر برچسب‌گذاری نشده دارد).

هر زوج تقریباً برچسب‌گذاری شده (زوج مرتبی که تنها یک عنصر برچسب‌گذاری نشده دارد) دو عمل محوری می‌پذیرد که این عمل متناظر با رها کردن یک عنصر یا ایجاد یک کپی از برچسب‌های تکراری آن زوج می‌باشد. هر یک از این اعمال سرانجام به یک زوج کاملاً یا تقریباً برچسب‌گذاری شده ختم می‌گردد. در نهایت الگوریتم زوج مرتب کاملاً برچسب‌گذاری شدهٔ (*v*, w) را بدست می‌آورد که مخالف ریشه است. زوج مرتب (*v*, w) با یک زوج مرتب از توزیع‌های احتمالاتی نُرمالایز نشده متناظر است که در آن هر استراتژیِ بازیکن شماره یک مانند «i»، یا به بازیکن شماره یک می‌پردازد یا باید کمتر از یک واحد بپردازد و بازی با احتمال ۰ توسط آن بازیکن (بازیکن شماره یک) انجام می‌شود (برای بازیکن شماره دو نیز به همین ترتیب). با نُرمالایز کردن این مقادیر به توزیع‌های احتمال، تعادل نش بدست می‌آید (که در آن مقدار پرداختی به بازیکنان برابر وارون عوامل نرمال سازی می‌باشد).

خصوصیات الگوریتم[ویرایش]

این الگوریتم حداکثر می‌تواند تا «n + m» تعادل نش متفاوت بیابد. هر برچسبی که در مرحله اولیه برای رها شدن انتخاب شود، تعیین کننده تعادل نشی است که الگوریتم می‌یابد. الگوریتم لمکه-هاوسون معادل رویکرد مبتنی بر هوموتوپی زیر است. بازیِ G را اینگونه تغییر می‌دهیم که یک استراتژی خالص دلخواه مانند g را انتخاب می‌کنیم و به بازیکنی که آن استراتژی را داشت مقدار زیاد «B» را می‌پردازیم تا حتماً آن را بازی کند. در این بازی تغییر یافته، می‌دانیم که استراتژی g با احتمال ۱ به وقوع می‌پیوندد و بازیکن مقابل نیز در جواب با احتمال ۱ بهترین بازی ممکن خود را انجام می‌دهد. زنجیره‌ای از بازی را در نظر بگیرید که در آن B به طور مداوم کاهش می‌یابد و به صفر میل می‌کند. یک مسیر تعادل نش وجود دارد که تعادل نش منحصربه‌فرد بازی جدید را به تعادلی در بازی اصلی G می‌رساند. استراتژی خالص انتخاب شدهٔ g برای دریافت جایزهٔ B، به برچسبی که در ابتدا رها می‌شود بستگی دارد^[۳].

در حالی که این الگوریتم در عمل بهینه و کارآمد است، در بدترین حالت تعداد عملیات محوری لازم ممکن است تابعی نمایی از تعداد تمام استراتژی‌های خالص بازی باشد^[۴]. متعاقباً نشان داده شده است که یافتن هر جوابی که با الگوریتم لمکه-هاوسون بدست می‌آید PSPACE-complete می‌باشد^[۵].

منابع[ویرایش]

↑ C. E. Lemke and J. T. Howson (1964). "Equilibrium points of bimatrix games". SIAM Journal on Applied Mathematics. 12 (2): 413–423.
↑ Nisan, Noam; Roughgarden, Tim; Tardos, Éva; Vazirani, Vijay V. (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. p. 33. ISBN 0-521-87282-0.
↑ P. J-J. Herings and R. Peeters (2010). "Homotopy methods to compute equilibria in game theory". Economic Theory 42 (1): 119–156. doi:10.1007/s00199-009-0441-5.
↑ R. Savani and B. von Stengel (2006). "Hard-to-Solve Bimatrix Games". Econometrica 74 (2): 397–429. doi:10.1111/j.1468-0262.2006.00667.x.
↑ P.W. Goldberg, C.H. Papadimitriou and R. Savani (2011). "The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke–Howson Solutions". Proc. 52nd FOCS. pp. 67–76. doi:10.1109/FOCS.2011.26.

[1] C. E. Lemke and J. T. Howson (1964). "Equilibrium points of bimatrix games". SIAM Journal on Applied Mathematics. 12 (2): 413–423.

[2] Nisan, Noam; Roughgarden, Tim; Tardos, Éva; Vazirani, Vijay V. (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. p. 33. ISBN 0-521-87282-0.

[3] P. J-J. Herings and R. Peeters (2010). "Homotopy methods to compute equilibria in game theory". Economic Theory 42 (1): 119–156. doi:10.1007/s00199-009-0441-5.

[4] R. Savani and B. von Stengel (2006). "Hard-to-Solve Bimatrix Games". Econometrica 74 (2): 397–429. doi:10.1111/j.1468-0262.2006.00667.x.

[5] P.W. Goldberg, C.H. Papadimitriou and R. Savani (2011). "The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke–Howson Solutions". Proc. 52nd FOCS. pp. 67–76. doi:10.1109/FOCS.2011.26.

[۱]

[۲]

[۳]

[۴]

[۵]