משחק בצורה גרפית
בתורת המשחקים, הצורה המקובלת לייצוג משחק היא על ידי משחק בצורה תכסיסית. ייצוג בצורה גרפית הוא ייצוג אלטרנטיבי למשחק, אשר מיטיב לנצל תכונות מבניות של האינטראקציה בין השחקנים. הייצוג בצורה הגרפית תמציתי יותר מהייצוג בצורה התכסיסית במקרים בהם התועלות של השחקנים תלויות רק במספר מצומצם של שחקנים אחרים, ולא בכל יתר השחקנים במשחק.
מודל פורמלי
משחק בצורה גרפית מיוצג על ידי גרף לא מכוון . כל שחקן מתאים לקודקוד בגרף, ויש קשת בגרף אם התועלת של שחקן תלויה באופן ישיר בפעולתו של שחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} . בנוסף, לכל שחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} מוגדרת פונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u_{i}:\{1\ldots m\}^{d_{i}+1}\rightarrow\mathbb{R}} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_i} היא דרגת קודקוד השחקן בגרף. פונקציה זו מתאימה ערך, הנקרא תועלת, לכל קומבינציה של בחירת אסטרטגיות של שחקן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} וכל שכניו.
גודל הייצוג
באופן כללי, גודל הייצוג של משחק בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n}
שחקנים שלכל אחד מהם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m}
אסטרטגיות הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (O(m^{n}}
. בצורה גרפית, גודל הייצוג יהיה כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d}
הוא הדרגה המקסימלית בגרף.
עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d\ll n}
קיבלנו ייצוג שגודלו קטן יותר באופן משמעותי.
דוגמה
נסתכל על מקרה בו כל שחקן תלוי רק בעצמו ובשכן יחיד.
הדרגה המקסימלית בגרף היא 1, ונוכל לייצג את המשחק על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} טבלאות (פונקציות), כל אחד בגודל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m^{2}} . גודל הייצוג הכולל יהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle nm^{2}} . גודל הייצוג בצורה התכסיסית הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (O(m^{n}} , ואכן יש כאן הקטנה משמעותית של כמות המידע שנצטרך.
מציאת שיווי משקל נאש
באופן כללי בעיית מציאת שיווי משקל נאש עבור משחק נתון דורשת זמן חישוב אקספוננציאלי בגודל הייצוג.
ניתן להראות שאם הגרף הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G}
הוא עץ, הבעיה ניתנת לפתרון בזמן יעיל (פולינומי בגודל הייצוג), למשל על ידי אלגוריתם תכנות דינמי שמתחיל על ידי מציאת שיווי משקל בעלים, ומטפס במעלה העץ.
במקרה הכללי, אם הדרגה המקסימלית היא 3 או יותר, ניתן להראות שהבעיה היא NP-שלמה.