เกมเมทริกซ์: ตัวอย่างการแก้ปัญหา เกมที่เป็นปฏิปักษ์พร้อมกลยุทธ์ต่อเนื่อง b) ไม่เสมอไป

การแนะนำ

สถานการณ์ความขัดแย้งที่แท้จริงนำไปสู่เกมประเภทต่างๆ เกมมีความแตกต่างกันในหลายวิธี: ตามจำนวนผู้เล่นที่เข้าร่วม, ตามจำนวนผู้เล่นที่เป็นไปได้, ตามจำนวนกลยุทธ์ที่เป็นไปได้, โดยลักษณะของความสัมพันธ์ระหว่างผู้เล่น, โดยลักษณะของการชนะ, ตามประเภทของ ฟังก์ชั่นการชนะ ตามจำนวนการเคลื่อนไหว โดยลักษณะของการให้ข้อมูลของผู้เล่น ฯลฯ .d. พิจารณาประเภทของเกมตามแผนก:

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

· ตามลักษณะของการชนะเกมด้วย ผลรวมเป็นศูนย์(ทุนรวมของผู้เล่นไม่เปลี่ยนแปลง แต่จะถูกแจกจ่ายระหว่างผู้เล่นขึ้นอยู่กับผลลัพธ์ที่ได้) และเกมที่มี ผลรวมที่ไม่ใช่ศูนย์.

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

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

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

วิธีอื่นในการแบ่งเกมก็เป็นไปได้เช่นกัน ตอนนี้เรากลับมาที่หัวข้อการวิจัยโดยตรงนั่นคือทฤษฎีเกม ขั้นแรก เรามากำหนดแนวคิดนี้กันก่อน

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

วัตถุประสงค์ของทฤษฎีคือ:

1) พฤติกรรมที่ดีที่สุดในเกม

2) การศึกษาคุณสมบัติของพฤติกรรมที่เหมาะสมที่สุด

3) การกำหนดเงื่อนไขที่การใช้งานมีความหมาย (คำถามเกี่ยวกับการดำรงอยู่ เอกลักษณ์ และสำหรับเกมไดนามิก คำถามเกี่ยวกับความสอดคล้องเล็กน้อย)

4) การสร้างวิธีการเชิงตัวเลขเพื่อค้นหาพฤติกรรมที่เหมาะสมที่สุด

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

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

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

ทฤษฎีเกมคณิตศาสตร์เริ่มต้นด้วยการวิเคราะห์กีฬา ไพ่ และเกมอื่นๆ ว่ากันว่าเป็นผู้ค้นพบทฤษฎีเกมนักคณิตศาสตร์ชาวอเมริกันผู้โดดเด่นแห่งศตวรรษที่ 20 John von Neumann เกิดแนวคิดสำหรับทฤษฎีของเขาขณะดูเกมโป๊กเกอร์ นี่คือที่มาของชื่อ "ทฤษฎีเกม"

มาเริ่มสำรวจหัวข้อนี้ด้วย การวิเคราะห์ย้อนหลังการพัฒนาทฤษฎีเกมให้เราพิจารณาประวัติและพัฒนาการของประเด็นทฤษฎีเกมกัน โดยทั่วไปแล้ว "แผนภูมิต้นไม้ครอบครัว" จะแสดงเป็นต้นไม้ในแง่ของทฤษฎีกราฟ ซึ่งการแตกแขนงเกิดขึ้นจาก "ราก" บางส่วน The Pedigree of Game Theory เป็นหนังสือของ J. von Neumann และ O. Morgenstern ดังนั้นหลักสูตรทางประวัติศาสตร์ของการพัฒนาทฤษฎีเกมในฐานะวินัยทางคณิตศาสตร์จึงแบ่งออกเป็นสามขั้นตอนโดยธรรมชาติ:

ขั้นแรก- ก่อนการตีพิมพ์เอกสารโดย J. von Neumann และ O. Morgenstern เรียกได้ว่าเป็น "พรีโมโนแกรม" เลยก็ได้ ในขั้นตอนนี้ เกมยังคงทำหน้าที่เป็นการแข่งขันเฉพาะ ซึ่งอธิบายตามกฎกติกาในแง่ที่มีความหมาย ในตอนท้ายเท่านั้น J. von Neumann จึงพัฒนาแนวคิดของเกมในฐานะแบบจำลองทั่วไปของความขัดแย้งเชิงนามธรรม ผลลัพธ์ของขั้นตอนนี้คือการสะสมผลลัพธ์ทางคณิตศาสตร์เฉพาะจำนวนหนึ่งและแม้แต่หลักการส่วนบุคคลของทฤษฎีเกมในอนาคต

ระยะที่สองเป็นเอกสารของ J. von Neumann และ

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

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

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

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

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

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

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

ส่งผลงานดีๆ ของคุณในฐานความรู้ได้ง่ายๆ ใช้แบบฟอร์มด้านล่าง

นักศึกษา นักศึกษาระดับบัณฑิตศึกษา นักวิทยาศาสตร์รุ่นเยาว์ ที่ใช้ฐานความรู้ในการศึกษาและการทำงาน จะรู้สึกขอบคุณเป็นอย่างยิ่ง

การแนะนำ

1. ส่วนทางทฤษฎี

1.3 ลำดับเกม 2x2

1.4 วิธีพีชคณิต

1.5 วิธีการแบบกราฟิก

1.6 เกม 2xn หรือ mx2

1.7 การแก้เกมโดยใช้วิธีเมทริกซ์

2. ส่วนปฏิบัติ

2.2 เกม 2xn และ mx2

2.3 วิธีเมทริกซ์

2.4 วิธีสีน้ำตาล

การวิเคราะห์ผลลัพธ์

การแนะนำ

เกมผลรวมเป็นศูนย์คือเกมที่มีผลรวมเป็นศูนย์ เกมผลรวมเป็นศูนย์เป็นเกมที่ไม่ร่วมมือกันซึ่งเกี่ยวข้องกับผู้เล่นสองคนซึ่งมีผลตอบแทนตรงกันข้าม

อย่างเป็นทางการ เกมที่เป็นปฏิปักษ์สามารถแสดงได้ด้วยทรอยกา โดยที่ X และ Y คือชุดกลยุทธ์ของผู้เล่นคนแรกและคนที่สอง ตามลำดับ F คือฟังก์ชันผลตอบแทนของผู้เล่นคนแรก โดยกำหนดคู่กลยุทธ์แต่ละคู่ (x,y) โดยที่จำนวนจริงสอดคล้องกับอรรถประโยชน์ของ ผู้เล่นคนแรกในการดำเนินการตามสถานการณ์ที่กำหนด

เนื่องจากความสนใจของผู้เล่นตรงกันข้าม ฟังก์ชัน F พร้อมกันจึงแสดงถึงการสูญเสียผู้เล่นคนที่สอง

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

1. ส่วนทางทฤษฎี

1.1 คำจำกัดความและข้อกำหนดพื้นฐานของเกม

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

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

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

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

โดยเฉพาะอย่างยิ่งเกมที่มีผลรวมเป็นศูนย์ระหว่างผู้เล่นสองคนเรียกว่าการเป็นปรปักษ์เนื่องจากเป้าหมายของผู้เล่นในเกมนั้นตรงกันข้ามโดยตรง: การได้เปรียบของผู้เล่นคนหนึ่งเกิดขึ้นโดยเสียค่าใช้จ่ายในการสูญเสียอีกคนหนึ่งเท่านั้น

1.1.1 คำจำกัดความ ตัวอย่าง และวิธีแก้ปัญหาของเกมเมทริกซ์ในกลยุทธ์ล้วนๆ

เกมเมทริกซ์ผลรวมเป็นศูนย์ที่มีผู้เล่นสองคนถือได้ว่าเป็นเกมที่มีผู้เล่นสองคนที่เป็นนามธรรมดังต่อไปนี้

ผู้เล่นคนแรกมีกลยุทธ์ t i = 1, 2, …, t ส่วนคนที่สองมี n กลยุทธ์ j = 1, 2, …, p แต่ละคู่ของกลยุทธ์ (i, j) เชื่อมโยงกับตัวเลข a ij ซึ่งแสดงถึง ผลตอบแทนของผู้เล่นคนแรกเนื่องจากผู้เล่นคนที่สองหากผู้เล่นคนแรกใช้กลยุทธ์ i-th ของเขา และผู้เล่นคนที่สองใช้กลยุทธ์ j-th ของเขา

