משתמש:Michalrechter/ארגז חול

כיתוב תמונה

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

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

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

הוכחה

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

נגדיר את התשלום לקואליציה $\ 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)$,

כנדרש. ולכן, הליבה אינה ריקה. $\blacksquare$

לקריאה נוספת

• שמואל זמיר, מיכאל משלר ואילון סולן, תורת המשחקים, הוצאת מאגנס, תשס"ח/2008.