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

การปฏิบัติงาน №3

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

แนวคิดของโมเดลเกม

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

1. ตัวเลือกผู้เล่น;

2. จำนวนข้อมูลที่ผู้เล่นแต่ละคนมีเกี่ยวกับพฤติกรรมของพันธมิตร

3. ผลตอบแทนที่การกระทำแต่ละชุดนำไปสู่

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

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

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

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

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

ตัวอย่าง - เกม "ค้นหา"

ผู้เล่น แต่สามารถซ่อนตัวอยู่ในที่กำบัง 1 - แสดงว่ากลยุทธ์นี้เป็น A 1หรือในที่พักพิง 2 - กลยุทธ์ A 2. ผู้เล่น ที่สามารถมองหาผู้เล่นคนแรกในที่พักพิง 1 - กลยุทธ์ ใน 1หรือในที่พักพิง 2 - กลยุทธ์ ใน2. หากผู้เล่น แต่อยู่ใน Vault 1 และถูกค้นพบโดยผู้เล่น ที่, เช่น. กำลังดำเนินการสองสามกลยุทธ์ (A 1, B 1)แล้วผู้เล่น แต่จ่ายค่าปรับคือ 11=–1. ในทำนองเดียวกันเราได้รับ 22=–1. เห็นได้ชัดว่ากลยุทธ์ (A 1, B 2)และ (A 2, B 1)ให้ผู้เล่น แต่ชนะ 1 ดังนั้น 12=21=1. ดังนั้นเราจึงได้เมทริกซ์ผลตอบแทน

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

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

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

กลยุทธ์ที่สอดคล้องกับ maximin เรียกว่า กลยุทธ์สูงสุด. ผู้เล่น ที่สนใจลดผลตอบแทนผู้เล่น แต่; การเลือกกลยุทธ์ บีเจโดยคำนึงถึงผลตอบแทนสูงสุดที่เป็นไปได้สำหรับ A. Denote

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

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

เกมสถิติ

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

งาน

หลังจากใช้งานมาหลายปี อุปกรณ์อุตสาหกรรมจะอยู่ในสถานะใดสถานะหนึ่งต่อไปนี้: ใน 1 - อุปกรณ์สามารถใช้งานได้ในปีหน้าหลังจากการบำรุงรักษาเชิงป้องกัน B 2 - เพื่อการใช้งานอุปกรณ์ที่ปราศจากปัญหาในอนาคต จำเป็นต้องเปลี่ยนชิ้นส่วนและส่วนประกอบแต่ละส่วน ใน 3 - อุปกรณ์ต้องมีการซ่อมแซมหรือเปลี่ยนใหม่

ขึ้นอยู่กับสถานการณ์ปัจจุบัน B 1, B 2, B 3 ผู้บริหารขององค์กรสามารถตัดสินใจได้ดังต่อไปนี้: A 1 - ซ่อมแซมอุปกรณ์โดยผู้เชี่ยวชาญในโรงงานซึ่งต้องใช้ต้นทุนที่เหมาะสม a 1 = 6, a 2 = 10 และ 3 = 15 หน่วยเงิน ; A 2 - เรียกทีมช่างซ่อมพิเศษค่าใช้จ่ายในกรณีนี้คือ b 1 \u003d 15, b 2 \u003d 9, b 3 \u003d 18 หน่วยการเงิน A 3 - เปลี่ยนอุปกรณ์ใหม่โดยขายอุปกรณ์ที่ล้าสมัยตามมูลค่าคงเหลือ ค่าใช้จ่ายทั้งหมดของผลลัพธ์ของเหตุการณ์นี้จะเท่ากับ 1 =13 ตามลำดับ 2 =24 หน่วยเงิน 3 =12 หน่วย

ออกกำลังกาย

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

2. รวบรวมเมทริกซ์ผลตอบแทน อธิบายความหมายขององค์ประกอบ a ij ของเมทริกซ์ (เหตุใดจึงเป็นลบ)

