הצגת המקור של הדף "גרעינון (משחק שיתופי)"

ב[[תורת המשחקים]], '''גרעינון''' הוא מושג [[פתרון (תורת המשחקים)|פתרון]] נקודתי ל[[קואליציה (תורת המשחקים)|משחק בצורה קואליציונית]], הקיים לכל משחק והוצג לראשונה על ידי [[דוד שמיידלר]] ([[1969]]).{{הערה|כיוון=שמאל|{{JSTOR|David Schmeidler|The Nucleolus of a Characteristic Function Game|2099196|SIAM Journal on Applied Mathematics|November 1969, Vol. 17, No. 6}}}} הגרעינון למעשה ממזער את רמת חוסר שביעות הרצון של הקואליציות.

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

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

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

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

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

<math display="block">\, \mathcal {C} (N;v) = \left\{x \in \R^{N}\ :\ x(N)=v(N) \, \ e(S,x) \le 0 \quad \forall S \subseteq N \right\} </math>

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

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

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

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

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

<math display="block">\theta(x)=(e(S_1,x),e(S_2,x),...,e(S_{2^n},x))</math>

כאשר <math>\left\{S_1,...,S_{2^n}\right\}</math> הן כל תתי הקואליציות של <math>\,N</math> וכן <math>e(S_1,x)\ge e(S_2,x)\ge...\ge e(S_{2^n},x)</math>.

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

<math display="block">\theta(y)=(e(R_1,y),e(R_2,y),...,e(R_{2^n},y))</math>

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

<math display="block">\, \theta (x) = (\theta_{1}(x), \theta_{2} (x),..., \theta_{2^n} (x))</math>

נשים לב כי בהחלט ייתכן מצב בו <math>\, \theta (x) = \theta (y)</math> בעוד <math>\, x \ne y</math>.

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

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

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

<math display="block">\mathcal{N}(N;v;K):=\left\{x\in K\ :\ \theta(x) \precsim_{L} \theta(y) \, \ \forall y\in K\right\}</math>

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

דרך אינטואיטיבית להסתכל על מושג הגרעינון: פתרון הגרעינון יתקבל כאשר בורר, המתבקש להמליץ על חלוקת הסכום <math>\,v(N)</math> בין השחקנים משתמש בהליך הבא:
תחילה הוא מחפש [[וקטור תשלומים|וקטורי תשלומים]] <math>\,x</math> שעבורם <math>\, \theta_1(x)</math> מינימלי.
מכיוון ש-<math>\, \theta_1(x)</math> מודד את גובה התלונה המקסימלית כנגד <math>\,x</math>, הבורר ממזער גודל זה.
מבין כל הווקטורים הממזערים את התלונה המקסימלית, הוא מחפש את הווקטורים הממזערים את התלונה השנייה בגודלה, <math>\, \theta_2(x)</math>, וכן הלאה.

==תכונות הגרעינון==
===משפט 1===

נסמן <math>\mathcal {S} = \left\{S_1,...,S_k\ :\ S_i \ne S_j\ \forall 1 \le i,j \le k\, \ i \ne j \right\}</math>. לכל <math>\, k</math>, <math>\, 1 \le k \le 2^{n}</math> מתקיים:

<math> \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\}</math>, כאשר <math>\, 1 \le i \le \dbinom {2^n}{k} </math>, כלומר לכל <math>\, n</math> יש <math>\, \dbinom {2^n}{k}</math> קבוצות של <math>\, k</math> קואליציות שונות.

'''הוכחה:'''

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

===מסקנה 1===

לכל <math>\, k=1,2,...,2^n</math> הפונקציה <math>\, \theta_{k}(x)</math> רציפה ב-<math>\, x</math>.

'''הוכחה:'''

לכל קואליציה <math>\, S</math> הפונקציה <math>\, e(S,x)=v(S)-x(S) </math> היא פונקציה ליניארית ב-<math>\, x</math> ובפרט רציפה. מכיוון שמינימום ומקסימום של מספר סופי של פונקציות רציפות היא פונקציה רציפה, ממשפט <math>\mathit 1</math> נקבל כי <math>\, \theta_k (x)</math> היא פונקציה רציפה ב-<math>\, x</math>.

