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

משחק בניית רשת (אנגלית: Network Creation Games / Network Formation Games) הוא מקרה פרטי של משחק עומס בתורת המשחקים. מודל זה הוצג לראשונה על ידי Fabrikant בשנת 2003.

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

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

יהי $\ G=<V,E>$ גרף מכוון, כאשר לכל קשת $e\in E$ יש עלות קבועה $\ c_{e}$. משחק בניית רשת עם n שחקנים על G מוגדר על ידי אוסף של קודקודי מקור וקודקודי יעד. לכל שחקן i מוגדר קודקוד מקור $\ o_{i}$ וקודקוד יעד $\ t_{i}$ (כלומר כל שחקן i מקושר לזוג קודקודים $\ (o_{i},t_{i})\in E\times E$).

כמו כן לכל שחקן i, מרחב האסטרטגיות שלו הוא כל המסלולים $\ P_{i}$ שמחברים את קודקוד המקור שלו לקודקוד היעד. כל שחקן בוחר מסלול $p_{i}\in P_{i}$, כאשר המטרה היא למצוא מסלול בעל עלות מינימלית (עלות של מסלול היא סכום העלויות של הצלעות שמרכיבות את המסלול). העלות של כל צלע במסלול מחולקת בין כל השחקנים שבחרו בה לפי כלל חלוקה כלשהו.

נשתמש בכלל החלוקה הבא: $\ C_{i}(e)=C_{e}/X_{e}$, כאשר $\ X_{e}$ הוא מספר השחקנים שבחרו בצלע $\ e$.

המחיר של אסטרטגיה (כלומר אוסף המסלולים שבחרו כל השחקנים) היא סכום המחירים של המסלולים שנבחרו. $c(s)=\sum _{i=1}^{n}C_{i}(s)$

חשיבות

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

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

1. ככל שיותר שחקנים בוחרים בצלע כלשהי, מחיר השימוש בצלע זו יורד.

2. במשחק בניית רשת עם n שחקנים, מחיר האנרכיה חסום מלמעלה על ידי $PoA\leq n$ (חסם הדוק)

3. במשחק בניית רשת עם n שחקנים, מחיר היציבות חסום מלמעלה על ידי $PoS\leq H(n)$ (חסם הדוק), כאשר $\ H(n)$ מציין את הסכום ההרמוני

קישורים חיצוניים

• A.Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and S. Shenker, "On a Network Creation Game", PODC 2003