3. ค้นหาสิ่งที่ตัดสินใจเกี่ยวกับการทำงานของอุปกรณ์ในปีหน้าที่จะแนะนำให้ผู้บริหารขององค์กรเพื่อลดการสูญเสียภายใต้สมมติฐานดังต่อไปนี้: ก) ประสบการณ์ที่ได้รับจากองค์กรในการใช้งานอุปกรณ์ที่คล้ายกันแสดงให้เห็น ความน่าจะเป็นของสถานะที่ระบุของอุปกรณ์นั้นตามลำดับ q 1 = 0.15; q 2 =0.55; q 3 \u003d 0.3 (ใช้การทดสอบ Bayes); b) ประสบการณ์แสดงให้เห็นว่าทั้งสามสถานะที่เป็นไปได้ของอุปกรณ์มีแนวโน้มเท่าเทียมกัน (ใช้เกณฑ์ Laplace) c) ไม่มีอะไรแน่นอนเกี่ยวกับความน่าจะเป็นของอุปกรณ์ (ใช้เกณฑ์ของ Wald, Savage, Hurwitz) ค่าของพารามิเตอร์ g=0.8 ในเกณฑ์ Hurwitz ถูกตั้งค่าไว้

การตัดสินใจ

1) สถานการณ์ที่อธิบายไว้เป็นเกมทางสถิติ

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

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

2) เขียนเมทริกซ์ผลตอบแทนของเกม:

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

ก) ประสบการณ์การใช้งานที่สะสมในองค์กรที่คล้ายกับอุปกรณ์แสดงว่าความน่าจะเป็นของสถานะอุปกรณ์เท่ากับ q 1 =0.15; q 2 =0.55; q 3 \u003d 0.3

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

โดยที่ , (i=1.3)

ตามเกณฑ์ของ Bayes กลยุทธ์บริสุทธิ์ A i ถูกนำมาใช้อย่างดีที่สุด โดยที่ค่าเฉลี่ยของนักสถิติจะถูกขยายให้ใหญ่สุด กล่าวคือ ให้บริการโดย =max

กลยุทธ์ที่เหมาะสมที่สุดแบบเบย์คือ กลยุทธ์ A 1

b) ประสบการณ์แสดงให้เห็นว่าทั้งสามสถานะที่เป็นไปได้ของอุปกรณ์มีแนวโน้มเท่าเทียมกัน กล่าวคือ = 1/3.

ชัยชนะโดยเฉลี่ยคือ:

1/3 * (-6-10-15) \u003d -31/3 "-10.33;

1/3*(-15-9-18) = -42/3 = -14;

1/3 * (-13-24-12) \u003d -49/3 "-16.33.

จากข้อมูลของ Laplace กลยุทธ์ที่เหมาะสมที่สุดคือ A 1

c) ไม่มีอะไรแน่นอนเกี่ยวกับความน่าจะเป็นของอุปกรณ์

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

.

= สูงสุด (-15, -18, -24) = -15

ดังนั้นกลยุทธ์ A 1 จึงเหมาะสมที่สุด

มาสร้างเมทริกซ์ความเสี่ยงกัน โดยที่

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

เกมกลยุทธ์ที่ง่ายที่สุดคือเกมที่มียอดรวมเป็นศูนย์สำหรับสองคน (ผลรวมของผลตอบแทนของทั้งสองฝ่ายเป็นศูนย์) เกมประกอบด้วยสองท่า: ผู้เล่น A เลือกหนึ่งในกลยุทธ์ที่เป็นไปได้ของเขา Ai (i = 1, 2, m) และผู้เล่น B เลือกกลยุทธ์ Bj (j = 1, 2, ., n) และแต่ละตัวเลือกจะทำใน เพิกเฉยต่อทางเลือกของผู้เล่นอื่นอย่างสมบูรณ์

เป้าหมายของผู้เล่น A คือการเพิ่มฟังก์ชันสูงสุด φ (Ai, Bj) ในทางกลับกัน เป้าหมายของผู้เล่น B คือการลดฟังก์ชันเดียวกันให้เหลือน้อยที่สุด ผู้เล่นแต่ละคนสามารถเลือกตัวแปรหนึ่งตัวที่ค่าของฟังก์ชันขึ้นอยู่กับ หากผู้เล่น A เลือกกลยุทธ์บางอย่างของ Ai สิ่งนี้จะไม่ส่งผลต่อค่าของฟังก์ชัน φ (Ai, Bj) ในตัวมันเอง

อิทธิพลของ Ai ต่อขนาดของค่า φ (Ai, Bj) ไม่แน่นอน ความแน่นอนเกิดขึ้นหลังจากการเลือกเท่านั้นโดยอิงตามหลักการย่อเล็กสุดของ φ (Ai, Bj) โดยผู้เล่นอื่นของตัวแปร Bj ในกรณีนี้ Bj จะถูกกำหนดโดยผู้เล่นคนอื่น ให้ φ (Ai, Bj)= aij มาสร้างเมทริกซ์ A:

