ทฤษฎีเกม: เกมเมทริกซ์ ตัวอย่างการแก้ปัญหาทฤษฎีเกมในกลยุทธ์แบบผสมโดยบริการของเรา

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

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

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

ตอนนี้เกี่ยวกับทุกอย่างตามลำดับและในรายละเอียด

เมทริกซ์ผลตอบแทน กลยุทธ์บริสุทธิ์ ราคาเกม

ใน เกมเมทริกซ์ กฎของมันถูกกำหนด เมทริกซ์ผลตอบแทน .

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

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

มาสร้างเมทริกซ์ผลตอบแทน:

หากผู้เล่นคนแรกเลือก ฉัน-th กลยุทธ์ที่บริสุทธิ์และผู้เล่นคนที่สอง เจ- กลยุทธ์ที่บริสุทธิ์จากนั้นผลตอบแทนของผู้เล่นคนแรกคือ กไอเจหน่วยและการสูญเสียของผู้เล่นคนที่สองก็เช่นกัน กไอเจหน่วย

เพราะ กอิจ + (- ก ij ) = 0จากนั้นเกมที่อธิบายคือเกมเมทริกซ์ผลรวมเป็นศูนย์

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

งานของทฤษฎีเกมคือการกำหนดทางเลือกของกลยุทธ์ของผู้เล่นคนแรก ซึ่งจะรับประกันว่าเขาจะได้รับค่าเฉลี่ยสูงสุด เช่นเดียวกับการเลือกกลยุทธ์ของผู้เล่นคนที่สอง ซึ่งจะรับประกันว่าเขาจะได้รับการสูญเสียโดยเฉลี่ยสูงสุด

วิธีการเลือกกลยุทธ์ในเกมเมทริกซ์?

ลองดูเมทริกซ์ผลตอบแทนอีกครั้ง:

ขั้นแรก เราจะกำหนดผลตอบแทนของผู้เล่นคนแรกหากเขาใช้ ฉันกลยุทธ์ที่บริสุทธิ์ หากผู้เล่นคนแรกใช้ ฉัน-th กลยุทธ์ที่บริสุทธิ์ ดังนั้นจึงมีเหตุผลที่จะสันนิษฐานว่าผู้เล่นคนที่สองจะใช้กลยุทธ์ที่บริสุทธิ์ดังกล่าว เนื่องจากผลตอบแทนของผู้เล่นคนแรกจะน้อยที่สุด ในทางกลับกัน ผู้เล่นคนแรกจะใช้กลยุทธ์ที่แท้จริงที่จะให้ผลตอบแทนสูงสุดแก่เขา ตามเงื่อนไขเหล่านี้ ผลตอบแทนของผู้เล่นคนแรกซึ่งเราแสดงว่าเป็น โวลต์1 , ถูกเรียก ชนะสูงสุด หรือ ราคาเกมที่ต่ำกว่า .

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

ตอนนี้เรามาพิจารณาการสูญเสียของผู้เล่นคนที่สองหากเขาใช้ เจ-th กลยุทธ์ ในกรณีนี้ ผู้เล่นคนแรกใช้กลยุทธ์ของตัวเอง ซึ่งผู้เล่นคนที่สองจะสูญเสียมากที่สุด ผู้เล่นคนที่สองต้องเลือกกลยุทธ์ที่บริสุทธิ์ซึ่งการสูญเสียของเขาจะน้อยที่สุด การสูญเสียผู้เล่นคนที่สองซึ่งเราแสดงว่า โวลต์2 , ถูกเรียก การสูญเสียขั้นต่ำ หรือ ราคาเกมชั้นนำ .

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

ตัวอย่างที่ 1

.

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

ตอนนี้เราได้เรียนรู้วิธีหาราคาที่ต่ำและสูงของเกม กลยุทธ์ maximin และ minimax แล้วก็ถึงเวลาเรียนรู้วิธีกำหนดแนวคิดเหล่านี้อย่างเป็นทางการ

ดังนั้นการรับประกันผลตอบแทนของผู้เล่นคนแรกคือ:

ผู้เล่นคนแรกต้องเลือกกลยุทธ์ที่บริสุทธิ์ที่จะให้ผลตอบแทนขั้นต่ำสูงสุดแก่เขา กำไร (สูงสุด) นี้แสดงดังนี้:

.

ผู้เล่นคนแรกใช้กลยุทธ์ที่บริสุทธิ์เพื่อให้ผู้เล่นคนที่สองสูญเสียมากที่สุด การสูญเสียนี้ถูกกำหนดดังนี้:

ผู้เล่นคนที่สองต้องเลือกกลยุทธ์ที่แท้จริงเพื่อให้การสูญเสียน้อยที่สุด การสูญเสียนี้ (minimax) แสดงดังนี้:

.

อีกตัวอย่างหนึ่งจากซีรีส์เดียวกัน

ตัวอย่างที่ 2กำหนดเกมเมทริกซ์ด้วยเมทริกซ์ผลตอบแทน

.

กำหนดกลยุทธ์สูงสุดของผู้เล่นคนแรก กลยุทธ์ขั้นต่ำของผู้เล่นคนที่สอง ราคาที่ต่ำกว่าและราคาสูงสุดของเกม

สารละลาย. ทางด้านขวาของเมทริกซ์ payoff เราเขียนองค์ประกอบที่เล็กที่สุดในแถวและทำเครื่องหมายค่าสูงสุดและจากด้านล่างของเมทริกซ์ - องค์ประกอบที่ใหญ่ที่สุดในคอลัมน์และเลือกค่าต่ำสุด:

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

จุดอานในเกมเมทริกซ์

หากราคาบนและล่างของเกมเท่ากัน เกมเมทริกซ์จะถือว่ามีจุดอาน ในทางกลับกันก็เป็นความจริงเช่นกัน: หากเกมเมทริกซ์มีจุดอาน ราคาบนและล่างของเกมเมทริกซ์จะเท่ากัน องค์ประกอบที่สอดคล้องกันนั้นเป็นทั้งองค์ประกอบที่เล็กที่สุดในแถวและใหญ่ที่สุดในคอลัมน์ และมีค่าเท่ากับราคาของเกม

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

ในกรณีนี้ เกมเมทริกซ์มีวิธีแก้ปัญหาด้วยกลยุทธ์ที่บริสุทธิ์ .

ตัวอย่างที่ 3กำหนดเกมเมทริกซ์ด้วยเมทริกซ์ผลตอบแทน

.

สารละลาย. ทางด้านขวาของเมทริกซ์ payoff เราเขียนองค์ประกอบที่เล็กที่สุดในแถวและทำเครื่องหมายค่าสูงสุดและจากด้านล่างของเมทริกซ์ - องค์ประกอบที่ใหญ่ที่สุดในคอลัมน์และเลือกค่าต่ำสุด:

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

แก้ปัญหาเกมเมทริกซ์ด้วยตัวคุณเอง แล้วดูวิธีแก้ปัญหา

ตัวอย่างที่ 4กำหนดเกมเมทริกซ์ด้วยเมทริกซ์ผลตอบแทน

.

ค้นหาราคาที่ต่ำกว่าและสูงกว่าของเกม เกมเมทริกซ์นี้มีจุดอานหรือไม่?

เกมเมทริกซ์พร้อมกลยุทธ์ผสมผสานที่ดีที่สุด

ในกรณีส่วนใหญ่ เกมเมทริกซ์ไม่มีอานม้า ดังนั้นเกมเมทริกซ์ที่เกี่ยวข้องจึงไม่มีวิธีแก้ปัญหาเชิงกลยุทธ์อย่างแท้จริง

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

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

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

.

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

.

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

.

ตัวอย่างที่ 5กำหนดเกมเมทริกซ์ด้วยเมทริกซ์ผลตอบแทน

.

กำหนดความคาดหวังทางคณิตศาสตร์ของกำไรของผู้เล่นคนแรก (การสูญเสียของผู้เล่นคนที่สอง) หากกลยุทธ์แบบผสมของผู้เล่นคนแรกคือ และกลยุทธ์แบบผสมของผู้เล่นคนที่สองคือ

