משחק בצורה תכסיסית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
אין תקציר עריכה |
||
שורה 1:
{{בעבודה אקדמית|יעד=31 ביולי 2012}}
משחק בצורה תכסיסית (נקרא גם משחק בצורה אסטרטגית, או משחק מטריצה) הוא תיאור מקובל של משחק ב[[תורת המשחקים]], בו תוצאת המשחק מתוארת כתוצאה ישירה של בחירת [[תכסיס (בתורת המשחקים)|תכסיסים]], או אסטרטגיות, על ידי השחקנים בתחילת המשחק. צורת תיאור זו שימושית כאשר לא מתעניינים בשלבי המשחק, אלא רק בתוצאותיו, ומאפשרת מציאת [[שליטה של אסטרטגיות|תכסיסים שולטים ונשלטים]], כמו גם [[שיווי משקל נאש]], בקלות יחסית.
==הקדמה==
במסגרת [[תורת המשחקים]] קיימות מספר דרכים מקובלות לתאר משחק באופן מתמטי. תיאור מתמטי של משחק מאפשר חקירה [[אלגוריתם|אלגוריתמית]] של המשחק, והסקת מסקנות שימושיות לגביו. כל תיאור משחק צריך לכלול את כל התרחישים האפשריים בו, ואת התשלומים לכל שחקן בסוף כל תרחיש במשחק. עם זאת, שיטות תיאור שונות עשויות לתת ייצוג טבעי במידה שונה למושגים כמו שלבים, סדר פעולות וידיעה שלמה או חלקית.
שתי השיטות הנפוצות לתיאור מתמטי של משחק הן צורה תכסיסית, ו[[משחק בצורה רחבה|צורה רחבה]].
כאשר משחק מתואר בצורה תכסיסית, תכסיס של שחקן מתאר ביחידות את הפעולות בהן ינקוט במהלך המשחק. אם במשחק יש כמה שלבים, תכסיס של שחקן (שנקבע בתחילת המשחק) קובע מראש ביחידות את הפעולה שינקוט השחקן בכל שלב במשחק, בהנתן כל פעולה אפשרית של שחקנים אחרים. לכן, בחירת תכסיסים לכל אחד מהשחקנים קובעת ביחידות תוצאה למשחק.
כאשר משחק מתואר ב[[משחק בצורה רחבה|צורה רחבה]], לעומת זאת, תיאור המשחק הוא כ[[עץ (תורת הגרפים)|עץ]] החלטות, בו כל צומת מייצגת תרחיש אפשרי במשחק, וכל קשת מייצגת פעולה בה יכול לנקוט שחקן באותו תרחיש.
בשל ההבדלים בין שתי צורות ההצגה, הצורה התכסיסית טבעית לתיאור משחקים בעלי שלב אחד, בו השחקנים פועלים במקביל, או ללא ידיעה מראש על פעולות האחרים.
==תיאור לא פורמלי==
משחק בסיסי ניתן לייצוג בצורה תכסיסית על ידי מטריצה (טבלה רב מימדית), הנבנית באופן הבא-
# מספר מימדי המטריצה הוא כמספר השחקנים.
# בכל מימד, המתאים לשחקן, גודל המטריצה הוא כמספר התכסיסים העומדים לרשות השחקן (זכרו כי תכסיס מתאר את פעולת השחקן לכל אורך המשחק).
# כל תא במטריצה מייצג בחירת תכסיסים מסויימת של כל השחקנים. הערך בתוך התא הוא התשלומים המתאימים לכל שחקן בהנתן בחירת התכסיסים (כיוון שכאמור, כל בחירת תכסיסים קובעת תוצאה יחידה למשחק), המיוצגים כ[[וקטור שורה|וקטורים]].
כאשר המשחק הוא בין שני שחקנים, המטריצה המתארת אותו היא טבלה, כאשר כל שורה מתאימה לתכסיס של שחקן א', וכל עמודה מתאימה לתכסיס של שחקן ב'. בתוך כל תא בטבלה רשום זוג מספרים, כל אחד תשלום לשחקן המתאים.
ניתן לתאר משחקים מורכבים יותר בצורה תכסיסית, כגון משחקים בהם מעורב אלמנט של מזל (ובהם וקטור התשלומים מייצג [[התפלגות|התפלגויות]] של תשלומים), או [[הרחבת העירוב של משחק|הרחבה]] המאפשרת [[תכסיס מעורב|תכסיסים מעורבים]], בהם שחקן בוחר התפלגות אשר בעזרתה ייבחר תכסיס.
==שימושים==
בשל פשטות ההצגה של משחק בצורה תכסיסית בעזרת מטריצה, ישנם מספר מסקנות על המשחק שניתנות להסקה בקלות מהצורה התכסיסית. בין השאר:
*ניתן לחפש [[שליטה של אסטרטגיות|תכסיסים שולטים ונשלטים]] בקלות. לדוגמה, במשחק בעל שני שחקנים, על מנת לראות שתכסיס 1 של שחקן א' שולט חזק על תכסיס 2 שלו, כלומר שעבור כל בחירת תכסיסים על ידי שחקן ב', תכסיס 1 מניב תשלום עדיף לשחקן א' מאשר תכסיס 2, כל שיש הוא לבדוק האם בטבלה המייצגת את המשחק כל תא בשורה 1 מכיל תשלום גדול יותר לשחקן א' מאשר התא המקביל לו בשורה 2.
*ניתן למצוא [[שיווי משקל נאש]] במשחק, כלומר בחירת אסטרטגיות עבורה לאף אחד מהשחקנים אין אינטרס להיות היחיד המשנה את האסטרטגיה שלו, על ידי מציאת תא במטריצה שהזזתו בכל מימד, כלומר שינוי תכסיס של שחקן אחד בלבד, לא תעלה את התשלום עבור השחקן המתאים לאותו מימד.
==דוגמה==
נתון המשחק הבא- שני חוואים, א' ו-ב', הם בעליו של שדה. את השדה יש לעבד על מנת לקבל יבול, אותו ימכרו החוואים ויחלקו את הרווחים עליו שווה בשווה. בבוקר יום ראשון, קמים שני החוואים עייפים. כל אחד מהם מתלבט האם לצאת ולעבוד את השדה או לא.
אם אף אחד לא ייצא לעבד את השדה, הוא לא יניב יבול העונה ושני החוואים לא ירוויחו דבר. אם ייעבדו את השדה (אחד החוואים או שניהם), היבול יניב עשרה מטבעות, שיחולקו בין החוואים. כמו כן, כל חוואי נדרש לשלם שני מטבעות עבור הנסיעה באוטובוס אל השדה.
הטבלה המייצגת את המשחק בצורה תכסיסית נראית כך-
{|border="1"
|-
|colspan="2" rowspan="2"|
|colspan="2"| <span style="color: RED;">חוואי ב'</span>
|-
| לעבד || לא לעבד
|-
|rowspan="2"| <span style="color: Blue;">חוואי א'</span> || לעבד || <span style="color: Blue;">3</span>,<span style="color: Red;">3</span> || <span style="color: Blue;">3</span>,<span style="color: Red;">5</span>
|-
| לא לעבד || <span style="color: Blue;">5</span>,<span style="color: Red;">3</span> || <span style="color: Blue;">0</span>,<span style="color: Red;">0</span>
|}
ניתן לראות, לדוגמה, כי אם חוואי א' יחליט לקום ולעבד את השדה, בעוד חוואי ב' יישאר בבית, תוצאת המשחק תהיה תשלום של 5 לשחקן ב', ותשלום של 3 לשחקן א'.
כעת, נשנה מעט את כללי המשחק על מנת להפוך אותו למשחק בעל שלבים. ראשית, חוואי א' קם בבוקר. הוא מחליט אם לצאת לעבד את השדה, שולח הודעה עם החלטתו לעמיתו, ומיד יוצא מהבית, או חוזר לישון, בהתאם להחלטתו. חוואי ב' צריך לקבל את ההחלטה שלו כשהוא יודע מה החלטתו של חוואי א'.
אמנם, המשחק הזה כולל כמה תורות, אך גם הוא ניתן לייצוג בצורה תכסיסית. לחוואי א' יש, כמקודם, שני תכסיסים אפשריים, בעוד לחוואי ב' יש ארבעה: לחזור לישון ויהי מה (נסמן לא לעבד), לצאת לשדה ויהי מה (נסמן לעבד), לעשות מה שעשה חברו (נסמן לחקות), או לעשות ההיפך ממנו (נסמן למרוד). כך נראית הטבלה המתאימה למשחק החדש-
{|border="1"
|-
|colspan="2" rowspan="2"|
|colspan="4"| <span style="color: RED;">חוואי ב'</span>
|-
| לעבד || לחקות ||למרוד||לא לעבד
|-
|rowspan="4"| <span style="color: Blue;">חוואי א'</span> || לעבד || <span style="color: Blue;">3</span>,<span style="color: Red;">3</span> || <span style="color: Blue;">3</span>,<span style="color: Red;">3</span>
|<span style="color: Blue;">3</span>,<span style="color: Red;">5</span>
|| <span style="color: Blue;">3</span>,<span style="color: Red;">5</span>
|-
| לא לעבד || <span style="color: Blue;">5</span>,<span style="color: Red;">3</span> || <span style="color: Blue;">0</span>,<span style="color: Red;">0</span>
| <span style="color: Blue;">5</span>,<span style="color: Red;">3</span>
|| <span style="color: Blue;">0</span>,<span style="color: Red;">0</span>
|}
ניתן לשים לב כי בעמודות המתאימות לתכסיסים "לעבד" ו-"לא לעבד", בהם חוואי ב' פועל ללא התייחסות להחלטת חוואי א', מתקבלות תוצאות זהות לתוצאות במשחק הקודם. זאת משום שבבחירה בתכסיסים אלו, חוואי ב' אינו משתמש בידע שלו לגבי פעולת חוואי א', ולכן אינו מייחס חשיבות לכך שהמשחק הנ"ל מתנהל בתורות. כמו כן, ניתן להבחין בהבדל בין פעולות החוואים (אשר, במקרה של חוואי ב', תלויות בפעולות חוואי א') לבין תכסיסיהם (אשר בייצוג הנ"ל נבחרים מראש, לפני תחילת המשחק).
במשחק זה, בניגוד למשחק הקודם, נראה כי לחוואי ב' קיימת [[שליטה של אסטרטגיות|אסטרטגיה שלטת]], אם יחליט למרוד ולעשות ההיפך מחוואי א', בהינתן כל תכסיס של שחקן א' לא קיים תכסיס אשר יספק תשלום גדול יותר לחוואי ב'. על כן, התכסיס "למרוד" של חוואי ב' מהווה [[שליטה של אסטרטגיות|אסטרטגיה שלטת]] עבורו במשחק.
==הגדרה פורמלית==
משחק בצורה תכסיסית מוגדר כ- <math>\ G=(N,S,u) </math> כאשר
# <math>N</math> היא קבוצת השחקנים.
# <math>S=(S_{1},S_{2},\ldots,S_{N}) </math> היא קבוצת התכסיסים במשחק. לכל שחקן <math>i</math> ששייך לקבוצה <math>N</math> מוגדרת קבוצת תכסיסים <math>\!\ S_i</math>.
# <math>u=(u_{1},u{}_{2},\ldots,u{}_{N})</math> היא קבוצת פונקציות התשלום במשחק. לכל שחקן <math>i</math> ששייך לקבוצה <math>N</math> מוגדרת [[פונקציה]] <math>u_{i}:S_{1}\times S_{2}\times\ldots\times S_{N}\rightarrow\mathbb{R}</math> שמתאימה לכל בחירת תכסיסים של כל השחקנים את התשלום שמפיק השחקן ממנה.
המטריצה באופן פורמלי עבור משחק המוגדר <math>\ G=(N,S,u) </math> תיבנה באופן הבא:
# מטריצה n ממדית, כמספר השחקנים ב <math>N</math>.
# לכל מימד i במטריצה, גודלו יוגדר להיות כמספר איברי <math>S_{i}</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>, שתוצאתו היא ווקטור התשלומים לכל שחקן בהינתן בחירת תכסיס על ידי כל שחקן.
==המעבר בין משחק בצורה רחבה למשחק בצורה תכסיסית==
* המעבר בין משחק בצורה רחבה למשחק בצורה תכסיסית הוא יחיד ואופן המעבר הוא פשוט. בהינתן משחק בצורה רחבה יוגדר <math>\ G=(N,S,u) </math> כך ש <math>N</math> הוא קבוצת השחקנים במשחק המקורי. לכל שחקן <math>i</math> תוגדר קבוצה <math>S_{i}</math> שתכיל את כל התכסיסים האפשריים האפשריים לשחקן. ולבסוף <math>u</math> תוגדר להיות פונקציה כך שלכל בחירת ווקטור תכסיסים תתן את ווקטור התשלומים של המשחק בצורה הרחבה בהינתן שימוש בתכסיסים אלו. אם במשחק בצורה רחבה קיימת הגרלה, בווקטור התשלום תירשם התפלגות התוצאות האפשריות.
* משחק בצורה תכסיסית ניתן לתיאור על ידי משחק בצורה רחבה, אך לא באופן יחיד. לדוגמה, לא ניתן לדעת מתיאור המשחק באופן תכסיסי את סדר פעולות השחקנים לכן אפשר לסדר את סדר השחקנים כרצוננו במעבר בין הצורות. המעבר הטבעי בין תיאור של משחק בצורה תכסיסית למשחק בצורה רחבה, הוא בניית עץ שבו שחקן א' בוחר ענף של אסטרטגיה ולאחר מכן שחקן ב' בוחר ענף של אסטרטגיה וכן הלאה.
שורה 16 ⟵ 104:
*[[משחק בצורה גרפית]]
*[[מונחים בתורת המשחקים]]
==לקריאה נוספת==
*{{צ-ספר|מחבר=שמואל זמיר, [[מיכאל משלר]], [[אילון סולן]]|שם=תורת המשחקים|מו"ל=[[הוצאת מאגנס|מאגנס]]|שנת הוצאה=2008}}
[[קטגוריה: תורת המשחקים]]
{{נ}}
| |||