===משפט 2===

לכל קבוצה קומפקטית <math>\, K \subseteq \R^N</math>, הגרעינון ביחס ל-<math>\, K</math> אינו ריק.

'''הוכחה:'''

מכיוון ש-<math>\, \theta_1</math> רציפה, הקבוצה <math>\,\qquad X_1 := \left\{ x \in K\ :\ \theta_{1} (x) = min_{\left\{y \in K \right\}} \theta_{1} (y) \right\} </math> היא קבוצה קומפקטית לא ריקה. נגדיר בעזרת אינדוקציה לכל <math>\, k</math>, <math>\, 2 \le k \le 2^n </math> :

<math display="block">\, x_k := \left\{ x \in X_{k-1}\ :\ \theta_{k}(x) = min_{y \in X_{k-1}} \theta_{k}(y) \right\}</math>

באינדוקציה נניח כי הקבוצה <math>\, X_{k-1}</math> היא קבוצה קומפקטית לא ריקה. מכיוון ש-<math>\, \theta_k</math> רציפה ומהנחת האינדוקציה, גם הקבוצה <math>\, X_k </math> היא קבוצה קומפקטית לא ריקה. ניתן לראות כי הגרעינון של המשחק הוא למעשה <math>\, X_{2^n} </math>.

=== מסקנה 2===

הגרעינון של המשחק ביחס לכל [[תורת המשחקים - מונחים|מבנה קואליציוני]] הוא קבוצה לא ריקה.

'''הוכחה'''

מכיוון שקבוצת [[ליבה של משחק שיתופי|וקטורי התשלומים]] ביחס לכל מבנה קואליציוני היא קבוצה קומפקטית, ממשפט <math>\mathit 2</math> נקבל את המסקנה.

=== משפט 3===

תהי <math>\, K \subseteq \R^N</math> קבוצה סגורה המקיימת את התנאי: קיים מספר ממשי <math>\, c</math> שעבורו <math>\, \textstyle \sum_{i \in N} x_i = c\ ,\ \forall x \in K </math>, אזי הגרעינון ביחס ל-<math>\, K</math> אינו ריק.

'''הוכחה:'''

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

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

<math display="block">\, \tilde{K} = \left\{x \in K\ :\ e(S,x) \ne \mu\ ,\ \forall S \subseteq N \right\}</math>

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

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

לכן, <math>\, x_j \ge v(j)-\mu </math> לכל <math>\, j \in N</math>. מצד שני, מכיוון ש-<math>\, \textstyle \sum_{i \in N} x_i = c</math> מתקיים:

<math>\, x_i = c - \sum_{j \ne i}{x_j} \le c - \sum_{j \ne i}(v(j) - \mu) = c + |N-1|\mu - \sum_{j \ne i} v(j) </math>

מכאן נובע כי:

<math display="block">\, \tilde{K} \subseteq \times_{i \in N} \left[ v(i) - \mu\ ,\ c + |N-1|\mu - \sum_{j \ne i} v(j) \right] </math>

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

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

===משפט 4===

תהי <math>\, K \subseteq \R^N </math> קבוצה קמורה. אזי הגרעינון ביחס ל-<math>\, K</math> מכיל לכל היותר נקודה אחת.

'''הוכחה:'''

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

<math display="block">\, \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)) </math>

<math display="block">\, \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) </math>

מכיוון ש-<math>\, x</math> ו-<math>\, y</math> נמצאים בגרעינון, לפי הגדרת הגרעינון <math>\, \theta (x) \approx_L \theta (y)</math>, ולכן <math>\, \theta (x) = \theta (y) </math>. מכיוון ש-<math>\, K</math> היא קבוצה קמורה, גם <math>\, \frac{x+y}{2}</math> נמצאת ב-<math>\, K</math>. כמו כן, לכל <math>\, 1 \le k \le 2^n</math> מתקיים <math>\, \theta_k (x) = \theta_k (y)</math>. כעת:

