משפט פון נוימן-מורגנשטרן

משפט פון נוימן-מורגנשטרן בתורת המשחקים הינו משפט האפיון של פונקציית התועלת, והוא קובע מתי קיימת לשחקן פונקציית תועלת לינארית.

הגדרות וסימונים

הגרלות והגרלות מורכבות

עבור קבוצת אפשרויות, או פרסים, $A=\{A_{1},\cdots ,A_{n}\}$ נרצה להגדיר את קבוצת ההגרלות וקבוצת ההגרלות המורכבות על $A$.
תהי הגרלה $L$, הגרלה בה נקבל תוצאה $A_{i}$ בהסתברות $p_{i}$. נסמן: $L=[p_{1}(A_{1}),p_{2}(A_{2}),\cdots ,p_{n}(A_{n})]$.
תהי ${\mathcal {L}}$ קבוצת כל ההגרלות האפשריות על $A$.
הגרלה מורכבת היא הגרלה על הגרלות, והיא מוגדרת באופן הבא: $\!{\overline {L}}=[q_{1}(L_{1}),...,q_{j-1}(L_{j-1}),q_{j}(M),q_{j+1}(L_{j+1}),...,q_{J}(L_{J})]$
הינה הגרלה שבה: $\!1\leq \forall i\leq J$ מתקיים ש $\!L_{i}$ הגרלה, $\!\sum q_{i}=1,q_{i}\geq 0$.
תהי ${\overline {\mathcal {L}}}$ קבוצת כל ההגרלות האפשריות על $A$.

יחס העדפות

יחס העדפות (חלש) הינו יחס $\preceq$ המייצג את העדפותיו של שחקן מסוים. תהיינה $L_{1},L_{2}$ שתי הגרלות מורכבות שונות. במידה והשחקן מעדיף (חלש) את הגרלה $L_{1}$ על הגרלה $L_{2}$,
נסמן $L_{2}\preceq L_{1}$. אם השחקן אדיש בין שתי ההגרלות, נסמן $L_{2}\approx L_{1}$.

פונקציית תועלת

תהי $A=\{A_{1},\cdots ,A_{n}\}$ קבוצה של פרסים אפשריים, ויהי $\preceq$ יחס העדפות שלם וטרנזיטיבי על קבוצת ההגרלות ${\mathcal {L}}$ עבור $A$.
פונקציית תועלת $u$ המייצגת את יחס ההעדפות $\preceq$ היא פונקציה $u:{\mathcal {L}}\rightarrow \mathbb {R}$ המקיימת: $u(L_{1})\geq u(L_{2})\iff L_{1}\succeq L_{2}$.

לינאריות של פונקציית תועלת

פונקציית תועלת $u$ היא לינארית אם לכל $L=[p_{1}(A_{1}),p_{2}(A_{2}),\cdots ,p_{n}(A_{n})]$ מתקיים: $u(L)=p_{1}u(A_{1})+p_{2}u(A_{2})+\cdots +p_{n}u(A_{n})$.

אקסיומות פון נוימן-מורגנשטרן

הנחות יסוד:

• קיימת קבוצה סופית של פרסים $A=\{A_{1},\cdots ,A_{n}\}$ בה יכול השחקן לזכות.
• לשחקן יש יחס ההעדפות שלם וטרנזיטיבי על הגרלות מורכבות.
  

תחת ההנחות הללו, ארבע האקסיומות בתועלת פון ניומן-מורגנשטרן הן רציפות, מונוטוניות, פישוט והצבה.

רציפות

עבור שחקן $\!i$ מתקיים : לכל שלושה פרסים $\!A\preceq _{i}B\preceq _{i}C$ קיים $\!0\leq \theta _{i}\leq 1$ כך ש: $\!B\approx _{i}[\theta _{i}(A),(1-\theta _{i})C]$

כלומר,עבור יחס ההעדפות שלעיל לגבי שלושה פרסים $\!A,B,C$ כאלה, קיים מספר $\!0\leq \theta _{i}\leq 1$ עבורו ניתן ליצור הגרלה חדשה בה השחקן יזכה בפרס $\!C$ בסיכוי $\!1-\theta _{i}$
ובפרס $\!A$ בסיכוי $\!\theta _{i}$, והשחקן יוותר אדיש בין הגרלה זו לבין זכייה בפרס $\!B$.

מונוטוניות

