ในทฤษฎีเกมเกมสุ่ม (หรือเกมมาร์คอฟ ) คือเกมที่เล่นซ้ำๆโดยมีการเปลี่ยนสถานะแบบสุ่มซึ่งผู้เล่นหนึ่งคนหรือมากกว่านั้นเล่น เกมจะเล่นเป็นลำดับในแต่ละขั้นตอน ในตอนเริ่มต้นของแต่ละขั้นตอน เกมจะอยู่ในสถานะ ใดสถานะหนึ่ง ผู้เล่นจะเลือกการกระทำ และผู้เล่นแต่ละคนจะได้รับผลตอบแทนที่ขึ้นอยู่กับสถานะปัจจุบันและการกระทำที่เลือก จากนั้นเกมจะเปลี่ยนไปสู่สถานะสุ่มใหม่ ซึ่งการกระจายตัวของสถานะใหม่นั้นขึ้นอยู่กับสถานะก่อนหน้าและการกระทำที่ผู้เล่นเลือก กระบวนการนี้จะทำซ้ำในสถานะใหม่ และการเล่นจะดำเนินต่อไปเป็นจำนวนขั้นตอนที่จำกัดหรือไม่จำกัด ผลตอบแทนรวมของผู้เล่นมักจะคิดจากผลรวมที่ลดลงของผลตอบแทนในแต่ละขั้นตอน หรือค่าต่ำสุดของค่าเฉลี่ยของผลตอบแทนในแต่ละขั้นตอน

เกมสุ่มได้รับการแนะนำโดยLloyd Shapleyในช่วงต้นทศวรรษ 1950 ^{[ 1 ]} เกมเหล่านี้ขยายกระบวนการตัดสินใจของ Markovไปสู่ผู้ตัดสินใจหลายคนที่โต้ตอบกัน รวมถึงเกมรูปแบบเชิงกลยุทธ์ไปสู่สถานการณ์แบบไดนามิกที่สภาพแวดล้อมเปลี่ยนแปลงไปตามการเลือกของผู้เล่น^{[ 2 ]}

เกมสุ่มแบบผู้เล่นสองคนบนกราฟแบบมีทิศทางถูกนำมาใช้กันอย่างแพร่หลายในการสร้างแบบจำลองและการวิเคราะห์ระบบแบบไม่ต่อเนื่องที่ทำงานในสภาพแวดล้อมที่ไม่รู้จัก (เป็นปฏิปักษ์) การกำหนดค่าที่เป็นไปได้ของระบบและสภาพแวดล้อมจะถูกแทนด้วยจุดยอด และการเปลี่ยนสถานะจะสอดคล้องกับการกระทำของระบบ สภาพแวดล้อม หรือ "ธรรมชาติ" การทำงานของระบบจึงสอดคล้องกับเส้นทางอนันต์ในกราฟ ดังนั้น ระบบและสภาพแวดล้อมจึงสามารถมองได้ว่าเป็นผู้เล่นสองคนที่มีเป้าหมายที่ขัดแย้งกัน โดยผู้เล่นคนหนึ่ง (ระบบ) มุ่งเป้าไปที่การเพิ่มความน่าจะเป็นของการทำงาน "ที่ดี" ให้สูงสุด ในขณะที่ผู้เล่นอีกคน (สภาพแวดล้อม) มุ่งเป้าไปที่สิ่งที่ตรงกันข้าม

ในหลายกรณี ค่าความน่าจะเป็นนี้จะมีค่าสมดุลอยู่ แต่กลยุทธ์ที่เหมาะสมที่สุดสำหรับผู้เล่นทั้งสองฝ่ายอาจไม่มีอยู่จริง

เราจะแนะนำแนวคิดพื้นฐานและคำถามเกี่ยวกับอัลกอริทึมที่ศึกษาในสาขานี้ และกล่าวถึงปัญหาที่ยังไม่ได้รับการแก้ไขมาอย่างยาวนาน จากนั้นเราจะกล่าวถึงผลลัพธ์ล่าสุดที่คัดเลือกมาบางส่วน