สารละลาย. ตามสูตรสำหรับความคาดหวังทางคณิตศาสตร์ของการได้รับของผู้เล่นคนแรก (การสูญเสียของผู้เล่นคนที่สอง) จะเท่ากับผลคูณของเวกเตอร์กลยุทธ์แบบผสมของผู้เล่นคนแรก เมทริกซ์ผลตอบแทน และเวกเตอร์กลยุทธ์แบบผสมของผู้เล่นคนที่สอง:

ผู้เล่นคนแรกเรียกว่ากลยุทธ์แบบผสมที่จะให้ผลตอบแทนเฉลี่ยสูงสุดแก่เขาหากเกมเล่นซ้ำในจำนวนครั้งที่เพียงพอ

กลยุทธ์ผสมที่เหมาะสมที่สุด ผู้เล่นคนที่สองเรียกว่ากลยุทธ์แบบผสมซึ่งจะทำให้เขาสูญเสียโดยเฉลี่ยน้อยที่สุดหากเกมเล่นซ้ำในจำนวนครั้งที่เพียงพอ

โดยการเปรียบเทียบกับสัญลักษณ์ของ maximin และ minimax ในกรณีของกลยุทธ์บริสุทธิ์ กลยุทธ์ผสมที่เหมาะสมจะแสดงดังต่อไปนี้ (และเกี่ยวข้องกับ ความคาดหวังทางคณิตศาสตร์นั่นคือค่าเฉลี่ยของกำไรของผู้เล่นคนแรกและการสูญเสียของผู้เล่นคนที่สอง):

,

.

ในกรณีนี้ สำหรับฟังก์ชัน อี มีจุดอาน ซึ่งหมายถึงความเท่าเทียมกัน

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

การย่อเกมเมทริกซ์ให้เป็นปัญหาการเขียนโปรแกรมเชิงเส้น

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

ฟังก์ชันเป้าหมายในปัญหาการโปรแกรมเชิงเส้นตรง:

.

ระบบข้อจำกัดในปัญหาโดยตรงของโปรแกรมเชิงเส้น:

ฟังก์ชั่นเป้าหมายในปัญหาคู่:

.

ระบบข้อ จำกัด ในปัญหาคู่:

แสดงแผนที่เหมาะสมที่สุดของปัญหาการโปรแกรมเชิงเส้นตรง

,

และแผนที่ดีที่สุดของปัญหาคู่จะแสดงด้วย

รูปแบบเชิงเส้นสำหรับการออกแบบที่เหมาะสมที่สุดจะแสดงด้วย และ ,

และคุณต้องค้นหาผลรวมของพิกัดที่สอดคล้องกันของแผนที่เหมาะสมที่สุด

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

.

นักคณิตศาสตร์ได้พิสูจน์แล้วว่า ราคาเกม จะแสดงในรูปแบบเส้นตรงของแผนที่เหมาะสมดังนี้

,

นั่นคือเป็นผลรวมของพิกัดของแผนที่เหมาะสมที่สุด

เราผู้ปฏิบัติงานสามารถใช้สูตรนี้เพื่อแก้ปัญหาเกมเมทริกซ์ในกลยุทธ์แบบผสม ชอบ สูตรสำหรับการค้นหากลยุทธ์ผสมที่เหมาะสมที่สุด ผู้เล่นคนแรกและคนที่สองตามลำดับ:

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

ตัวอย่างที่ 6กำหนดเกมเมทริกซ์ด้วยเมทริกซ์ผลตอบแทน

.

ค้นหาราคาของเกม วีและกลยุทธ์ผสมที่เหมาะสมที่สุด และ

สารละลาย. เราสร้างปัญหาการเขียนโปรแกรมเชิงเส้นที่สอดคล้องกับเกมเมทริกซ์นี้:

เราได้รับวิธีแก้ปัญหาโดยตรง:

.

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