ผู้เล่นแต่ละคนทำการเคลื่อนไหวหนึ่งครั้ง: ผู้เล่นคนแรกเลือกกลยุทธ์ i-th ของเขา (i = 1, 2,..., m) คนที่สองเลือกกลยุทธ์ j-th ของเขา (j = 1, 2,..., n) หลังจากนั้นผู้เล่นคนแรกจะได้รับเงินรางวัล ij โดยเสียค่าใช้จ่ายของผู้เล่นคนที่สอง (ถ้า ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

แต่ละกลยุทธ์ของผู้เล่น i = 1, 2,…, t; j = 1, 2,…, n มักเรียกว่ากลยุทธ์ล้วนๆ

ต่อจากนี้ไปเกมเมทริกซ์ผลรวมเป็นศูนย์สำหรับผู้เล่นสองคนจะเรียกง่ายๆ ว่าเกมเมทริกซ์ แน่นอนว่าเกมเมทริกซ์เป็นของเกมที่เป็นปฏิปักษ์ จากคำจำกัดความ การกำหนดเมทริกซ์เกมก็เพียงพอที่จะระบุเมทริกซ์ A = (a ij) ของลำดับการจ่ายเงินรางวัลของผู้เล่นคนแรก

หากเราพิจารณาเมทริกซ์ผลตอบแทน

จากนั้นการเล่นเกมแต่ละเกมของเกมเมทริกซ์ที่มีเมทริกซ์ A จะลดลงเป็นตัวเลือกโดยผู้เล่นคนแรกของแถวที่ i และผู้เล่นคนที่สองของคอลัมน์ j-th และผู้เล่นคนแรกที่ได้รับ (ค่าใช้จ่ายของวินาทีที่สอง ) เงินรางวัลที่อยู่ในเมทริกซ์ A ที่จุดตัดของแถวที่ i และคอลัมน์ที่ j

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

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

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

(ผม = 1, 2,..., ม.) (1.2)

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

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

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

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

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

คำนิยาม. หากในเกมที่มีเมทริกซ์ A ราคาสุทธิต่ำกว่าและบนของเกมตรงกัน เช่น b = c แสดงว่าเกมนี้มีจุดอานม้าในกลยุทธ์ล้วนๆ และราคาสุทธิของเกม:

n = ข = โวลต์ (1.6)

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

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

โดยที่ i, j เป็นกลยุทธ์ล้วนๆ ของผู้เล่นคนแรกและคนที่สอง ตามลำดับ (i 0 , j 0) เป็นกลยุทธ์ที่ก่อให้เกิดจุดอานม้า ด้านล่างนี้เราจะแสดงให้เห็นว่าคำจำกัดความของจุดอานนั้นเทียบเท่ากับเงื่อนไข (1.8)

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

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

ทฤษฎีบท 1 ให้ f (x, y) เป็นฟังก์ชันจริงของตัวแปรสองตัว x A และ y B และมีอยู่จริง

แล้วข = ค

การพิสูจน์. จากคำจำกัดความของค่าต่ำสุดและค่าสูงสุดจะเป็นดังนี้

เนื่องจากทางด้านซ้ายของ (1.11) x นั้นไม่แน่นอน

ทางด้านขวาของความไม่เท่าเทียมกัน (1.12) y จึงเป็นสิ่งที่ไม่แน่นอน

Q.E.D.

โดยเฉพาะอย่างยิ่ง เมทริกซ์ () เป็นกรณีพิเศษของฟังก์ชัน f (x, y) กล่าวคือ ถ้าเราใส่ x = i, y = j, = f (x, y) จากนั้นจากทฤษฎีบท 1 เราจะได้ว่าค่าสุทธิล่าง ราคาไม่เกินราคาสุทธิบนของการเล่นในเกมเมทริกซ์

คำนิยาม. ให้ f (x, y) เป็นฟังก์ชันจริงของตัวแปรสองตัว x A และ y B จุด (x 0, y 0) เรียกว่าจุดอานสำหรับฟังก์ชัน f (x, y) หากสมการต่อไปนี้เป็นไปตามสมการ

ฉ (x, y 0) ฉ (x 0, y 0)ฉ (x 0, y) (1.14)

สำหรับ x A และ y B ใดๆ

1.2 กลยุทธ์แบบผสมที่เหมาะสมที่สุดและคุณสมบัติของพวกเขา

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

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

ดังนั้น หากผู้เล่นคนแรกมีกลยุทธ์ m ล้วนๆ 1, 2, … i, … m ดังนั้นกลยุทธ์แบบผสมของเขา x จะเป็นชุดตัวเลข x = (x 1, x 2, ..., x i,…, x m ) น่าพอใจ ความสัมพันธ์

x ผม 0 (ผม = 1, 2, ... , เสื้อ), = 1. (1.15)

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

ใช่ เจ 0 (เจ = 1, 2, ... , n) = 1. (1.16)

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

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

คำนิยาม. ผลตอบแทนเฉลี่ยของผู้เล่นคนแรกในเกมเมทริกซ์ที่มีเมทริกซ์ A แสดงเป็นความคาดหวังทางคณิตศาสตร์ของผลตอบแทนของเขา

อี (A, x, y) = (1.20)

แน่นอนว่าผลตอบแทนเฉลี่ยของผู้เล่นคนแรกคือฟังก์ชันของตัวแปร x และ y สองชุด ผู้เล่นคนแรกมีเป้าหมายโดยการเปลี่ยนกลยุทธ์แบบผสม x เพื่อเพิ่มผลตอบแทนเฉลี่ย E (A, x, y) ให้สูงสุด และผู้เล่นคนที่สองพยายามทำให้ E (A, x, y) น้อยที่สุดโดยใช้กลยุทธ์แบบผสมของเขา เช่น ในการแก้เกมจำเป็นต้องค้นหา x, y ซึ่งบรรลุราคาสูงสุดของเกม

1.3 เกมลำดับที่ 22

เกมเมทริกซ์ลำดับที่ 22 จะได้รับจากเมทริกซ์ผลตอบแทนต่อไปนี้สำหรับผู้เล่นคนแรก:

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

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

ให้เราแสดงด้วย x = (x 1 , x 2), y = (y 1 , y 2) กลยุทธ์แบบผสมของผู้เล่นคนแรกและคนที่สองตามลำดับ โปรดจำไว้ว่า x 1 หมายถึงความน่าจะเป็นของผู้เล่นคนแรกที่ใช้กลยุทธ์แรกของเขา และ x 2 = 1 - x 1 คือความน่าจะเป็นที่เขาจะใช้กลยุทธ์ที่สอง ในทำนองเดียวกันสำหรับผู้เล่นคนที่สอง: 1 คือความน่าจะเป็นที่เขาจะใช้กลยุทธ์แรก 2 = 1 - 1 คือความน่าจะเป็นที่เขาจะใช้กลยุทธ์ที่สอง

ตามข้อพิสูจน์ของทฤษฎีบท เพื่อให้กลยุทธ์แบบผสม x และ y เหมาะสมที่สุด จำเป็นและเพียงพอสำหรับความสัมพันธ์ที่ไม่เป็นลบ x 1, x 2, y 1, y 2:

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

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

0<<1, 0<< 1,

0< <1, 01. (1.25)

สมมติว่าอสมการทั้งสองจาก (1.22) เข้มงวด

จากนั้นตามทฤษฎีบท y 1 = y 2 = 0 ซึ่งขัดแย้งกับเงื่อนไข (1.25)

ได้รับการพิสูจน์ในทำนองเดียวกันว่าอสมการทั้งสองจาก (1.23) ไม่สามารถเป็นอสมการเข้มงวดได้

ตอนนี้เราสมมติว่าหนึ่งในอสมการ (1.22) สามารถเข้มงวดได้ เช่น อย่างแรก

ซึ่งหมายความว่าตามทฤษฎีบท y 1 = 0, y 2 = 1 ดังนั้นจาก (1.23) เราได้

หากอสมการทั้งสอง (1.24) เข้มงวด ดังนั้นตามทฤษฎีบท x 1 = x 2 = 0 ซึ่งขัดแย้งกับ (1.25) ถ้า 12 ถึง 22 แสดงว่าหนึ่งในอสมการ (1.27) เป็นแบบเข้มงวด และอีกอันคือความเท่าเทียมกัน ยิ่งไปกว่านั้น ความเท่าเทียมกันจะคงอยู่สำหรับองค์ประกอบที่ใหญ่กว่าของ 12 และ 22 กล่าวคือ อสมการหนึ่งจาก (1.27) จะต้องเข้มงวด เช่น 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

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

ดังนั้น หากเกมเมทริกซ์ลำดับที่ 22 ไม่มีจุดอาน กลยุทธ์แบบผสมที่เหมาะสมที่สุดของผู้เล่นและราคาของเกมสามารถกำหนดได้โดยการแก้ระบบสมการ (1.24) เป็นที่ยอมรับกันว่าหากในเกมเมทริกซ์ลำดับ 2x2 ผู้เล่นคนใดคนหนึ่งมีกลยุทธ์บริสุทธิ์ที่เหมาะสมที่สุด ผู้เล่นอีกคนก็มีกลยุทธ์บริสุทธิ์ที่เหมาะสมที่สุดเช่นกัน

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

1.4 วิธีพีชคณิต

มีสองกรณีที่เป็นไปได้ในการแก้ปัญหาโดยใช้วิธีพีชคณิต:

1. เมทริกซ์มีจุดอาน

2. เมทริกซ์ไม่มีจุดอาน

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

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

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

เงินรางวัลในแต่ละกรณีจะต้องเท่ากับราคาของเกม V ในกรณีนี้ ความสัมพันธ์ต่อไปนี้ถูกต้อง:

สามารถสร้างระบบสมการที่คล้ายกับ (2.5), (2.6) เพื่อกลยุทธ์ที่ดีที่สุดของผู้เล่นคนที่สอง:

โดยคำนึงถึงเงื่อนไขการทำให้เป็นมาตรฐาน:

มาแก้สมการ (1.37) - (1.41) ร่วมกับสิ่งที่ไม่ทราบ คุณจะแก้ได้ครั้งละ 3 ข้อเท่านั้น: แยกกัน (1.36), (1.38), (1.40) และ (1.37), ( 1.39), (1.41) จากผลลัพธ์ของโซลูชันที่เราได้รับ:

1.5 วิธีการแบบกราฟิก

วิธีแก้ปัญหาโดยประมาณสำหรับเกม 22 สามารถรับได้ค่อนข้างง่ายโดยใช้วิธีกราฟิก สาระสำคัญของมันมีดังนี้:

รูปที่ 1.1 - การค้นหาส่วนของความยาวหน่วย

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

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

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

รูปที่ 1.2 - การค้นหาราคาของเกม

อย่างไรก็ตาม ควรสังเกตว่าการก่อสร้างนี้ดำเนินการสำหรับผู้เล่นคนแรก ที่นี่ความยาวของส่วนจะเท่ากับราคาเกม V

เส้น 1N2 เรียกว่าขีดจำกัดการชนะที่ต่ำกว่า ที่นี่คุณจะเห็นได้อย่างชัดเจนว่าจุด N สอดคล้องกับจำนวนเงินสูงสุดของการรับประกันชัยชนะของผู้เล่นคนแรก

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

หรือบนแกน II-II

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

รูปที่ 1.3 - การกำหนดกลยุทธ์ของผู้เล่นคนที่สอง

เส้นนี้ 1N2 คือขีดจำกัดสูงสุดของการสูญเสีย จุด N สอดคล้องกับการสูญเสียขั้นต่ำที่เป็นไปได้ของผู้เล่นคนที่สอง และจะกำหนดกลยุทธ์

ขึ้นอยู่กับค่าเฉพาะของสัมประสิทธิ์เมทริกซ์ กราฟอาจมีรูปแบบที่แตกต่างกัน เช่น:

รูปที่ 1.4 - กำหนดกลยุทธ์ที่ดีที่สุดของผู้เล่นคนแรก

ในสถานการณ์เช่นนี้ กลยุทธ์ที่ดีที่สุดของผู้เล่นคนแรกนั้นบริสุทธิ์:

1.6 เกม 2n หรือ m2

ในเกมลำดับที่ 2n ผู้เล่นคนแรกมี 2 กลยุทธ์ล้วนๆ และผู้เล่นคนที่สองไม่มีกลยุทธ์ล้วนๆ กล่าวคือ เมทริกซ์ผลตอบแทนของผู้เล่นคนแรกมีรูปแบบ:

หากเกมดังกล่าวมีจุดอานม้า ก็เป็นเรื่องง่ายที่จะค้นหาและรับวิธีแก้ไข

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

เนื่องจากเกมไม่มีจุดอาน ความไม่เท่าเทียมกัน (1.54) จึงถูกแทนที่ด้วยความไม่เท่าเทียมกัน

ในการแก้ปัญหาระบบ (1.56), (1.55), (1.53) ขอแนะนำให้ใช้วิธีแบบกราฟิก เพื่อจุดประสงค์นี้ เราแนะนำสัญลักษณ์ทางด้านซ้ายของอสมการ (1.53)

แบบจำลองทางคณิตศาสตร์เกมเมทริกซ์

หรือเราได้รับจาก (1.55) และทำการแปลงอย่างง่าย

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

ตามนิพจน์ แต่ละค่า j=1, 2, …, n สอดคล้องกับเส้นตรงในระบบพิกัดสี่เหลี่ยม

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

ขอบเขตล่างของชุดข้อจำกัดอยู่ที่ไหน ในรูปที่ 1.6 กราฟของฟังก์ชันจะแสดงเป็นเส้นหนา

โพสต์บน http://www.allbest.ru/

รูปที่ 1.6 - กราฟฟังก์ชัน

เป้าหมายของผู้เล่นคนแรกคือการเพิ่มเงินรางวัลให้สูงสุดผ่านการเลือก เช่น คำนวณ

ในรูปที่ 1.6 จุดหมายถึงค่าสูงสุดที่ได้รับ ราคาของเกมเป็นเพราะ:

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

ตอนนี้เราสามารถแก้ระบบสมการได้แล้ว

และกำหนดค่าของและ (ตามภาพกราฟิกจะถูกกำหนดโดยประมาณ) จากนั้นให้นำค่าทั้งหมดสำหรับค่า j ที่ไม่ได้เป็นจุดมาแก้ระบบสมการ (1.56) ตามตัวอย่างที่แสดงในรูปที่ 1.6 จะได้ระบบดังต่อไปนี้

และส่วนที่เหลือ ระบบนี้สามารถแก้ไขได้โดยการลาดเอียง หากสำหรับ j=j 0 กลยุทธ์ของผู้เล่นคนที่สองก่อให้เกิดจุด M 0 จากนั้นค่าสูงสุดของขอบเขตล่างของชุดข้อ จำกัด จะแสดงโดยส่วนที่ขนานกับ แกน ในกรณีนี้ ผู้เล่นคนแรกมีค่าที่เหมาะสมที่สุดมากมายและราคาของเกม กรณีนี้แสดงไว้ในรูปที่ 1.7 โดยที่ส่วน MN แสดงถึงขีดจำกัดบน ค่าที่เหมาะสมที่สุดอยู่ภายในขีดจำกัด ผู้เล่นคนที่สอง มีกลยุทธ์ที่เหมาะสมที่สุด j=j 0

เกมเมทริกซ์ลำดับ m2 สามารถแก้ไขได้โดยใช้วิธีกราฟิก เมทริกซ์ผลตอบแทนของผู้เล่นคนแรกในกรณีนี้มีรูปแบบ

กลยุทธ์แบบผสมของผู้เล่นคนแรกและคนที่สอง ตามลำดับ ได้รับการกำหนดในลักษณะเดียวกันในกรณีของเกมลำดับ 2n ปล่อยให้ค่าตั้งแต่ 0 ถึง 1 ถูกพล็อตไปตามแกนนอน และมูลค่าของการชนะโดยเฉลี่ย) ของผู้เล่นคนแรกตามแนวแกนตั้ง ภายใต้เงื่อนไขที่ผู้เล่นคนแรกใช้กลยุทธ์ i-th ของเขาเอง (i=1, 2, ..., m) ที่สอง - กลยุทธ์แบบผสมของเขา (y 1, 1- y 1) =y ตัวอย่างเช่น เมื่อ m=4 เป็นกราฟ) สามารถแสดงได้ดังแสดงในรูปที่ 1.7

