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

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

המודל

מרחב הפעולה

תחילה אנו מניחים שמקבל ההחלטות עומד בפני מצב עם מספר סופי של תוצאות אפשריות: ${\displaystyle O=\{A_{1},\cdots ,A_{K}\}}$.

כדי לנתח סיטואציות שבהן תוצאת המשחק אינה ודאית, כלומר היא הגרלה על קבוצת התוצאות, יש להרחיב את יחס ההעדפות של השחקן להתפלגויות על O. הגרלה ${\displaystyle \,L}$ שבה כל תוצאה אפשרית ${\displaystyle \,A_{k}}$ יכולה להתקבל בהסתברות ${\displaystyle \,p_{k}}$ תסומן על ידי ${\displaystyle L=[p_{1}(A_{1}),\ldots ,p_{K}(A_{K})]}$, וקבוצת ההגרלות על ${\displaystyle \,O}$:

$${\displaystyle {\mathcal {L}}(O)=\{[p_{1}(A_{1}),\ldots ,p_{K}(A_{K})]:{\vec {p}}\in \Delta ^{K}\}}$$

כאשר השתמשנו בסימון של הסימפלקס ה-K ממדי: ${\displaystyle \Delta ^{K}=\{{\vec {p}}\in [0,1]^{K}:\sum \nolimits _{k=1}^{K}{p_{k}}=1\}}$.

מתברר שכדי להוכיח את המשפט עלינו להרחיב את יחס ההעדפות של השחקן להגרלות על הגרלות. הגרלה מורכבת ${\displaystyle {\hat {L}}}$ שבה כל הגרלה ${\displaystyle \,L_{j}}$ יכולה להתקבל בהסתברות ${\displaystyle \,q_{j}}$ תסומן על ידי ${\displaystyle {\hat {L}}=[q_{1}(L_{1}),\ldots ,q_{J}(L_{J})]}$, וקבוצת ההגרלות המורכבות על ${\displaystyle \,O}$:

$${\displaystyle {\hat {\mathcal {L}}}(O)=\{[q_{1}(L_{1}),\ldots ,q_{J}(L_{J})]:J\in \mathbb {N} ,\ L_{j}\in {\mathcal {L}}(O),\ {\vec {q}}\in \Delta ^{J}\}}$$

יחס ההעדפות ופונקציית התועלת

כעת נגדיר את העדפותיו של השחקן. יחס העדפות ${\displaystyle \succsim _{i}}$ הוא יחס בינארי על ${\displaystyle {\hat {\mathcal {L}}}(O)}$ המייצג את העדפותיו של השחקן ${\displaystyle \,i}$. תהיינה ${\displaystyle {\hat {L}}_{1},{\hat {L}}_{2}}$ שתי הגרלות מורכבות. במידה והשחקן ${\displaystyle \,i}$ מעדיף את הגרלה ${\displaystyle {\hat {L}}_{1}}$ על פני הגרלה ${\displaystyle {\hat {L}}_{2}}$, נסמן ${\displaystyle {\hat {L}}_{1}\succsim _{i}{\hat {L}}_{2}}$. אם השחקן אדיש בין שתי ההגרלות, נסמן ${\displaystyle {\hat {L}}_{1}\approx _{i}{\hat {L}}_{2}}$.

ברור שכדי לנתח משחק בצורה מתמטית עלינו לדרוש שיחס ההעדפות יהיה שלם, כלומר שהשחקן יכול להשוות בין כל שתי הגרלות מורכבות, ובנוסף יחס ההעדפות צריך להיות טרנזיטיבי, שהרי אם יחס ההעדפות אינו טרנזיטיבי אנו עלולים לקבל מצבים שיש בהם סתירה לוגית כמו למשל: "השחקן מעדיף במבה על פני בייגלה, ומעדיף בייגלה על פני ביסלי, אך הוא מעדיף ביסלי על פני במבה". יהי אם כן ${\displaystyle \succsim _{i}}$ יחס העדפות שלם וטרנזיטיבי על ${\displaystyle {\hat {\mathcal {L}}}(O)}$, המייצג את העדפותיו של השחקן ${\displaystyle \,i}$.

נפנה להגדרת פונקציית התועלת. העתקה ${\displaystyle u:{\hat {\mathcal {L}}}(O)\rightarrow \mathbb {R} }$ נקראת פונקציית תועלת המייצגת את יחס ההעדפות ${\displaystyle \succsim _{i}}$ אם לכל הגרלה מורכבת ${\displaystyle {\hat {L}}_{1},{\hat {L}}_{2}\in {\hat {\mathcal {L}}}(O)}$ מתקיים:

$${\displaystyle {\hat {L}}_{1}\succsim _{i}{\hat {L}}_{2}\quad \iff \quad u({\hat {L}}_{1})\geq u({\hat {L}}_{2})}$$

יש לשים לב שלפי הגדרה זו ניתן לייצג יחס העדפות על ידי פונקציות שונות ורבות. למעשה, u היא פונקציית תועלת אורדינלית, כלומר מייצגת רק את סדר ההעדפות על התוצאות ואין בה שום חשיבות למידת ההעדפה של תוצאה כזו או אחרת. פונקציית תועלת ${\displaystyle u:{\hat {\mathcal {L}}}(O)\rightarrow \mathbb {R} }$ נקראת ליניארית אם לכל הגרלה ${\displaystyle {\hat {L}}=[q_{1}(L_{1}),q_{2}(L_{2}),\ldots ,q_{J}(L_{J})]}$ מתקיים:

$${\displaystyle u({\hat {L}})=q_{1}u(L_{1})+q_{2}u(L_{2})+\ldots +q_{J}u(L_{J})}$$