เนื้อหา 1 ข้อมูลทั่วไป 2 1.1 เกม . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 การเคลื่อนไหว . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 กลยุทธ์ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 เกมเมทริกซ์ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 จุดติดตาม กลยุทธ์บริสุทธิ์ 7 2.1 ตัวอย่าง . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 ตัวอย่างที่ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 ตัวอย่างที่ 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 กลยุทธ์ผสม 9 3.1 เกม 2×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 ตัวอย่าง . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 ตัวอย่างที่ 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 ตัวอย่างที่ 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 การตีความทางเรขาคณิต . . . . . . . . . . . . . . . . . . . 12 3.2 เกม 2×n และ m×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 ตัวอย่างที่ 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. ข้อมูลทั่วไปจากทฤษฎีเกม 1.1. เกมส์ ทฤษฎีเกมส์คือ ทฤษฎีทางคณิตศาสตร์ สถานการณ์ความขัดแย้งเช่น สถานการณ์ดังกล่าวซึ่งผลประโยชน์ของสองฝ่ายหรือมากกว่าที่มีเป้าหมายต่างกันขัดแย้งกัน เกมคือสถานการณ์ความขัดแย้งที่ควบคุมโดยกฎบางอย่าง ซึ่งควรระบุ: ตัวเลือกที่เป็นไปได้สำหรับการกระทำของผู้เข้าร่วม ผลลัพธ์เชิงปริมาณของเกม หรือการชำระเงิน (ชนะ แพ้) ซึ่งชุดการเคลื่อนไหวที่กำหนดนำไปสู่จำนวน ข้อมูลของแต่ละด้านเกี่ยวกับพฤติกรรมของอีกฝ่ายหนึ่ง เกมจับคู่ - เกมที่มีเพียงสองฝ่าย (ผู้เล่นสองคน) เข้าร่วม เกมจับคู่ผลรวมเป็นศูนย์ - เกมจับคู่ที่จำนวนเงินที่จ่ายเป็นศูนย์ เช่น การสูญเสียของผู้เล่นคนหนึ่งจะเท่ากับการได้รับของอีกคนหนึ่ง ขึ้นอยู่กับทัศนคติของผู้เล่นแต่ละคนต่อมูลค่าของฟังก์ชันผลตอบแทน เกมที่จับคู่จะถูกแบ่งย่อย: การสูญเสียของผู้เล่นคนหนึ่งจะเท่ากับการได้รับของอีกคนหนึ่ง เกมที่ไม่เป็นปฏิปักษ์กันคือเกมคู่ที่ผู้เล่นไล่ตามเป้าหมายที่ต่างกัน แต่ไม่ตรงข้ามกันโดยตรง 2 1.2. การเคลื่อนไหว การเคลื่อนไหว - ตัวเลือกของหนึ่งในการกระทำที่กำหนดโดยกฎของเกม การดำเนินการตามตัวเลือกนี้มีการเคลื่อนไหวสองประเภท: การเคลื่อนไหวส่วนบุคคล - + ตัวเลือกที่ใส่ใจของหนึ่งในการกระทำที่กำหนดโดยกฎของเกม + การดำเนินการตามตัวเลือกนี้ การย้ายแบบสุ่ม - การย้ายแบบสุ่มคือตัวเลือกจากจำนวนความเป็นไปได้ที่ไม่ได้ดำเนินการโดยการตัดสินใจของผู้เล่น แต่โดยกลไกการเลือกแบบสุ่ม ด้านล่างเราจะพิจารณาเกมจับคู่ที่มีผลรวมเป็นศูนย์ที่มีเฉพาะการเคลื่อนไหวส่วนบุคคล แต่ละฝ่ายไม่มีข้อมูลเกี่ยวกับพฤติกรรมของอีกฝ่าย 3 1.3. กลยุทธ์ กลยุทธ์ของผู้เล่นคือชุดของกฎที่กำหนดทางเลือกของการกระทำสำหรับการเคลื่อนไหวส่วนบุคคลของผู้เล่นรายนี้ ขึ้นอยู่กับสถานการณ์ที่พัฒนาขึ้นในระหว่างเกม เกมจะแบ่งออกเป็นแบบจำกัดและไม่จำกัด ทั้งนี้ขึ้นอยู่กับจำนวนของกลยุทธ์ที่เป็นไปได้ เกมที่ไม่มีที่สิ้นสุดเป็นเกมที่ผู้เล่นอย่างน้อยหนึ่งคนมีกลยุทธ์จำนวนไม่สิ้นสุด เกมที่จำกัดคือเกมที่ผู้เล่นแต่ละคนมีกลยุทธ์ในจำนวนที่จำกัด จำนวนการเคลื่อนไหวติดต่อกันสำหรับผู้เล่นคนใดคนหนึ่งจะกำหนดการแบ่งเกมเป็นการเคลื่อนไหวครั้งเดียวและการเคลื่อนไหวหลายครั้งหรือตำแหน่ง + ในเกมแบบ one-move ผู้เล่นแต่ละคนเลือกเพียงตัวเลือกเดียวจากตัวเลือกที่เป็นไปได้ แล้วกำหนดผลลัพธ์ของเกม + เกมหลายจังหวะหรือหลายตำแหน่งพัฒนาทันเวลาโดยแสดงถึงลำดับของขั้นตอนต่อเนื่องซึ่งแต่ละขั้นตอนเกิดขึ้นหลังจากการเคลื่อนไหวของผู้เล่นคนใดคนหนึ่งและการเปลี่ยนแปลงที่สอดคล้องกันในสถานการณ์ ในเกมแบบเคลื่อนไหวครั้งเดียว ผู้เล่นแต่ละคนเลือกเพียงตัวเลือกเดียวจากตัวเลือกที่เป็นไปได้ จากนั้นจึงกำหนดผลลัพธ์ของเกม กลยุทธ์ที่ดีที่สุดของผู้เล่นคือกลยุทธ์ที่เมื่อเกมเล่นซ้ำหลายๆ ครั้ง จะให้ผู้เล่นได้รับกำไรเฉลี่ยสูงสุดเท่าที่จะเป็นไปได้ ในทฤษฎีเกม คำแนะนำทั้งหมดจัดทำขึ้นบนพื้นฐานของข้อสันนิษฐานของพฤติกรรมที่สมเหตุสมผลของผู้เล่น การคำนวณผิดและข้อผิดพลาดของผู้เล่นซึ่งหลีกเลี่ยงไม่ได้ในทุกสถานการณ์ความขัดแย้ง ตลอดจนองค์ประกอบของความตื่นเต้นและความเสี่ยงในทฤษฎีเกมจะไม่นำมาพิจารณา 4 1.4. เกมเมทริกซ์ เกมเมทริกซ์คือเกมผลรวมศูนย์จำกัดแบบเคลื่อนที่ครั้งเดียว วิธีที่เป็นไปได้การกระทำ ตามวิธีการดำเนินการที่เลือก (กลยุทธ์) ผลลัพธ์ที่ได้จะถูกกำหนด ลองดูตัวอย่าง ให้มีผู้เล่นสองคน A และ B ซึ่งสามารถเลือกได้หนึ่งคน กลยุทธ์ i-thจากกลยุทธ์ที่เป็นไปได้ A1 , A2 , ...Am และตัวเลือกที่สอง กลยุทธ์ j-th ของกลยุทธ์ที่เป็นไปได้ B1 , B2 , ...Bm เป็นผลให้ผู้เล่นคนแรกชนะ aj และผู้เล่นคนที่สองสูญเสียค่านี้ จากตัวเลข aij เราเขียนเมทริกซ์   a11 a11 · · · a1n  a21 a22 · · · a2n    A = (aij) =  .. .. .. ..   . . . .  am1 am2 ··· amn เมทริกซ์ A = (aij), i = 1, m, j = 1, n เรียกว่าเมทริกซ์ payoff หรือเมทริกซ์ของเกม m × n ในเมทริกซ์นี้ แถวจะมีไว้สำหรับกลยุทธ์ของผู้เล่น A ที่ชนะ (เพิ่มสูงสุด) เสมอ นั่นคือผู้เล่นที่พยายามเพิ่มผลตอบแทนให้ได้สูงสุด คอลัมน์นี้สงวนไว้สำหรับกลยุทธ์ของผู้เล่น B ที่แพ้ นั่นคือผู้เล่นที่ต้องการลดเกณฑ์ประสิทธิภาพ การทำให้เป็นปกติของเกมคือกระบวนการลดเกมตำแหน่งเป็นเกมเมทริกซ์ เกมในรูปแบบปกติเป็นเกมตำแหน่งที่ลดลงเป็นเกมเมทริกซ์ ทางเลือกเดียว (ย้าย) จากวิธีดำเนินการที่เป็นไปได้จำนวนจำกัดในแต่ละขั้นตอนของการพัฒนานี้ สถานการณ์. วิธีแก้ปัญหาเกม - ค้นหากลยุทธ์ที่เหมาะสมที่สุดของผู้เล่นทั้งสองฝ่ายและกำหนดมูลค่าของเกม มูลค่าของเกมคือกำไร (ขาดทุน) ที่คาดหวังของผู้เล่น วิธีแก้ปัญหาของเกมสามารถพบได้ในกลยุทธ์ล้วน - เมื่อผู้เล่นต้องทำตามกลยุทธ์เดียวหรือในกลยุทธ์ผสม เมื่อผู้เล่นต้องใช้กลยุทธ์บริสุทธิ์ตั้งแต่สองกลยุทธ์ขึ้นไปด้วยความน่าจะเป็นที่แน่นอน กรณีหลังนี้เรียกว่าใช้งานอยู่ 5 กลยุทธ์แบบผสมของผู้เล่นคนหนึ่งคือเวกเตอร์ ซึ่งแต่ละองค์ประกอบจะแสดงความถี่ของการใช้กลยุทธ์บริสุทธิ์ที่สอดคล้องกันโดยผู้เล่น ราคาสูงสุดหรือต่ำกว่าของเกม - หมายเลข α = max min aij i j กลยุทธ์สูงสุด (สตริง) - กลยุทธ์ที่ผู้เล่นเลือกเพื่อเพิ่มผลตอบแทนขั้นต่ำให้ได้สูงสุด เห็นได้ชัดว่าเมื่อเลือกกลยุทธ์ maximin ที่ระมัดระวังที่สุด ผู้เล่น A จะรับประกันผลตอบแทนอย่างน้อย α ให้กับตัวเอง (โดยไม่คำนึงถึงพฤติกรรมของฝ่ายตรงข้าม) ค่าสูงสุดหรือค่าสูงสุดของเกม - จำนวน β = min max aij j i กลยุทธ์ขั้นต่ำสุด (คอลัมน์) - กลยุทธ์ที่ผู้เล่นเลือกเพื่อลดการสูญเสียสูงสุด เห็นได้ชัดว่า เมื่อเลือกกลยุทธ์มินิแม็กซ์ที่ระมัดระวังที่สุด ผู้เล่น B จะไม่อนุญาตให้ผู้เล่น A ชนะมากกว่า β ไม่ว่าในกรณีใดๆ ราคาที่ต่ำกว่าของเกมจะไม่เกินราคาที่สูงขึ้นของเกมเสมอ α = max min aij 6 min max aij = β i j j i ทฤษฎีบท 1 (ทฤษฎีบทหลักของทฤษฎีเกมเมทริกซ์) เกมที่จำกัดทุกเกมมีวิธีแก้ปัญหาอย่างน้อยหนึ่งวิธี บางทีอาจเป็นกลยุทธ์แบบผสม 6 2. เกมที่มีจุดอาน การแก้ปัญหาด้วยกลยุทธ์ล้วน ๆ เกมที่มีจุดอานคือเกมที่ α = max min aij = min max aij = β i j j i สำหรับเกมที่มีจุดอาน การหาทางออก ประกอบด้วยการเลือกกลยุทธ์ maximin และ minimax ที่เหมาะสมที่สุด - ความหมายทั่วไปราคาที่ต่ำกว่าและสูงกว่าของเกม α=β=ν 2.1. ตัวอย่าง ตัวอย่างที่ 1 ค้นหาวิธีแก้ปัญหาโดยใช้กลยุทธ์เฉพาะของเกมที่กำหนดโดยเมทริกซ์   8 4 7 A= 6 5 9  7 7 8 วิธีแก้ไข: กำหนดราคาบนและล่างของเกม ในการทำเช่นนี้เราจะหาจำนวนขั้นต่ำของ aj ใน บรรทัด i-thαi = นาที aij j และจำนวนสูงสุดของจำนวน aij in คอลัมน์ j-th βj = max aij i เราเขียนตัวเลข αi (ขั้นต่ำของแถว) ถัดจากเมทริกซ์ผลตอบแทนทางด้านขวาเป็นคอลัมน์เพิ่มเติม เราเขียนตัวเลข βi (คอลัมน์สูงสุด) ใต้เมทริกซ์เป็นแถวเพิ่มเติม: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 ค้นหาจำนวนสูงสุดของ αi α = สูงสุด αi = 7 i และ จำนวนขั้นต่ำ βj β = นาที βj = 7 j α = β - เกมมีจุดอานม้า กลยุทธ์ที่ดีที่สุดสำหรับผู้เล่นคือกลยุทธ์ A3 และสำหรับผู้เล่น B - กลยุทธ์ B2 ต้นทุนสุทธิของเกม ν = 7 ตัวอย่างที่ 2 เมทริกซ์ผลตอบแทนจะได้รับ: 1 1 2   1 2 1 1 2 ค้นหาวิธีแก้ปัญหาของเกมด้วยกลยุทธ์ที่บริสุทธิ์ วิธีแก้ไข: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1 เกมมีจุดอานหกจุด กลยุทธ์ที่เหมาะสมคือ: A1 และ B3 หรือ B4 A3 และ B3 หรือ B4 A4 และ B3 หรือ B4 8 3. วิธีแก้ปัญหาของเกมในกลยุทธ์แบบผสม สำหรับ α ̸= β ในกรณีที่เมื่อเลือกกลยุทธ์ ผู้เล่นทั้งคู่ไม่มีข้อมูลเกี่ยวกับตัวเลือกของอีกฝ่าย เกมมีวิธีแก้ปัญหาในกลยุทธ์แบบผสม SA = (p1 , p2 , ..., pm) เป็นกลยุทธ์แบบผสมของผู้เล่น A ซึ่งกลยุทธ์ A1 , A2 , ..., Am ถูกนำมาใช้ด้วยความน่าจะเป็น ∑ m p1 , p2 , ..., pm , pi = 1, pi > 0, i = 1, m i=1 SB = (q1 , q2 , ..., qn) เป็นกลยุทธ์ผสมของผู้เล่น B ซึ่งกลยุทธ์ B1 , B2 , ..., Bm ใช้กับความน่าจะเป็น ∑ n q1 , q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 = aij p∗i qi∗ j=1 i=1 2 × n, m × 2). หากผู้เล่นคนใดคนหนึ่งใช้กลยุทธ์ผสมที่เหมาะสมที่สุด ผลตอบแทนของเขาจะเท่ากับราคาของเกม ν โดยไม่คำนึงถึงความน่าจะเป็นที่ผู้เล่นคนที่สองจะใช้กลยุทธ์ที่รวมอยู่ในกลยุทธ์ที่เหมาะสมที่สุด (รวมถึงกลยุทธ์บริสุทธิ์) 9 3.1. เกม 2 × 2 พิจารณาเกม 2 × 2 ที่มีเมทริกซ์: () a11 a21 a21 a22 ปล่อยให้เกมไม่มีวิธีแก้ปัญหาด้วยกลยุทธ์ล้วนๆ ให้เราค้นหากลยุทธ์ที่เหมาะสมที่สุด SA∗ และ SB∗ อันดับแรก เรากำหนดกลยุทธ์ SA∗ = (p∗1 , p∗2) ตามทฤษฎีบท หากฝ่าย A ยึดมั่นในกลยุทธ์ ν โดยไม่คำนึงถึงแนวทางการดำเนินการของฝ่าย B ผลตอบแทนจะยังคงเท่ากับราคาของเกม ν ดังนั้น หากฝ่าย A ปฏิบัติตามกลยุทธ์ที่เหมาะสมที่สุด SA∗ = (p∗1 , p∗2) ฝ่าย B ก็สามารถใช้กลยุทธ์ใดๆ ของเขาได้โดยไม่ต้องเปลี่ยนผลตอบแทน จากนั้น เมื่อผู้เล่น B ใช้กลยุทธ์ B1 หรือ B2 เพียงอย่างเดียว ผู้เล่นจะได้รับผลตอบแทนเฉลี่ยเท่ากับราคาของเกม: a11 p∗1 + a21 p∗2 = ν ← สำหรับกลยุทธ์ B1 โปรดทราบว่า p∗1 + p ∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 ค่าของเกม: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 ในทำนองเดียวกัน กลยุทธ์ที่เหมาะสมที่สุดของผู้เล่น B นั้นพบได้: SB∗ = (q1∗ , q2∗) พิจารณาว่า q1∗ + q2∗ = 1: q1∗ = a2 2 − a1 2 a11 + a22 − a12 − a21 q2∗ = a1 1 − a2 1 a11 + a22 − a12 − a21 3.1.1 ตัวอย่าง ตัวอย่างที่ 3 หาคำตอบของเกมด้วยเมทริกซ์ () −1 1 A= 1 −1 10 คำตอบ: เกมไม่มีจุดอาน เนื่องจาก α= -1, β = 1, α ̸= β เรากำลังมองหาวิธีแก้ปัญหาในกลยุทธ์ผสม การใช้สูตรสำหรับ p∗ และ q ∗ เราได้ p∗1 = p∗2 = 0.5 และ q1∗ = q2∗ = 0.5, ν = 0 ดังนั้น SA∗ = (0.5, 0.5) SB∗ = (0.5, 0.5) ตัวอย่างที่ 4 หาคำตอบของเกมด้วยเมทริกซ์ () 2 5 A= 6 4 คำตอบ: เกมไม่มีจุดอาน เนื่องจาก α= 4, β = 5, α ̸= β เรากำลังมองหาวิธีแก้ปัญหาในกลยุทธ์ผสม โดยสูตรสำหรับ p∗ และ q 0.8) 11 3.1.2. การตีความทางเรขาคณิต เกม 2×2 สามารถตีความทางเรขาคณิตอย่างง่ายได้ ให้เรานำหน่วยของแกน abscissa ไปยังแต่ละจุดที่เราเชื่อมโยงกลยุทธ์แบบผสม S = (p1 , p2) = (p1 , 1 − p1) p2 , กลยุทธ์ A2 - ระยะทางไปยังปลายด้านซ้าย .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ ด้านขวาสุดของส่วน (x = 1) - กลยุทธ์ A2 ในตอนท้าย ของส่วน แกนสองเส้นตั้งฉากกับแกน abscissa จะถูกเรียกคืน: แกน I - I - ผลตอบแทนถูกเลื่อนออกไปด้วยกลยุทธ์ A1 แกน II - II - ผลตอบแทนถูกเลื่อนออกไปด้วยกลยุทธ์ A2 ให้ผู้เล่น B ใช้กลยุทธ์ B1 ; มันให้แกน I − I และ II − II ตามลำดับ จุดที่มีพิกัด a11 และ a21 เราลากเส้น B1 − B1′ ผ่านจุดเหล่านี้ สำหรับกลยุทธ์แบบผสมใดๆ SA = (p1 , p2) ผลตอบแทนของผู้เล่นจะพิจารณาจากจุด N บนเส้น B1 − B1′ ซึ่งตรงกับจุด SA บนแกน x ที่แบ่งส่วนตาม p2: p1 เห็นได้ชัดว่า เส้นตรง B2 − B2′ ซึ่งกำหนดผลตอบแทนสำหรับกลยุทธ์ B2 สามารถสร้างได้ในลักษณะเดียวกันทุกประการ 12 .y .I .I ฉัน .B2 .N .a21 .B2′ ก 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ จำเป็นต้องค้นหากลยุทธ์ที่เหมาะสมที่สุด SA∗ เช่น ดังนั้นผลตอบแทนขั้นต่ำของผู้เล่น A (ที่มีพฤติกรรมแย่ที่สุดของผู้เล่น B สำหรับเขา) จะกลายเป็นค่าสูงสุด สำหรับสิ่งนี้ ขอบเขตล่างของผลตอบแทนของผู้เล่น A ถูกสร้างขึ้นสำหรับกลยุทธ์ B1 , B2 เช่น เส้นขาด B1 N B2′ ;. บนขอบเขตนี้จะอยู่ที่ผลตอบแทนขั้นต่ำของผู้เล่น A สำหรับกลยุทธ์แบบผสมใดๆ ของเขา จุด N ซึ่งผลตอบแทนนี้ถึงสูงสุดและกำหนดทางออกและราคาของเกม .y .I .I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 เอ∗ ส . 1∗ P พิกัดของจุด N ไม่ใช่อะไรนอกจากค่าของเกม ν อักษรย่อของมันเท่ากับ ∗2 และระยะทางไปยังจุดสิ้นสุดด้านขวาของส่วนเท่ากับ ∗1 เช่น ระยะทางจากจุด SA∗ ไปยังจุดสิ้นสุดของส่วนเท่ากับความน่าจะเป็น ∗2 และ ∗1 ของกลยุทธ์ A2 และ A1 ของกลยุทธ์ผสมที่เหมาะสมที่สุดของผู้เล่น A ในกรณีนี้ วิธีแก้ปัญหาของเกมถูกกำหนดโดย จุดตัดของกลยุทธ์ B1 และ B2 ด้านล่างแสดงกรณีที่กลยุทธ์ที่ดีที่สุดของผู้เล่นคือกลยุทธ์บริสุทธิ์ A2 ที่นี่กลยุทธ์ A2 (สำหรับกลยุทธ์ใด ๆ ของฝ่ายตรงข้าม) ทำกำไรได้มากกว่ากลยุทธ์ A1 , 13 .y .y .I .I I I .I I. I .B2′ 1′ บี .B1′ บี 2 .B2′ บี 2 .B1 .v = a21 .B1 .v = a21 ฉัน ฉัน ฉัน ฉัน ฉัน .ฉัน .x .I . .x 2∗ พี . A∗ S = A2 . 2∗ พี . A∗ S = A2 ทางด้านขวาจะแสดงกรณีที่ผู้เล่น B มีกลยุทธ์ที่ไม่เกิดประโยชน์โดยเจตนา การตีความทางเรขาคณิตทำให้สามารถเห็นภาพราคาที่ต่ำกว่าของเกม α และตัวบน β .y .I .I I .B2 .B1′ .N .B1 . B2′ .β = a21 .α = a22 .I ฉัน .I .∗ .x .P2 เอ∗ ส . 1∗ P บนกราฟเดียวกัน เรายังสามารถให้การตีความทางเรขาคณิตของกลยุทธ์ที่เหมาะสมที่สุดของผู้เล่น B เป็นเรื่องง่ายที่จะเห็นว่าส่วนแบ่ง q1∗ ของกลยุทธ์ B1 ของกลยุทธ์ผสมที่เหมาะสมที่สุด SB∗ = (q1∗ , q2∗) เท่ากับอัตราส่วนของความยาวของส่วน KB2 ต่อผลรวมของความยาวของส่วน KB1 และ KB2 บนแกน I - I: .y .I .I I .B2 . B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 เอ∗ ส . 1∗ P 14 KB2 q1∗ = KB2 + KB1 หรือ LB2′ q1∗ = LB2′ + LB1′ ค่าสูงสุดของขอบเขตล่างของผลตอบแทนพิจารณาค่าต่ำสุดของขอบเขตบน .y .I .I .A2 .A′1 .N .A1 .A′2 .I ฉัน .I .x .q2∗ . B∗ S .q1∗ 15 3.2. เกม 2 × n และ m × 2 คำตอบของเกม 2 × n และ m × 2 ขึ้นอยู่กับทฤษฎีบทต่อไปนี้ ทฤษฎีบท 3. เกมจำกัดใดๆ m × n มีวิธีแก้ปัญหาที่จำนวนของกลยุทธ์ที่ใช้งานอยู่ของแต่ละด้านไม่เกินจำนวนที่น้อยที่สุดของ m และ n ตามทฤษฎีบทนี้ เกม 2 × n มักจะมีวิธีแก้ปัญหาที่ผู้เล่นแต่ละคนมีกลยุทธ์ที่ใช้งานอยู่ไม่เกินสองกลยุทธ์ เราต้องค้นหากลยุทธ์เหล่านี้เท่านั้นและเกม 2 × n จะกลายเป็นเกม 2 × 2 ซึ่งแก้ไขได้เบื้องต้น การค้นหากลยุทธ์ที่ใช้งานสามารถทำได้แบบกราฟิก: 1) การสร้างการตีความแบบกราฟิก; 2) กำหนดขีด จำกัด ล่างของการได้รับ 3) สองกลยุทธ์ของผู้เล่นคนที่สองนั้นแตกต่างกันที่ขอบเขตการจ่ายเงินที่ต่ำกว่า ซึ่งสอดคล้องกับเส้นสองเส้นที่ตัดกันที่จุดที่มีพิกัดสูงสุด (หากมีเส้นมากกว่าสองเส้นตัดกัน คู่ใดก็ได้) - กลยุทธ์เหล่านี้ทำงานอยู่ กลยุทธ์ของผู้เล่น B ดังนั้นเกม 2 × n จะลดลงเป็นเกม 2 × 2 เกม m × 2 ยังสามารถแก้ไขได้ด้วยความแตกต่างที่ไม่ได้สร้างขอบเขตการจ่ายเงินสูงสุดและไม่ใช่ค่าสูงสุด . ตัวอย่างที่ 5 หาทางออกให้กับเกม () 7 9 8 A= 10 6 9 วิธีแก้ปัญหา: โดยใช้วิธีการทางเรขาคณิต เราเลือกกลยุทธ์ที่ใช้งานอยู่ เส้น B1 − B1′ , B2 − B2′ และ B3 − B3′ สอดคล้องกับกลยุทธ์ B1 , B2 , B3 เส้นแบ่ง B1 N B2 คือขอบเขตล่างของผลตอบแทนของผู้เล่น เกมมีวิธีแก้ปัญหา S∗A = (23 , 31); S∗B = (0.5; 0.5; 0); v = 8.16 .y .I .I ฉัน 1' บีบี 2 .B3′ .N .B3 .B1 .B2′ .I ฉัน .I . .x 2∗ พี . เอ∗ ส . 1∗ P 17 เกมดัชนี, 2 ย้าย, 3 2 × 2, 10 ส่วนตัว, 3 2 × 2, 9 สุ่ม, 3 รูปทรงเรขาคณิต, 12 มูลค่าเกมบริสุทธิ์, 7 ตัวอย่าง, 10 2 × n, 9, 16 ม. × 2, 9 , 16 แบบไม่มีที่สิ้นสุด, 4 รูปแบบปกติ, 5 แบบจำกัด, 4 แบบหลายทาง, 4 แบบทางเดียว, 4 เมทริกซ์, 5 แบบคู่, 2 แบบผลรวมศูนย์, 2 แบบตรงข้าม, 2 แบบไม่เป็นปฏิปักษ์, 2 วิธีแก้ปัญหา, 5 แบบผสม, 5, 9 กลยุทธ์บริสุทธิ์ . 5 ทฤษฎีเกม 2 18

