הצגת המקור של הדף "פתרון קלעי סמורודינסקי"

ב[[תורת המשחקים]], '''פתרון קלעי-סמורודינסקי''' (<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>.
כלומר, אם משחק אחד מכיל את השני, הפתרון יהיה טוב לשחקנים לפחות כמו הפתרון הקודם. זהו שינוי לעומת פתרון נאש שאינו מבטיח מונוטוניות זאת.

==אפיון הפתרון==
[[קובץ:Kalai_smorodinsky_example.png|שמאל|ממוזער|250px|דוגמה לפתרון בשיטת קלעי-סמורודינסקי]]
קיים פתרון יחיד  <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>.

== ראו גם ==
* [[מונוטוניות (משחק מיקוח)]]
* [[משחק מיקוח]]
== לקריאה נוספת ==
*{{צ-ספר|מחבר=שמואל זמיר, [[מיכאל משלר]], [[אילון סולן]]|שם=תורת המשחקים|מו"ל=[[הוצאת מאגנס|מאגנס]]|שנת הוצאה=2008|מקום הוצאה=ירושלים|ISBN=9654932946}}
* [http://www.jstor.org/pss/1914280 המאמר של קלעי וסמורודינסקי ב־JSTOR].
[[קטגוריה:תורת המשחקים]]