รูปที่ 1.7 - กราฟฟังก์ชัน)

ผู้เล่นคนแรกพยายามเพิ่มผลตอบแทนโดยเฉลี่ยให้สูงสุด ดังนั้นเขาจึงพยายามค้นหา

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

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

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

ดังนั้น การแก้ปัญหาระบบ (1.69) เราจึงได้กลยุทธ์ที่ดีที่สุดของผู้เล่นคนที่สองและราคาของเกม เราค้นหากลยุทธ์แบบผสมที่เหมาะสมที่สุดสำหรับผู้เล่นคนแรกโดยการแก้ระบบสมการต่อไปนี้:

1.7 วิธีเมทริกซ์สำหรับการแก้เกม

การกำหนด:

เมทริกซ์ย่อยกำลังสองใดๆ ของเมทริกซ์ลำดับ

เมทริกซ์(1);

เมทริกซ์ถูกย้ายไปที่;

เมทริกซ์ที่อยู่ติดกับ B;

- (1) เมทริกซ์ที่ได้รับจาก X โดยการลบองค์ประกอบที่สอดคล้องกับแถวที่ถูกลบเมื่อได้รับ

- (1) เมทริกซ์ที่ได้จากการลบองค์ประกอบที่สอดคล้องกับแถวที่ถูกลบเมื่อได้รับ