หากมีหลายฝ่ายที่ขัดแย้งกัน (บุคคล) ซึ่งแต่ละฝ่ายจะตัดสินใจบางอย่างโดยกำหนดกฎเกณฑ์ที่กำหนด และแต่ละฝ่ายรู้สถานะสุดท้ายของสถานการณ์ความขัดแย้งด้วยการจ่ายเงินที่กำหนดไว้ล่วงหน้าสำหรับแต่ละฝ่าย จากนั้นเราจะพูดว่า มีเกม

งานของทฤษฎีเกมคือการเลือกแนวพฤติกรรมดังกล่าวสำหรับผู้เล่นที่กำหนด การเบี่ยงเบนจากที่สามารถลดผลตอบแทนของเขาได้เท่านั้น

คำจำกัดความบางอย่างของเกม

การประเมินเชิงปริมาณของผลลัพธ์ของเกมเรียกว่าการจ่ายเงิน

คู่ (สองคน) เรียกว่าเกมผลรวมเป็นศูนย์หากผลรวมของการชำระเงินเป็นศูนย์ เช่น หากการสูญเสียของผู้เล่นคนใดคนหนึ่งเท่ากับการได้รับของอีกคนหนึ่ง

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

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

เกมกำหนดเมทริกซ์ กซึ่งมี มเส้นและ นคอลัมน์เรียกว่าเกมคู่จำกัดมิติ ม* น;

