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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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


המודל[עריכת קוד מקור | עריכה]

מרחב הפעולה[עריכת קוד מקור | עריכה]

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


כדי לנתח סיטואציות שבהן תוצאת המשחק אינה ודאית, כלומר היא הגרלה על קבוצת התוצאות, יש להרחיב את יחס ההעדפות של השחקן להתפלגויות על O. הגרלה \, L שבה כל תוצאה אפשרית \, A_k יכולה להתקבל בהסתברות \, p_k תסומן על ידי L = [ p_1(A_1) , \ldots , p_K(A_K) ], וקבוצת ההגרלות על \, O:


\mathcal{L}(O) = \{ [ p_1(A_1) , \ldots , p_K(A_K) ] : \vec{p} \in \Delta^K \}


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


מתברר שכדי להוכיח את המשפט עלינו להרחיב את יחס ההעדפות של השחקן להגרלות על הגרלות. הגרלה מורכבת \hat{L} שבה כל הגרלה \, L_j יכולה להתקבל בהסתברות \, q_j תסומן על ידי \hat{L}=[q_1(L_1),\ldots,q_J(L_J)], וקבוצת ההגרלות המורכבות על \, O:


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


יחס ההעדפות ופונקציית התועלת[עריכת קוד מקור | עריכה]

כעת נגדיר את העדפותיו של השחקן. יחס העדפות \succsim_i הוא יחס בינארי על \hat{\mathcal{L}}(O) המייצג את העדפותיו של השחקן \, i. תהיינה \hat{L}_1 , \hat{L}_2 שתי הגרלות מורכבות. במידה והשחקן \, i מעדיף את הגרלה \hat{L}_1 על פני הגרלה \hat{L}_2, נסמן \hat{L}_1 \succsim_i \hat{L}_2. אם השחקן אדיש בין שתי ההגרלות, נסמן \hat{L}_1 \approx_i \hat{L}_2.


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


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


\hat{L}_1 \succsim_i \hat{L}_2 \quad \iff \quad u(\hat{L}_1) \ge u(\hat{L}_2)


יש לשים לב שלפי הגדרה זו ניתן לייצג יחס העדפות על ידי פונקציות שונות ורבות. למעשה, u היא פונקציית תועלת אורדינלית, כלומר מייצגת רק את סדר ההעדפות על התוצאות ואין בה שום חשיבות למידת ההעדפה של תוצאה כזו או אחרת. פונקציית תועלת u: \hat{\mathcal{L}}(O) \rightarrow \mathbb{R} נקראת לינארית אם לכל הגרלה \hat{L} = [q_1(L_1),q_2(L_2),\ldots,q_J(L_J)] מתקיים:


u(\hat{L}) = q_1 u(L_1) + q_2 u(L_2) + \ldots + q_J u(L_J)


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


ארבע האקסיומות של פון נוימן ומורגנשטרן[עריכת קוד מקור | עריכה]

הנחות יסוד:

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

הגרלה \!L, הגרלה בה נקבל תוצאה \!A_i בהסתברות \! p_i. נסמן: L=[p_1(A_1),p_2(A_2),\cdots,p_n(A_n)].
כאשר נגדיר הגרלה מורכבת באופן הבא:

\!\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

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

רציפות[עריכת קוד מקור | עריכה]

עבור שחקן \!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^j_1(A_1),p^j_2(A_2),...,p^j_K(A_K)]

ותהי ההגרלה המורכבת: \!\overline{L}=[q_1(L_1),q_2(L_2),...,q_j(L_j)]

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

נגדיר:

\!r_k=[(q_1)p^1_k+(q_2)p^2_k+...+(q_j)p^J_k]

(כלומר,בהסתברות \!q_i נזכה בתוצאה \!L_i , ואז בסיכוי \!p^i_k נזכה בפרס \!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}(O) של שחקן \, i הוא שלם וטרנזיטיבי ומקיים את ארבע האקסיומות של פון נוימן ומורגנשטרן, אזי יחס ההעדפות ניתן לייצוג על ידי פונקציית תועלת לינארית.


הוכחה[עריכת קוד מקור | עריכה]

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

הוכחת הטענה. יהי \succsim _i יחס העדפות על \{ A_1 , \ldots , A_K \} שמקיים את אקסיומות הרציפות והמונוטוניות, כאשר A_K \succ _i A_1.
לפי רציפות לכל k \in \{ 1 , \ldots , K \} קיים \theta_i^k \in [0,1] כך ש- A_k \approx_i [ \theta _i^k(A_K) , (1-\theta_i^k)(A_1) ].
אם \varphi_i^k \in [0,1] מקיים A_k \approx_i [ \varphi_i^k(A_K) , (1-\varphi_i^k)(A_1) ], אז לפי מונוטוניות \varphi_i^k = \theta_i^k.


הוכחת המשפט. יהי \succsim_i יחס העדפות המקיים את תנאי המשפט. נטפל במקרה שבו A_K \succ_i A_1.