อัลกอริทึม:

1. เลือกเมทริกซ์ย่อยรูปสี่เหลี่ยมจัตุรัสของเมทริกซ์ลำดับ () แล้วคำนวณ

2. ถ้ามีค่าเป็นหรือ เราจะละทิ้งเมทริกซ์ที่พบแล้วลองใช้เมทริกซ์ตัวอื่น

3. ถ้า (), () เราจะคำนวณและสร้าง X และจากและบวกศูนย์ในตำแหน่งที่เหมาะสม

ตรวจสอบว่าความไม่เท่าเทียมกันเป็นที่พอใจหรือไม่

สำหรับทุกคน (1.75)

และความไม่เท่าเทียมกัน

สำหรับทุกคน (1.76)

หากความสัมพันธ์อันใดอันหนึ่งไม่พอใจ เราก็ลองอันอื่น หากความสัมพันธ์ทั้งหมดถูกต้อง ให้ X และผลเฉลยที่จำเป็น

1.8 วิธีการประมาณราคาเกมอย่างต่อเนื่อง

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

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

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

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

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

2. ส่วนปฏิบัติ

ทั้งคู่ตัดสินใจว่าจะไปเดินเล่นที่ไหนและใช้เวลาให้เกิดประโยชน์กับทั้งคู่

หญิงสาวตัดสินใจไปเดินเล่นในสวนสาธารณะเพื่อรับอากาศบริสุทธิ์และในตอนเย็นไปดูหนังที่โรงภาพยนตร์ที่ใกล้ที่สุด

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

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

ตารางที่ 1. เมทริกซ์ผลตอบแทน

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

โพสต์บน http://www.allbest.ru/

2.2 เกม 2xn และ mx2

ปัญหาที่ 1(2xn)

มีการปลูกพืชธัญพืชสองชนิดสำหรับสภาพอากาศแห้งและเปียก

และสภาวะทางธรรมชาติถือได้ว่าเป็น แห้ง เปียก ปานกลาง

โพสต์บน http://www.allbest.ru/

ค่าสูงสุดของ M() ได้มาที่จุด M ซึ่งเกิดจากการตัดกันของเส้นตรงที่สอดคล้องกับ j=1, j"=2 จากข้อมูลนี้ เราถือว่า:

ปัญหาที่ 2(mx2)

ชายและหญิงกำลังพิจารณาทางเลือกว่าจะไปที่ไหนในช่วงสุดสัปดาห์

ทางเลือกของสถานที่พักผ่อนอาจถือได้ว่าเป็น: สวนสาธารณะ โรงภาพยนตร์ ร้านอาหาร

โพสต์บน http://www.allbest.ru/

ค่าสูงสุดของ M() ได้มาที่จุด E ซึ่งเกิดจากการตัดกันของเส้นตรงที่สอดคล้องกับ j=1, j"=2 จากข้อมูลนี้ เราถือว่า:

ในการกำหนดค่าของ v จะต้องแก้สมการต่อไปนี้:

2.5 วิธีเมทริกซ์

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

ร้านอาหารกลางมีบริการดังต่อไปนี้:

1) การบริการลูกค้าที่มีราคาแพงกว่าและมีคุณภาพสูง

2) อาหารที่เน้นอาหารฝรั่งเศส

ร้านอาหารแห่งที่ 2 ให้บริการ:

1) บริการราคาไม่แพงและมีคุณภาพสูง

2) เมนูผสมผสานอาหารที่มีชื่อเสียงของโลก

3) โปรโมชั่นและส่วนลดอย่างต่อเนื่อง

4) จัดส่งและรับคำสั่งซื้อสำหรับการจัดส่งถึงบ้าน

ตามภารกิจ กำไรสำหรับหนึ่งวันระหว่างร้านอาหารสองร้านจะแบ่งดังนี้:

ตารางที่ 2. เมทริกซ์ผลตอบแทน

การแก้เกมของแบบฟอร์มโดยใช้วิธีเมทริกซ์:

มีเมทริกซ์ย่อยอยู่ 6 ตัวและ:

พิจารณาเมทริกซ์:

x 1 = ? 0, x 2 = ? 0

เนื่องจาก x 2 =< 0, то мы отбрасываем.

ตอนนี้เรามาพิจารณาเมทริกซ์กัน:

x 1 = ? 0, x 2 = ? 0

ราคาเกม.

อัตราส่วนนี้ขัดแย้งกับข้อกำหนดจึงไม่เหมาะสม

ตอนนี้เรามาพิจารณาเมทริกซ์กัน:

x 1 = , x 2 = ? 0,

ย 1 =< 0, y 2 = ? 0.

เนื่องจาก y 1 =< 0, то мы отбрасываем и.

ตอนนี้เรามาพิจารณาเมทริกซ์กัน:

x 1 = , x 2 = 0 เนื่องจาก x 2 = 0 จากนั้นเราทิ้ง และ

ตอนนี้เรามาพิจารณาเมทริกซ์กัน:

x 1 = , x 2 = ? 0 เนื่องจาก x 1 = 0 เราจึงทิ้ง และ

ตอนนี้เรามาพิจารณาเมทริกซ์กัน:

x 1 = , x 2 =, y 1 = , y 2 = จากนั้นเราจะดำเนินการต่อไป:

x 1 = , x 2 =, y 1 = , y 2 = หรือ

ราคาเกม.

ตอนนี้มีการตรวจสอบความสัมพันธ์พื้นฐานแล้ว:

โพสต์บน http://www.allbest.ru/

คำตอบ: x 1 = , x 2 =, y 1 = , y 2 = , y 3 =0, y 4 =0,

วิธีสีน้ำตาล

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

ปล่อยให้เกมถูกกำหนดโดยเมทริกซ์ผลตอบแทนต่อไปนี้:

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

2 ถ้าเขาใช้กลยุทธ์ที่ 1 ของเขา

3 ถ้าเขาใช้กลยุทธ์ที่ 3 ของเขา

ค่าที่ได้รับสรุปไว้ในตารางที่ 1

ตารางที่ 3. กลยุทธ์ของผู้เล่นคนที่สอง

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

1 ถ้าเขาใช้กลยุทธ์ที่ 1 ของเขา

3 ถ้าเขาใช้กลยุทธ์ที่ 2 ของเขา

4 ถ้าเขาใช้กลยุทธ์ที่ 3 ของเขา

ตารางที่ 4. กลยุทธ์ผู้เล่นคนแรก

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

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

