გადახდის მატრიცა. თამაშის ქვედა და ზედა ფასი

განვიხილოთ დაწყვილებული სასრული თამაში. მიეცით მოთამაშეს ააქვს თპირადი სტრატეგიები, რომელსაც ჩვენ აღვნიშნავთ

მიეცით მოთამაშეს INხელმისაწვდომი პპერსონალური სტრატეგიები, მოდით დავასახელოთ ისინი. ისინი ამბობენ, რომ თამაშს აქვს ზომები თ X პ.

მოთამაშეების მიერ ნებისმიერი წყვილი სტრატეგიის არჩევის შედეგად, თამაშის შედეგი ცალსახად განისაზღვრება, ე.ი. მოგება ა;. მოთამაშე ა(დადებითი ან უარყოფითი) და დანაკარგი (-აი)მოთამაშე IN.დავუშვათ, რომ ღირებულებები ა..ცნობილია ნებისმიერი წყვილი სტრატეგიით (A:, B;.). მატრიცა P =(ა..), მე = = 1, 2, ..., მ ჯ = 1, 2, ..., P,რომლის ელემენტებია სტრატეგიების შესაბამისი მოგება ა.და Bj,დაურეკა გადახდის მატრიცა,ან თამაშის მატრიცა. ზოგადი ფორმაასეთი მატრიცა წარმოდგენილია ცხრილში. 12.1. ამ ცხრილის რიგები შეესაბამება მოთამაშის სტრატეგიებს A,და სვეტები - მოთამაშის სტრატეგიები IN.

ცხრილი 12.1

მოდით შევქმნათ გადახდის მატრიცა შემდეგი თამაშისთვის.

12.1. თამაშის ძებნა.

მოთამაშე აშეუძლია დაიმალოს ორიდან ერთ-ერთ თავშესაფარში (I და II); მოთამაშე INეძებს მოთამაშეს A,და თუ იპოვის, 1 დენს ჯარიმას იღებს. ერთეულები საწყისი A,წინააღმდეგ შემთხვევაში იხდის მოთამაშეს ა 1 დღე ერთეულები აუცილებელია თამაშის გადახდის მატრიცის აგება.

