משחק פוטנציאל

בתורת המשחקים, משחק נקרא משחק פוטנציאל אם התמריץ של כל השחקנים לשינוי האסטרטגיה שלהם ניתן לביטוי כפונקציה גלובלית אחת-פונקציית הפוטנציאל.

המושג הוגדר לראשונה על ידי דב מונדרר ולויד שפלי, בעוד השימוש הראשון בפונקציית פוטנציאל היה ב-1973 על ידי רוברט רוזנטל.

במשחק פוטנציאל מדויק, מתקיים כי שינוי ערך התועלת לשחקן שמשנה אסטרטגיה שווה לשינוי בערך פונקציית הפוטנציאל. במשחק פוטנציאל אורדינלי, נדרש רק כי סימני ההפרש יהיו זהים. בפרט, משחק פוטנציאל מדויק הוא גם משחק פוטנציאל אורדינלי.

פונקציית הפוטנציאל היא כלי שימושי לניתוח מאפייני שיווי משקל של משחקים, מכיוון שתמריצי כל השחקנים ממופים לפונקציה אחת. שימוש עיקרי של הפונקציה הוא למציאת הנקודות בהן מתקיים שיווי משקל טהור. נקודות אלו הן בדיוק נקודות המינימום או המקסימום של הפונקציה (בהתאם להגדרת המשחק).

הגדרה פורמלית

יהי N מספר השחקנים, S קבוצת פרופילי האסטרטגיות מעל הקבוצות $S_{i}$ של כל שחקן, ו-$u_{i}$ פונקציית התועלת של השחקן ה-i.

משחק $G=(N,S=S_{1}\times ...\times S_{N},u:S\rightarrow \mathbb {R} ^{N})$ הוא משחק פוטנציאל מדויק אם קיימת פונקציה $\Phi :S\rightarrow \mathbb {R}$ כך ש- $\forall _{s\in S}\forall _{s_{i},s'_{i}\in S_{i}}u_{i}(s'_{i},s_{-i})-u_{i}(s_{i},s_{-i})=\Phi (s'_{i},s_{-i})-\Phi (s_{i},s_{-i})$

משחק $G=(N,S=S_{1}\times ...\times S_{N},u:S\rightarrow \mathbb {R} ^{N})$ הוא משחק פוטנציאל אורדינלי, אם קיימת פונקציה $\Phi :S\rightarrow \mathbb {R}$ כך ש- $\forall _{s\in S}\forall _{s_{i},s'_{i}\in S_{i}}u_{i}(s'_{i},s_{-i})>u_{i}(s_{i},s_{-i})\iff \Phi (s'_{i},s_{-i})>\Phi (s_{i},s_{-i})$

חשיבות

• עבור משחק פוטנציאל, בעיית הכרעת קיום נקודת שיווי משקל טהור היא טריוויאלית. זאת בעוד שבמקרה הכללי, בעיית זו היא בעיה PPAD שלמה.

תכונות עיקריות

• בכל משחק פוטנציאל סופי, קיימת לפחות נקודה אחת בה מתקיים שיווי משקל נאש טהור.
• אם G משחק פוטנציאל מדויק, אזי כל פונקציות הפוטנציאל של G שוות עד כדי קבוע.
• כל משחק פוטנציאל סופי הוא איזומורפי למשחק עומס. והפוך, כל משחק עומס הוא משחק פוטנציאל מדויק.
• בעיית מציאת נקודת שיווי משקל נאש טהור במשחק פוטנציאל היא PLS שלמה, זאת בעוד שבמקרה הכללי, בעיית מציאת נקודת שיווי משקל נאש (מעורב) היא PPAD שלמה.

דוגמאות

דוגמה למשחק פוטנציאל מדויק הוא משחק דילמת האסיר:

דילמת האסיר

p1/p2	D	C
C	(0,5)	(3,3)
D	(1,1)	(5,0)

במקרה זה, פונקציית הפוטנציאל תראה כך:

פונקציית הפוטנציאל

	D	C
C	4+K	2+K
D	5+K	4+K

עבור $K$ קבוע כלשהו.

דוגמה למשחק פוטנציאל אורדינלי שאינו משחק פוטנציאל מדויק:

p1/p2	D	C
C	(0,5)	(3,3)
D	(2,1)	(5,0)

עבור משחק זה, פונקציית הפוטנציאל כפי שהוגדרה עבור דילמת האסיר היא פונקציית פוטנציאל אורדינלי, אך אינה פונקציית פוטנציאל מדויקת. למעשה, לא קיימת פונקציית פוטנציאל מדויקת עבור המשחק.

משחק פוטנציאל אורדינלי מוכלל

משחק $G=(N,S=S_{1}\times ...\times S_{N},u:S\rightarrow \mathbb {R} ^{N})$ הוא משחק פוטנציאל אורדינלי מוכלל, אם קיימת פונקציה $\Phi :S\rightarrow \mathbb {R}$ כך ש- $\forall _{s\in S}\forall _{s_{i},s'_{i}\in S_{i}}u_{i}(s'_{i},s_{-i})>u_{i}(s_{i},s_{-i})\implies \Phi (s'_{i},s_{-i})>\Phi (s_{i},s_{-i})$

ההגדרה שונה (חלשה) מהגדרת משחק פוטנציאל אורדינלי (לא מוכלל) בהתייחסותה למקרים בהם תועלת השחקן ששינה אסטרטגיה אינה משתנה. במשחק פוטנציאל אורדינלי, ערך פונקציית הפוטנציאל צריך גם הוא שלא להשתנות, בעוד במשחק פוטנציאל אורדינלי מוכלל, ערך הפונקציה יכול לעלות, לרדת או לא להשתנות. עבור משחק סופי, הגדרה זו שקולה לכך שכל סדרה של "שיפורי תועלת" היא סופית. כש"שיפור תועלת" הוא שינוי אסטרטגיה על ידי שחקן כלשהו, כך שערך התועלת של השחקן עולה.

חשיבות ההגדרה היא שבדומה למשחק פוטנציאל (אורדינלי או מדויק), גם במשחק פוטנציאל אורדינלי מוכלל מובטח קיום נקודת שיווי משקל נאש טהור.

דוגמה למשחק פוטנציאל אורדינלי מוכלל, שאינו משחק פוטנציאל אורדינלי:

p1/p2	B	A
C	(2,0)	(1,0)
D	(0,1)	(2,0)

במקרה זה, פונקציית פוטנציאל אורדינלי צריכה לקיים תנאי בלתי אפשרי:

($\phi (C,A)<\phi (D,A)<\phi (D,B)<\phi (C,B)=$$\phi (C,A$

קישורים חיצוניים

• נעם ניסן, סיבוכיות ושיווי משקל נאש