นักวิจัยแก้ปัญหาทฤษฎีเกมอายุเกือบ 60 ปี

Dejan Milutinovic ศาสตราจารย์ด้านวิศวกรรมไฟฟ้าและคอมพิวเตอร์ที่ UC Santa Cruz ได้ทำงานร่วมกับเพื่อนร่วมงานเป็นเวลานานเกี่ยวกับชุดย่อยที่ซับซ้อนของทฤษฎีเกมที่เรียกว่าเกมที่แตกต่าง ซึ่งเกี่ยวข้องกับผู้เล่นเกมที่กำลังเคลื่อนไหว หนึ่งในเกมเหล่านี้เรียกว่าเกมไล่ตามกำแพง ซึ่งเป็นรูปแบบที่ค่อนข้างง่ายสำหรับสถานการณ์ที่ผู้ไล่ตามเร็วกว่ามีเป้าหมายที่จะจับผู้หลบหนีที่ช้ากว่าซึ่งถูกจำกัดให้เคลื่อนที่ไปตามกำแพง เนื่องจากเกมนี้ได้รับการอธิบายเป็นครั้งแรกเมื่อเกือบ 60 ปีที่แล้ว จึงเกิดภาวะที่กลืนไม่เข้าคายไม่ออกภายในเกม ซึ่งเป็นชุดของตำแหน่งที่คิดว่าไม่มีวิธีแก้ปัญหาที่เหมาะสมที่สุดสำหรับเกม แต่ตอนนี้ มิลูติโนวิชและเพื่อนร่วมงานของเขาได้พิสูจน์ในรายงานฉบับใหม่ที่ตีพิมพ์ในวารสารIEEE Transactions on Automatic Controlว่าภาวะที่กลืนไม่เข้าคายไม่ออกที่มีมายาวนานนี้ไม่มีอยู่จริง และแนะนำวิธีการวิเคราะห์แบบใหม่ที่พิสูจน์ว่ามีวิธีแก้ไขเชิงกำหนดเสมอสำหรับ เกมไล่ตามกำแพง การค้นพบนี้เปิดประตูสู่การแก้ปัญหาที่คล้ายคลึงกันอื่น ๆ ที่มีอยู่ในเกมที่แตกต่างกัน และช่วยให้มีเหตุผลที่ดีขึ้นเกี่ยวกับระบบอัตโนมัติ เช่น ยานพาหนะไร้คนขับ ทฤษฎีเกมถูกนำมาใช้เพื่อให้เหตุผลเกี่ยวกับพฤติกรรมในหลากหลายสาขา เช่น เศรษฐศาสตร์ รัฐศาสตร์ วิทยาการคอมพิวเตอร์ และวิศวกรรม ภายในทฤษฎีเกม ความสมดุลของ Nash เป็นหนึ่งในแนวคิดที่เป็นที่รู้จักมากที่สุด แนวคิดนี้ได้รับการแนะนำโดยนักคณิตศาสตร์ จอห์น แนช และกำหนดกลยุทธ์ที่เหมาะสมของเกมสำหรับผู้เล่นทุกคนในเกมเพื่อจบเกมด้วยความเสียใจน้อยที่สุด ผู้เล่นใดก็ตามที่เลือกที่จะไม่เล่นกลยุทธ์ที่เหมาะสมที่สุดในเกมของพวกเขาจะจบลงด้วยความเสียใจมากขึ้น ดังนั้น ผู้เล่นที่มีเหตุผลล้วนมีแรงจูงใจที่จะเล่นกลยุทธ์ที่สมดุล แนวคิดนี้ใช้กับเกมไล่ตามกำแพง ซึ่งเป็นคู่กลยุทธ์สมดุลแบบคลาสสิกของ Nash สำหรับผู้เล่นสองคน ผู้ไล่ตามและผู้หลบหลีก ซึ่งอธิบายถึงกลยุทธ์ที่ดีที่สุดของพวกเขาในเกือบทุกตำแหน่ง อย่างไรก็ตาม มีชุดของตำแหน่งระหว่างผู้ไล่ตามและผู้หลบหลีก ซึ่งการวิเคราะห์แบบคลาสสิกล้มเหลวในการให้กลยุทธ์ที่เหมาะสมที่สุดแก่ เกม และจบลงด้วยการดำรงอยู่ของภาวะที่กลืนไม่เข้าคายไม่ออก ชุดของตำแหน่งนี้เรียกว่าพื้นผิวเดี่ยว - และเป็นเวลาหลายปีที่ชุมชนการวิจัยยอมรับภาวะที่กลืนไม่เข้าคายไม่ออกว่าเป็นข้อเท็จจริง แต่มิลูติโนวิชและผู้เขียนร่วมของเขาไม่เต็มใจที่จะยอมรับสิ่งนี้ “สิ่งนี้ทำให้เรารำคาญใจเพราะเราคิดว่า หากผู้หลบเลี่ยงรู้ว่ามีพื้นผิวเดียว มีความเสี่ยงที่ผู้หลบหลีกสามารถไปที่พื้นผิวเอกพจน์และใช้งานในทางที่ผิด” มิลูติโนวิชกล่าว "ผู้หลบเลี่ยงสามารถบังคับให้คุณไปที่พื้นผิวที่เป็นเอกพจน์ซึ่งคุณไม่รู้ว่าควรปฏิบัติตัวอย่างไรอย่างเหมาะสม - จากนั้นเราก็ไม่รู้ว่าผลที่ตามมาในเกมที่ซับซ้อนกว่านี้คืออะไร" ดังนั้น มิลูติโนวิชและผู้เขียนร่วมของเขาจึงคิดวิธีใหม่ในการแก้ปัญหา โดยใช้แนวคิดทางคณิตศาสตร์ที่ไม่มีอยู่จริงในตอนที่เกมวิ่งไล่ตามกำแพงถือกำเนิดขึ้น ด้วยการใช้สารละลายความหนืดของสมการแฮมิลตัน-จาโคบี-ไอแซกส์ และแนะนำการวิเคราะห์อัตราการสูญเสียสำหรับการแก้พื้นผิวเอกพจน์ พวกเขาสามารถค้นพบว่าโซลูชันที่เหมาะสมที่สุดในเกมสามารถกำหนดได้ในทุกสถานการณ์ของเกมและแก้ปัญหาที่กลืนไม่เข้าคายไม่ออก คำตอบของความหนืดของสมการเชิงอนุพันธ์ย่อยเป็นแนวคิดทางคณิตศาสตร์ที่ไม่มีอยู่จริงจนกระทั่งทศวรรษที่ 1980 และนำเสนอแนวเหตุผลเฉพาะเกี่ยวกับการแก้สมการแฮมิลตัน-จาโคบี-ไอแซกส์ ตอนนี้เป็นที่ทราบกันดีว่าแนวคิดนี้เกี่ยวข้องกับการให้เหตุผลเกี่ยวกับการควบคุมที่เหมาะสมและปัญหาทฤษฎีเกม การใช้สารละลายความหนืดซึ่งเป็นฟังก์ชันในการแก้ปัญหาทฤษฎีเกมเกี่ยวข้องกับการใช้แคลคูลัสเพื่อหาอนุพันธ์ของฟังก์ชันเหล่านี้ การค้นหาโซลูชันที่เหมาะสมที่สุดในเกมค่อนข้างง่ายเมื่อโซลูชันความหนืดที่เกี่ยวข้องกับเกมมีอนุพันธ์ที่กำหนดไว้อย่างดี นี่ไม่ใช่กรณีของเกมไล่ล่าบนกำแพง และการขาดอนุพันธ์ที่ชัดเจนทำให้เกิดภาวะที่กลืนไม่เข้าคายไม่ออก โดยทั่วไปเมื่อเกิดภาวะที่กลืนไม่เข้าคายไม่ออก แนวทางปฏิบัติคือให้ผู้เล่นสุ่มเลือกการกระทำที่เป็นไปได้อย่างใดอย่างหนึ่งและยอมรับความสูญเสียที่เกิดจากการตัดสินใจเหล่านี้ แต่นี่คือสิ่งที่จับต้องได้: หากมีการสูญเสีย ผู้เล่นที่มีเหตุผลแต่ละคนจะต้องการลดการสูญเสียให้เหลือน้อยที่สุด ดังนั้น เพื่อหาวิธีลดการสูญเสียของผู้เล่น ผู้เขียนจึงวิเคราะห์วิธีแก้ปัญหาความหนืดของสมการแฮมิลตัน-จาโคบี-ไอแซกส์รอบๆ พื้นผิวเอกพจน์ซึ่งอนุพันธ์ไม่ได้กำหนดไว้อย่างดี จากนั้นจึงแนะนำการวิเคราะห์อัตราการสูญเสียในสถานะพื้นผิวเอกพจน์เหล่านี้ของสมการ พวกเขาพบว่าเมื่อนักแสดงแต่ละคนลดอัตราการสูญเสียให้เหลือน้อยที่สุด จะมีกลยุทธ์เกมที่ชัดเจนสำหรับการกระทำของพวกเขาบนพื้นผิวเดียว ผู้เขียนพบว่าอัตราการลดการสูญเสียนี้ไม่เพียงแต่กำหนดการกระทำที่เหมาะสมของเกมสำหรับพื้นผิวเอกพจน์เท่านั้น แต่ยังสอดคล้องกับการกระทำที่เหมาะสมของเกมในทุกสถานะที่เป็นไปได้ ซึ่งการวิเคราะห์แบบดั้งเดิมก็สามารถค้นหาการกระทำเหล่านี้ได้เช่นกัน “เมื่อเรานำการวิเคราะห์อัตราการสูญเสียไปใช้ที่อื่น การดำเนินการที่เหมาะสมของเกมจากการวิเคราะห์แบบดั้งเดิมจะไม่ได้รับผลกระทบ” มิลูติโนวิชกล่าว "เราใช้ทฤษฎีคลาสสิกและเสริมด้วยการวิเคราะห์อัตราการสูญเสีย ดังนั้นจึงมีวิธีแก้ปัญหาอยู่ทุกที่ นี่คือผลลัพธ์สำคัญที่แสดงให้เห็นว่าการเสริมนั้นไม่ใช่แค่การแก้ไขเพื่อหาทางออกบนพื้นผิวเอกพจน์ แต่เป็นการสนับสนุนพื้นฐาน ไปจนถึงทฤษฎีเกม Milutinovic และผู้เขียนร่วมของเขาสนใจที่จะสำรวจปัญหาทฤษฎีเกมอื่นๆ เกี่ยวกับพื้นผิวเอกพจน์ ซึ่งสามารถนำวิธีการใหม่ไปใช้ได้ บทความนี้ยังเป็นการเรียกร้องให้ชุมชนการวิจัยตรวจสอบประเด็นขัดแย้งอื่น ๆ ในทำนองเดียวกัน "ตอนนี้คำถามคือ เราจะแก้ปัญหาอื่น ๆ แบบไหนได้บ้าง" มิลูติโนวิชกล่าว