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

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

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

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

הוכחה

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

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

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

$X^S:=\{(x^i{)}_{i\in S}:x^i\in {ℝ}_{+}^L\mathrm{\forall }i\in S,x(S)=a(S)\}\subseteq {ℝ}_{+}^{|S|L}$

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

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

מתקיים:

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

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

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

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

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

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

$\mathrm{\forall }i\in N.z^i:=\sum _{\{s\in {𝒟}^{\ast }:i\in S\}}{\delta }_S{x}^{S,i}$.

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

$z^i\in {ℝ}_{+}^L$ כי הוא ממוצע של וקטורים ב-${ℝ}_{+}^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 {𝒟}^{\ast }}\sum _{i\in S}{\delta }_S{x}^{S,i}=\sum _{S\in {𝒟}^{\ast }}{\delta }_S\sum _{i\in S}{x}^{S,i}=\sum _{S\in {𝒟}^{\ast }}{\delta }_S{x}^S(S)$
מכיוון ש-$x^S(S)=a(S)$ ועל ידי שינוי סדר סכימה, נקבל:

$z(N)=\sum _{S\in {𝒟}^{\ast }}{\delta }_{S}a(S)=\sum _{S\in {𝒟}^{\ast }}{\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)\ge \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)\ge \sum _{i\in N}\sum _{\{S:i\in S\}}{\delta }_S{u}_i(x^{S,i})$

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

$v(N)\ge \sum _{S\in {𝒟}^{\ast }}\sum _{i\in S}{\delta }_S{u}_i(x^{S,i})=\sum _{S\in {𝒟}^{\ast }}{\delta }_{S}v(S)$.

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

ראו גם

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

לקריאה נוספת

• תבנית:צ-ספר