ทฤษฎีเกมสำหรับเอเจนต์

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

Definition

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

Scope

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

Core questions

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

Key concepts

• เกมรูปแบบปกติและรูปแบบขยาย
• ผลตอบแทนและกลยุทธ์
• กลยุทธ์เด่น
• ดุลยภาพแบบแนช
• กลยุทธ์แบบผสม
• เกมผลรวมเป็นศูนย์และมินิแม็กซ์
• ปัญหาของนักโทษ
• การคำนวณดุลยภาพ

Key theories

ดุลยภาพแบบแนช

ดุลยภาพแบบแนชคือชุดของกลยุทธ์ที่ไม่มีเอเจนต์ใดสามารถปรับปรุงผลตอบแทนของตนได้ด้วยการเปลี่ยนกลยุทธ์ของตนฝ่ายเดียว; แนชพิสูจน์ว่าทุกเกมจำกัดมีดุลยภาพอย่างน้อยหนึ่งชุด ซึ่งอาจเป็นในกลยุทธ์แบบผสม

มินิแม็กซ์ในเกมผลรวมเป็นศูนย์

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

กลยุทธ์เด่นและภาวะกลืนไม่เข้าคายไม่ออก

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

Clinical relevance

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

History

ทฤษฎีเกมก่อตั้งโดยฟอน นอยมันน์และมอร์เกนสเติร์น (1944) และขยายโดยแนวคิดดุลยภาพของแนช (1950) ซึ่งกลายเป็นแกนหลักของเศรษฐศาสตร์ และตั้งแต่ทศวรรษ 1990 เป็นต้นมา ได้เข้ามามีบทบาทสำคัญใน AI และวิทยาการคอมพิวเตอร์ผ่านทฤษฎีเกมเชิงอัลกอริทึม ซึ่งศึกษาความซับซ้อนในการคำนวณของดุลยภาพและการใช้งานในระบบหลายเอเจนต์

Key figures

• John von Neumann
• Oskar Morgenstern
• John F. Nash
• Yoav Shoham
• Kevin Leyton-Brown

Seminal works

• nash1950
• vonneumann1944
• shoham2009

Frequently asked questions

ดุลยภาพแบบแนชคืออะไร?

ดุลยภาพแบบแนชคือการรวมกันของกลยุทธ์ โดยมีหนึ่งกลยุทธ์ต่อเอเจนต์ ซึ่งไม่มีเอเจนต์ใดสามารถทำได้ดีกว่าด้วยการเปลี่ยนกลยุทธ์ของตนเองเท่านั้น ในขณะที่เอเจนต์อื่น ๆ ยังคงกลยุทธ์เดิมไว้ มันแสดงถึงแนวคิดของพฤติกรรมที่มีเหตุผลที่เสถียรและสอดคล้องกัน

ทำไมปัญหาของนักโทษจึงมีความสำคัญต่อเอเจนต์ AI?

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