קדם גרעינון

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

סימונים

יהי $\ (N;v)$ משחק בצורה קואליציונית כאשר $N=\{1,\ldots ,n\}$ קבוצת השחקנים.

מבנה קואליציוני הוא חלוקה ${\mathcal {B}}$ של קבוצת השחקנים $\ N$ .

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

הסדר האלפביתי

ערך מורחב – סדר אלפביתי

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

הגרעינון

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

לכל וקטור $x\in \mathbb {R} ^{n}$ , $\ e_{v}(S,x)=v(S)-x(S)$ נקרא העודף (excess) של הקואליציה $\ S$ ב- $\ x$ (ביחס לפונקציה הקואליציונית $\ v$ ). העודף $\ e(S,x)$ (נשמיט את $\ v$ כאשר ברור על איזו פונקציה קואליציונית מדובר) מהווה מדד לחוסר שביעות הרצון של חברי הקואליציה $\ S$ מוקטור התשלומים $\ x$ . ככל שהעודף גדול יותר כך גדלה מידת חוסר שביעות הרצון.

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

\theta (x)=(e(S_{1},x),e(S_{2},x),\ldots ,e(S_{2^{n}},x))\quad :\quad e(S_{i},x)\geq e(S_{i+1},x)\ \forall i

כאשר $S_{1},S_{2},\ldots ,S_{2^{n}}$ הן כל הקואליציות ב- $\ N$ , ויש לשים לב שהסדר שלהן נקבע רק עדי כדי שוויון בין העודפים.

הגרעינון של המשחק $\ (N;v)$ ביחס לקבוצה $\ K$ הוא אוסף הווקטורים $x\in K$ הממזערים את העודפים ביחס הלקסיקוגרפי:

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

הגרעינון ${\mathcal {N}}(N;v)$ הוא הגרעינון ביחס לקבוצת וקטורי התשלומים, והקדם גרעינון ${\mathcal {PN}}(N;v)$ הוא הגרעינון ביחס לקבוצת וקטורי הקדם תשלומים.

תכונות

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

קיום ויחידות

משפט: תהי $K\in \mathbb {R} ^{N}$ קבוצה סגורה (ולא ריקה). אם קיים מספר ממשי $\ c$ כך ש- $\ x(N)=c$ לכל $x\in K$ אזי הגרעינון ביחס ל- $\ K$ אינו ריק.

קל לראות שקבוצת וקטורי הקדם תשלומים $\ X^{0}(N;v)$ מקיימת את התנאי לעיל, ולכן נסיק מיד כי הקדם גרעינון ${\mathcal {PN}}(N;v)$ אינו ריק (קיום).

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

ברור שקבוצת וקטורי הקדם תשלומים $\ X^{0}(N;v)$ היא קמורה, ולכן הקדם גרעינון ${\mathcal {PN}}(N;v)$ מכיל לכל היותר נקודה אחת (יחידות).

לפיכך הקדם גרעינון הוא אכן מושג פתרון נקודתי, ולכן נתייחס ל- ${\mathcal {PN}}(N;v)$ בתור וקטור (במקום כיחידון).

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

סימטריה

משפט: הקדם גרעינון מקיים את עקרון הסימטריה. כלומר אם $i,j\in N$ שחקנים סימטריים, אזי ${\mathcal {PN}}_{i}(N;v)={\mathcal {PN}}_{j}(N;v)$ .

ובאופן יותר כללי -

משפט: הקדם גרעינון מקיים את עקרון האנונימיות.

שחקן האפס

משפט: הקדם גרעינון מקיים את עקרון שחקן האפס. כלומר אם $i\in N$ שחקן אפס, אזי ${\mathcal {PN}}_{i}(N;v)=0$ .

ובאופן יותר כללי -

משפט: אם $i\in N$ שחקן גולם, אזי ${\mathcal {PN}}_{i}(N;v)=v(\{i\})$ .

קווריאנטיות תחת שקילות אסטרטגית

משפט: הקדם גרעינון מקיים את עקרון הקווריאנטיות תחת שקילות אסטרטגית. כלומר לכל $\ a>0$ ולכל $b\in \mathbb {R} ^{n}$ מתקיים ${\mathcal {PN}}(N;av+b)=a{\mathcal {PN}}(N;v)+b$ .

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

הגרעינון לעומת הקדם גרעינון

הקדם גרעינון "מחפש" את וקטורי התשלום שממזער את התלונות בתוך מאגר כל וקטורי התשלום היעילים. הגרעינון של המשחק, עושה זאת במאגר כל וקטורי התשלום היעילים והסבירים פרטית. לפיכך, מבחינה לקסיקורפית, הקדם גרעינון ממזער יותר את התלונות. כלומר: $\theta ({\mathcal {PN}})\precsim _{L}\theta ({\mathcal {N}})$ .

תנאים מספיקים לשוויון

אם וקטור הקדם גרעינון סביר פרטית, אז הוא מוכל בקבוצת וקטורי התשלומים $\ X(N;v)$ , ולכן בגרעינון.

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

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

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

דוגמה להבדל

נתבונן במשחק המוגדר בטבלה. מאחר שיש וקטור יחיד שהוא גם יעיל וגם סביר פרטית, הוא הגרעינון של המשחק. בעמודה האחרונה רואים דוגמה לוקטור יעיל $\ y$ שממזער את התלונות יותר מאשר הגרעינון. אך הקדם הגרעינון ממזער את התלונות לפחות כמו $\ y$ . לכן בסה"כ $\theta ({\mathcal {PN}})\precsim _{L}\theta (y)\prec _{L}\theta ({\mathcal {N}})$ . כלומר, בדוגמה זו הגרעינון של המשחק והקדם גרעינון שונים.

$e\left(S,y=\left(1,-1,2\right)\right)$	$e\left(S,{\mathcal {N}}=\left(2,0,0\right)\right)$	$v\left(S\right)$	$S$
1	0	2	$\left\{1\right\}$
1	0	0	$\left\{2\right\}$
2-	0	0	$\left\{3\right\}$
0	2-	0	$\left\{1,2\right\}$
1	2	4	$\left\{1,3\right\}$
1	2	2	$\left\{2,3\right\}$
0	0	2	$\left\{1,2,3\right\}$