גרעינון (משחק שיתופי)

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

מושגי יסוד

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

עודף

הגדרה: לכל וקטור $x\in \mathbb {R} ^{N}$, הגודל $e\left(S,x\right):=v\left(S\right)-x\left(S\right)$ נקרא העודף של קואליציה $\;S\;$ ב-$\;x\;$.

כאשר עבור משחק $\,(N;v)$ ,$\,N$ היא קבוצת השחקנים, ולכל קואליציה לא ריקה $\,S\subseteq N$ מגדירים את הווקטור $\textstyle x\in \mathbb {R} ^{N}$ להיות $x(S)=\textstyle \sum _{i\in S}{x_{i}}$, כאשר $\,x(\emptyset )=0$.

העודף $\;e\left(S,x\right)\;$ הוא מדד לחוסר שביעות הרצון של חברי הקואליציה $\,S$ מהווקטור $\,x$. כאשר העודף חיובי חברי $\,S$ אינם מרוצים מ-$\,x$, שכן הם יכולים להתאגד ביניהם, לקבל $\,v\left(S\right)$ ולחלק ביניהם את הסכום כך שכל אחד מחברי הקואליציה יקבל יותר מאשר היה מקבל ב- $\,x$. כאשר העודף שלילי חברי קואליציה $\,S$ מרוצים מ-$\,x$, וככל שהעודף קטן יותר כך קטנה מידת חוסר שביעות הרצון של חברי $\,S$.

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

$$\,{\mathcal {C}}(N;v)=\left\{x\in \mathbb {R} ^{N}\ :\ x(N)=v(N)\,\ e(S,x)\leq 0\quad \forall S\subseteq N\right\}$$

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

סדר לקסיקוגרפי

יהיו $\,a=(a_{i})_{i=1}^{d}$ ו - $\,b=(b_{i})_{i=1}^{d}$ שני וקטורים ב - $\,\mathbb {R} ^{d}$. נאמר כי $\,\textstyle a\succsim _{L}b$ אם ורק אם $\,a=b$ או שקיים $\,k\in \mathbb {N}$, $\,1\leq k\leq d$ כך שמתקיים $\,a_{k}>b_{k}$ וגם $\,a_{i}=b_{i}$ לכל $\,1\leq i<k$. יחס סדר זה נקרא סדר לקסיקוגרפי. יחס הסדר הלקסיקוגרפי הוא רפלקסיבי, טרנזיטיבי ושלם.

הגדרת הגרעינון

הגדרת וקטור עודפים

לכל וקטור $x\in \mathbb {R} ^{N}$ נחשב את העודפים של כל הקואליציות, ונסדר אותם כוקטור בסדר יורד משמאל לימין:

$$\theta (x)=(e(S_{1},x),e(S_{2},x),...,e(S_{2^{n}},x))$$

כאשר $\left\{S_{1},...,S_{2^{n}}\right\}$ הן כל תתי הקואליציות של $\,N$ וכן $e(S_{1},x)\geq e(S_{2},x)\geq ...\geq e(S_{2^{n}},x)$.

כאשר עוברים לוקטור אחר $\,\theta (y)$ יש צורך בסימון אחר לקואליציות, כלומר:

$$\theta (y)=(e(R_{1},y),e(R_{2},y),...,e(R_{2^{n}},y))$$

כאשר שוב הקואליציות $\,(R_{k})_{k=1}^{2^{n}}$ מסודרות בסדר עודפים יורד, והסדר הוא למעשה פרמוטציה של הסדר הקודם. על מנת לקצר את הסימונים, נסמן את הקואורדינטה ה-$\,k$ של $\theta (x)$ ב- $\theta _{k}(x)$, כלומר:

$$\,\theta (x)=(\theta _{1}(x),\theta _{2}(x),...,\theta _{2^{n}}(x))$$

נשים לב כי בהחלט ייתכן מצב בו $\,\theta (x)=\theta (y)$ בעוד $\,x\neq y$.

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

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

תהי $\,K\subseteq \mathbb {R} ^{N}$ קבוצה סגורה. הגרעינון (nucleolus) ביחס ל-$\,K$ הוא הקבוצה:

$${\mathcal {N}}(N;v;K):=\left\{x\in K\ :\ \theta (x)\precsim _{L}\theta (y)\,\ \forall y\in K\right\}$$

אינטואיציה לגרעינון

