แนวคิดของโมเดลเกม เมทริกซ์การชำระเงิน

พิจารณาคู่จบเกม ให้ผู้เล่น อามี ตู่กลยุทธ์ส่วนบุคคลที่เราจะกำหนด

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

ผลของการเลือกโดยผู้เล่นของคู่กลยุทธ์ใด ๆ ผลลัพธ์ของเกมจะถูกกำหนดอย่างเฉพาะเจาะจงเช่น ได้รับ เอ;. ผู้เล่น อา(บวกหรือลบ) และการสูญเสีย (-อา)ผู้เล่น วีสมมติค่า ก..เป็นที่รู้จักสำหรับคู่ของกลยุทธ์ (A :, B;.) เมทริกซ์ พี =(ก..), ผม = = 1, 2, ..., m j = 1, 2, ..., พีองค์ประกอบที่เป็นเงินรางวัลที่สอดคล้องกับกลยุทธ์ ก.และ บีเจเรียกว่า เมทริกซ์การชำระเงิน,หรือ เมทริกซ์ของเกม แบบฟอร์มทั่วไปเมทริกซ์ดังกล่าวถูกนำเสนอในตาราง 12.1. แถวของตารางนี้สอดคล้องกับกลยุทธ์ของผู้เล่น เอ,และคอลัมน์สำหรับกลยุทธ์ของผู้เล่น วี

ตาราง 12.1

มาสร้างเมทริกซ์การชำระเงินสำหรับเกมถัดไปกัน

12.1. เกมค้นหา

ผู้เล่น อาสามารถซ่อนตัวในหนึ่งในสองที่พักพิง (I และ II); ผู้เล่น วีกำลังมองหาผู้เล่น เอ,และถ้าเขาพบมัน เขาได้รับโทษ 1 ถ้ำ หน่วย จาก เอ,มิฉะนั้นจะจ่ายให้ผู้เล่น อา 1 วัน หน่วย จำเป็นต้องสร้างเมทริกซ์การชำระเงินของเกม

