สมดุลแบบแนช

สมดุลแบบแนช (Nash equilibrium) เป็นแนวคิดในวิชาทฤษฎีเกมที่อธิบายสถานการณ์ที่ผู้เล่นแต่ละคนเลือกทางเลือกที่ดีสุดสำหรับตัวเองเมื่อพิจารณาถึงทางเลือกของผู้เล่นอื่นในจุดสมดุลนั้น ผู้เล่นแต่ละคนจึงไม่สามารถได้ประโยชน์มากขึ้นด้วยการเปลี่ยนทางเลือกของตัวเองแต่เพียงฝ่ายเดียวได้ในจุดสมดุล สมดุลแบบแนชเรียกตามชื่อของจอห์น แนช นักคณิตศาสตร์ซึ่งเป็นผู้นิยามสมดุลในลักษณะนี้
== ประวัติ ==
ชื่อแนวคิดสมดุลแบบแนชมีที่มาจากจอห์น แนช ผู้ที่นิยามแนวคิดสมดุลในรูปแบบที่ใช้กันในปัจจุบันเมื่อปี 1950 แต่การใช้แนวคิดที่มีลักษณะของสมดุลแบบแนชนั้นย้อนไปได้ถึงงานเขียนของอ็องตวน-โอกุสแต็ง กูร์โน ที่ตีพิมพ์ในปี 1838
ในหนังสือ Recherches sur les principes mathématiques de la théorie des richesses (งานวิจัยว่าด้วยหลักคณิตศาสตร์ของทรัพยศาสตร์) กูร์โนได้เขียนถึงวิเคราะห์การแข่งขันระหว่างผู้ผลิตสินค้าในตลาดผู้ขายน้อยราย (เรียกภายหลังว่าเป็นแบบจำลองการแข่งขันแบบกูร์โน) ในแบบจำลองนี้ กำไรของผู้ผลิตสินค้าแต่ละราย ไม่เพียงขึ้นอยู่กับปริมาณการผลิตของตัวเอง แต่ขึ้นอยู่กับการผลิตของคู่แข่งด้วย ผลลัพธ์ของแบบจำลองของกูร์โนเป็นจุดสมดุลแบบแนชรูปแบบหนึ่ง แต่กูร์โนไม่ได้ขยายความให้แนวคิดมีนัยทั่วไปกับสถานการณ์อื่นๆ
แนวคิดทฤษฎีเกมในแบบที่ใช้กันในปัจจุบัน มีรากฐานจากงานของจอห์น ฟอน นอยมันน์และอ็อสคาร์ มอร์เกินสแตร์น ในหนังสือ The Theory of Games and Economic Behavior (ทฤษฎีว่าด้วยเกมและพฤติกรรมทางเศรษฐกิจ) ซึ่งตีพิมพ์ครั้งแรกในปี 1944 ได้นิยามเกมและแนวคิดกลยุทธ์แบบผสม ซึ่งเป็นหมายถึงการที่ผู้เล่นในเกมเลือกแจกแจงความน่าจะเป็นที่จะใช้ทางเลือกแต่ละทางที่ตนเองมี หนังสือยกตัวอย่างแนวคิดกลยุทธ์แบบผสมในเกมเป่ายิ้งฉุบว่า "สามัญสำนึกจะบอกได้ว่าวิธีที่ดีที่จะเล่นเกมนี้คือการเลือกทางเลือกทั้งสามทางด้วยความน่าจะเป็นแต่ละทางเท่ากับ 1/3" ฟอนนอยมันน์กับมอร์เกินสแตร์นได้เสนอแนวคิดคำตอบของเกมที่มีกลยุทธ์แต่ผสม แต่แนวคิดนี้ใช้ได้เฉพาะกับเกมผลรวมเป็นศูนย์
ในปี 1950 จอห์น แนชได้นิยามกลยุทธ์แบบผสมสำหรับเกมใดๆ ที่ผู้เล่นมีทางเลือกจำกัด และพิสูจน์ว่าสมดุลชนิดนี้มีอยู่ในเกมลักษณะดังกล่าวใดๆ ที่ผู้เล่นสามารถใช้กลยุทธ์แบบผสม บทพิสูจน์ในตอนแรกของแนชใช้ทฤษฎีบทจุดตรึงของคาคูทานิ ถัดมาในปี 1951 แนชได้ตีพิมพ์บทความวิชาการอีกบทความหนึ่งซึ่งใช้ทฤษฎีบทจุดตรึงของเบราเวอร์ในการพิสูจน์แทน
== นิยาม ==
ในทางทฤษฎีเกม การนิยามเกมแบบพื้นฐานประกอบไปด้วยองค์ประกอบสามอย่าง ได้แก่ ผู้เล่น ทางเลือกของผู้เล่นแต่ะละคนในเกม (เรียกในทฤษฎีเกมว่า "กลยุทธ์") และความพึงพอใจของผู้เล่นแต่ละคนที่มีต่อผลลัพธ์แต่ละแบบของเกม ซึ่งมักเขียนในรูปแบบที่เรียกว่าฟังก์ชันอรรถประโยชน์ ค่าของอรรถประโยชน์ของผู้เล่นแต่ละคน ขึ้นอยู่กับกลยุทธ์ของผู้เล่นทุกคนในเกม หากเขียนด้วยสัญลักษณ์ทางคณิตศาสตร์ นิยามพื้นฐานของเกมสามารถกำหนดได้ดังต่อไปนี้
เซตของผู้เล่น  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})
ทฤษฎีบทของแนชพิจารณาเกมที่สามารถมีกลยุทธ์แบบผสมได้ กลยุทธ์แบบผสม หมายถึงการที่ผู้เล่นแต่ละคนเลือกความน่าจะเป็นที่จะเลือกทางเลือกแต่ละทางให้แก่ทุกสมาชิกในเซตกลยุทธ์ (ความน่าจะเป็นของสมาชิกแต่ละอันอาจจะเป็น 0 หรือ 1 ได้) โดยผลรวมของความน่าจะเป็นของทุกตัวเลือกเท่ากับ 1 ตามนิยามของการแจกแจงความน่าจะเป็น ในกรณีนี้ เซตกลยุทธ์ที่เป็นกลยุทธ์แบบผสม จะกลายเป็นมีลักษณะเป็นซิมเพล็กซ์แทน
== การมีอยู่ของสมดุลแบบแนช ==
แนชพิสูจน์ว่า ถ้าหากเกมมีจำนวนผู้เล่นจำกัด และผู้เล่นแต่ละคนมีเซตกลยุทธ์ที่จำกัด และเราพิจารณากลยุทธ์แบบผสม เกมนั้นจะมีสมดุลแบบแนชในกลยุทธ์แบบผสมอย่างน้อยหนึ่งจุดเสมอ แต่หากเราไม่อนุญาตให้มีการผสมกลยุทธ์แล้ว (นั่นคือ มีเพียงเซตกลยุทธ์ที่เป็นเซตจำกัด) เกมนั้นอาจไม่มีสมดุลแบบแนชก็ได้ ในกรณีนี้ เรียกว่าเกมนั้นไม่มีกลยุทธ์แบบแท้
วิธีพิสูจน์ด้วยทฤษฎีบทจุดตรึงที่แนชใช้นั้น สามารถใช้พิสูจน์ทฤษฎีบทที่มีนัยทั่วไปกว่านั้นได้ กล่าวคือ ถ้าหากว่าเกมนั้นมีเซตกลยุทธ์เป็นเซตย่อยของปริภูมิแบบยุคลิดที่กระชับ คอนเวกซ์ และไม่เป็นเซตว่าง และฟังก์ชันอรรถประโยชน์ของผู้เล่นแต่ละคนเป็นฟังก์ชันต่อเนื่องในเซตโพรไฟล์กลยุทธ์ และกึ่งเว้าต่อกลยุทธ์ของตัวเอง เกมนั้นก็จะมีจุดสมดุลแบบแนชอย่างน้อยหนึ่งจุด เกมที่มีกลยุทธ์แบบผสมถือเป็นกรณีเฉพาะอันหนึ่งของเกมในนัยทั่วไปนี้
== อ้างอิง ==
ทฤษฎีเกม