משחק זרימה

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

הגדרה

תהי $(V,E,s,t,c)$ רשת זרימה, תהי $N$ קבוצת שחקנים סופית ותהי $I$ פונקציה המתאימה לכל קשת בגרף המכוון $(V,E)$ שחקן השולט עליה.

משחק הזרימה המתאים לבעיית הזרימה $F=(V,E,s,t,c,N,I)$ הוא משחק בצורה קואליציונית $(N;v)$ שבו השווי $v(S)$ של קואליציה $S$ הוא כמות הזרימה המקסימלית שחברי $S$ יכולים להעביר מ- $s$ ל- $t$.

משחק בצורה קואליציונית $(N;v)$ המהווה משחק זרימה של איזושהי בעיית זרימה, נקרא משחק זרימה.

דוגמה

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

במשחק הזרימה המתאים לבעיית הזרימה לעיל מתקיים:

$v(1)=0$
$v(2)=2$
$v(3)=0$
$v(1,2)=3$
$v(1,3)=2$
$v(2,3)=2$
$v(1,2,3)=4$

תכונות

התנאים הבאים שקולים עבור משחק $(N;v)$:

• המשחק $(N;v)$ הוא משחק זרימה
• המשחק $(N;v)$ הוא משחק מאוזן לחלוטין ובפרט הליבה שלו אינה ריקה
• המשחק $(N;v)$ הוא משחק שוק
• המשחק $(N;v)$ הוא מינימום של מספר סופי של משחקים אדיטיביים (ראו: משחק אדיטיבי)

לקריאה נוספת

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