13. นอยมันน์ และ แนช (ทฤษฎีเกม)

จอห์น ฟอน นอยมันน์
จากวิกิพีเดีย สารานุกรมเสรี
ไปที่: ป้ายบอกทาง, ค้นหา


จอห์น ฟอน นอยมันน์ ในช่วงปี ค.ศ. 1940
จอห์น ฟอน นอยมันน์ (John von Neumann, Neumann János, 28 ธ.ค. ค.ศ. 1903 - 8 ก.พ. ค.ศ. 1957) เป็นนักคณิตศาสตร์ชาวอเมริกันเชื้อสายฮังการี มีผลงานสำคัญในหลายสาขา ทั้ง ควอนตัมฟิสิกส์ ทฤษฎีเซต วิทยาการคอมพิวเตอร์ เศรษฐศาสตร์ และ จะว่าไปแล้วก็ทุกๆ สาขาในวิชาคณิตศาสตร์ เลยก็ว่าได้
เนื้อหา
[ซ่อน]
• 1 ประวัติ
• 2 ผลงาน
• 3 ชีวิตส่วนตัว
• 4 ดูเพิ่ม

[แก้] ประวัติ
เขาเป็นบุตรชายคนโต ในพี่น้อง 3 คน ชื่อเดิมของนอยมันน์ คือ János Lajos Margittai Neumann เกิดที่เมืองบูดาเปส บิดาคือ Neumann Miksa (Max Neumann) เป็นนักการธนาคาร และ มารดาคือ Kann Margit (Margaret Kann) นอยมันน์มีชื่อเล่น ว่า "Jancsi" เขาเติบโตมาในครอบครัวชาวยิวที่ไม่เคร่งครัด และได้แสดงถึงความจำที่เป็นเลิศ มาตั้งแต่ยังเป็นเด็ก โดยสามารถทำการหารเลข 8 หลักในใจได้ตอนอายุ 6 ปี. ในปี ค.ศ. 1911 ก็เข้าเรียนที่ Lutheran Gymnasium (ในประเทศเยอรมนี, gymnasium หมายถึง โรงเรียนมัธยมปลาย) พอปี ค.ศ. 1913 เนื่องจากคุณพ่อของเขาได้รับตำแหน่ง (ยศ) เขาจึงได้รับชื่อในภาษาเยอรมัน von จึงใช้ชื่อเต็มเป็น János von Neumann
[แก้] ผลงาน

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

เขาเรียนจบปริญญาเอกสาขาคณิตศาสตร์ จาก มหาวิทยาลัยบูดาเปส ประเทศฮังการี ตอนอายุ 23 ปี
ระหว่างปี ค.ศ. 1926 ถึง 1930 เขาทำงานเป็น "อาจารย์อิสระ" ("Privatdozent" เป็นตำแหน่งในระบบมหาวิทยาลัยยุโรป สำหรับผู้ที่ต้องการจะเป็นศาสตราจารย์มหาวิทยาลัย ตำแหน่งนี้ไม่มีเงินเดือนประจำ) โดยในขณะนั้นเขาเป็นอาจารย์อิสระที่อายุน้อยที่สุดมหาวิทยาลัยเบอร์ลิน ประเทศเยอรมนี
ในปี ค.ศ. 1930 นอยมันน์ได้รับเชิญให้ไปยังเมืองพรินซ์ตัน, มลรัฐนิวเจอร์ซี และได้เป็นหนึ่งในหกบุคคล (J. W. Alexander, อัลเบิร์ต ไอน์สไตน์, Marston Morse, Oswald Veblen, จอห์น ฟอน นอยมันน์ และ Hermann Weyl) ที่ถูกคัดเลือกเพื่อเป็นอาจารย์ประจำชุดแรกของ Institute for Advanced Study เขาเป็นศาสตราจารย์คณิตศาสตร์ที่นั่น ตั้งแต่เริ่มก่อตั้งสาขาวิชาในปี ค.ศ. 1933 จนกระทั่งวาระสุดท้ายของชีวิตเขา.
ในช่วงสงครามโลกครั้งที่สอง นอยมันน์ได้มีส่วนร่วมใน โครงการแมนฮัตตัน (Manhattan Project) ซึ่งเป็นโครงการสร้างระเบิดปรมาณู
ช่วง ค.ศ. 1936 จนถึง 1938 แอลัน ทัวริง ได้เป็นนักเรียนแลกเปลี่ยนไปที่สถาบัน และเรียนจบปริญญาเอก โดยมีนอยมันน์เป็นอาจารย์ที่ปรึกษา การไปเป็นนักเรียนแลกเปลี่ยนครั้งนี้ของทัวริง เกิดขึ้นหลักจากที่เขาได้ดีพิมพ์บทความวิชาการ "On Computable Numbers with an Application to the Entscheidungs-problem" ในปี ค.ศ. 1934 ได้ไม่นาน. งานตีพิมพ์นี้ เกี่ยวข้องกับ หลักการของ logical design และ universal machine. ถึงแม้จะเป็นที่แน่ชัดว่า นอยแมนรู้ถึงแนวความคิดของทัวริง แต่ก็ไม่เป็นที่แน่ชัดว่า เขาได้ใช้หลักการของทัวริง ในการออกแบบเครื่อง IAS ที่ถูกสร้างในเวลา 10 ปีต่อมา
นอยมันน์นั้น ได้รับการขนานนามว่าเป็น บิดาของทฤษฎีเกม (game theory). เขาได้ตีพิมพ์หนังสือ Theory of Games and Economic Behavior โดยร่วมเขียนกับ Oskar Morgenstern ในปี ค.ศ. 1944 เขาได้คิดหลักการ "MAD" (mutually assured destruction) อาจแปลไทยได้เป็น "รับรองได้ว่าเจ๊งไปด้วยกันทั้งคู่แน่" ซึ่งเป็นหลักการซึ่งใช้เป็นหลักสำคัญ ในการวางแผนกลยุทธ์ทางด้านอาวุธนิวเคลียร์ของอเมริกา ในช่วงสงครามเย็น
นอยมันน์เป็นคนคิด สถาปัตยกรรมแบบ ฟอน นอยมันน์ ซึ่งใช้กันในคอมพิวเตอร์ (แบบที่ไม่ได้ประมวลผลแบบขนาน) ส่วนใหญ่ พูดได้ว่า คอมพิวเตอร์เกือบทั้งหมดในโลกนี้ เป็นเครื่องจักรแบบ ฟอน นอยมันน์ เขาเป็นผู้ริเริ่มสาขา cellular automata และได้สร้างตัวอย่างชุดแรกของ self-replicating automata โดยใช้แค่กระดาษกราฟ กับ ดินสอธรรมดาๆ (ไม่มีคอมพิวเตอร์ช่วยเลย) คำว่า เครื่องจักรแบบ ฟอน นอยมันน์ ยังหมายความถึง เครื่องจักรที่สร้างตนเองซ้ำได้ (self-replicating machine)
นอยมันน์ได้พิสูจน์ว่า การใช้เครื่องจักรที่สร้างตนเองซ้ำได้ เป็นวิธีที่มีประสิทธิภาพที่สุด ในการทำเหมืองขนาดใหญ่มากๆ อย่างการทำเหมืองบนดวงจันทร์ หรือ แถบดาวเคราะห์น้อย เนื่องจากกลไกแบบนี้จะมีการเติบโตเป็นแบบเลขชี้กำลัง
[แก้] ชีวิตส่วนตัว
นอยมันน์นับเป็นบุคคลที่ฉลาดล้ำลึก และความจำที่เป็นเลิศเกือบจะเรียกได้ว่า จำได้ทุกอย่าง ในระดับรายละเอียดเลยก็ว่าได้ เขาเป็นคนชอบออกสังคมไม่เก็บตัว ชอบดื่มเหล้า เต้นรำ และ การเริงรมย์ เป็นคนสนุกสนาน และขบขัน เสียชีวิตที่กรุงวอชิงตัน ดี.ซี.
จาก การโปรแกรมเชิงเส้น ที่เขียนโดย George B. Dantzig ซึ่งเป็นผู้ที่คิดค้น simplex method ที่ใช้แก้ปัญหาการโปรแกรมเชิงเส้น เขาได้เขียนถึงนอยมันน์ จากประสบการณ์ที่ได้ไปพบและขอคำแนะนำจากนอยมันน์ และยังได้สะท้อนถึงบุคคลิกของนอยมันน์ และได้เล่าถึงตอนที่นอยมันน์ได้ช่วยเหลือ โดยการตอบคำถามของ Hotelling (ผู้คิดค้น Principal components analysis) ระหว่างการนำเสนอผลงานการโปรแกรมเชิงเส้นของเขา
ทฤษฎีเกม
จากวิกิพีเดีย สารานุกรมเสรี
ไปที่: ป้ายบอกทาง, ค้นหา


ทฤษฎีเกม เป็นสาขาของคณิตศาสตร์ประยุกต์ที่ศึกษาเกี่ยวกับสถานการณ์ขัดแย้งที่มีผู้เล่นหลายฝ่าย ที่แต่ละฝ่ายพยายามแสวงหาผลตอบแทนให้ได้มากที่สุด แม้ว่าทฤษฎีเกมมีรากฐานการศึกษาเกี่ยวข้องกับการละเล่นหลายชนิด เช่นหมากรุก ทิก-แทก-โท และโปเกอร์ อันเป็นที่มาของชื่อ[ต้องการแหล่งอ้างอิง] แต่แบบจำลองนี้ยังเกี่ยวข้องกับสถานการณ์ขัดแย้งในหลายสาขาเช่นสังคมวิทยา เศรษฐศาสตร์ รัฐศาสตร์ การทหาร รวมถึงชีววิทยา
ผู้เริ่มศึกษาทฤษฎีเกมในระยะแรกคือ จอห์น ฟอน นอยมันน์ และออสการ์ มอร์เกินสเติร์น โดยได้ตีพิมพ์ตำรา Theory of Games and Economic Behavior ใน พ.ศ. 2487 ต่อมา จอห์น แนชได้พัฒนาการศึกษาในด้านนี้และได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์จากการนำทฤษฎีเกมไปประยุกต์ใช้ในด้านเศรษฐศาสตร์
เนื้อหา
[ซ่อน]
• 1 ประวัติ
• 2 รูปแบบของเกม
o 2.1 เกมรูปแบบครอบคลุม
o 2.2 เกมรูปแบบปกติ
• 3 ชนิดของเกม
o 3.1 เกมร่วมมือ และเกมไม่ร่วมมือ
o 3.2 เกมสมมาตร และเกมไม่สมมาตร
o 3.3 เกมผลรวมศูนย์ และเกมผลรวมไม่เป็นศูนย์
• 4 ตัวอย่างเกมที่มีชื่อเสียง
o 4.1 เกมความลำบากใจของนักโทษ
o 4.2 เกมไก่ตื่น
o 4.3 เกมแห่งความร่วมมือ
• 5 การประยุกต์ใช้
o 5.1 รัฐศาสตร์
o 5.2 เศรษฐศาสตร์
o 5.3 ชีววิทยา
o 5.4 วิทยาการคอมพิวเตอร์
o 5.5 สังคมวิทยา
• 6 อ้างอิง
• 7 แหล่งข้อมูลอื่น

