משחק עומס

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

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

משאבים: המשחק כולל משאבים או מתקנים מרובים ששחקנים יכולים לבחור מהם. משאבים אלו יכולים להיות כבישים, נתיבים, ערוצי תקשורת או כל תשתית משותפת אחרת.

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

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

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

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

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

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

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

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

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

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

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

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

^ ] R.W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65–67, 1973.
^ Robert W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, International Journal of Game Theory 2, 1973-12-01, עמ' 65–67 doi: 10.1007/BF01737559

[1] ] R.W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65–67, 1973.

[2] Robert W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, International Journal of Game Theory 2, 1973-12-01, עמ' 65–67 doi: 10.1007/BF01737559

[1]

[2]