ส่วนประกอบของเกมสุ่มมีดังนี้: ชุดผู้เล่นจำนวนจำกัด; ปริภูมิสถานะ(อาจเป็นเซตจำกัดหรือปริภูมิที่วัดได้ ); สำหรับผู้เล่นแต่ละคนชุดการกระทำ (อาจเป็นเซตจำกัดหรือปริภูมิที่วัดได้); ความน่าจะเป็นของการเปลี่ยนสถานะจากโดยที่คือชุดการกระทำ ไปยังโดยที่คือความน่าจะเป็นที่สถานะถัดไปจะเป็นเมื่อกำหนดสถานะปัจจุบันและชุดการกระทำปัจจุบัน; และฟังก์ชันผลตอบแทนจากไปยังโดยที่พิกัดที่ ของคือผลตอบแทนของผู้เล่นซึ่งเป็นฟังก์ชันของสถานะและชุดการกระทำ ${\displaystyle I}$${\displaystyle S}$${\displaystyle (S,{\mathcal {S}})}$${\displaystyle i\in I}$${\displaystyle A^{i}}$${\displaystyle (A^{i},{\mathcal {A}}^{i})}$${\displaystyle P}$${\displaystyle S\times A}$${\displaystyle A=\times _{i\in I}A^{i}}$${\displaystyle S}$${\displaystyle P(S\mid s,a)}$${\displaystyle S}$${\displaystyle s}$${\displaystyle a}$${\displaystyle g}$${\displaystyle S\times A}$${\displaystyle R^{I}}$${\displaystyle i}$${\displaystyle g}$${\displaystyle g^{i}}$${\displaystyle i}$${\displaystyle s}$${\displaystyle a}$

เกมเริ่มต้นที่สถานะเริ่มต้นบางอย่างในแต่ละขั้นตอนผู้เล่นจะสังเกตก่อนจากนั้นเลือกการกระทำพร้อมกันจากนั้นสังเกตโปรไฟล์การกระทำและจากนั้นธรรมชาติจะเลือกตามความน่าจะเป็นการเล่นเกมสุ่มหนึ่งครั้งจะกำหนดลำดับของผลตอบแทนโดย ที่${\displaystyle s_{1}}$${\displaystyle t}$${\displaystyle s_{t}}$${\displaystyle a_{t}^{i}\in A^{i}}$${\displaystyle a_{t}=(a_{t}^{i})_{i}}$${\displaystyle s_{t+1}}$${\displaystyle P(\cdot \mid s_{t},a_{t})}$${\displaystyle s_{1},a_{1},\ldots ,s_{t},a_{t},\ldots }$${\displaystyle g_{1},g_{2},\ldots }$${\displaystyle g_{t}=g(s_{t},a_{t})}$

เกมลดราคาที่มีปัจจัยส่วนลด( ) คือเกมที่ผลตอบแทนของผู้เล่นคือเกม-ขั้น คือเกมที่ผลตอบแทนของผู้เล่น คือ${\displaystyle \Gamma _{\แลมบ์ดา }}$${\displaystyle \lambda }$${\displaystyle 0<\lambda \leq 1}$${\displaystyle i}$${\displaystyle \lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}}$${\displaystyle n}$${\displaystyle i}$${\displaystyle {\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}}$

ค่า ของเกมสุ่มแบบผล รวมเป็นศูนย์สำหรับผู้เล่นสองคนซึ่งมีสถานะและการกระทำจำนวนจำกัดนั้นมีอยู่จริง และ Truman BewleyและElon Kohlberg (1976) ได้พิสูจน์แล้วว่าลู่เข้าสู่ค่าจำกัดเมื่อเข้าสู่ค่าอนันต์ และลู่เข้าสู่ค่าจำกัดเดียวกันเมื่อเข้าสู่ค่าอนันต์ ${\displaystyle v_{n}(s_{1})}$${\displaystyle v_{\แลมบ์ดา }(s_{1})}$${\displaystyle \Gamma _{n}}$${\displaystyle \Gamma _{\แลมบ์ดา }}$${\displaystyle v_{n}(s_{1})}$${\displaystyle n}$${\displaystyle v_{\แลมบ์ดา }(s_{1})}$${\displaystyle \lambda }$${\displaystyle 0}$