יהיו $\!0\leq \alpha ,\beta \leq 1$ ונניח כי $\!A\succ _{i}B$ אזי: $\![\alpha (A),(1-\alpha )B]\succeq _{i}[\beta (A),(1-\beta (B)]$ אם ורק אם $\!\alpha \geq \beta$

כלומר,אם שחקן מעדיף את פרס $\!A$ על פני פרס $\!B$, אזי הוא יעדיף כל הגרלה הנותנת לו את פרס $\!A$ בסיכוי $\!\alpha$ , על פני הגרלה הנותנת לו את $\!A$ בסיכוי נמוך יותר.

אקסיומת הפישוט

לכל $\!j=1,2...,J$ תהי $\!L_{j}$ ההגרלה הפשוטה:

$\!L_{j}=[p_{1}^{j}(A_{1}),p_{2}^{j}(A_{2}),...,p_{K}^{j}(A_{K})]$

ותהי ההגרלה המורכבת: $\!{\overline {L}}=[q_{1}(L_{1}),q_{2}(L_{2}),...,q_{j}(L_{j})]$

לכל $\!k=1...K$

נגדיר:

$\!r_{k}=[(q_{1})p_{k}^{1}+(q_{2})p_{k}^{2}+...+(q_{j})p_{k}^{J}]$

(כלומר,בהסתברות $\!q_{i}$ נזכה בתוצאה $\!L_{i}$ , ואז בסיכוי $\!p_{k}^{i}$ נזכה בפרס $\!A_{k}$. כאשר נסכום לכל $\!i$ נקבל את ההסתברות ל $\!A_{k}$ ) כך נוצרת ההגרלה הפשוטה:

$\!L=[r_{1}(A_{1}),r_{2}(A_{2}),...,r_{K}(A_{K})]$

אזי:

$\!L\approx _{i}{\overline {L}}$

כלומר, בהינתן הגרלה המגדירה את ההסתברויות לזכות באוסף פרסים, כל הגרלה שתגדיר את אותן הסתברויות, גם אם הינה בעלת יותר או פחות שלבים מההגרלה המקורית, שקולה להגרלה המקורית מבחינת יחס ההעדפות של השחקן.

הצבה

תהי $\!{\overline {L}}=[q_{1}(L_{1}),q_{2}(L_{2}),...,q_{j}(L_{j})]$ הגרלה מורכבת ו $\!M$ הגרלה פשוטה.

אם $\!L_{j}\approx _{i}M$ אזי: $\!{\overline {L}}\approx _{i}[q_{1}(L_{1}),...,q_{j-1}(L_{j-1}),q_{j}(M),q_{j+1}(L_{j+1}),...,q_{J}(L_{J})]$

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

משפט פון נוימן-מורגנשטרן

אם יחס ההעדפות ${{\succsim }_{i}}$ על ${\hat {\mathcal {L}}}$ של שחקן $i$ הוא שלם וטרנזיטיבי ומקיים את ארבעת האקסיומות של פון נוימן ומורגנשטרן, אזי יחס ההעדפות ניתן לייצוג על ידי פונקציית תועלת ליניארית.

הוכחה

טענת עזר. אם יחס ההעדפות של שחקן מקיים את אקסיומות הרציפות והמונוטוניות, ואם $A{{\succsim }_{i}}B{{\succsim }_{i}}C$ ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle A{{\succ }_{i}}C} , אזי הגודל ${{\theta }_{i}}$ המוגדר באקסיומת הרציפות יחיד.

הוכחת הטענה. יהי ${{\succsim }_{i}}$ יחס העדפות על $\left\{{{A}_{1}},\ldots ,{{A}_{K}}\right\}$ שמקיים את אקסיומות הרציפות והמונוטוניות, כאשר ${{A}_{K}}{{\succ }_{i}}{{A}_{1}}$.

לפי רציפות לכל $k\in \left\{1,\ldots ,K\right\}$ קיים $\theta _{i}^{k}\in \left[0,1\right]$ כך ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle {{A}_{k}}{{\approx }_{i}}\left[ \theta _{i}^{k}\left( {{A}_{K}} \right),\left( 1-\theta _{i}^{k} \right)\left( {{A}_{1}} \right) \right]} .

אם $\varphi _{i}^{k}\in \left[0,1\right]$ מקיים ${{A}_{k}}{{\approx }_{i}}\left[\varphi _{i}^{k}\left({{A}_{K}}\right),\left(1-\varphi _{i}^{k}\right)\left({{A}_{1}}\right)\right]$, אז לפי מונוטוניות $\varphi _{i}^{k}=\theta _{i}^{k}$.

הוכחת המשפט. יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle {{\succsim }_{i}}} יחס העדפות המקיים את תנאי המשפט. נטפל במקרה שבו ${{A}_{K}}{{\succ }_{i}}{{A}_{1}}$.

שלב ראשון: הגדרת פונקציה $u_{i}$ על קבוצת ההגרלות.