דרך אינטואיטיבית להסתכל על מושג הגרעינון: פתרון הגרעינון יתקבל כאשר בורר, המתבקש להמליץ על חלוקת הסכום $\,v(N)$ בין השחקנים משתמש בהליך הבא: תחילה הוא מחפש וקטורי תשלומים $\,x$ שעבורם $\,\theta _{1}(x)$ מינימלי. מכיוון ש-$\,\theta _{1}(x)$ מודד את גובה התלונה המקסימלית כנגד $\,x$, הבורר ממזער גודל זה. מבין כל הווקטורים הממזערים את התלונה המקסימלית, הוא מחפש את הווקטורים הממזערים את התלונה השנייה בגודלה, $\,\theta _{2}(x)$, וכן הלאה.

תכונות הגרעינון

משפט 1

נסמן ${\mathcal {S}}=\left\{S_{1},...,S_{k}\ :\ S_{i}\neq S_{j}\ \forall 1\leq i,j\leq k\,\ i\neq j\right\}$. לכל $\,k$, $\,1\leq k\leq 2^{n}$ מתקיים:

$\theta _{k}(x)=max_{{\mathcal {S}}_{i}}min\left\{e(S_{1},x),...,e(S_{k},x)\ :\ s_{1},...,s_{k}\in {\mathcal {S}}_{i}\right\}$, כאשר $\,1\leq i\leq {\dbinom {2^{n}}{k}}$, כלומר לכל $\,n$ יש $\,{\dbinom {2^{n}}{k}}$ קבוצות של $\,k$ קואליציות שונות.

הוכחה:

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

מסקנה 1

לכל $\,k=1,2,...,2^{n}$ הפונקציה $\,\theta _{k}(x)$ רציפה ב-$\,x$.

הוכחה:

לכל קואליציה $\,S$ הפונקציה $\,e(S,x)=v(S)-x(S)$ היא פונקציה ליניארית ב-$\,x$ ובפרט רציפה. מכיוון שמינימום ומקסימום של מספר סופי של פונקציות רציפות היא פונקציה רציפה, ממשפט ${\mathit {1}}$ נקבל כי $\,\theta _{k}(x)$ היא פונקציה רציפה ב-$\,x$.

משפט 2

לכל קבוצה קומפקטית $\,K\subseteq \mathbb {R} ^{N}$, הגרעינון ביחס ל-$\,K$ אינו ריק.

הוכחה:

מכיוון ש-$\,\theta _{1}$ רציפה, הקבוצה $\,\qquad X_{1}:=\left\{x\in K\ :\ \theta _{1}(x)=min_{\left\{y\in K\right\}}\theta _{1}(y)\right\}$ היא קבוצה קומפקטית לא ריקה. נגדיר בעזרת אינדוקציה לכל $\,k$, $\,2\leq k\leq 2^{n}$ :

$$\,x_{k}:=\left\{x\in X_{k-1}\ :\ \theta _{k}(x)=min_{y\in X_{k-1}}\theta _{k}(y)\right\}$$

באינדוקציה נניח כי הקבוצה $\,X_{k-1}$ היא קבוצה קומפקטית לא ריקה. מכיוון ש-$\,\theta _{k}$ רציפה ומהנחת האינדוקציה, גם הקבוצה $\,X_{k}$ היא קבוצה קומפקטית לא ריקה. ניתן לראות כי הגרעינון של המשחק הוא למעשה $\,X_{2^{n}}$.

מסקנה 2

הגרעינון של המשחק ביחס לכל מבנה קואליציוני הוא קבוצה לא ריקה.

הוכחה

מכיוון שקבוצת וקטורי התשלומים ביחס לכל מבנה קואליציוני היא קבוצה קומפקטית, ממשפט ${\mathit {2}}$ נקבל את המסקנה.

משפט 3

תהי $\,K\subseteq \mathbb {R} ^{N}$ קבוצה סגורה המקיימת את התנאי: קיים מספר ממשי $\,c$ שעבורו $\,\textstyle \sum _{i\in N}x_{i}=c\ ,\ \forall x\in K$, אזי הגרעינון ביחס ל-$\,K$ אינו ריק.

הוכחה:

תחילה נשים לב שהקבוצה $\,K$ המקיימת תנאי זה אינה בהכרח חסומה, ולכן אינה בהכרח קומפקטית. נבחר נקודה $\,y\in K$ כלשהי. נגדיר בעזרת $\,y$ קבוצה קומפקטית $\,{\tilde {K}}$:

יהי $\,y\in K$ וקטור כלשהו. נסמן: $\,\mu =\theta _{1}(y)=max_{S\subseteq N}e(S,y)$. כעת נגדיר את הקבוצה $\,{\tilde {K}}$ להיות:

$$\,{\tilde {K}}=\left\{x\in K\ :\ e(S,x)\neq \mu \ ,\ \forall S\subseteq N\right\}$$

