משפט שפלי-שוביק
משפט שפלי שוביק הוא משפט מתחום תורת המשחקים, הקובע כי הליבה של משחק שוק אינה ריקה.
הערה: המשפט מסתמך על כך שמשחק שוק נגזר משוק שבו פונקציות הייצור הן רציפות וקעורות.
המשפט ההפוך אינו נכון.
הוכחה
הוכחת המשפט משתמשת במשפט בונדרבה-שפלי. נוכיח כי משחק שוק הוא משחק מאוזן, כלומר, תנאי בונדרבה-שפלי מתקיים.
במהלך ההוכחה נשתמש בסימונים המופיעים בערך משחק שוק.
נסמן ב- $ 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