ตัดสินใจด้วย ในการรวบรวมเมทริกซ์การชำระเงิน คุณควรวิเคราะห์พฤติกรรมของผู้เล่นแต่ละคน ผู้เล่น อาสามารถซ่อนตัวอยู่ในที่กำบัง I - เราหมายถึงกลยุทธ์นี้โดย อา v ในห้องนิรภัย II - กลยุทธ์ ก. g ผู้เล่น วีสามารถมองหาผู้เล่นคนแรกในที่พักพิง I - กลยุทธ์ วี(หรือในห้องนิรภัย II - กลยุทธ์ วี,.ถ้าผู้เล่น อาอยู่ในที่ซ่อนฉันและผู้เล่นค้นพบที่นั่น วีเหล่านั้น. มีการดำเนินการสองสามกลยุทธ์ (Α ν วี{), แล้วผู้เล่น อาจ่ายค่าปรับคือ เอน = -1 ในทำนองเดียวกัน เราได้รับ ก. n = -1 (อา 2, ว.,).เห็นได้ชัดว่ากลยุทธ์ (A, วี.)และ (A2, / 1,) ให้ผู้เล่น อาผลตอบแทนคือ 1 ดังนั้น เอพี = ก. n = I ดังนั้นสำหรับเกม "ค้นหา" ขนาด 2x2 เราได้รับเมทริกซ์การชำระเงิน:

พิจารณาเกม ตู่ X พีด้วยเมทริกซ์ P = aเจ) , ผม = 1,2, ..., τη; เจ= 1, 2, ... และกำหนดกลยุทธ์ที่ดีที่สุด อาที่ อาวี ..., อา t. การเลือกกลยุทธ์ อาเครื่องเล่น jy อาต้องถือว่าผู้เล่น วีจะตอบให้เป็นหนึ่งในกลยุทธ์ วีซึ่งกำไรสำหรับผู้เล่น อาน้อยที่สุด (ผู้เล่น วีพยายามที่จะ "ทำร้าย" ผู้เล่น ก)

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

ในบรรดาตัวเลขทั้งหมด a (r = 1,2, ..., ต)เลือกที่ใหญ่ที่สุด:. โทรมาเลย แต่ท้ายเกมหรือ ผลตอบแทนสูงสุด (สูงสุด)นี้ รับประกันผลตอบแทนของผู้เล่น A สำหรับกลยุทธ์ของผู้เล่น Bเพราะฉะนั้น,

(12.2)

กลยุทธ์ที่สอดคล้องกับ maximin เรียกว่า กลยุทธ์สูงสุดผู้เล่น วีสนใจลดเงินรางวัลของผู้เล่น เอ;การเลือกกลยุทธ์ วีเขาคำนึงถึงผลกำไรสูงสุดในกรณีนี้สำหรับ ก.เราหมายถึง

ในบรรดาตัวเลขทั้งหมด β เลือกที่เล็กที่สุด

และเรียก β ราคาสูงสุดของเกม, หรือ มินิแม็กซ์ วิน (minimax).นี้ รับประกันการสูญเสียผู้เล่น B.เพราะฉะนั้น,

(12.4)

กลยุทธ์ที่สอดคล้องกับค่าต่ำสุดเรียกว่า กลยุทธ์มินิแม็กซ์

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

จากปัญหา 12.1 เมื่อเลือกกลยุทธ์ Л (แถวแรกของเมทริกซ์) ผลตอบแทนขั้นต่ำเท่ากับ a = นาที (-l; 1) = -1 และสอดคล้องกับกลยุทธ์ β1 ของผู้เล่น วีเมื่อเลือกกลยุทธ์ หลี่ 2 (แถวที่สองของเมทริกซ์) ผลตอบแทนขั้นต่ำคือ เอ 2 = นาที (l; -1) = -1 ทำได้ด้วยกลยุทธ์ วี,.

รับประกันตัวเอง ชนะสูงสุดสำหรับกลยุทธ์ของผู้เล่นทุกคน วี, เช่น. ราคาที่ต่ำกว่าของเกม a = max (a, a2) = = max (-l; -1) = -1 ผู้เล่น อาสามารถเลือกกลยุทธ์ใดก็ได้: Aj or อา 2 คือ กลยุทธ์ใด ๆ ของเขานั้นสูงสุด

การเลือกกลยุทธ์ B (คอลัมน์ 1) ผู้เล่น วีเข้าใจว่าผู้เล่น อาจะตอบสนองด้วยกลยุทธ์ อา 2 เพื่อเพิ่มกำไรของคุณให้สูงสุด (ขาดทุน วี).ดังนั้นการสูญเสียสูงสุดของผู้เล่น วีเมื่อเขาเลือกกลยุทธ์ B จะเท่ากับ β = ตรวจสอบ (-1; 1) = 1

ในทำนองเดียวกันการสูญเสียสูงสุดของผู้เล่น B (กำไร อา) เมื่อเขาเลือกกลยุทธ์ B2 (คอลัมน์ 2) คือ β2 = สูงสุด (l; -1) = 1

ดังนั้นสำหรับกลยุทธ์ของผู้เล่นทุกคน อาการสูญเสียขั้นต่ำที่รับประกันของผู้เล่น B คือ β = πιίη (β1, β2) = นาที (l; 1) = 1 - ราคาสูงกว่าของเกม

กลยุทธ์ของผู้เล่น B ก็คือขั้นต่ำสุด เสริมโต๊ะ. 12.1 โดยสตริง β; และคอลัมน์ a; เราได้ตาราง 12.2. ที่จุดตัดของแถวและคอลัมน์เพิ่มเติม เราจะเขียนราคาเกมบนและล่าง

ตาราง 12.2

ในปัญหา 12.1 ที่พิจารณาข้างต้น ราคาเกมบนและล่างแตกต่างกัน: ฉ β.

หากราคาเกมบนและล่างเท่ากัน แสดงว่า มูลค่ารวมด้านบนและ ราคาต่ำสุดของเกม α = β = υ เรียกว่า ราคาที่แท้จริงของเกมหรือ ในราคาของเกมกลยุทธ์ขั้นต่ำที่สอดคล้องกับราคาเกมคือ กลยุทธ์ที่เหมาะสมและจำนวนทั้งหมดของพวกเขา - ทางออกที่ดีที่สุดหรือ การตัดสินใจเกม. ในกรณีนี้ผู้เล่น อาได้รับการรับประกันสูงสุด (ขึ้นอยู่กับพฤติกรรมของผู้เล่น วี)ผลตอบแทน υ และผู้เล่น วีบรรลุการรับประกันขั้นต่ำ (โดยไม่คำนึงถึงพฤติกรรมของผู้เล่น Л) การสูญเสีย υ ว่ากันว่าทางแก้ของเกมมี ความมั่นคงเหล่านั้น. หากผู้เล่นคนใดคนหนึ่งปฏิบัติตามกลยุทธ์ที่เหมาะสมที่สุดของเขา จะไม่สามารถทำกำไรให้อีกฝ่ายหนึ่งเบี่ยงเบนไปจากกลยุทธ์ที่เหมาะสมที่สุดของเขาได้

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

เราหมายถึง ก*และ วี*- คู่ของกลยุทธ์บริสุทธิ์ที่บรรลุการแก้ปัญหาของเกมในปัญหาจุดอาน ให้เราแนะนำฟังก์ชั่นการจ่ายเงินของผู้เล่นคนแรกในแต่ละกลยุทธ์: พี (อา:, วี-) = และที่... จากนั้น จากสภาวะที่เหมาะสมที่สุดที่จุดอาน ความไม่เท่าเทียมกันสองเท่าจะถือ: พี (อจ. บี *)<Р(А*, В*)<Р(А", В ), ซึ่งเป็นจริงสำหรับทุกคน ผม = 1, 2, ..., m; j = 1, 2, ..., ป.แท้จริงแล้วการเลือกกลยุทธ์ อา* ผู้เล่นคนแรกที่มีกลยุทธ์ที่ดีที่สุด วี"ผู้เล่นคนที่สองเพิ่มการชนะขั้นต่ำให้สูงสุด: พี (อา*, บี")> พี (อาจี วี"),และทางเลือกของกลยุทธ์ บี "ผู้เล่นคนที่สองที่มีกลยุทธ์ที่เหมาะสมของคนแรกจะลดการสูญเสียสูงสุด: P (D, วี*)<Р(А", В).

12.2. กำหนดราคาที่ต่ำกว่าและด้านบนของเกมที่กำหนดโดยเมทริกซ์การชำระเงิน

เกมมีจุดอานหรือไม่?

ตารางที่ 12. 3

สารละลาย.สะดวกในการดำเนินการคำนวณทั้งหมดในตารางซึ่งนอกเหนือจากเมทริกซ์ อาร์แนะนำคอลัมน์ a; และสตริง)