משחק עומס

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

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

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

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

משחק עומס כמשחק פוטנציאל
כל משחק עומס הוא משחק פוטנציאל. המסקנה הנגזרת מכך היא שלכל משחק עומס קיים שיווי משקל נאש טהור.ההוכחה לכך די פשוטה ומסתכמת בהגדרת פונקציית הפוטנציאל כך: מה שאומר שפונקציית הפוטנציאל של המשחק מוגדרת כ"מחיר הכללי" של המערכת.

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

ראו גם
משחקי בניית רשת

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

הערות שוליים

תורת המשחקים