ในตาราง 5 ในคอลัมน์กลยุทธ์ของผู้เล่นคนที่สองในบรรทัดที่สองจะมีหมายเลข 1 ซึ่งบ่งชี้ว่าในเกมที่สองจะเป็นประโยชน์สำหรับผู้เล่นคนที่สองที่จะใช้กลยุทธ์ที่ 1 ของเขา ในคอลัมน์คือค่าเฉลี่ยสูงสุดที่ชนะ 3 ของผู้เล่นคนแรกที่เขาได้รับในเกมแรก คอลัมน์ w ประกอบด้วยการสูญเสียเฉลี่ยน้อยที่สุด 1 แต้มที่ผู้เล่นคนที่สองได้รับในเกมแรก คอลัมน์ v มีค่าเฉลี่ยเลขคณิต v = (u + w) - นั่นคือมูลค่าโดยประมาณของราคาเกมที่ได้รับอันเป็นผลมาจากการแพ้หนึ่งเกมของเกม หากผู้เล่นคนที่สองใช้กลยุทธ์ที่ 1 ของเขา คนแรกจะได้รับ 3, 1, 2 ตามลำดับ โดยกลยุทธ์ที่ 1, 2, 3 ของเขา และชัยชนะรวมของผู้เล่นคนแรกสำหรับทั้งสองเกมจะเป็น:

2 + 3=5 ด้วยกลยุทธ์ที่ 1 ของเขา

3 + 1=4 ด้วยกลยุทธ์ที่ 2 ของเขา

3 + 2=5 ด้วยกลยุทธ์ที่ 3 ของเขา

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

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

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

1 + 3=4 ด้วยกลยุทธ์ที่ 1 ของเขา

3 + 2=5 ด้วยกลยุทธ์ที่ 2 ของเขา

4 + 3=7 ด้วยกลยุทธ์ที่ 3 ของเขา

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

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

ดังนั้น จะได้ตารางที่ 4 ต่อไปนี้สำหรับสองเกม

ตารางที่ 6. การชนะและแพ้รวมของผู้เล่นหลังจากเล่นสองเกม

ในแถวที่สามของตารางที่ 6 ในคอลัมน์กลยุทธ์ของผู้เล่นคนที่สองจะมีหมายเลข 1 ซึ่งบ่งชี้ว่าในเกมที่สาม ผู้เล่นคนที่สองต้องใช้กลยุทธ์ที่ 1 ของเขา ในกรณีนี้ ผู้เล่นคนแรกจะชนะ 3, 1, 2 โดยใช้กลยุทธ์ที่ 1, 2, 3 ของเขาตามลำดับ และชัยชนะรวมของเขาในสามเกมจะเป็น:

3 + 5 = 8 ด้วยกลยุทธ์ที่ 1 ของเขา

1 +4 = 5 ด้วยกลยุทธ์ที่ 2 ของเขา

2 + 5 = 7 ด้วยกลยุทธ์ที่ 3 ของเขา

การชนะรวมของผู้เล่นคนแรกเหล่านี้จะถูกบันทึกไว้ในแถวที่สามของตาราง 6 และคอลัมน์ที่สอดคล้องกับกลยุทธ์ของเขา 1, 2, 3 เนื่องจากผู้เล่นคนแรกจะได้รับชัยชนะรวมสูงสุด 8 คนด้วยกลยุทธ์ที่ 1 ดังนั้นอันดับที่ 1 จะถูกเลือก ตามนั้น

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

3 + 4=7 ด้วยกลยุทธ์ที่ 1 ของเขา

2 + 5=7 ด้วยกลยุทธ์ที่ 2 ของเขา

3 + 7 = 10 ด้วยกลยุทธ์ที่ 3 ของเขา

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

ในตาราง 6 ในบรรทัดที่สามในคอลัมน์และบันทึกการชนะรวมที่ใหญ่ที่สุดของผู้เล่นคนแรกในสามเกม หารด้วยจำนวนเกม เช่น; ในคอลัมน์ที่มีการเสียรวมน้อยที่สุดของผู้เล่นคนที่สองในสามเกม หารด้วยจำนวนเกม คือ คอลัมน์ v มีค่าเฉลี่ยเลขคณิต

ดังนั้นเราจึงได้โต๊ะ 7 สำหรับสามเกม

ตารางที่ 7. การชนะและแพ้รวมของผู้เล่นหลังจากเล่นสามเกม

ตารางที่ 8. ตารางสุดท้ายหลังจากเล่นไปยี่สิบเกม

จากโต๊ะ 7 และ 8 จะเห็นได้ว่าใน 20 เกมที่แพ้ กลยุทธ์ 1, 2, 3 สำหรับผู้เล่นคนแรกเกิดขึ้น 12, 3, 5 ครั้งตามลำดับ ดังนั้น ความถี่สัมพัทธ์จึงเท่ากันตามลำดับ กลยุทธ์ 1, 2, 3 สำหรับผู้เล่นคนที่สองเกิดขึ้น 7, 11,2 ครั้งตามลำดับ ดังนั้นความถี่สัมพัทธ์จึงเท่ากันตามลำดับ ราคาโดยประมาณของเกม การประมาณนี้ค่อนข้างดี

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

การวิเคราะห์ผลลัพธ์

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

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

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

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

สำหรับวิธีการของ Brown มีการร่างภารกิจขึ้นมาโดยคำนึงถึงสหภาพแรงงานและฝ่ายบริหารของ บริษัท หน้าที่ของพวกเขาคือจัดหาอาหารให้กับคนงาน หากผู้เล่นทั้งสองใช้กลยุทธ์ที่เหมาะสม อาหารต่อคนจะเป็น 2.45,000 รูเบิล

รายชื่อแหล่งที่มาที่ใช้

1) วิลิซอฟ วี.ยา. บันทึกการบรรยาย "ทฤษฎีเกมและการตัดสินใจทางสถิติ" - สาขา - "Voskhod" MAI 2522. 146 น.

2) ครุเชฟสกี้ เอ.วี. ทฤษฎีเกม - เคียฟ: โรงเรียนวิชชา, 2520 - 216 น.

3) Churchmen U., Akof R., Arnof L., การวิจัยการดำเนินงานเบื้องต้น - ม.: วิทยาศาสตร์. พ.ศ. 2510 - 488 น.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0 %B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

โพสต์บน Allbest.ru

เอกสารที่คล้ายกัน

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

งานหลักสูตรเพิ่มเมื่อ 05/05/2010


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

การนำเสนอเพิ่มเมื่อ 10/23/2013


คำจำกัดความพื้นฐานของทฤษฎีเกมบิเมทริกซ์ ตัวอย่างเกม Bimatrix "Student-Teacher" กลยุทธ์แบบผสมในเกมบิเมทริกซ์ ค้นหา "สถานการณ์สมดุล" เกมบิเมทริกซ์ 2x2 และสูตรในกรณีที่ผู้เล่นแต่ละคนมีสองกลยุทธ์

บทคัดย่อเพิ่มเมื่อ 13/02/2554


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

งานหลักสูตร เพิ่มเมื่อ 10/17/2014


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

วิทยานิพนธ์เพิ่มเมื่อ 08/08/2550


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

ทดสอบเพิ่มเมื่อ 11/10/2014


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

งานหลักสูตร เพิ่มเมื่อ 17/08/2013


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

วิทยานิพนธ์เพิ่มเมื่อ 06/01/2558


เทคนิคการสร้างแบบจำลองทางคณิตศาสตร์ของระบบคอมพิวเตอร์ที่สะท้อนโครงสร้างและกระบวนการทำงาน จำนวนการเข้าถึงไฟล์ในกระบวนการแก้ไขปัญหาโดยเฉลี่ย การพิจารณาความเป็นไปได้ในการวางไฟล์ในไดรฟ์หน่วยความจำภายนอก

งานห้องปฏิบัติการ เพิ่มเมื่อ 21/06/2556


การออกแบบแบบจำลองทางคณิตศาสตร์ คำอธิบายของเกมโอเอกซ์ แบบจำลองของเกมลอจิกที่ใช้พีชคณิตแบบบูล อุปกรณ์อิเล็กทรอนิกส์ดิจิทัลและการพัฒนาแบบจำลองทางคณิตศาสตร์ เกมคอนโซล, ตัวควบคุมเกม, เส้นสนามเกม

