אלגוריתם Lemke-Howson

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

קלט: משחק Nondegenerate Bitmatrix.
פלט: אחד משיווי משקל נאש של המשחק.

הגדרות

נגדיר משחק Bitmatrix בשני שחקנים על ידי מטריצות התועלות $A_{mxn}$ ו $B_{mxn}$.

יהיו {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