[แก้] ประวัติ


จอห์น แนช หนึ่งในผู้พัฒนาการศึกษาทฤษฎีเกม
ใน พ.ศ. 2256 เจมส์ เวลด์เกรฟ ได้ทำการวิเคราะห์หากลยุทธที่ดีที่สุดในการเล่นเกมไพ่ชนิดหนึ่งที่มีผู้เล่นสองคน เรียกว่า le Her โดยใช้หลักการคล้ายกับทฤษฎีเกม และ แอนโทนี ออกัสติน คอร์นอต์ ได้ตีพิมพ์ผลงานเรื่อง Researches into the Mathematical Principles of the Theory of Wealth ใน พ.ศ. 2381 ซึ่งเป็นกรณีทั่วไปของการศึกษาของเจมส์ แต่ทฤษฎีเกมได้มีการศึกษาเป็นสาขาเฉพาะครั้งแรกโดย จอห์น ฟอน นอยมันน์ โดยได้เริ่มตีพิมพ์ผลงานด้านนี้มาตั้งแต่ พ.ศ. 2473 และได้ตีพิมพ์ตำรา Theory of Games and Economic Behavior ที่เขียนร่วมกับ ออสการ์ มอร์เกินสเติร์น ใน พ.ศ. 2487 ที่มีเนื้อหาเกี่ยวกับวิธีการหา "กลยุทธเด่น" ซึ่งเป็นทางเลือกที่ดีที่สุดสำหรับเกมผลรวมศูนย์ที่มีผู้เล่นสองคน ตำรานี้นับว่าเป็นการวางรากฐานของทฤษฎีเกมทั้งทางด้านคณิตศาสตร์และเศรษฐศาสตร์อย่างมั่นคง จึงถือได้ว่า จอห์น ฟอน นอยมันน์ เป็นผู้ให้กำเนิดทฤษฎีเกม[ต้องการแหล่งอ้างอิง]
ใน พ.ศ. 2493 จอห์น แนชได้พัฒนาการศึกษาในด้านทฤษฎีเกมในด้านต่าง ๆ จำนวนมาก เช่น การศึกษาถึงตำแหน่งที่ดีที่สุดของเกมที่ทุกคนพอใจในตำแหน่งนี้ เรียกว่า "จุดสมดุลของแนช" นักเศรษฐศาสตร์ได้นำแนวคิดนี้ไปช่วยในการวิเคราะห์ในหลาย ๆ เรื่อง เช่น การประมูล การแข่งขันของผู้ผลิตสินค้า ทำให้จอห์น แนช ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์ ร่วมกับจอห์น ฮาร์ซานยิ และ ไรน์ฮาร์ด เซลเทน ในปี พ.ศ. 2537 ในฐานะที่เป็นผู้นำหลักทฤษฎีเกมไปประยุกต์ใช้ในด้านเศรษฐศาสตร์ และได้มีการสร้างภาพยนตร์เกี่ยวกับชีวประวัติของเขาเรื่อง A Beautiful Mind โดย ซิลเวีย นาซาร์ ใน พ.ศ. 2544
หลังจากนั้น ได้มีการศึกษาทฤษฎีเกมในวงกว้างมากขึ้น และได้มีการนำทฤษฎีเกมไปประยุกต์ใช้ในด้านสังคมวิทยา รัฐศาสตร์ และชีววิทยา
ปัจจุบัน ทฤษฎีเกมได้มีการพัฒนาขึ้นเรื่อย ๆ อย่างต่อเนื่อง ในปี พ.ศ. 2548 โทมัส เชลลิง และ โรเบิร์ต ออมันน์ ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์จากผลงานด้านทฤษฎีเกม โดยการสร้างแบบจำลองไดนามิกที่เกี่ยวข้องกับทฤษฎีเกมประยุกต์ และได้พัฒนาแนวคิดต่าง ๆ ให้ครอบคลุมมากขึ้น
[แก้] รูปแบบของเกม
เกมที่ทฤษฎีเกมศึกษาประกอบด้วยผู้เล่นจำนวนหนึ่ง และทางเลือกสำหรับผู้เล่นแต่ละคน ซึ่งแต่ละทางเลือกมีผลตอบแทนที่แตกต่างกัน
[แก้] เกมรูปแบบครอบคลุม


