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

בתורת המשחקים, **פתרון קלעי-סמורודינסקי** (\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 \ge d\}
* m_2(S) = \max\{x_2:x \in S, x \ge 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)
.
כלומר, אם משחק אחד מכיל את השני, הפתרון יהיה טוב לשחקנים לפחות כמו הפתרון הקודם. זהו שינוי לעומת פתרון נאש שאינו מבטיח מונוטוניות זאת.

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

## ראו גם
* מונוטוניות (משחק מיקוח)
* משחק מיקוח
## לקריאה נוספת
*
* המאמר של קלעי וסמורודינסקי ב־JSTOR.
קטגוריה:תורת המשחקים