משחק בצורה גרפית

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

מודל פורמלי

משחק בצורה גרפית מיוצג על ידי גרף לא מכוון $G$. כל שחקן מתאים לקודקוד בגרף, ויש קשת $(i,j)$ בגרף אם התועלת של שחקן $i$ תלויה באופן ישיר בפעולתו של שחקן $j$. בנוסף, לכל שחקן $i$ מוגדרת פונקציה $u_{i}:\{1\ldots m\}^{d_{i}+1}\rightarrow \mathbb {R}$, כאשר $d_{i}$ היא דרגת קודקוד השחקן בגרף. פונקציה זו מתאימה ערך, הנקרא תועלת, לכל קומבינציה של בחירת אסטרטגיות של שחקן $i$ וכל שכניו.

גודל הייצוג

באופן כללי, גודל הייצוג של משחק בין $n$ שחקנים שלכל אחד מהם $m$ אסטרטגיות הוא $(O(m^{n}$. בצורה גרפית, גודל הייצוג יהיה $(O(m^{d}$ כאשר $d$ הוא הדרגה המקסימלית בגרף.
עבור $d\ll n$ קיבלנו ייצוג שגודלו קטן יותר באופן משמעותי.

דוגמה

נסתכל על מקרה בו כל שחקן תלוי רק בעצמו ובשכן יחיד.

הדרגה המקסימלית בגרף היא 1, ונוכל לייצג את המשחק על ידי $n$ טבלאות (פונקציות), כל אחד בגודל $m^{2}$. גודל הייצוג הכולל יהיה $nm^{2}$. גודל הייצוג בצורה התכסיסית הוא $(O(m^{n}$, ואכן יש כאן הקטנה משמעותית של כמות המידע שנצטרך.

מציאת שיווי משקל נאש

באופן כללי בעיית מציאת שיווי משקל נאש עבור משחק נתון דורשת זמן חישוב אקספוננציאלי בגודל הייצוג.
ניתן להראות שאם הגרף $G$ הוא עץ, הבעיה ניתנת לפתרון בזמן יעיל (פולינומי בגודל הייצוג), למשל על ידי אלגוריתם תכנות דינמי שמתחיל על ידי מציאת שיווי משקל בעלים, ומטפס במעלה העץ.
במקרה הכללי, אם הדרגה המקסימלית היא 3 או יותר, ניתן להראות שהבעיה היא NP-שלמה.

ראו גם

• מונחים בתורת המשחקים
• משחק בצורה תכסיסית