เกม "ไม่ลดราคา" คือเกมที่ผลตอบแทนของผู้เล่นคือ "ขีดจำกัด" ของค่าเฉลี่ยของผลตอบแทนในแต่ละขั้นตอน จำเป็นต้องมีข้อควรระวังบางประการในการกำหนดค่าของเกมผลรวมเป็นศูนย์แบบสองผู้เล่นและในการกำหนดค่าผลตอบแทนสมดุลของเกมผลรวมไม่เป็นศูนย์ค่าสม่ำเสมอของเกมสุ่มผลรวมเป็นศูนย์แบบสองผู้เล่นมีอยู่ ถ้าสำหรับทุกๆมีจำนวนเต็มบวก และคู่กลยุทธ์ของผู้เล่น 1 และผู้เล่น 2 เช่นนั้นสำหรับทุกๆและและทุกๆ ค่าคาดหวังของ เมื่อเทียบกับความน่าจะเป็นในการเล่นที่กำหนดโดยและมีค่าอย่างน้อยและค่าคาดหวังของ เมื่อเทียบกับความน่าจะเป็นในการเล่นที่กำหนดโดยและ มี ค่าอย่างมากJean-François MertensและAbraham Neyman (1981) พิสูจน์ว่าเกมสุ่มผลรวมเป็นศูนย์แบบสองผู้เล่นทุกเกมที่มีสถานะและการกระทำจำนวนจำกัดมีค่าสม่ำเสมอ^{[ 3 ]}${\displaystyle \Gamma _{\infty }}$${\displaystyle i}$${\displaystyle \Gamma _{\infty }}$${\displaystyle \Gamma _{\infty }}$${\displaystyle v_{\infty }}$${\displaystyle \Gamma _{\infty }}$${\displaystyle \varepsilon >0}$${\displaystyle N}$${\displaystyle \sigma _{\varepsilon }}$${\displaystyle \tau _{\varepsilon }}$${\displaystyle \sigma }$${\displaystyle \tau }$${\displaystyle n\geq N}$${\displaystyle {\bar {g}}_{n}^{i}}$${\displaystyle \sigma _{\varepsilon }}$${\displaystyle \tau }$${\displaystyle v_{\infty }-\varepsilon }$${\displaystyle {\bar {g}}_{n}^{i}}$${\displaystyle \sigma }$${\displaystyle \tau _{\varepsilon }}$${\displaystyle v_{\infty }+\varepsilon }$

ถ้าจำนวนผู้เล่นมีจำกัด และชุดการกระทำและชุดสถานะมีจำนวนจำกัด เกมสุ่มที่มีจำนวนขั้นตอนจำกัดจะมีสมดุลแนช เสมอ เช่นเดียวกันนี้ก็เป็นจริงสำหรับเกมที่มีจำนวนขั้นตอนไม่จำกัด หากผลตอบแทนรวมคือผลรวมที่คิดลดแล้ว

