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

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

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

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

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

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

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

יהי G=(N,S=S_1\times\cdots\times S_N, u: S \rightarrow \reals^N) משחק של N שחקנים, כאשר לשחקן ה-i קבוצת אסטרטגיות S_i, ופונקציית תועלת u_i.

בהינתן \epsilon \geq 0 פרופיל S \in S_1 \times \cdots \times S_N יהיה שיווי משקל-\epsilon אם מתקיים ש u_i(S)\geq u_i(s_i^',s_{-i})-\epsilon

עבור כל s_i^' \in S_i , i \in N.

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

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

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

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

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

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