מההגדרה נובע ישירות כי $\,{\tilde {K}}\subseteq K$ וכן כי $\,y\in {\tilde {K}}$, כלומר הקבוצה $\,{\tilde {K}}$ אינה ריקה. יהי $\,z\in K\setminus {\tilde {K}}$, אזי קיימת קואליציה $\,T$ עבורה $\,e(T,z)>\mu$. לכן, נקבל כי $\,\theta _{1}(z)>\mu =\theta _{1}(y)$, כלומר $\,\theta (y)\prec _{L}\theta (z)$. נשתמש בתכונה זו בהמשך.

לסיום נראה כי הקבוצה $\,{\tilde {K}}$ היא קבוצה קומפקטית. מכיוון שקבוצה זו מוגדרת על ידי אי שוויונים ליניאריים חלשים, קבוצה זו היא קבוצה סגורה. נראה כי היא גם חסומה. יהי $\,x\in {\tilde {K}}$. אזי $\,e(S,x)\leq \mu$ לכל קואליציה $\,S$. בפרט זה נכון עבור $\,S=\left\{j\right\}$, ונקבל: $\,\mu \geq e(\left\{j\right\},x)=v(j)-x_{j}$.

לכן, $\,x_{j}\geq v(j)-\mu$ לכל $\,j\in N$. מצד שני, מכיוון ש-$\,\textstyle \sum _{i\in N}x_{i}=c$ מתקיים:

$\,x_{i}=c-\sum _{j\neq i}{x_{j}}\leq c-\sum _{j\neq i}(v(j)-\mu )=c+|N-1|\mu -\sum _{j\neq i}v(j)$

מכאן נובע כי:

$$\,{\tilde {K}}\subseteq \times _{i\in N}\left[v(i)-\mu \ ,\ c+|N-1|\mu -\sum _{j\neq i}v(j)\right]$$

ולכן $\,{\tilde {K}}$ היא קבוצה חסומה.

לסיכום, קיבלנו ש- $\,{\tilde {K}}$ היא קבוצה קומפקטית, מוכלת ב-$\,K$, מכילה את $\,y$ ומקיימת $\,\theta (y)\prec _{L}\theta (z)$ לכל $\,z\in K\setminus {\tilde {K}}$. מכיוון ש- $\,{\tilde {K}}$ קומפקטית, ממשפט ${\mathit {2}}$ נובע שהגרעינון ביחס אליה אינו ריק. כלומר, לכל $\,x$ בגרעינון ביחס ל-$\,{\tilde {K}}$, הווקטור $\,\theta (x)$ קטן מ- או שווה ל- $\,\theta (y)$ בסדר הלקסיקוגרפי, הקטן מ-$\,\theta (z)$ לכל $\,z\in K\setminus {\tilde {K}}$. מכאן נקבל שהגרעינון ביחס ל-$\,{\tilde {K}}$ שווה לגרעינון ביחס ל-$\,K$, כלומר הגרעינון של $\,K$ אינו ריק, כנדרש.

משפט 4

תהי $\,K\subseteq \mathbb {R} ^{N}$ קבוצה קמורה. אזי הגרעינון ביחס ל-$\,K$ מכיל לכל היותר נקודה אחת.

הוכחה:

תהיינה $\,x,y$ שתי נקודות בגרעינון. נראה כי $\,x=y$. נסמן:

$$\,\theta (x)=(e(S_{1},x),e(S_{2},x),...,e(S_{2^{n}},x))\quad ;\quad \theta (y)=(e(R_{1},y),e(R_{2},y),...,e(R_{2^{n}},y))$$

$$\,\theta \left({\frac {x+y}{2}}\right)=\left(e\left(T_{1},{\frac {x+y}{2}}\right),e\left(T_{2},{\frac {x+y}{2}}\right),...,e\left(T_{2^{n}},{\frac {x+y}{2}}\right)\right)$$

מכיוון ש-$\,x$ ו-$\,y$ נמצאים בגרעינון, לפי הגדרת הגרעינון $\,\theta (x)\approx _{L}\theta (y)$, ולכן $\,\theta (x)=\theta (y)$. מכיוון ש-$\,K$ היא קבוצה קמורה, גם $\,{\frac {x+y}{2}}$ נמצאת ב-$\,K$. כמו כן, לכל $\,1\leq k\leq 2^{n}$ מתקיים $\,\theta _{k}(x)=\theta _{k}(y)$. כעת:

$$\,2e\left(T,{\frac {x+y}{2}}\right)=2v(T)-(x+y)(T)=e(T,x)+e(T,y)$$