გადაწყვეტა. გადახდის მატრიცის შესაქმნელად, თქვენ უნდა გაანალიზოთ თითოეული მოთამაშის ქცევა. მოთამაშე აშეუძლია I თავშესაფარში დამალვა - ამ სტრატეგიას აღვნიშნავთ ა v ან თავშესაფარში II – სტრატეგია ა.დ მოთამაშე INშეუძლია მოძებნოს პირველი მოთამაშე თავშესაფარში I - სტრატეგია IN(ან თავშესაფარში II - სტრატეგია IN.,.თუ მოთამაშე ამდებარეობს Vault I-ში და აღმოაჩინა მოთამაშე იქ IN,იმათ. რამდენიმე სტრატეგია ხორციელდება (Α ν IN{), შემდეგ მოთამაშე აიხდის ჯარიმას, ე.ი. ა n = -1. ანალოგიურად ვიღებთ ა. n = -1 (ა 2, IN.,).აშკარაა, რომ სტრატეგიები (A, IN.,)და (L2, /1,) მიეცით მოთამაშეს აანაზღაურება არის 1, ასე რომ აპ = ა. n = I. ამრიგად, 2x2 ზომის საძიებო თამაშისთვის ვიღებთ ანაზღაურების მატრიცას:

განიხილეთ თამაში თ X პმატრიცით P =aკ) , მე = 1,2, ..., თქვენ; ჯ= 1, 2, ..., და და განსაზღვრეთ საუკეთესო სტრატეგიებს შორის აზე ავ..., ატ.სტრატეგიის არჩევა აჯი მოთამაშე აუნდა ველოდოთ, რომ მოთამაშე INუპასუხებს მას ერთ-ერთი სტრატეგიის გამოყენებით IN.,რისთვისაც ანაზღაურება მოთამაშისთვის ამინიმალური (მოთამაშე INცდილობს მოთამაშის "დაზიანებას". ა).

აღვნიშნოთ a-ით; მოთამაშის ყველაზე პატარა მოგება აროდესაც ის ირჩევს სტრატეგიას L; ყველა შესაძლო მოთამაშის სტრატეგიისთვის IN(ყველაზე მცირე რაოდენობა მე-ე ხაზიგადახდის მატრიცა), ე.ი.

ყველა რიცხვს შორის a (r = 1,2,..., T)ავირჩიოთ ყველაზე დიდი: . დავურეკოთ და თამაშის დაბალი ფასი,ან მაქსიმალური მოგება (მაქსიმინი).ეს გარანტირებული მოგება A მოთამაშისთვის B მოთამაშის ნებისმიერი სტრატეგიისთვის.აქედან გამომდინარე,

(12.2)

მაქსიმინის შესაბამისი სტრატეგია ე.წ მაქსიმალური სტრატეგია.მოთამაშე INდაინტერესებულია მოთამაშის მოგების შემცირებით ა;სტრატეგიის არჩევა IN.,იგი ითვალისწინებს მაქსიმალურ შესაძლო მოგებას ა.აღვნიშნოთ

ყველა რიცხვს შორის β. ავირჩიოთ ყველაზე პატარა,

და მოვუწოდებთ β თამაშის ყველაზე მაღალი ფასი, ან მინიმალური მოგება (მინიმქსი).ეს გარანტირებული წაგება მოთამაშისთვის B.აქედან გამომდინარე,

(12.4)

მინიმაქსის შესაბამისი სტრატეგია ეწოდება მინიმალური სტრატეგია.

პრინციპი, რომელიც კარნახობს, რომ მოთამაშეებმა აირჩიონ ყველაზე "ფრთხილი" მინიმქსის და მაქსიმინის სტრატეგიები, ეწოდება პრინციპი. მინიმაქსი.ეს პრინციპი გამომდინარეობს გონივრული დაშვებიდან, რომ თითოეული მოთამაშე ცდილობს მიაღწიოს მიზნის საპირისპირო მიზნებს, ვიდრე მისი მოწინააღმდეგე. მოდით განვსაზღვროთ თამაშის ქვედა და ზედა ფასები და შესაბამისი სტრატეგიები პრობლემა 12.1-ში. განვიხილოთ გადახდის მატრიცა

12.1 პრობლემისგან. სტრატეგიის არჩევისას L, (მატრიცის პირველი რიგი) მინიმალური მოგებაუდრის a, =min(-l; 1) = -1 და შეესაბამება მოთამაშის β1 სტრატეგიას IN.სტრატეგიის არჩევისას ლ 2 (მატრიცის მეორე რიგი) მინიმალური მოგებაა ა 2 = min(l; -1) = -1, ეს მიიღწევა სტრატეგიით IN.,.

საკუთარი თავის გარანტია მაქსიმალური მოგებანებისმიერი მოთამაშის სტრატეგიისთვის IN, ე.ი. თამაშის დაბალი ფასი a = max(a, a2) = = max(-l; -1) = -1, მოთამაშე აშეუძლია აირჩიოს ნებისმიერი სტრატეგია: Aj ან ა 2, ე.ი. მისი ნებისმიერი სტრატეგია არის მაქსიმუმი.

სტრატეგიის არჩევა B, (სვეტი 1), მოთამაშე INესმის, რომ მოთამაშე აუპასუხებს სტრატეგიით ა 2 თქვენი მოგების მაქსიმიზაციისთვის (წაგება IN).შესაბამისად, მოთამაშის მაქსიმალური დანაკარგია INროდესაც ის ირჩევს B სტრატეგიას, უდრის β, = შემოწმება (-1; 1) = 1.

ანალოგიურად, B მოთამაშის მაქსიმალური წაგება (გამარჯვება ა) როდესაც ის ირჩევს სტრატეგიას B2 (სვეტი 2) უდრის β2 = max(l; -1) = 1.

ამრიგად, ნებისმიერი მოთამაშის სტრატეგიისთვის ა B მოთამაშის გარანტირებული მინიმალური წაგება უდრის β = = πιίη(β1, β2) = min(l; 1) = 1 - თამაშის ზედა ფასი.

B მოთამაშის ნებისმიერი სტრატეგია არის მინიმალური. ცხრილის დამატების შემდეგ 12.1 ხაზი β; და სვეტი a;, ვიღებთ ცხრილს. 12.2. დამატებითი სტრიქონების და სვეტების კვეთაზე ჩვენ დავწერთ თამაშების ზედა და ქვედა ფასებს.

ცხრილი 12.2

ზემოთ განხილულ პრობლემაში 12.1, თამაშის ზედა და ქვედა ფასები განსხვავებულია: a F β.

თუ თამაშის ზედა და ქვედა ფასები ემთხვევა, მაშინ ზოგადი მნიშვნელობათამაშის ზედა და ქვედა ფასები α = β = υ ეწოდება თამაშის სუფთა ფასი,ან თამაშის ფასად.თამაშის ფასის შესაბამისი მინიმალური სტრატეგიებია ოპტიმალური სტრატეგიები,და მათი მთლიანობა - ოპტიმალური გადაწყვეტა,ან გადაწყვეტილებათამაშები. ამ შემთხვევაში მოთამაშე აიღებს მაქსიმალურ გარანტიას (მოთამაშის ქცევისგან დამოუკიდებლად) IN)ანაზღაურება არის υ, და მოთამაშე INაღწევს გარანტირებულ მინიმალურ (მიუხედავად A მოთამაშის ქცევისა) წაგებას υ. ისინი ამბობენ, რომ თამაშის გამოსავალი აქვს სტაბილურობა,იმათ. თუ ერთ-ერთი მოთამაშე იცავს მას ოპტიმალური სტრატეგია, მაშინ სხვისთვის არ შეიძლება იყოს მომგებიანი მისი ოპტიმალური სტრატეგიიდან გადახვევა.

