משחק עץ פורש

בתורת המשחקים, משחק עץ פורש (minimum cost spanning tree game) הוא משחק שיתופי שבו לכל קואליציה ${\begin{aligned}c(S),S\end{aligned}}$ היא ההוצאה המינימלית הדרושה כדי לחבר את כל חברי ${\begin{aligned}S\end{aligned}}$ לקדקוד הראשית של העץ.

הגדרה

תהי ${\begin{aligned}(N,V,E,v_{0},a,I)\end{aligned}}$ מערכת עץ פורש שבה:

• ${\begin{aligned}N=\{1,2,...,n\}\end{aligned}}$ היא קבוצת שחקנים.
• ${\begin{aligned}(V,E)\end{aligned}}$ הוא גרף סופי קשיר שבו ${\begin{aligned}V=\{v_{1}\,,v_{2}\,...,v_{n-1}\}\end{aligned}}$ היא קבוצת הקודקודים ו- ${\begin{aligned}E=\{e_{1}\,,e_{2}\,...,e_{n}\}\end{aligned}}$ היא קבוצת הקשתות.
• ${\begin{aligned}v_{0}\in V\end{aligned}}$ הוא קדקוד הראשית, או המקור.
• ${\begin{aligned}a:E\rightarrow R_{++}\end{aligned}}$ היא פונקציה המתאימה לכל קשת ${\begin{aligned}e\in E\end{aligned}}$ הוצאה ${\begin{aligned}a(e)\end{aligned}}$ גדולה מ- ${\begin{aligned}0\end{aligned}}$.
• ${\begin{aligned}I:N\rightarrow V\setminus \{v_{0}\}\end{aligned}}$ היא פונקציה המתאימה לכל שחקן קדקוד שאינו המקור.

אוסף קשתות המחבר את חברי קואליציה כלשהי ${\begin{aligned}S\end{aligned}}$ למקור, הוא אוסף המכיל לכל שחקן ${\begin{aligned}i\end{aligned}}$ ב-${\begin{aligned}S\end{aligned}}$, מסלול ${\begin{aligned}I(i)\end{aligned}}$ המוביל מהקדקוד למקור. ההוצאה של אוסף קשתות היא סכום ההוצאות של כל הקשתות באוסף.

תהי ${\begin{aligned}S\end{aligned}}$ קואליציה ו- ${\begin{aligned}C\end{aligned}}$ קבוצת ההוצאות של כל אוספי הקשתות המחברים את חברי הקואליציה למקור.

נסמן ב- ${\begin{aligned}c(S)\end{aligned}}$ את ההוצאה המינימאלית מבין כל ההוצאות של האוספים המחברים את חברי ${\begin{aligned}S\end{aligned}}$ למקור.

משחק עץ פורש ${\begin{aligned}(N;c)\end{aligned}}$ המתאים למערכת עץ פורש, הוא משחק שבו לכל קואליציה ${\begin{aligned}c(S),S\end{aligned}}$ היא ההוצאה המינימלית הדרושה כדי לחבר את כל חברי ${\begin{aligned}S\end{aligned}}$ למקור.

אוסף (או אוספי) הקשתות שההוצאות להקמתו הן ${\begin{aligned}c(S)\end{aligned}}$, הוא עץ ששורשו במקור. עץ זה נקרא עץ ההוצאות המינימליות של הקואליציה ${\begin{aligned}S\end{aligned}}$ ומסומן על ידי ${\begin{aligned}(V^{S},E^{S})\end{aligned}}$.

דוגמה

משחק עץ פורש

נתבונן במערכת עץ פורש הכוללת קודקוד מקור ו-5 שחקנים, ושערכי הקשתות שלה הם:
${\begin{aligned}E=\{e_{1}=1\,,e_{2}=3\,,e_{3}=4\,,e_{4}=3\,,e_{5}=1\,,e_{6}=1\,,e_{7}=1\,,e_{8}=1\,,e_{9}=3\}\end{aligned}}$

ניקח את הקואליציה הכוללת את שחקן 2, שחקן 3, ושחקן 4.

עץ ההוצאות המינימלי של קואליציה זו הוא ${\begin{aligned}e_{1}\,,e_{6}\,,e_{7}\,,e_{8}\end{aligned}}$ וערכו הוא 4. במקרה זה, שחקן 1 הוא "נוסע חופשי": הוא זוכה בחיבור למקור למרות שאינו חבר בקואליציה.

תכונות נוספות

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

נתבונן למשל במקרה פרטי של מערכת עץ פורש בה הפונקציה ${\begin{aligned}I\end{aligned}}$ היא חד חד ערכית ועל ,כלומר כל קודקוד משויך לשחקן אחד ויחיד.

במקרה זה, עץ ההוצאות המינימליות ${\begin{aligned}(V^{N},E^{N})\end{aligned}}$ מכיל ${\begin{aligned}n\end{aligned}}$ קשתות, כאשר לכל שחקן ${\begin{aligned}i\end{aligned}}$ ניתן לשייך את הקשת ${\begin{aligned}e(i)\end{aligned}}$ - הקשת היוצאת ממנו לכיוון ${\begin{aligned}v_{0}\end{aligned}}$.

ניתן להוכיח כי הווקטור ${\begin{aligned}x_{i}:=a(e(i))\end{aligned}}$ נמצא בליבה של משחק העץ הפורש המתאים ולכן היא אינה ריקה.

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

ראו גם

• מונחים בתורת המשחקים

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946