משחק עומס

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

דוגמה

הנוסעים רוצים להגיע מהעיר s לעיר t. הכבישים עם פונקציית העומס x הם כבישים רגילים - ככל שיסעו בהם יותר מכוניות הם יהיו יותר עמוסים ולכן זמן הנסיעה יעלה. ואילו הכבישים בעלי פונקציית העומס 1 הם אוטוסטרדות - לא משנה כמה מכוניות יסעו בהם - העיכוב ( שהוא המחיר) יהיה קבוע - זמן הנסיעה. זהו בדיוק משחק עומס אם נגדיר את המשאבים להיות הכבישים, פונקציית העומס להיות פונקציית המשאבים והשחקנים להיות הנוסעים בכביש.

הגדרה פורמלית

בהינתן קבוצת משאבים $E$, ואוסף אסטרטגיות של n שחקנים $S$ כאשר פרופיל האסטרטגיות של שחקן $i$ הוא $s_{i}\subseteq 2^{E}$.
לכל משאב $e\in E$ נגדיר פונקציית עלות $C_{e}:\mathbb {N} \rightarrow \mathbb {R}$ לא יורדת.
לכן לכל שחקן $i$ מוגדרת גם פונקציית עלות $C_{i}(s_{i})=\sum _{e\in s_{i}}C_{e}(X_{e})$

משחק עומס כמשחק פוטנציאל

כל משחק עומס הוא משחק פוטנציאל. המסקנה הנגגזרת מכך היא שלכל משחק עומס קיים שיווי משקל נאש
ההוכחה לכך די פשוטה ומסתכמת בהגדרת פונקציית הפוטנציאל כך: $\phi (s)=\sum _{e\in E}\sum _{j=1}^{x_{e}}C_{e}(j)$
מה שאומר שפונקציית הפוטנציאל של המשחק מוגדרת כ"מחיר הכללי" של המערכת.

תכונות עיקריות

• מחיר היציבות של כל משחק עומס הוא לכל היותר 2.
• קיים תמיד לפחות ש"מ נאש יחיד.

ראו גם

• משחקי בניית רשת

לקריאה נוספת

• סיכום שיעור של ישי מנסור על משחקי עומס ופוטנציאל .
• סיכום שיעור בקורס נושאים בגבול כלכלה וחישוב (האונ' העברית) בנושא משחקי עומס ופוטנציאל