קבוצת המיקוח

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

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

קבוצת המיקוח מכילה את הליבה אבל היא יכולה להכיל גם וקטורי תשלומים מחוץ לליבה.

דוגמה

קבלן צריך שני עובדים כדי לבנות קיר והוא פונה לאבנר, ברוך וגידי בהצעה ששניים מהם יעבדו עבורו. מכיוון שאבנר יותר מנוסה מאשר ברוך וגידי הוא יסיים את העבודה מהר יותר מהשניים האחרים. לכן הקבלן ישלם $\ 500$ ש"ח לזוג הכולל את אבנר וברוך או גידי ו-$\ 250$ ש"ח לזוג ברוך וגידי.

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

נניח ואבנר יציע לברוך לחלק את הרווח כך: $\ (400,100)$, כלומר $\ 400$ ש"ח לאבנר ן-$\ 100$ ש"ח לברוך. ברוך לא יהיה מרוצה כי באפשרותו להציע לגידי ליצור קואליציה ולחלק את הרווח $\ (125,125)$. גידי לבטח יסכים וברוך ירוויח יותר מאשר בהצעתו של אבנר. זהו ערעור של ברוך נגד הצעתו של אבנר.

גם אבנר יכול לערער ולהציע לגידי חלוקה של $\ (410,90)$, אך ברוך יחסום אותו על ידי אותה הצעה של $\ (125,125)$ לגידי. זהו ערעור לא מוצדק כי לברוך יש ערעור נגדי. מצד שני, ערעורו המקורי של ברוך הוא מוצדק, כי אם אבנר יציע לגידי חלוקה בה גידי מקבל לפחות $\ 125$ ש"ח, אבנר כבר יקבל פחות מה-$\ 400$ בהצעתו ואין לאבנר ערעור נגדי.

אם נוצרת קואליציה של אבנר וברוך עם החלוקה $\ (375,125)$, לאף שחקן אין ערעור מוצדק: אם למשל ברוך יציע לגידי ליצור קואליציה עם החלוקה $\ (126,124)$ אז אבנר יציע לגידי את החלוקה $\ (375,125)$ כערעור נגדי. אם אבנר יערער ויציע לגידי חלוקה של $\ (376,124)$, ברוך יחסום אותו עם הערעור הנגדי $\ (125,125)$.

עבור הקואליציה של אבנר וברוך, החלוקה $\ (375,125)$ של הרווח היא החלוקה היחידה בה לאף אחד מהם אין ערעור מוצדק וזהו פתרון קבוצת המיקוח עבור מבנה קואליציוני זה.

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

יהי $\ (N;v)$ משחק בצורה קואליציונית.

• מבנה קואליציוני ${\mathcal {B}}$ הוא חלוקה של קבוצת השחקנים לקואליציות זרות שאיחודן $\ N$.
• $X({\mathcal {B}};v)$ היא קבוצת וקטורי התשלומים ביחס ל-${\mathcal {B}}$:

$X({\mathcal {B}};v):={\Big \{}x\in \mathbb {R} ^{N}:\sum _{i\in B}x_{i}=\sum _{i\in B}v(i)\ \forall B\in {\mathcal {B}},x_{i}\geq v(i)\ \forall i\in N{\Big \}}$ . כלומר, קבוצת כל וקטורי התשלומים שבהם כל שחקן מקבל לפחות את מה שהוא יכול לקבל לבד, וכל קואליציה של ${\mathcal {B}}$ מחלקת את הערך שלה בין חבריה.

• ערעור של שחקן $\ k$ נגד שחקן $\ l$ ב-$\ x$, כאשר $k\neq l$ באותה קואליציה ו-$x\in X({\mathcal {B}},v)$ וקטור תשלומים, הוא זוג סדור $\ (C,v)$ שבו:

1. $\ C$ היא קואליציה, $k\in C,l\notin C$.
2. $y\in \mathbb {R} ^{C}$ הוא וקטור המקיים $y_{i}>x_{i}\ \forall i\in C$, וכן $\sum _{i\in C}y_{i}=v(C)$.

• יהי $\ (C,y)$ ערעור של $\ k$ נגד $\ l$ ב$\ x$. ערעור נגדי של $l$ נגד $k$ הוא זוג סדור $\ (D,z)$ המקיים:

1. $\ D$ היא קואליציה, $l\in D,k\notin D$.
2. $z\in \mathbb {R} ^{D}$ הוא וקטור המקיים $\sum _{i\in D}z_{i}=v(D)$.
3. $z_{i}\geq x_{i}\ \forall i\in D\backslash C$.
4. $z_{i}\geq y_{i}\ \forall i\in D\cap C$.

• ערעור $\ (C,y)$ של $\ k$ נגד $\ l$ ייקרא ערעור מוצדק אם ל-$\ k$ אין ערעור נגדי לו.
• תחת הנחות אלו, קבוצת וקטורי התשלומים ${\mathcal {M}}(N;v;{\mathcal {B}})$ ב-$x({\mathcal {B}},v($ בהם אין לאף שחקן ערעור מוצדק נגד שחקן אחר תיקרא קבוצת המיקוח ביחס למבנה הקואליציוני ${\mathcal {B}}$.

תכונות

• קבוצת המיקוח ביחס למבנה קואליציוני תמיד מכילה את הליבה ביחס לאותו מבנה.
• אם $X({\mathcal {B}};v)$ לא ריק אז גם קבוצת המיקוח ביחס ל-${\mathcal {B}}$ אינה ריקה.
• הגרעינון שייך תמיד לקבוצת המיקוח.
• במשחק קמור, קבוצת המיקוח עבור המבנה הקואליציוני ${\mathcal {B}}=\{N\}$ שווה לליבה.