אלגוריתם 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