לפי טענת עזר, לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle k\in \left\{ 1,\ldots ,K \right\}} קיים מספר ממשי יחיד $\theta _{i}^{k}\in \left[0,1\right]$ המקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle A_k \approx _i \left[ \theta _i^k \left( A_K \right),\left( 1-\theta _i^k \right)\left( A_1 \right) \right]\ }

כעת נגדיר פונקציה $u_{i}$ על קבוצת ההגרלות המורכבות ${\hat {\mathcal {L}}}$. תהי נתונה הגרלה מורכבת ${\hat {L}}=\left[{{q}_{1}}\left({{L}_{1}}\right),\ldots ,{{q}_{J}}\left({{L}_{J}}\right)\right]$, שבה ${{q}_{1}},\ldots ,{{q}_{J}}$ הם מספרים אי-שליליים שסכומם $1$, ו-$L_{1},\ldots ,L_{J}$ הן הגרלות פשוטות הנתונות על ידי $L_{j}=\left[p_{1}^{j}\left(A_{1}\right),\ldots ,p_{K}^{j}\left(A_{K}\right)\right]$.

נגדיר לכל $k\in \left\{1,\ldots ,K\right\}$:

$r_{k}={q_{1}}{p_{k}^{1}}+{q_{2}}{p_{k}^{2}}+\ldots +{q_{J}}{p_{k}^{J}}\$

זוהי ההסתברות שתוצאת ההגרלה תהיה $A_{k}$. נגדיר פונקציה $u_{i}$ על קבוצת ההגרלות המורכבות באופן הבא:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle u_i \left( \hat{L} \right) = {r_1}{\theta _i^1} + {r_2}{\theta _i^2} + \ldots + {r_K}{\theta _i^K}\ }

מכאן נובע בפרט שלכל הגרלה פשוטה $L=\left[p_{1}\left(A_{1}\right),\ldots ,p_{K}\left(A_{K}\right)\right]$ מתקיים:

$u_{i}\left(L\right)=\sum \limits _{k=1}^{K}{{p_{k}}{\theta _{i}^{k}}}$

שלב שני: $u_{i}\left(A_{k}\right)=\theta _{i}^{k}$ לכל $k\in \left\{1,\ldots ,K\right\}$.

הפרס $A_{k}$ שקול להגרלה $L=\left[1\left(A_{k}\right)\right]$, השקולה להגרלה המורכבת ${\hat {L}}=\left[1\left(L\right)\right]$. תוצאת ההגרלה ${\hat {L}}$ היא $A_{k}$ בהסתברות $1$, ולכן במקרה זה:

$r_{l}=\left\{{\begin{array}{*{35}{l}}1\quad \quad \quad l=k\\0\quad \quad \quad l\neq k\\\end{array}}\right.$

מכאן נקבל כי:

$u_{i}\left(A_{k}\right)=\theta _{i}^{k}\quad \forall k\in \left\{1,\ldots ,K\right\}$

מכיוון ש-$\theta _{i}^{1}=0$ ו-$\theta _{i}^{K}=1$, נקבל כי $u_{i}\left(A_{1}\right)=0$ ו-$u_{i}\left(A_{K}\right)=1$.

שלב שלישי: $u_{i}$ ליניארית.

כדי להראות ש-$u_{i}$ ליניארית, נראה כי לכל הגרלה פשוטה $L=\left[p_{1}\left(A_{1}\right),\ldots ,p_{K}\left(A_{K}\right)\right]$ מתקיים:

$u_{i}\left(L\right)=\sum \limits _{k=1}^{K}{{p_{k}}{u_{i}}\left(A_{k}\right)}\$

אך משוואה זו מתקיימת, שכן משלב ראשון אגף שמאל שווה ל-$\sum \nolimits _{k=1}^{K}{{p_{k}}{\theta _{i}^{k}}}$, ומשלב שני אגף ימין שווה אף הוא לגודל זה.

שלב רביעי: $u_{i}$ הינה פונקציית תועלת.

כדי להראות כי $u_{i}$ הינה פונקציית תועלת המייצגת את יחס ההעדפות $\succsim _{i}$ יש להראות כי לכל שתי הגרלות מורכבות ${\hat {L}}$ ו-${\hat {L}}'$ מתקיים:

$u_{i}\left({\hat {L}}\right)\geq u_{i}\left({\hat {L}}'\right)$ אם ורק אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle \hat{L} \succsim _i \hat{L}'}

תהיינה, אם כן, ${\hat {L}}$ ו-${\hat {L}}'$ שתי הגרלות מורכבות. נסמן:

${\hat {L}}=\left[q_{1}\left(L_{1}\right),\ldots ,q_{J}\left(L_{J}\right)\right]\quad ,\quad {\hat {L}}'=\left[q'_{1}\left(L'_{1}\right),\ldots ,q'_{J'}\left(L'_{J'}\right)\right]$

כאשר

$L_{j}=\left[p_{1}^{j}\left(A_{1}\right),\ldots ,p_{K}^{j}\left(A_{K}\right)\right]\quad \forall j\in \left\{1,\ldots ,J\right\}\quad ,\quad L'_{j}=\left[{p'}_{1}^{j}\left(A_{1}\right),\ldots ,{p'}_{K}^{j}\left(A_{K}\right)\right]\quad \forall j\in \left\{1,\ldots ,J'\right\}$

לכל $k\in \left\{1,\ldots ,K\right\}$ נסמן:

$r_{k}=\sum \limits _{j=1}^{J}{{q_{j}}{p_{k}^{j}}}\quad ,\quad r'_{k}=\sum \limits _{j=1}^{J'}{{q'_{j}}{{p'}_{k}^{j}}}$

אלו ההסתברויות לקבלת התוצאה $A_{k}$ בשתי ההגרלות המורכבות ${\hat {L}}$ ו-${\hat {L}}'$. מהגדרת פונקציית התועלת,

$u_{i}\left({\hat {L}}\right)=\sum \limits _{k=1}^{K}{{r_{k}}{\theta _{i}^{k}}}\quad ,\quad u_{i}\left({\hat {L}}'\right)=\sum \limits _{k=1}^{K}{{r'_{k}}{\theta _{i}^{k}}}$