כלומר ה"ליניאריות" היא בהסתברויות על ההגרלות הפשוטות.

ארבע האקסיומות של פון נוימן ומורגנשטרן

הנחות יסוד:

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

הגרלה ${\displaystyle L}$, הגרלה בה נקבל תוצאה ${\displaystyle A_{i}}$ בהסתברות ${\displaystyle p_{i}}$. נסמן: ${\displaystyle L=[p_{1}(A_{1}),p_{2}(A_{2}),\cdots ,p_{n}(A_{n})]}$.
כאשר נגדיר הגרלה מורכבת באופן הבא:

${\displaystyle {\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})]}$ היא הגרלה שבה: ${\displaystyle 1\leq \forall i\leq j}$ מתקיים ש ${\displaystyle L_{i}}$ הגרלה, ${\displaystyle \sum q_{i}=1,q_{i}\geq 0}$

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

רציפות

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

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

מונוטוניות

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

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

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

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

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

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

לכל ${\displaystyle k=1...K}$

נגדיר:

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

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

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

אזי:

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

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

הצבה

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

אם ${\displaystyle L_{j}\approx _{i}M}$ אזי: ${\displaystyle {\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})]}$

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

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

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

הוכחה

טענת עזר. אם יחס ההעדפות של שחקן מקיים את אקסיומות הרציפות והמונוטוניות, ואם ${\displaystyle A\succsim _{i}B\succsim _{i}C}$ ו- ${\displaystyle A\succ _{i}C}$, אזי הגודל ${\displaystyle \,\theta _{i}}$ המוגדר באקסיומת הרציפות יחיד.

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

לפי רציפות לכל ${\displaystyle k\in \{1,\ldots ,K\}}$ קיים ${\displaystyle \theta _{i}^{k}\in [0,1]}$ כך ש- ${\displaystyle A_{k}\approx _{i}[\theta _{i}^{k}(A_{K}),(1-\theta _{i}^{k})(A_{1})]}$.

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

הוכחת המשפט. יהי ${\displaystyle \succsim _{i}}$ יחס העדפות המקיים את תנאי המשפט. נטפל במקרה שבו ${\displaystyle A_{K}\succ _{i}A_{1}}$.

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

לפי טענת עזר, לכל ${\displaystyle k\in \{1,\ldots ,K\}}$ קיים מספר ממשי יחיד ${\displaystyle \theta _{i}^{k}\in [0,1]}$ המקיים:

$${\displaystyle A_{k}\approx _{i}[\theta _{i}^{k}(A_{K}),(1-\theta _{i}^{k})(A_{1})]\ }$$

כעת נגדיר פונקציה ${\displaystyle \,u_{i}}$ על קבוצת ההגרלות המורכבות ${\displaystyle {\hat {\mathcal {L}}}(O)}$. תהי נתונה הגרלה מורכבת ${\displaystyle {\hat {L}}=[q_{1}(L_{1}),\ldots ,q_{J}(L_{J})]}$, שבה ${\displaystyle {\vec {q}}\in \Delta ^{J}}$, ו-${\displaystyle L_{1},\ldots ,L_{J}}$ הן הגרלות פשוטות הנתונות על ידי ${\displaystyle L_{j}=[p_{1}^{j}(A_{1}),\ldots ,p_{K}^{j}(A_{K})]}$.

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

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

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

$${\displaystyle u_{i}({\hat {L}})=r_{1}\theta _{i}^{1}+r_{2}\theta _{i}^{2}+\ldots +r_{K}\theta _{i}^{K}}$$

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

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

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

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

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

מכאן נקבל כי:

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

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

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

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

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

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

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

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

$${\displaystyle {\hat {L}}\succsim _{i}{\hat {L}}'\quad \iff \quad u_{i}({\hat {L}})\geq u_{i}({\hat {L}}')}$$

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

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

כאשר

$${\displaystyle L_{j}=[p_{1}^{j}(A_{1}),\ldots ,p_{K}^{j}(A_{K})]\quad ,\quad L'_{j}=[{p'}_{1}^{j}(A_{1}),\ldots ,{p'}_{K}^{j}(A_{K})]}$$

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

$${\displaystyle 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}}}$$

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

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

לכן,

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

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

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

נסמן ${\displaystyle L_{k}=[\theta _{i}^{k}(A_{K}),(1-\theta _{i}^{k})(A_{1})]}$. אזי על פי הגדרת ${\displaystyle \theta _{i}^{k}}$ מתקיים ${\displaystyle A_{k}\approx _{i}L_{k}}$ לכל ${\displaystyle k\in \{1,\ldots ,K\}}$. מאקסיומת ההצבה המופעלת ${\displaystyle \,K}$ פעמים, הן עבור ${\displaystyle {\hat {L}}}$ והן עבור ${\displaystyle {\hat {L}}'}$, מתקיים:

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

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

$${\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}}}$$

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

$${\displaystyle {\hat {L}}\approx _{i}[r(A_{K}),(1-r)(A_{1})]\quad ,\quad {\hat {L}}'\approx _{i}[r'(A_{K}),(1-r')(A_{1})]}$$

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

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

לכן, בסה"כ,

${\displaystyle {\hat {L}}\succsim _{i}{\hat {L}}'\quad \iff \quad u_{i}({\hat {L}})\geq u_{i}({\hat {L}}')}$.

כנדרש.

ראו גם

• מונחים בתורת המשחקים

לקריאה נוספת

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

קישורים חיצוניים

• משפט פון נוימן-מורגנשטרן, באתר אנציקלופדיה בריטניקה (באנגלית)