ที่ไหน ฉัน=
เป็นกลยุทธ์ของผู้เล่นคนแรกที่มีกลยุทธ์ m; เจ=เป็นกลยุทธ์ของผู้เล่นคนที่สองที่มี n กลยุทธ์ ไอเจคือผลตอบแทนของผู้เล่นคนแรก ฉันกลยุทธ์ -th เมื่อใช้โดยวินาที เจ-th กลยุทธ์ (หรืออะไรเหมือนกัน แพ้ที่สอง เจกลยุทธ์ที่เมื่อใช้ครั้งแรก ฉันไทย);

ก =   ไอเจ คือเมทริกซ์ผลตอบแทนของเกม

1.1 เล่นด้วยกลยุทธ์ที่บริสุทธิ์

ราคาที่ต่ำกว่าของเกม (สำหรับผู้เล่นคนแรก)

 = สูงสุด (นาที ไอเจ). (1.2)

ฉัน เจ

ราคาเกมบน (สำหรับผู้เล่นคนที่สอง):

= นาที (สูงสุด ไอเจ) . (1.3)

เจ ฉัน

ถ้า  =  เกมนี้เรียกว่าจุดอานม้า (1.4) หรือเกมที่มีกลยุทธ์ล้วนๆ ในนั้น วี =  =  เรียกว่าเกมที่ทรงคุณค่า ( วี- ราคาของเกม).

