הצגת המקור של הדף "משחק עומס"

'''ב[[תורת המשחקים]], משחק עומס''' '''(Congestion game)''' הוא מקרה פרטי של [[משחק פוטנציאל]], ובפרט [[משחק פוטנציאל מדויק]]. המושג, המשחק, הוגדר על ידי רוברט ו. רוזנטל והוצג לראשונה במאמרו בשנת 1973.{{הערה|1=] R.W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International
Journal of Game Theory, 2(1):65–67, 1973.}}<ref>{{צ-מאמר|מחבר=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|קישור=https://doi.org/10.1007/BF01737559}}</ref>
<br />במשחק עומס קיימים משאבים עם מחיר שתלוי במספר השחקנים המשתמשים בו כשהמחיר המשולם על ידי כל שחקן הוא סכום המחירים של המשאבים אשר הוא מחזיק.{{ש}}דוגמה למשחק עומס היא תנועה ברשת כבישים - כאשר השחקנים הם הנהגים, המשאבים הם הכבישים, המחיר הוא העומס בכביש והאסטרטגיה היא מסלול הנסיעה וכל נהג נוסף שנוסע בכביש מעלה את המחיר, העומס, (=הזמן) המבוזבז על ידי כל נהג.

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

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

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

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

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

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

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

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

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

==משחק עומס כמשחק פוטנציאל==
כל משחק עומס הוא משחק פוטנציאל. המסקנה הנגזרת מכך היא שלכל משחק עומס קיים [[שיווי משקל נאש]] טהור.{{ש}}ההוכחה לכך די פשוטה ומסתכמת בהגדרת פונקציית הפוטנציאל כך: <math>\phi(s) = \sum_{e \in E}\sum_{j=1}^{x_{e}}C_{e}(j)</math><br />מה שאומר שפונקציית הפוטנציאל של המשחק מוגדרת כ"מחיר הכללי" של המערכת.

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

==ראו גם==
*[[משחקי בניית רשת]]

==לקריאה נוספת==
*סיכום שיעור של [[ישי מנצור]] על [http://www.math.tau.ac.il/~mansour/course_games/scribe/lecture6.pdf משחקי עומס ופוטנציאל].
*סיכום שיעור בקורס נושאים בגבול כלכלה וחישוב (האוניברסיטה העברית) בנושא [https://web.archive.org/web/20120407055553/http://pluto.huji.ac.il/~mfeldman/hujieconcs/lecture2.pdf משחקי עומס ופוטנציאל ]

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:תורת המשחקים]]