אלגוריתם Lemke-Howson

אלגוריתם Lemke-Howson, שפותח על ידי C. E. Lemke ו J. T. Howson בשנת 1964 הוא האלגוריתם הקומבינטורי השימושי ביותר
כיום למציאת שיווי משקל נאש במשחקי Nondegenerate Bitmatrix בשני שחקנים.
האלגוריתם פותר בעיה המהווה מקרה פרטי של בעיית LPC.
קלט: משחק Nondegenerate Bitmatrix.
פלט: אחד משיווי משקל נאש של המשחק.

 הגדרות 
נגדיר משחק Bitmatrix בשני שחקנים על ידי מטריצות התועלות  ו .

יהיו {M = {1,...,m ו {N = {m+1,m+2,...,m+n ותהי M ∪ N קבוצת התוויות.

 אלגוריתם 

 1 Define labeling
 2 Choose K ∈ M ∪ N called the missing label
 3 Let (x,y) = (0,0) ∈ P X Q. Drop label K from (x,y) (from x ∈ P if K ∈ M, from y ∈ Q if K ∈ N).
 4 Let (x,y) be the current vertex. Let L be the label that is picked up by dropping label K. 
 If L = K finish and (x,y) is the Nash equilibrium. Else drop L in the other polytope and repeat this step.

 תיאור 
האלגוריתם מוצא שווי משקל נאש אחד ומהווה הוכחה לקיומו של שווי משקל זה.
האלגוריתם עוקב אחר מסלול של זוגות קודקודים ב P X Q עבור ה polytopes P,Q המתחיל בנקודה (0,0) הנקראת Artificial equilibrium ונגמר בנקודת
שיווי משקל נאש.
המסלול עוקב אחר צלעות ב P ו Q לסירוגין תוך שמירה על הקודקוד ב polytope השני קבוע. מכיוון שהמשחק הוא Nondegenerate קודקוד של
P נתון על ידי m - 1 תוויות. זריקת תווית L של קודקוד X ב P מוגדרת על ידי מעבר על הצלע הייחודית שיש לה את כל התוויות של X פרט ל L. 
הבחירה הראשונית של האלגוריתם תהיה אסטרטגיה טהורה K של שחקן (כל תווית ב M ∪ N) הנקראת missing label.
תחילה (0,0) = (x,y) התווית K נזרקת.
בסוף הצלע המתאימה הצלע החדשה שנבחרת היא שכפול שכן היא הייתה נוכחת ב polytope השני.
כעת הצלע המשוכפלת נזרקת ב polytope השני ונבחרת צלע חדשה. אם הצלע שנבחרה היא ה missing label האלגוריתם מסתיים והוא מצא
את השיווי משקל נאש. אחרת חוזר על עצמו על ידי זריקת הצלע המשוכפלת ב polytope השני וכן הלאה...

 זמן ריצה 
האלגוריתם מסתיים ומוצא את שיווי משקל נאש מכיוון שב P X Q יש מספר סופי של זוגות קודקודים.
זוג הקודקודים הבא במסלול תמיד ייחודי ולכן לא מבקרים באותו זוג קודקודים פעמיים שכן אז הייתה אפשרות נוספת להמשך מלכתחילה.
מכיוון שמספר הקודקודים ב P X Q אקספוננציאלי ב n ו m זמן הריצה של האלגוריתם אקספוננציאלי.
לא מזמן הוכח שהאלגוריתם שייך למחלקת הסיבוכיות PPAD_(מחלקת_סיבוכיות).

 שיפורים 
קיימים מספר שיפורים של האלגוריתם המנצלים יוריסטיקות שונות על מנת לשפר את זמן הריצה בפועל:

BFS-Lemke-Howson

Porter, Nudelman and Shoham heuristic

Novel heuristics

 מקורות 
 Algorithmic Game Theory by Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani, Cambridge Press, 2007
 B Von Stengel: Computing equilibria for two-person games, 1996
 Lemke, C. E., Howson, Jr., J. T.: Equilibrium Points of Bimatrix Games, 1964

 ראו גם 
 PPAD_(מחלקת_סיבוכיות)
 שיווי משקל נאש
 תורת_המשחקים
 Polytopes
 List of PPAD-complete problems

 הערות שוליים 

קטגוריה:תורת המשחקים
Lemke-Howson