משחק בצורה תכסיסית – הבדלי גרסאות

 

==הקדמה==

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

 

 

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

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

# מספר ממדי המטריצה הוא כמספר השחקנים.

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

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

 

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

משחק בצורה תכסיסית מוגדר כ- <math> G = (N,(S_i)_{i \in N}, (u_i)_{i\in N}) </math> כאשר

# <math>N = (1,2,\ldots,n)</math> היא קבוצת השחקנים.

המטריצה באופן פורמלי עבור משחק המוגדר <math> G = (N,(S_i)_{i \in N}, (u_i)_{i\in N}) </math> תיבנה באופן הבא:

# מטריצה n ממדית, כמספר השחקנים ב <math>N</math>.

# עבור המטריצה שהוגדרה בגודל <math>|S_{1}|\times |S_{2}|\times\ldots\times |S_{N}|</math>, כל תא במטריצה ייצג בחירת ווקטור תכסיסים ובתוכו הערך <math>u(s_{1},s_{2},\ldots,s_{N})</math> כך ש <math>\forall i</math> מתקיים <math>s_{i} \isin S_{i}</math>, שתוצאתו היא ווקטור התשלומים לכל שחקן בהינתן בחירת תכסיס על ידי כל שחקן.

 

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

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

 

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

* המעבר בין משחק בצורה רחבה למשחק בצורה תכסיסית הוא יחיד ואופן המעבר הוא פשוט. בהינתן משחק בצורה רחבה יוגדר <math> G = (N,(S_i)_{i \in N}, (u_i)_{i\in N}) </math> כך ש <math>N</math> הוא קבוצת השחקנים במשחק המקורי. לכל שחקן <math>i</math> תוגדר קבוצה <math>S_{i}</math> שתכיל את כל התכסיסים האפשריים לשחקן <math>i</math>. ולבסוף <math>u_i</math> תוגדר להיות פונקציה כך שלכל בחירת ווקטור תכסיסים תתן את התשלום של שחקן <math>i</math> במשחק בצורה הרחבה בהינתן שימוש בתכסיסים אלו. אם במשחק בצורה רחבה קיימת הגרלה, בווקטור התשלום תירשם [[תוחלת]] התוצאות האפשריות.

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