שיווי משקל אפסילון

בתורת המשחקים, שיווי משקל אפסילון ($\ \varepsilon$) הוא פרופיל אסטרטגיה שמקיים בקירוב את התנאי של שיווי משקל נאש. $\varepsilon$ הוא מספר המייצג את הקרבה לשווי המשקל במשחק שבו לא מתקיים שווי משקל נאש מדויק, והוא יכול להיות קטן כפי רצוננו. שיווי משקל-ε נפוץ בעיקר במשחקים אקראיים, שעלולים להיות בעלי אורך אין סופי.

קיימים מספר משחקים כאלה ללא שיווי משקל נאש, אבל בעלי שיווי משקל-$\varepsilon$ עבור כל $\varepsilon$ גדול ממש מ-0.

הגדרה

בהינתן משחק וערך $\varepsilon$ לא שלילי, נאמר שפרופיל אסטרטגיה הוא בעל שיווי משקל-$\varepsilon$ אם אף שחקן לא יוכל להרוויח יותר מ $\varepsilon$ על ידי שינוי אסטרטגיה. כל שיווי משקל נאש מהווה שיווי משקל-$\varepsilon$ עבור $\varepsilon =0$.

הגדרה מתמטית:

יהי $G=(N,S=S_{1}\times \cdots \times S_{N},u:S\rightarrow \mathbb {R} ^{N})$ משחק של N שחקנים, כאשר לשחקן ה-i קבוצת אסטרטגיות $S_{i}$, ופונקציית תועלת $u_{i}$.

בהינתן $\varepsilon \geq 0$ פרופיל $S\in S_{1}\times \cdots \times S_{N}$ יהיה שיווי משקל-$\varepsilon$ אם מתקיים ש $u_{i}(S)\geq u_{i}(s_{i}^{'},s_{-i})-\varepsilon$

עבור כל $s_{i}^{'}\in S_{i},i\in N$.

דוגמה

דוגמה למשחק ללא שיווי משקל נאש אבל כן בעל שיווי משקל-$\varepsilon$ לכל $\varepsilon$ גדול מ-0.

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

אין אסטרטגיה של שחקן ב' שיכולה להבטיח תמורה של 1, ולכן במשחק זה לא מתקיים שיווי משקל נאש.

לעומת זאת, בהינתן $\varepsilon >0$ שחקן ב' ינקוט באסטרטגיה הבאה: הוא ינחש פלי בהסתברות של $\varepsilon$ וינחש עץ בהסתברות של $1-\varepsilon$. תוחלת התועלת של שחקן ב' באסטרטגיה זו היא לפחות $1-\varepsilon$ בעוד שראינו שאין אף אסטרטגיה עם תועלת של 1.

מכאן נובע ששחקן ב' לא יכול לשפר את תוחלת הרווח שלו ביותר מ-$\varepsilon$, ולכן זהו שיווי משקל-$\varepsilon$.