แผนภาพต้นไม้แสดงทางเลือกในการตัดสินใจ
เกมรูปแบบครอบคลุม เป็นเกมที่ผู้เล่นแต่ละคนตัดสินใจเลือกทางเลือกต่าง ๆ ตามลำดับ โดยผู้เล่นจะทราบถึงการตัดสินใจของผู้เล่นอีกฝ่ายในตาก่อนหน้า สามารถเขียนเกมประเภทนี้ได้ในรูปแผนภาพต้นไม้ โดยตั้งต้นที่จุดเริ่มแรก และจบที่จุดสิ้นสุดของเกม ซึ่งสามารถมีได้หลายจุด มีการใช้จุดยอดแทนสถานะที่มีทางเลือกในการตัดสินใจของผู้เล่น และใช้เส้นแทนทางเลือกของผู้เล่นในตาถัดไป
สำหรับเกมในภาพ มีผู้เล่นสองคน ผู้เล่น 1 ตัดสินใจเลือกก่อนระหว่าง ทางเลือก F และทางเลือก U จากนั้นผู้เล่น 2 ซึ่งทราบถึงการตัดสินใจของผู้เล่น 1 ตัดสินใจเลือกระหว่าง ทางเลือก A และทางเลือก R โดยมีผลตอบแทนที่ได้แสดงไว้ด้านล่าง เช่น ถ้าผู้เล่น 1 เลือก U และผู้เล่น 2 เลือก A ผลตอบแทนที่ได้คือ ผู้เล่น 1 ได้ 8 และผู้เล่น 2 ได้ 2
เกมหลายชนิด เช่น หมากรุก ทิก-แทก-โท ก็ถือว่าเป็นเกมรูปแบบครอบคลุม จึงสามารถหาวิธีที่ดีที่สุดในการเล่นเกมเหล่านี้ได้ โดยการใช้แผนภาพต้นไม้
[แก้] เกมรูปแบบปกติ
ผู้เล่น 2
เลือก ซ้าย ผู้เล่น 2
เลือก ขวา
ผู้เล่น 1
เลือก บน 4, 3 –1, –1
ผู้เล่น 1
เลือก ล่าง 0, 0 3, 4
ตารางแสดงเกมที่มีผู้เล่น 2 คน และมี 2 ทางเลือก
เกมรูปแบบปกติ เป็นเกมที่ผู้เล่นไม่ทราบถึงการตัดสินใจของผู้เล่นคนอื่น นิยมเขียนแสดงเกมในรูปแบบตาราง ซึ่งมักจะใช้ในกรณีที่มีผู้เล่น 2 คน โดยผู้เล่นคนหนึ่งจะแทนการตัดสินใจด้วยแถวต่าง ๆ และผู้เล่นอีกคนหนึ่งแทนการตัดสินใจด้วยคอลัมน์ต่าง ๆ
สำหรับเกมในภาพ ผู้เล่น 1 มีทางเลือก 2 ทาง คือ บน และ ล่าง ส่วนผู้เล่น 2 มีทางเลือก 2 ทาง คือ ซ้าย และ ขวา จุดตัดของแถวและคอลัมน์จะแสดงถึงผลตอบแทนที่ผู้เล่นทั้งสองได้รับ เช่น ถ้าผู้เล่น 1 เลือก บน และผู้เล่น 2 เลือก ซ้าย ผลตอบแทนที่ได้คือ ผู้เล่น 1 ได้ 4 และผู้เล่น 2 ได้ 3
[แก้] ชนิดของเกม
[แก้] เกมร่วมมือ และเกมไม่ร่วมมือ
เกมร่วมมือเป็นเกมที่ผู้เล่นแต่ละฝ่ายสามารถตกลงกันได้เพื่อให้ได้รับผลตอบแทนรวมที่ดีที่สุด โดยจะถือว่าผู้เล่นที่ร่วมมือกันจะเป็นผู้เล่นฝ่ายเดียวกันและจะปฏิบัติตามข้อตกลงที่ได้ตกลงกันไว้ ซึ่งแตกต่างจากเกมไม่ร่วมมือที่ผู้เล่นแต่ละฝ่ายไม่สามารถตกลงผลตอบแทนกันได้เลย จะต้องตัดสินใจโดยใช้ผลตอบแทนของตนเป็นหลักเท่านั้น
[แก้] เกมสมมาตร และเกมไม่สมมาตร
E F
E 1, 2 0, 0
F 0, 0 1, 2
เกมไม่สมมาตร
เกมสมมาตรเป็นเกมที่ผลตอบแทนที่ได้รับขึ้นกับการตัดสินใจของตนเองและคนอื่นเท่านั้น โดยไม่ขึ้นกับว่าใครจะเป็นผู้เล่นเกมนี้ จึงมีกลยุทธในการเล่นที่เหมือนกันสำหรับผู้เล่นทุกคน เกมที่มีผู้เล่น 2 คนและทางเลือก 2 ทางที่มีชื่อเสียงจำนวนมากจัดอยุ่ในประเภทนี้ เช่น เกมความลำบากใจของนักโทษ เกมไก่ตื่น และเกมความร่วมใจ
เกมไม่สมมาตรจะมีกลยุทธในการเล่นที่แตกต่างกันออกไปสำหรับผู้เล่นแต่ละคน เช่นเกมในภาพถือว่าเป็นเกมไม่สมมาตร ถึงแม้กลยุทธในการเล่นที่ดีที่สุดจะเป็นกลยุทธเดียวกันก็ตาม
[แก้] เกมผลรวมศูนย์ และเกมผลรวมไม่เป็นศูนย์
A B
A –1, 1 3, –3
B 0, 0 –2, 2
เกมผลรวมศูนย์
เกมผลรวมศูนย์เป็นกรณีเฉพาะของเกมผลรวมคงที่ ซึ่งเป็นเกมในลักษณะที่ผลรวมของผลตอบแทนที่ได้ของผู้เล่นจะเป็นค่าคงที่ เช่น การแบ่งปันผลกำไร หรือเกมที่มีผู้ชนะและผู้แพ้ เช่น หมากรุก หมากล้อม ก็ถือว่าเป็นเกมผลรวมศูนย์เช่นกัน ในการเขียนเกมในรูปแบบตารางที่มีผู้เล่นสองคนจึงสามารถละไว้โดยเขียนเพียงผลตอบแทนของผู้เล่นเพียงคนเดียวได้ และกลยุทธในการตัดสินใจให้ได้ผลตอบแทนมากที่สุดจะเป็นวิธีเดียวกับที่ทำให้ฝ่ายตรงข้ามได้ผลตอบแทนน้อยที่สุด
เกมส่วนมากที่นักทฤษฎีเกมศึกษามักจะเป็นเกมผลรวมไม่เป็นศูนย์ เนื่องจากในความเป็นจริง ผลลัพธ์ที่ได้ไม่จำเป็นต้องคงที่เสมอไป ขึ้นอยู่กับแนวทางการตัดสินใจของแต่ละฝ่าย ดังนั้น การได้รับผลตอบแทนมากที่สุดจึงไม่จำเป็นต้องทำให้ฝ่ายตรงข้ามได้ผลตอบแทนน้อยที่สุด
[แก้] ตัวอย่างเกมที่มีชื่อเสียง
[แก้] เกมความลำบากใจของนักโทษ
เกมความลำบากใจของนักโทษ (Prisoner's dilemma) เป็นเกมที่มีผู้เล่น 2 คนและทางเลือก 2 ทาง แนวคิดของเกมนี้ได้สร้างขึ้นโดย เมอร์ริล ฟลูด และ เมลวิน เดรชเชอร์ ใน พ.ศ. 2493 โดยมีลักษณะเป็นเกมที่ผู้เล่นทั้งสองฝ่ายพยายามเลือกทางเลือกที่ได้ผลตอบแทนมากที่สุด แต่กลับทำให้ผลตอบแทนรวมที่ได้ต่ำลง มีสถานการณ์ดังนี้
คนร้ายสองคนคือ A และ B ถูกตำรวจจับและถูกแยกไปสอบปากคำทีละคน ตำรวจไม่สามารถดำเนินคดีกับคนร้ายทั้งสองได้ทันทีเพราะไม่มีพยาน คนร้ายแต่ละคนมีทางเลือกสองทางคือ รับสารภาพ และไม่รับสารภาพ ถ้าคนร้ายคนหนึ่งรับสารภาพแต่อีกคนไม่รับ ตำรวจจะกันคนที่รับสารภาพไว้เป็นพยานและปล่อยตัวไป และจะส่งฟ้องคนที่ไม่รับสารภาพซึ่งมีโทษจำคุก 20 ปี ถ้าทั้งสองคนรับสารภาพ จะได้รับการลดโทษเหลือจำคุกคนละ 10 ปี แต่ถ้าทั้งสองคนไม่รับสารภาพ ตำรวจจะสามารถส่งฟ้องได้เพียงข้อหาเล็กน้อยเท่านั้นซึ่งมีโทษจำคุก 1 ปี
เกมนี้สามารถเขียนแสดงในรูปแบบตารางได้ดังนี้
รับสารภาพ ไม่รับสารภาพ
รับสารภาพ -10, -10 0, -20
ไม่รับสารภาพ -20, 0 -1, -1
จะเห็นว่ากลยุทธเด่นของผู้เล่นทั้งสองฝ่ายคือการรับสารภาพ เพราะไม่ว่าผู้เล่นอีกฝ่ายจะตัดสินใจอย่างไร ก็จะได้ผลตอบแทนที่ดีกว่าเสมอ แต่เมื่อทั้งสองฝ่ายเลือกทางเลือกนี้ กลับไม่ให้ผลตอบแทนที่ดีที่สุด ถึงแม้ผู้เล่นจะทราบว่าผลตอบแทนที่ดีที่สุดจะเกิดขึ้นเมื่อทั้งสองฝ่ายไม่รับสารภาพ แต่ทั้งคู่อาจไม่กล้าทำเพราะไม่ไว้ใจอีกฝ่ายว่าจะรับสารภาพหรือไม่ จึงทำให้ทั้งสองฝ่ายต้องได้รับผลตอบแทนที่ต่ำลง และจุด (-10, -10) ก็เป็นจุดสมดุลของแนชในเกมนี้ เพราะผู้เล่นทั้งสองฝ่ายไม่สามารถเปลี่ยนไปเลือกทางเลือกอื่นที่ได้ผลตอบแทนดีกว่านี้
[แก้] เกมไก่ตื่น
เกมไก่ตื่น (Chicken) เป็นเกมที่มีผู้เล่น 2 คนและทางเลือก 2 ทาง มีสถานการณ์ดังนี้
ผู้เล่นสองคนขับรถด้วยความเร็วสูงเข้าหากัน ฝ่ายที่หักหลบรถก่อนจะเป็นผู้แพ้ แต่ถ้าผู้เล่นทั้งสองฝ่ายไม่หักหลบรถ รถจะชนกันและจะทำให้ผู้เล่นทั้งสองฝ่ายเกิดความเสียหายอย่างมาก
เกมนี้สามารถเขียนแสดงในรูปแบบตารางได้ดังนี้
หลบ ไม่หลบ
หลบ 0, 0 -1, +1
ไม่หลบ +1, -1 -10, -10
จะเห็นว่าเกมในรูปแบบนี้ไม่มีกลยุทธเด่น และมีจุดสมดุลของแนชสองจุดคือ (-1, +1) และ (+1, -1) แต่วิธีทางจิตวิทยาสำหรับผู้เล่นเกมนี้คือ พยายามส่งสัญญาณให้ผู้เล่นฝ่านตรงข้ามเห็นว่า ตนจะไม่หักหลบอย่างแน่นอน ซึ่งจะทำให้ผู้เล่นฝ่ายตรงข้ามต้องยอมหักหลบไปเอง มิฉะนั้นจะเสียผลตอบแทนอย่างมาก
[แก้] เกมแห่งความร่วมมือ
เกมแห่งความร่วมมือ (Stag hunt) เป็นเกมที่มีผู้เล่น 2 คนและทางเลือก 2 ทาง ซึ่งเป็นทางเลือกระหว่างทางที่ปลอดภัยกับการให้ความร่วมมือกับอีกฝ่าย มีสถานการณ์ดังนี้
ผู้เล่นสองคนต้องการเลือกล่าสัตว์ชนิดหนึ่งระหว่างกวางกับกระต่าย ซึ่งกวางมีราคาดีกว่ากระต่ายมาก แต่ก็ล่ายากกว่าเช่นกัน จำเป็นต้องใช้สองคนร่วมมือกันจึงจะล่าได้ ในขณะที่กระต่ายมีราคาต่ำแต่ล่าได้ง่าย สามารถล่าได้โดยใช้เพียงคนเดียว
เกมนี้สามารถเขียนแสดงในรูปแบบตารางได้ดังนี้
ล่ากวาง ล่ากระต่าย
ล่ากวาง +10, +10 0, +3
ล่ากระต่าย +3, 0 +3, +3
จะเห็นว่าเกมในรูปแบบนี้ไม่มีกลยุทธเด่น และมีจุดสมดุลของแนชสองจุดคือ (+10, +10) และ (+3, +3) ซึ่งการที่ผู้เล่นทั้งสองจะได้ผลตอบแทนสูงสุดนั้น จะต้องอาศัยความร่วมมือร่วมใจกัน คือเลือกล่ากวางทั้งคู่ ซึ่งผู้เล่นจะต้องมีความไว้วางใจผู้เล่นอีกฝ่ายด้วย
[แก้] การประยุกต์ใช้
[แก้] รัฐศาสตร์
มีการนำทฤษฎีเกมมาประยุกต์ใช้ในด้านรัฐศาสตร์ เช่น การหาเสียงเลือกตั้ง ในปี พ.ศ. 2500 แอนโทนี ดาวน์ส ได้ตีพิมพ์ผลงานเรื่อง An Economic Theory of Democracy ซึ่งมีเนื้อหาเกี่ยวกับการเลือกตำแหน่งในการหาเสียงเลือกตั้งให้ได้ผลดีที่สุด
[แก้] เศรษฐศาสตร์
ในทางเศรษฐศาสตร์ ได้มีการนำทฤษฎีเกมมาช่วยในการตัดสินใจในหลาย ๆ ด้านมาเป็นเวลานานแล้ว เช่น การต่อรองผลประโยชน์ การประมูล การแข่งขันของผู้ผลิต การรวมกลุ่มทางเศรษฐกิจ โดยมีแนวคิดสำคัญที่ใช้คือเรื่องจุดสมดุลของแนช อย่างไรก็ตาม ในเกมการแข่งขันทางธุรกิจ อาจมีการปรับเปลี่ยนกลยุทธได้ตลอดเวลาเพื่อให้ได้รับผลตอบแทนที่สูงขึ้น และผลลัพธ์ที่ได้ก็จะเข้าสู่จุดสมดุลของแนช ซึ่งเป็นจุดที่ทุกฝ่ายไม่สามรถเปลี่ยนกลยุทธเพื่อให้ได้ผลตอบแทนสูงกว่านี้อีกแล้ว
[แก้] ชีววิทยา
มีการใช้ทฤษฎีเกมเพื่ออธิบายถึงปรากฏการณ์ต่าง ๆ ทางชีววิทยา เช่น ในปี พ.ศ. 2473 โรนัลด์ ฟิชเชอร์ ได้ใช้ทฤษฎีเกมในการอธิบายถึงอัตราส่วนของสัตว์เพศผู้ต่อเพศเมียที่เป็น 1:1 เนื่องจากเป็นอัตราส่วนที่สามารถสืบพันธุ์ได้จำนวนมากที่สุด นอกจากนี้ นักชีววิทยายังใช้ทฤษฎีเกมเพื่อช่วยในการศึกษาพฤติกรรมต่าง ๆ ของสัตว์ เช่น การใช้เกมไก่ตื่นในการอธิบายถึงการต่อสู้ของสัตว์
[แก้] วิทยาการคอมพิวเตอร์
มีการพัฒนาในด้านวิทยาการคอมพิวเตอร์และการเขียนโปรแกรมเพื่อหาอัลกอริทึมที่ดีที่สุดในการเล่นเกมในสถานการณ์หนึ่งเป็นระยะเวลานาน
[แก้] สังคมวิทยา
ได้มีการนำทฤษฎีเกมมาประยุกต์ใช้ในด้านสังคมวิทยา เช่น วิลลาร์ด แวน ออร์มาน ควินท์ และ เดวิด ลูอิส ได้พัฒนาการศึกษาด้านประเพณีนิยม และมีการวิเคราะห์เกี่ยวกับเกมต่าง ๆ ที่ต้องเลือกระหว่างศีลธรรมกับผลประโยชน์ของตนเอง เช่น เกมความลำบากใจของนักโทษ
Introduction to Game Theory/Prisoner's Dilema
From Wikibooks, the open-content textbooks collection
< Introduction to Game Theory
Jump to: navigation, search
Let's start by jumping right in and looking at a game. The game commonly referred to as The Prisoner's Dilemma is a classic example used to demonstrate game theory. It is usually explained through the use of this story, although the actual game called The Prisoner's Dilemma - often just called PD for short, is not limited to this situation. The underlying dynamics of it can be used to describe all sorts of phenomena.
[edit] The Story
Two men, Andy and Bob, were arrested after an armed robbery. The police had enough evidence to convict the two for the theft of the get-away car, but not enough to convict them for the actual armed robbery. However, if the police could get a confession from either of the two men they could conceivably convict them both for the armed robbery.
The police locked the two men in two separate rooms and gave them each the same offer:
If Andy confessed and Bob stayed silent, then Andy would go scot-free and Bob would be charged for the robbery and get 10 years in jail. Of course, this worked the other way around as well. If Bob confessed and Andy stayed silent, Andy would receive the 10 years.
If Andy confessed and Bob confessed as well, then they would both receive 7 years in jail.
If both Andy and Bob stayed silent, then they would both receive 2 years in prison for the get-away car robbery.
The two prisoners are left to make their decision without any way to contact each other. The question is: what did each person choose?
[edit] Solution
The solution that occurs every time this game is played (assuming each acts in his own best interests) is that both Andy and Bob will choose to confess, resulting in a sentence of 7 years each. This answer seems to be counter-intuitive, doesn't it? Why would both players choose to confess, an option that is clearly inferior to both of them staying silent and getting 2 years each? Not only this, but in terms of total years in prison, this is the worst possible outcome!
[edit] Explanation
The reason that both players choose to confess is easy to explain. Let's talk about Person A (and whatever holds for Andy, will hold for Bob as well because they are both in identical situations).
The following is the explanation assuming that Andy & Bob cannot communicate their choices to each other directly or indirectly.
Andy has the following Matrix:
If he confesses:
Minimum Jail Term: 0 Years (If Bob remains silent)
Maximum Jail Term: 7 Years (If Bob confesses)
If he remains silent:
Minimum Jail Term: 2 Years (If Bob remains silent)
Maximum Jail Term: 10 Years (If Bob confesses)



Table Format
Bob remains silent Bob Confesses
Andy Confesses 0 7
Andy Remains Silent 2 10
The expected payoff for the game (the average amount of benefit that a strategy will provide) is better — in this case, 3.5 years expected jail time for confessing versus 6 years for silence — if Andy confesses. Therefore, from a rational perspective, Andy should choose to confess rather than remain silent.
Also, it doesn't matter what Bob does - Andy is always better off confessing. If Bob confesses, Andy can get either 7 years for confessing or 10 for silence, and if Bob is silent, Andy can get either 0 years for confessing or 2 for silence. Unfortunately for Person Andy, this also holds true for Person Bob - who is always better off confessing. This means that if both agents do what is in their best interests, they will be 7 years together in prison! This demonstrates that in many games the "best" solution - the one where the total utility of the outcome is highest - is not the one which will ultimately occur.
Retrieved from "http://en.wikibooks.org/wiki/Introduction_to_Game_Theory/Prisoner%27s_Dilema"
Zero-sum
From Wikipedia, the free encyclopedia
Jump to: navigation, search
For the X-Files episode, see Zero Sum. For the Japanese manga magazine, see Monthly Comic Zero Sum.
In game theory and economic theory, zero-sum describes a situation in which a participant's gain or loss is exactly balanced by the losses or gains of the other participant(s). If the total gains of the participants are added up, and the total losses are subtracted, they will sum to zero. Zero-sum can be thought of more generally as constant sum where the benefits and losses to all players sum to the same value of money and pride and dignity. Cutting a cake is zero- or constant-sum because taking a larger piece reduces the amount of cake available for others. In contrast, non-zero-sum describes a situation in which the interacting parties' aggregate gains and losses is either less than or more than zero. Zero sum games are also called strictly competitive.
Contents
[hide]
• 1 Definition
• 2 Solution
o 2.1 Example
o 2.2 Solving
• 3 Non-zero-sum
o 3.1 Economics
o 3.2 Psychology
o 3.3 Complexity
• 4 Extensions
• 5 References
• 6 External links

[edit] Definition
The zero-sum property (if one gains, another loses) means that any result of a zero-sum situation is Pareto optimal (generally, any game where all strategies are Pareto optimal is called a conflict game) [1]
Situations where participants can all gain or suffer together, are referred to as non-zero-sum. Thus, a country with an excess of bananas trading with another country for their excess of apples, where both benefit from the transaction, is in a non-zero-sum situation. Other non-zero-sum games are games in which the sum of gains and losses by the players are sometimes more or less than what they began with.
The concept was first developed in game theory and consequently zero-sum situations are often called zero-sum games though this does not imply that the concept, or game theory itself, applies only to what are commonly referred to as games.
[edit] Solution
For 2-player finite zero-sum games, the different game theoretic Solution concepts of Nash equilibrium, minimax, and maximin all give the same solution. In the solution, players play a mixed strategy.
[edit] Example
A B C
1 30, -30 -10, 10 20, -20
2 10, -10 20, -20 -20, 20
A zero sum game
A game's payoff matrix is a convenient representation. Consider for example the two-player zero-sum game pictured at right.
The order of play proceeds as follows: The first player (red) chooses in secret one of the two actions 1 or 2; the second player (blue), unaware of the first player's choice, chooses in secret one of the three actions A, B or C. Then, the choices are revealed and each player's points total is affected according to the payoff for those choices.
Example: Red chooses action 2 and Blue chooses action B. When the payoff is allocated, Red gains 20 points and Blue loses 20 points.
Now, in this example game both players know the payoff matrix and attempt to maximize the number of their points. What should they do?
Red could reason as follows: "With action 2, I could lose up to 20 points and can win only 20, while with action 1 I can lose only 10 but can win up to 30, so action 1 looks a lot better." With similar reasoning, Blue would choose action C. If both players take these actions, Red will win 20 points. But what happens if Blue anticipates Red's reasoning and choice of action 1, and deviously goes for action B, so as to win 10 points? Or if Red in turn anticipates this devious trick and goes for action 2, so as to win 20 points after all?
John von Neumann had the fundamental and surprising insight that probability provides a way out of this conundrum. Instead of deciding on a definite action to take, the two players assign probabilities to their respective actions, and then use a random device which, according to these probabilities, chooses an action for them. Each player computes the probabilities so as to minimise the maximum expected point-loss independent of the opponent's strategy. This leads to a linear programming problem with the optimal strategies for each player. This minimax method can compute provably optimal strategies for all two-player zero-sum games.
For the example given above, it turns out that Red should choose action 1 with probability 4/7 and action 2 with probability 3/7, while Blue should assign the probabilities 0, 4/7 and 3/7 to the three actions A, B and C. Red will then win 20/7 points on average per game.
[edit] Solving
The Nash equilibrium for a two-player, zero-sum game can be found by solving a linear programming problem. Suppose a zero-sum game has a payoff matrix M where element Mi,j is the payoff obtained when the minimizing player chooses pure strategy i and the maximizing player chooses pure strategy j (i.e. the player trying to minimize the payoff chooses the row and the player trying to maximize the payoff chooses the column). Assume every element of M is positive. The game will have at least one Nash equilibrium. The Nash equilibrium can be found by solving the following linear program to find a vector u:
Minimize:
∑ ui
i
Subject to the constraints:
u ≥ 0
Mu ≥ 1
The first constraint says each element of the u vector must be nonnegative, and the second constraint says each element of the Mu vector must be at least 1. For the resulting u vector, the inverse of the sum of its elements is the value of the game. Multiplying u by that value gives a probability vector, giving the probability that the maximizing player will choose each of the possible pure strategies.
If the game matrix does not have all positive elements, simply add a constant to every element that is large enough to make them all positive. That will increase the value of the game by that constant, and will have no effect on the equilibrium mixed strategies for the equilibrium.
The equilibrium mixed strategy for the minimizing player can be found by solving the dual of the given linear program. Or, it can be found by using the above procedure to solve a modified payoff matrix which is the transpose and negation of M (adding a constant so it's positive), then solving the resulting game.
If all the solutions to the linear program are found, they will constitute all the Nash equilibria for the game. Conversely, any linear program can be converted into a two-player, zero-sum game by using a change of variables that puts it in the form of the above equations. So such games are equivalent to linear programs, in general.
[edit] Non-zero-sum
[edit] Economics
Many economic situations are not zero-sum, since valuable goods and services can be created, destroyed, or badly allocated, and any of these will create a net gain or loss. Assuming the counterparties are acting rationally, any commercial exchange is a non-zero-sum activity, because each party must consider the goods s/he is receiving as being at least fractionally more valuable to him/her than the goods s/he is delivering. Economic exchanges must benefit both parties enough above the zero-sum such that each party can overcome his or her transaction costs.
See also:
• Absolute advantage
• Comparative advantage
• Free trade
[edit] Psychology
The most common or simple example from the subfield of Social Psychology is the concept of "Social Traps." In some cases we can enhance our collective well-being by pursuing our personal interests — or parties can pursue mutually destructive behavior as they choose their own ends.
[edit] Complexity
It has been theorized by Robert Wright in his book Nonzero: The Logic of Human Destiny, that society becomes increasingly non-zero-sum as it becomes more complex, specialized, and interdependent. As former US President Bill Clinton states:
The more complex societies get and the more complex the networks of interdependence within and beyond community and national borders get, the more people are forced in their own interests to find non-zero-sum solutions. That is, win–win solutions instead of win–lose solutions.... Because we find as our interdependence increases that, on the whole, we do better when other people do better as well — so we have to find ways that we can all win, we have to accommodate each other.... Bill Clinton, Wired interview, December 2000 .[1]
[edit] Extensions
In 1944 John von Neumann and Oskar Morgenstern proved that any zero-sum game involving n players is in fact a generalized form of a zero-sum game for two players, and that any non-zero-sum game for n players can be reduced to a zero-sum game for n + 1 players; the (n + 1) player representing the global profit or loss.[citation needed]

Minimax
From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about the decision theory concept. For other uses, see Minimax (disambiguation).

To comply with Wikipedia's quality standards, this article is in need of reorganization.
There is good information here, but it is poorly organized. Please discuss this issue on the talk page and help improve this article.

Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the maximum possible loss. Alternatively, it can be thought of as maximizing the minimum gain (maximin). It started from two player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves. It has also been extended to more complex games and to general decision making in the presence of uncertainty.
Contents
[hide]
• 1 Game theory
o 1.1 Minimax theorem
o 1.2 Example
o 1.3 Maximin
• 2 Combinatorial game theory
o 2.1 Minimax algorithm with alternate moves
o 2.2 Pseudocode
o 2.3 Example
• 3 Minimax for individual decisions
o 3.1 Minimax in the face of uncertainty
o 3.2 Minimax criterion in statistical decision theory
• 4 Maximin in philosophy
• 5 See also
• 6 Notes
• 7 External links

[edit] Game theory
In the theory of simultaneous games, a minimax strategy is a mixed strategy which is part of the solution to a zero-sum game. In zero-sum games, the minimax solution is the same as the Nash equilibrium.
[edit] Minimax theorem
The minimax theorem states:
For every two-person, zero-sum game with finite strategies, there exists a value V and a mixed strategy for each player, such that (a) Given player 2's strategy, the best payoff possible for player 1 is V, and (b) Given player 1's strategy, the best payoff possible for player 2 is -V.
Equivalently, Player 1's strategy guarantees him a payoff of V regardless of Player 2's strategy, and similarly Player 2 can guarantee himself a payoff of -V. The name minimax arises because each player minimizes the maximum payoff possible for the other--since the game is zero-sum, he also maximizes his own minimum payoff.
This theorem was established by John von Neumann[1], who is quoted as saying "As far as I can see, there could be no theory of games … without that theorem … I thought there was nothing worth publishing until the Minimax Theorem was proved".[2]
See Sion's minimax theorem and Parthasarathy's theorem for generalizations; see also example of a game without a value.
[edit] Example
B chooses B1 B chooses B2 B chooses B3
A chooses A1 +3 -2 +2
A chooses A2 -1 0 +4
A chooses A3 -4 -3 +1
The following example of a zero-sum game, where A and B make simultaneous moves, illustrates minimax solutions. Suppose each player has three choices and consider the payoff matrix for A displayed at right. Assume the payoff matrix for B is the same matrix with the signs reversed (i.e. if the choices are A1 and B1 then B pays 3 to A). Then, the minimax choice for A is A2 since the worst possible result is then having to pay 1, while the simple minimax choice for B is B2 since the worst possible result is then no payment. However, this solution is not stable, since if B believes A will choose A2 then B will choose B1 to gain 1; then if A believes B will choose B1 then A will choose A1 to gain 3; and then B will choose B2; and eventually both players will realize the difficulty of making a choice. So a more stable strategy is needed.
Some choices are dominated by others and can be eliminated: A will not choose A3 since either A1 or A2 will produce a better result, no matter what B chooses; B will not choose B3 since B2 will produce a better result, no matter what A chooses.
A can avoid having to make an expected payment of more than 1/3 by choosing A1 with probability 1/6 and A2 with probability 5/6, no matter what B chooses. B can ensure an expected gain of at least 1/3 by using a randomized strategy of choosing B1 with probability 1/3 and B2 with probability 2/3, no matter what A chooses. These mixed minimax strategies are now stable and cannot be improved.
[edit] Maximin
Frequently, in game theory, maximin is distinct from minimax. Minimax is used in zero-sum games to denote minimizing the opponent's maximum payoff. In a zero-sum game, this is identical to minimizing one's own maximum loss, and to maximizing one's own minimum gain.
"Maximin" is a term commonly used for non-zero-sum games to describe the strategy which maximizes one's own minimum payoff. In non-zero-sum games, this is not generally the same as minimizing the opponent's maximum gain, or to the Nash equilibrium strategy.
[edit] Combinatorial game theory
In combinatorial game theory, there is a minimax algorithm for game solutions.
A simple version of the minimax algorithm, stated below, deals with games such as tic-tac-toe, where each player can win, lose, or draw. If player A can win in one move, his best move is that winning move. If player B knows that one move will lead to the situation where player A can win in one move, while another move will lead to the situation where player A can, at best, draw, then player B's best move is the one leading to a draw. Late in the game, it's easy to see what the "best" move is. The Minimax algorithm helps find the best move, by working backwards from the end of the game. At each step it assumes that player A is trying to maximize the chances of A winning, while on the next turn player B is trying to minimize the chances of A winning (i.e., to maximize B's own chances of winning).
[edit] Minimax algorithm with alternate moves
A minimax algorithm[3] is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. A value is associated with each position or state of the game. This value is computed by means of a position evaluation function and it indicates how good it would be for a player to reach that position. The player then makes the move that maximizes the minimum value of the position resulting from the opponent's possible following moves. If it is A's turn to move, A gives a value to each of his legal moves.
A possible allocation method consists in assigning a certain win for A as +1 and for B as −1. This leads to combinatorial game theory as developed by John Horton Conway. An alternative is using a rule that if the result of a move is an immediate win for A it is assigned positive infinity and, if it is an immediate win for B, negative infinity. The value to A of any other move is the minimum of the values resulting from each of B's possible replies. For this reason, A is called the maximizing player and B is called the minimizing player, hence the name minimax algorithm. The above algorithm will assign a value of positive or negative infinity to any position since the value of every position will be the value of some final winning or losing position. Often this is generally only possible at the very end of complicated games such as chess or go, since it is not computationally feasible to look ahead as far as the completion of the game, except towards the end, and instead positions are given finite values as estimates of the degree of belief that they will lead to a win for one player or another.
This can be extended if we can supply a heuristic evaluation function which gives values to non-final game states without considering all possible following complete sequences. We can then limit the minimax algorithm to look only at a certain number of moves ahead. This number is called the "look-ahead", measured in "plies". For example, the chess computer Deep Blue (that beat Garry Kasparov) looked ahead 12 plies, then applied a heuristic evaluation function.
The algorithm can be thought of as exploring the nodes of a game tree. The effective branching factor of the tree is the average number of children of each node (i.e., the average number of legal moves in a position). The number of nodes to be explored usually increases exponentially with the number of plies (it is less than exponential if evaluating forced moves or repeated positions). The number of nodes to be explored for the analysis of a game is therefore approximately the branching factor raised to the power of the number of plies. It is therefore impractical to completely analyze games such as chess using the minimax algorithm.
The performance of the naïve minimax algorithm may be improved dramatically, without affecting the result, by the use of alpha-beta pruning. Other heuristic pruning methods can also be used, but not all of them are guaranteed to give the same result as the un-pruned search.
[edit] Pseudocode
Pseudocode for the minimax algorithm (using an evaluation heuristic to terminate at a given depth) is given below.
The code is based on the observation that max(a,b) = − min( − a, − b). This avoids the need for the algorithm to treat the two players separately.
function minimax(node, depth)
if node is a terminal node or depth = 0
return the heuristic value of node
else
let α := -∞
foreach child of node { evaluation is identical for both players }
let α := max(α, -minimax(child, depth-1))
return α
[edit] Example

Suppose the game being played only has a maximum of two possible moves per player each turn. The algorithm generates the tree on the right, where the circles represent the moves of the player running the algorithm (maximizing player), and squares represent the moves of the opponent (minimizing player). Because of the limitation of computation resources, as explained above, the tree is limited to a look-ahead of 4 moves.
The algorithm evaluates each leaf node using a heuristic evaluation function, obtaining the values shown. The moves where the maximizing player wins are assigned with positive infinity, while the moves that lead to a win of the minimizing player are assigned with negative infinity. At level 3, the algorithm will choose, for each node, the smallest of the child node values, and assign it to that same node (e.g the node on the left will choose the minimum between "10" and "+∞", therefore assigning the value "10" to himself). The next step, in level 2, consists of choosing for each node the largest of the child node values. Once again, the values are assigned to each parent node. The algorithm continues evaluating the maximum and minimum values of the child nodes alternatively until it reaches the root node, where it chooses the move with the largest value (represented in the figure with a blue arrow). This is the move that the player should make in order to minimize the maximum possible loss.
[edit] Minimax for individual decisions
[edit] Minimax in the face of uncertainty
Minimax theory has been extended to decisions where there is no other player, but where the consequences of decisions depend on unknown facts. For example, deciding to prospect for minerals entails a cost which will be wasted if the minerals are not present, but will bring major rewards if they are. One approach is to treat this as a game against nature, and using a similar mindset as Murphy's law, take an approach which minimizes the maximum expected loss, using the same techniques as in the two-person zero-sum games.
In addition, expectiminimax trees have been developed, for two-player games in which chance (for example, dice) is a factor.
[edit] Minimax criterion in statistical decision theory
Main article: Minimax estimator
In classical statistical decision theory, we have an estimator δ that is used to estimate a parameter . We also assume a risk function R(θ,δ), usually specified as the integral of a loss function. In this framework, is called minimax if it satisfies
.
An alternative criterion in the decision theoretic framework is the Bayes estimator in the presence of a prior distribution Π. An estimator is Bayes if it minimizes the average risk

[edit] Maximin in philosophy
In philosophy, the term "maximin" is often used to refer to what John Rawls called The Difference Principle. In his book A Theory of Justice, Rawls defined this principle as the rule which states that social and economic inequalities should be arranged so that "they are to be of the greatest benefit to the least-advantaged members of society". In other words, an unequal distribution can be just when it maximizes the benefit to those who have the most minuscule allocation of welfare conferring resources (which he refers to as "primary goods").[original research?]
Nash equilibrium
From Wikipedia, the free encyclopedia
Jump to: navigation, search
Nash Equilibrium
A solution concept in game theory

Relationships
Subset of: Rationalizability, Epsilon-equilibrium, Correlated equilibrium

Superset of: Evolutionarily stable strategy, Subgame perfect equilibrium, Perfect Bayesian equilibrium, Trembling hand perfect equilibrium

Significance
Proposed by: John Forbes Nash

Used for: All non-cooperative games

Example: Rock paper scissors

This box: view • talk • edit

In game theory, Nash equilibrium (named after John Forbes Nash, who proposed it) is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his or her own strategy (i.e., by changing unilaterally). If each player has chosen a strategy and no player can benefit by changing his or her strategy while the other players keep theirs unchanged, then the current set of strategy choices and the corresponding payoffs constitute a Nash equilibrium. In other words, to be a Nash equilibrium, each player must answer negatively to the question: "Knowing the strategies of the other players, and treating the strategies of the other players as set in stone, can I benefit by changing my strategy?"
Stated simply, Amy and Bill are in Nash equilibrium if Amy is making the best decision she can, taking into account Bill's decision, and Bill is making the best decision he can, taking into account Amy's decision. Likewise, many players are in Nash equilibrium if each one is making the best decision that they can, taking into account the decisions of the others. However, Nash equilibrium does not necessarily mean the best cumulative payoff for all the players involved; in many cases all the players might improve their payoffs if they could somehow agree on strategies different from the Nash equilibrium (e.g. competing businessmen forming a cartel in order to increase their profits).
Contents
[hide]
• 1 History
• 2 Definitions
o 2.1 Informal definition
o 2.2 Formal definition
• 3 Examples
o 3.1 Competition game
o 3.2 Coordination game
o 3.3 Prisoner's dilemma
o 3.4 Nash equilibria in a payoff matrix
• 4 Stability
• 5 Occurrence
o 5.1 Where the conditions are not met
o 5.2 Where the conditions are met
• 6 NE and non-credible threats
• 7 Proof of existence
o 7.1 Alternate proof using the Brouwer fixed point theorem
• 8 Computing Nash equilibria
o 8.1 Examples
• 9 See also
• 10 References
o 10.1 Game Theory textbooks
o 10.2 Original Papers
o 10.3 Other References
• 11 Notes
• 12 External links

[edit] History
The concept of the Nash equilibrium (NE) in pure strategies was first developed by Antoine Augustin Cournot in his theory of oligopoly (1838). Firms choose a quantity of output to maximize their own profit. However, the best output for one firm depends on the outputs of others. A Cournot equilibrium occurs when each firm's output maximizes its profits given the output of the other firms, which is a pure-strategy NE. However, the modern game-theoretic concept of NE is defined in terms of mixed-strategies, where players choose a probability distribution over possible actions. The concept of the mixed strategy NE was introduced by John von Neumann and Oskar Morgenstern in their 1944 book The Theory of Games and Economic Behavior. However, their analysis was restricted to the very special case of zero-sum games. They showed that a mixed-strategy NE will exist for any zero-sum game with a finite set of actions. The contribution of John Forbes Nash in his 1951 article Non-Cooperative Games was to define a mixed strategy NE for any game with a finite set of actions and prove that at least one (mixed strategy) NE must exist.
[edit] Definitions
[edit] Informal definition
Informally, a set of strategies is a Nash equilibrium if no player can do better by unilaterally changing his or her strategy. As a heuristic, one can imagine that each player is told the strategies of the other players. If any player would want to do something different after being informed about the others' strategies, then that set of strategies is not a Nash equilibrium. If, however, the player does not want to switch (or is indifferent between switching and not) then the set of strategies is a Nash equilibrium.
Each strategy in a Nash equilibrium is a best response to all other strategies in that equilibrium.[1]
The Nash equilibrium may sometimes appear non-rational in a third-person perspective. This is because it may happen that a Nash equilibrium is not pareto optimal.
The Nash-equilibrium may also have non-rational consequences in sequential games because players may "threat"-en each other with non-rational moves. For such games the Subgame perfect Nash equilibrium may be more meaningful as a tool of analysis.
[edit] Formal definition
Let (S, f) be a game, where Si is the strategy set for player i, S=S1 X S2 ... X Sn is the set of strategy profiles and f=(f1(x), ..., fn(x)) is the payoff function. Let x-i be a strategy profile of all players except for player i. When each player i {1, ..., n} chooses strategy xi resulting in strategy profile x = (x1, ..., xn) then player i obtains payoff fi(x). Note that the payoff depends on the strategy profile chosen, i.e. on the strategy chosen by player i as well as the strategies chosen by all the other players. A strategy profile x* S is a Nash equilibrium (NE) if no unilateral deviation in strategy by any single player is profitable for that player, that is

A game can have a pure strategy NE or an NE in its mixed extension (that of choosing a pure strategy stochastically with a fixed frequency). Nash proved that if we allow mixed strategies, then every n-player game in which every player can choose from finitely many strategies admits at least one Nash equilibrium.
When the inequality above holds strictly (with > instead of ) for all players and all feasible alternative strategies, then the equilibrium is classified as a strict Nash equilibrium. If instead, for some player, there is exact equality between and some other strategy in the set S, then the equilibrium is classified as a weak Nash equilibrium.
[edit] Examples
[edit] Competition game
Player 2 chooses '0' Player 2 chooses '1' Player 2 chooses '2' Player 2 chooses '3'
Player 1 chooses '0' 0, 0 2, -2 2, -2 2, -2
Player 1 chooses '1' -2, 2 1, 1 3, -1 3, -1
Player 1 chooses '2' -2, 2 -1, 3 2, 2 4, 0
Player 1 chooses '3' -2, 2 -1, 3 0, 4 3, 3
A competition game
This can be illustrated by a two-player game in which both players simultaneously choose a whole number from 0 to 3 and they both win the smaller of the two numbers in points. In addition, if one player chooses a larger number than the other, then he/she has to give up two points to the other. This game has a unique pure-strategy Nash equilibrium: both players choosing 0 (highlighted in light red). Any other choice of strategies can be improved if one of the players lowers his number to one less than the other player's number. In the table to the left, for example, when starting at the green square it is in player 1's interest to move to the purple square by choosing a smaller number, and it is in player 2's interest to move to the blue square by choosing a smaller number. If the game is modified so that the two players win the named amount if they both choose the same number, and otherwise win nothing, then there are 4 Nash equilibria (0,0...1,1...2,2...and 3,3).
[edit] Coordination game
Main article: Coordination game
Player 2 adopts strategy 1 Player 2 adopts strategy 2
Player 1 adopts strategy 1 A, A B, C
Player 1 adopts strategy 2 C, B D, D
A coordination game
The coordination game is a classic (symmetric) two player, two strategy game, with the payoff matrix shown to the right, where the payoffs satisfy A>C and D>B. The players should thus coordinate, either on A or on D, to receive a high payoff. If the players' choices do not coincide, a lower payoff is rewarded. An example of a coordination game is the setting where two technologies are available to two firms with compatible products, and they have to elect a strategy to become the market standard. If both firms agree on the chosen technology, high sales are expected for both firms. If the firms do not agree on the standard technology, few sales result. Both strategies are Nash equilibria of the game.
Driving on a road, and having to choose either to drive on the left or to drive on the right of the road, is also a coordination game. For example, with payoffs 100 meaning no crash and 0 meaning a crash, the coordination game can be defined with the following payoff matrix:
Drive on the Left Drive on the Right
Drive on the Left 100, 100 0, 0
Drive on the Right 0, 0 100, 100
The driving game
In this case there are two pure strategy Nash equilibria, when both choose to either drive on the left or on the right. If we admit mixed strategies (where a pure strategy is chosen at random, subject to some fixed probability), then there are three Nash equilibria for the same case: two we have seen from the pure-strategy form, where the probabilities are (0%,100%) for player one, (0%, 100%) for player two; and (100%, 0%) for player one, (100%, 0%) for player two respectively. We add another where the probabilities for each player is (50%, 50%).
[edit] Prisoner's dilemma
Main article: Prisoner's dilemma
(note differences in the orientation of the payoff matrix)
The Prisoner's Dilemma has the same payoff matrix as depicted for the Coordination Game, but now C > A > D > B. Because C > A and D > B, each player improves his situation by switching from strategy #1 to strategy #2, no matter what the other player decides. The Prisoner's Dilemma thus has a single Nash Equilibrium: both players choosing strategy #2 ("betraying"). What has long made this an interesting case to study is the fact that D < A (ie., "both betray" is globally inferior to "both remain loyal"). The globally optimal strategy is unstable; it is not an equilibrium.
[edit] Nash equilibria in a payoff matrix
There is an easy numerical way to identify Nash Equilibria on a Payoff Matrix. It is especially helpful in two-person games where players have more than two strategies. In this case formal analysis may become too long. This rule does not apply to the case where mixed (stochastic) strategies are of interest. The rule goes as follows: if the first payoff number, in the duplet of the cell, is the maximum of the column of the cell and if the second number is the maximum of the row of the cell - then the cell represents a Nash equilibrium.
We can apply this rule to a 3x3 matrix:
Option A Option B Option C
Option A 0, 0 25, 40 5, 10
Option B 40, 25 0, 0 5, 15
Option C 10, 5 15, 5 10, 10
A Payoff Matrix
Using the rule, we can very quickly (much faster than with formal analysis) see that the Nash Equlibria cells are (B,A), (A,B), and (C,C). Indeed, for cell (B,A) 40 is the maximum of the first column and 25 is the maximum of the second row. For (A,B) 25 is the maximum of the second column and 40 is the maximum of the first row. Same for cell (C,C). For other cells, either one or both of the duplet members are not the maximum of the corresponding rows and columns.
This said, the actual mechanics of finding equilibrium cells is obvious: find the maximum of a column and check if the second member of the pair is the maximum of the row. If these conditions are met, the cell represents a Nash Equilibrium. Check all columns this way to find all NE cells. An NxN matrix may have between 0 and NxN pure strategy Nash equilibria.

[edit] Stability
The concept of stability, useful in the analysis of many kinds of equilibrium, can also be applied to Nash equilibria.
A Nash equilibrium for a mixed strategy game is stable if a small change (specifically, an infinitesimal change) in probabilities for one player leads to a situation where two conditions hold:
1. the player who did not change has no better strategy in the new circumstance
2. the player who did change is now playing with a strictly worse strategy
If these cases are both met, then a player with the small change in his mixed-strategy will return immediately to the Nash equilibrium. The equilibrium is said to be stable. If condition one does not hold then the equilibrium is unstable. If only condition one holds then there are likely to be an infinite number of optimal strategies for the player who changed. John Nash showed that the latter situation could not arise in a range of well-defined games.
In the "driving game" example above there are both stable and unstable equilibria. The equilibria involving mixed-strategies with 100% probabilities are stable. If either player changes his probabilities slightly, they will be both at a disadvantage, and his opponent will have no reason to change his strategy in turn. The (50%,50%) equilibrium is unstable. If either player changes his probabilities, then the other player immediately has a better strategy at either (0%, 100%) or (100%, 0%).
Stability is crucial in practical applications of Nash equilibria, since the mixed-strategy of each player is not perfectly known, but has to be inferred from statistical distribution of his actions in the game. In this case unstable equilibria are very unlikely to arise in practice, since any minute change in the proportions of each strategy seen will lead to a change in strategy and the breakdown of the equilibrium.
A Coalition-Proof Nash Equilibrium (CPNE) (similar to a Strong Nash Equilibrium) occurs when players cannot do better even if they are allowed to communicate and collaborate before the game. Every correlated strategy supported by iterated strict dominance and on the Pareto frontier is a CPNE[2]. Further, it is possible for a game to have a Nash equilibrium that is resilient against coalitions less than a specified size, k. CPNE is related to the theory of the core.
[edit] Occurrence
If a game has a unique Nash equilibrium and is played among players under certain conditions, then the NE strategy set will be adopted. Sufficient conditions to guarantee that the Nash equilibrium is played are:
1. The players all will do their utmost to maximize their expected payoff as described by the game.
2. The players are flawless in execution.
3. The players have sufficient intelligence to deduce the solution.
4. The players know the planned equilibrium strategy of all of the other players.
5. The players believe that a deviation in their own strategy will not cause deviations by any other players.
6. There is common knowledge that all players meet these conditions, including this one. So, not only must each player know the other players meet the conditions, but also they must know that they all know that they meet them, and know that they know that they know that they meet them, and so on.
[edit] Where the conditions are not met
Examples of game theory problems in which these conditions are not met:
1. The first condition is not met if the game does not correctly describe the quantities a player wishes to maximize. In this case there is no particular reason for that player to adopt an equilibrium strategy. For instance, the prisoner’s dilemma is not a dilemma if either player is happy to be jailed indefinitely.
2. Intentional or accidental imperfection in execution. For example, a computer capable of flawless logical play facing a second flawless computer will result in equilibrium. Introduction of imperfection will lead to its disruption either through loss to the player who makes the mistake, or through negation of the 4th 'common knowledge' criterion leading to possible victory for the player. (An example would be a player suddenly putting the car into reverse in the game of 'chicken', ensuring a no-loss no-win scenario).
3. In many cases, the third condition is not met because, even though the equilibrium must exist, it is unknown due to the complexity of the game, for instance in Chinese chess.[3] Or, if known, it may not be known to all players, as when playing tic-tac-toe with a small child who desperately wants to win (meeting the other criteria).
4. The fourth criterion of common knowledge may not be met even if all players do, in fact, meet all the other criteria. Players wrongly distrusting each other's rationality may adopt counter-strategies to expected irrational play on their opponents’ behalf. This is a major consideration in “Chicken” or an arms race, for example.
[edit] Where the conditions are met
Due to the limited conditions in which NE can actually be observed, they are rarely treated as a guide to day-to-day behaviour, or observed in practice in human negotiations. However, as a theoretical concept in economics, and evolutionary biology the NE has explanatory power. The payoff in economics is money, and in evolutionary biology gene transmission, both are the fundamental bottom line of survival. Researchers who apply games theory in these fields claim that agents failing to maximize these for whatever reason will be competed out of the market or environment, which are ascribed the ability to test all strategies. This conclusion is drawn from the "stability" theory above. In these situations the assumption that the strategy observed is actually a NE has often been borne out by research.[verification needed]
[edit] NE and non-credible threats


Extensive and Normal form illustrations that show the difference between SPNE and other NE. The blue equilibrium is not subgame perfect because player two makes a non-credible threat at 2(2) to be unkind (U).
The nash equilibrium is a superset of the subgame perfect nash equilibrium. The subgame perfect equilibrium in addition to the Nash Equilibrium requires that the strategy also is a Nash equilibrium in every subgame of that game. This eliminates all non-credible threats, that is, strategies that contain non-rational moves in order to make the counter-player change his strategy.
The image to the right shows a simple sequential game that illustrates the issue with subgame imperfect Nash equilibria. In this game player one chooses left(L) or right(R), which is followed by player two being called upon to be kind (K) or unkind (U) to player one, However, player two only stands to gain from being unkind if player one goes left. If player one goes right the rational player two would de facto be kind to him in that subgame. However, The non-credible threat of being unkind at 2(2) is still part of the blue (L, (U,U)) nash equilibrium. Therefore, if rational behavior can be expected by both parties the subgame perfect Nash equilibrium may be a more meaningful solution concept when such dynamic inconsistencies arise.
[edit] Proof of existence
As above, let σ − i be a mixed strategy profile of all players except for player i. We can define a best response correspondence for player i, bi. bi is a relation from the set of all probability distributions over opponent player profiles to a set of player i's strategies, such that each element of
bi(σ − i)
is a best response to σ − i. Define
.
One can use the Kakutani fixed point theorem to prove that b has a fixed point. That is, there is a σ * such that . Since b(σ * ) represents the best response for all players to σ * , the existence of the fixed point proves that there is some strategy set which is a best response to itself. No player could do any better by deviating, and it is therefore a Nash equilibrium.
When Nash made this point to John von Neumann in 1949, von Neumann famously dismissed it with the words, "That's trivial, you know. That's just a fixed point theorem." (See Nasar, 1998, p. 94.)
[edit] Alternate proof using the Brouwer fixed point theorem
We have a game G = (N,A,u) where N is the number of players and is the action set for the players. All of the actions sets Ai are finite. Let denote the set of mixed strategies for the players. The finiteness of the Ais insures the compactness of Δ.
We can now define the gain functions. For a mixed strategy , we let the gain for player i on action be
Gaini(σ,a) = max{0,ui(ai,σ − i) − ui(σi,σ − i)}
The gain function represents the benefit a player gets by unilaterally changing his strategy. We now define where
gi(σ)(a) = σi(a) + Gaini(σ,a)
for . We see that

We now use g to define as follows. Let

for . It is easy to see that each fi is a valid mixed strategy in Δi. It is also easy to check that each fi is a continuous function of σ, and hence f is a continuous function. Now Δ is the cross product of a finite number of compact convex sets, and so we get that Δ is also compact and convex. Therefore we may apply the Brouwer fixed point theorem to f. So f has a fixed point in Δ, call it σ * .
I claim that σ * is a Nash Equilibrium in G. For this purpose, it suffices to show that

This simply states the each player gains no benefit by unilaterally changing his strategy which is exactly the necessary condition for being a Nash Equilibrium.
Now assume that the gains are not all zero. Therefore, , , and such that Gaini(σ * ,a) > 0. Note then that

So let . Also we shall denote as the gain vector indexed by actions in Ai. Since f(σ * ) = σ * we clearly have that . Therefore we see that


Since C > 1 we have that is some positive scaling of the vector . Now I claim that

. To see this, we first note that if Gaini(σ * ,a) > 0 then this is true by definition of the gain function. Now assume that Gaini(σ * ,a) = 0. By our previous statements we have that

and so the left term is zero, giving us that the entire expression is 0 as needed.
So we finally have that





where the last inequality follows since is a non-zero vector. But this is a clear contradiction, so all the gains must indeed be zero. Therefore σ * is a Nash Equilibrium for G as needed.
[edit] Computing Nash equilibria
If a player A has a dominant strategy sA then there exists a Nash equilibrium in which A plays sA. In the case of two players A and B, there exists a Nash equilibrium in which A plays sA and B plays a best response to sA. If sA is a strictly dominant strategy, A plays sA in all Nash equilibria. If both A and B have strictly dominant strategies, there exists a unique Nash equilibrium in which each plays his strictly dominant strategy.
In games with mixed strategy Nash equilibria, the probability of a player choosing any particular strategy can be computed by assigning a variable to each strategy that represents a fixed probability for choosing that strategy. In order for a player to be willing to randomize, his expected payoff for each strategy should be the same. In addition, the sum of the probabilities for each strategy of a particular player should be 1. This creates a system of equations from which the probabilities of choosing each strategy can be derived.[1]
[edit] Examples
Player A plays H Player A plays T
Player B plays H -1, +1 +1, -1
Player B plays T +1, -1 -1, +1
Matching pennies
In the matching pennies game, player A loses a point to B if A and B play the same strategy and wins a point from B if they play different strategies. To compute the mixed strategy Nash equilibrium, assign A the probability p of playing H and (1-p) of playing T, and assign B the probability q of playing H and (1-q) of playing T.
E[payoff for A playing H] = (-1)q + (+1)(1-q) = 1-2q
E[payoff for A playing T] = (+1)q + (-1)(1-q) = 2q-1
E[payoff for A playing H] = E[payoff for A playing T] ⇒ 1-2q = 2q-1 ⇒ q = 1/2
E[payoff for B playing H] = (+1)p + (-1)(1-p) = 2p-1
E[payoff for B playing T] = (-1)p + (+1)(1-p) = 1-2p
E[payoff for B playing H] = E[payoff for B playing T] ⇒ 2p-1 = 1-2p ⇒ p = 1/2
Thus a mixed strategy Nash equilibrium in this game is for each player to randomly choose H or T with equal probability.
จอห์น แนช
จากวิกิพีเดีย สารานุกรมเสรี
ไปที่: ป้ายบอกทาง, ค้นหา




จอห์น แนช
จอห์น ฟอบส์ แนช จูเนียร์ (John Forbes Nash, Jr.) เกิดเมื่อวันที่ 13 มิถุนายน ค.ศ. 1928 เป็นนักคณิตศาสตร์ชาวอเมริกัน มีความเชี่ยวชาญเรื่องทฤษฎีเกม, เรขาคณิตเชิงอนุพันธ์ และสมการเชิงอนุพันธ์แบบแบ่งส่วน ดำรงตำแหน่งนักวิจัยอาวุโสสาขาคณิตศาสตร์ที่มหาวิทยาลัยปรินซ์ตัน ได้รับรางวัลโนเบลสาขาเศรษฐศาสตร์ ประจำปี พ.ศ. 2537 จากผลงานเรื่องทฤษฎีเกมร่วมกับ Reinhard Selten และ John Harsanyi
ชีวประวัติของแนชได้มีการนำไปสร้างเป็นภาพยนตร์ที่โด่งดังในวงการฮอลลีวูด ชื่อ A Beautiful Mind ซึ่งเป็นภาพยนตร์ที่ได้รับการเสนอชื่อเข้าชิงรางวัลออสการ์ได้ถึง 8 รายการ เนื้อหาในภาพยนตร์จะเกี่ยวกับนักคณิตศาสตร์ผู้ปราชญ์เปรื่องคนหนึ่งที่มีชื่อเดียวกับเขา และต้องต่อสู้กับโรคประสาทหลอนเช่นเดียวกัน
[แก้] วัยเด็กและการศึกษา
แนชเกิดและเติบโตขึ้นในมลรัฐเวสต์เวอร์จิเนีย บิดาของเขาคือ จอห์น ฟอบส์ แนช เป็นวิศวกรไฟฟ้าและมารดาของเขาคือ มากาเรต เวอร์จิเนีย มาร์ติน เป็นครูสอนวิชาภาษาอังกฤษและภาษาละติน ต่อมา เมื่อวันที่ 16 พฤศจิกายน ค.ศ. 1930 มารดาของเขาก็ได้ให้กำเนิดน้องสาว คือ มาร์ธา แนช
เมื่อแนชอายุได้ 12 ปี เขาก็เริ่มทำการทดลองทางวิทยาศาสตร์ภายในห้องนอนของเขา แนชเป็นคนที่ค่อนข้างเก็บตัวเงียบและไม่อยากจะทำงานร่วมกับผู้อื่น เขาชอบทำงานตัวคนเดียวมากกว่า เขาปฏิเสธการอยู่ห้องร่วมกับคนอื่น แนชปรับตัวเข้ากับเพื่อนร่วมชั้นไม่ได้เพราะเพื่อนๆมักจะแกล้งเขาเสมอและเขามักจะนึกว่าตัวเองฉลาดกว่าคนอื่น เขาเชื่อว่าการเต้นรำและการเล่นกีฬาเป็นสิ่งที่ทำให้เขาไม่มีสมาธิกับการทดลองและการเรียนของเขา
มาร์ธา น้องสาวของจอห์น แนชดูเป็นคนปกติมากกว่าจอห์น และจอห์นก็ดูผิดปกติไปจากเด็กคนอื่นๆ มาร์ธาเล่าว่า "จอห์นนี่เป็นคนที่ผิดปกติจากคนอื่น พ่อแม่ก็รู้ว่าเขาผิดปกติ แต่พวกเขาก็รู้ว่าจอห์นนี่ฉลาด เขามักจะทำอะไรด้วยวิธีของตัวเอง แม่บอกว่าการที่ฉันเป็นเพื่อนเล่นให้กับเขาคือสิ่งที่ฉันทำได้เพื่อเขา... แต่ฉันก็ไม่ค่อยสนใจหรอกว่าพี่ชายฉันเป็นคนค่อนข้างแปลก"[1]
แนชเขียนไว้ในหนังสือชีวประวัติของเขาบอกว่า หนังสือเรื่อง Men of Mathematics แต่งโดย E.T. Bell (จริงๆคือ เป็นเรียงความที่อยู่ใน Fermat) เป็นหนังสือที่ทำให้เขาหันมาสนใจด้านคณิตศาสตร์ แนชเข้าไปเรียนที่วิทยาลัยบลูฟิลด์ตั้งแต่ตอนที่ยังเรียนไฮสกูลอยู่ ต่อมาก็ได้ศึกษาต่อในระดับมหาวิทยาลัยที่สถาบันเทคโนโลยีคาร์เนจี (ต่อมาเปลี่ยนชื่อเป็นมหาวิทยาลัยคาร์เนจีเมลลอน) ในเมืองพิตต์สเบิร์ก มลรัฐเพนซิลวาเนีย โดยได้รับทุนการศึกษาเวสติงเฮาส์ ตอนแรก แนชสนใจศึกษาวิชาวิศวกรรมเคมี ต่อมาก็มาศึกษาด้านเคมี ก่อนจะหันมาเปลี่ยนเป็นคณิตศาสตร์ในที่สุด เขาสำเร็จการศึกษาโดยได้รับทั้งปริญญาตรีและปริญญาโทในปี ค.ศ. 1948 ที่สถาบันคาร์เนจีนั่นเอง
หลังจากจบการศึกษาแล้ว แนชทำงานในช่วงหน้าร้อนที่เมืองไวท์โอค มลรัฐแมรีแลนด์ โดยเป็นทำวิจัยเกี่ยวกับทหารเรือภายใต้การควบคุมของนักคณิตศาสตร์ชื่อ Clifford Truesdell
[แก้] หลังจบการศึกษา
ในปี 1948 ช่วงที่แนชกำลังสมัครงานที่ภาควิชาคณิตศาสตร์แห่งมหาวิทยาลัยปรินซ์ตันอยู่นั้น ศาสตราจารย์ R.J. Duffin ที่ปรึกษาของแนชและอดีตศาสตราจารย์แห่งสถาบันเทคโนโลยีคาร์เนจีได้เขียนจดหมายแนะนำตัวให้กับแนชโดยมีใจความสั้นๆคือ "เด็กหนุ่มนี้เป็นอัจฉริยะ"[2] แต่ว่ากลายเป็นมหาวิทยาลัยฮาร์วาร์ดที่ตอบรับการสมัครงานของแนชก่อน ซึ่งที่จริงแล้ว ฮาร์วาร์ดเป็นเป้าหมายอันดับหนึ่งของเขาเพราะเป็นสถาบันที่มีชื่อเสียงมายาวนานและมีคณะคณิตศาสตร์ที่โด่งดัง แต่ Solomon Lefschetz หัวหน้าภาควิชาคณิตศาสตร์แห่งมหาวิทยาลัยปรินซ์ตันและจอห์น เอส. เคเนดี แนะนำเขาว่าฮาร์วาร์ดคงจะไม่เห็นค่าของเขาเท่าที่มหาวิทยาลัยปรินซ์ตัน[1] จนในที่สุด แนชจึงได้ตัดสินใจย้ายจากไวท์โอคมาทำงานที่มหาวิทยาลัยปรินซ์ตัน และทำงานอยู่ที่นั่นจนเกิดทฤษฎีดุลยภาพของเขา (ทฤษฎีดุลยภาพของแนช) แนชได้รับปริญญาดุษฎีบัณฑิตกิตติมศักดิ์ในปี 1950 จากวิทยานิพนธ์เรื่องทฤษฏีเกมแบบไม่มีความร่วมมือกัน[3] โดยมี Albert W. Tucker เป็นอาจารย์ที่ปรึกษา วิทยานิพนธ์นี้ส่วนหนึ่งมีเนื้อหาเกี่ยวกับนิยามและคุณสมบัติของสิ่งที่ต่อมาเรียกว่า "ดุลยภาพของแนช" ซึ่งเกี่ยวกับ 3 ประเด็นหลักดังนี้ :
• "Equilibrium Points in N-person Games", Proceedings of the National Academy of Sciences 36 (1950), 48–49. [1]
• "The Bargaining Problem", Econometrica 18 (1950), 155–162. [2]
• "Two-person Cooperative Games", Econometrica 21 (1953), 128–140. [3]
นอกจากนั้น แนชยังได้มีผลงานสำคัญๆเกี่ยวกับเรขาคณิตเชิงพีชคณิตอีกด้วย คือ:
• "Real algebraic manifolds", Annals of Mathematics 56 (1952), 405–421. [4] See also Proc. Internat. Congr. Math. (AMS, 1952, pp 516–517)
ผลงานที่มีชื่อเสียงที่สุดของเขาในสาขาของคณิตศาสตร์บริสุทธิ์ คือ Nash embedding theorem
Howard Raiffa
From Wikipedia, the free encyclopedia
Jump to: navigation, search

To comply with Wikipedia's quality standards, this article may need to be rewritten.
Please help improve this article. The discussion page may contain suggestions.

Howard Raiffa (1924– IPA: /ˈreɪfə/) is the Frank P. Ramsey Professor (Emeritus) of Managerial Economics, a joint chair held by the Business School and the Kennedy School of Government at Harvard University. He is an influential Bayesian decision theorist and negotiation theorist.
• His book Applied Statistical Decision Theory with Robert Schlaifer introduced the idea of conjugate prior distributions.
• A lecture of his in the 1960s concerning the use of Bayesian methods for betting on horses gave John Craven USN, a US Navy scientist the idea of using Bayesian methods to search for a missing US Air Force hydrogen bomb lost near Palomares, Spain in the Palomares hydrogen bombs incident of 1966. Craven used the same methods again in the search for the lost submarine USS Scorpion in 1968. Raiffa has analysed situations involving the use of subjective probability and argues that subjective probabilities should follow the same rules (the Kolmogorov axioms) as objective, frequency-based probabilities.
Consider a situation in which you are required to gamble and are given two possible gambles.
Gamble A, in which you bet on the outcome of a fight between the world's greatest boxer and the world's greatest wrestler in a ring fight. (Assume you are fairly ignorant about martial arts and would have great difficulty making a choice of who to bet on.) If your chosen champion wins you win $500 otherwise you get nothing. You place your choice in a sealed envelope which is opened after the game.
Gamble B. Draw a ball from an opaque urn known to contain 50 orange and 50 blue balls. You will receive $500 if you draw an orange ball and nothing for a blue ball. The balls have been thoroughly mixed and you should assume that all balls are equally likely to be drawn. The draw takes place after the ring match is over.
Many people would feel more unsure about taking Gamble A in which the probabilities are unknown, rather than Gamble B, in which the probabilities are easily seen to be one half for each outcome.
Raiffa argues that a decision-maker should in fact assign a subjective probability of one-half to each outcome of Gamble A, provided that no information was available which makes one outcome more likely than the other.
Raiffa argues as follows. Suppose someone has the following preferences. If forced to take Gamble A they would bet on the boxer, but if given a free choice between the gambles they would prefer Gamble B. Presumably, such a person when allowed to choose Gamble A would prefer to simply bet on the boxer rather than toss a coin to decide the matter of whether they should bet on the boxer or the wrestler. But this randomised approach is equivalent to Gamble B. So, by the axioms of substitutibility and transitivity for utilities, they should also prefer to bet on the boxer than on Gamble B. A similar argument can be used to show that when the player has no preference between the boxer and the wrestler he should also have no preference between Gamble A and Gamble B.
(The axiom of substitutibility says that if someone is indifferent between outcomes A and B and indifferent between outcomes A and C, they should be indifferent between B and C. The axiom of transitivity says that if someone prefers outcome A to B and also prefers B to C, then they should prefer A to C.)
Others, such as Daniel Ellsberg disagree with Raiffa's reasoning and have devised alternatives interpretations of decision theory. One of the most radical departures is Dempster-Shafer theory which rejects the use of probability theory completely, in favour of a theory of belief functions which do not satisfy the axioms of probability.