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

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

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

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

הוכחה

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

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

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

$X^S:=\{(x^i{)}_{i\in S}:x^i\in {\mathbb{ℝ}}_{+}^L\mathrm{\forall }i\in S,x(S)=a(S)\}\subseteq {\mathbb{ℝ}}_{+}^{|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 {\mathbb{ℝ}}_{+}^{|S|L}$ שבה מתקבל המקסימום בהגדרת $v(S)$.

מתקיים:

(i) $x^{S,i}\in {\mathbb{ℝ}}_{+}^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{ℝ}}_{+}^L$ הוא הסל ההתחלתי של שחקן i.

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

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

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

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

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

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

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

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

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

ראו גם

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

לקריאה נוספת

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