ตัวอย่าง.กำหนดเมทริกซ์ผลตอบแทนสำหรับเกม 2 คน A. กำหนดกลยุทธ์ที่เหมาะสมที่สุดสำหรับผู้เล่นแต่ละคนและราคาของเกม:

(1.4)

สูงสุด 10 9 12 6

ฉัน

นาที 6

เจ

เป็นกลยุทธ์ของผู้เล่นคนแรก (แถว)

กลยุทธ์ของผู้เล่นคนที่สอง (คอลัมน์)

- ราคาของเกม

ดังนั้นเกมจึงมีจุดอาน กลยุทธ์ เจ = 4 เป็นกลยุทธ์ที่ดีที่สุดสำหรับผู้เล่นคนที่สอง ฉัน=2 - สำหรับอันแรก เรามีเกมที่มีกลยุทธ์ที่บริสุทธิ์

1.2 เกมกลยุทธ์ผสม

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

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

เอ็กซ์= (เอ็กซ์ 1 …เอ็กซ์ ฉัน …เอ็กซ์ ม) เป็นกลยุทธ์ผสมของผู้เล่นคนแรก

ที่= (ที่ 1 ...ที่ เจ ...ที่ น) เป็นกลยุทธ์ผสมของผู้เล่นคนที่สอง

xฉัน , ย เจ– ความถี่สัมพัทธ์ (ความน่าจะเป็น) ของผู้เล่นที่ใช้กลยุทธ์ของพวกเขา

เงื่อนไขสำหรับการใช้กลยุทธ์แบบผสม

. (1.5)

ถ้า เอ็กซ์* = (เอ็กซ์ 1 * ….เอ็กซ์ฉัน * ... เอ็กซ์ ม*) เป็นกลยุทธ์ที่เหมาะสมที่สุดที่ผู้เล่นคนแรกเลือก; วาย* = (ที่ 1 * …ที่เจ * ... ที่ น*) เป็นกลยุทธ์ที่เหมาะสมที่สุดที่ผู้เล่นคนที่สองเลือก จากนั้นตัวเลขคือราคาของเกม

(1.6)

เพื่อให้หมายเลข วีคือราคาของเกมและ เอ็กซ์* และ ที่* - กลยุทธ์ที่ดีที่สุด จำเป็นและเพียงพอที่ความไม่เท่าเทียมกัน

(1.7)

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

การลดปัญหาทฤษฎีเกมไปสู่ปัญหาการเขียนโปรแกรมเชิงเส้น

ตัวอย่าง. ค้นหาวิธีแก้ปัญหาของเกมที่กำหนดโดยเมทริกซ์ผลตอบแทน ก.

เอ = (1.8)

ย 1 ย 2 ย 3

สารละลาย:

ให้เราสร้างปัญหาการเขียนโปรแกรมเชิงเส้นคู่คู่

สำหรับผู้เล่นคนแรก

(1.9)

ที่ 1 +ที่ 2 +ที่ 3 = 1 (1.10)

ปลดปล่อยตัวเองจากตัวแปร วี(ราคาของเกม) เราแบ่งด้านซ้ายและขวาของนิพจน์ (1.9), (1.10) โดย วี. ยอมรับแล้ว ที่ เจ /วีสำหรับตัวแปรใหม่ ซี ฉัน, เราได้รับ ระบบใหม่ข้อ จำกัด (1.11) และ ฟังก์ชั่นวัตถุประสงค์ (1.12)

(1.11)

. (1.12)

ในทำนองเดียวกัน เราได้รับโมเดลเกมสำหรับผู้เล่นคนที่สอง:

(1.13)

เอ็กซ์ 1 +เอ็กซ์ 2 +เอ็กซ์ 3 = 1 . (1.14)

ย่อโมเดล (1.13), (1.14) ให้อยู่ในรูปไม่มีตัวแปร วี, เราได้รับ

(1.15)

, (1.16)

ที่ไหน
.

หากเราจำเป็นต้องกำหนดกลยุทธ์เชิงพฤติกรรมของผู้เล่นคนแรก เช่น ความถี่สัมพัทธ์ของการใช้กลยุทธ์ของเขา ( เอ็กซ์ 1 ….เอ็กซ์ ฉัน …เอ็กซ์ ม) เราจะใช้โมเดลของผู้เล่นคนที่สองเพราะ ตัวแปรเหล่านี้อยู่ในโมเดลผลตอบแทนของเขา (1.13), (1.14)

เราลด (1.15), (1.16) เป็นรูปแบบบัญญัติ

(1.17)

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

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

จากประวัติศาสตร์ของทฤษฎีเกม

ประวัติทฤษฎีเกม เมื่อระเบียบวินัยอิสระเริ่มขึ้นในปี 1944 เมื่อ John von Neumann และ Oscar Morgenstern ตีพิมพ์หนังสือ "Theory of Games and Economic Behavior" ("Theory of Games and Economic Behavior") แม้ว่าจะเคยพบตัวอย่างทฤษฎีเกมมาก่อน: ตำราทัลมุดของชาวบาบิโลนเกี่ยวกับการแบ่งทรัพย์สินของสามีที่เสียชีวิตระหว่างภรรยาของเขา, เกมไพ่ในศตวรรษที่ 18, การพัฒนาทฤษฎีหมากรุกในต้นศตวรรษที่ 20, การพิสูจน์ ของทฤษฎีบทมินิแมกซ์ของจอห์น ฟอน นอยมันน์คนเดียวกันในปี พ.ศ. 2471 หากไม่มีทฤษฎีเกมก็จะไม่มี

ในปี 1950 เมลวิน เดรสเชอร์และเมอรีล ฟลัดจาก แรนด์ คอร์ปอเรชั่นจอห์น แนช คนแรกที่ใช้ปัญหาภาวะที่กลืนไม่เข้าคายไม่ออกของนักโทษ ในงานของเขาเกี่ยวกับสภาวะสมดุลในเกมที่มีผู้เล่นสองคน ได้พัฒนาแนวคิดเรื่องสมดุลของแนช

Reinhard Salten ในปี 1965 ได้ตีพิมพ์หนังสือ "Oligopoly processing in game theory on demand" ("Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit") ซึ่งการประยุกต์ใช้ทฤษฎีเกมในเศรษฐศาสตร์ได้รับแรงผลักดันใหม่ ก้าวไปข้างหน้าในวิวัฒนาการของทฤษฎีเกมเกี่ยวข้องกับงานของ John Maynard Smith "Evolutionary Stable Strategy" ("Evolutionary Stable Strategy", 1974) ภาวะที่กลืนไม่เข้าคายไม่ออกของนักโทษได้รับความนิยมในหนังสือ The Evolution of Cooperation ของ Robert Axelrod ซึ่งตีพิมพ์ในปี 1984 ในปี 1994 John Nash, John Harsanyi และ Reinhard Salten ได้รับรางวัลโนเบลสาขาทฤษฎีเกม