แถวของเมทริกซ์สอดคล้องกับกลยุทธ์ Ai คอลัมน์สอดคล้องกับกลยุทธ์ Bj Matrix A เรียกว่า payoff หรือ game matrix องค์ประกอบของเมทริกซ์คือผลตอบแทนของผู้เล่น A หากเขาเลือกกลยุทธ์ Ai และผู้เล่น B เลือกกลยุทธ์ Bj

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

a = สูงสุด ต่ำสุด aij

มูลค่า a - ผลตอบแทนที่รับประกันของผู้เล่น A - เรียกว่าราคาที่ต่ำกว่าของเกม กลยุทธ์ Ai0 ซึ่งรับประกันว่าจะได้รับ a เรียกว่า maximin

ผู้เล่น B เลือกกลยุทธ์โดยใช้หลักการดังต่อไปนี้: เมื่อเลือกกลยุทธ์ Bj การสูญเสียของเขาจะไม่เกินค่าสูงสุดขององค์ประกอบของคอลัมน์ jth ของเมทริกซ์เช่น น้อยกว่าหรือเท่ากับ max aij

พิจารณาชุด max aij สำหรับ ความหมายต่างกัน j ผู้เล่น B จะเลือกค่า j โดยธรรมชาติเพื่อลดการสูญเสียสูงสุด β ของเขา:

β = min miax aij

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

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

ทฤษฎีเกมเป็นวินัยทางคณิตศาสตร์ ซึ่งหัวข้อนี้เป็นวิธีการตัดสินใจในสถานการณ์ขัดแย้ง

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

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

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

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

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

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

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

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

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

พิจารณาเกมคู่ขนาน ให้ผู้เล่น แต่ มี ม กลยุทธ์ส่วนตัวซึ่งเราหมายถึง A 1 , A2 , ..., เป็น . ให้ผู้เล่น ที่ มีอยู่ น กลยุทธ์ส่วนบุคคล เราหมายถึงพวกเขา B1 , B2 , ..., Bm . เขาว่ากันว่าเกมมีมิติ ม × น . เป็นผลมาจากการเลือกคู่ของกลยุทธ์ใด ๆ ของผู้เล่น

A i และ B j (i = 1, 2, ..., m; j = 1, 2, ..., n)

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

ตารางที่3.1

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

พิจารณาเกม ม × น ด้วยเมทริกซ์ P = (a ij), i = 1, 2, ..., m; เจ = 1, 2, ..., n และกำหนดกลยุทธ์ที่ดีที่สุด A 1 , A2 , ..., เป็น . การเลือกกลยุทธ์ AI ผู้เล่น แต่ ควรคาดหวังผู้เล่น ที่ จะตอบด้วยกลยุทธอันใดอันหนึ่ง บีเจ , ซึ่งผลตอบแทนสำหรับผู้เล่น แต่ น้อยที่สุด (ผู้เล่น ที่ พยายามที่จะ "ทำร้าย" ผู้เล่น แต่ ). แสดงโดย ฉัน , ผลตอบแทนที่น้อยที่สุดของผู้เล่น แต่ เมื่อเลือกกลยุทธ์ AI สำหรับกลยุทธ์ของผู้เล่นที่เป็นไปได้ทั้งหมด ที่ (จำนวนน้อยที่สุดใน ฉัน- แถวที่หนึ่งของเมทริกซ์ผลตอบแทน) เช่น

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

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

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

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

แนวคิดพื้นฐานของรูปแบบการจัดการสินค้าคงคลัง

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

พิจารณาลักษณะสำคัญของแบบจำลองการจัดการสินค้าคงคลัง

ความต้องการ. ความต้องการสินค้าในสต็อกสามารถ กำหนดขึ้น(ในกรณีที่ง่ายที่สุด - คงที่ในเวลา) หรือ สุ่มความสุ่มของอุปสงค์อธิบายโดยโมเมนต์ของอุปสงค์แบบสุ่ม หรือโดยจำนวนอุปสงค์แบบสุ่มในช่วงเวลาที่กำหนดหรือแบบสุ่ม

ต่อเติมโกดัง.การเติมเต็มคลังสินค้าสามารถทำได้เป็นระยะ ๆ ในช่วงเวลาหนึ่ง หรือเมื่อสินค้าหมดสต็อก เช่น ลดระดับลงสู่ระดับหนึ่ง

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

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

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

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

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

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

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

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

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