לכן,

$u_{i}\left({\hat {L}}\right)\geq u_{i}\left({\hat {L}}'\right)\quad \iff \quad \sum \limits _{k=1}^{K}{{r_{k}}{\theta _{i}^{k}}}\geq \sum \limits _{k=1}^{K}{{r'_{k}}{\theta _{i}^{k}}}$

מצד שני, מאקסיומת הפישוט,

${\hat {L}}\approx _{i}\left[r_{1}\left(A_{1}\right),r_{2}\left(A_{2}\right),\ldots ,r_{K}\left(A_{K}\right)\right]\quad ,\quad {\hat {L}}'\approx _{i}\left[r'_{1}\left(A_{1}\right),r_{2}\left(A_{2}\right),\ldots ,r'_{K}\left(A_{K}\right)\right]$

נסמן $L_{k}=\left[\theta _{i}^{k}\left(A_{K}\right),\left(1-\theta _{i}^{k}\right)\left(A_{1}\right)\right]$. אזי על פי הגדרת $\theta _{i}^{k}$ מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle A_k \approx _i L_k} לכל $k\in \left\{1,\ldots ,K\right\}$. מאקסיומת ההצבה המופעלת $K$ פעמים, הן עבור ${\hat {L}}$ והן עבור ${\hat {L}}'$, מתקיים:

${\hat {L}}\approx _{i}\left[r_{1}\left(L_{1}\right),r_{2}\left(L_{2}\right),\ldots ,r_{K}\left(L_{K}\right)\right]\quad ,\quad {\hat {L}}'\approx _{i}\left[r'_{1}\left(L_{1}\right),r'_{2}\left(L_{2}\right),\ldots ,r'_{K}\left(L_{K}\right)\right]$

כיוון שכל ההגרלות $L_{k}$ הן הגרלות על $A_{1},A_{K}$ ההגרלות באגף ימין של שתי המשוואות לעיל אף הן על שתי תוצאות אלו בלבד. לכן אם נסמן ב-$r$ ו-$r'$ את ההסתברות הכוללת של $A_{K}$ בהגרלות ${\hat {L}}$ ו-${\hat {L}}'$ בהתאמה, אזי

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle r = \sum\limits_{k=1}^{K} {{r_k}{\theta _i^k}} \quad , \quad r' = \sum\limits_{k=1}^{K} {{r'_k}{\theta _i^k}}}

ומאקסיומת הפישוט, נובע:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle \hat{L} \approx _i \left[ r \left( A_K \right) , \left( 1-r \right) \left( A_1 \right) \right] \quad , \quad \hat{L}' \approx _i \left[ r' \left( A_K \right) , \left( 1-r' \right) \left( A_1 \right) \right]}

מאקסיומת המונוטוניות,

${\hat {L}}\succsim _{i}{\hat {L}}'\quad \iff \quad r\geq r'$.

לכן, בסה"כ,

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle \hat{L} \succsim _i \hat{L}' \quad \iff \quad u_i \left( \hat{L} \right) \ge u_i \left( \hat{L}' \right)} .

כנדרש.

לקריאה נוספת

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