สมดุลของแนช
- ผู้เสนอ
- John Nash
- ปี
- 1950
- ประเภท
- algorithm
- กลุ่มวิธี
- Game-theoretic
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
สมดุลของแนชเป็นแนวคิดการแก้ปัญหาทฤษฎีเกมที่ผู้เล่นแต่ละคนไม่สามารถเปลี่ยนแปลงกลยุทธ์ของตนเองฝ่ายเดียวเพื่อเพิ่มผลตอบแทนได้ แนวคิดนี้ถูกทำให้เป็นรูปธรรมโดย จอห์น แนช ในปี 1950 อัลกอริทึมของเลมเค-เฮาซันใช้ในการคำนวณหาจุดสมดุลในเกมแบบสองเมทริกซ์ โดยการระบุคู่ของจุดยอดที่มีป้ายกำกับสมบูรณ์ในโพลีโทปกลยุทธ์
แนวคิดเบื้องหลังวิธีการ
ในสมดุลของแนช กลยุทธ์ของผู้เล่นแต่ละคนเป็นการตอบสนองที่ดีที่สุดต่อกลยุทธ์ของผู้เล่นคนอื่น ๆ ลองนึกภาพสถานการณ์ที่ผู้เล่นทั้งสองฝ่ายทราบกลยุทธ์ของอีกฝ่าย: จะไม่มีใครอยากเปลี่ยนแปลง เพราะการทำเช่นนั้นจะส่งผลเสียต่อตนเองเท่านั้น อัลกอริทึมของเลมเค-เฮาซันใช้ประโยชน์จากโครงสร้างทางเรขาคณิตของโพลีฮีดราของเกม โดยติดตามป้ายกำกับ (ข้อจำกัดที่ไม่ได้รับการตอบสนอง) และการหมุนเวียนผ่านจุดยอด จนกว่าจะพบคู่ที่มีป้ายกำกับสมบูรณ์ ซึ่งเป็นสถานการณ์ที่ผู้เล่นทั้งสองฝ่ายไม่มีการเปลี่ยนแปลงที่ให้ผลกำไร
ประวัติศาสตร์
จอห์น แนช พิสูจน์ในการศึกษาระดับปริญญาเอกของเขาในปี 1950 ว่าทุกเกมที่มีจำกัดมีสมดุลกลยุทธ์แบบผสมอย่างน้อยหนึ่งสมดุล ในปี 1964 เลมเคและเฮาซันได้ตีพิมพ์อัลกอริทึมเชิงสร้างสรรค์แรกสำหรับการค้นหาสมดุลเหล่านี้ โดยเปลี่ยนการพิสูจน์การมีอยู่ของแนชให้เป็นวิธีการคำนวณที่ใช้งานได้จริง ผลงานของพวกเขาได้กลายเป็นรากฐานสำหรับทฤษฎีเกมเชิงคำนวณและเศรษฐศาสตร์เชิงอัลกอริทึม
ควรใช้เมื่อใด
ใช้การวิเคราะห์สมดุลของแนชเมื่อศึกษาเกมที่มีผู้เล่นสองคนและปริภูมิกลยุทธ์แบบไม่ต่อเนื่อง หรือเมื่อต้องการหาจุดสมดุลแบบผสมที่สมบูรณ์ เหมาะสำหรับการจำลองปัญหาการแข่งขัน การเจรจาต่อรอง และการประสานงานที่ปฏิสัมพันธ์เชิงกลยุทธ์มีความสำคัญสูงสุด วิธีการของเลมเค-เฮาซันทำงานได้ดีที่สุดสำหรับเกมสองเมทริกซ์ที่ไม่เสื่อมสภาพ กรณีที่เสื่อมสภาพอาจต้องใช้การคำนวณเชิงสัญลักษณ์หรือการรบกวน
ข้อจำกัดและข้อควรพิจารณา
- จำกัดเฉพาะเกมสองผู้เล่น (สองเมทริกซ์); การขยายไปยังเกม n-ผู้เล่นเป็นปัญหา NP-hard
- ล้มเหลวหรือไม่ก็ไม่มีประสิทธิภาพกับเกมที่เสื่อมสภาพซึ่งมีจุดหมุนเข้าได้หลายจุด
- อาจพบเพียงสมดุลเดียว; บ่อยครั้งมีสมดุลหลายจุดในเกมที่ไม่ใช่ผลรวมเป็นศูนย์
- ไม่ได้จัดการกับเกมแบบไดนามิกหรือเกมแบบขยายโดยตรงหากไม่ปรับรูปแบบ
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- มีประสิทธิภาพในการคำนวณเพื่อหาจุดสมดุลของแนชในเกมสองเมทริกซ์แบบจำกัด
- รับประกันการลู่เข้าสู่คู่จุดยอดที่มีป้ายกำกับสมบูรณ์สำหรับเกมที่ไม่เสื่อมสภาพ
- ให้รากฐานทางทฤษฎีที่เชื่อมโยงเรขาคณิตเชิงการจัดหมู่กับทฤษฎีเกม
- สามารถนำไปใช้กับสมดุลกลยุทธ์แบบผสม ซึ่งมักจะสมจริงกว่าผลลัพธ์กลยุทธ์แบบบริสุทธิ์
การประยุกต์ใช้
- เศรษฐศาสตร์: การจำลองการแข่งขันแบบผู้ขายน้อยราย (oligopolistic competition) และพฤติกรรมการกำหนดราคาในตลาด
- การประมูลและการออกแบบกลไก: การวิเคราะห์กลยุทธ์การเสนอราคาในการประมูลแบบราคาแรกและแบบปิดผนึก
- ความปลอดภัยทางไซเบอร์: การคาดการณ์สมดุลระหว่างผู้โจมตีและผู้ป้องกันในเกมความปลอดภัยเครือข่าย
- ชีววิทยาทางป่า: การวิเคราะห์กลยุทธ์ที่เสถียรเชิงวิวัฒนาการในการปฏิสัมพันธ์ระหว่างผู้ล่าและเหยื่อ
วิธีการทำงาน
วิธีการทำงาน
แปลงเกมสองเมทริกซ์ให้เป็นปัญหาการเติมเต็มเชิงเส้น (LCP) สองปัญหา โดยปัญหาหนึ่งสำหรับผู้เล่นแต่ละคน ซึ่งแสดงถึงเงื่อนไขการตอบสนองที่ดีที่สุดของพวกเขา
กำหนดป้ายกำกับให้กับขอบและจุดยอดของโพลีโทปกลยุทธ์ โดยอิงตามแรงจูงใจของผู้เล่นที่ถูกละเมิด
เริ่มต้นจากจุดยอดที่เป็นค่าหนึ่งทั้งหมด (มีป้ายกำกับสมบูรณ์) ดำเนินการหมุนเวียนคล้ายซิมเพล็กซ์เพื่อนำทางโพลีโทป โดยการลบและเพิ่มป้ายกำกับ จนกว่าจะค้นพบคู่ที่มีป้ายกำกับสมบูรณ์
ยืนยันว่ากลยุทธ์ของผู้เล่นทั้งสองฝ่ายเป็นการตอบสนองซึ่งกันและกันที่ดีที่สุด โดยการตรวจสอบว่าไม่มีใครสามารถเพิ่มผลตอบแทนได้เมื่อพิจารณากลยุทธ์ของอีกฝ่าย
ข้อผิดพลาดที่พบบ่อย
- สมมติว่ามีสมดุลที่ไม่ซ้ำกันอยู่; เกมจำนวนมากมีสมดุลของแนชหลายจุดที่มีผลตอบแทนแตกต่างกัน
- การสับสนระหว่างสมดุลกลยุทธ์แบบผสม (การเล่นแบบสุ่ม) กับสมดุลกลยุทธ์แบบบริสุทธิ์ นำไปสู่การตีความพฤติกรรมของตัวแทนที่ผิดพลาด
- การมองข้ามความแตกต่างระหว่างเงื่อนไขที่จำเป็นและเพียงพอสำหรับสมดุล; คู่ที่มีป้ายกำกับสมบูรณ์สอดคล้องกับความเป็นเลิศ แต่ก็อาจไม่เกิดขึ้นจริงหากผู้เล่นไม่สามารถประสานงานกันได้
คำถามที่พบบ่อย
เกมสามารถไม่มีสมดุลของแนชได้หรือไม่?
สมดุลของแนชแบบบริสุทธิ์อาจไม่มีอยู่ (เช่น เกมเป่ายิ้งฉุบ) แต่ทุกเกมที่มีจำกัดมีสมดุลกลยุทธ์แบบผสมอย่างน้อยหนึ่งสมดุล ซึ่งผู้เล่นจะสุ่มเลือกการกระทำด้วยความน่าจะเป็นที่แน่นอน
สมดุลกลยุทธ์แบบผสมแตกต่างจากสมดุลกลยุทธ์แบบบริสุทธิ์อย่างไร?
ในสมดุลกลยุทธ์แบบบริสุทธิ์ ผู้เล่นแต่ละคนจะยึดติดกับการกระทำที่เฉพาะเจาะจงอย่างแน่นอน ในสมดุลกลยุทธ์แบบผสม ผู้เล่นแต่ละคนจะใช้การแจกแจงความน่าจะเป็นเหนือการกระทำ สมดุลแบบผสมมักจะมีความทั่วไปมากกว่าและมีอยู่เมื่อไม่มีสมดุลแบบบริสุทธิ์
เหตุใดอัลกอริทึมของเลมเค-เฮาซันจึงเป็นที่นิยมมากกว่าการค้นหาแบบ brute-force?
อัลกอริทึมใช้ประโยชน์จากโครงสร้างโพลีโทปของปริภูมิกลยุทธ์ ลดปริภูมิการค้นหาแบบทวีคูณ และบรรลุการลู่เข้าในเวลาพหุนามสำหรับเกมที่ไม่เสื่อมสภาพ ในขณะที่การแจงนับแบบ brute-force จะไม่สามารถทำได้เมื่อปริภูมิกลยุทธ์เติบโตขึ้น
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วLemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว