משחק בצורה תכסיסית

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

הקדמה

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

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

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

תיאור לא פורמלי

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

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

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

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

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

משחק בצורה תכסיסית מוגדר כ- $G=(N,(S_{i})_{i\in N},(u_{i})_{i\in N})$ כאשר

1. $N=(1,2,\ldots ,n)$ היא קבוצת השחקנים.
2. $S=(S_{1},S_{2},\ldots ,S_{N})$ היא קבוצת התכסיסים במשחק. לכל שחקן $i$ ששייך לקבוצה $N$ מוגדרת קבוצת תכסיסים $\!\ S_{i}$.
3. $u=(u_{1},u{}_{2},\ldots ,u{}_{N})$ היא קבוצת פונקציות התשלום במשחק. לכל שחקן $i$ ששייך לקבוצה $N$ מוגדרת פונקציה $u_{i}:S_{1}\times S_{2}\times \ldots \times S_{N}\rightarrow \mathbb {R}$ שמתאימה לכל בחירת תכסיסים של כל השחקנים את התשלום שמפיק השחקן ממנה.

המטריצה באופן פורמלי עבור משחק המוגדר $G=(N,(S_{i})_{i\in N},(u_{i})_{i\in N})$ תיבנה באופן הבא:

1. מטריצה n ממדית, כמספר השחקנים ב $N$.
2. לכל ממד i במטריצה, גודלו יוגדר להיות כמספר איברי $S_{i}$.
3. עבור המטריצה שהוגדרה בגודל $|S_{1}|\times |S_{2}|\times \ldots \times |S_{N}|$, כל תא במטריצה ייצג בחירת ווקטור תכסיסים ובתוכו הערך $u(s_{1},s_{2},\ldots ,s_{N})$ כך ש $\forall i$ מתקיים $s_{i}\in S_{i}$, שתוצאתו היא ווקטור התשלומים לכל שחקן בהינתן בחירת תכסיס על ידי כל שחקן.

דוגמה

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

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

הטבלה המייצגת את המשחק בצורה תכסיסית נראית כך-

		חוואי ב'
		לעבד	לא לעבד
חוואי א'	לעבד	3,3	3,5
	לא לעבד	5,3	0,0

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

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

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

		חוואי ב'
		לעבד	לחקות	למרוד	לא לעבד
חוואי א'	לעבד	3,3	3,3	3,5	3,5
	לא לעבד	5,3	0,0	5,3	0,0

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

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

שימושים

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

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

המעבר בין משחק בצורה רחבה למשחק בצורה תכסיסית

• המעבר בין משחק בצורה רחבה למשחק בצורה תכסיסית הוא יחיד ואופן המעבר הוא פשוט. בהינתן משחק בצורה רחבה יוגדר $G=(N,(S_{i})_{i\in N},(u_{i})_{i\in N})$ כך ש $N$ הוא קבוצת השחקנים במשחק המקורי. לכל שחקן $i$ תוגדר קבוצה $S_{i}$ שתכיל את כל התכסיסים האפשריים לשחקן $i$. ולבסוף $u_{i}$ תוגדר להיות פונקציה כך שלכל בחירת ווקטור תכסיסים תתן את התשלום של שחקן $i$ במשחק בצורה הרחבה בהינתן שימוש בתכסיסים אלו. אם במשחק בצורה רחבה קיימת הגרלה, בווקטור התשלום תירשם תוחלת התוצאות האפשריות.
• משחק בצורה תכסיסית ניתן לתיאור על ידי משחק בצורה רחבה, אך לא באופן יחיד. לדוגמה, לא ניתן לדעת מתיאור המשחק באופן תכסיסי את סדר פעולות השחקנים לכן אפשר לסדר את סדר השחקנים כרצוננו במעבר בין הצורות. המעבר הטבעי בין תיאור של משחק בצורה תכסיסית למשחק בצורה רחבה, הוא בניית עץ שבו שחקן א' בוחר ענף של אסטרטגיה ולאחר מכן שחקן ב' בוחר ענף של אסטרטגיה וכן הלאה. לדוגמה, אם נתון משחק בצורה תכסיסית בין שני משתתפים, ובו לכל שחקן שני תכסיסים אפשריים, אזי נוכל לבנות עץ שבו שחקן א' מתחיל ויש לו ענפים לכל אחד מן התכסיסים המובילים לקודקודים שבהם תור שחקן ב' לשחק והם תחת אותה קבוצת ידיעה, מכל אחד משני קודקודים אלו יצאו שני ענפים עם התכסיסים האפשריים של שחקן ב'. סך הכל קיבלנו ארבעה עלים שעליהם נרשום את תשלומי השחקנים, על פי ארבעת תאי המטריצה המקורית. באותה המידה היה ניתן לבחור את שחקן ב' כפותח המשחק ושיוביל לקודקודים שבהם שחקן א' משחק, אך אין זה ישנה את מהות המשחק מאחר שעצם היות הקודקודים תחת אותה קבוצת הידיעה אומר שאינם יודעים מה הייתה הבחירה של השחקן הקודם שדרכו הגיעו למצב הנתון.

ראו גם

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

לקריאה נוספת

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