<math display="block">\, 2e \left( T, \frac{x+y}{2} \right) = 2v(T) - (x+y)(T) = e(T,x) + e(T,y) </math>

ומכאן:

<math display="block">\, 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]</math>

מכיוון שהקואליציה <math>\, S_1 </math> ממקסמת את העודף ב-<math>\, x</math> נקבל כי: <math>\, e(T_1,x) \le e(S_1,x) </math>, ומכיוון שהקואליציה <math>\, R_1</math> ממקסמת את העודף ב-<math>\, y</math> נקבל כי: <math>\, e(T_1,y) \le e(R_1,y) </math>. ראינו כי <math>\, \theta_k (x) = \theta_k (y)</math>, ובפרט <math>\, e(S_1,x) = e(R_1,y) </math>. מליניאריות העודף נקבל:

<math display="block">\, e \left(T_1, \frac{x+y}{2} \right) = \frac{ e(T_1,x) + e(T_1,y)}{2} \le e(S_1,x) </math>

אם <math>\, e\left(T_1, \frac{x+y}{2} \right) < e(S_1,x) </math> נקבל כי <math>\, \theta \left( \frac{x+y}{2} \right) \prec_L \theta(x) </math> בסתירה לכך ש-<math>\, x</math> בגרעינון. מכאן ש- <math>\, e \left(T_1, \frac{x+y}{2} \right) = e(S_1,x) </math>, ולכן: <math>\, e(T_1,x) + e(T_1,y) = e(S_1,x) + e(R_1,x)</math> יחד עם מה שראינו קודם, ניתן להסיק כי <math>\, e(T_1,y) = e(R_1,y) \; \And \; e(T_1,x) = e(S_1,x) </math>, ולכן <math>\, T_1</math> ממקסמת את העודף גם ב-<math>\, x</math> וגם ב-<math>\, y</math>. כלומר, על ידי שינוי סדר הקואליציות ניתן לרשום:

<math display="block">\, \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) ]</math>

כאשר כאן <math>\, T_1,S_{2}',...,S_{2^n}' </math> הם פרמוטציה של הקואליציות <math>\, S_1,S_2,...,S_{2^n} </math> שבה הוחלפו <math>\, S_1</math> ו- <math>\, T_1</math> זה בזה, ובצורה דומה עבור <math>\, T_1,R_{2}',...,R_{2^n}' </math>. באינדוקציה על <math>\, k </math> ניתן להראות כי לכל <math>\, k</math> מתקיים <math>\, e(T_k,x) = e(S_k,x) </math> ו- <math>\, E(T_k,y) = e(R_k,y)</math>. כלומר מתקיים: <math>\, e(T,x) = e(T,y) \, \ \forall T \subseteq N</math>. בפרט, אם נציב <math>\, T = \left\{i \right\} </math> נקבל כי לכל שחקן <math>\, i</math>:

<math>\, v(i) - x_i = e(\left\{i \right\},x) = e(\left\{i \right\},y) = v(i) - y_i</math>. לכן נקבל: <math>\, \forall i \quad, \quad x_i = y_i </math>.

כלומר, קיבלנו כי <math>\, x = y </math> כנדרש.

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

טענה: לכל מבנה קואליציוני <math>\, \mathcal B</math> הגרעינון של המשחק ביחס למבנה זה מכיל וקטור יחיד.

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

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

לכל מבנה קואליציוני <math>\ \mathcal B </math>, אם ה[[ליבה של משחק שיתופי|ליבה]] של <math>\ \mathcal B</math> אינה ריקה אזי הגרעינון של <math>\ \mathcal B</math> נמצא בליבה.

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

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

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

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

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

== לקריאה נוספת ==
*{{צ-ספר|מחבר=שמואל זמיר, [[מיכאל משלר]], [[אילון סולן]]|שם=תורת המשחקים|מו"ל=[[הוצאת מאגנס|מאגנס]]|שנת הוצאה=2008|מקום הוצאה=ירושלים|ISBN=9654932946}}

==הערות שוליים==
{{הערות שוליים}}

[[קטגוריה:תורת המשחקים]]