ומכאן:

$$\,2\theta \left({\frac {x+y}{2}}\right)=\left[e(T_{1},x)+e(T_{1},y)\,,\,e(T_{2},x)+e(T_{2},y)\,,\,...\,,\,e(T_{2^{n}},x)+e(T_{2^{n}},y)\right]$$

מכיוון שהקואליציה $\,S_{1}$ ממקסמת את העודף ב-$\,x$ נקבל כי: $\,e(T_{1},x)\leq e(S_{1},x)$, ומכיוון שהקואליציה $\,R_{1}$ ממקסמת את העודף ב-$\,y$ נקבל כי: $\,e(T_{1},y)\leq e(R_{1},y)$. ראינו כי $\,\theta _{k}(x)=\theta _{k}(y)$, ובפרט $\,e(S_{1},x)=e(R_{1},y)$. מליניאריות העודף נקבל:

$$\,e\left(T_{1},{\frac {x+y}{2}}\right)={\frac {e(T_{1},x)+e(T_{1},y)}{2}}\leq e(S_{1},x)$$

אם $\,e\left(T_{1},{\frac {x+y}{2}}\right)<e(S_{1},x)$ נקבל כי $\,\theta \left({\frac {x+y}{2}}\right)\prec _{L}\theta (x)$ בסתירה לכך ש-$\,x$ בגרעינון. מכאן ש- $\,e\left(T_{1},{\frac {x+y}{2}}\right)=e(S_{1},x)$, ולכן: $\,e(T_{1},x)+e(T_{1},y)=e(S_{1},x)+e(R_{1},x)$ יחד עם מה שראינו קודם, ניתן להסיק כי $\,e(T_{1},y)=e(R_{1},y)\;\And \;e(T_{1},x)=e(S_{1},x)$, ולכן $\,T_{1}$ ממקסמת את העודף גם ב-$\,x$ וגם ב-$\,y$. כלומר, על ידי שינוי סדר הקואליציות ניתן לרשום:

$$\,\theta (y)=[e(T_{1},y)\,,\,e(R_{2}',y)\,,\,...\,,\,e(R_{2^{n}}',y)]\quad ;\quad \theta (x)=[e(T_{1},x)\,,\,e(S_{2}',x)\,,\,...\,,\,e(S_{2^{n}}',x)]$$

כאשר כאן $\,T_{1},S_{2}',...,S_{2^{n}}'$ הם פרמוטציה של הקואליציות $\,S_{1},S_{2},...,S_{2^{n}}$ שבה הוחלפו $\,S_{1}$ ו- $\,T_{1}$ זה בזה, ובצורה דומה עבור $\,T_{1},R_{2}',...,R_{2^{n}}'$. באינדוקציה על $\,k$ ניתן להראות כי לכל $\,k$ מתקיים $\,e(T_{k},x)=e(S_{k},x)$ ו- $\,E(T_{k},y)=e(R_{k},y)$. כלומר מתקיים: $\,e(T,x)=e(T,y)\,\ \forall T\subseteq N$. בפרט, אם נציב $\,T=\left\{i\right\}$ נקבל כי לכל שחקן $\,i$:

$\,v(i)-x_{i}=e(\left\{i\right\},x)=e(\left\{i\right\},y)=v(i)-y_{i}$. לכן נקבל: $\,\forall i\quad ,\quad x_{i}=y_{i}$.

כלומר, קיבלנו כי $\,x=y$ כנדרש.

מסקנה: הגרעינון הוא ערך יחיד

טענה: לכל מבנה קואליציוני $\,{\mathcal {B}}$ הגרעינון של המשחק ביחס למבנה זה מכיל וקטור יחיד.

הוכחה: ממסקנה $\,{\mathit {2}}$ הגרעינון ביחס לכל מבנה קואליציוני אינו ריק. מצד שני, לכל מבנה קואליציוני $\,{\mathcal {B}}$, הקבוצה $\,X({\mathcal {B}};v)$ היא קבוצה קמורה. ממשפט $\,{\mathit {4}}$ הגרעינון ביחס אליה מכיל לכל היותר נקודה אחת.

הגרעינון והליבה

לכל מבנה קואליציוני $\ {\mathcal {B}}$, אם הליבה של $\ {\mathcal {B}}$ אינה ריקה אזי הגרעינון של $\ {\mathcal {B}}$ נמצא בליבה.

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

הגרעינון במשנה

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

תכונות נוספות

הגרעינון של משחק בצורה קואליציונית מוכל בגרעין של המשחק ובקבוצת המיקוח של המשחק.

לקריאה נוספת

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