משחק מיקוח

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Gnome-edit-clear.svg ערך זה זקוק לעריכה: הסיבה לכך היא: דרושה עריכה וויקיזציה מקיפה; תת-ניסוח; לא ברור.
אתם מוזמנים לסייע ולתקן את הבעיות, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה.

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

הגדרה פורמלית[עריכת קוד מקור | עריכה]

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

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

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

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

פתרון משחק המיקוח[עריכת קוד מקור | עריכה]

פתרון לבעית המיקוח הוא פונקציה \varphi המתאימה לכל בעיית מיקוח (S,d) נקודה בS.

פתרון נאש למשחק המיקוח[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – פתרון נאש

בשנת 1950 הציע‏[1] ג'ון נאש מספר אקסיומות שצריך לקיים פתרון למשחק מיקוח:

  1. סימטריה: במשחק סימטרי, הפתרון ייתן תשלום זהה לשני השחקנים. משחק סימטרי הוא משחק בו הקבוצה 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 \ge x_1 ,y_2 \ge 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 \in S עבורה המלבן שהיא קודקודו הימני העליון, והנקודה d היא קודקודו השמאלי התחתון, מקבל שטח מקסימלי. העובדה שהקב' S קומפקטית מבטיחה שהמקסימום אכן מתקבל בה, ואילו הקמירות שלה מבטיחה שזה הינו יחיד.

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

דרישות אפשריות נוספות[עריכת קוד מקור | עריכה]

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

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

פתרון קלעי-סמורודינסקי[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – פתרון קלעי סמורודינסקי

בשנת 1975 הציגו‏[2] אהוד קלעי ומאיר סמורודינסקי פתרון שונה מזה של נאש. השניים החליפו את אקסיומת האי-תלות באפשרויות לא רלוונטיות בדרישת מונוטוניות. כדי לתאר את הפתרון, נסמן 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 S היא נקודת אי-ההסכמה, המייצגת את התוצאה שתבחר במידה והמשא ומתן לא יצליח.
  • יש 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 \ne i,j} \in \mathbb{R}^{n-2} \; . \; (x_i,x_j,(x_k)_{k \ne 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) \;, כפי שהוגדר מקודם.

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ John Nash, "The Bargaining Problem", Econometrica, 1950
  2. ^ Ehud Kalai and Meir Smorodinsky, "Other Solutions to Nash's Bargaining Problem", Econometrica, 1975