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

בתורת המשחקים, פתרון קלעי-סמורודינסקי ( ${\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.