พิจารณาเกมคู่ที่มีผลรวมเป็นศูนย์ที่มีขอบเขตจำกัด ให้เราแสดงโดย กการชนะของผู้เล่น กและผ่าน ข– การชนะของผู้เล่น บี- เพราะ ก = –ขจากนั้นเมื่อวิเคราะห์เกมดังกล่าวไม่จำเป็นต้องพิจารณาตัวเลขทั้งสองนี้ - ก็เพียงพอที่จะพิจารณาการชนะของผู้เล่นคนใดคนหนึ่ง ปล่อยให้มันเป็นเช่น ก- ต่อไปนี้เพื่อความสะดวกในการนำเสนอ กเราจะเรียกตามอัตภาพว่า " เรา“และด้านข้าง บี – "ศัตรู".

ให้เรามี มกลยุทธ์ที่เป็นไปได้ ก 1 , ก 2 , …, เช้าและศัตรู nกลยุทธ์ที่เป็นไปได้ บี 1 , บี 2 , …, บีเอ็น(เกมดังกล่าวเรียกว่าเกม ม.×น- สมมติว่าแต่ละฝ่ายได้เลือกกลยุทธ์บางอย่าง: เราได้เลือกแล้ว ฉัน, คู่ต่อสู้ บีเจ- หากเกมประกอบด้วยการเคลื่อนไหวส่วนบุคคลเท่านั้น จากนั้นเลือกกลยุทธ์ ฉันและ บีเจกำหนดผลลัพธ์ของเกมโดยไม่ซ้ำกัน - เงินรางวัลของเรา (บวกหรือลบ) ให้เราแสดงถึงกำไรนี้ด้วย ไอจ(กำไรเมื่อเราเลือกกลยุทธ์ ฉันและศัตรู – กลยุทธ์ บีเจ).

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

สมมติว่าเรารู้ค่าต่างๆ ไอจสำหรับกลยุทธ์แต่ละคู่ ค่าเหล่านี้สามารถเขียนเป็นเมทริกซ์ได้ โดยแถวที่สอดคล้องกับกลยุทธ์ของเรา ( ฉัน) และคอลัมน์ – กลยุทธ์ของศัตรู ( บีเจ):

เมทริกซ์ดังกล่าวเรียกว่า เมทริกซ์การชำระเงินของเกมหรือเพียงแค่ เมทริกซ์ของเกม.

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

ลองพิจารณาดู ตัวอย่างที่ 1เกมที่เป็นปฏิปักษ์ 4x5 เรามีสี่กลยุทธ์ในการกำจัด ศัตรูมีห้ากลยุทธ์ เมทริกซ์ของเกมมีดังนี้:

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

ให้เราแสดงโดย อ้ายมูลค่าการชนะขั้นต่ำสำหรับกลยุทธ์ ฉัน:

และเพิ่มคอลัมน์ที่มีค่าเหล่านี้ลงในเมทริกซ์เกม:

เมื่อเลือกกลยุทธ์ เราควรเลือกกลยุทธ์ที่มีมูลค่า อ้ายขีดสุด. ให้เราแสดงค่าสูงสุดนี้ด้วย α :

ขนาด α เรียกว่า ราคาต่ำสุดของเกมหรือ สูงสุด(ชนะขั้นต่ำสูงสุด) กลยุทธ์ผู้เล่น กซึ่งสอดคล้องกับค่าสูงสุด α , เรียกว่า กลยุทธ์สูงสุด.

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

ตอนนี้เรามาดูเหตุผลที่คล้ายกันสำหรับศัตรูกัน บี บี ก บี 2 – เราจะตอบเขา ก .

ให้เราแสดงโดย เบต้าเจ ก บี) สำหรับกลยุทธ์ ฉัน:

เบต้าเจ β :

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

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

และเพิ่มแถวที่มีค่าเหล่านี้ลงในเมทริกซ์เกม:

เมื่อเลือกกลยุทธ์ ศัตรูจะเลือกกลยุทธ์ที่มีมูลค่ามากกว่า เบต้าเจน้อยที่สุด ลองแสดงมันด้วย β :

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

Minimax คือมูลค่าของการชนะ ซึ่งมากกว่าที่คู่ต่อสู้ที่สมเหตุสมผลจะไม่ให้เราอย่างแน่นอน (กล่าวอีกนัยหนึ่ง คู่ต่อสู้ที่สมเหตุสมผลจะแพ้ไม่เกิน β - ในตัวอย่างนี้ minimax β เท่ากับ 5 (เซลล์ที่เกี่ยวข้องในตารางถูกเน้นด้วยสีเทา) และทำได้โดยใช้กลยุทธ์ของศัตรู บี 3 .

ดังนั้น ตามหลักการเตือน (“ถือว่าแย่ที่สุดเสมอ!”) เราต้องเลือกกลยุทธ์ ก 4 และศัตรู - กลยุทธ์ บี 3. หลักการเตือนเป็นพื้นฐานในทฤษฎีเกมและเรียกว่า หลักการขั้นต่ำสุด.

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

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

ผู้เล่น กต้องยึดถือกลยุทธ์สูงสุด ก 1 ชนะไม่ต่ำกว่า –3 (คือ แพ้ไม่เกิน 3) กลยุทธ์ผู้เล่นขั้นต่ำ บี– กลยุทธ์ใด ๆ บี 1 และ บี 2รับรองว่าให้ไม่เกิน4

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

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

8 สิ่งที่เรียกว่าเกมแห่งคุณค่า

9. หลักการขั้นต่ำสุดคืออะไร 2. ราคาเกมที่ต่ำกว่าและบน หลักการขั้นต่ำสุด

พิจารณาเกมเมทริกซ์ประเภทที่มีเมทริกซ์ผลตอบแทน

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

ดังนั้นเพื่อให้ได้ชัยชนะที่ยิ่งใหญ่ที่สุดของผู้เล่น กคุณต้องเลือกกลยุทธ์สำหรับตัวเลข ขีดสุด.

การทดสอบการควบคุมขั้นสุดท้าย

1. สามารถตั้งค่าเกมที่เป็นปฏิปักษ์ได้:

ก) ชุดกลยุทธ์สำหรับทั้งผู้เล่นและจุดอาน

b) ชุดกลยุทธ์สำหรับทั้งผู้เล่นและฟังก์ชั่นผลตอบแทนของผู้เล่นคนแรก

2. ราคาของเกมจะมีอยู่เสมอสำหรับเกมเมทริกซ์ที่มีกลยุทธ์แบบผสม

ก. ใช่.

3. หากคอลัมน์ทั้งหมดในเมทริกซ์ผลตอบแทนเหมือนกันและมีรูปแบบ (4 5 0 1) แล้วกลยุทธ์ใดที่เหมาะสมที่สุดสำหรับผู้เล่นคนที่ 1?

ก) ก่อน

ข) ที่สอง

c) รายการใดรายการหนึ่งจากสี่รายการ

4. ให้ในเกมเมทริกซ์ หนึ่งในกลยุทธ์แบบผสมของผู้เล่นคนที่ 1 มีรูปแบบ (0.3, 0.7) และหนึ่งในกลยุทธ์แบบผสมของผู้เล่นคนที่ 2 มีรูปแบบ (0.4, 0, 0.6) มิติของเมทริกซ์นี้เป็นเท่าใด?

ก) 2*3

c) มิติอื่น

5. หลักการครอบงำช่วยให้คุณสามารถลบออกจากเมทริกซ์ได้ในขั้นตอนเดียว:

ก) ทั้งบรรทัด

b) หมายเลขส่วนบุคคล

6. ในวิธีการแบบกราฟิกสำหรับการแก้เกมขนาด 2*m เราจะพบได้โดยตรงจากกราฟ:

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

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

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

7. กราฟของซองจดหมายด้านล่างสำหรับวิธีกราฟิกในการแก้เกม 2*m ในกรณีทั่วไปคือ:

ก) หัก

ข) ตรง

ค) พาราโบลา

8. ในเกมเมทริกซ์ 2*2 มีสององค์ประกอบของกลยุทธ์แบบผสมของผู้เล่น:

ก) กำหนดค่านิยมของกันและกัน

ข) เป็นอิสระ

9. ในเกมเมทริกซ์ องค์ประกอบ aij คือ:

ก) การชนะของผู้เล่นคนที่ 1 เมื่อเขาใช้กลยุทธ์ i-th และอันดับที่ 2 - กลยุทธ์ j-th

b) กลยุทธ์ที่ดีที่สุดของผู้เล่นคนที่ 1 เมื่อฝ่ายตรงข้ามใช้กลยุทธ์ i-th หรือ j-th

