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

בתורת המשחקים, פתרון קלעי סמורודינסקי ${\mathcal {KS}}$ הינו פתרון למשחקי מיקוח, השונה מפתרון נאש. פתרון זה נקרא גם נקודת ההסכמה של קלעי וסמורודינסקי. פתרון זה נוצר כתוצאה מביקורת על העקרונות עליהם התבסס נאש ובראשם עיקרון אי התלות באפשרויות לא רלוונטיות. המשפט המוכיח קיום ויחידות פתרון זה התפרסם על ידי אהוד קלעי ומאיר סמורודינסקי ב 1975.

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

נגדיר משפחה ${\mathcal {F}}_{d}$ של משחקי מיקוח $(S,d)$ המקיימים את התכונות הבאות:

• S קמורה וקומפקטית.
• $\exists x:x\in S,x>>d$. כלומר, קיימת נקודה x ב S כך ש $x_{1}>d_{1},x_{2}>d_{2}$.
• $\forall x\in S,[d_{1},x_{1}]\times [d_{2},x_{2}]\subseteq S$. כלומר, לכל $x\in S$, המלבן המוגדר על ידי x ו-d מוכל בתוך S. תכונה זאת נקראת קומפרהנסיביות.

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

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

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

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

משחק מיקוח $(S,d)$ הוא סימטרי אם הוא מקיים את התנאים הבאים:

• $d_{1}=d_{2}$. כלומר, נקודת אי ההסכמה הינה סימטרית.
• $(x_{1},x_{2})\in S\Leftrightarrow (x_{2},x_{1})\in S$. כלומר, נקודה שייכת ל S אם ורק אם הנקודה הסימטרית לה סביב האלכסון הראשי אף היא ב S.

פתרון $\varphi$ מקיים את עקרון הסימטריה אם לכל משחק מיקוח סימטרי (S,d) הפתרון אף הוא סימטרי: $\varphi _{1}(S,d)=\varphi _{2}(S,d)$.

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

נקודה $x\in S$ היא יעילה ב $S$ אם לא קיימת נקודה אחרת $y\in S$ עבורה $x\leq y$. כלומר, עבור משחק מיקוח (S,d), נאמר כי נקודה היא יעילה ב $S$ אם לא קיימת נקודה אחרת ב-$S$ שעבורה ניתן להגדיל את התועלת של לפחות אחד השחקנים מבלי לפגוע בתועלת של השחקן השני.
פתרון $\varphi$ מקיים את עקרון היעילות אם לכל משחק מיקוח $(S,d)$ הנקודה $\varphi (S,d)$ היא יעילה.

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

פתרון $\varphi$ מקיים את עקרון הקווריאנטיות תחת טרנספורמציות אפיניות חיוביות אם לכל משחק מיקוח $(S,d)$ ולכל שני ווקטורים
$a,b\in \mathbb {R} ^{2}$ כך ש$a_{1},a_{2}>0$ מתקיים: $\varphi (aS+b,ad+b)=a\varphi (S,d)+b$

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

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

נקודת אוטופיה

נגדיר נקודת אוטופיה m במשחק (S,d):

• הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle m_{1}(S)=max\{x_{1}:x\in S,x\geq d\}}
• $m_{2}(S)=max\{x_{2}:x\in S,x\geq d\}$

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

פתרון $\varphi$ מקיים את עיקרון המונוטוניות החלשה אם לכל שני משחקי מיקוח הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle (S,d),(T,d)} המקיימים:

• $S\subseteq T$
• $m_{1}(T)=m_{1}(S),m_{2}(T)=m_{2}(S)\!$

מתקיים $\varphi (T,d)\geq \varphi (S,d)$. כלומר, אם משחק אחד מכיל את השני, הפתרון יהיה טוב לשחקנים לפחות כמו הפתרון הקודם. זהו שינוי לעומת פתרון נאש שאינו מבטיח מונוטוניות זאת.

אפיון הפתרון

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

קיים פתרון יחיד ${\mathcal {KS}}$ עבור משפחת המשחקים ${\mathcal {F}}_{d}$ המקיים את עקרונות הסימטריה, היעילות, אי תלות בטרנספורמציות אפיניות והמונוטוניות החלשה. פתרון זה מתקבל במשחק $(S,d)$ בנקודת החיתוך בין השפה של $S$ ובין הקטע המחבר את $d$ ואת נקודת האוטופיה $m(S)$. בגרסאות אחרות של הפתרון נקבעת נקודת אי ההסכמה כ (0,0) ואז מחלישים את הדרישה לאי תלות בטרנספורמציות אפיניות ומשתמשים בעיקרון אי תלות ביחידות מדידה. עקרון זה דומה לאי תלות אך מאפשר לכפול ב a אך לא מאפשר להוסיף b.

ראו גם

• מונוטוניות (משחק מיקוח)
• משחק מיקוח

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946
• המאמר של קלעי וסמורודינסקי ב JSTOR.