שלב ראשון: הגדרת פונקציה \, u_i על קבוצת ההגרלות.

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

A_k \approx_i [ \theta_i^k(A_K) , (1-\theta_i^k)(A_1) ]\

כעת נגדיר פונקציה \, u_i על קבוצת ההגרלות המורכבות \hat{\mathcal{L}}(O). תהי נתונה הגרלה מורכבת \hat{L} = [ q_1(L_1) , \ldots , q_J(L_J) ], שבה \vec{q} \in \Delta^J, ו-L_1,\ldots,L_J הן הגרלות פשוטות הנתונות על ידי L_j = [ p_1^j(A_1) , \ldots , p_K^j(A_K) ].

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

r_k = q_1 p_k^1 + q_2 p_k^2 + \ldots + q_J p_k^J

זוהי ההסתברות שתוצאת ההגרלה תהיה \, A_k. נגדיר פונקציה \, u_i על קבוצת ההגרלות המורכבות באופן הבא:

u_i(\hat{L}) = r_1 \theta_i^1 + r_2 \theta_i^2 + \ldots + r_K \theta_i^K

מכאן נובע בפרט שלכל הגרלה פשוטה L = [ p_1(A_1), \ldots , p_K(A_K) ] מתקיים:

u_i(L) = \sum\limits_{k=1}^{K} {p_k \theta_i^k}


שלב שני: u_i(A_k) = \theta_i^k לכל k \in \{ 1 , \ldots , K \}.

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

r_l = \left\{  \begin{array} {*{35}{l}}
   1\quad \quad \quad l = k  \\
   0\quad \quad \quad l \ne k  \\
\end{array} \right.

מכאן נקבל כי:

u_i(A_k) = \theta_i^k \quad \forall k \in \{ 1 , \ldots , K \}

מכיוון ש-\theta_i^1 = 0 ו-\theta_i^K = 1, נקבל כי \, u_i(A_1)=0 ו-\, u_i(A_K)=1.


שלב שלישי: \, u_i לינארית.

כדי להראות ש-\, u_i לינארית, נראה כי לכל הגרלה פשוטה L = [ p_1(A_1) , \ldots , p_K(A_K) ] מתקיים:

u_i(L) = \sum\limits_{k=1}^{K} {p_k u_i(A_k)}

אך משוואה זו מתקיימת, שכן משלב ראשון אגף שמאל שווה ל-\sum\nolimits_{k=1}^{K} {p_k \theta_i^k}, ומשלב שני אגף ימין שווה אף הוא לגודל זה.


שלב רביעי: \, u_i היא פונקציית תועלת.

כדי להראות כי \, u_i היא פונקציית תועלת המייצגת את יחס ההעדפות \succsim_i יש להראות כי לכל שתי הגרלות מורכבות \hat{L} ו-\hat{L}' מתקיים:

\hat{L} \succsim_i \hat{L}' \quad \iff \quad u_i(\hat{L}) \ge u_i(\hat{L}')

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

\hat{L} = [q_1(L_1),\ldots,q_J(L_J)] \quad , \quad \hat{L}' = [q'_1(L'_1),\ldots,q'_{J'}(L'_{J'})]

כאשר

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)]

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

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(\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}

לכן,

u_i(\hat{L}) \ge u_i(\hat{L}') \quad \iff \quad \sum\limits_{k=1}^{K} {r_k \theta_i^k} \ge \sum\limits_{k=1}^{K} {r'_k \theta_i^k}

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

\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)]

נסמן L_k = [\theta_i^k(A_K),(1-\theta_i^k)(A_1)]. אזי על פי הגדרת \theta _i^k מתקיים A_k \approx_i L_k לכל k \in \{1,\ldots,K\}. מאקסיומת ההצבה המופעלת \, K פעמים, הן עבור \hat{L} והן עבור \hat{L}', מתקיים:

\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)]

כיוון שכל ההגרלות \, L_k הן הגרלות על \, A_1,A_K ההגרלות באגף ימין של שתי המשוואות לעיל אף הן על שתי תוצאות אלו בלבד. לכן אם נסמן ב-\, r ו-\, r' את ההסתברות הכוללת של \, A_K בהגרלות \hat{L} ו-\hat{L}' בהתאמה, אזי

r = \sum\limits_{k=1}^{K} {r_k \theta_i^k} \quad , \quad r' = \sum\limits_{k=1}^{K} {r'_k \theta_i^k}

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

\hat{L} \approx_i [r(A_K),(1-r)(A_1)] \quad , \quad \hat{L}' \approx_i [r'(A_K),(1-r')(A_1)]

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

\hat{L} \succsim_i \hat{L}' \quad \iff \quad r \ge r'.

לכן, בסה"כ,

\hat{L} \succsim_i \hat{L}' \quad \iff \quad u_i(\hat{L}) \ge u_i(\hat{L}').

כנדרש.

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]