c) การสูญเสียผู้เล่นคนที่ 1 เมื่อเขาใช้กลยุทธ์ j-th และคนที่ 2 - กลยุทธ์ i-th

10. องค์ประกอบเมทริกซ์ aij ​​สอดคล้องกับจุดอาน สถานการณ์ต่อไปนี้เป็นไปได้:

ก) องค์ประกอบนี้มีขนาดเล็กที่สุดในบรรทัดอย่างเคร่งครัด

b) องค์ประกอบนี้เป็นลำดับที่สองในบรรทัด

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

ก) กลยุทธ์ของศัตรูในขั้นตอนก่อนหน้า

b) กลยุทธ์ของคุณในขั้นตอนก่อนหน้า

ค) อย่างอื่น

12. ตามเกณฑ์ความคาดหวังทางคณิตศาสตร์ ผู้เล่นแต่ละคนจะได้ประโยชน์จากข้อเท็จจริงที่ว่า:

ก) สถานการณ์ที่เลวร้ายที่สุดสำหรับเขาจะเกิดขึ้น

c) สถานการณ์ทั้งหมดหรือบางสถานการณ์เป็นไปได้โดยมีความน่าจะเป็นที่กำหนด

13. ให้เมทริกซ์กำหนดเกมโดยเมทริกซ์ซึ่งมีองค์ประกอบทั้งหมดเป็นลบ ราคาของเกมเป็นบวก:

B: ไม่.

c) ไม่มีคำตอบที่ชัดเจน

14. ราคาของเกมคือ:

หมายเลข.

ข) เวกเตอร์

ค) เมทริกซ์

15. จำนวนแต้มอานม้าสูงสุดที่สามารถมีได้ในเกมขนาด 5*5 คือเท่าใด (เมทริกซ์สามารถมีตัวเลขใดก็ได้):

16. ให้ในเกมเมทริกซ์มิติ 2*3 หนึ่งในกลยุทธ์ผสมของผู้เล่นคนที่ 1 มีรูปแบบ (0.3, 0.7) และหนึ่งในกลยุทธ์ผสมของผู้เล่นคนที่ 2 มีรูปแบบ (0.3, x, 0.5) . หมายเลข x คืออะไร?

c) หมายเลขอื่น

17. เกณฑ์ Wald เปลี่ยนเป็นเกณฑ์ Laplace ในมิติใดของเมทริกซ์เกม

c) เฉพาะในกรณีอื่นเท่านั้น

18. ราคาสูงสุดของเกมจะน้อยกว่าราคาต่ำสุดของเกมเสมอ

B: ไม่.

b) คำถามไม่ถูกต้อง

19. มีกลยุทธ์อะไรบ้างในเกมเมทริกซ์:

ก) สะอาด

ข) ผสม

ค) ทั้งสองอย่าง

20. ในเกมที่เป็นปรปักษ์บางเกม ค่าของฟังก์ชัน payoff ของผู้เล่นทั้งสองคนสำหรับค่าตัวแปรบางตัวจะเท่ากับ 1 ได้หรือไม่?

ก) เสมอ

ข) บางครั้ง

ค) ไม่เคย

21. ในเกมเมทริกซ์ ให้หนึ่งในกลยุทธ์ผสมของผู้เล่นคนที่ 1 อยู่ในรูปแบบ (0.3, 0.7) และหนึ่งในกลยุทธ์ผสมของผู้เล่นคนที่ 2 อยู่ในรูปแบบ (0.4, 0.1,0.1,0.4) . มิติของเมทริกซ์นี้เป็นเท่าใด?

c) มิติอื่น

22. หลักการครอบงำช่วยให้คุณสามารถลบออกจากเมทริกซ์ได้ในขั้นตอนเดียว:

ก) ทั้งคอลัมน์

b) หมายเลขส่วนบุคคล

c) เมทริกซ์ย่อยที่มีขนาดเล็กกว่า

23. ในเกมเมทริกซ์ขนาด 3*3 มีสององค์ประกอบของกลยุทธ์แบบผสมของผู้เล่น:

ก) กำหนดที่สาม

b) ไม่ได้กำหนด

24. ในเกมเมทริกซ์ องค์ประกอบ aij คือ:

ก) การสูญเสียผู้เล่นคนที่ 2 เมื่อเขาใช้กลยุทธ์ j-th และคนที่ 2 - กลยุทธ์ i-th.

b) กลยุทธ์ที่ดีที่สุดของผู้เล่นคนที่ 2 เมื่อฝ่ายตรงข้ามใช้กลยุทธ์ i-th หรือ j-th

c) การชนะของผู้เล่นคนที่ 1 เมื่อเขาใช้กลยุทธ์ j-th และอันดับที่ 2 - กลยุทธ์ i-th

25. องค์ประกอบเมทริกซ์ aij ​​สอดคล้องกับจุดอาน สถานการณ์ต่อไปนี้เป็นไปได้:

ก) องค์ประกอบนี้ใหญ่ที่สุดในคอลัมน์

b) องค์ประกอบนี้ใหญ่ที่สุดในลำดับอย่างเคร่งครัด

c) สตริงมีองค์ประกอบทั้งที่มากกว่าและน้อยกว่าองค์ประกอบนี้

26. ตามเกณฑ์ของวาลด์ ผู้เล่นแต่ละคนจะถือว่า:

ก) สถานการณ์ที่เลวร้ายที่สุดสำหรับเขาจะเกิดขึ้น

b) ทุกสถานการณ์เป็นไปได้อย่างเท่าเทียมกัน

c) ทุกสถานการณ์เป็นไปได้ด้วยความน่าจะเป็นที่กำหนด

27. ราคาที่ต่ำกว่าน้อยกว่าราคาบนของเกม:

ข) ไม่เสมอไป

ค) ไม่เคย

28. ผลรวมขององค์ประกอบของกลยุทธ์แบบผสมสำหรับเกมเมทริกซ์จะเป็นดังนี้:

ก) เท่ากับ 1

b) ไม่เป็นลบ

ค) เชิงบวก

ง) ไม่เสมอไป

29. ให้ในเกมเมทริกซ์มิติ 2*3 หนึ่งในกลยุทธ์ผสมของผู้เล่นคนที่ 1 มีรูปแบบ (0.3, 0.7) และหนึ่งในกลยุทธ์ผสมของผู้เล่นคนที่ 2 มีรูปแบบ (0.2, x, x) . หมายเลข x คืออะไร?

สถาบันพลังงานมอสโก

(มหาวิทยาลัยเทคนิค)

รายงานห้องปฏิบัติการ

ในทฤษฎีเกม

“โปรแกรมสำหรับค้นหากลยุทธ์ที่เหมาะสมที่สุดสำหรับเกมผลรวมศูนย์ที่จับคู่กันในรูปแบบเมทริกซ์”

เสร็จสิ้นโดยนักศึกษา

กลุ่ม A5-01

อัชราปอฟ ดาเลอร์

อัชราโปวา โอลก้า

แนวคิดพื้นฐานของทฤษฎีเกม

ทฤษฎีเกมถูกออกแบบมาเพื่อแก้ไข สถานการณ์ความขัดแย้ง , เช่น. สถานการณ์ที่ผลประโยชน์ของสองฝ่ายขึ้นไปซึ่งมีเป้าหมายที่แตกต่างกันขัดแย้งกัน

หากเป้าหมายของทั้งสองฝ่ายอยู่ตรงข้ามกันพวกเขาก็พูดถึง ความขัดแย้งที่เป็นปฏิปักษ์ .

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

เรียกว่าการเล่นเกมตั้งแต่ต้นจนจบ งานสังสรรค์ - ผลลัพธ์ของเกมก็คือ การชำระเงิน (หรือ ชัยชนะ ).

งานปาร์ตี้ประกอบด้วย ย้าย , เช่น. ตัวเลือกของผู้เล่นจากชุดทางเลือกที่เป็นไปได้

การเคลื่อนไหวอาจจะเป็น ส่วนตัวและ สุ่ม.การย้ายส่วนตัว ,ไม่เหมือน สุ่ม เกี่ยวข้องกับการเลือกตัวเลือกบางอย่างอย่างมีสติของผู้เล่น

เกมที่มีการเคลื่อนไหวส่วนตัวอย่างน้อยหนึ่งครั้งเรียกว่า เชิงกลยุทธ์ .