เกมสุ่มแบบผลรวมไม่เป็นศูนย์จะมีผลตอบแทนสมดุลสม่ำเสมอหากสำหรับทุก ๆมีจำนวนเต็มบวก และโปรไฟล์กลยุทธ์ที่สำหรับการเบี่ยงเบนฝ่ายเดียวของผู้เล่นทุก ๆ ครั้ง กล่าวคือ โปรไฟล์กลยุทธ์ ที่มีสำหรับทุก ๆและทุก ๆ ความคาดหวังของเมื่อเทียบกับความน่าจะเป็นในการเล่นที่กำหนดโดยมีค่าอย่างน้อยและความคาดหวังของเมื่อเทียบกับความน่าจะเป็นในการเล่นที่กำหนดโดย มี ค่าอย่างมากNicolas Vieilleได้แสดงให้เห็นว่าเกมสุ่มสองผู้เล่นทั้งหมดที่มีสถานะและพื้นที่การกระทำจำกัดจะมีผลตอบแทนสมดุลสม่ำเสมอ^{[ 4 ]}${\displaystyle \Gamma _{\infty }}$${\displaystyle v_{\infty }}$${\displaystyle \varepsilon >0}$${\displaystyle N}$${\displaystyle \sigma }$${\displaystyle i}$${\displaystyle \tau }$${\displaystyle \sigma ^{j}=\tau ^{j}}$${\displaystyle j\neq i}$${\displaystyle n\geq N}$${\displaystyle {\bar {g}}_{n}^{i}}$${\displaystyle \sigma }$${\displaystyle v_{\infty }^{i}-\varepsilon }$${\displaystyle {\bar {g}}_{n}^{i}}$${\displaystyle \tau }$${\displaystyle v_{\infty }^{i}+\varepsilon }$

เกมสุ่มแบบผลรวมไม่เป็นศูนย์จะมีผลตอบแทนสมดุลเฉลี่ยแบบจำกัดหากสำหรับทุกๆจะมีโปรไฟล์กลยุทธ์ที่ทำให้สำหรับการเบี่ยงเบนฝ่ายเดียวของผู้เล่นแต่ละครั้งความคาดหวังของค่าต่ำสุดของค่าเฉลี่ยของผลตอบแทนในแต่ละขั้นตอนเมื่อเทียบกับความน่าจะเป็นในการเล่นที่กำหนดโดย มีค่าอย่างน้อยและความคาดหวังของค่าสูงสุดของค่าเฉลี่ยของผลตอบแทนในแต่ละขั้นตอนเมื่อเทียบกับความน่าจะเป็นในการเล่นที่กำหนดโดย มีค่า ไม่เกินJean-François MertensและAbraham Neyman (1981) พิสูจน์ว่าเกมสุ่มแบบผลรวมเป็นศูนย์สองผู้เล่นที่มีสถานะและการกระทำจำนวนจำกัดทุกเกมมีค่าเฉลี่ยแบบจำกัด^{[ 3 ]}และNicolas Vieilleได้แสดงให้เห็นว่าเกมสุ่มแบบสองผู้เล่นทั้งหมดที่มีพื้นที่สถานะและการกระทำจำกัดมีผลตอบแทนสมดุลเฉลี่ยแบบจำกัด^{[ 4 ]}โดยเฉพาะอย่างยิ่ง ผลลัพธ์เหล่านี้บ่งชี้ว่าเกมเหล่านี้มีค่าและผลตอบแทนสมดุลโดยประมาณ ซึ่งเรียกว่าผลตอบแทนสมดุลเฉลี่ยลิมินฟ์ (หรือผลตอบแทนสมดุลเฉลี่ยลิมินฟ์อัพ) เมื่อผลตอบแทนรวมเป็นลิมิตที่ต่ำกว่า (หรือลิมิตที่สูงกว่า) ของค่าเฉลี่ยของผลตอบแทนในแต่ละขั้นตอน ${\displaystyle \Gamma _{\infty }}$${\displaystyle v_{\infty }}$${\displaystyle \varepsilon >0}$${\displaystyle \sigma }$${\displaystyle i}$${\displaystyle \sigma }$${\displaystyle v_{\infty }^{i}-\varepsilon }$${\displaystyle \tau }$${\displaystyle v_{\infty }^{i}+\varepsilon }$

ไม่ว่าเกมสุ่มทุกเกมที่มีผู้เล่น สถานะ และการกระทำจำนวนจำกัด จะมีผลตอบแทนสมดุลที่สม่ำเสมอ หรือผลตอบแทนสมดุลเฉลี่ยแบบจำกัด หรือแม้แต่ผลตอบแทนสมดุลเฉลี่ยแบบลิมินฟ์หรือไม่นั้น ยังคงเป็นคำถามที่ท้าทายและยังไม่มีคำตอบ

