משחק סטוכסטי
תאוריה

הרכיבים של משחק סטוכסטי הם:
קבוצה סופית של שחקנים  I
מרחב מצב  M (אשר מהווה קבוצה סופית או מרחב הניתן למדידה  (M,{\mathcal {A}}))
עבור כל שחקן  i\in I, קבוצת פעולה  S^{i} (S^{i},{\mathcal {S}}^{i}))
הסתברות מעבר  P מ-  M\times S, כאשר  S=\times _{i\in I}S^{i} הם פרופילי הפעולה, ל-  M, כאשר  P(A\mid m,s) הנה ההסתברות שהמצב הבא יהיה  A בהינתן שהמצב הנוכחי הוא  m ופרופיל הפעולה הנוכחית הוא  s.
פונקציית תגמול  g מ- M\times S ל- R^{I}, כאשר קואורדינטת ה-  i של  g,  g^{i}, מייצגת את התגמול לשחקן  i כפונקציה של המצב  m ופרופיל הפעולה  s.
המשחק מתחיל במצב התחלתי מסוים  m_{1}. בשלב  t, השחקנים צופים ראשית ב-  m_{t}. לאחר מכן הם בוחרים בו-זמנית פעולות  s_{t}^{i}\in S^{i}, ואחר-כך הם צופים בפרופיל הפעולה  s_{t}=(s_{t}^{i})_{i}, ואז הטבע בוחר  m_{t+1} לפי הסתברות  P(\cdot \mid m_{t},s_{t}). מהלך של המשחק הסטוכסטי,  m_{1},s_{1},\ldots ,m_{t},s_{t},\ldots  מגדיר זרם של תגמולים  g_{1},g_{2},\ldots , כאשר  g_{t}=g(m_{t},s_{t}).
המשחק המנוכה Γλ עם מקדם הניכיון  \lambda  ( 0<\lambda \leq 1) הוא המשחק אשר התגמול לשחקן i הוא  \lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}. משחק שלב ה-n הוא המשחק אשר התגמול לשחקן i הוא  {\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}.
הערך (vn(m1, ו- ( vλ(m1 בהתאמה, של משחק סטוכסטי סכום-אפס של שני שחקנים nΓ, ו- Γλ  בהתאמה, עם מצבים ופעולות סופיים קיים, וטרומן בוולי ואילון קולברג (1967) הוכיחו כי ( vλ(m1 מתכנס לגבול כאשר n שואף לאינסוף. כמו כן, הם הוכיחו כי ( vλ(m1 מתכנס לאותו הגבול כאשר λ שואף ל-0. המשחק "הבלתי מנוכה",  \Gamma _{\infty }הוא משחק אשר התגמול לשחקן  iהוא ה-"גבול" של ממוצע תגמולי השלב. צריך לנקוט בכמה אמצעי זהירות בהגדרת הערך של  \Gamma _{\infty } של שני-שחקנים בעל סכום-אפס, ובהגדרת תגמולים שיווי-משקליים של  \Gamma _{\infty } שאינו בעל סכום-אפס. הערך האחיד  v_{\infty } של משחק סטוכסטי סכום-אפס בעל שני-שחקנים  \Gamma _{\infty } מתקיים אם עבור כל  \varepsilon >0 ישנו מספר חיובי ושלם  Nוזוג אסטרטגי:  \sigma _{\varepsilon } של שחקן מס' 1 ו-  \tau _{\varepsilon } של שחקן מס' 2, כך שעבור כל  \sigma  ו-  \tau  וכל  n\geq N התוחלת של  {\bar {g}}_{n}^{i} המתייחסת להסתברות במהלכים שמוגדרים על ידי  \sigma _{\varepsilon } ו-  \tau  הנה לפחות  v_{\infty }-\varepsilon , והתוחלת של  {\bar {g}}_{n}^{i} המתייחסת להסתברות במהלכים המוגדרים על ידי  \sigma  ו-  \tau _{\varepsilon } היא לכל היותר  v_{\infty }+\varepsilon . ז'אן פרנסואה מרטנס ואברהם נוימן (1981) הוכיחו שלכל משחק סטוכסטי לשני-שחקנים בעל סכום-אפס עם מצבים ופעולות סופיים, קיים ערך אחיד.
אם ישנו מספר סופי של שחקנים וקבוצות הפעולה וקבוצת המצבים הם סופיים, אזי למשחק סטוכסטי עם מספר סופי של שלבים תמיד יהיה שיווי משקל נאש. אותו הדבר נכון עבור משחק עם אינסוף שלבים אם התגמול הכולל הוא הסכום המנוכה.למשחק הסטוכסטי  \Gamma _{\infty } שאינו בעל סכום-אפס יש תגמול שיווי-משקלי אחיד  v_{\infty } אם עבור כל  \varepsilon >0ישנו מספר חיובי ושלם  N ופרופיל אסטרטגי  \sigma כך שעבור כל סטייה חד-צדדית הנעשית על ידי שחקן  i, (כלומר, פרופיל אסטרטגי  \tau  עם  \sigma ^{j}=\tau ^{j} עבור כל  j\neq i, וכל  n\geq N התוחלת של  {\bar {g}}_{n}^{i}המתייחסת להסתברות במהלכים המוגדרים על ידי  \sigma  הנה לפחות  v_{\infty }^{i}-\varepsilon , והתוחלת של  {\bar {g}}_{n}^{i}המתייחסת להסתברות במהלכים המוגדרים על ידי  \tau  הנה לכל היותר  v_{\infty }^{i}+\varepsilon  וייל הראה שמשחקים סטוכסטיים בעלי שני-שחקנים עם מצב סופי ומרחבי פעולה יש תגמול שיווי-משקל אחיד.
למשחק הסטוכסטי שאינו בעל סכום-אפס יש תגמול שיווי-משקלי ממוצע מוגבל אם עבור כל  \varepsilon >0 יש פרופיל אסטרטגי  \sigma  כך שעבור כל סטייה חד-צדדית הנעשית על ידי שחקן  i, התוחלת של הגבול התחתון של ממוצע תגמולי השלב המתייחסת להסתברות במהלכים המוגדרים על ידי  \sigma היא לפחות  v_{\infty }^{i}-\varepsilon , והתוחלת של הגבול העליון של תגמול ממוצע השלב המתייחסת להסתברות במהלכים המוגדרים על ידי  \tau  הנה לכל היותר  v_{\infty }+\varepsilon . ז'אן פרנסואה מרטנס ואברהם נוימן הוכיחו (1981) כי לכל משחק סטוכסטי שהוא סכום-אפס בעל שני שחקנים עם מצבים ופעולות סופיים רבים ישנו ערך ממוצע מוגבל, וניקולה וייל הראה שלכל המשחקים הסטוכסטיים בעלי שני שחקנים עם מצב ומרחבי פעולה סופיים יש תגמול שיווי-משקלי ממוצע מוגבל. במיוחד, התוצאות הללו מביעות שלמשחקים הללו יש ערך ותגמול שיווי-משקל מקורב, הנקרא תגמול שיווי-משקלי בעל ממוצע גבול-תחתון (ובהתאמה, בעל ממוצע גבול-עליון), כשאר התגמול הכולל הוא הגבול התחתון (או הגבול העליון) של ממוצע תגמולי השלב. שאלה שנותרה פתוחה היא האם לכל משחק סטוכסטי עם מס' שחקנים, מצבים ופעולות רבים וסופיים ישנו תגמול שיווי-משקל אחיד, או תגמול שיווי-משקל ממוצע מגדל, או אפילו תגמול שיווי-משקל בעל ממוצע גבול-תחתון. שיווי המשקל המושלם של מרקוב הוא עיבוד תת-משחקי משוכלל של הקונספט של שיווי משקל נאש עבור משחקים סטוכסטיים.