สมดุลแบบแนช

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

ประวัติ

ชื่อแนวคิดสมดุลแบบแนชมีที่มาจากจอห์น แนช ผู้ที่นิยามแนวคิดสมดุลในรูปแบบที่ใช้กันในปัจจุบันเมื่อปี 1950 แต่การใช้แนวคิดที่มีลักษณะของสมดุลแบบแนชนั้นย้อนไปได้ถึงงานเขียนของอ็องตวน-โอกุสแต็ง กูร์โน ที่ตีพิมพ์ในปี 1838^[1] ในหนังสือ Recherches sur les principes mathématiques de la théorie des richesses (ฝรั่งเศส: งานวิจัยว่าด้วยหลักคณิตศาสตร์ของทรัพยศาสตร์) กูร์โนได้เขียนถึงวิเคราะห์การแข่งขันระหว่างผู้ผลิตสินค้าในตลาดผู้ขายน้อยราย (เรียกภายหลังว่าเป็นแบบจำลองการแข่งขันแบบกูร์โน) ในแบบจำลองนี้ กำไรของผู้ผลิตสินค้าแต่ละราย ไม่เพียงขึ้นอยู่กับปริมาณการผลิตของตัวเอง แต่ขึ้นอยู่กับการผลิตของคู่แข่งด้วย ผลลัพธ์ของแบบจำลองของกูร์โนเป็นจุดสมดุลแบบแนชรูปแบบหนึ่ง แต่กูร์โนไม่ได้ขยายความให้แนวคิดมีนัยทั่วไปกับสถานการณ์อื่นๆ^[2]

แนวคิดทฤษฎีเกมในแบบที่ใช้กันในปัจจุบัน มีรากฐานจากงานของจอห์น ฟอน นอยมันน์และอ็อสคาร์ มอร์เกินสแตร์น ในหนังสือ The Theory of Games and Economic Behavior (อังกฤษ: ทฤษฎีว่าด้วยเกมและพฤติกรรมทางเศรษฐกิจ) ซึ่งตีพิมพ์ครั้งแรกในปี 1944 ได้นิยามเกมและแนวคิดกลยุทธ์แบบผสม ซึ่งเป็นหมายถึงการที่ผู้เล่นในเกมเลือกแจกแจงความน่าจะเป็นที่จะใช้ทางเลือกแต่ละทางที่ตนเองมี หนังสือยกตัวอย่างแนวคิดกลยุทธ์แบบผสมในเกมเป่ายิ้งฉุบว่า "สามัญสำนึกจะบอกได้ว่าวิธีที่ดีที่จะเล่นเกมนี้คือการเลือกทางเลือกทั้งสามทางด้วยความน่าจะเป็นแต่ละทางเท่ากับ 1/3"^[3] ฟอนนอยมันน์กับมอร์เกินสแตร์นได้เสนอแนวคิดคำตอบของเกมที่มีกลยุทธ์แต่ผสม แต่แนวคิดนี้ใช้ได้เฉพาะกับเกมผลรวมเป็นศูนย์

ในปี 1950 จอห์น แนชได้นิยามกลยุทธ์แบบผสมสำหรับเกมใดๆ ที่ผู้เล่นมีทางเลือกจำกัด และพิสูจน์ว่าสมดุลชนิดนี้มีอยู่ในเกมลักษณะดังกล่าวใดๆ ที่ผู้เล่นสามารถใช้กลยุทธ์แบบผสม บทพิสูจน์ในตอนแรกของแนชใช้ทฤษฎีบทจุดตรึงของคาคูทานิ^[4] ถัดมาในปี 1951 แนชได้ตีพิมพ์บทความวิชาการอีกบทความหนึ่งซึ่งใช้ทฤษฎีบทจุดตรึงของเบราเวอร์ในการพิสูจน์แทน^[5]

นิยาม

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

เซตของผู้เล่น $N=\{1,2,\dots ,n\}$
เซตของกลยุทธ์ $S_{i}$ สำหรับผู้เล่น $i$ แต่ละคนในเซตผู้เล่น
ค่าอรรถประโยชน์ $u_{i}(s_{1},s_{2},\dots ,s_{n})$ สำหรับผู้เล่น $i$ แต่ละคนในเซตผู้เล่น ที่อิงจากกลยุทธ์ $s_{1},s_{2},\dots ,s_{n}$ ที่ผู้เล่นแต่ละคนเลือก

โพรไฟล์กลยุทธ์ (อังกฤษ: strategy profile) หมายถึงเวกเตอร์ที่ระบุกลยุทธ์ของผู้เล่นทุกคน นั่นคือ $s=(s_{1},s_{2},\dots ,s_{n})$ และใช้สัญลักษณ์ $s_{-i}$ หมายถึงโพรไฟล์กลยุทธ์ของผู้เล่นทุกคนยกเว้น $i$ ค่าอรรถประโยชน์ของผู้เล่น $i$ จึงสามารถเขียนได้เป็น $u_{i}(s)$ และ $u_{i}(s_{i},s_{-i})$ ด้วย