เกมที่มีการสุ่มการเคลื่อนไหวทั้งหมดเรียกว่า การพนัน .

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

ปัญหาทฤษฎีเกม– ค้นหากลยุทธ์ที่เหมาะสมที่สุดสำหรับผู้เล่น เช่น กลยุทธ์ที่ให้ผลกำไรสูงสุดหรือการสูญเสียขั้นต่ำ

การจำแนกแบบจำลองทางทฤษฎีเกม

เกม nบุคคลมักจะแสดงเป็น, ที่ไหน
- ชุดกลยุทธ์ของผู้เล่น i-th
- การชำระเงินสำหรับเกม

ตามการกำหนดนี้ สามารถเสนอการจำแนกประเภทของแบบจำลองทฤษฎีเกมดังต่อไปนี้:

ไม่ต่อเนื่อง (หลายกลยุทธ์ ไม่ต่อเนื่อง)

สุดท้าย

ไม่มีที่สิ้นสุด

ต่อเนื่อง (หลายกลยุทธ์ ต่อเนื่อง)

ไม่มีที่สิ้นสุด

nบุคคล (
)

แนวร่วม (สหกรณ์)

ไม่ร่วมมือ (ไม่ร่วมมือ)

2 ท่าน (คู่)

ศัตรูกัน (เกมผลรวมเป็นศูนย์)

(ผลประโยชน์ของทั้งสองฝ่ายอยู่ตรงกันข้าม กล่าวคือ การสูญเสียผู้เล่นคนหนึ่งจะเท่ากับกำไรของอีกฝ่าย)

ไม่เป็นปฏิปักษ์

พร้อมข้อมูลครบถ้วน (หากผู้เล่นทำท่าส่วนตัวรู้เบื้องหลังของเกมทั้งหมด เช่น ท่าเคลื่อนไหวของคู่ต่อสู้ทั้งหมด)

ด้วยข้อมูลที่ไม่ครบถ้วน

ด้วยจำนวนเงินเป็นศูนย์ (การชำระเงินทั้งหมดเท่ากับศูนย์)

ผลรวมที่ไม่เป็นศูนย์

ย้ายครั้งเดียว (ลอตเตอรี่)

มัลติพาส

การแสดงเมทริกซ์ของเกมผลรวมศูนย์ที่จับคู่กัน

ในบทช่วยสอนนี้เราจะดูที่ เกมที่เป็นปฏิปักษ์สองคน กำหนดไว้ในรูปแบบเมทริกซ์ ซึ่งหมายความว่าเรารู้กลยุทธ์มากมายของผู้เล่นคนแรก (player ก){ ก ฉัน }, ฉัน = 1,…, มและกลยุทธ์ที่หลากหลายสำหรับผู้เล่นคนที่สอง (player บี){ บี เจ }, เจ = 1,..., nและให้เมทริกซ์ด้วย ก = || ก ฉัน || ชัยชนะของผู้เล่นคนแรก เนื่องจากเรากำลังพูดถึงเกมที่เป็นปฏิปักษ์ จึงสันนิษฐานว่าการได้รับของผู้เล่นคนแรกเท่ากับการแพ้ของผู้เล่นคนที่สอง เราถือว่าองค์ประกอบเมทริกซ์ ก ฉัน– การชนะของผู้เล่นคนแรกเมื่อเขาเลือกกลยุทธ์ ก ฉันและการตอบโต้ของผู้เล่นคนที่สองต่อเขาด้วยกลยุทธ์ บี เจ- เราจะแสดงถึงเกมดังกล่าวเป็น
, ที่ไหน ม - จำนวนกลยุทธ์ของผู้เล่น เอ,n - จำนวนกลยุทธ์ของผู้เล่น ใน.โดยทั่วไปสามารถแสดงได้ด้วยตารางต่อไปนี้:

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

เป็นตัวอย่างง่ายๆ ลองพิจารณาเกมที่เกมประกอบด้วยสองท่า

การเคลื่อนไหวครั้งที่ 1: ผู้เล่น กเลือกหนึ่งในตัวเลข (1 หรือ 2) โดยไม่แจ้งให้ฝ่ายตรงข้ามทราบถึงการเลือกของเขา

การเคลื่อนไหวครั้งที่ 2: ผู้เล่น ในเลือกหนึ่งในตัวเลข (3 หรือ 4)

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

เกมนี้สามารถนำเสนอในรูปแบบ
ด้วยวิธีต่อไปนี้:

จะเห็นได้ง่ายว่าเกมนี้เป็นศัตรูกัน นอกจากนี้ ยังเป็นเกมที่มีข้อมูลไม่ครบถ้วนเพราะว่า ถึงผู้เล่น ใน,การเคลื่อนไหวส่วนตัวไม่ทราบว่าผู้เล่นเลือกอะไร ก.

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

เมื่อแก้เกมในรูปแบบเมทริกซ์ คุณควรตรวจสอบเกมว่ามีหรือไม่ จุดอาน - เมื่อต้องการทำเช่นนี้ ให้ป้อนค่าสองค่า:

– ประมาณการราคาเกมที่ต่ำกว่าและ

– การประมาณการด้านบนของราคาของเกม

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

ก็สามารถพิสูจน์ได้ว่า α ≤ วี ≤ β , ที่ไหน วี–ราคาเกม กล่าวคือ ชัยชนะที่เป็นไปได้ของผู้เล่นคนแรก

ถ้าความสัมพันธ์ยังคงอยู่ α = β = วีแล้วพวกเขาก็พูดอย่างนั้น เกมนี้มีจุดอาน
, และ สามารถแก้ไขได้ด้วยกลยุทธ์ล้วนๆ - กล่าวอีกนัยหนึ่ง มีสองสามกลยุทธ์
ให้กับผู้เล่น กวี.

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

กลับไปที่เกมที่เราพิจารณาในตัวอย่างที่ 1 และตรวจสอบว่ามีจุดอานหรือไม่

สำหรับเกมนี้
= -5,
= 4,
มันจึงไม่มีจุดอาน

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

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

มาเปลี่ยนแปลงกฎของเกมจากตัวอย่างที่ 1 กัน เราจะจัดให้มีนักพนัน ในข้อมูลการเลือกผู้เล่น ก.แล้วมี ในสองกลยุทธ์เพิ่มเติมจะปรากฏขึ้น:

- กลยุทธ์ที่เป็นประโยชน์สำหรับ ก.ถ้าจะเลือก เอ - 1,ที่ ในเลือก 3 ถ้าเลือก เอ - 2,ที่ ในเลือก 4;

- กลยุทธ์ที่ไม่เกิดประโยชน์ ก.ถ้าจะเลือก เอ - 1,ที่ ในเลือก 4 ถ้าเลือก เอ - 2,ที่ ในเลือก 3

เกมนี้เต็มไปด้วยข้อมูลที่ครบถ้วน

ในกรณีนี้
= -5,
= -5,
ดังนั้นเกมจึงมีจุดอาน
- จุดอานนี้สอดคล้องกับกลยุทธ์ที่ดีที่สุดสองคู่:
และ
- ราคาเกม วี= -5. เป็นที่ชัดเจนว่าสำหรับ กเกมดังกล่าวไม่ได้ผลกำไร

ตัวอย่างที่ 2 และ 3 เป็นตัวอย่างที่ดีของทฤษฎีบทต่อไปนี้ ซึ่งพิสูจน์แล้วในทฤษฎีเกม:

ทฤษฎีบท 1

เกมคู่อริทุกเกมที่มีข้อมูลครบถ้วนสามารถแก้ไขได้ด้วยกลยุทธ์ล้วนๆ

ที่. ทฤษฎีบท 1 กล่าวว่าเกมที่มีผู้เล่นสองคนที่มีข้อมูลครบถ้วนจะมีจุดอานและมีกลยุทธ์ที่บริสุทธิ์คู่หนึ่ง
ให้กับผู้เล่น กการชนะที่ยั่งยืนเท่ากับราคาของเกม วี.

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

ทฤษฎีบทต่อไปนี้เป็นการสรุปทฤษฎีบทที่ 1 ให้กับกรณีของเกมที่มีข้อมูลที่ไม่สมบูรณ์:

ทฤษฎีบท 2

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

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