אלגוריתם Lemke-Howson

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש
Gnome-colors-edit-find-replace.svg
יש לשכתב ערך זה. ייתכן שהערך מכיל טעויות, או שהניסוח וצורת הכתיבה שלו אינם מתאימים.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף.
יש לשכתב ערך זה. ייתכן שהערך מכיל טעויות, או שהניסוח וצורת הכתיבה שלו אינם מתאימים.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף.

אלגוריתם Lemke-Howson, שפותח על ידי C. E. Lemke ו J. T. Howson בשנת[1]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 זמן הריצה של האלגוריתם אקספוננציאלי. לא מזמן הוכח[2] שהאלגוריתם שייך למחלקת הסיבוכיות PPAD_(מחלקת_סיבוכיות).

שיפורים

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

BFS-Lemke-Howson

[3]Porter, Nudelman and Shoham heuristic

Novel heuristics[4]

מקורות

  • 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

ראו גם

הערות שוליים

  1. ^ Lemke, C. E., Howson, Jr., J. T.: Equilibrium Points of Bimatrix Games, Journal of the Society of Industrial and Applied Mathematics, 1964
  2. ^ X. Chen, X. Deng, Settling the Complexity of 2-Player Nash-Equilibrium. Electronic Colloquium on Computational Complexity (ECCC), 2005.
  3. ^ R.Porter, E. Nudelman, Y. Shoham. Simple Search Methods for Finding a Nash Equilibrium. Proceedings of the National Conference on Artificial Intelligence, 2004
  4. ^ B Codenotti, S De Rossi, M Pagan: An experimental analysis of Lemke-Howson algorithm, Arxiv preprint arXiv:0811.3247, 2008