משחק סדר

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

דוגמה[עריכת קוד מקור | עריכה]

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

מס' סידורי שחקן זמן לימוד הפסד ליום (ברופי)
1 A 3 300
2 B 4 250
3 C 2 400

לפי הסידור הנוכחי, הפסדו של A הוא 900 רופי, הפסדו של B הוא 1750 רופי והפסדו של C הוא 3600 רופי. אם B ו-C יחליפו את הסדר ביניהם, אזי ההפסד של C ירד ל-2000 רופי, בעוד שההפסד של B יעלה ל-2250 רופי. סך ההפסדים של השניים יקטן ב-1100 רופי. לכן אם C יפצה את B ב-1000 רופי, שניהם ירוויחו. נשים לב כי A ו-C אינם יכולים להתחלף ללא הסכמת B. באופן דומה ניתן לחשב את הסידור האופטימלי אליו ניתן להגיע על ידי שינוי סדר השחקנים. נאמר כי סידור חדש של השחקנים קביל עבור קואליציה אם תחת שני הסידורים (החדש והמקורי) משך הזמן עד שיסתיים הלימוד אצל כל שחקן שאינו חבר בה אינו משתנה. למשל הסידור שבו C ראשון, B שני ו-A שלישי קביל עבור הקואליציה {A,B,C} אך אינו קביל עבור הקואליציה {A,C}. ניתן להתאים למשחק סדר משחק בצורה קואליציונית שבו שוויה של קואליציה S הוא סכום הכסף שיכולים חברי הקואליציה לחסוך על ידי קביעת סדר שקביל עבור S. הפונקציה הקואליציונית המתאימה לדוגמה שתיארנו היא:

v(A)=0
v(B)=0
v(C)=0
v(A,B)=0
v(A,C)=0
v(B,C)=1100
v(A,B,C)=1700

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]