משפט שפלי-שוביק

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

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

המשפט ההפוך אינו נכון.

הוכחה

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

במהלך ההוכחה נשתמש בסימונים המופיעים בערך משחק שוק.

נסמן ב- $X^{S}$ את קבוצת כל ההקצאות עבור קואליציה $S$:

$X^{S}:=\left\{(x^{i})_{i\in {S}}:x^{i}\in \mathbb {R} _{+}^{L}\quad \forall {i}\in {S},\quad x(S)=a(S)\right\}\subseteq {\mathbb {R} _{+}^{|S|L}}$

כאשר $a(S)=\sum _{i\in {s}}a^{i}$ הוא סך המצרכים העומד לרשות הקואליציה $\ S$.

נגדיר את התשלום לקואליציה $\ S$ בצורה הבאה: $v(S)=max\left\{\sum _{i\in {S}}u_{i}(x^{i}):x=(x^{i})_{i\in {S}}\in {X^{S}}\right\}$, כאשר $\ u_{i}$ היא פונקציית הייצור.
לכל קואליציה $S\neq \varnothing$ נבחר הקצאה $x^{S}=(x^{S,i})_{i\in {S}}\in \mathbb {R} _{+}^{|S|L}$ שבה מתקבל המקסימום בהגדרת $\ v(S)$.

מתקיים:

(i) $x^{S,i}\in \mathbb {R} _{+}^{L}$ לכל שחקן i.

(ii) $x^{S}(S)=\sum _{i\in {S}}x^{S,i}=\sum _{i\in {s}}a^{i}=a(S)$, כאשר $a^{i}\in \mathbb {R} _{+}^{L}$ הוא הסל ההתחלתי של שחקן i.

(iii) $v(S)=\sum _{i\in {S}}u_{i}(x^{S,i})$

נראה כעת כי המשחק הוא משחק מאוזן.

יהי $\delta =(\delta _{S})_{s\in {{\mathcal {D}}^{*}}}\in {P}$, כאשר ${\mathcal {D}}^{*}$ הוא אוסף כל הקואליציות הלא ריקות ב-$\ N$, ו-$\ P$ היא קבוצת כל וקטורי המקדמים המאזנים חלש את ${\mathcal {D}}^{*}$.

צריך להראות כי $v(N)\geq \sum _{S\in {{\mathcal {D}}^{*}}}\delta _{S}v(S)$.
נגדיר:

$\forall {i}\in {N}.\quad z^{i}:=\sum _{\{s\in {{\mathcal {D}}^{*}}:i\in {S}\}}\delta _{S}x^{S,i}$.

נראה כי $z=(z^{i})_{i\in {N}}$ הוא הקצאה אפשרית:

$z^{i}\in \mathbb {R} _{+}^{L}$ כי הוא ממוצע של וקטורים ב-$\mathbb {R} _{+}^{L}$. נותר להראות כי $\ z(N)=a(N)$:

$z(N)=\sum _{i\in {N}}z^{i}=\sum _{i\in {N}}\sum _{\{S:i\in {S}\}}\delta _{S}x^{S,i}=\sum _{S\in {{\mathcal {D}}^{*}}}\sum _{i\in {S}}\delta _{S}x^{S,i}=\sum _{S\in {{\mathcal {D}}^{*}}}\delta _{S}\sum _{i\in {S}}x^{S,i}=\sum _{S\in {{\mathcal {D}}^{*}}}\delta _{S}x^{S}(S)$
מכיוון ש-$\ x^{S}(S)=a(S)$ ועל ידי שינוי סדר סכימה, נקבל:

$z(N)=\sum _{S\in {{\mathcal {D}}^{*}}}\delta _{S}a(S)=\sum _{S\in {{\mathcal {D}}^{*}}}\delta _{S}\sum _{i\in {S}}a^{i}=\sum _{i\in {N}}a^{i}\sum _{\{S:i\in {S}\}}\delta _{S}$

$\ \delta$ הוא וקטור מקדמים מאזנים, כלומר -

$\sum _{\{S:i\in {S}\}}\delta _{S}=1$
לכן -

$z(N)=\sum _{i\in {N}}a^{i}=a(N)$
כלומר $\ z$ הוא אכן הקצאה אפשרית. לכן, מהגדרת $\ v$ ומהגדרת $\ z$ נקבל:

$v(N)\geq \sum _{i\in {N}}u_{i}(z^{i})=\sum _{i\in {N}}u_{i}\left(\sum _{\{S:i\in {S}\}}\delta _{S}x^{S,i}\right)\geq \sum _{i\in {N}}\sum _{\{S:i\in {S}\}}\delta _{S}u_{i}(x^{S,i})$

אי השוויון האחרון נובע מקעירות הפונקציות $\ u_{i}$. על ידי שינוי סדר סכימה, נקבל:

$v(N)\geq \sum _{S\in {{\mathcal {D}}^{*}}}\sum _{i\in {S}}\delta _{S}u_{i}(x^{S,i})=\sum _{S\in {{\mathcal {D}}^{*}}}\delta _{S}v(S)$.

כיון ש- $\delta$ הוא וקטור מקדמים מאזנים חלש כלשהו, נובע מכאן כי תנאי בונדרבה-שפלי מתקיים, ולכן הליבה של המשחק אינה ריקה. $\blacksquare$

ראו גם

• תורת המשחקים
• משחק שוק
• ליבה של משחק שיתופי
• משפט בונדרבה-שפלי

לקריאה נוספת

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