ทฤษฎีเกมในชีวิตและธุรกิจ

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

ในบางแง่มุม ชื่อ "ทฤษฎีเกม" เป็นสิ่งที่น่าเสียดาย เนื่องจากเป็นการบ่งชี้ว่าทฤษฎีเกมเกี่ยวข้องเฉพาะกับ คุณค่าทางสังคมการปะทะกันที่เกิดขึ้นในเกมห้องนั่งเล่น แต่ทฤษฏีนี้ยังมีความหมายที่กว้างกว่ามาก

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

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

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

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

แบบจำลองทางคณิตศาสตร์ในทฤษฎีเกมและการทำให้เป็นทางการของปัญหา

ดังที่เราได้กล่าวไปแล้ว เกมคือ แบบจำลองทางคณิตศาสตร์สถานการณ์ความขัดแย้ง และต้องการส่วนประกอบดังนี้

1. ผู้มีส่วนได้เสีย;
2. การกระทำที่เป็นไปได้ในแต่ละด้าน
3. ผลประโยชน์ของคู่สัญญา

ฝ่ายที่สนใจในเกมจะเรียกว่าผู้เล่น แต่ละคนสามารถดำเนินการได้อย่างน้อยสองการกระทำ (หากผู้เล่นมีเพียงหนึ่งการกระทำ แสดงว่าเขาไม่ได้มีส่วนร่วมในเกมจริง ๆ เนื่องจากเป็นที่ทราบล่วงหน้าว่าเขาจะทำอะไร) ผลของเกมเรียกว่าชนะ .

สถานการณ์ความขัดแย้งที่แท้จริงไม่ได้เกิดขึ้นเสมอไป แต่เกม (ในแนวคิดของทฤษฎีเกม) - ดำเนินไปพร้อมกันเสมอ กฎบางอย่าง ซึ่งกำหนดว่า:

1. ตัวเลือกผู้เล่น;
2. จำนวนข้อมูลที่ผู้เล่นแต่ละคนมีเกี่ยวกับพฤติกรรมของพันธมิตร
3. ผลตอบแทนที่การกระทำแต่ละชุดนำไปสู่

ตัวอย่างของเกมที่เป็นทางการ เช่น ฟุตบอล เกมไพ่ หมากรุก

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

เกมมีลักษณะที่ไม่แน่นอนของผลลัพธ์ . สาเหตุของความไม่แน่นอนสามารถแบ่งออกเป็นกลุ่มต่อไปนี้:

1. combinatorial (ในหมากรุก);
2. อิทธิพลของปัจจัยสุ่ม (เช่นในเกม "หัวหรือก้อย", ลูกเต๋า, เกมไพ่);
3. เชิงกลยุทธ์ (ผู้เล่นไม่รู้ว่าฝ่ายตรงข้ามจะทำอะไร)

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

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

การจัดประเภทเกม

1. จำแนกตามจำนวนผู้เล่น (เกมสำหรับสองคนขึ้นไป) เกมสองคนเป็นศูนย์กลางของทฤษฎีเกมทั้งหมด แนวคิดพื้นฐานของทฤษฎีเกมสำหรับเกมที่มีผู้เล่นสองคนเป็นการสรุปแนวคิดที่สำคัญมากเกี่ยวกับความสมดุล ซึ่งปรากฏโดยธรรมชาติในเกมที่มีผู้เล่นสองคน สำหรับเกม นบุคคล ดังนั้นส่วนหนึ่งของทฤษฎีเกมอุทิศให้กับเกมที่ห้ามไม่ให้ผู้เล่นร่วมมือกัน ในอีกส่วนหนึ่งของทฤษฎีเกม นบุคคลจะสันนิษฐานว่าผู้เล่นสามารถร่วมมือกันเพื่อผลประโยชน์ร่วมกัน (ดูต่อไปในย่อหน้านี้เกี่ยวกับเกมที่ไม่ให้ความร่วมมือและร่วมมือกัน)
2. จำแนกตามจำนวนผู้เล่นและกลยุทธ์ของพวกเขา (จำนวนของกลยุทธ์อย่างน้อยสอง อาจเป็นอนันต์)
3. จำแนกตามจำนวนข้อมูล เกี่ยวกับการเคลื่อนไหวที่ผ่านมา: เกมที่มีข้อมูลครบถ้วนและข้อมูลไม่ครบถ้วน ให้มีผู้เล่น 1 - ผู้ซื้อและผู้เล่น 2 - ผู้ขาย หากผู้เล่น 1 ไม่มีข้อมูลที่ครบถ้วนเกี่ยวกับการกระทำของผู้เล่น 2 ดังนั้นผู้เล่น 1 อาจไม่สามารถแยกแยะระหว่างสองทางเลือกที่เขาต้องเลือกได้ ตัวอย่างเช่น การเลือกระหว่างสองประเภทของผลิตภัณฑ์บางอย่างและไม่ทราบว่าผลิตภัณฑ์นั้นตามลักษณะบางอย่าง กแย่กว่าสินค้า ขผู้เล่น 1 อาจไม่เห็นความแตกต่างระหว่างทางเลือก
4. การจำแนกตามหลักการของการแบ่งเงินรางวัล : สหกรณ์, แนวร่วมในแง่หนึ่งและไม่ร่วมมือ, ไม่ร่วมมือในอีกด้านหนึ่ง. ใน เกมที่ไม่ให้ความร่วมมือ หรือมิฉะนั้น - เกมที่ไม่ให้ความร่วมมือ ผู้เล่นเลือกกลยุทธ์พร้อมกันโดยไม่รู้ว่าผู้เล่นคนที่สองจะเลือกกลยุทธ์ใด ไม่สามารถสื่อสารระหว่างผู้เล่นได้ ใน เกมสหกรณ์ หรือมิฉะนั้น - เกมพันธมิตร ผู้เล่นสามารถสร้างพันธมิตรและดำเนินการร่วมกันเพื่อเพิ่มชัยชนะ
5. เกมผลรวมศูนย์ จำกัด สองคน หรือเกมที่เป็นปรปักษ์กันคือ เกมกลยุทธ์พร้อมข้อมูลที่ครบถ้วนเกี่ยวกับบุคคลที่มีส่วนได้ส่วนเสีย เกมที่เป็นปฏิปักษ์กันคือ เกมเมทริกซ์ .

ตัวอย่างคลาสสิกจากทฤษฎีเกมคือภาวะที่กลืนไม่เข้าคายไม่ออกของนักโทษ

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

หากภารกิจเชิงกลยุทธ์นี้ถูกกำหนดขึ้นในแง่ของข้อสรุป ก็จะสรุปได้ดังต่อไปนี้:

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

ตัวอย่างการใช้วิธีการทางคณิตศาสตร์ของทฤษฎีเกม

ตอนนี้เราหันไปพิจารณาวิธีแก้ปัญหาสำหรับตัวอย่างเกมประเภททั่วไปซึ่งมีวิธีการตรวจสอบและการแก้ปัญหาในทฤษฎีเกม

ตัวอย่างของเกมที่ไม่ร่วมมือ (ไม่ร่วมมือ) อย่างเป็นทางการของคนสองคน

ในย่อหน้าที่แล้ว เราได้พิจารณาตัวอย่างเกมที่ไม่ร่วมมือ (ไม่ให้ความร่วมมือ) (ภาวะที่กลืนไม่เข้าคายไม่ออกของนักโทษ) มาเสริมทักษะของเรากันเถอะ พล็อตคลาสสิกที่ได้รับแรงบันดาลใจจาก The Adventures of Sherlock Holmes ของ Arthur Conan Doyle ก็เหมาะสำหรับเรื่องนี้เช่นกัน แน่นอนว่าเราสามารถคัดค้านได้: ตัวอย่างไม่ได้มาจากชีวิต แต่มาจากวรรณกรรม แต่โคนันดอยล์ไม่ได้พิสูจน์ตัวเองว่าเป็นนักเขียนนิยายวิทยาศาสตร์! คลาสสิกเพราะงานเสร็จสมบูรณ์โดย Oscar Morgenstern ซึ่งเราได้สร้างไว้แล้ว - หนึ่งในผู้ก่อตั้งทฤษฎีเกม

