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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

מודל פורמלי[עריכת קוד מקור | עריכה]

משחק בצורה גרפית מיוצג על ידי גרף לא מכוון 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 קיבלנו ייצוג שגודלו קטן יותר באופן משמעותי.

דוגמה[עריכת קוד מקור | עריכה]

GraphicalGameExample.png

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

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

מציאת שיווי משקל נאש[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]