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

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

== משפחת המשחקים הרלונטיים לפתרון ==
נגדיר משפחה <math>\mathcal{F}_d</math> של משחקי מיקוח <math>(S,d)</math> המקיימים את התכונות הבאות:
* <math> S </math> קמורה וקומפקטית.
* <math> \exists x: x \in S, x\gg d </math>. כלומר, קיימת נקודה <math>x\in S</math> כך ש <math>x_1>d_1, x_2>d_2</math>.
*<math>\forall x \in S, [d_1, x_1] \times [d_2, x_2] \subseteq S</math>. כלומר, לכל <math>x \in S</math>, המלבן המוגדר על ידי <math> x </math> ו־<math>d</math> מוכל בתוך <math> S </math>. תכונה זאת נקראת קומפרהנסיביות.

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

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

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

===עקרון הסימטריה===
משחק מיקוח <math>(S,d)</math> הוא סימטרי אם הוא מקיים את התנאים הבאים:
:* <math>d_1 = d_2</math>. כלומר, נקודת אי ההסכמה סימטרית.
:* <math>(x_1,x_2) \in S \Leftrightarrow (x_2,x_1) \in S</math>. כלומר, נקודה שייכת ל־<math> S </math> אם ורק אם הנקודה הסימטרית לה סביב האלכסון הראשי אף היא ב־<math> S </math>.

פתרון <math>\varphi</math> מקיים את עקרון הסימטריה אם לכל משחק מיקוח סימטרי <math> (S, d)</math> הפתרון אף הוא סימטרי: 
<math>\varphi_1(S,d)=\varphi_2(S,d)</math>.

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

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

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

====נקודת אוטופיה====
נגדיר נקודת אוטופיה <math> m </math> במשחק <math> (S, d)</math>:
<br/>
* <math>m_1(S) = \max\{x_1:x \in S, x \ge d\}</math>
* <math>m_2(S) = \max\{x_2:x \in S, x \ge d\}</math>
כלומר, זוהי הנקודה בעלת ערכי הקואורינטות הגדולים ביותר המתקבלים על ידי נקודות ב־<math> S </math>.
<br />

פתרון <math>\varphi</math> מקיים את עיקרון המונוטוניות החלשה אם לכל שני משחקי מיקוח <math>(S,d), (T,d)</math> המקיימים:<br />
* <math>S \subseteq T</math>
* <math>m_1(T) = m_1(S), m_2(T) = m_2(S) \! </math>
מתקיים 
<math>
\varphi(T,d) \geq \varphi(S,d)
</math>.
כלומר, אם משחק אחד מכיל את השני, הפתרון יהיה טוב לשחקנים לפחות כמו הפתרון הקודם. זהו שינוי לעומת פתרון נאש שאינו מבטיח מונוטוניות זאת.

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

== ראו גם ==
* מונוטוניות (משחק מיקוח)
* משחק מיקוח
== לקריאה נוספת ==
*
* [http://www.jstor.org/pss/1914280 המאמר של קלעי וסמורודינסקי ב־JSTOR].
קטגוריה:תורת המשחקים