משחק מיקוח

בתורת המשחקים, משחק מיקוח או משחק מיקוח נאש (על-שם המתמטיקאי ג'ון פורבס נאש) הוא סוג של משחק שיתופי, המתייחס למצבים בהם שני שחקנים או יותר מנהלים משא ומתן וצריכים להגיע להסכמה בנוגע לאופן חלוקת הרווח, שיכול להיות מוצר או סכום כספי כלשהו. כל שחקן במשחק מיקוח יעדיף להגיע להסכמה מאשר להימנע ממנה, ועליו לדאוג כי היא תשרת במידה המקסימלית את צרכיו.

דוגמאות למצב מסוג זה הן ועד עובדים המנהל משא ומתן עם מנהלי חברה בנוגע להעלאה בשכר, משא ומתן בין שתי קהילות בנוגע לחלוקת שטח משותף ומיקוח בין מוכר וקונה על מחירו של בית. בכל אחד מהמקרים הללו הצדדים יכולים להשיג, מתוך הסכמה, מגוון של פתרונות, אך למשא ומתן ישנו פתרון גם אם הצדדים אינם מגיעים לעמק השווה.

ניתוחן של בעיות מיקוח מסוג זה מתבצעת על ידי חיפוש אחר פתרון שייצג את התועלת, בבחינת רווח, של כל צד.

הגדרה פורמלית

דוגמה למשחק מיקוח בו איש מכירות (ציר X) ואיש רכש (ציר Y) מתמקחים על מחיר של מוצר (לכל היותר 100), התועלת של איש המכירות היא רווחו הנקי, ואילו התועלת של איש הרכש היא כמה הוא חוסך בקנייה. S הוא הישר העובר בין (0,100) ו-(100,0), ו d היא הנקודה (0,0).

בעיית מיקוח של שני שחקנים מוגדרת על ידי מרחב התוצאות השלם, המצוין באמצעות זוג סדור של אלמנטים $(S,d)$, כאשר:

• $\,S\subseteq \mathbb {R} ^{2}$ היא קבוצה סגורה, חסומה וקמורה, אשר מייצגת את כל נקודות ההסכמה האפשריות במשחק. כל נקודה $x$ במרחב הווקטורי $S$ מייצגת הסכם אפשרי, כאשר $x=(x_{1},x_{2})\in S$. כלומר, אם השחקנים יסכימו על הנקודה $x$, השחקן הראשון יקבל תשלום של $x_{1}$, והשחקן השני יקבל תשלום של $x_{2}$.
• $d\in \mathbb {R} ^{2}$ היא נקודת אי-הסכמה או הסטטוס-קוו, המייצגת את התוצאה שתבחר במידה והמשא ומתן לא יצליח.

במקרים רבים מתקיים $d=\left(0,0\right)$. לדוגמה, אם כוכב קולנוע וחברת סרטים אינם מצליחים להגיע להסכם לגבי תנאי העסקתו של הכוכב בסרט חדש, אז כוכב הקולנוע לא יקבל את העבודה וחברת הסרטים לא תקבל את הכוכב.

פתרון משחק המיקוח

פתרון לבעיית המיקוח הוא פונקציה $\varphi$ המתאימה לכל בעיית מיקוח $(S,d)$ תוצאה יחידה, נקודה $x$ כלשהי ב-$S$.
קיימים כמה סוגי פתרונות למשחק מיקוח, כאשר אלו נבדלים זה מזה בהנחות המגדירות את התנאים הרצויים לשם קבלת הסכמה בין השחקנים. בהתייחס ליישומם של פתרונות משחקי מיקוח הרי שחלק מאלו תלויי סיטואציה, תרבות ונורמה.

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

ערך מורחב – פתרון נאש

במאמרים שפרסם בשנת 1950, העוסקים בתורת המיקוח, הציג ג'ון נאש מספר אקסיומות שצריך לקיים פתרון למשחק מיקוח. אקסיומות אלו לטענתו תואמות הליך מיקוח סביר, שישיג עבור כל שחקן את הרווח המקסימלי. בהצבת האקסיומות מתקבל פתרון יחיד לבעיית המיקוח. האקסיומות שהציג נאש הן:

1. סימטריה – במשחק סימטרי, הפתרון ייתן תשלום זהה לשני השחקנים. משחק סימטרי הוא משחק בו הקבוצה $S$ היא סימטרית (כלומר אם $S$ מכילה את הנקודה $(x_{1},x_{2})$, אזי היא מכילה גם את הנקודה $(x_{2},x_{1})$), ונקודה אי ההסכמה $d$ אף היא סימטרית (כלומר מתקבל בה אותו תשלום לשני השחקנים).

   

   בתרשים מתאר בעיית מיקוח סימטרית (S,d). פתרון 𝛗, המקיים את עקרון הסימטריה, יימצא על גבי הקו השחור המודגש.

2. יעילות – הנקודה המתקבלת מן הפתרון עבור משחק מסוים תהיה יעילה. נקודה יעילה היא נקודה שעבורה לא קיימת נקודה אחרת ב-$S$ המעניקה תשלום טוב יותר לאחד השחקנים, ואשר אינה פוגעת בתשלום של השחקן האחר. באופן פורמלי, הנקודה $(x_{1},x_{2})$ היא יעילה אם לא קיימת ב-$S$ נקודה אחרת, $y_{1},y_{2}$, כך שמתקיים $y_{1}\geq x_{1}$ או $y_{2}\geq x_{2}$, ואחד מן האי־שוויונים הוא אי-שוויון ממש. תרשים ב' מתאר משחק מיקוח, ובו מודגשת קבוצת ההסכמים היעילים.

   

   בתרשים מתוארת בעיית מיקוח (S,d). תת-הקבוצה של S, המייצגת את אוסף הנקודות היעילות פארטו, היא הקו השחור המודגש. פתרון 𝛗, המקיים את עיקרון היעילות, שייך לתת קבוצה זו.

3. קווריאנטיות לטרנספורמציות אפיניות חיוביות – לכל משחק מיקוח $(S,d)$ ולכל שני וקטורים $a,b\in \mathbb {R} ^{2}$ המקיימים $a_{1},a_{2}>0$ מתקיים:
   $\varphi (aS+b,ad+b)=a\varphi (S,d)+b$.
4. אי תלות באפשרויות לא רלוונטיות – לכל משחק מיקוח $(S,d)$ ולכל תת-קבוצה $T\subseteq S$ המכילה את הפתרון $\varphi (S,d)\in T$, מתקיים: $\varphi (T,d)=\varphi (S,d)$.

נאש הראה כי קיים פתרון יחיד המוגדר על משפחת כל משחקי המיקוח אשר מקיים את כלל האקסיומות שהוצגו לעיל, הוא פתרון נאש. פתרון נאש מתקבל ע"י:

$$N(S,d)=argmax_{x\in S,d\leq x}(x_{1}-d_{1})(x_{2}-d_{2})$$

מבחינה גאומטרית, פתרון נאש הוא בהכרח נקודה $(x_{1},x_{2})\in S$ שעבורה המלבן שהיא קודקודו הימני העליון, והנקודה $(d_{1},d_{2})\in S$ היא קודקודו השמאלי התחתון, הוא בעל השטח המקסימלי. העובדה שהקבוצה $S$ קבוצה קומפקטית מבטיחה שמקסימום אכן יתקבל בה, ואילו הקמירות של הקבוצה מבטיחה שזה הוא המקסימום היחיד.

דרישות אפשריות נוספות

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

• עקרון הסבירות הפרטית – הפתרון טוב לשני השחקנים לפחות כמו נק' אי ההסכמה.
• אי-תלות ביחידות מדידה – זהו מקרה פרטי של עקרון הקווריאנטיות תחת טרנספורמציות אפיניות. תהי $a=(a_{1},a_{2})\in \mathbb {R} ^{2}$ עם $a_{1},a_{2}>0$. נסמן: $aS=\{(a_{1}x_{1},a_{2}x_{2}):(x_{1},x_{2})\in S\}$ ועבור נק' כלשהי $b\in \mathbb {R} ^{2}$ נסמן $ab=(a_{1}b_{1},a_{2}b_{2})$. אז מתקיים $\varphi (aS,ad)=a\varphi (S,d)$.
• הומוגניות – זו תכונה חלשה יותר מאי-תלות ביחידות מדידה. התכונה דורשת כי לכל משחק מיקוח $(S,d)$ ולכל קבוע $c>0$ יתקיים: $\varphi \left(cS\right)=c\varphi \left(S\right)$.
• סימטריה חזקה – דרישה חזקה מדרישת הסימטריה. עיקרון זה אומר כי לכל משחק מיקוח, פתרון משחק המיקוח תחת שיקוף סביב הקו $y=x$ הוא שיקוף הפתרון סביב ציר זה.
• דרישות אי תלות מוחלשות – אקסיומת האי-תלות באפשרויות לא רלוונטיות עוררה מחלוקת, ומאמרים מאוחרים יותר מזה של נאש ניסו להציע אלטרנטיבות שיחליפוה. ניתן לחשוב על דרישות אי תלות מוחלשות, למשל אי-תלות רק בתוצאות לא סבירות מבחינת השחקנים, בתוצאות לא יעילות, או בתוצאות שגרועות יותר מהפתרון.
• מונוטוניות – דרישה לכך שאם נוסיף תוצאות אפשריות למשחק, הפתרון עבור שני השחקנים יהווה שיפור.
  • עקרון מונוטוניות בנקודת אי ההסכמה, דורש שעבור נקודת אי הסכמה חדשה טובה יותר לשחקן אחד וגרועה יותר לאחר, הפתרון יהווה שיפור עבור השחקן הראשון.
• רציפות – עיקרון זה דורש שלכל משחק מיקוח ולכל מספר ε קיימת δ, כך שאם נגדיל או נקטין את מרחב תוצאות המשחק בשטח הקטן מ-δ, פתרון המשחק לא ישתנה ביותר מ-ε.

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

ערך מורחב – פתרון קלעי סמורודינסקי

בשנת 1975 הציגו אהוד קלעי ומאיר סמורודינסקי פתרון שונה מזה של נאש. השניים החליפו את אקסיומת האי-תלות באפשרויות לא רלוונטיות של נאש בדרישת מונוטוניות. החלפת האקסיומה הובילה לפתרון שונה. כדי לתאר את הפתרון נסמן ב-$g_{1}$ את התשלום המקסימלי ששחקן 1 יכול לקבל במשחק, וב- $g_{2}$ את התשלום המקסימלי ששחקן 2 יכול לקבל. בהתייחס למשתנים אלו, הפתרון $\varphi =(\varphi _{1},\varphi _{2})$ יקיים ${\frac {\varphi _{1}}{\varphi _{2}}}={\frac {g_{1}}{g_{2}}}$.

פתרונות נוספים

• פתרון שלא מקיים אף דרישה – נגדיר את הפונקציה כך: ניקח את פתרון נאש ואז ניקח ממוצע עם d ואם אפשר נוריד לשחקן הראשון שתיים אלא אם כן d משמאל לראשית הצירים או ראשית הצירים היא תוצאה אפשרית, ואז לא נוריד לשחקן הראשון שתיים.
• פתרון מיקוח בשלבים – הפתרון מוגדר כך: מבין הנקודות הסבירות פרטית נבחר את הנקודה הטובה ביותר לשחקן הראשון ואת הנקודה הטובה ביותר לשחקן השני (מבין הנקודות הכי טובות לשחקן A ניקח את התוצאה הכי טובה לשחקן B), וניקח את הממוצע נתייחס לנקודה החדשה בתור נקודת האי הסכמה של המשחק ונמשיך בתהליך. הפתרון של המשחק הוא הגבול של הנקודות האלו. הפתרון מוגדר היטב כיוון שזו סדרה מונוטונית בקבוצה קומפקטית ולכן תתכנס, והממוצע שייך לקבוצה כי היא קמורה.
  

פתרון זה מקיים רציפות, סימטריה חזקה, יעילות, קווריאנטיות תחת טרנספורמציות אפיניות חיוביות, סבירות פרטית, אי תלות באפשרויות גרועות ובלא סבירות ובלא יעילות, מונוטוניות בנקודת האי הסכמה.

• פתרון שוויון הכוח היחסי הכללי – הפתרון מוגדר כך: הפתרון הוא הנקודה היעילה אשר בה שטח הנקודות הטובות מהנקודה, לשחקן הראשון, שהן גם סבירות פרטית, שווה לשטח הנקודות הטובות מהתוצאה לשחקן השני, שהן גם סבירות פרטית.
  

שטח קבוצות אלה מוגדר כי אלו קבוצות סגורות. הנקודה המתקבלת היא יחידה: מאחר שהשטח גדל לטובת השחקן השני ככל שהנקודה היעילה יותר ימנית, ובהתחלה (הנקודה הכי שמאלית) כולו אצל השחקן הראשון, רק בנקודה אחת יתקיים השוויון. הנקודה קיימת כי בנקודה הכי ימנית השטח כולו אצל השחקן השני.

פתרון זה מקיים רציפות, סימטריה חזקה, יעילות, קווריאנטיות תחת טרנספורמציות אפיניות חיוביות, סבירות פרטית, אי תלות באפשרויות גרועות ובלא סבירות, מונוטוניות בנקודת האי הסכמה.

• פתרון שוויון הכוח היחסי – הפתרון דומה לפתרון הקודם אך במקום להשוות את השטחים המדוברים בפתרון הקודם, הפתרון משווה שטחים אלו בחיתוך עם הקבוצה הקמורה שנוצרת מהנקודות היעילות ונקודת אי ההסכמה. פתרון זה מוגדר היטב, מאותן סיבות, כמו הפתרון הקודם.

פתרונות דומים לזה ימצאו מלקיחת הקמור של הנקודות היעילות ונקודת אי ההסכמה עם קבוצת נקודות נוספת, כל עוד זו נקבעת לפי פרופורציות בין הנקודה היעילה הכי שמאלית ונקודת אי ההסכמה (לשחקן השני), ופרופורציות סימטריות בין הנקודה היעילה הכי ימנית ונקודת אי ההסכמה (לשחקן הראשון). כלומר נוסיף קבוצות סימטריות במלבנים אלו לפי פרופורציות, וכל פתרון כזה שומר על כל התכונות.
פתרון זה מקיים רציפות, סימטריה חזקה, יעילות, קווריאנטיות תחת טרנספורמציות אפיניות חיוביות, סבירות פרטית, אי תלות באפשרויות גרועות ובלא סבירות ולא יעילות, מונוטוניות בנקודת האי הסכמה.

משחק מיקוח רב משתתפים

משחק מיקוח עם n שחקנים הוא זוג $(S,d)$ עבורו:

• $\,S\subseteq \mathbb {R} ^{n}$ היא קבוצת כל התוצאות האפשריות בהתקיים משא ומתן מוצלח בין כל השחקנים.
• $d\in \mathbb {R} ^{n}$ היא נקודת אי-ההסכמה, המייצגת את התוצאה שתבחר במידה והמשא ומתן לא יצליח.
• יש $x\in s$ המקיימת $x\gg d$.

נסמן ב-${\mathcal {F}}^{n}$ את משפחת משחקי המיקוח $(S,d)$ עם n שחקנים. פתרון הוא פונקציה $\varphi :{\mathcal {F}}^{n}\rightarrow S$ המתאימה לכל משחק מיקוח $(S,d)\in {\mathcal {F}}^{n}$ נקודה $\varphi (S,d)\in S$.

נבחין כי נקודה ב-$S$ היא תוצאה (הסכם חלוקה) שכלל השחקנים הסכימו עליה יחדיו. מודל המשחק לא לוקח בחשבון את האפשרות שחלק מהשחקנים יתאגדו לקואליציה (אלו הם משחקים בצורה קואליציונית).

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

כדי שיתקיים פתרון נאש עבור משחק מיקוח עם n שחקנים, יש להגדיר, באופן דומה למקרה של משחק מיקוח לשני שחקנים, את אותם העקרונות.

עקרון הסימטריה עבור משחק מיקוח $(S,d)$ רב משתתפים, יתקיים תחת התנאים הבאים:

• נקודת אי ההסכמה היא סימטרית ($d_{1}=d_{2}=d_{3}=...=d_{n}$).
• לכל נקודה $x\in S$ ולכל פרמוטציה $\pi$ של $\{1,2,...,N\}$ מתקיים: $\pi (x)=(x_{\pi (1)},x_{\pi (2)},...,x_{\pi (n)})\in S$

הפתרון $\varphi$ יקיים את עקרון הסימטריה אם לכל משחק סימטרי $(S,d)$ יתקיים $\varphi _{1}(S,d)=\varphi _{2}(S,d)=...=\varphi _{n}(S,d)$

עקרונות היעילות, קווריאנטיות תחת טרנספורמציות אפיניות ו-אי תלות באפשרויות לא רלוונטיות זהים למקרה של משחק מיקוח עם 2 שחקנים.

פתרון נאש עבור משחק עם יותר משני שחקנים

בדומה למקרה עבור שני שחקנים, על משפחת המשחקים ${\mathcal {F}}^{n}$ ניתן להגדיר פתרון אחד ויחיד המקיים את עקרונות נאש (סימטריה, יעילות, קווריאנטיות ואי-תלות), והפתרון הוא $N^{*}(S,d)=argmax_{x\in S,d\leq x}\prod _{k=1}^{n}(x_{k}-d_{k})=argmax_{x\in S,d\leq x}(x_{1}-d_{1})(x_{2}-d_{2})...(x_{n}-d_{n})$

כלומר, $N^{*}(S,d)$ הוא הווקטור $x\in S$ עבורו שטח המלבן (ה-n ממדי) $[d_{1},x_{1}]\times [d_{2},x_{2}]\times ...\times [d_{n},x_{n}]$ הוא מקסימלי

עקרונות נוספים

עקרון העקביות

פתרון $\varphi$ מקיים את עקרון העקביות (consistency) אם לכל משחק מיקוח $(S,d)$ ולכל שני שחקנים שונים $(\varphi _{i}(S,d),\varphi _{j}(S,d))$, $(S,d)$ הוא פתרון משחק המיקוח עם שני שחקנים $({\hat {S}},{\hat {d}})$ המוגדר באופן הבא:

• ${\hat {d}}_{1}=d_{i}$, ${\hat {d}}_{2}=d_{j}$ – נקודת ההסכמה נגזרת מנקודת ההסכמה במשחק המקורי.
• ${\hat {S}}={\Big \{}(x_{i},x_{j})\in \mathbb {R} ^{2}{\Big |}\exists (x_{k})_{k\neq i,j}\in \mathbb {R} ^{n-2}.(x_{i},x_{j},(x_{k})_{k\neq i,j})=\varphi (S,d){\Big \}}$ – קבוצת האפשרויות היא קבוצת כל האפשרויות שבהן השחקנים שאינם i ו-j מקבלים את המוצע להם לפי הפתרון $\varphi$.

עקרון האנונימיות

תהי פרמוטציה $\pi$ על קבוצת השחקנים $\{1,2,...,N\}$. נסמן:

• $\pi (d)=(d_{\pi (1)},d_{\pi (2)},...,d_{\pi (n)})$
• $\pi (S)={\big \{}\pi (x)=(x_{\pi (1)},x_{\pi (2)},...,x_{\pi (n)}){\big |}x\in S{\big \}}\in S$

אזי משחק המיקוח $(\pi (S),\pi (d))$ מתקבל ממשחק המיקוח $(S,d)$ על ידי החלפת שמות השחקנים.

פתרון $\varphi$ מקיים את עקרון האנונימיות (או לחלופין: עקרון אי תלות בשמות השחקנים) אם לכל משחק מיקוח $(S,d)$ ולכל פרמוטציה $\pi$ על קבוצת השחקנים, מתקיים: $\varphi _{i}(S,d)=\varphi _{\pi (i)}(\pi (S),\pi (d))$

הפתרון היחיד המוגדר על קבוצת המשחקים ${\mathcal {F}}^{n}$ ומקיים את עקרונות היעילות, קווריאנטיות תחת טרנספורמציות אפיניות, יעילות ועקביות הוא פתרון נאש $N^{*}(S,d)$, כפי שהוגדר מקודם.

ראו גם

• מונוטוניות (משחק מיקוח)
• פתרון קלעי סמורודינסקי
• חלוקה הוגנת

לקריאה נוספת

• שמואל זמיר, מיכאל משלר, אילון סולן, תורת המשחקים, ירושלים: מאגנס, 2008, מסת"ב 9654932946