เกมสุ่ม

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

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

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

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

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

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

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

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

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

เกมสุ่มที่ไม่เป็นศูนย์ non ${\displaystyle \Gamma _{\infty }}$ มีผลตอบแทนสมดุลสม่ำเสมอ ${\displaystyle v_{\infty }}$ ถ้าสำหรับทุกๆ ${\displaystyle \varepsilon >0}$ มีจำนวนเต็มบวก ${\รูปแบบการแสดงผล 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 }$. Nicolas Vieilleได้แสดงให้เห็นว่าเกมสุ่มสองคนทั้งหมดที่มีสถานะ จำกัด และพื้นที่แอ็คชั่นมีผลตอบแทนสมดุลที่สม่ำเสมอ ^[4]

เกมสุ่มที่ไม่เป็นศูนย์ non ${\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 }$. Jean-François MertensและAbraham Neyman (1981) พิสูจน์ให้เห็นว่าเกมสุ่มสโตคาสติกแบบซีโร่ซัมสองคนทุกเกมที่มีสถานะและการกระทำมากมายมีค่าเฉลี่ยที่จำกัด^[3]และNicolas Vieilleได้แสดงให้เห็นว่าเกมสุ่มสองคนทั้งหมดที่มี สถานะจำกัดและพื้นที่ดำเนินการมีผลตอบแทนสมดุลที่จำกัดโดยเฉลี่ย ^[4]โดยเฉพาะอย่างยิ่ง ผลลัพธ์เหล่านี้บอกเป็นนัยว่าเกมเหล่านี้มีมูลค่าและผลตอบแทนดุลยภาพโดยประมาณ เรียกว่า liminf-average โดยเฉลี่ย (ตามลำดับคือ limsup-average) ผลตอบแทนดุลยภาพ เมื่อผลตอบแทนรวมเป็นขีดจำกัดที่ต่ำกว่า (หรือขีดจำกัดที่เหนือกว่า ) ของค่าเฉลี่ยของผลตอบแทนบนเวที

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

มาร์คอฟสมดุลที่สมบูรณ์แบบคือการปรับแต่งของแนวคิดของย่อยเกมที่สมบูรณ์แบบสมดุลของแนชกับเกมสุ่ม

เกม Stochastic ถูกรวมเข้ากับเกม Bayesianเพื่อจำลองความไม่แน่นอนเหนือกลยุทธ์ของผู้เล่น ^[5]ส่งผลให้ "สุ่มเกมเบส์" รูปแบบการแก้ไขผ่านการรวมกันเรียกซ้ำของสมการสมดุลคชกรรมแนชและสม optimality ยาม

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

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

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

• บรรยายเรื่อง Stochastic Two-Player Games โดย Antonin Kucera