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

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

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

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

• $S$ קמורה וקומפקטית.
• $\exists x:x\in S,x\gg d$. כלומר, קיימת נקודה $x\in 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)$:

• $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$ מקיים את עיקרון המונוטוניות החלשה אם לכל שני משחקי מיקוח $(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.