/ 365วันแห่งโปรแกรม

[365 วันแห่งโปรแกรม #day69] สมดุลของแนช

วันที่หกสิบเก้าของ ‪#‎365วันแห่งโปรแกรม วันนี้ไม่ได้เกี่ยวกับโปรแกรมมิ่งสักเท่าไหร่ครับ แค่อยากเขียนล้วนๆ เลย 5555 วันนี้เราจะคุยกันเรื่อง สมดุลของแนช (Nash equilibrium)


Nash equilibrium

Nash equilibrium หรือ สมดุลของแนช เป็นทฤษฎีทางคณิตศาสตร์/เศรษฐศาสตร์ ที่ใช้หาจุดสมดุลของเกมเมื่อผู้เล่นทั้งหมดเป็นอิสระต่อกัน

โดยทั่วไปแล้วคำว่าเกมในทฤษฎีเกมจะหมายถึงสถานการณ์ที่มีการแข่งขันกันเพื่อเอาชนะ ดังนั้นแล้วโดยทั่วไปเกมจะต้องมีผู้แพ้และผู้ชนะ แต่ถ้าเกมอยู่ในสภาพที่เสถียร (stable) แล้วเกมนั้นจะไม่มีผู้แพ้ (หรือไม่มีผู้ชนะ) กล่าวคือทุกคนจะได้ประโยชน์หรือเสียประโยชน์เท่าๆ กัน ซึ่งการที่จะไปถึงจุดที่เสถียรนั้นก็มีอยู่ 2 ทาง ทางแรกคือการเล่นแบบร่วมมือ (co-operative) และอีกทางคือการเล่นแบบต่างคนต่างเอาตัวรอดไม่ร่วมมือกัน (Non-cooperative) ซึ่งในสมดุลของแนชจะเป็นแบบ Non-cooperative

Prisoners' dilemma

Prisoners' dilemma เป็นตัวอย่างที่ดีที่นิยมใช้ในการอธิบายสมดุลของแนช ซึ่งในสถานการณ์จำลองนี้จะมีผู้เล่น 2 คน ซึ่งกำลังจะถูกตัดสินให้จำคุก ผู้เล่นแต่ละคนมีสิทธิ์ที่จะปฏิเสธข้อกล่าวหา หรือยอมรับผิดก็ได้ และการตัดสินใจของผู้เล่นคนหนึ่งจะกระทบกับอีกคนหนึ่งด้วย

สมมติว่า Al และ Bill โดนจับคดียาเสพติด โดย Al และ Bill ไม่ได้มีความเกี่ยวข้องกันโดยส่วนตัว (ไม่ไว้ใจกัน) กำหนดให้ผลลัพธ์ของการตัดสินใจรับสารภาพเป็นดังนี้

  1. โดนคดียาเสพติดจะมีโทษติดคุก 2 ปี

  2. ถ้า Al สารภาพ ส่วน Bill ปฏิเสธ Al จะโดน 1 ปี ส่วน Bill โดน 10 ปี

  3. ถ้า Bill สารภาพ ส่วน Al ปฏิเสธ Bill จะโดน 1 ปี ส่วน Al โดน 10 ปี

  4. ถ้าสารภาพทั้งคู่จะมีโทษ 3 ปีเหมือนกัน

การหาสมดุลของแนชนั้นเราจะเริ่มจากการเขียน payoff matrix ดังนี้

payoff matrix

เริ่มพิจารณา

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

ในมุมมองของ Al

ถ้า Al ปฏิเสธ มีโอกาสโดนจำคุก 2 ปี หรือไม่ก็ 10 ปี ไปเลย แต่ถ้าสารภาพ อาจจะโดน 1 ปี หรือไม่ก็ 3 ปี ดังนั้นการสารภาพย่อมให้ผลลัพธ์ที่ดีกว่าสำหรับ Al

Al prefer

ในมุมมองของ Bill

Bill นั้นจะมองแบบเดียวกับ Al เลย มั่นใจไม่ได้เลยว่า Al จะตอบอะไร ดังนั้นทางเลือกที่ดีที่สุดย่อมเป็นการสารภาพ

Bill prefer

สมดุลอยู่ตรงไหน?

Nash equilibrium

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

ภาคทฤษฎี

สมดุลของแนชนั้นไม่ใช่สิ่งที่เลื่อนลอย แต่มันมีหลักการมารองรับว่าตรงไหนสมดุล ตรงไหนไม่สมดุล งั้นเรามาดูก่อนว่าแนชบอกไว้ว่าอะไร

Nash equilibrium - (game theory) a stable state of a system that involves several interacting participants in which no participant can gain by a change of strategy as long as all the other participants remain unchanged

แปลเป็นไทยน่าจะประมาณนี้

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

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

เราจะเริ่มจากช่องที่เราบอกว่าไม่ใช่จุดสมดุลของแนชกันก่อนครับ

payoff matrix with number

ช่องที่ 1 (2:2)

ในช่องที่ 1 คือสถานการณ์ที่ทั้งคู่ปฏิเสธ จุดนี้คือจุดที่ optimal ที่สุด

ในมุมของ Al ถ้า Al ลองเปลี่ยนกลยุทธจากปฏิเสธไปเป็นสารภาพ จะพบว่า Al ได้ลดโทษจาก 2 ปี เหลือเพียง 1 ปี ส่วน Bill ติด 10 ปี ซึ่งถือว่า Al ได้ประโยชน์

ในมุมของ Bill ถ้า Bill ลองเปลี่ยนกลยุทธจากปฏิเสธไปเป็นสารภาพ จะพบว่า Bill ได้ลดโทษจาก 2 ปี เหลือเพียง 1 ปี ส่วน Al ติด 10 ปี ซึ่งถือว่า Bill ได้ประโยชน์

someone change strategy from deny to confess other stay deny

จะเห็นว่าใครเปลี่ยนคนนั้นก็ได้ประโยชน์หากคนที่เหลือไม่เปลี่ยน ดังนั้นช่องที่ 1 ไม่ใช่สมดุลของแนช

ช่องที่ 2 (1:10)

ในมุมของ Al ถ้า Al ลองเปลี่ยนกลยุทธจากสารภาพไปเป็นปฏิเสธ จะพบว่า Al ติดคุกเพิ่มขึ้น จาก 1 ปีเป็น 2 ปี และ Bill ติดคุกเหลือ 2 ปีเช่นกัน

ในมุมของ Bill ถ้า Bill ลองเปลี่ยนกลยุทธจากปฏิเสธไปเป็นสารภาพ จะพบว่า Bill ติดคุกน้อยลงจาก 10 ปี เป็น 3 ปี และ Al โดนเพิ่มจาก 1 ปีเป็น 3 ปี

someone change strategy other constant

จะเห็นว่าในช่องนี้ถ้า Bill เปลี่ยนกลยุทธ Bill จะได้ประโยชน์ ดังนั้นช่องที่ 2 ไม่ใช่สมดุลของแนช

ช่องที่ 3 (10:1)

ในมุมของ Al ถ้า Al ลองเปลี่ยนกลยุทธจากปฏิเสธไปเป็นสารภาพ จะพบว่า Al ติดคุกน้อยลงจาก 10 ปี เป็น 3 ปี และ Bill โดนเพิ่มจาก 1 ปีเป็น 3 ปี

ในมุมของ Bill ถ้า Bill ลองเปลี่ยนกลยุทธจากสารภาพไปเป็นปฏิเสธ จะพบว่า Bill ติดคุกเพิ่มขึ้น จาก 1 ปีเป็น 2 ปี และ Al ติดคุกเหลือ 2 ปีเช่นกัน

someone change strategy other constant

จะเห็นว่าในช่องนี้ถ้า Al เปลี่ยนกลยุทธ Al จะได้ประโยชน์ ดังนั้นช่องที่ 3 ไม่ใช่สมดุลของแนช

ช่องที่ 4 (3:3)

ข้อนี้คือสารภาพคู่ เป็นข้อที่เราคิดกันว่าเป็นสมดุลของแนช

ในมุมของ Al ถ้า Al ลองเปลี่ยนกลยุทธจากสารภาพไปเป็นปฏิเสธ จะพบว่า Al ติดคุกเพิ่มขึ้นจาก 3 ปี เป็น 10 ปี ส่วน Bill เหลือแค่ 1 ปี

ในมุมของ Bill ถ้า Bill ลองเปลี่ยนกลยุทธจากสารภาพไปเป็นปฏิเสธ จะพบว่า Bill ติดคุกเพิ่มขึ้นจาก 3 ปี เป็น 10 ปี ส่วน Al เหลือแค่ 1 ปี

someone change strategy from confess to deny other stay confess

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

สรุป

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

ในอีกด้านหนึ่งเราต้องไม่ลืมว่า ไม่ใช่ทุกเกมที่มีจุดสมดุล และมีบางเกมที่มีจุดสมดุลหลายจุด ดังนั้นการจึงไม่ควรใช้แค่ทฤษฎีใดทฤษฎีหนึ่งในการหาสมดุลของเกม

John Forbes Nash, Jr.

John Forbes Nash, Jr เป็นนักคณิตศาสตร์ชาวอเมริกัน ที่มีส่วนร่วมในการพัฒนาทฤษฎี game theory, differential geometry และ partial differential equations ผลงานของเขาถูกนำไปใช้อย่างแพร่หลายทั้งในด้านเศรษฐศาสตร์ คอมพิวเตอร์ เกมทักษะ การเมือง และการทหาร แนชป่วยเป็นโรค paranoid schizophrenia (หวาดระแวง) ถูกจับเข้ารับการรักษาอยู่นาน แต่ไม่หายขาด สุดท้ายเขาสามารถหาวิธีใช้ชีวิตอยู่กับโรคนี้ได้ เขากลับมาเป็นอาจารย์ที่ Princeton สอนวิชาคณิตศาสตร์ และค้นคว้าเกี่ยวกับงานทางทฤษฎีคณิตศาสตร์จนถึงวาระสุดท้ายของชีวิต แนชและภรรยาเสียชีวิตด้วยอุบัติเหตุทางรถยนต์ เมื่อ 23 พฤษภาคม 2015

ตลอดชีวิตของแนชได้รับรางวัลมากมาย ไม่ว่าจะเป็น John von Neumann Theory Prize (1978), Nobel Memorial Prize in Economic Sciences (1994) และ Abel Prize (2015)

หากสนใจเพิ่มเติมเกี่ยวกับชีวิตของแนชสามารถดูได้จากภาพยนตร์เรื่อง A Beautiful Mind

บทความนี้ขออุทิศแด่ John Forbes Nash, Jr. ผู้ล่วงลับ

References

แทบทุกสิ่งทุกอย่างจาก KHAN ACADEMY

ข้อมูลของแนชจาก Wikipedia

#‎day69 #365วันแห่งโปรแกรม ‪#‎โครงการ365วันแห่ง‬...