ตัวอย่างที่ 1ข้อความที่ตัดตอนมาโดยย่อจากหนึ่งใน The Adventures of Sherlock Holmes จะได้รับ ตามแนวคิดที่รู้จักกันดีของทฤษฎีเกม ให้สร้างแบบจำลองของสถานการณ์ความขัดแย้งและเขียนเกมอย่างเป็นทางการ

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

สารละลาย. วีรบุรุษของ Conan Doyle ถือได้ว่าเป็นผู้เข้าร่วมในเกมนั่นคือผู้เล่น ในการกำจัดของผู้เล่นแต่ละคน ฉัน (ฉัน=1,2) สองกลยุทธ์บริสุทธิ์:

• ลงที่ Dover (กลยุทธ์ สi1 ( ฉัน=1,2) );
• ลงที่สถานีระหว่างทาง (กลยุทธ์ สไอทู ( ฉัน=1,2) )

ขึ้นอยู่กับว่ากลยุทธ์ใดในสองกลยุทธ์ที่ผู้เล่นแต่ละคนเลือก การผสมผสานกลยุทธ์พิเศษจะถูกสร้างขึ้นเป็นคู่ ส = (ส1 , ส 2 ) .

ชุดค่าผสมแต่ละชุดสามารถเชื่อมโยงกับเหตุการณ์ - ผลของการพยายามฆ่าเชอร์ล็อก โฮล์มส์ โดยศาสตราจารย์โมริอาร์ตี เราสร้างเมทริกซ์ของเกมนี้ด้วยเหตุการณ์ที่เป็นไปได้

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

ตัวอย่างของพิธีการและการแก้ปัญหาของเกมสหกรณ์ (แนวร่วม) นคน

ณ จุดนี้ภาคปฏิบัติซึ่งก็คือการแก้ปัญหาตัวอย่างจะนำหน้าด้วยภาคทฤษฎีซึ่งเราจะทำความคุ้นเคยกับแนวคิดของทฤษฎีเกมสำหรับการแก้ปัญหาเกมแบบร่วมมือ (ไม่ร่วมมือ) สำหรับภารกิจนี้ ทฤษฎีเกมแนะนำ:

• ฟังก์ชั่นที่เป็นลักษณะเฉพาะ (พูดง่าย ๆ มันสะท้อนถึงคุณค่าของผลประโยชน์จากการเข้าร่วมกับผู้เล่นในแนวร่วม)
• แนวคิดของการเพิ่ม (คุณสมบัติของปริมาณซึ่งประกอบด้วยความจริงที่ว่ามูลค่าของปริมาณที่สอดคล้องกับวัตถุทั้งหมดเท่ากับผลรวมของค่าของปริมาณที่สอดคล้องกับส่วนต่าง ๆ ในการแบ่งพาร์ติชันของวัตถุในระดับหนึ่ง เป็นส่วน) และ superadditivity (ค่าของปริมาณที่สอดคล้องกับวัตถุทั้งหมดมากกว่าผลรวมของค่าของปริมาณที่สอดคล้องกับส่วนต่าง ๆ ของมัน) ของฟังก์ชันลักษณะเฉพาะ

การเพิ่มพิเศษของฟังก์ชั่นลักษณะเฉพาะบ่งชี้ว่าพันธมิตรมีประโยชน์สำหรับผู้เล่น เนื่องจากในกรณีนี้ ผลตอบแทนของพันธมิตรจะเพิ่มขึ้นตามจำนวนผู้เล่น

ในการทำให้เกมเป็นทางการ เราจำเป็นต้องแนะนำสัญกรณ์ที่เป็นทางการสำหรับแนวคิดข้างต้น

สำหรับเกม นหมายถึงชุดของผู้เล่นทั้งหมดเป็น เอ็น= (1,2,...,n) เซตย่อยที่ไม่ว่างใดๆ ของเซต เอ็นแสดงว่า ต(รวมทั้งตนเอง เอ็นและเซตย่อยทั้งหมดที่ประกอบด้วยองค์ประกอบเดียว) มีกิจกรรมบนเว็บไซต์ เซตและการดำเนินการกับเซตซึ่งจะเปิดในหน้าต่างใหม่เมื่อคุณคลิกที่ลิงก์

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

สำหรับสองแนวร่วมของชุดย่อยที่ไม่ว่างเปล่า ต1 และ ต2 การเพิ่มฟังก์ชั่นลักษณะของเกมสหกรณ์ (แนวร่วม) เขียนได้ดังนี้:

และความเหนือชั้นเป็นดังนี้:

ตัวอย่างที่ 2นักเรียน 3 คนของโรงเรียนดนตรีแห่งหนึ่งได้รับเงินพิเศษจากชมรมต่างๆ พวกเขาได้รับเงินจากผู้เข้าชมชมรม พิจารณาว่าการร่วมมือกันสร้างผลกำไรหรือไม่ (ถ้าเป็นเช่นนั้นภายใต้เงื่อนไขใด) โดยใช้แนวคิดของทฤษฎีเกมเพื่อแก้ปัญหาเกมแบบร่วมมือ นบุคคล โดยมีข้อมูลเบื้องต้นดังต่อไปนี้

โดยเฉลี่ยแล้ว รายได้ต่อคืนของพวกเขาคือ:

• นักไวโอลินมี 600 หน่วย
• มือกีตาร์มี 700 หน่วย
• นักร้องมี 900 หน่วย

ในความพยายามที่จะเพิ่มรายได้ นักเรียนได้สร้างกลุ่มต่างๆ เป็นเวลาหลายเดือน ผลการวิจัยพบว่าการรวมทีมกันสามารถเพิ่มรายได้ในช่วงเย็นดังนี้:

• นักไวโอลิน + นักกีตาร์ได้รับ 1,500 หน่วย
• นักไวโอลิน + นักร้องได้รับ 1,800 หน่วย
• นักกีตาร์ + นักร้องได้รับ 1,900 หน่วย
• นักไวโอลิน + นักกีตาร์ + นักร้อง ได้ 3,000 หน่วย

สารละลาย. ในตัวอย่างนี้ จำนวนผู้เข้าร่วมในเกม น= 3 ดังนั้นโดเมนของฟังก์ชันลักษณะเฉพาะของเกมจึงประกอบด้วย 2³ = 8 ชุดย่อยที่เป็นไปได้ของชุดของผู้เล่นทั้งหมด รายชื่อพันธมิตรที่เป็นไปได้ทั้งหมด ต:

• การรวมตัวกันขององค์ประกอบหนึ่งซึ่งแต่ละองค์ประกอบประกอบด้วยผู้เล่นหนึ่งคน - นักดนตรี: ต{1} , ต{2} , ต{3} ;
• การรวมกันของสององค์ประกอบ: ต{1,2} , ต{1,3} , ต{2,3} ;
• แนวร่วมของ สามองค์ประกอบ: ต{1,2,3} .

เรากำหนดหมายเลขซีเรียลให้กับผู้เล่นแต่ละคน:

• นักไวโอลิน - ผู้เล่นคนที่ 1;
• นักกีตาร์ - ผู้เล่นคนที่ 2;
• นักร้องคือผู้เล่นคนที่ 3

ตามข้อมูลปัญหา เรากำหนดลักษณะเฉพาะของเกม โวลต์:

v(T(1)) = 600 ; v(T(2)) = 700 ; v(T(3)) = 900 ; ค่าของฟังก์ชันลักษณะเฉพาะเหล่านี้จะพิจารณาจากผลตอบแทนของผู้เล่นคนแรก คนที่สอง และคนที่สาม ตามลำดับ เมื่อพวกเขาไม่ได้รวมกันเป็นพันธมิตร

v(T(1,2)) = 1,500 ; v(T(1,3)) = 1800 ; v(T(2,3)) = 1900 ; ค่าของฟังก์ชั่นลักษณะเฉพาะเหล่านี้ถูกกำหนดโดยรายได้ของผู้เล่นแต่ละคู่ที่รวมกันเป็นพันธมิตร

v(T(1,2,3)) = 3000 ; ค่าของฟังก์ชันคุณลักษณะนี้ถูกกำหนดโดยรายได้เฉลี่ยในกรณีที่ผู้เล่นรวมกันเป็นแฝดสาม

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

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