אלגוריתם Lemke-Howson

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

אלגוריתם Lemke-Howson, שפותח על ידי C. E. Lemke ו J. T. Howson בשנת 1964[1] הוא האלגוריתם הקומבינטורי השימושי ביותר כיום למציאת שיווי משקל נאש במשחקי 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