ให้ฟังก์ชัน และ แสดงตามลำดับ:

กำลังเติมสต็อก,

การบริโภคสต็อก

ความต้องการสินค้าในสต็อค

เป็นระยะเวลาหนึ่ง

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

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

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

การเคลื่อนไหวส่วนบุคคล- นี่คือตัวเลือกที่มีสติโดยผู้เล่นในการกระทำที่เป็นไปได้อย่างใดอย่างหนึ่ง (เช่น การเคลื่อนไหวในเกมหมากรุก)

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

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

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

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

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

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

พิจารณาเกม ม x น ด้วยเมทริกซ์ Р = (ไอเจ), ผม = 1,2, ... , m; j = 1,2, ... , n และกำหนดกลยุทธ์ที่ดีที่สุด A 1, A 2, ..., A m. การเลือกกลยุทธ์ ฉันผู้เล่น แต่ควรคาดหวังผู้เล่น ที่จะตอบด้วยกลยุทธอันใดอันหนึ่ง บีเจ, ซึ่งผลตอบแทนสำหรับผู้เล่น แต่น้อยที่สุด (ผู้เล่น ที่พยายามที่จะ "ทำร้าย" ผู้เล่น แต่). แสดงโดย เอฉัน, ผลตอบแทนที่น้อยที่สุดของผู้เล่น แต่เมื่อเลือกกลยุทธ์ ฉันสำหรับกลยุทธ์ของผู้เล่นที่เป็นไปได้ทั้งหมด ที่(จำนวนน้อยที่สุดใน ฉัน-th เส้นของเมทริกซ์ผลตอบแทน) เช่น

ฉัน = ไอจ , เจ = 1,...,น.

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

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

แสดงว่า: β ฉัน = ไอจ , ผม = 1,... , ม

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

เพราะฉะนั้น, ผม = 1,... , ม; เจ = 1,...,น.

กลยุทธ์ minimax เรียกว่า กลยุทธ์ขั้นต่ำ.

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

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

§ 6 องค์ประกอบของทฤษฎีเกม

6.1 แนวคิดของโมเดลเกม

แบบจำลองทางคณิตศาสตร์ของสถานการณ์ความขัดแย้งเรียกว่า เกม , ฝ่ายที่เกี่ยวข้องในความขัดแย้ง ผู้เล่น และผลของความขัดแย้ง ชนะ .

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

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

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

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

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

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

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

หนึ่งในแนวคิดพื้นฐานของทฤษฎีเกมคือแนวคิด กลยุทธ์ .

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

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

หากเกมซ้ำมากพอ ผู้เล่นอาจไม่สนใจที่จะชนะและแพ้ในแต่ละเกม เอเฉลี่ยชนะ (แพ้) ในทุกฝ่าย

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

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

จบเกมที่ผู้เล่น แต่มันมี tกลยุทธ์และผู้เล่น บี - พีกลยุทธ์เรียกว่าเกม

พิจารณาเกม
ผู้เล่นสองคน แต่และ ที่("เรา" และ "คู่ต่อสู้")

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

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

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

เกมเมทริกซ์
ดูเหมือนกับ:

พิจารณาเกม
ด้วยเมทริกซ์

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

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

(1)

ในบรรดาตัวเลขทั้งหมด (
) เลือกที่ใหญ่ที่สุด:
.

โทรมาเลย
ลดราคาอีก, หรือ ชนะสูงสุด (maxmin) นี่คือการรับประกันผลตอบแทนของผู้เล่น A สำหรับกลยุทธ์ใดๆ ของผู้เล่น B เพราะฉะนั้น,

. (2)

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

. (3)

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

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

. (4)

กลยุทธ์ minimax เรียกว่า กลยุทธ์มินิแม็กซ์

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

ทฤษฎีบท.ราคาที่ต่ำกว่าของเกมไม่เคยเกินราคาบนของเกม
.

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

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

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

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

เกมที่
, เรียกว่า เกมจุดอาน องค์ประกอบ ซึ่งมีคุณสมบัตินี้ คือจุดอานของเมทริกซ์

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

1) หากทั้งสองฝ่ายยึดกลยุทธ์ที่เหมาะสม ผลตอบแทนเฉลี่ยจะเท่ากับต้นทุนสุทธิของเกม วีซึ่งเป็นราคาทั้งบนและล่าง

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

คลาสของเกมที่มีจุดอานเป็นที่สนใจอย่างมากทั้งจากมุมมองทางทฤษฎีและทางปฏิบัติ

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