რამდენიმე სუფთა სტრატეგია ა.და B. იძლევა თამაშს ოპტიმალურ გადაწყვეტას, თუ და მხოლოდ იმ შემთხვევაში, თუ შესაბამისი ელემენტი y ერთდროულად ყველაზე დიდია თავის სვეტში და ყველაზე პატარა მწკრივში. ამ სიტუაციას, თუ ის არსებობს, ე.წ უნაგირის წერტილი(მსგავსი უნაგირის ზედაპირისა, რომელიც ერთი მიმართულებით იხრება მაღლა და მეორე მიმართულებით ქვემოთ).

აღვნიშნოთ A*და IN*– სუფთა სტრატეგიების წყვილი, რომელიც ახერხებს თამაშის გადაწყვეტას უნაგირის წერტილის პრობლემაში. მოდით წარმოგიდგინოთ პირველი მოთამაშის ანაზღაურების ფუნქცია თითოეული წყვილი სტრატეგიისთვის: P(A:, IN-) = და y. შემდეგ, ოპტიმალური მდგომარეობიდან უნაგირის წერტილში, ორმაგი უტოლობა მოქმედებს: P(Aj, B*)<Р(А*, В*)<Р(А", В ), რაც ყველასთვის სამართლიანია მე = 1, 2, ..., m;j = 1, 2, ..., პ.მართლაც, სტრატეგიის არჩევანი ა* პირველი მოთამაშე ოპტიმალური სტრატეგიით IN"მეორე მოთამაშე მაქსიმალურად ანაზღაურებს მინიმალურ შესაძლო ანაზღაურებას: P(A*, ბ")> P(Aგ IN"),და სტრატეგიის არჩევა B"მეორე მოთამაშე, პირველის ოპტიმალური სტრატეგიით, ამცირებს მაქსიმალურ დანაკარგს: P(D, IN*)<Р(А", В).

12.2. განსაზღვრეთ თამაშის ქვედა და ზედა ფასი, რომელიც მოცემულია გადახდის მატრიცით

აქვს თუ არა თამაშს უნაგირის წერტილი?

ცხრილი 12. 3

გამოსავალი.მოსახერხებელია განახორციელოს ყველა გამოთვლა ცხრილში, რომელიც, გარდა მატრიცისა R,შეყვანილია სვეტი a; და სიმებიანი)