Skip to content
กลับไปยังผลการค้นหา

สมดุลของแนช

ผู้เสนอ
John Nash
ปี
1950
ประเภท
algorithm
กลุ่มวิธี
Game-theoretic

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

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

แนวคิดเบื้องหลังวิธีการ

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

ประวัติศาสตร์

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

ควรใช้เมื่อใด

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

ข้อจำกัดและข้อควรพิจารณา

  • จำกัดเฉพาะเกมสองผู้เล่น (สองเมทริกซ์); การขยายไปยังเกม n-ผู้เล่นเป็นปัญหา NP-hard
  • ล้มเหลวหรือไม่ก็ไม่มีประสิทธิภาพกับเกมที่เสื่อมสภาพซึ่งมีจุดหมุนเข้าได้หลายจุด
  • อาจพบเพียงสมดุลเดียว; บ่อยครั้งมีสมดุลหลายจุดในเกมที่ไม่ใช่ผลรวมเป็นศูนย์
  • ไม่ได้จัดการกับเกมแบบไดนามิกหรือเกมแบบขยายโดยตรงหากไม่ปรับรูปแบบ

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

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

การประยุกต์ใช้

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

วิธีการทำงาน

วิธีการทำงาน

1

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

2

กำหนดป้ายกำกับให้กับขอบและจุดยอดของโพลีโทปกลยุทธ์ โดยอิงตามแรงจูงใจของผู้เล่นที่ถูกละเมิด

3

เริ่มต้นจากจุดยอดที่เป็นค่าหนึ่งทั้งหมด (มีป้ายกำกับสมบูรณ์) ดำเนินการหมุนเวียนคล้ายซิมเพล็กซ์เพื่อนำทางโพลีโทป โดยการลบและเพิ่มป้ายกำกับ จนกว่าจะค้นพบคู่ที่มีป้ายกำกับสมบูรณ์

4

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

ข้อผิดพลาดที่พบบ่อย

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

คำถามที่พบบ่อย

เกมสามารถไม่มีสมดุลของแนชได้หรือไม่?

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

สมดุลกลยุทธ์แบบผสมแตกต่างจากสมดุลกลยุทธ์แบบบริสุทธิ์อย่างไร?

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

เหตุใดอัลกอริทึมของเลมเค-เฮาซันจึงเป็นที่นิยมมากกว่าการค้นหาแบบ brute-force?

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

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. 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
    คัดลอกแล้ว