โปรไฟล์กลยุทธ์เรียกว่าminmax-acceptable ^{[ 5 ] [ 6 ]}หากยูทิลิตี้ของผู้เล่นแต่ละคนมีค่าอย่างน้อยเท่ากับค่า minmax ของผู้เล่น ${\displaystyle s^{*}}$${\displaystyle s^{*}}$

$${\displaystyle u_{i}(s^{*})\geq \min _{s_{-i}}\max _{s_{i}}u_{i}(s_{-i},s_{i})}$$.

สมดุลแนชทุกแบบสามารถยอมรับได้ด้วยหลักการ minmax เนื่องจากในสมดุลแนชจะต้องมีคุณสมบัติที่เข้มงวดกว่าดังต่อไปนี้:

$${\displaystyle u_{i}(s^{*})=\max _{s_{i}}u_{i}(s_{-i}^{*},s_{i})}$$.

แต่สิ่งที่ตรงกันข้ามไม่จำเป็นต้องเป็นจริงเสมอไป Solan ^{[ 5 ]}และ Flesch และ Solan ^{[ 6 ]}ได้พิสูจน์ผลลัพธ์การมีอยู่ทั่วไปของโปรไฟล์ที่ยอมรับ Minmax ในเกมสุ่ม ซึ่งแตกต่างจากสมดุลแนชซึ่งโดยทั่วไปแล้วยังไม่เป็นที่ทราบแน่ชัดว่ามีอยู่จริงหรือไม่

สมดุลมาร์คอฟที่สมบูรณ์แบบ (Markov perfect equilibrium)เป็นการปรับปรุงแนวคิดของสมดุลแนชที่สมบูรณ์แบบในเกมย่อย (sub-game perfect Nash equilibrium)สำหรับเกมสุ่ม (stochastic games)

เกมสุ่มได้รับการรวมเข้ากับเกมเบย์เซียนเพื่อสร้างแบบจำลองความไม่แน่นอนเกี่ยวกับกลยุทธ์ของผู้เล่น^{[ 7 ]} แบบจำลอง เกมเบย์เซียนสุ่มที่ได้จะได้รับการแก้ไขผ่านการรวมกันแบบวนซ้ำของสมการสมดุลแนชแบบเบย์เซียนและสมการความเหมาะสมของเบลล์แมน

EB Dynkin ^{[ 8 ]}นำเสนอปัญหาต่อไปนี้ในทฤษฎีเกมที่เกี่ยวข้องกับการหยุดกระบวนการสุ่ม สมมติว่าเป็นลำดับที่เพิ่มขึ้นของ σ-algebras ในปริภูมิความน่าจะเป็น บางส่วนโดยที่ประกอบด้วย ทั้งหมดผู้เล่นสองคนสังเกตลำดับสุ่ม, , กล่าวคือ ฟังก์ชันที่วัดได้เทียบกับเกมสามารถหยุดได้ที่เวลา n โดยผู้เล่นคนแรกถ้าและโดยผู้เล่นคนที่สองถ้าถ้าเกมหยุดที่เวลา n ผู้เล่นคนแรกจะได้รับ จากผู้เล่นคนที่สองผู้เล่น 1 พยายามที่จะเพิ่มผลตอบแทนที่คาดหวังให้สูงสุด และผู้เล่น 2 พยายามที่จะลดให้น้อยที่สุด ${\displaystyle {\mathcal {F}}_{n},n=0,1,\ldots }$${\displaystyle (\Omega ,{\mathcal {F}},{\mathbf {P} })}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}_{n}}$${\displaystyle \{X_{n}\}_{n=1}^{\infty }}$${\displaystyle \{\varPhi _{n}\}_{n=1}^{\infty }}$${\displaystyle \{{\mathcal {F}}_{n}\}_{n=0}^{\infty }}$${\displaystyle \varPhi _{n}\geq 0}$${\displaystyle \varPhi _{n}<0}$${\displaystyle x_{n}}$

ให้เป็นเวลาแบบมาร์คอฟโดยสัมพันธ์กับฟิลเทรชันและเป็นฟังก์ชันลักษณะเฉพาะของเหตุการณ์ให้ เป็นเซตของเวลาหยุดทั้งหมดโดยสัมพันธ์กับฟิลเทรชัน, , และให้เป็นเวลาหยุดที่ผู้เล่นคนแรก (หรือผู้เล่นคนที่สอง) เลือก ผลตอบแทน ซึ่งเป็นการจ่ายเงินของผู้เล่นคนที่สองให้กับผู้เล่นคนแรก จะถูกกำหนดดังนี้ ${\displaystyle \tau }$${\displaystyle \{{\mathcal {F}}_{n}\}_{n=0}^{\infty }}$${\displaystyle \chi _{A}}$${\displaystyle A}$${\displaystyle {\mathcal {T}}}$${\displaystyle \{{\mathcal {F}}_{n}\}_{n=0}^{\infty }}$${\textstyle \Lambda =\{\lambda =\tau \chi _{\varPhi _{\tau }\geqslant 0},\tau \in {\mathcal {T}}\}}$${\textstyle \mathrm {M} =\{\mu =\tau \chi _{\varPhi _{\tau }<0},\tau \in {\mathcal {T}}\}}$${\displaystyle \lambda }$${\displaystyle \mu }$${\displaystyle R(\lambda ,\mu )={\mathbf {E} }X_{\lambda \land \mu }}$

ภายใต้เงื่อนไขที่ว่าDynkin [ ^{8 ] พิสูจน์}ว่าค่าของเกมมีอยู่จริง เขาสร้างกลยุทธ์ ε-เหมาะสมที่สุด และแนะนำเงื่อนไขหลายประการสำหรับการมีอยู่ของกลยุทธ์ที่เหมาะสมที่สุด (สำหรับการขยายเพิ่มเติม โปรดดู Neveu ^{[ 9 ]}และ Yasuda ^{[ 10 ]} ) ${\displaystyle {\mathbf {E} }(\sup _{n}|X_{n}|)<\infty }$${\displaystyle v=\sup _{\lambda \in \Lambda }\inf _{\mu \in \mathrm {M} }R(\lambda ,\mu )}$

เกมสุ่มมีการประยุกต์ใช้ในเศรษฐศาสตร์ชีววิทยาเชิงวิวัฒนาการและเครือข่ายคอมพิวเตอร์^{[ 11 ] [ 12 ]} เกมเหล่านี้เป็นการวางนัยทั่วไปของเกมซ้ำๆซึ่งสอดคล้องกับกรณีพิเศษที่มีสถานะเดียวเท่านั้น

• กระบวนการสุ่ม

• Filar, J. & Vrieze, K. (1997) กระบวนการตัดสินใจของมาร์คอฟที่แข่งขันได้ สปริงเกอร์-แวร์แลกไอเอสบีเอ็น 0-387-94805-8.
• Neyman, A. & Sorin, S. (2003). เกมสุ่มและการประยุกต์ใช้ . ดอร์เดรชท์: สำนักพิมพ์ Kluwer Academic Press. ISBN 1-4020-1492-9.
• Yoav Shoham; Kevin Leyton-Brown (2009). ระบบหลายเอเจนต์: รากฐานเชิงอัลกอริทึม ทฤษฎีเกม และตรรกะ สำนักพิมพ์มหาวิทยาลัยเค มบริดจ์ หน้า  153–156 ISBN 978-0-521-89943-7.(เหมาะสำหรับนักศึกษาปริญญาตรี; เนื้อหาหลัก ไม่มีบทพิสูจน์)

• การบรรยายเรื่องเกมสองผู้เล่นแบบสุ่ม โดย อันโตนิน คูเซรา