จากนิยามเกมข้างต้น โพร์ไฟล์กลยุทธ์ $s^{*}=(s_{1}^{*},s_{2}^{*},\dots ,s_{n}^{*})$ ถือว่าเป็นจุดสมดุลแบบแนช ถ้ากลยุทธ์ $s_{i}^{*}$ ที่ผู้เล่น $i$ เลือก เป็นกลยุทธ์ที่ให้อรรถประโยชน์สูงสุดแก่ผู้เล่น $i$ เมื่อผู้เล่นคนอื่นๆ เลือกเล่นกลยุทธ์ที่ระบุใน $s^{*}$ กล่าวอีกทางหนึ่งคือ ผู้เล่นแต่ละคนในเกมไม่สามารถทำให้อรรถประโยชน์ของตัวเองสูงขึ้นด้วยการเลือกกลยุทธ์อื่นที่ไม่ใช่ $s_{i}^{*}$ ตราบใดที่ผู้เล่นคนอื่นทุกคนเลือกกลยุทธ์ของตัวเองตามที่กำหนดในโพรไฟล์กลยุทธ์ $s^{*}$ เงื่อนไขนี้เขียนด้วยสัญลักษณ์ทางคณิตศาสตร์ได้ว่า $\forall i\in N,\forall s_{i}'\in S_{i}:u_{i}(s^{*})\geq u_{i}(s_{i}',s_{-i}^{*})$ ^[6]

ทฤษฎีบทของแนชพิจารณาเกมที่สามารถมีกลยุทธ์แบบผสมได้ กลยุทธ์แบบผสม หมายถึงการที่ผู้เล่นแต่ละคนเลือกความน่าจะเป็นที่จะเลือกทางเลือกแต่ละทางให้แก่ทุกสมาชิกในเซตกลยุทธ์ (ความน่าจะเป็นของสมาชิกแต่ละอันอาจจะเป็น 0 หรือ 1 ได้) โดยผลรวมของความน่าจะเป็นของทุกตัวเลือกเท่ากับ 1 ตามนิยามของการแจกแจงความน่าจะเป็น ในกรณีนี้ เซตกลยุทธ์ที่เป็นกลยุทธ์แบบผสม จะกลายเป็นมีลักษณะเป็นซิมเพล็กซ์แทน^[6]

การมีอยู่ของสมดุลแบบแนช

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

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

อ้างอิง

↑ Kreps, David M. (2018) [1987]. "Nash Equilibrium". ใน Macmillan Publishers (บ.ก.). The New Palgrave Dictionary of Economics (ภาษาอังกฤษ) (3 ed.). Palgrave Macmillan. pp. 9251–9258. doi:10.1057/978-1-349-95121-5_963-1. ISBN 978-1-349-95188-8.
↑ Watson, Joel (2018) [2008]. "Nash, John Forbes (Born 1928)". ใน Macmillan Publishers (บ.ก.). The New Palgrave Dictionary of Economics (ภาษาอังกฤษ) (3 ed.). Palgrave Macmillan. pp. 9276–9283. doi:10.1057/978-1-349-95121-5_1957-1. ISBN 978-1-349-95121-5.
↑ Von Neumann, John; Morgenstern, Oskar (1953). Theory of Games and Economic Behavior (ภาษาอังกฤษ) (3 ed.). Princeton: Princeton University Press. OCLC 10006173.
↑ ^4.0 ^4.1 Nash, John F. (1950). "Equilibrium points in n-person games". Proceedings of the National Academy of Sciences. 36 (1): 48–49. doi:10.1073/pnas.36.1.48. ISSN 0027-8424. PMID 16588946.
↑ Nash, John (1951). "Non-cooperative games". Annals of Mathematics. 54 (2): 286–295. doi:10.2307/1969529. ISSN 0003-486X. JSTOR 1969529.
↑ ^6.0 ^6.1 ^6.2 Fudenberg, Drew; Tirole, Jean (1991). Game Theory (ภาษาอังกฤษ). Cambridge, Massachusetts: MIT Press. ISBN 978-0-262-06141-4.

[Palgrave_Nash_equilibrium-1] Kreps, David M. (2018) [1987]. "Nash Equilibrium". ใน Macmillan Publishers (บ.ก.). The New Palgrave Dictionary of Economics (ภาษาอังกฤษ) (3 ed.). Palgrave Macmillan. pp. 9251–9258. doi:10.1057/978-1-349-95121-5_963-1. ISBN 978-1-349-95188-8.

[Palgrave_Nash-2] Watson, Joel (2018) [2008]. "Nash, John Forbes (Born 1928)". ใน Macmillan Publishers (บ.ก.). The New Palgrave Dictionary of Economics (ภาษาอังกฤษ) (3 ed.). Palgrave Macmillan. pp. 9276–9283. doi:10.1057/978-1-349-95121-5_1957-1. ISBN 978-1-349-95121-5.

[VonNeumann-Morgenstern-3] Von Neumann, John; Morgenstern, Oskar (1953). Theory of Games and Economic Behavior (ภาษาอังกฤษ) (3 ed.). Princeton: Princeton University Press. OCLC 10006173.

[Nash_1950-4] 4.0 ^4.1 Nash, John F. (1950). "Equilibrium points in n-person games". Proceedings of the National Academy of Sciences. 36 (1): 48–49. doi:10.1073/pnas.36.1.48. ISSN 0027-8424. PMID 16588946.

[Nash-5] Nash, John (1951). "Non-cooperative games". Annals of Mathematics. 54 (2): 286–295. doi:10.2307/1969529. ISSN 0003-486X. JSTOR 1969529.

[Fudenberg-Tirole-6] 6.0 ^6.1 ^6.2 Fudenberg, Drew; Tirole, Jean (1991). Game Theory (ภาษาอังกฤษ). Cambridge, Massachusetts: MIT Press. ISBN 978-0-262-06141-4.

[1]

[2]

[3]

[4]

[5]

[6]