פתרון קלעי סמורודינסקי

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

משפחת המשחקים הרלונטיים לפתרוןעריכה

נגדיר משפחה   של משחקי מיקוח   המקיימים את התכונות הבאות:

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

שתי התכונות הראשונות זהות לדרוש על ידי פתרון נאש.

עקרונות הפתרוןעריכה

פתרון קלעי סמורודינסקי חולק עם פתרון נאש את שלושת העקרונות הראשונים:

עקרון הסימטריהעריכה

משחק מיקוח   הוא סימטרי אם הוא מקיים את התנאים הבאים:

  •  . כלומר, נקודת אי ההסכמה סימטרית.
  •  . כלומר, נקודה שייכת ל־  אם ורק אם הנקודה הסימטרית לה סביב האלכסון הראשי אף היא ב־ .

פתרון   מקיים את עקרון הסימטריה אם לכל משחק מיקוח סימטרי   הפתרון אף הוא סימטרי:  .

עקרון היעילותעריכה

נקודה   היא יעילה ב   אם לא קיימת נקודה אחרת   עבורה  . כלומר, עבור משחק מיקוח (S,d), נאמר כי נקודה היא יעילה ב   אם לא קיימת נקודה אחרת ב-  שעבורה ניתן להגדיל את התועלת של לפחות אחד השחקנים מבלי לפגוע בתועלת של השחקן השני.
פתרון   מקיים את עקרון היעילות אם לכל משחק מיקוח   הנקודה   היא יעילה.

עקרון הקווריאנטיות תחת טרנספורמציות אפיניות חיוביותעריכה

פתרון   מקיים את עקרון הקווריאנטיות תחת טרנספורמציות אפיניות חיוביות אם לכל משחק מיקוח   ולכל שני ווקטורים
  כך ש־  מתקיים:  

עקרון המונוטוניות החלשהעריכה

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

נקודת אוטופיהעריכה

נגדיר נקודת אוטופיה   במשחק  :

  •  
  •  

כלומר, זוהי הנקודה בעלת ערכי הקואורינטות הגדולים ביותר המתקבלים על ידי נקודות ב־ .

פתרון   מקיים את עיקרון המונוטוניות החלשה אם לכל שני משחקי מיקוח   המקיימים:

  •  
  •  

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

אפיון הפתרוןעריכה

 
דוגמה לפתרון בשיטת קלעי-סמורודינסקי

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

ראו גםעריכה

לקריאה נוספתעריכה