მათემატიკური მეთოდები და მოდელები ეკონომიკაში

მატრიცული თამაშები

შესავალი

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

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

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

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

თამაში სუფთა სტრატეგიებში

განვიხილოთ თამაში ორი მოთამაშით ადა IN.დავუშვათ მოთამაშე აᲛას აქვს მსტრატეგიები A 1, A 2, ..., A mდა მოთამაშე INᲛას აქვს ნსტრატეგიები B 1 , B 2 , … , B n .ჩვენ ვვარაუდობთ, რომ მოთამაშის არჩევანია ასტრატეგიები Და მე ,მაგრამ მოთამაშე INსტრატეგიები ბჯცალსახად განსაზღვრავს თამაშის შედეგს, ე.ი. გამარჯვება აიჯმოთამაშე ადა გამარჯვება ბ ijმოთამაშე IN.Აქ i=1,2,…,m, j=1,2,…,n.

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

b ij =-a ij

ეს თანასწორობა ნიშნავს, რომ ერთ-ერთი მოთამაშის მოგება უდრის მეორის დაკარგვას. ამ შემთხვევაში, საკმარისია გავითვალისწინოთ მხოლოდ ერთ-ერთი მოთამაშის ანაზღაურება, მაგალითად, მოთამაშის ა.

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

ამ მატრიცის რიგები შეესაბამება მოთამაშის სტრატეგიებს A,და სვეტები არის მოთამაშის სტრატეგიები IN. IN ზოგადი შემთხვევაამ თამაშს ჰქვია (m×n)-თამაში.

მაგალითი 1ორი მოთამაშე ადა INჩააგდოს მონეტა. თუ მონეტის მხარეები ერთნაირია, მაშინ გამარჯვებულია ა, ე.ი. მოთამაშე INიხდის მოთამაშეს არაღაც თანხა 1-ის ტოლია და თუ ისინი არ ემთხვევა, მაშინ მოთამაშე B იგებს, ე.ი. პირიქით, მოთამაშე აიხდის მოთამაშეს INიგივე თანხა , ტოლია 1. შექმენით გადახდის მატრიცა.

გამოსავალი.დავალების მიხედვით

მართალია ფიზიკა-ტექნიკური ფაკულტეტი დავამთავრე, მაგრამ უნივერსიტეტში თამაშების თეორია არ წამიკითხეს. მაგრამ, რადგან სტუდენტობის წლებში ბევრს ვთამაშობდი, ჯერ უპირატესობაზე, შემდეგ კი ბრიჯზე, დამაინტერესა თამაშების თეორიამ და ავითვისე პატარა სახელმძღვანელო. და ახლახან საიტის მკითხველმა მიხაილმა გადაჭრა თამაშის თეორიის პრობლემა. გავაცნობიერე, რომ დავალება მაშინვე არ დამცა, გადავწყვიტე, მეხსიერებაში განმეახლა თამაშების თეორიის ცოდნა. გთავაზობთ პატარა წიგნს - თამაშების თეორიის ელემენტების პოპულარული პრეზენტაცია და მატრიცული თამაშების ამოხსნის რამდენიმე მეთოდი. იგი თითქმის არ შეიცავს მტკიცებულებებს და ასახავს თეორიის ძირითად დებულებებს მაგალითებით. წიგნი დაწერა მათემატიკოსმა და მეცნიერების პოპულარიზაციამ ელენა სერგეევნა ვენცელმა. საბჭოთა ინჟინრების რამდენიმე თაობა სწავლობდა მისი სახელმძღვანელოდან "ალბათობის თეორია". ელენა სერგეევნამ ასევე დაწერა რამდენიმე ლიტერატურული ნაწარმოები ფსევდონიმით I. Grekova.

ელენა ვენცელი. თამაშის თეორიის ელემენტები. – M.: Fizmatgiz, 1961. – 68გვ.

ჩამოტვირთვა მოკლე მიმოხილვაფორმატში ან

§ 1. თამაშის თეორიის საგანი. Ძირითადი ცნებები

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

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

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

თამაში განსხვავდება რეალური კონფლიქტური სიტუაციისგან იმით, რომ იგი თამაშობს შესაბამისად გარკვეული წესები. კაცობრიობა დიდი ხანია იყენებს კონფლიქტური სიტუაციების ისეთ ფორმალიზებულ მოდელებს, რომლებიც ამ სიტყვის პირდაპირი გაგებით თამაშებია. მაგალითებია ჭადრაკი, ქვები, კარტი და ა.შ. ყველა ეს თამაში არის შეჯიბრის ხასიათი, რომელიც მიმდინარეობს ცნობილი წესებიდა დამთავრებული ამა თუ იმ მოთამაშის „გამარჯვებით“ (გამარჯვებით).

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

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

თამაშის თეორიის ელემენტარული პრეზენტაცია რამდენიმე ძირითადი ცნების ჩამოყალიბებით დავიწყოთ. განვიხილავთ წყვილთა თამაშს, რომელშიც ორი მოთამაშე A და B მონაწილეობს საპირისპირო ინტერესებით. "თამაშში" ვგულისხმობთ მოვლენას, რომელიც შედგება A და B მხარეების მოქმედებების სერიისგან. იმისათვის, რომ თამაში დაექვემდებაროს მათემატიკურ ანალიზს, თამაშის წესები ზუსტად უნდა იყოს ჩამოყალიბებული. „თამაშის წესები“ ნიშნავს პირობების სისტემას, რომელიც არეგულირებს ორივე მხარის მოქმედების შესაძლო ვარიანტებს, ინფორმაციის რაოდენობას, რომელსაც აქვს თითოეული მხარე მეორის ქცევის შესახებ, „მოძრაობების“ მონაცვლეობის თანმიმდევრობას (ინდივიდუალური გადაწყვეტილებების დროს მიღებული თამაში), ისევე როგორც თამაშის შედეგი ან შედეგი, რომელიც იწვევს ამ სვლების კომპლექტს. ეს შედეგი (მოგება ან წაგება) ყოველთვის არ არის რაოდენობრივი, მაგრამ, როგორც წესი, შესაძლებელია, გაზომვის გარკვეული მასშტაბის დაყენებით, მისი გამოხატვა გარკვეული რიცხვით. მაგალითად, ჭადრაკის თამაშში მოგებას შეიძლება პირობითად მიენიჭოს მნიშვნელობა +1, წაგება -1, ფრე 0.

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

ვინაიდან ნულოვანი ჯამის თამაშში ერთ-ერთი მოთამაშის ანაზღაურება უდრის მეორის ანაზღაურებას საპირისპირო ნიშნით, მაშინ, ცხადია, ასეთი თამაშის გაანალიზებისას შეიძლება განიხილოს მხოლოდ ერთი მოთამაშის ანაზღაურება. ეს იყოს, მაგალითად, მოთამაშე A. მომავალში, მოხერხებულობისთვის, A მხარეს პირობითად დავარქმევთ „ჩვენ“, ხოლო B მხარეს - „მოწინააღმდეგეს“.

ამ შემთხვევაში მხარე A („ჩვენ“) ყოველთვის ჩაითვლება „მოგებულად“, ხოლო B მხარე („მოწინააღმდეგე“) „წაგებულად“. ეს ფორმალური პირობა აშკარად არ ნიშნავს რეალურ უპირატესობას პირველი მოთამაშისთვის; ადვილი მისახვედრია, რომ იგი იცვლება მისი საპირისპიროთი, თუ ანაზღაურების ნიშანი შებრუნებულია.

ჩვენ წარმოვადგენთ თამაშის განვითარებას დროულად, როგორც თანმიმდევრული ეტაპების ან „მოძრაობების“ სერიისგან შემდგარ. თამაშის თეორიაში ნაბიჯი არის თამაშის წესებით გათვალისწინებული ერთ-ერთი ვარიანტის არჩევა. მოძრაობები იყოფა პირად და შემთხვევით. პირადი ნაბიჯი არის ერთ-ერთი მოთამაშის მიერ შეგნებული არჩევანი მოცემულ სიტუაციაში შესაძლო ერთ-ერთი ნაბიჯისა და მისი განხორციელება. პირადი სვლის მაგალითია ჭადრაკის თამაშის ნებისმიერი სვლა. შემდეგი ნაბიჯის შესრულებისას მოთამაშე შეგნებულად არჩევს ერთ-ერთ ვარიანტს, რომელიც შესაძლებელია დაფაზე ფიგურების მოცემული მოწყობისთვის. ნაკრები პარამეტრებიყოველი პირადი ნაბიჯი რეგულირდება თამაშის წესებით და დამოკიდებულია ორივე მხარის წინა სვლების მთლიანობაზე.

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

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

თამაშები კლასიფიცირდება არა მხოლოდ სვლების ბუნებით (პირადი, შემთხვევითი), არამედ თითოეული მოთამაშისთვის ხელმისაწვდომი ინფორმაციის ბუნებით და მოცულობით სხვის ქმედებებთან დაკავშირებით. თამაშების განსაკუთრებულ კლასს წარმოადგენს ე.წ სრული ინფორმაცია". თამაში სრული ინფორმაციით არის თამაში, რომელშიც თითოეულმა მოთამაშემ იცის ყველა წინა ნაბიჯის შედეგები, როგორც პირადი, ასევე შემთხვევითი, ყოველი პირადი ნაბიჯის დროს. სრული ინფორმაციის მქონე თამაშების მაგალითებია ჭადრაკი, ქვები და ცნობილი თამაში ტიკ-ტაკ-ტო.

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

თამაშის თეორიის ერთ-ერთი ძირითადი ცნებაა „სტრატეგიის“ ცნება. მოთამაშის სტრატეგია არის წესების ერთობლიობა, რომელიც ცალსახად განსაზღვრავს არჩევანს მოცემული მოთამაშის თითოეული პირადი ნაბიჯისთვის, თამაშის დროს შექმნილი სიტუაციიდან გამომდინარე. როგორც წესი, გადაწყვეტილებას (არჩევანს) თითოეული პერსონალური ნაბიჯისთვის მოთამაშე იღებს თავად თამაშის დროს, არსებული კონკრეტული სიტუაციიდან გამომდინარე. თუმცა, თეორიულად, საქმე არ იცვლება, თუ წარმოვიდგენთ, რომ ყველა ამ გადაწყვეტილებას მოთამაშე წინასწარ იღებს. ამისათვის მოთამაშემ წინასწარ უნდა შეადგინოს თამაშის მსვლელობისას ყველა შესაძლო სიტუაციის სია და თითოეული მათგანისთვის საკუთარი გადაწყვეტა. პრინციპში (თუ პრაქტიკულად არა) ეს შესაძლებელია ნებისმიერი თამაშისთვის. თუ ასეთი გადაწყვეტილების სისტემა მიიღება, ეს ნიშნავს, რომ მოთამაშემ აირჩია გარკვეული სტრატეგია.

მოთამაშეს, რომელმაც აირჩია სტრატეგია, ახლა არ შეუძლია თამაშში მონაწილეობა პირადად, მაგრამ ჩაანაცვლებს მის მონაწილეობას წესების სიით, რომელსაც გამოიყენებს მისთვის რაიმე უინტერესო ადამიანი (მსაჯი). სტრატეგია ასევე შეიძლება მიეცეს ავტომატს კონკრეტული პროგრამის სახით. ასე თამაშობენ ამჟამად კომპიუტერულ ჭადრაკს. იმისათვის, რომ „სტრატეგიის“ ცნებას აზრი ჰქონდეს, თამაშში უნდა იყოს პირადი სვლები; მხოლოდ შემთხვევითი სვლებისგან შემდგარ თამაშებში არ არსებობს სტრატეგიები.

შესაძლო სტრატეგიების რაოდენობის მიხედვით, თამაშები იყოფა "სასრულ" და "უსასრულო". თამაში ითვლება სასრულად, თუ თითოეულ მოთამაშეს აქვს მხოლოდ სასრული რაოდენობის სტრატეგიები. ფინალური თამაში, რომელშიც მოთამაშე A თამაშობს მსტრატეგიები და მოთამაშე B ნსტრატეგიებს mxn თამაშს უწოდებენ.

განვიხილოთ თამაში mxn ორი მოთამაშისგან A და B ("ჩვენ" და "მოწინააღმდეგე"). ჩვენ აღვნიშნავთ ჩვენს სტრატეგიებს A 1 , A 2 , …, A m მტრის სტრატეგიებს B 1 , B 2 , …, B n . თითოეულმა მხარემ აირჩიოს გარკვეული სტრატეგია; ჩვენთვის ეს იქნება A i, მოწინააღმდეგისთვის B j. თუ თამაში შედგება მხოლოდ პირადი სვლებისგან, მაშინ A i, B j სტრატეგიების არჩევანი ცალსახად განსაზღვრავს თამაშის შედეგს - ჩვენს ანაზღაურებას. ავღნიშნოთ როგორც ij. თუ თამაში შეიცავს, გარდა პირადი, შემთხვევით სვლებს, მაშინ ანაზღაურება წყვილი სტრატეგიისთვის A i, B j არის შემთხვევითი მნიშვნელობა, რომელიც დამოკიდებულია ყველა შემთხვევითი სვლის შედეგზე. ამ შემთხვევაში, მოსალოდნელი ანაზღაურების ბუნებრივი შეფასება არის მისი საშუალო მნიშვნელობა (მათემატიკური მოლოდინი). ერთი და იგივე ნიშნით აღვნიშნავთ როგორც თავად ანაზღაურებას (თამაშში შემთხვევითი სვლების გარეშე), ასევე მის საშუალო მნიშვნელობას (შემთხვევითი სვლებით თამაშში).

გაგვაგებინეთ ანაზღაურების ij მნიშვნელობები (ან საშუალო ანაზღაურება) თითოეული წყვილი სტრატეგიისთვის. მნიშვნელობები შეიძლება დაიწეროს მართკუთხა ცხრილის (მატრიცის) სახით, რომლის რიგები შეესაბამება ჩვენს სტრატეგიებს (A i), ხოლო სვეტები შეესაბამება მოწინააღმდეგის სტრატეგიებს (B j). ასეთ ცხრილს უწოდებენ ანაზღაურების მატრიცას ან უბრალოდ თამაშის მატრიცას. თამაშის მატრიცა mxn ნაჩვენებია ნახ. 1.

ბრინჯი. 1. mxn მატრიცა

თამაშის მატრიცას შევამოკლებთ როგორც ‖a ij ‖. განვიხილოთ თამაშების რამდენიმე ელემენტარული მაგალითი.

მაგალითი 1ორი მოთამაშე A და B, ერთმანეთის შეხედვის გარეშე, მაგიდაზე ათავსებენ მონეტას პირისპირ ან კუდებს, როგორც მათ მიზანშეწონილად თვლიან. თუ მოთამაშეებმა აირჩიეს ერთი და იგივე მხარე (ორივეს აქვს გერბი ან ორივეს აქვს კუდი), მაშინ მოთამაშე A იღებს ორივე მონეტას; წინააღმდეგ შემთხვევაში, მათ იღებს მოთამაშე B. საჭიროა თამაშის ანალიზი და მისი მატრიცა. გამოსავალი. თამაში შედგება მხოლოდ ორი სვლისგან: ჩვენი მხრივ და მოწინააღმდეგის მორიგე, ორივე პირადი. თამაში არ მიეკუთვნება თამაშებს სრული ინფორმაციით, რადგან გადაადგილების მომენტში მოთამაშემ არ იცის რა გააკეთა მეორემ. ვინაიდან თითოეულ მოთამაშეს აქვს მხოლოდ ერთი პირადი ნაბიჯი, მოთამაშის სტრატეგია არის არჩევანი ამ ერთ პერსონალურ მოძრაობაში.

ჩვენ გვაქვს ორი სტრატეგია: A 1 - აირჩიე გერბი და A 2 - აირჩიე კუდები; მოწინააღმდეგეს აქვს იგივე ორი სტრატეგია: B 1 - გერბი და B 2 - კუდები. ამრიგად, ეს თამაშიარის 2x2 თამაში. მონეტის მოგებას განვიხილავთ, როგორც +1. თამაშის მატრიცა:

ამ თამაშის მაგალითით, რაც არ უნდა ელემენტარული იყოს, თამაშის თეორიის ზოგიერთი არსებითი იდეის გარკვევა შეიძლება. ჯერ დავუშვათ, რომ მოცემული თამაში შესრულებულია მხოლოდ ერთხელ. მაშინ, ცხადია, სხვაზე უფრო გონივრულ მოთამაშეთა რაიმე „სტრატეგიაზე“ საუბარი აზრი არ აქვს. თითოეულ მოთამაშეს ერთი და იგივე მიზეზით შეუძლია მიიღოს ნებისმიერი გადაწყვეტილება. თუმცა, როდესაც თამაში მეორდება, სიტუაცია იცვლება.

მართლაც, დავუშვათ, რომ ჩვენ (მოთამაშე A) ჩვენთვის ავირჩიეთ გარკვეული სტრატეგია (ვთქვათ, A 1) და მივყვეთ მას. შემდეგ, პირველი რამდენიმე სვლის შედეგების მიხედვით, მოწინააღმდეგე გამოიცნობს ჩვენს სტრატეგიას და უპასუხებს მას ჩვენთვის ყველაზე ნაკლებად ხელსაყრელი გზით, ე.ი. აირჩიეთ კუდები. ჩვენთვის აშკარად წამგებიანია ყოველთვის რომელიმე ერთი სტრატეგიის გამოყენება; წაგებული რომ არ ვიყოთ, ხან გერბი უნდა ავირჩიოთ, ხან კუდები. თუმცა, თუ გერბებსა და კუდებს გარკვეული თანმიმდევრობით შევცვლით (მაგალითად, ერთის მეშვეობით), მტერსაც შეუძლია გამოიცნოს ამის შესახებ და უპასუხოს ამ სტრატეგიას ჩვენთვის ყველაზე ცუდი გზით. ცხადია, საიმედო გზა იმის უზრუნველსაყოფად, რომ მტერმა არ იცოდეს ჩვენი სტრატეგია არის არჩევანის ორგანიზება ყოველ ნაბიჯზე, როდესაც ჩვენ თვითონ არ ვიცით ეს წინასწარ (ამის უზრუნველყოფა შეიძლება, მაგალითად, მონეტის გადაყრით). ამრიგად, ინტუიციური მსჯელობის საშუალებით მივუდგებით თამაშის თეორიის ერთ-ერთ არსებით ცნებას – „შერეული სტრატეგიის“ კონცეფციას, ე.ი. ისეთი, რომ „სუფთა“ სტრატეგიები – ინ ამ საქმეს A 1 და A 2 - ალტერნატიული შემთხვევითი გარკვეული სიხშირეებით. ამ მაგალითში, სიმეტრიის მიზეზების გამო, წინასწარ ცხადია, რომ A 1 და A 2 სტრატეგიები უნდა იცვლებოდეს ერთი და იგივე სიხშირით; უფრო რთულ თამაშებში გამოსავალი შეიძლება შორს იყოს ტრივიალურისგან.

მაგალითი 2მოთამაშეები A და B ერთდროულად და ერთმანეთისგან დამოუკიდებლად წერენ სამი რიცხვიდან ერთს: 1, 2 ან 3. თუ დაწერილი რიცხვების ჯამი ლუწია, მაშინ B იხდის A-ს ამ თანხას რუბლით; თუ ის კენტია, მაშინ, პირიქით, A იხდის B ამ თანხას. საჭიროა თამაშის ანალიზი და მისი მატრიცის გაკეთება.

გამოსავალი. თამაში შედგება ორი სვლისგან; ორივე პირადულია. გვაქვს (A) სამი სტრატეგია: A 1 - ჩაწერეთ 1; და 2 - ჩაწერეთ 2; A 3 - ჩაწერეთ 3. მოწინააღმდეგეს (B) აქვს იგივე სამი სტრატეგია. თამაში არის 3×3 თამაში:

ცხადია, როგორც წინა შემთხვევაში, მტერს შეუძლია უპასუხოს ნებისმიერ სტრატეგიას, რომელსაც ჩვენ ვირჩევთ ჩვენთვის ყველაზე ცუდი გზით. მართლაც, თუ ჩვენ ვირჩევთ, მაგალითად, სტრატეგიას A 1, მტერი მას ყოველთვის უპასუხებს B 2 სტრატეგიით; სტრატეგიაზე A 2 - სტრატეგია B 3; სტრატეგიაზე A 3 - სტრატეგია B 2 ; ამდენად, გარკვეული სტრატეგიის ნებისმიერი არჩევანი აუცილებლად მიგვიყვანს წაგებამდე (თუმცა არ უნდა დაგვავიწყდეს, რომ მტერიც იმავე გასაჭირშია). ამ თამაშის გადაწყვეტა (ანუ ორივე მოთამაშისთვის ყველაზე მომგებიანი სტრატეგიების ნაკრები) მოცემულია § 5-ში.

მაგალითი 3ჩვენ გვაქვს სამი სახის იარაღი: A 1, A 2, A 3; მტერს ჰყავს სამი ტიპის თვითმფრინავი: B 1, B 2, B 3. ჩვენი ამოცანაა თვითმფრინავის დარტყმა; მტრის ამოცანაა მისი დაუმარცხებლად შენარჩუნება. A 1 იარაღის გამოყენებისას თვითმფრინავები B 1 , B 2 , B 3 მოხვდებიან შესაბამისად 0,9, 0,4 და 0,2 ალბათობით; A 2-ით შეიარაღებისას - 0,3, 0,6 და 0,8 ალბათობით; A 3-ით შეიარაღებისას - 0,5, 0,7 და 0,2 ალბათობით. საჭიროა სიტუაციის ჩამოყალიბება თამაშის თეორიის თვალსაზრისით.

გამოსავალი. სიტუაცია შეიძლება განიხილებოდეს, როგორც 3x3 თამაში ორი პირადი სვლით და ერთი შემთხვევითი ნაბიჯით. ჩვენი პირადი ნაბიჯი არის იარაღის ტიპის არჩევანი; მტრის პირადი მოძრაობა - თვითმფრინავის არჩევანი ბრძოლაში მონაწილეობისთვის. შემთხვევითი მოძრაობა - იარაღის გამოყენება; ეს ნაბიჯი შეიძლება დასრულდეს თვითმფრინავის დამარცხებით ან არდამარცხებით. ჩვენი ანაზღაურება არის ერთი, თუ თვითმფრინავი მოხვდა, და ნულოვანი წინააღმდეგ შემთხვევაში. ჩვენი სტრატეგიები არის სამი იარაღის ვარიანტი; მტრის სტრატეგიები - თვითმფრინავის სამი ვარიანტი. ყოველი მოცემული წყვილი სტრატეგიისთვის ანაზღაურების საშუალო ღირებულება სხვა არაფერია, თუ არა მოცემული იარაღით მოცემულ თვითმფრინავზე დარტყმის ალბათობა. თამაშის მატრიცა:

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

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

§ 2. თამაშის ქვედა და ზედა ფასი. "მინიმქსის" პრინციპი

განვიხილოთ თამაში mxn მატრიცით, როგორც ნახ. 1. ი ასოთი აღვნიშნავთ ჩვენი სტრატეგიის რიცხვს; ასო j არის მოწინააღმდეგის სტრატეგიის ნომერი. ჩვენ საკუთარ თავს დავალება გვაქვს განვსაზღვროთ ჩვენი ოპტიმალური სტრატეგია. მოდით გავაანალიზოთ თითოეული ჩვენი სტრატეგია თანმიმდევრულად, დაწყებული A 1-ით.

A i სტრატეგიის არჩევისას ყოველთვის უნდა ველოდოთ, რომ მოწინააღმდეგე უპასუხებს მას ერთ-ერთი B j სტრატეგიით, რომლისთვისაც ჩვენი ანაზღაურება a ij მინიმალურია. მოდით განვსაზღვროთ ეს ანაზღაურებადი ღირებულება, ე.ი. რიცხვებიდან ყველაზე პატარა a ij in მე-მე ხაზი. აღნიშნეთ α i:

აქ ნიშანი min (მინიმუმი j-ში) აღნიშნავს ამ პარამეტრის მნიშვნელობების მინიმუმს ყველა შესაძლო j-სთვის. ჩამოვწეროთ α i რიცხვები; მატრიცის გვერდით მარჯვნივ, როგორც დამატებითი სვეტი:

ნებისმიერი A i სტრატეგიის არჩევისას უნდა გავითვალისწინოთ ის, რომ მოწინააღმდეგის გონივრული ქმედებების შედეგად α i-ზე მეტს არ მივიღებთ. ბუნებრივია, ვიმოქმედოთ ყველაზე ფრთხილად და ვიმედოვნოთ ყველაზე გონივრულ მოწინააღმდეგეზე (ანუ ყოველგვარი რისკის თავიდან აცილება), ჩვენ უნდა შევჩერდეთ სტრატეგიაზე, რომლის რიცხვი α i არის მაქსიმალური. ჩვენ აღვნიშნავთ ამ მაქსიმალურ მნიშვნელობას α-ით:

ან, ფორმულის (2.1) გათვალისწინებით,

მნიშვნელობა α ეწოდება დაბალი ფასითამაში, წინააღმდეგ შემთხვევაში - maximin payoff ან უბრალოდ maximin. რიცხვი α დევს მატრიცის გარკვეულ მწკრივში; A მოთამაშის სტრატეგიას, რომელიც შეესაბამება ამ ხაზს, ეწოდება მაქსიმინის სტრატეგია. ცხადია, თუ ჩვენ ვიცავთ მაქსიმინის სტრატეგიას, მაშინ გარანტირებული გვაქვს ანაზღაურება მოწინააღმდეგის ნებისმიერი ქცევისთვის, მინიმუმ α-ზე ნაკლები. ამიტომ, α-ს მნიშვნელობას უწოდებენ "თამაშის ქვედა ფასს". ეს არის გარანტირებული მინიმუმი, რომელიც შეგვიძლია მივაწოდოთ საკუთარ თავს ყველაზე ფრთხილი („გადაზღვევის“) სტრატეგიით.

ცხადია, მსგავსი მსჯელობა შეიძლება განხორციელდეს ოპონენტ B-სთვისაც. ვინაიდან ოპონენტი დაინტერესებულია ჩვენი ანაზღაურებით მინიმუმამდე შემცირებით, მან უნდა გადახედოს მის თითოეულ სტრატეგიას ამ სტრატეგიისთვის მაქსიმალური ანაზღაურების თვალსაზრისით. ამიტომ, მატრიცის ბოლოში, ჩვენ დავწერთ მაქსიმალურ მნიშვნელობებს თითოეული სვეტისთვის:

და იპოვეთ β j-ის მინიმუმი:

β-ის მნიშვნელობა ეწოდება უმაღლესი ფასითამაშები, წინააღმდეგ შემთხვევაში - "მინიმქსი". მოწინააღმდეგის სტრატეგიას, რომელიც შეესაბამება მინიმალური ანაზღაურებას, ეწოდება მისი "მინიმაქსის სტრატეგია". მისი ყველაზე ფრთხილი მინიმაქსის სტრატეგიის დაცვით, ოპონენტი თავის თავს გარანტიას აძლევს შემდეგს: რაც არ უნდა გავაკეთოთ მის წინააღმდეგ, ის ნებისმიერ შემთხვევაში დაკარგავს β-ზე მეტ თანხას. სიფრთხილის პრინციპს, რომელიც კარნახობს მოთამაშეებს შესაბამისი სტრატეგიების არჩევას (მაქსიმუმი და მინიმალური), ხშირად უწოდებენ "მინიმქსის პრინციპს" თამაშის თეორიაში და მის გამოყენებაში. მოთამაშეთა ყველაზე ფრთხილ მაქსიმ და მინიმქს სტრატეგიებს ზოგჯერ მოიხსენიებენ ზოგადი ტერმინით „მინიმაქსის სტრატეგიები“.

როგორც მაგალითები, ჩვენ განვსაზღვრავთ თამაშის ქვედა და ზედა ფასებს და მინიმალური სტრატეგიებს 1-ლი ნაწილის 1, 2 და 3 მაგალითებისთვის.

მაგალითი 1§ 1-ის მაგალითში მოცემულია თამაში შემდეგი მატრიცით:

ვინაიდან α i და β j მნიშვნელობები მუდმივია და ტოლია –1 და +1, შესაბამისად, თამაშის ქვედა და ზედა ფასებიც უდრის –1 და +1: α = –1, β = +1. . A მოთამაშის ნებისმიერი სტრატეგია არის მისი მაქსიმუმი, ხოლო B მოთამაშის ნებისმიერი სტრატეგია არის მისი მინიმალური სტრატეგია. დასკვნა ტრივიალურია: თავისი რომელიმე სტრატეგიის დაცვით, მოთამაშე A-ს შეუძლია გარანტია, რომ წააგებს არაუმეტეს 1-ისა; იგივეს გარანტია შეუძლია B მოთამაშემ.

მაგალითი 2§ 1-ის მე-2 მაგალითში მოცემულია თამაში მატრიცით:

თამაშის დაბალი ფასი α = –3; თამაშის ზედა ღირებულება არის β = 4. ჩვენი მაქსიმალური სტრატეგია არის A 1; მისი სისტემატური გამოყენებით, ჩვენ შეგვიძლია დარწმუნებით ველოდოთ მინიმუმ -3 მოგებას (მაქსიმუმ 3 წაგებას). მოწინააღმდეგის მინიმალური სტრატეგია არის ნებისმიერი სტრატეგია B 1 და B 2; მათი სისტემატიურად გამოყენების შემთხვევაში, მას შეუძლია მინიმუმ გარანტირებული იყოს, რომ დაკარგავს არაუმეტეს 4-ს. თუ ჩვენ გადავუხვიეთ ჩვენი მაქსიმალური სტრატეგიისგან (მაგალითად, ავირჩიოთ სტრატეგია A 2), მტერს შეუძლია ამის გამო "დაგვსაჯოს" სტრატეგია B 3 და გამოყენებით. ჩვენი ანაზღაურების შემცირება -5-მდე; ანალოგიურად, მოწინააღმდეგის უკან დახევამ მისი მინიმალური სტრატეგიიდან შეიძლება გაზარდოს მისი წაგება 6-მდე.

მაგალითი 3§ 1-ის მე-3 მაგალითში მოცემულია თამაში მატრიცით:

თამაშის დაბალი ფასი α = 0.3; ზედა შეფასების თამაში β = 0.7. ჩვენი ყველაზე ფრთხილი (მაქსიმალური) სტრატეგია არის A 2; A 2 იარაღის გამოყენებით, ჩვენ გარანტიას ვაძლევთ, რომ თვითმფრინავს საშუალოდ დავარტყამთ ყველა შემთხვევის არანაკლებ 0,3-ში. მოწინააღმდეგის ყველაზე ფრთხილი (მინიმქსი) სტრატეგიაა B 2; ამ თვითმფრინავის გამოყენებით, მტერი შეიძლება იყოს დარწმუნებული, რომ მას მოხვდება არაუმეტეს 0,7 შემთხვევაში.

ბოლო მაგალითის გამოყენებით, მოსახერხებელია მინიმალური სტრატეგიების ერთი მნიშვნელოვანი თვისების დემონსტრირება - მათი არასტაბილურობა. მოდით გამოვიყენოთ ჩვენი ყველაზე ფრთხილი (მაქსიმალური) სტრატეგია A 2, ხოლო მოწინააღმდეგე - მისი ყველაზე ფრთხილი (მინიმქსი) სტრატეგია B 2. სანამ ორივე მოწინააღმდეგე იცავს ამ სტრატეგიებს, საშუალო ანაზღაურება არის 0.6; ის აღემატება თამაშის დაბალ ფასს, მაგრამ ნაკლებია, ვიდრე ზედა. ახლა დავუშვათ, რომ მტერმა გაიგო, რომ ჩვენ ვიყენებთ სტრატეგიას A 2; ის დაუყოვნებლივ უპასუხებს მას B 1 სტრატეგიით და შეამცირებს ანაზღაურებას 0.3-მდე. თავის მხრივ, ჩვენ გვაქვს კარგი პასუხი სტრატეგიაზე B 1: სტრატეგია A 1, რომელიც გვაძლევს ანაზღაურებას 0.9 და ა.შ.

ამრიგად, სიტუაცია, რომელშიც ორივე მოთამაშე იყენებს მინიმქს სტრატეგიებს, არასტაბილურია და შეიძლება დაირღვეს მოპირდაპირე მხარის სტრატეგიის შესახებ მიღებული ინფორმაციით. თუმცა, არის თამაშები, რომლებისთვისაც მინიმალური სტრატეგიები სტაბილურია. ეს ის თამაშებია, რომლებშიც დაბალი ფასი უდრის ზედას: α = β. თუ თამაშის ქვედა ფასი უდრის ზედას, მაშინ მათ საერთო მნიშვნელობას უწოდებენ თამაშის წმინდა ფასს (ზოგჯერ მხოლოდ თამაშის ფასი), ჩვენ მას აღვნიშნავთ ν ასოთი.

განვიხილოთ მაგალითი. დაე, 4×4 თამაში იყოს მოცემული მატრიცით:

ვიპოვოთ თამაშის უფრო დაბალი ფასი: α = 0.6. ვიპოვოთ თამაშის ზედა ფასი: β = 0.6. ისინი ერთნაირი აღმოჩნდა, შესაბამისად, თამაშს აქვს წმინდა ღირებულება α = β = ν = 0.6. ელემენტი 0.6, ხაზგასმულია ანაზღაურების მატრიცაში, არის როგორც მინიმუმი მის მწკრივში, ასევე მაქსიმუმი მის სვეტში. გეომეტრიაში ზედაპირის წერტილს, რომელსაც აქვს მსგავსი თვისება (ერთდროული მინიმუმი ერთი კოორდინატის გასწვრივ და მაქსიმუმი მეორის გასწვრივ) უნაგირის წერტილს უწოდებენ; ანალოგიით, ეს ტერმინი ასევე გამოიყენება თამაშის თეორიაში. მატრიცის ელემენტს, რომელსაც აქვს ეს თვისება, ეწოდება მატრიცის უნაგირის წერტილი, ხოლო თამაშს ამბობენ, რომ აქვს უნაგირის წერტილი.

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

ამ მტკიცების შემოწმება მარტივია განსახილველი თამაშის მაგალითზე უნაგირის წერტილით. ჩვენ ვხედავთ, რომ უნაგირის წერტილით თამაშის შემთხვევაში, მინიმაქსის სტრატეგიებს აქვთ ერთგვარი „სტაბილურობა“: თუ ერთი მხარე იცავს თავის მინიმაქსის სტრატეგიას, მაშინ მხოლოდ მეორესთვის შეიძლება იყოს წამგებიანი საკუთარი თავისგან გადახვევა. გაითვალისწინეთ, რომ ამ შემთხვევაში, ის ფაქტი, რომ ნებისმიერ მოთამაშეს აქვს ინფორმაცია იმის შესახებ, რომ მოწინააღმდეგემ აირჩია თავისი ოპტიმალური სტრატეგია, ვერ შეცვლის მოთამაშის ქცევას: თუ მას არ სურს იმოქმედოს საკუთარი ინტერესების საწინააღმდეგოდ, მან უნდა დაიცვას თავისი ოპტიმალური სტრატეგია. უნაგირის წერტილით თამაშში ოპტიმალური სტრატეგიების წყვილი, თითქოსდა, არის „წონასწორობის პოზიცია“: ოპტიმალური სტრატეგიიდან ნებისმიერი გადახრა მიჰყავს გადახრილ მოთამაშეს არასახარბიელო შედეგებამდე, რაც აიძულებს მას დაუბრუნდეს საწყის პოზიციას.

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

1) თუ ორივე მხარე იცავს თავის ოპტიმალურ სტრატეგიებს, მაშინ საშუალო ანაზღაურება უდრის თამაშის ν წმინდა ფასს, რომელიც არის მისი ქვედა და ზედა ფასი.

2) თუ ერთ-ერთი მხარე იცავს თავის ოპტიმალურ სტრატეგიას, ხოლო მეორე გადაუხვევს საკუთარს, მაშინ გადახრილ მხარეს შეუძლია მხოლოდ წააგოს ამისგან და არავითარ შემთხვევაში არ გაზარდოს თავისი მოგება.

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

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

§ 3. სუფთა და შერეული სტრატეგიები. თამაშის გადაჭრა შერეული სტრატეგიებით

პრაქტიკული მნიშვნელობის სასრულ თამაშებს შორის შედარებით იშვიათია თამაშები უნაგირის წერტილით; უფრო დამახასიათებელია შემთხვევა, როდესაც თამაშის ქვედა და ზედა ფასები განსხვავებულია. ასეთი თამაშების მატრიცების გაანალიზებით, მივედით დასკვნამდე, რომ თუ თითოეულ მოთამაშეს ეძლევა ერთი სტრატეგიის არჩევა, მაშინ, გონივრულად მოქმედი მოწინააღმდეგეზე დაყრდნობით, ეს არჩევანი უნდა განისაზღვროს მინიმქსის პრინციპით. ჩვენი მაქსიმინის სტრატეგიის დაცვით, ჩვენ, რა თქმა უნდა, გარანტიას ვაძლევთ საკუთარ თავს ანაზღაურებას, რომელიც ტოლია თამაშის დაბალი ფასის ტოლფასი მოწინააღმდეგის ნებისმიერი ქცევისთვის. ჩნდება ბუნებრივი კითხვა: შესაძლებელია თუ არა გარანტირებული მოგცეთ α-ზე მეტი საშუალო ანაზღაურება, თუ იყენებთ არა მხოლოდ ერთ „სუფთა“ სტრატეგიას, არამედ შემთხვევით ცვლით რამდენიმე სტრატეგიას? ასეთი კომბინირებული სტრატეგია, რომელიც შედგება რამდენიმეს გამოყენებაში სუფთა სტრატეგიებიშემთხვევითი კანონის მიხედვით მონაცვლეობა სიხშირეების გარკვეული თანაფარდობით, თამაშის თეორიაში შერეულ სტრატეგიებს უწოდებენ.

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

აღნიშნული განცხადება არის თამაშების თეორიის ე.წ. მთავარი თეორემის შინაარსი. ეს თეორემა პირველად დაამტკიცა ფონ ნეუმანმა 1928 წელს. თეორემის ცნობილი მტკიცებულებები შედარებით რთულია; ამიტომ წარმოგიდგენთ მხოლოდ მის ფორმულირებას.

ყველა სასრულ თამაშს აქვს მინიმუმ ერთი გამოსავალი (შესაძლოა შერეული სტრატეგიების სფეროში).

გადაწყვეტილების შედეგად მიღებული ანაზღაურება ეწოდება თამაშის ფასს. მთავარი თეორემიდან გამომდინარეობს, რომ ყველა სასრულ თამაშს აქვს ფასი. ცხადია, ν თამაშის მნიშვნელობა ყოველთვის მდგომარეობს თამაშის α ქვედა მნიშვნელობასა და თამაშის β ზედა მნიშვნელობას შორის:

(3.1) α ≤ ν ≤ β

მართლაც, α არის მაქსიმალური გარანტირებული ანაზღაურება, რომელიც ჩვენ შეგვიძლია უზრუნველვყოთ საკუთარი თავისთვის მხოლოდ ჩვენი სუფთა სტრატეგიების გამოყენებით. ვინაიდან შერეული სტრატეგიები მოიცავს, როგორც განსაკუთრებულ შემთხვევას, ყველა წმინდას, ნებადართულია, გარდა სუფთა, ასევე შერეული სტრატეგიებისა, ჩვენ, ნებისმიერ შემთხვევაში, არ ვაუარესებთ ჩვენს შესაძლებლობებს; აქედან გამომდინარე ν ≥ α. ანალოგიურად, მოწინააღმდეგის შესაძლებლობების გათვალისწინებით, ჩვენ ვაჩვენებთ, რომ ν ≤ β, რაც გულისხმობს საჭირო უტოლობას (3.1).

მოდით შემოვიტანოთ სპეციალური აღნიშვნა შერეული სტრატეგიებისთვის. თუ, მაგალითად, ჩვენი შერეული სტრატეგია მოიცავს A 1, A 2, A 3 სტრატეგიების გამოყენებას p 1, p 2, p 3 და p 1 + p 2 + p 3 = 1 სიხშირეებით, ჩვენ აღვნიშნავთ ამ სტრატეგიას.

ანალოგიურად, მოწინააღმდეგის შერეული სტრატეგია აღინიშნება:

სადაც q 1 , q 2 , q 3 - სიხშირეები, რომლებშიც შერეულია B 1 , B 2 , B 3 სტრატეგიები; q 1 + q 2 + q 3 = 1.

დავუშვათ, რომ ჩვენ ვიპოვეთ თამაშის გამოსავალი, რომელიც შედგება ორი ოპტიმალური შერეული სტრატეგიისგან S A *, S B *. ზოგადად, მოცემული მოთამაშისთვის ხელმისაწვდომი ყველა სუფთა სტრატეგია არ შედის მის ოპტიმალურ შერეულ სტრატეგიაში, არამედ მხოლოდ ზოგიერთი მათგანი. მოთამაშის ოპტიმალურ შერეულ სტრატეგიაში შემავალ სტრატეგიებს მის „სასარგებლო“ სტრატეგიებს დავარქმევთ. გამოდის, რომ თამაშის გამოსავალს აქვს კიდევ ერთი შესანიშნავი თვისება: თუ ერთ-ერთი მოთამაშე იცავს თავის ოპტიმალურ შერეულ სტრატეგიას S A * (S B *), მაშინ ანაზღაურება იგივე რჩება და თამაშის ფასს უტოლდება, არ აქვს მნიშვნელობა. რას აკეთებს სხვა მოთამაშე, თუ ის არ სცილდება მის "სასარგებლო" სტრატეგიებს. მას, მაგალითად, შეუძლია გამოიყენოს თავისი ნებისმიერი „სასარგებლო“ სტრატეგია სუფთა ფორმადა ასევე შეგიძლიათ შეურიოთ ისინი ნებისმიერი პროპორციით.

§ 4. ელემენტარული მეთოდებითამაშის გადაწყვეტილებები. თამაშები 2x2 და 2xნ

თუ თამაშს mxn არ აქვს უნაგირის წერტილი, მაშინ გამოსავლის პოვნა ზოგადად საკმაოდ რთული პრობლემაა, განსაკუთრებით დიდი m და n-სთვის. ზოგჯერ ეს ამოცანა შეიძლება გამარტივდეს სტრატეგიების რაოდენობის შემცირებით, ზოგიერთი ზედმეტის წაშლით. გადაჭარბებული სტრატეგიები არის ა) დუბლიკატი და ბ) აშკარად წამგებიანი. განვიხილოთ, მაგალითად, მატრიცის თამაში:

ადვილია იმის დანახვა, რომ A 3 სტრატეგია ზუსტად იმეორებს („აორმაგებს“) სტრატეგიას A 1, ასე რომ, ამ ორი სტრატეგიიდან რომელიმე შეიძლება გადაიკვეთოს. გარდა ამისა, A 1 და A 2 სტრიქონების შედარება, ჩვენ ვხედავთ, რომ A 2 სტრიქონის თითოეული ელემენტი ნაკლებია (ან ტოლია) A 1 სტრიქონის შესაბამის ელემენტზე. აშკარაა, რომ არასდროს არ უნდა გამოვიყენოთ A2 სტრატეგია, ეს აშკარად წამგებიანია. A 3 და A 2-ის გადაკვეთით, მატრიცას უფრო მარტივ ფორმამდე მივყავართ. გარდა ამისა, ჩვენ აღვნიშნავთ, რომ სტრატეგია B 3 აშკარად არახელსაყრელია მტრისთვის; წაშლით, მატრიცას მივყავართ საბოლოო ფორმამდე:

ამრიგად, 4x4 თამაში მცირდება 2x3 თამაშამდე დუბლიკატი და აშკარად წამგებიანი სტრატეგიების აღმოფხვრით.

დუბლიკატიური და აშკარად წამგებიანი სტრატეგიების აღმოფხვრის პროცედურა ყოველთვის წინ უნდა უსწრებდეს თამაშის გადაწყვეტას. სასრული თამაშების უმარტივესი შემთხვევები, რომელთა მოგვარება ყოველთვის შესაძლებელია ელემენტარული მეთოდებით, არის 2x2 და 2xn თამაშები.

განვიხილოთ 2×2 თამაში მატრიცით:

აქ შეიძლება მოხდეს ორი შემთხვევა: 1) თამაშს აქვს უნაგირის წერტილი; 2) თამაშს არ აქვს უნაგირის წერტილი. პირველ შემთხვევაში, გამოსავალი აშკარაა: ეს არის სტრატეგიების წყვილი, რომლებიც იკვეთება უნაგირის წერტილში. სხვათა შორის, ჩვენ აღვნიშნავთ, რომ 2×2 თამაშში უნაგირის წერტილის არსებობა ყოველთვის შეესაბამება მიზანმიმართულად არახელსაყრელი სტრატეგიების არსებობას, რაც უნდა აღმოიფხვრას წინასწარი ანალიზით.

დაე, არ იყოს უნაგირის წერტილი და, შესაბამისად, თამაშის ქვედა ფასი არ უდრის ზედას: α ≠ β. საჭიროა A მოთამაშის ოპტიმალური შერეული სტრატეგიის პოვნა:

იგი გამოირჩევა იმ თვისებით, რომ, როგორიც არ უნდა იყოს მოწინააღმდეგის ქმედებები (თუ ის არ სცილდება მის „სასარგებლო“ სტრატეგიებს), ანაზღაურება ტოლი იქნება თამაშის ν. 2x2 თამაშში მოწინააღმდეგის ორივე სტრატეგია "სასარგებლოა", წინააღმდეგ შემთხვევაში თამაშს ექნებოდა გადაწყვეტა სუფთა სტრატეგიის დომენში (უნაგირების წერტილი). ეს ნიშნავს, რომ თუ ჩვენ დავიცავთ ჩვენს ოპტიმალურ სტრატეგიას (4.1), მაშინ მოწინააღმდეგეს შეუძლია გამოიყენოს თავისი ნებისმიერი სუფთა სტრატეგია B 1 , B 2 საშუალო ანაზღაურების ν შეცვლის გარეშე. აქედან გვაქვს ორი განტოლება:

საიდანაც, იმის გათვალისწინებით, რომ p 1 + p 2 = 1, მივიღებთ:

თამაშის ν მნიშვნელობას ვპოულობთ p 1, p 2 მნიშვნელობების რომელიმე განტოლებაში (4.2) ჩანაცვლებით.

თუ თამაშის ფასი ცნობილია, მაშინ უნდა განისაზღვროს მოწინააღმდეგის ოპტიმალური სტრატეგია

საკმარისია ერთი განტოლება, მაგალითად:

აქედან გამომდინარე, იმის გათვალისწინებით, რომ q 1 + q 2 = 1, გვაქვს:

მაგალითი 1მოდი ვიპოვოთ გამოსავალი 2×2 თამაშისთვის, რომელიც განხილულია § 1-ის მაგალითში, მატრიცით:

თამაშს არ აქვს უნაგირის წერტილი (α = –1; β = +1) და, შესაბამისად, გამოსავალი უნდა იყოს შერეული სტრატეგიების არეალში:

თქვენ უნდა იპოვოთ p 1 , p 2 , q 1 და q 2 . p 1-ისთვის გვაქვს განტოლება

1*p 1 + (–1)(1 – p 1) = (–1)p 1 + 1(1 – p 1)

საიდანაც p 1 = 1/2, p 2 = 1/2.

ანალოგიურად, ჩვენ ვპოულობთ: q 1 = 1/2, q 2 = 1/2, ν = 0.

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

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

მაგალითი 2თამაში ასეთია. არის ორი კარტი: ტუზი და დუსი. მოთამაშე A ამახვილებს ერთ მათგანს შემთხვევით; B ვერ ხედავს, რომელი კარტი გაითამაშა. თუ A ათამაშებს ტუზს, ის აცხადებს: "მე მაქვს ტუზი" და მეტოქისგან 1 რუბლს მოითხოვს. თუ A-მ დუი გაათამაშა, მაშინ მას შეუძლია ან A 1) თქვას „მე მაქვს ტუზი“ და მოწინააღმდეგისგან 1 რუბლი მოსთხოვოს, ან A 2) აღიაროს, რომ მას აქვს დუი და გადაუხადოს მოწინააღმდეგეს 1 მანეთი.

მტერს, თუ მას ნებაყოფლობით გადაუხდიან 1 რუბლს, შეუძლია მხოლოდ მისი მიღება. თუ ისინი მისგან მოითხოვენ 1 რუბლს, მაშინ მას შეუძლია ან B 1) დაუჯეროს მოთამაშე A-ს, რომ მას აქვს ტუზი და მისცეს მას 1 რუბლი, ან B 2) მოითხოვოს ჩეკი, რათა დარწმუნდეს, რომ განცხადება A არის სიმართლე. გამოდის, რომ A-ს ნამდვილად აქვს ტუზი, B-მ უნდა გადაიხადოს A 2 მანეთი. თუ აღმოჩნდება, რომ A ატყუებს და მას აქვს დუისი, მოთამაშე A უხდის B მოთამაშეს 2 რუბლს. საჭიროა თამაშის ანალიზი და თითოეული მოთამაშისთვის ოპტიმალური სტრატეგიის პოვნა.

გამოსავალი.თამაშს აქვს შედარებით რთული სტრუქტურა; იგი შედგება ერთი სავალდებულო შემთხვევითი სვლისგან - მოთამაშის A-ს მიერ ორი კარტიდან ერთ-ერთის არჩევა - და ორი პირადი სვლისგან, რომლებიც, თუმცა, სულაც არ არის შესრულებული. მართლაც, თუ A-მ ტუზი დახატა, მაშინ ის არანაირ პირად სვლას არ აკეთებს: მას ეძლევა მხოლოდ ერთი შესაძლებლობა - მოითხოვოს 1 რუბლი, რასაც აკეთებს. ამ შემთხვევაში, პირადი ნაბიჯი - დაიჯერო ან არ დაიჯერო (ანუ გადაიხადე ან არ გადაიხადო 1 რუბლი) - გადაეცემა B მოთამაშეს. თუ A-მ პირველი შემთხვევითი სვლის შედეგად მიიღო დუი, მაშინ მას ეძლევა პირადი გადაადგილება: გადაიხადე 1 რუბლი ან სცადე მოწინააღმდეგის მოტყუება და მოითხოვე 1 რუბლი (მოკლედ: „არ მოატყუო“ ან „მოატყუო“). თუ A ირჩევს პირველს, მაშინ B-მ უნდა მიიღოს მხოლოდ 1 რუბლი; თუ A აირჩია ეს უკანასკნელი, მაშინ B მოთამაშეს ეძლევა პირადი ნაბიჯი: დაიჯეროს ან არ დაიჯეროს A (ანუ გადაიხადოს A 1 რუბლი ან მოითხოვოს გადამოწმება).

თითოეული მოთამაშის სტრატეგიები არის წესები, რომლებიც ეუბნებიან მოთამაშეს, თუ რა უნდა გააკეთოს პირადი ნაბიჯის გადადგმისას. ცხადია, A-ს აქვს მხოლოდ ორი სტრატეგია: A 1 - მოტყუება, A 2 - არ მოტყუება. B-ს ასევე აქვს ორი სტრატეგია: B 1 - გჯეროდეს, B 2 - არ გჯეროდეს. მოდით ავაშენოთ თამაშის მატრიცა. ამისათვის ჩვენ ვიანგარიშებთ საშუალო ანაზღაურებას სტრატეგიების თითოეული კომბინაციისთვის.

1. A 1 B 1 (A ატყუებს, B სწამს). თუ A-მ მიიღო ტუზი (ამის ალბათობა არის ½, მაშინ მას არ ეძლევა პირადი ნაბიჯი; ის მოითხოვს 1 რუბლს და მოთამაშე B სჯერა მას; A-ს ანაზღაურება რუბლებში არის 1. თუ A მიიღებს დუსს (ამის ალბათობა ასევე არის ½), ის ატყუებს თავისი სტრატეგიის მიხედვით და ითხოვს 1 რუბლს; სჯერა მას და იხდის; ანაზღაურება A ასევე უდრის 1-ს. საშუალო ანაზღაურება: a 11 = ½ * 1 + ½ * 1 = 1.

2. A 1 B 2 (A ატყუებს, B არ სჯერა). თუ A-ს აქვს ტუზი, მას არ აქვს პირადი სვლა; ის მოითხოვს 1 რუბლს; მისი სტრატეგიის მიხედვით, მას არ სჯერა B და ჩეკის შედეგად იხდის 2 რუბლს (ა-ს ანაზღაურება არის +2). თუ A-მ მიიღო დუი, მას, თავისი სტრატეგიის მიხედვით, 1 რუბლი სჭირდება; ბ, მისი თქმით, არ სჯერა; შედეგად, A იხდის 2 რუბლს (A-ს მოგება არის -2). საშუალო მოგებაა: a 12 = ½*(+2) + ½*(–2) = 0.

3. A 2 B 1 (A არ ატყუებს, B სჯერა). თუ A ათამაშებს ტუზს, ის მოითხოვს 1 რუბლს; B თავისი სტრატეგიის მიხედვით იხდის; A-ს ანაზღაურება არის +1. თუ A-მ დუსს გაათამაშა, ის იხდის 1 რუბლს თავისი სტრატეგიის მიხედვით; რჩება მხოლოდ B-ს მიღება (A-ს ანაზღაურება არის -1). საშუალო მოგებაა: და 21 = ½*(+1) + ½*(–1) = 0.

4. A 2 B 2 (A არ ატყუებს, B არ სჯერა). თუ A ათამაშებს ტუზს, ის მოითხოვს 1 რუბლს; B ამოწმებს და ჩეკის შედეგად იხდის 2 რუბლს (ანაზღაურება არის +2). თუ A-მ დუიზი ამოიღო, ის იხდის 1 რუბლს; მასში რჩება მხოლოდ მიღება (ანაზღაურება არის 1). საშუალო მოგებაა: და 22 = ½*(+2) + ½*(–1) = ½.

ჩვენ ვაშენებთ თამაშის მატრიცას:

მატრიცას არ აქვს უნაგირის წერტილი. თამაშის ქვედა ფასი α = 0, თამაშის ზედა ფასი β = ½. მოდით ვიპოვოთ თამაშის გამოსავალი შერეული სტრატეგიების სფეროში. ფორმულის გამოყენებით (4.3), ვიღებთ:

იმათ. მოთამაშე A უნდა გამოიყენოს თავისი პირველი სტრატეგია (მოტყუება) ყველა შემთხვევის მესამედში, ხოლო მეორე (არ მოატყუო) ყველა შემთხვევის ორ მესამედში. ამავე დროს, ის მოიგებს საშუალოდ თამაშის ფასს ν = 1/3.

მნიშვნელობა ν = 1/3 მიუთითებს, რომ მოცემულ პირობებში თამაში მომგებიანია A-სთვის და არახელსაყრელი B-სთვის. თავისი ოპტიმალური სტრატეგიის გამოყენებით A-ს ყოველთვის შეუძლია უზრუნველყოს საკუთარი თავი დადებითი საშუალო ანაზღაურებით. გაითვალისწინეთ, რომ თუ A გამოიყენებდა თავის ყველაზე ფრთხილ (მაქსიმალურ) სტრატეგიას (ამ შემთხვევაში, ორივე სტრატეგია A 1 და A 2 არის მაქსიმუმი), მას ექნება საშუალო ანაზღაურება ნულის ტოლი. ამრიგად, შერეული სტრატეგიის გამოყენება A-ს აძლევს შესაძლებლობას გააცნობიეროს თავისი უპირატესობა B-ზე, რაც წარმოიქმნება თამაშის ამ წესებით.

ჩვენ განვსაზღვრავთ ოპტიმალურ სტრატეგიას B. გვაქვს: q 1 *1 + q 2 *0 = 1/3, q 1 = 1/3, q 2 = 2/3. სად

ე.ი. B მოთამაშემ ყველა შემთხვევის მესამედში უნდა დაუჯეროს A-ს და გადაუხადოს მას 1 რუბლი შემოწმების გარეშე, ხოლო ორ მესამედში - ჩეკი. შემდეგ ყოველ თამაშში საშუალოდ 1/3-ს წააგებს. თუ ის გამოიყენებდა თავის მინიმქს სუფთა სტრატეგიას B 2 (არ მჯერა), ის წააგებდა საშუალოდ 1/2 თამაშში.

2×2 თამაშის გამოსავალი შეიძლება მიეცეს მარტივი გეომეტრიული ინტერპრეტაციით. მოდით იყოს 2×2 თამაში მატრიცით

ავიღოთ x ღერძის მონაკვეთი 1-ის სიგრძით (ნახ. 4.1). მონაკვეთის მარცხენა ბოლო (აბსცისის წერტილი x = 0) წარმოადგენს A 1 სტრატეგიას; განყოფილების მარჯვენა ბოლო (x = 1) - სტრატეგია A 2 . მოდით დავხატოთ ორი პერპენდიკულარი x ღერძზე A 1 და A 2 წერტილების გავლით: ღერძი მე-ᲛᲔდა ღერძი II–II. ღერძზე მე-ᲛᲔჩვენ გადავადებთ ანაზღაურებას A 1 სტრატეგიით; ღერძზე II–II- მოგება სტრატეგიით A 2 . განვიხილოთ მოწინააღმდეგის სტრატეგია B 1; ის იძლევა ორ წერტილს ღერძებზე მე-ᲛᲔდა II–IIორდინატებით შესაბამისად 11 და 21 . ამ წერტილებს გავავლოთ სწორი ხაზი B 1 B 1. ცხადია, თუ მოწინააღმდეგის B 1 სტრატეგიისთვის შერეულ სტრატეგიას გამოვიყენებთ

მაშინ ჩვენი საშუალო მომატება, რომელიც ამ შემთხვევაში უდრის a 11 p 1 + a 21 p 2 , წარმოდგენილი იქნება M წერტილით B 1 B 1 სწორ ხაზზე; ამ წერტილის აბსცისა არის p 2. სწორ ხაზს B 1 B 1 , რომელიც ასახავს ანაზღაურებას სტრატეგიით B 1 , პირობითად დაერქმევა "სტრატეგია B 1".

ცხადია, სტრატეგია B 2 შეიძლება აშენდეს ზუსტად ანალოგიურად (ნახ. 4.2).

ჩვენ უნდა ვიპოვოთ ოპტიმალური სტრატეგია S A *, ანუ ის, რისთვისაც მინიმალური მოგება(B-ის ნებისმიერი ქცევისთვის) მაქსიმუმზე გადაიქცევა. ამისათვის ჩვენ ვაშენებთ ქვედა ზღვარს ანაზღაურებაზე B 1, B 2 სტრატეგიებისთვის, ე.ი. გატეხილი ხაზი B 1 NB 2 მონიშნულია ნახ. 4.2 თამამი ხაზით. ეს ქვედა ზღვარი გამოხატავს A მოთამაშის მინიმალურ ანაზღაურებას მისი ნებისმიერი შერეული სტრატეგიისთვის; წერტილი N, სადაც ეს მინიმალური ანაზღაურება აღწევს მაქსიმუმს, განსაზღვრავს თამაშის გამოსავალს და ფასს. ადვილი მისახვედრია, რომ N წერტილის ორდინატი არის თამაშის ν ფასი, ხოლო მისი აბსციზა არის p 2 - A 2 სტრატეგიის გამოყენების სიხშირე ოპტიმალურ შერეულ სტრატეგიაში S A *.

ჩვენს შემთხვევაში, თამაშის გადაწყვეტა განისაზღვრა სტრატეგიების გადაკვეთის წერტილით. თუმცა, ეს ყოველთვის ასე არ იქნება; ნახ. ნახაზი 4.3 გვიჩვენებს შემთხვევას, როდესაც სტრატეგიების კვეთის არსებობის მიუხედავად, გამოსავალი იძლევა სუფთა სტრატეგიებს ორივე მოთამაშისთვის (A 2 და B 2), ხოლო თამაშის ფასი არის ν = a 22 . ამ შემთხვევაში, მატრიცას აქვს უნაგირის წერტილი და სტრატეგია A 1 აშკარად წამგებიანია, რადგან მოწინააღმდეგის ნებისმიერი სუფთა სტრატეგიისთვის ის უფრო მცირე ანაზღაურებას იძლევა ვიდრე A 2 .

იმ შემთხვევაში, როდესაც მტერს აქვს მიზანმიმართულად არახელსაყრელი სტრატეგია, გეომეტრიული ინტერპრეტაცია აქვს ნახ. 4.4.

ამ შემთხვევაში ანაზღაურების ქვედა ზღვარი ემთხვევა B 1 სტრატეგიას, სტრატეგია B 2 აშკარად წამგებიანია მოწინააღმდეგისთვის.

გეომეტრიული ინტერპრეტაცია შესაძლებელს ხდის თამაშის ქვედა და ზედა ფასების ვიზუალიზაციას (ნახ. 4.5).

საილუსტრაციოდ, მოდით ავაშენოთ 2×2 თამაშების გეომეტრიული ინტერპრეტაციები 1 და 2 მაგალითებში (სურათები 4.6 და 4.7).

ჩვენ ვნახეთ, რომ ნებისმიერი 2×2 თამაში შეიძლება გადაწყდეს ელემენტარული ხრიკებით. ნებისმიერი 2xn თამაში შეიძლება გადაწყდეს ზუსტად იგივე გზით. სადაც ჩვენ გვაქვს მხოლოდ ორი სტრატეგია და მტერს აქვს თვითნებური რიცხვი.

გვქონდეს ორი სტრატეგია: A 1 , A 2 და მტრის - n სტრატეგია: B 1 , B 2 , ..., B n . მოცემულია მატრიცა ‖a ij‖; მას აქვს ორი მწკრივი და n სვეტი. როგორც ორი სტრატეგიის შემთხვევაში, პრობლემას ვაძლევთ გეომეტრიულ ინტერპრეტაციას; მოწინააღმდეგის n სტრატეგია წარმოდგენილი იქნება n სწორი ხაზით (ნახ. 4.8). ჩვენ ვაშენებთ ანაზღაურების ქვედა ზღვარს (პოლიხაზი B 1 MNB 2) და ვპოულობთ მასზე N წერტილს მაქსიმალური ორდინატით. ეს წერტილი იძლევა თამაშის გამოსავალს (სტრატეგია ) N წერტილის ორდინატი უდრის ν თამაშის ფასს, ხოლო აბსცისა უდრის A 2 სტრატეგიის р 2 სიხშირეს.

ამ შემთხვევაში მოწინააღმდეგის ოპტიმალური სტრატეგია მიიღება ორი „სასარგებლო“ სტრატეგიის ნაზავის გამოყენებით: B 2 და B 4 , რომლებიც იკვეთება N წერტილში. სტრატეგია B 3 აშკარად წამგებიანია, ხოლო სტრატეგია B 1 წამგებიანია ოპტიმალური სტრატეგიით S A. *. თუ A დაიცავს თავის ოპტიმალურ სტრატეგიას, მაშინ ანაზღაურება არ შეიცვლება, არ აქვს მნიშვნელობა რომელ "სასარგებლო" სტრატეგიას იყენებს B, თუმცა, ის შეიცვლება, თუ B გადავა B 1 ან B 3 სტრატეგიებზე. თამაშის თეორიაში დადასტურდა, რომ ნებისმიერ სასრულ თამაშს mxn აქვს გამოსავალი, რომელშიც არც ერთი მხარის "სასარგებლო" სტრატეგიების რაოდენობა არ აღემატება უმცირესს ორი რიცხვიდან m და n. კერძოდ, აქედან გამომდინარეობს, რომ თამაშს 2xm ყოველთვის აქვს გამოსავალი, რომელშიც ორივე მხრიდან მონაწილეობს არაუმეტეს ორი „სასარგებლო“ სტრატეგია.

გეომეტრიული ინტერპრეტაციის გამოყენებით, შეგიძლიათ მოგცეთ მარტივი გზა ნებისმიერი 2xm თამაშის გადასაჭრელად. უშუალოდ ნახაზიდან ვპოულობთ მტრის "სასარგებლო" სტრატეგიის წყვილს B j და B k, რომლებიც იკვეთება N წერტილზე (თუ ორზე მეტი სტრატეგია იკვეთება N წერტილში, ჩვენ ვიღებთ მათგან ნებისმიერ ორს). ჩვენ ვიცით, რომ თუ მოთამაშე A იცავს თავის ოპტიმალურ სტრატეგიას, მაშინ ანაზღაურება არ არის დამოკიდებული იმ პროპორციაზე, რომელშიც B იყენებს თავის „სასარგებლო“ სტრატეგიებს, შესაბამისად,

ამ განტოლებიდან და პირობიდან p 2 = 1 - p 1 ვპოულობთ p1, p2 და თამაშის ν მნიშვნელობას. თამაშის ფასის ცოდნა, შეგიძლიათ დაუყოვნებლივ განსაზღვროთ ოპტიმალური სტრატეგია მოთამაშე B. ამისათვის, მაგალითად, წყდება განტოლება: q j a 1 j + q k a 1 k = ν, სადაც q j + q k = 1. იმ შემთხვევაში, როდესაც ჩვენ გვაქვს m სტრატეგია, ხოლო მტერს აქვს მხოლოდ ორი, ცხადია, პრობლემა მოგვარებულია სრულიად მსგავსი გზით; საკმარისია აღვნიშნოთ, რომ ანაზღაურების ნიშნის შებრუნებით შესაძლებელია მოთამაშე A "გამარჯვებულიდან" "დამარცხებულად" გადაიქცეს. შესაძლებელია თამაშის გადაჭრა ანაზღაურების ნიშნის შეცვლის გარეშე; მაშინ პრობლემა წყდება უშუალოდ B-სთვის, მაგრამ აგებულია არა ქვედა, არამედ ზედა ანაზღაურების ზღვარი (ნახ. 4.9). ზღვარზე იძებნება წერტილი N მინიმალური ორდინატით, რომელიც არის თამაშის ν ფასი.

განვიხილოთ და ამოხსენით 2×2 და 2xm თამაშების რამდენიმე მაგალითი, რომლებიც პრაქტიკული მნიშვნელობის თამაშების გამარტივებული მაგალითებია.

მაგალითი 3მხარე A აგზავნის ორ ბომბდამშენს მტრის ზონაში B მედა II; მედაფრინავს წინ II- უკან. ერთ-ერთი ბომბდამშენი - წინასწარ უცნობია, რომელმა უნდა ატაროს ბომბი, მეორე ასრულებს ესკორტის ფუნქციას. მტრის მიდამოში ბომბდამშენებს უტევს მებრძოლი B მხრიდან. ბომბდამშენები შეიარაღებულნი არიან სხვადასხვა სიჩქარის ცეცხლსასროლი იარაღით. თუ მებრძოლი თავს დაესხმება უკანა ბომბდამშენს II, მაშინ მხოლოდ ამ ბომბდამშენის ქვემეხები ისვრიან მასზე; თუ ის თავს დაესხმება წინა ბომბდამშენს, მაშინ ორივე ბომბდამშენის ქვემეხი ისვრის მას. მებრძოლზე დარტყმის ალბათობა პირველ შემთხვევაში არის 0,3, მეორეში 0,7.

თუ მებრძოლი არ ჩამოაგდეს ბომბდამშენის თავდაცვითი ცეცხლით, მაშინ ის ურტყამს არჩეულ სამიზნეს 0,6 ალბათობით. ბომბდამშენების ამოცანაა ბომბის მიზნამდე მიტანა; მებრძოლის ამოცანაა ამის თავიდან აცილება, ე.ი. ჩამოაგდეს გადამზიდავი ბომბდამშენი. საჭიროა მხარეთა ოპტიმალური სტრატეგიების არჩევა:

ა) A მხარისთვის: რომელი ბომბდამშენი უნდა იყოს გამოყენებული გადამზიდად?

ბ) B მხარისთვის: რომელ ბომბდამშენს უნდა შეუტიოს?

გამოსავალი. გვაქვს 2×2 თამაშის მარტივი შემთხვევა; მოგება - ალბათობაგადამზიდველის უკმარისობა. ჩვენი სტრატეგიები: 1 - გადამზიდავი - ბომბდამშენი მე; 2 - გადამზიდავი - ბომბდამშენი II. მტრის სტრატეგიები: B 1 - ბომბდამშენი თავს დაესხმება მე; 2-ში - ბომბდამშენი უტევს II. მოდით შევადგინოთ თამაშის მატრიცა, ე.ი. იპოვეთ საშუალო ანაზღაურება სტრატეგიების თითოეული კომბინაციისთვის.

1. A 1 B 1 (გადამზიდავი მე, შეუტია მე). გადამზიდავი არ მოხვდება, თუ ბომბდამშენები ჩამოაგდებენ მებრძოლს, ან თუ არა, მაგრამ ის არ მოხვდება მიზანში: a 11 = 0.7 + 0.3 * 0.4 = 0.82.

2. A 2 B 1 (გადამზიდავი II, შეუტია მე). a 21 = 1

3. A 1 B 2 (გადამზიდავი მე, შეუტია II). A 12 = 1

4. A 2 B 2 (გადამზიდავი II, შეუტია II). A 22 \u003d 0.3 + 0.7 * 0.4 \u003d 0.58

თამაშის მატრიცას აქვს ფორმა:

თამაშის დაბალი ფასია 0.82; ზედა ფასი 1. მატრიცას არ აქვს უნაგირის წერტილი; ჩვენ ვეძებთ გამოსავალს შერეული სტრატეგიების სფეროში. Ჩვენ გვაქვს:

p 1 * 0.82 + p 2 * 1 = ν

p1 *1 + p2 *0.58 = v

p 1 = 0.7; p 2 \u003d 0.3

ჩვენი ოპტიმალური სტრატეგია დიახ, ანუ, თქვენ უნდა აირჩიოთ უფრო ხშირად, როგორც გადამზიდავი მე, როგორ II. თამაშის ღირებულება არის ν = 0,874. ვიცით ν, ჩვენ განვსაზღვრავთ q 1 და q 2 - B 1 და B 2 სტრატეგიების სიხშირეებს მოწინააღმდეგის ოპტიმალურ სტრატეგიაში S B *. გვაქვს: q 1 * 0.82 + q 2 * 1 \u003d 0.874 და q 2 \u003d 1 - q 1, საიდანაც q 1 \u003d 0.7; q 2 \u003d 0.3, ანუ მტრის ოპტიმალური სტრატეგიაა .

მაგალითი 4მხარე A უტევს ობიექტს, მხარე B იცავს მას. A მხარეს ორი სიბრტყე აქვს; მხარე B - სამი საზენიტო იარაღი. თითოეული თვითმფრინავი არის ძლიერი იარაღის მატარებელი; იმისთვის, რომ ობიექტს მოხვდეს, საკმარისია მასში მინიმუმ ერთი თვითმფრინავი შეაღწიოს. A-ის მხარეს შეუძლია აირჩიოს ობიექტთან მიახლოება სამი მიმართულებით: მე, II, III(ნახ. 4.10). მტერს (მხარე B) შეუძლია განათავსოს თავისი იარაღი ნებისმიერი მიმართულებით; ამავდროულად, თითოეული იარაღი ისვრის მხოლოდ სივრცის არეალს, რომელიც დაკავშირებულია ამ მიმართულებას, და არ ისვრის მეზობელი მიმართულებებით. თითოეულ იარაღს შეუძლია მხოლოდ ერთი თვითმფრინავის გასროლა; ნასროლი თვითმფრინავი მოხვდება ალბათობით 1. A მხარეს არ იცის სად არის განთავსებული იარაღი; B მხარემ არ იცის, საიდან მოვა თვითმფრინავები. A მხარის ამოცანაა ობიექტზე დარტყმა; B მხარის ამოცანაა მისი დამარცხების თავიდან აცილება. იპოვნეთ თამაშის გამოსავალი.

გამოსავალი. თამაში არის 2×3 თამაში. მოგება - ობიექტზე დარტყმის ალბათობა. ჩვენი შესაძლო სტრატეგიები: A 1 - გაგზავნეთ ერთი თვითმფრინავი ორზე სხვადასხვა მიმართულებები. A 2 - გაგზავნეთ ორივე თვითმფრინავი იმავე მიმართულებით. მტრის სტრატეგიები: B 1 - მოათავსეთ თითო იარაღი თითოეული მიმართულებით; B 2 - მოათავსეთ ორი იარაღი ერთი მიმართულებით და ერთი მეორეში; 3-ში - ჩადეთ სამივე იარაღი ერთი მიმართულებით. ჩვენ ვაკეთებთ თამაშის მატრიცას.

1. A 1 B 1 (თვითმფრინავები დაფრინავენ სხვადასხვა მიმართულებები; იარაღები მოთავსებულია ერთ დროს). ცხადია, ამ შემთხვევაში, არც ერთი თვითმფრინავი არ შეაღწევს ობიექტს: a 11 = 0.

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

3. A 1 B 2 (თვითმფრინავი დაფრინავს სათითაოდ; მტერი იცავს ორ მიმართულებას და მესამეს ტოვებს დაუცველი). ალბათობა იმისა, რომ სულ მცირე ერთი თვითმფრინავი შეიჭრება ობიექტამდე, უდრის ალბათობას, რომ ერთ-ერთი მათგანი აირჩევს დაუცველ მიმართულებას: და 12 = 2/3.

4. A 2 B 2 (თვითმფრინავები ერთად დაფრინავენ ერთი მიმართულებით; მტერი ერთ მიმართულებას იცავს ორი იარაღით და ერთი ერთით, ანუ ფაქტობრივად იცავს ერთ მიმართულებას და ტოვებს ორს დაუცველს). ალბათობა იმისა, რომ მინიმუმ ერთი თვითმფრინავი შეიჭრება ობიექტამდე, უდრის ალბათობას, რომ წყვილი თვითმფრინავი აირჩევს რეალურად დაუცველ მიმართულებას: a 22 = 2/3.

5. A 1 B 3 (თვითმფრინავები ერთ ჯერზე დაფრინავენ; მტერი მხოლოდ ერთ მიმართულებას იცავს სამი იარაღით): a 13 = 1.

6. A 2 B 3 (ორივე თვითმფრინავი ერთად დაფრინავს; მტერი მხოლოდ ერთ მიმართულებას იცავს სამი იარაღით). იმისათვის, რომ ობიექტს მოხვდეს, თვითმფრინავმა უნდა აირჩიოს დაუცველი მიმართულება: a 23 = 2/3.

თამაშის მატრიცა:

მატრიციდან ჩანს, რომ B 3 სტრატეგია აშკარად წამგებიანია B 2-თან შედარებით (ეს შეიძლებოდა წინასწარ გადაწყვეტილიყო). B 3 სტრატეგიის გადაკვეთით, თამაში მცირდება 2x2 თამაშზე:

მატრიცას აქვს უნაგირის წერტილი: თამაშის ქვედა ფასი 2/3 ემთხვევა ზედას. ამავდროულად, ჩვენ აღვნიშნავთ, რომ ჩვენთვის (A) სტრატეგია A 1 აშკარად წამგებიანია. დასკვნა: ორივე მხარე A და B ყოველთვის უნდა გამოიყენონ თავიანთი სუფთა სტრატეგიები A 2 და B 2, ე.ი. თვითმფრინავები უნდა გავაგზავნოთ 2-ით, შემთხვევით ავირჩიოთ მიმართულება, რომლითაც გაიგზავნება წყვილი; მტერმა უნდა განათავსოს თავისი იარაღი შემდეგნაირად: ორი - ერთი მიმართულებით, ერთი - მეორე მიმართულებით და ამ მიმართულებების არჩევანიც შემთხვევით უნდა მოხდეს (აქ, როგორც ვხედავთ, "სუფთა სტრატეგიები" უკვე შეიცავს შემთხვევითობის ელემენტს. ). ამ ოპტიმალური სტრატეგიების გამოყენებით, ჩვენ ყოველთვის მივიღებთ მუდმივ საშუალო ანაზღაურებას 2/3 (ანუ ობიექტს მოხვდება 2/3 ალბათობით). გაითვალისწინეთ, რომ თამაშის ნაპოვნი გამოსავალი არ არის უნიკალური; წმინდა სტრატეგიებში ამოხსნის გარდა, არსებობს A მოთამაშის შერეული სტრატეგიების მთელი სპექტრი, რომლებიც ოპტიმალურია, p 1 \u003d 0-დან p 1 \u003d 1/3-მდე (ნახ. 4.11).

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

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

გამოსავალი.ჩვენ ჯერ კიდევ გვაქვს ორი შესაძლო სტრატეგია: A 1 - გაგზავნეთ თვითმფრინავები ერთდროულად, A 2 - გაგზავნეთ ორი თვითმფრინავი ერთად. მტერს აქვს ხუთი შესაძლო სტრატეგია: B 1 - მოათავსეთ თითო იარაღი თითოეული მიმართულებით; B 2 - განათავსეთ ორი იარაღი ორი სხვადასხვა მიმართულებით; 3-ში - ჩადეთ ორი იარაღი ერთი მიმართულებით და თითო-თითო - დანარჩენ ორში; 4-ში - ჩადეთ სამი იარაღი ერთი მიმართულებით და ერთი მეორეში; 5-ში - დააყენეთ ოთხივე იარაღი ერთი მიმართულებით. სტრატეგიები B 4, B 5 წინასწარ იქნება გაუქმებული, როგორც აშკარად წამგებიანი. წინა მაგალითის მსგავსად, ჩვენ ვაშენებთ თამაშის მატრიცას:

თამაშის ქვედა ფასია 1/2, ზედა 3/4. მატრიცას არ აქვს უნაგირის წერტილი; გამოსავალი მდგომარეობს შერეული სტრატეგიების სფეროში. გეომეტრიული ინტერპრეტაციის გამოყენებით (ნახ. 4.12) გამოვყოფთ მტრის „სასარგებლო“ სტრატეგიებს: B 1 და B 2.

p 1 და p 2 სიხშირეები განისაზღვრება განტოლებიდან: p 1 * 0 + (1 - p 1) * 1 = ν და p 1 * 5/6 + (1 - p 1) * 1/2 = ν; საიდანაც p 1 = 3/8; p2 = 5/8; ν = 5/8, ე.ი. ჩვენი ოპტიმალური სტრატეგიაა . მისი გამოყენებით, ჩვენ საკუთარ თავს გარანტიას ვაძლევთ საშუალოდ 5/8 მოგებას. ვიცით თამაშის ფასი ν = 5/8, ვპოულობთ მოწინააღმდეგის "სასარგებლო" სტრატეგიების q 1 და q 2 სიხშირეებს: q 1 * 0 + (1 - q 1) * 5/6 = 5/8 , q 1 = ¼, q 2 = ¾. მტრის ოპტიმალური სტრატეგია იქნება: .

მაგალითი 6 A მხარეს აქვს ორი სტრატეგია A 1 და A 2 , B მხარეს აქვს ოთხი სტრატეგია B 1 , B 2 , B 3 და B 4 . თამაშის მატრიცას აქვს ფორმა:

იპოვნეთ თამაშის გამოსავალი.

გამოსავალი. თამაშის დაბალი ფასი 3; ზედა 4. გეომეტრიული ინტერპრეტაცია (ნახ. 4.13) აჩვენებს, რომ B მოთამაშის სასარგებლო სტრატეგიებია B 1 და B 2 ან B 2 და B 4:

მოთამაშე A-ს აქვს უსასრულოდ ბევრი ოპტიმალური შერეული სტრატეგია: ოპტიმალურ სტრატეგიაში p 1 შეიძლება განსხვავდებოდეს 1/5-დან 4/5-მდე. თამაშის ღირებულება არის ν = 4. B მოთამაშეს აქვს სუფთა ოპტიმალური სტრატეგია B 2.

§ 5. ზოგადი მეთოდებითამაშის დასრულების გადაწყვეტილებები

ჯერჯერობით, ჩვენ განვიხილეთ მხოლოდ 2xn ტიპის ყველაზე ელემენტარული თამაშები, რომელთა გადაჭრა ძალიან მარტივად შეიძლება და მისაღები და საილუსტრაციო გეომეტრიული ინტერპრეტაცია. ზოგადად, mxn თამაშის ამოხსნა საკმაოდ რთული პრობლემაა და პრობლემის სირთულე და მისი ამოსახსნელად საჭირო გამოთვლების რაოდენობა მკვეთრად იზრდება m და n-ის გაზრდით. თუმცა, ეს სირთულეები არ არის ფუნდამენტური ხასიათისა და დაკავშირებულია მხოლოდ გამოთვლების ძალიან დიდ მოცულობასთან, რაც რიგ შემთხვევებში შესაძლოა პრაქტიკულად შეუსრულებელი აღმოჩნდეს. ამოხსნის მეთოდის ფუნდამენტური ასპექტი იგივე რჩება ნებისმიერი მ.

მოდით ილუსტრაციით ეს ავღნიშნოთ თამაშის 3xn მაგალითით. მოდით მივცეთ მას გეომეტრიული ინტერპრეტაცია - უკვე სივრცითი. სამი ჩვენი სტრატეგია A 1 , A 2 და A 3 წარმოდგენილი იქნება სამი პუნქტით სიბრტყეზე ჰოი; პირველი დევს საწყისზე (სურ. 5.1), მეორე და მესამე ცულებზე ოჰდა OUსაწყისიდან 1 მანძილზე.

ღერძები გაყვანილია A 1, A 2 და A 3 წერტილებით მე – მე, II – IIდა III – III, სიბრტყეზე პერპენდიკულარული ჰოი. ღერძზე მე – მეანაზღაურება გადაიდო A 1 სტრატეგიით ღერძებზე II – IIდა III – III- ანაზღაურება სტრატეგიებისთვის A 2, A 3. თითოეული მტრის სტრატეგია B j წარმოდგენილი იქნება ცულებზე მოწყვეტილი თვითმფრინავით მე – მე, II – IIდა III – IIIსეგმენტები, რომლებიც ტოლია შესაბამისი სტრატეგიების A 1, A 2 და A 3 და სტრატეგია B j. მტრის ყველა სტრატეგიის ამგვარად აგების შემდეგ, ჩვენ ვიღებთ თვითმფრინავების ოჯახს სამკუთხედზე A 1, A 2 და A 3 (ნახ. 5.2). ამ ოჯახისთვის ასევე შესაძლებელია ავაშენოთ ქვედა ანაზღაურებადი ზღვარი, როგორც ეს გავაკეთეთ 2xn-ის შემთხვევაში და ვიპოვოთ წერტილი N ამ საზღვარზე სიბრტყის ზემოთ მაქსიმალური სიმაღლით. ჰოი. ეს სიმაღლე იქნება თამაშის ფასი ν.

A 1, A 2 და A 3 სტრატეგიების p 1 , p 2 , p 3 სიხშირეები ოპტიმალურ სტრატეგიაში S A * განისაზღვრება N წერტილის კოორდინატებით (x, y), კერძოდ: p 2 = x, p 3 = y, p 1 = 1 - p 2 - p 3. თუმცა, ეს გეომეტრიული კონსტრუქცია 3xn შემთხვევისთვისაც კი არ არის ადვილი განსახორციელებელი და დიდ დროს და ფანტაზიას მოითხოვს. თამაშის ზოგად შემთხვევაში, ის გადადის m-განზომილებიან სივრცეში და კარგავს ყოველგვარ ხილვადობას, თუმცა ზოგიერთ შემთხვევაში გეომეტრიული ტერმინოლოგიის გამოყენება შეიძლება სასარგებლო იყოს. mxn თამაშების პრაქტიკაში გადაჭრისას უფრო მოსახერხებელია არა გეომეტრიული ანალოგიების, არამედ გამოთვლითი ანალიტიკური მეთოდების გამოყენება, მით უმეტეს, რომ პრობლემის გადასაჭრელად კომპიუტერებიეს მეთოდები ერთადერთი შესაფერისია.

ყველა ეს მეთოდი არსებითად მცირდება პრობლემის გადაჭრამდე თანმიმდევრული ცდებით, მაგრამ ცდების თანმიმდევრობის შეკვეთა საშუალებას გაძლევთ შექმნათ ალგორითმი, რომელიც მიგვიყვანს გადაწყვეტამდე ყველაზე ეკონომიური გზით. აქ მოკლედ შევეხებით mxn თამაშების ამოხსნის ერთ გამოთვლით მეთოდს - ეგრეთ წოდებულ "ხაზოვანი პროგრამირების" მეთოდს. ამისათვის ჩვენ ჯერ ვაძლევთ ზოგად განცხადებას mxn თამაშში გადაწყვეტის პოვნის პრობლემის შესახებ. დაე, თამაში mxn იყოს მოცემული m სტრატეგიებით A 1 , А 2 , …, A m მოთამაშის А და n სტრატეგიებით B 1 , B 2 , …, B n მოთამაშის В და მოცემულია ანაზღაურების მატრიცა ‖a i j ‖. საჭიროა თამაშის გამოსავლის პოვნა, ე.ი. A და B მოთამაშეების ორი ოპტიმალური შერეული სტრატეგია

სადაც p 1 + p 2 + ... + p m = 1; q 1 + q 2 + ... + q n = 1 (ზოგიერთი რიცხვი p i და q j შეიძლება იყოს ნულის ტოლი).

ჩვენმა ოპტიმალურმა სტრატეგიამ S A * უნდა მოგვაწოდოს ანაზღაურება არანაკლებ ν-ზე მოწინააღმდეგის ნებისმიერი ქცევისთვის და ანაზღაურება ტოლი ν მისი ოპტიმალური ქცევისთვის (სტრატეგია S B *). ანალოგიურად, სტრატეგიამ S B * უნდა მიაწოდოს მტერს დანაკარგი არაუმეტეს ν ვიდრე ჩვენი ნებისმიერი ქცევისთვის და ტოლი ν ჩვენი ოპტიმალური ქცევისთვის (სტრატეგია S A *).

თამაშის ν მნიშვნელობის მნიშვნელობა ამ შემთხვევაში ჩვენთვის უცნობია; ჩვენ ვივარაუდებთ, რომ ის უდრის რაიმე დადებით რიცხვს. ამის ვარაუდით, ჩვენ არ ვარღვევთ მსჯელობის ზოგადობას; იმისათვის, რომ ν > 0, აშკარად საკმარისია, რომ ‖a i j ‖ მატრიცის ყველა ელემენტი იყოს არაუარყოფითი. ამის მიღწევა ყოველთვის შესაძლებელია ‖a i j‖ ელემენტებს საკმარისად დიდი დადებითი მნიშვნელობის დამატებით. ლ; ხოლო თამაშის ფასი გაიზრდება ლ, მაგრამ გამოსავალი არ იცვლება.

მოდით ავირჩიოთ ჩვენი ოპტიმალური სტრატეგია S A *. მაშინ ჩვენი საშუალო ანაზღაურება მოწინააღმდეგის სტრატეგიისთვის B j იქნება ტოლი: a j = p 1 a 1j + p 2 a 2j + … + p m a mj . ჩვენს ოპტიმალურ სტრატეგიას S A * აქვს თვისება, რომ მოწინააღმდეგის ნებისმიერი ქცევისთვის ის უზრუნველყოფს ანაზღაურებას არანაკლებ ν; შესაბამისად, ნებისმიერი რიცხვი a j არ შეიძლება იყოს ν-ზე ნაკლები. ჩვენ ვიღებთ რამდენიმე პირობას:

უტოლობებს (5.1) ვყოფთ დადებით მნიშვნელობაზე ν და აღვნიშნავთ

შემდეგ პირობები (5.1) შეიძლება ჩაიწეროს როგორც

სადაც ξ 1 , ξ 2 , ..., ξ m არის არაუარყოფითი რიცხვები. ვინაიდან p 1 + p 2 + ... + p m = 1, მაშინ სიდიდეები ξ 1 , ξ 2 , ..., ξ m აკმაყოფილებს პირობას

(5.3) ξ 1 + ξ 2 + … + ξ m = 1/ν.

ჩვენ გვინდა, რომ ჩვენი გარანტირებული მოგება მაქსიმალურად მაღალი იყოს; ცხადია, ხოლო მარჯვენა ნაწილითანასწორობა (5.3) იღებს მინიმალურ მნიშვნელობას. ამრიგად, თამაშის გამოსავლის პოვნის პრობლემა მცირდება შემდეგზე მათემატიკის პრობლემა: განსაზღვრეთ ξ 1 , ξ 2 , …, ξ m , პირობების დამაკმაყოფილებელი არაუარყოფითი სიდიდეები, რათა მათი ჯამი Φ = ξ 1 + ξ 2 + … + ξ m იყოს მინიმალური.

ჩვეულებრივ, ექსტრემალური მნიშვნელობების პოვნასთან დაკავშირებული პრობლემების გადაჭრისას (მაქსიმუმი და მინიმალური), ფუნქცია დიფერენცირებულია და წარმოებულები ტოლდება ნულთან. მაგრამ ასეთი ტექნიკა ამ შემთხვევაში გამოუსადეგარია, ვინაიდან ფუნქცია Φ, რომელიც მინიმუმამდე უნდა შემცირდეს, წრფივია და მისი წარმოებულები ყველა არგუმენტთან მიმართებაში ერთის ტოლია, ე.ი. არასოდეს ქრება. შესაბამისად, ფუნქციის მაქსიმუმი მიიღწევა სადღაც არგუმენტების ცვლილების რეგიონის საზღვარზე, რაც განისაზღვრება არგუმენტებისა და პირობების არანეგატიურობის მოთხოვნით (5.2). დიფერენციაციის გამოყენებით უკიდურესი მნიშვნელობების პოვნის მეთოდი ასევე შეუსაბამოა იმ შემთხვევებში, როდესაც თამაშის გადასაჭრელად განისაზღვრება ქვედა (ან ზედა) ანაზღაურების საზღვრის მაქსიმუმი, როგორც ეს გავაკეთეთ, მაგალითად, 2xn თამაშების გადაჭრისას. მართლაც, ქვედა საზღვარი შედგება სწორი ხაზების სეგმენტებისგან და მაქსიმუმი მიიღწევა არა იმ წერტილში, სადაც წარმოებული არის ნულის ტოლი (ასეთი წერტილი საერთოდ არ არსებობს), არამედ ინტერვალის საზღვარზე ან სწორი სეგმენტების გადაკვეთის წერტილი.

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

საჭიროა მოიძებნოს ξ 1 , ξ 2 , ..., ξ m არაუარყოფითი მნიშვნელობები, რომლებიც აკმაყოფილებს (5.4) პირობებს და, ამავდროულად, მინიმუმამდე დაიყვანოს მოცემული ერთგვაროვანი. ხაზოვანი ფუნქციარაოდენობები ξ 1 , ξ 2 , …, ξ m (წრფივი ფორმა): Φ = c 1 ξ 1 + c 2 ξ 2 + … + c m ξ m

ადვილი მისახვედრია, რომ ზემოთ დასმული თამაშის თეორიის პრობლემა არის წრფივი პროგრამირების ამოცანის განსაკუთრებული შემთხვევა c 1 = c 2 = ... = c m = 1. ერთი შეხედვით, შეიძლება ჩანდეს, რომ პირობები (5.2) არის არ ექვივალენტური პირობების (5.4), ვინაიდან ტოლობის ნიშნების ნაცვლად ისინი შეიცავს უტოლობის ნიშნებს. თუმცა, უთანასწორობის ნიშნების თავიდან აცილება მარტივია ახალი ფიქტიური არაუარყოფითი ცვლადების შემოღებით z 1 , z 2 , …, z n და ჩაწერის პირობები (5.2) სახით:

ფორმა Φ მინიმიზაციისთვის არის Φ = ξ 1 + ξ 2 + … + ξ m . ხაზოვანი პროგრამირების აპარატი საშუალებას იძლევა, შედარებით მცირე რაოდენობის თანმიმდევრული ნიმუშებით, აირჩიოთ ξ 1, ξ 2, ..., ξ m მნიშვნელობები, რომლებიც აკმაყოფილებს მოთხოვნებს. უფრო მეტი სიცხადისთვის, აქ ჩვენ ვაჩვენებთ ამ აპარატის გამოყენებას უშუალოდ კონკრეტული თამაშების გადაჭრის მასალაზე.

მაგალითი 1საჭიროა იპოვოთ გამოსავალი 3 × 3 თამაშისთვის, რომელიც მოცემულია § 1-ის მე-2 მაგალითში მატრიცით:

იმისათვის, რომ ყველა ij იყოს არაუარყოფითი, ჩვენ მატრიცის ყველა ელემენტს ვუმატებთ L = 5. მივიღებთ მატრიცას:

ამ შემთხვევაში თამაშის ფასი 5-ით გაიზრდება, მაგრამ გადაწყვეტილება არ შეიცვლება.

მოდით განვსაზღვროთ ოპტიმალური სტრატეგია S A *. პირობებს (5.2) აქვს ფორმა:

სადაც ξ 1 = p 1 / ν, ξ 2 = p 2 / ν, ξ 3 = p 3 / ν. უთანასწორობის ნიშნებისგან თავის დასაღწევად შემოვიყვანთ ცვლადებს z 1 , z 2 , z 3 ; პირობები (5.6) შეიძლება დაიწეროს შემდეგნაირად:

ხაზოვანი ფორმა Φ არის: Φ = ξ 1 + ξ 2 + ξ 3 და უნდა გაკეთდეს რაც შეიძლება პატარა. თუ სამივე B სტრატეგია არის „სასარგებლო“, მაშინ სამივე მოჩვენებითი ცვლადი z 1 , z 2 , z 3 გაქრება (ანუ, თამაშის ფასის ტოლი ანაზღაურება N მიიღწევა თითოეული სტრატეგიით B j). მაგრამ ჩვენ ჯერ კიდევ არ გვაქვს იმის თქმა, რომ სამივე სტრატეგია „სასარგებლოა“. ამის შესამოწმებლად, შევეცადოთ გამოვხატოთ Φ-ს ფორმა მოჩვენებითი ცვლადების მიხედვით z 1 , z 2 , z 3 და ვნახოთ, მივაღწევთ თუ არა მათი ნულის ტოლი დაყენებით ფორმის მინიმუმს. ამისათვის ჩვენ ვხსნით განტოლებებს (5.7) ξ 1 , ξ 2 , ξ 3 ცვლადებთან მიმართებაში (ანუ, გამოვხატავთ ξ 1 , ξ 2 , ξ 3 ცვლადების გამოსახულებით z 1 , z 2 , z 3. ):

ξ 1 , ξ 2 , ξ 3 , მივიღებთ: Φ = 1/5 + z 1 /20 + z 2 /10 + z 3 /20. აქ ყველა z-ის კოეფიციენტები დადებითია; მაშასადამე, z 1 , z 2 , z 3 ნებისმიერმა ზრდამ შეიძლება გამოიწვიოს მხოლოდ Φ ფორმის ზრდა და ჩვენ გვინდა, რომ ეს იყოს მინიმალური. მაშასადამე, z 1 , z 2 , z 3 მნიშვნელობები, რომლებიც ფ ფორმას მინიმუმამდე აქცევს, არის z 1 = z 2 = z 3 = 0. ამიტომ, ფორმის მინიმალური მნიშვნელობა Φ: 1/ν = 1. /5, საიდანაც თამაშის ფასი ν = 5. ნულოვანი მნიშვნელობები z 1 , z 2 , z 3 ჩანაცვლებით ფორმულებში (5.8), ვპოულობთ: ξ 1 = 1/20, ξ 2 = 1/10, ξ 3 = 1/20, ან მათი გამრავლება ν, p 1 \u003d 1/4, p 2 \u003d 1/2, p 3 \u003d 1/4. ამრიგად, ოპტიმალური სტრატეგია A არის ნაპოვნი: , ე.ი. რიცხვი 1 უნდა ჩავწეროთ ყველა შემთხვევის ერთ მეოთხედში, 2 შემთხვევათა ნახევარში და 3 დარჩენილ კვარტალში.

ვიცით თამაშის ფასი ν = 5, უკვე შეგვიძლია ცნობილი გზებიიპოვნეთ მოწინააღმდეგის ოპტიმალური სტრატეგია . ამისათვის ჩვენ ვიყენებთ ჩვენს ნებისმიერ "სასარგებლო" სტრატეგიას (მაგალითად, A 2 და A 3) და ვწერთ განტოლებებს:

9q 1 + 11 (1-q 2 -q 1) = 5,

საიდანაც q 1 = q3 = 1/4; q 2 \u003d 1/2. მოწინააღმდეგის ოპტიმალური სტრატეგია იგივე იქნება, რაც ჩვენი: . ახლა დაუბრუნდით თავდაპირველ (არაკონვერტირებულ) თამაშს. ამისთვის საჭიროა მხოლოდ მატრიცის ელემენტებს დამატებული თამაშის ν = 5 მნიშვნელობის გამოკლება L = 5. ჩვენ ვიღებთ ორიგინალური თამაშის ფასს v 0 = 0. შესაბამისად, ორივე მხარის ოპტიმალური სტრატეგიები უზრუნველყოფს საშუალო ანაზღაურებას ნულის ტოლი; თამაში ერთნაირად მომგებიანი ან არახელსაყრელია ორივე მხარისთვის.

მაგალითი 2სპორტულ A-ს აქვს სამი ვარიანტი A 1, A 2 და A 3 გუნდის შემადგენლობისთვის. კლუბი B - ასევე სამი ვარიანტი B 1 , B 2 და B 3 . შეჯიბრში მონაწილეობის შესახებ განაცხადის შეტანისას არცერთმა კლუბმა არ იცის, რა შემადგენლობას აირჩევს მეტოქე. A კლუბის მოგების ალბათობა სხვადასხვა ვარიანტებიშემადგენლობა, რომელიც დაახლოებით ცნობილია წარსული შეხვედრების გამოცდილებიდან, მოცემულია მატრიცით:

იპოვეთ სიხშირე, რომლითაც კლუბებმა უნდა განათავსონ თითოეული გუნდი ერთმანეთთან შეხვედრებზე, რათა მიაღწიონ მოგების საშუალო რაოდენობას.

გამოსავალი. თამაშის დაბალი ფასია 0.4; ზედა 0.6; ჩვენ ვეძებთ გამოსავალს შერეული სტრატეგიების სფეროში. იმისათვის, რომ წილადებთან საქმე არ გვქონდეს, მატრიცის ყველა ელემენტს ვამრავლებთ 10-ზე; ამ შემთხვევაში თამაშის ფასი 10-ჯერ გაიზრდება და გადაწყვეტილება არ შეიცვლება. ჩვენ ვიღებთ მატრიცას:

პირობებს (5.5) აქვს ფორმა:

და მინიმალური პირობა Φ = ξ 1 + ξ 2 + ξ 3 = მინ.

ვამოწმებთ, არის თუ არა მოწინააღმდეგის სამივე სტრატეგია „სასარგებლო“. როგორც ჰიპოთეზა, ჩვენ ჯერ ვივარაუდოთ, რომ მოჩვენებითი ცვლადები z 1 , z 2 , z 3 ნულის ტოლია და შესამოწმებლად ვხსნით განტოლებებს (5.10) ξ 1 , ξ 2 , ξ 3:

(5.12) 136Φ = 30 +13z 1 +18z 2 – 51z 3

ფორმულა (5.12) გვიჩვენებს, რომ z 1 და z 2 ცვლადების გაზრდა მათი სავარაუდო მნიშვნელობიდან ნულიდან შეიძლება მხოლოდ გაზარდოს Φ, ხოლო z 3-ის გაზრდა შეიძლება შემცირდეს Φ. თუმცა, z 3-ის მატება უნდა მოხდეს ფრთხილად, რათა მნიშვნელობები ξ 1, ξ 2, ξ 3, z 3-დან გამომდინარე, ამ შემთხვევაში არ გახდეს უარყოფითი. აქედან გამომდინარე, ჩვენ ვაყენებთ z 1 და z 2 მნიშვნელობებს ნულის ტოლი ტოლობის მარჯვენა მხარეს (5.11) და გავზრდით z 3 მნიშვნელობას მისაღებ ზღვრებამდე (ნებისმიერ მნიშვნელობებამდე ξ 1, ξ 2, ξ 3 ქრება). მეორე თანასწორობიდან (5.11) ჩანს, რომ z 3-ის ზრდა არის "უსაფრთხო" ξ 2-ის მნიშვნელობისთვის - ის მხოლოდ აქედან იზრდება. რაც შეეხება ξ 1 და ξ 3 მნიშვნელობებს, აქ z 3-ის ზრდა შესაძლებელია მხოლოდ გარკვეულ ზღვარამდე. ξ 1-ის მნიშვნელობა ქრება z 3 = 10/23-ზე; რაოდენობა ξ 3 ქრება ადრე, უკვე z 3 = 1/4-ზე. მაშასადამე, z 3-ს მაქსიმალური დასაშვები მნიშვნელობის z 3 = 1/4 მიცემით, ჩვენ ასევე გადავაქცევთ ξ 3 მნიშვნელობას ნულზე.

იმის შესამოწმებლად, ხდება თუ არა ფორმა Φ მინიმალური z 1 = 0, z 2 = 0, ξ 3 = 0, ჩვენ გამოვხატავთ დარჩენილ (არანულოვან) ცვლადებს z 1 , z 2 , ξ 3 სავარაუდოდ ნულის ტოლი. . განტოლებების (5.10) ამოხსნა ξ 1 , ξ 2 და z 3 მიმართებით, მივიღებთ:

(5.13) 32Φ = 7 + Зz 1 + 4z 2 + ξ 3

ფორმულიდან (5.13) ჩანს, რომ ნებისმიერი ზრდა z 1 , z 2 , ξ 3 მათი სავარაუდო ნულოვანი მნიშვნელობების მიღმა შეიძლება მხოლოდ გაზარდოს Φ-ს ფორმა. მაშასადამე, ნაპოვნია თამაშის გამოსავალი; იგი განისაზღვრება მნიშვნელობებით z 1 = z 2 = ξ 3 = 0, საიდანაც ξ 1 = 1/32, ξ 2 = 3/16, z 3 = 1/4. ფორმულით (5.13) ჩანაცვლებით, ჩვენ ვპოულობთ თამაშის ν მნიშვნელობას: 32Φ = 7 = 32/ν; v = 32/7. ჩვენი ოპტიმალური სტრატეგია: . "სასარგებლო" სტრატეგიები (კომპოზიციები A 1 და A 2) უნდა იქნას გამოყენებული 1/7 და 6/7 სიხშირეებით; შემადგენლობა A 3 - არასოდეს გამოიყენოთ.

მოწინააღმდეგის ოპტიმალური სტრატეგიის მოსაძებნად, ზოგად შემთხვევაში, შეიძლება გაკეთდეს შემდეგი: შეცვალოს ანაზღაურებადი ნიშანი, დაამატოთ მუდმივი მნიშვნელობა L მატრიცის ელემენტებს, რათა ისინი არაუარყოფითი გახადონ და მოწინააღმდეგისთვის პრობლემა გადაწყვიტოთ. ისევე, როგორც ჩვენ თვითონ გადავწყვიტეთ. თუმცა, ის ფაქტი, რომ ჩვენ უკვე ვიცით თამაშის ν ღირებულება გარკვეულწილად ამარტივებს დავალებას. გარდა ამისა, ამ კონკრეტულ შემთხვევაში, პრობლემა კიდევ უფრო გამარტივებულია იმით, რომ გადაწყვეტაში მონაწილეობს მხოლოდ ორი "სასარგებლო" მტრის სტრატეგია B 1 და B 2, რადგან z 3-ის მნიშვნელობა არ არის ნულის ტოლი და, შესაბამისად, B 3 სტრატეგიით თამაშის ფასი არ არის მიღწეული. A მოთამაშის ნებისმიერი „სასარგებლო“ სტრატეგიის არჩევით, მაგალითად A 1, შეგიძლიათ იპოვოთ q 1 და q 2 სიხშირეები. ამისათვის ჩვენ ვწერთ განტოლებას 8q 1 + 2(1 - q 1) = 32/7, საიდანაც q 1 = 3/7, q 2 = 4/7; მოწინააღმდეგის ოპტიმალური სტრატეგია იქნება: , ე.ი. მტერმა არ უნდა გამოიყენოს B 3 კომპოზიცია, ხოლო B 1 და B 2 კომპოზიციები უნდა იყოს გამოყენებული 3/7 და 4/7 სიხშირეებით.

თავდაპირველ მატრიცას დავუბრუნდეთ, ჩვენ განვსაზღვრავთ თამაშის ნამდვილ მნიშვნელობას ν 0 = 32/7:10 = 0,457. ეს ნიშნავს, რომ შეხვედრების დიდი რაოდენობით, A კლუბის გამარჯვებების რაოდენობა იქნება ყველა შეხვედრის 0,457.

§ 6. თამაშების ამოხსნის სავარაუდო მეთოდები

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

გამეორების მეთოდის იდეა შემდეგია. ტარდება „აზროვნების ექსპერიმენტი“, რომელშიც ოპონენტები A და B იყენებენ თავიანთ სტრატეგიებს ერთმანეთის წინააღმდეგ. ექსპერიმენტი შედგება ელემენტარული თამაშების თანმიმდევრობისგან, რომელთაგან თითოეულს აქვს მოცემული თამაშის მატრიცა. ის იწყება იმით, რომ ჩვენ (მოთამაშე A) შემთხვევით ვირჩევთ ჩვენს ერთ-ერთ სტრატეგიას, მაგალითად A i . ამაზე მტერი პასუხობს თავისი სტრატეგიით B j, რომელიც ჩვენთვის ყველაზე ნაკლებად მომგებიანია, ე.ი. ამცირებს A i სტრატეგიის ანაზღაურებას მინიმუმამდე. ჩვენ ვპასუხობთ ამ ნაბიჯს ჩვენი A k სტრატეგიით, რომელიც იძლევა მაქსიმალურ საშუალო ანაზღაურებას, როდესაც მოწინააღმდეგე იყენებს B j სტრატეგიას. შემდეგი - ისევ მტრის მხრივ. ის პასუხობს ჩვენს წყვილ A i და A k სვლას თავისი სტრატეგიით B j, რომელიც გვაძლევს ყველაზე მცირე საშუალო ანაზღაურებას ამ ორი სტრატეგიისთვის (A i, A k) და ა.შ. განმეორებითი პროცესის ყოველ საფეხურზე, თითოეული მოთამაშე პასუხობს მეორე მოთამაშის ნებისმიერ სვლას თავისი სტრატეგიით, რომელიც ოპტიმალურია მის ყველა წინა სვლაზე, განიხილება როგორც შერეული სტრატეგია, რომელშიც სუფთა სტრატეგიები წარმოდგენილია პროპორციების შესაბამისი პროპორციებით. მათი გამოყენების სიხშირე.

ასეთი მეთოდი, თითქოს, მოთამაშეთა რეალური პრაქტიკული „მომზადების“ მოდელია, როდესაც თითოეული მათგანი გამოცდილებით იკვლევს მოწინააღმდეგის ქცევას და ცდილობს მასზე პასუხის გაცემას მისთვის სასარგებლო გზით. თუ სასწავლო პროცესის ასეთი იმიტაცია საკმარისად დიდხანს გაგრძელდება, მაშინ საშუალო მომატება ერთი წყვილი სვლაზე ( ელემენტარული თამაში) მიდრეკილია თამაშის ფასზე და სიხშირეებზე p 1 ... p m ; q 1 … q n, რომელსაც მოთამაშეთა სტრატეგიები ხვდებიან ამ გათამაშებაში, მიუახლოვდება სიხშირეებს, რომლებიც განსაზღვრავენ ოპტიმალურ სტრატეგიებს. გამოთვლები აჩვენებს, რომ მეთოდის კონვერგენცია ძალიან ნელია, მაგრამ ეს არ არის დაბრკოლება მაღალსიჩქარიანი კომპიუტერებისთვის.

ილუსტრირებით განმეორებითი მეთოდის გამოყენება წინა აბზაცის მე-2 მაგალითში ამოხსნილი 3×3 თამაშის მაგალითზე. თამაში მოცემულია მატრიცით:

ცხრილი 6.1 გვიჩვენებს განმეორებითი პროცესის პირველ 18 საფეხურს. პირველი სვეტი იძლევა ელემენტარული თამაშის რაოდენობას (მოძრაობების წყვილი) ნ; მეორეში - ნომერი მემოთამაშის არჩეული სტრატეგია; მომდევნო სამში - "კუმულაციური მოგება" პირველისთვის ნთამაშები მოწინააღმდეგის სტრატეგიებით B 1 , B 2 , B 3 . ამ მნიშვნელობებიდან ყველაზე პატარა ხაზგასმულია. Უფრო ნომერი მიდის ჯმოწინააღმდეგის მიერ არჩეული სტრატეგია და, შესაბამისად, დაგროვილი ანაზღაურება ნთამაშები სტრატეგიებით A 1 , A 2 , A 3 ამ მნიშვნელობებით, მაქსიმალური ხაზგასმულია ზემოდან. ხაზგასმული მნიშვნელობები განსაზღვრავს სხვა მოთამაშის საპასუხო სტრატეგიის არჩევანს. შემდეგი სვეტები ზედიზედ ნაჩვენებია: მინიმალური საშუალო ანაზღაურება ν უდრის მინიმალურ დაგროვილ ანაზღაურებას გაყოფილი თამაშების რაოდენობაზე ნ; მაქსიმალური საშუალო მოგება, უდრის მაქსიმალურ დაგროვილ მოგებას გაყოფილი ნ, და მათი საშუალო არითმეტიკული ν* = (ν + )/2. მატებასთან ერთად ნსამივე მნიშვნელობა ν და ν* მიუახლოვდება თამაშის ν მნიშვნელობას, მაგრამ მნიშვნელობა ν* ბუნებრივად მიუახლოვდება მას შედარებით სწრაფად.

ცხრილი 6.1.

როგორც მაგალითიდან ჩანს, გამეორებების დაახლოება ძალიან ნელია, მაგრამ ასეთი მცირე გაანგარიშებაც კი შესაძლებელს ხდის თამაშის ფასის სავარაუდო მნიშვნელობის პოვნას და „სასარგებლო“ სტრატეგიების გავრცელების გამოვლენას. საანგარიშო მანქანების გამოყენებისას მეთოდის ღირებულება მნიშვნელოვნად იზრდება. თამაშების გადაჭრის განმეორებითი მეთოდის უპირატესობა ის არის, რომ გამოთვლების მოცულობა და სირთულე შედარებით სუსტად იზრდება სტრატეგიების რაოდენობის მატებასთან ერთად. მდა ნ.

§ 7. რამდენიმე უსასრულო თამაშის ამოხსნის ხერხები

უსასრულო თამაში არის თამაში, რომელშიც ერთ-ერთ მხარეს მაინც აქვს სტრატეგიების უსასრულო ნაკრები. ასეთი თამაშების გადაჭრის ზოგადი მეთოდები ჯერ არ არის შემუშავებული. თუმცა, პრაქტიკისთვის, შეიძლება საინტერესო იყოს ზოგიერთი კონკრეტული შემთხვევა, რომელიც აღიარებს შედარებით მარტივ გამოსავალს. განვიხილოთ ორი მოწინააღმდეგის თამაში A და B, რომელთაგან თითოეულს აქვს სტრატეგიების უსასრულო (დაუთვლელი) ნაკრები; ეს სტრატეგიები მოთამაშისთვის A შეესაბამება სხვადასხვა მნიშვნელობამუდმივად ცვალებადი პარამეტრი Xდა B-სთვის - პარამეტრი ზე. ამ შემთხვევაში, ‖a ij‖ მატრიცის ნაცვლად, თამაში განისაზღვრება ორი მუდმივად ცვალებადი არგუმენტის გარკვეული ფუნქციით. a (x, y), რომელსაც ჩვენ დავარქმევთ ანაზღაურების ფუნქციას (გაითვალისწინეთ, რომ თავად ფუნქცია a (x, y)არ უნდა იყოს უწყვეტი). მოგების ფუნქცია a (x, y)შეიძლება გეომეტრიულად იყოს წარმოდგენილი ზოგიერთი ზედაპირით a (x, y)არგუმენტის ცვლილების არეალის ზემოთ (x, y)(ნახ. 7.1)

ანაზღაურების ფუნქციის ანალიზი a (x, y)ხორციელდება ანაზღაურების მატრიცის ანალიზის მსგავსად. პირველ რიგში, ნაპოვნია α თამაშის უფრო დაბალი ფასი; რადგან ეს განისაზღვრება თითოეულისთვის Xფუნქციის მინიმუმი a (x, y)ყველასთვის ზე: , მაშინ ამ მნიშვნელობების მაქსიმუმი იძებნება ყველასთვის X(მაქსიმუმი):

თამაშის ზედა ფასი (მინიმქსი) განისაზღვრება ანალოგიურად:

განვიხილოთ შემთხვევა, როდესაც α = β. ვინაიდან ν თამაშის ფასი ყოველთვის არის α და β შორის, მათი ჯამური მნიშვნელობა არის ν. ტოლობა α = β ნიშნავს, რომ ზედაპირი a (x, y)აქვს უნაგირის წერტილი, ანუ ისეთი წერტილი კოორდინატებით x 0, y 0, რომელშიც a (x, y)არის ამავე დროს მინიმალური ზედა მაქსიმუმ X(ნახ. 7.2).

მნიშვნელობა a (x, y)ამ ეტაპზე არის თამაშის ფასი ν: ν = a (x 0, y 0).უნაგირის წერტილის არსებობა ნიშნავს, რომ ამ უსასრულო თამაშს აქვს სუფთა სტრატეგიული გადაწყვეტა; x 0, y 0არის ოპტიმალური სუფთა სტრატეგიები A და B. ზოგად შემთხვევაში, როდესაც α ≠ β, თამაშს შეიძლება ჰქონდეს გამოსავალი მხოლოდ შერეული სტრატეგიების რეგიონში (შესაძლოა არა ერთადერთი). უსასრულო თამაშების შერეულ სტრატეგიას აქვს გარკვეული ალბათობის განაწილება სტრატეგიებისთვის Xდა ზეგანიხილება როგორც შემთხვევითი ცვლადები. ეს განაწილება შეიძლება იყოს უწყვეტი და განისაზღვრება სიმკვრივით ვ 1 (X)და ვ 2 (y); შეიძლება იყოს დისკრეტული, შემდეგ კი ოპტიმალური სტრატეგიები შედგება ინდივიდუალური სუფთა სტრატეგიების ნაკრებისგან, რომლებიც არჩეულია ზოგიერთი არანულოვანი ალბათობით.

იმ შემთხვევაში, როდესაც უსასრულო თამაშს არ აქვს უნაგირის წერტილი, შესაძლებელია თამაშის ქვედა და ზედა ფასების ვიზუალური გეომეტრიული ინტერპრეტაციის მიცემა. განვიხილოთ უსასრულო თამაში ანაზღაურების ფუნქციით a (x, y)და სტრატეგიები x, y, განუწყვეტლივ ავსებს ღერძების სეგმენტებს (x 1, x 2)და (1-ზე, 2-ზე). თამაშის α-ს დაბალი ფასის დასადგენად, უნდა „გავიხედოთ“ ზედაპირზე a (x, y)ღერძის მხრიდან ზე, ე.ი. დააპროექტეთ იგი ბინაზე ჰოა(ნახ. 7.3). ჩვენ ვიღებთ გარკვეულ ფიგურას, რომელიც შემოსაზღვრავს გვერდებიდან სწორი ხაზებით x \u003d x 1 და x \u003d x 2, ხოლო ზემოდან და ქვემოდან - მრუდებით K B და K N. თამაშის უფრო დაბალი ფასი α, ცხადია, მეტი არაფერია. ვიდრე K N მრუდის მაქსიმალური ორდინატი.

ანალოგიურად, β თამაშის ზედა ფასის საპოვნელად, უნდა „გახედოთ“ ზედაპირს a (x, y)ღერძის მხრიდან X(პროექტი ზედაპირი სიბრტყეზე uOa) და იპოვეთ პროექციის K B ზედა საზღვრის მინიმალური ორდინატი (სურ. 7.4).

განვიხილოთ უსასრულო თამაშების ორი ელემენტარული მაგალითი.

მაგალითი 1მოთამაშეებს A და B თითოეულს აქვთ შესაძლო სტრატეგიების უთვალავი ნაკრები Xდა ზედა 0 ≤ x ≤ 1; 0 ≤ y ≤ 1. a-სთვის ანაზღაურებადი ფუნქცია მოცემულია გამოსახულებით a (x, y) - (x - y) 2 . იპოვნეთ თამაშის გამოსავალი.

ამოხსნა: a(x, y) ზედაპირი პარაბოლური ცილინდრია (ნახ. 7.5) და არ აქვს უნაგირის წერტილი. მოდით განვსაზღვროთ თამაშის დაბალი ფასი; ცხადია ყველასთვის X; აქედან გამომდინარე = 0. მოდით განვსაზღვროთ თამაშის ზედა ფასი. ამისათვის ჩვენ მოვძებნით ფიქსირებული ზე

ამ შემთხვევაში მაქსიმუმი ყოველთვის მიიღწევა ინტერვალის საზღვარზე (როცა x = 0 ან x = 1), ე.ი. ის უდრის y 2 რაოდენობებს; (1 - y) 2, რაც უფრო დიდია. გამოვსახოთ ამ ფუნქციების გრაფიკები (ნახ. 7.6), ე.ი. ზედაპირის პროექცია a (x, y)თვითმფრინავამდე uOa. თამამი ხაზი ნახ. 7.6 აჩვენებს ფუნქციას. ცხადია, მისი მინიმალური მნიშვნელობა მიიღწევა y = 1/2-ზე და უდრის 1/4-ს. ამიტომ, თამაშის ზედა ღირებულება არის β = 1/4. ამ შემთხვევაში თამაშის ზედა ფასი ემთხვევა თამაშის ν ფასს. მართლაც, მოთამაშე A-ს შეუძლია გამოიყენოს შერეული სტრატეგია S A = , რომელშიც უკიდურესი მნიშვნელობები x = 0 და x = 1 შედის იგივე სიხშირეებით; მაშინ, ნებისმიერი სტრატეგიისთვის, B მოთამაშის საშუალო ანაზღაურება მოთამაშისთვის A იქნება: ½y 2 + ½(1 - y) 2 . ადვილია იმის დადასტურება, რომ ეს მნიშვნელობა ნებისმიერი მნიშვნელობისთვის ზე 0-სა და 1-ს შორის აქვს მნიშვნელობა არანაკლებ ¼: ½y 2 + ½(1 - y) 2 ≥ ¼.

ამგვარად, მოთამაშე A, ამ შერეული სტრატეგიის გამოყენებით, შეუძლია თავის თავს გარანტია მიიღოს თამაშის ზედა ფასის ტოლი ანაზღაურება; ვინაიდან თამაშის ფასი არ შეიძლება იყოს ზედა ფასზე მეტი, ეს სტრატეგია S A ოპტიმალურია: S A = S A *.

რჩება B მოთამაშის ოპტიმალური სტრატეგიის პოვნა. ცხადია, თუ თამაშის ν ფასი უდრის β თამაშის ზედა ფასს, მაშინ B მოთამაშის ოპტიმალური სტრატეგია ყოველთვის იქნება მისი სუფთა მინიმალური სტრატეგია, რაც მას გარანტიას აძლევს. თამაშის ზედა ფასი. ამ შემთხვევაში, ასეთი სტრატეგია არის y 0 = ½. მართლაც, ამ სტრატეგიით, რაც არ უნდა გააკეთოს მოთამაშე A, მისი ანაზღაურება არ იქნება ¼-ზე მეტი. ეს გამომდინარეობს აშკარა უტოლობიდან (x - ½) 2 = x(x -1) + ¼ ≤ ¼

მაგალითი 2მხარე A ("ჩვენ") ისვრის მტრის თვითმფრინავ B-ს. დაბომბვის თავიდან აცილების მიზნით, მტერს შეუძლია მანევრირება გარკვეული გადატვირთვით ზე, საიდანაც მას, თავისი შეხედულებისამებრ, შეუძლია დაურთოს ღირებულებები ზე = 0 (სწორხაზოვანი მოძრაობა) ადრე ზე = ზემაქს(ფრენა მაქსიმალური გამრუდების წრის გასწვრივ). ჩვენ ვვარაუდობთ ზემაქსსაზომი ერთეული, ე.ი. დავაყენოთ ზემაქს= 1. მტრის წინააღმდეგ ბრძოლაში შეგვიძლია გამოვიყენოთ სამიზნეები ჭურვის ფრენისას ამა თუ იმ ჰიპოთეზაზე დაფუძნებული სამიზნის მოძრაობის შესახებ. გადატვირთვა Xამ ჰიპოთეტურ მანევრში შეიძლება ვივარაუდოთ, რომ ტოლია ნებისმიერი მნიშვნელობის 0-დან 1-მდე. ჩვენი ამოცანაა მტრის დარტყმა; მტრის ამოცანაა დარჩეს დაუმარცხებელი. მონაცემების დამარცხების ალბათობა Xდა ზედაახლოებით გამოიხატება ფორმულით: a(x, y) = , სად ზე- მტრის მიერ გამოყენებული გადატვირთვა; x - გადატვირთვა, მხედველობაში მიღებული. საჭიროა ორივე მხარისთვის ოპტიმალური სტრატეგიების განსაზღვრა.

გამოსავალი. ცხადია, თამაშის ამოხსნა არ იცვლება, თუ დავაყენებთ p = 1. ანაზღაურების ფუნქცია a (x, y)წარმოდგენილია ნახ. 7.7.

ეს არის ცილინდრული ზედაპირი, რომლის გენერატორები კოორდინატთა კუთხის ბისექტრის პარალელურია. ჰოიდა გენერატრიქსის პერპენდიკულარული სიბრტყის მონაკვეთი არის ნორმალური განაწილების მრუდის ტიპის მრუდი. ზემოთ შემოთავაზებული თამაშის ქვედა და ზედა ფასის გეომეტრიული ინტერპრეტაციის გამოყენებით, ვპოულობთ β = 1 (ნახ. 7.8) და (ნახ. 7.9). თამაშს არ აქვს უნაგირის წერტილი; გამოსავალი შერეული სტრატეგიების სფეროში უნდა ვეძებოთ. პრობლემა გარკვეულწილად წააგავს წინა მაგალითის პრობლემას. მართლაც, მცირე ღირებულებებისთვის კფუნქცია იქცევა როგორც ფუნქცია –(x – y) 2, ხოლო თამაშის ამოხსნა მიიღება, თუ წინა მაგალითის ამოხსნისას A და B მოთამაშეების როლები შებრუნებულია; იმათ. ჩვენი ოპტიმალური სტრატეგია იქნება სუფთა სტრატეგია x = 1/2, ხოლო მოწინააღმდეგის ოპტიმალური სტრატეგია S B = იქნება ექსტრემალური სტრატეგიების გამოყენება y = 0 და y = 1 იგივე სიხშირით. ეს ნიშნავს, რომ ჩვენ ყოველთვის უნდა გამოვიყენოთ ფარგლები, გამოითვლება გადატვირთვაზე x = 1/2 და მტერმა ყველა შემთხვევაში ნახევარში საერთოდ არ უნდა გამოიყენოს მანევრი, ხოლო ნახევარში - მაქსიმალური შესაძლო მანევრი.

ბრინჯი. 7.8 ნახ. 7.9.

ადვილია იმის დამტკიცება, რომ ეს გამოსავალი იქნება k ≤ 2-ისთვის. მართლაც, საშუალო ანაზღაურება მოწინააღმდეგის სტრატეგიისთვის არის S B = და ჩვენი სტრატეგიისთვის. Xფუნქციით გამოხატული , რომელსაც k ≤ 2 მნიშვნელობებისთვის აქვს ერთი მაქსიმუმი x = 1/2, რომელიც უდრის α თამაშის ქვედა ფასს. მაშასადამე, S B სტრატეგიის გამოყენება უზრუნველყოფს მოწინააღმდეგეს α-ზე მეტი წაგების გარანტიას, საიდანაც ირკვევა, რომ α - თამაშის დაბალი ღირებულება - არის თამაშის ν ფასი.

k > 2-ისთვის a(x) ფუნქციას აქვს ორი მაქსიმუმი (ნახ. 7.10), რომლებიც სიმეტრიულად მდებარეობს x = 1/2 წერტილებში x 0 და 1 - x 0 და x 0-ის მნიშვნელობა დამოკიდებულია k-ზე.

ცხადია, ზე კ\u003d 2 x 0 \u003d 1 - x 0 \u003d ½; მატებასთან ერთად კწერტილები x 0 და 1 - x 0 ერთმანეთისგან შორდებიან, უახლოვდებიან უკიდურესი წერტილები(0 და 1). ამიტომ, თამაშის გადაწყვეტა დამოკიდებული იქნება კ. დავაყენოთ k-ის კონკრეტული მნიშვნელობა, მაგალითად k = 3 და ვიპოვოთ თამაშის გამოსავალი; ამისათვის განვსაზღვრავთ a(x) მრუდის მაქსიმუმის აბსცისა x 0-ს. a(x) ფუნქციის წარმოებულს გავუტოლებთ ნულს, ვწერთ განტოლებას x 0-ის დასადგენად:

ამ განტოლებას აქვს სამი ფესვი: x \u003d 1/2 (სადაც მიღწეულია მინიმუმი) და x 0, 1 - x 0, სადაც მიიღწევა მაქსიმალური. განტოლების რიცხობრივად ამოხსნით, დაახლოებით ვპოულობთ x 0 ≈ 0,07; 1 - x 0 ≈ 0.93.

მოდით დავამტკიცოთ, რომ ამ შემთხვევაში თამაშის გამოსავალი არის შემდეგი წყვილი სტრატეგია:

ჩვენი სტრატეგიით და მტრის სტრატეგიით ზესაშუალო ანაზღაურება არის

იპოვეთ მინიმალური a 1 (y) 0-ზე< у < 1. Функция a 1 (y) симметрична относительно y = 1/2 и может иметь только один или два максимума; ее минимум, во всяком случае, достигается либо в середине отрезка (0, 1), либо на его концах. Полагая у = 0 (или у = 1), найдем

დაყენება y = 1/2, მივიღებთ

რომელიც მეტია 1-ზე (0); შესაბამისად, თამაშის ფასი არ არის 1-ზე ნაკლები (0):

ახლა ვთქვათ, რომ მოწინააღმდეგე იყენებს სტრატეგიას S B * და ჩვენ ვიყენებთ x სტრატეგიას. მაშინ საშუალო ანაზღაურება იქნება

მაგრამ ჩვენ ზუსტად ავირჩიეთ x 0 ისე, რომ x = x 0-ზე მიღწეული იყოს გამოხატვის მაქსიმუმი (7.2); აქედან გამომდინარე,

იმათ. მოწინააღმდეგეს, რომელიც იყენებს S B * სტრატეგიას, შეუძლია თავიდან აიცილოს 0,530-ზე მეტი ზარალი; მაშასადამე, ν = 0,530 არის თამაშის ფასი, ხოლო სტრატეგიები S A * და S B * იძლევა გამოსავალს. ეს ნიშნავს, რომ ჩვენ უნდა გამოვიყენოთ x = 0.07 და x = 0.93 სამიზნეები იგივე სიხშირით, ხოლო მტერმა არ უნდა მანევრირება იგივე სიხშირით და მანევრირება მაქსიმალური გადატვირთვით.

გაითვალისწინეთ, რომ ანაზღაურება ν = 0.530 შესამჩნევად აღემატება თამაშის ქვედა ფასს , რომელიც ჩვენ შეგვიძლია მოგაწოდოთ ჩვენი მაქსიმალური სტრატეგიის გამოყენებით x 0 = 1/2.

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

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

დასასრულს, ჩვენ აღვნიშნავთ, რომ სასრული თამაშებისგან განსხვავებით, უსასრულო თამაშებს შეიძლება არ ჰქონდეს გამოსავალი. მოდით მოვიყვანოთ უსასრულო თამაშის მაგალითი, რომელსაც არ აქვს გამოსავალი. ორი მოთამაშე ასახელებს ნებისმიერ მთელ რიცხვს. ვინც დაასახელა უფრო დიდი ნომერი, მეორისგან იღებს 1 რუბლს. თუ ორივე ერთ ნომერს დაურეკავს, თამაში ფრედ მთავრდება. თამაშს გამოსავალი აშკარად არ აქვს. თუმცა, არსებობს უსასრულო თამაშების კლასები, რომელთა გამოსავალი ნამდვილად არსებობს.

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

A მოთამაშის მოცემული სტრატეგიების არჩევის ალბათობების (ფარდობითი სიხშირეების) ვექტორი ავღნიშნოთ შემდეგნაირად:
P = (p 1, p 2,…, p m),
სადაც p i ≥ 0, p 1 + p 2 +…+ p m = 1. მნიშვნელობა p i ეწოდება A i სტრატეგიის გამოყენების ალბათობას (ფარდობით სიხშირეს).

ანალოგიურად, B მოთამაშისთვის შემოტანილია ალბათობის უცნობი ვექტორი (შეფარდებითი სიხშირეები), რომელსაც აქვს ფორმა:
Q = (q 1, q 2,…, q n),
სადაც q j ≥ 0, q 1 + q 2 +…+ q n = 1. q j რაოდენობას ეწოდება B j სტრატეგიის გამოყენების ალბათობა (ფარდობითი სიხშირე). წმინდა სტრატეგიების A 1 , A 2 , …A m და B 1, B 2, …B n სტრატეგიების სიმრავლეს (ერთობლიობას) თითოეული მათგანის არჩევის ალბათობის ვექტორებთან ერთად ეწოდება. შერეული სტრატეგიები.

სასრულ ანტაგონისტური თამაშების თეორიაში მთავარი თეორემაა ფონ ნეუმანის თეორემა: ყველა სასრულ მატრიცის თამაშს აქვს მინიმუმ ერთი ოპტიმალური გადაწყვეტა, შესაძლოა შერეულ სტრატეგიებს შორის.
ამ თეორემიდან გამომდინარეობს, რომ არა კარგად განსაზღვრულ თამაშს აქვს მინიმუმ ერთი ოპტიმალური გადაწყვეტა შერეულ სტრატეგიებში. ასეთ თამაშებში გამოსავალი იქნება P * და Q * ოპტიმალური შერეული სტრატეგიების წყვილი, ისეთი, რომ თუ ერთ-ერთი მოთამაშე დაიცავს თავის ოპტიმალურ სტრატეგიას, მაშინ მეორე მოთამაშისთვის არ არის მომგებიანი მისი ოპტიმალური სტრატეგიიდან გადახვევა.
A მოთამაშის საშუალო ანაზღაურება განისაზღვრება მათემატიკური მოლოდინით:

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

სტრატეგიები P * , Q * ეწოდება ოპტიმალური შერეულისტრატეგიები, თუ M A (P, Q *) ≤ M A (P * , Q *) ≤ M A (P * , Q) (1)
ამ შემთხვევაში M A (P * , Q *) ეწოდება ფასზეთამაშები და აღინიშნება V-ით (V * ≤ V ≤ V *). უტოლობებიდან პირველი (1) ნიშნავს იმას A მოთამაშის გადახრა მისი ოპტიმალური შერეული სტრატეგიიდანიმ პირობით, რომ მოთამაშე B დაიცავს თავის ოპტიმალურ შერეულ სტრატეგიას, იწვევს საშუალო მოგების შემცირებასმოთამაშე A. უტოლობებიდან მეორე ნიშნავს იმას B მოთამაშის გადახრა მისი ოპტიმალური შერეული სტრატეგიიდანიმ პირობით, რომ მოთამაშე A დაიცავს თავის ოპტიმალურ შერეულ სტრატეგიას, იწვევს B მოთამაშის საშუალო დანაკარგის ზრდას.

ზოგადად, ასეთი პრობლემები წარმატებით წყდება ამ კალკულატორით.

მაგალითი.

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

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

ჩვენ ვპოულობთ გარანტირებულ ანაზღაურებას, რომელიც განისაზღვრება თამაშის დაბალი ფასით a = max(a i) = 2, რაც მიუთითებს მაქსიმალურ სუფთა სტრატეგიაზე A 1 .
თამაშის ზედა ფასი b = min(b j) = 7. ეს მიუთითებს უნაგირის წერტილის არარსებობაზე, რადგან a ≠ b, მაშინ თამაშის ფასი არის 2 ≤ y ≤ 7 ფარგლებში. ჩვენ ვპოულობთ თამაშის ამოხსნას. შერეულ სტრატეგიებში. ეს აიხსნება იმით, რომ მოთამაშეებს არ შეუძლიათ მოწინააღმდეგეს თავიანთი წმინდა სტრატეგიების გამოცხადება: უნდა დამალონ თავიანთი ქმედებები. თამაში შეიძლება გადაიჭრას მოთამაშეებს სტრატეგიების შემთხვევით არჩევის მიცემით (სუფთა სტრატეგიების შერევით).

2. შეამოწმეთ ანაზღაურებადი მატრიცა დომინანტური რიგებისა და დომინანტური სვეტებისთვის.
ანაზღაურების მატრიცაში არ არის დომინანტური რიგები და დომინანტური სვეტები.

3. თამაშის გამოსავლის პოვნა შერეულ სტრატეგიებში.
ჩამოვწეროთ განტოლებათა სისტემა.
I მოთამაშისთვის
4p1 +7p2 +2p3 = y
7p1 +3p2 +p3 = y
2p 1 +2p 2 +8p 3 = y
p1 +p2 +p3 = 1

II მოთამაშისთვის
4q1 +7q2 +2q3 = y
7q1 +3q2 +2q3 = y
2q1 +q2 +8q3 = y
q 1 + q 2 + q 3 = 1

ამ სისტემების ამოხსნისას გაუსის მეთოდით, ჩვენ ვპოულობთ:

y=4 1/34
p 1 = 29/68 (1-ლი სტრატეგიის გამოყენების ალბათობა).
p 2 = 4/17 (მე-2 სტრატეგიის გამოყენების ალბათობა).
p 3 = 23/68 (მე-3 სტრატეგიის გამოყენების ალბათობა).

I მოთამაშის ოპტიმალური შერეული სტრატეგია: P = (29/68; 4/17; 23/68)
q 1 = 6 / 17 (1-ლი სტრატეგიის გამოყენების ალბათობა).
q 2 = 9/34 (მე-2 სტრატეგიის გამოყენების ალბათობა).
q 3 = 13/34 (მე-3 სტრატეგიის გამოყენების ალბათობა).

II მოთამაშის ოპტიმალური შერეული სტრატეგია: Q = (6/17; 9/34; 13/34)
თამაშის ფასი: y = 4 1/34

5. თამაშის თეორია და სტატისტიკური გადაწყვეტილებები

5.1. მატრიცის თამაშინულოვანი ჯამი

ეკონომიკური და მათემატიკური მოდელირება ხორციელდება შემდეგ პირობებში:

გარკვეულობა;

გაურკვევლობები.

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

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

მოდელირება გაურკვევლობის პირობებში შეესაბამება ამისთვის საჭირო ზოგიერთი მონაცემის სრულ არარსებობას (თამაშის თეორია).

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

თამაშის თეორიაში გამოიყენება შემდეგი ძირითადი ცნებები:

სტრატეგია;

მოგების ფუნქცია.

გადაადგილება ჩვენ მოვუწოდებთ მოთამაშის მიერ თამაშის წესებით გათვალისწინებული ერთ-ერთი მოქმედების არჩევანს და განხორციელებას.

სტრატეგია - ეს არის ტექნოლოგია სიტუაციიდან გამომდინარე, თითოეული ნაბიჯისთვის მოქმედების კურსის არჩევისთვის.

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

მატრიცულ თამაშში ანაზღაურების ფუნქცია წარმოდგენილია როგორც გადახდის მატრიცა :

სად არის გადახდის თანხა I მოთამაშისთვის, რომელმაც აირჩია ნაბიჯი, II მოთამაშისგან, რომელმაც აირჩია ნაბიჯი.

ასეთ წყვილ თამაშში ორივე მოთამაშის ანაზღაურებადი ფუნქციების მნიშვნელობები ტოლია სიდიდით და საპირისპირო ნიშნით, ე.ი. და ამ თამაშს ჰქვია ნულოვანი ჯამი .

„მატრიცული თამაშის თამაშის“ პროცესი წარმოდგენილია შემდეგნაირად:

დაყენებულია გადახდის მატრიცა;

მოთამაშე I, განურჩევლად II მოთამაშისა, ირჩევს ამ მატრიცის ერთ-ერთ მწკრივს, მაგალითად, -th;

II მოთამაშე, I მოთამაშის მიუხედავად, ირჩევს ამ მატრიცის ერთ-ერთ სვეტს, მაგალითად, - th;

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

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

მაგალითი

განვიხილოთ თამაში.

გადახდის მატრიცა მოცემულია:

.

მიეცით საშუალება I მოთამაშეს, განურჩევლად II მოთამაშისა, აირჩიოს ამ მატრიცის მე-3 სტრიქონი, ხოლო მოთამაშე II, მიუხედავად I მოთამაშისა, აირჩიოს ამ მატრიცის მე-2 სვეტი:

შემდეგ მოთამაშე I მიიღებს 9 ერთეულს II მოთამაშისგან.

5.2. ოპტიმალური სუფთა სტრატეგია მატრიცულ თამაშში

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

ანაზღაურების მატრიცის i-ე რიგის სვლად არჩევით, მოთამაშე I უზრუნველყოფს მინიმუმ ანაზღაურებას უარეს შემთხვევაშიროდესაც II მოთამაშე ცდილობს მინიმუმამდე დაიყვანოს ეს მნიშვნელობა. მაშასადამე, მოთამაშე I ავირჩევ მე-ე რიგს, რომელიც მას მაქსიმალურ ანაზღაურებას მისცემს:

.

II მოთამაშეც ანალოგიურად კამათობს და თავის თავს გარანტირებული აქვს მინიმალური ზარალის გარანტია:

.

შემდეგი უტოლობა ყოველთვის მართალია:

მნიშვნელობა ეწოდება დაბალი თამაშის ფასი .

მნიშვნელობა ეწოდება თამაშის ყველაზე მაღალი ფასი .

ოპტიმალურ სტრატეგიებს ე.წ სუფთა , თუ მათთვის თანასწორობა დაკმაყოფილებულია:

,

.

მნიშვნელობა ეწოდება თამაშის წმინდა ფასი , თუ .

ოპტიმალური სუფთა სტრატეგიები და ფორმა უნაგირის წერტილი გადახდის მატრიცა.

უნაგირის წერტილისთვის, შემდეგი პირობები დაკმაყოფილებულია:

ანუ ელემენტი არის ყველაზე პატარა მწკრივში და ყველაზე დიდი სვეტში.

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

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

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

მაგალითი

.

ანაზღაურების მატრიცის ზოგიერთი მწკრივის არჩევით, როგორც სვლა, მოთამაშე I უზრუნველყოფს ანაზღაურებას უარეს შემთხვევაში არანაკლებ მნიშვნელობის სვეტში მონიშნული:

ამიტომ, მოთამაშე I აირჩევს ანაზღაურების მატრიცის მე-2 რიგს, რომელიც უზრუნველყოფს მას მაქსიმალურ ანაზღაურებას, მიუხედავად II მოთამაშის სვლისა, რომელიც შეეცდება მინიმუმამდე დაიყვანოს ეს მნიშვნელობა:

მოთამაშე II კამათობს ანალოგიურად და ირჩევს 1 სვეტს სვლად:

ამრიგად, არსებობს ანაზღაურების მატრიცის სადა წერტილი:

შეესაბამება I და II მოთამაშის ოპტიმალურ სუფთა სტრატეგიას, რომ მოთამაშე I არ შეამცირებს ანაზღაურებას II მოთამაშის მიერ სტრატეგიის ნებისმიერი ცვლილებისთვის და მოთამაშე II არ გაზრდის თავის ზარალს I მოთამაშის სტრატეგიის ნებისმიერი ცვლილებისთვის.

5.3. ოპტიმალური შერეული სტრატეგია მატრიცულ თამაშში

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

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

I მოთამაშის შერეული სტრატეგია არის რიცხვების ასეთი მოწესრიგებული ნაკრები (ვექტორი), რომელიც აკმაყოფილებს ორ პირობას:

1) ამისთვის, ანუ, ანაზღაურების მატრიცის თითოეული მწკრივის არჩევის ალბათობა არ არის უარყოფითი;

2), ანუ, ანაზღაურების მატრიცის თითოეული მწკრივის არჩევანი აგრეგატში წარმოადგენს სრული ჯგუფიივენთი.

II მოთამაშის შერეული სტრატეგია არის რიცხვების მოწესრიგებული ნაკრები (ვექტორი), რომელიც აკმაყოფილებს პირობებს:

გადახდის თანხა მოთამაშე I, რომელიც ირჩევს შერეულ სტრატეგიას

II მოთამაშისგან, რომელმაც აირჩია შერეული სტრატეგია

,

არის საშუალო

.

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

და ,

თუ რაიმე თვითნებური შერეული სტრატეგიისთვის დაკმაყოფილებულია შემდეგი პირობა:

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

თუ ანაზღაურების მატრიცაში არ არის უნაგირის წერტილი, მაშინ

,

ანუ არსებობს დადებითი განსხვავება (შეინარჩუნა განსხვავება )

- ³ 0,

და მოთამაშეებმა უნდა ეძებონ დამატებითი შესაძლებლობები, რათა დამაჯერებლად მიიღონ მეტი წილი ამ განსხვავებაში მათ სასარგებლოდ.

მაგალითი

განვიხილოთ თამაში, რომელიც მოცემულია ანაზღაურების მატრიცით:

.

დაადგინეთ არის თუ არა უნაგირის წერტილი:

, .

გამოდის, რომ ანაზღაურების მატრიცაში არ არის უნაგრული წერტილი და გაუნაწილებელი სხვაობაა:

.

5.4. ოპტიმალური შერეული სტრატეგიების მოძიება

2×2 თამაშისთვის

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

დაე, ალბათობა იმისა, რომ მოთამაშე მე აირჩევს ანაზღაურების მატრიცის პირველ რიგს

უდრის . მაშინ მეორე რიგის არჩევის ალბათობაა.

დაე, II მოთამაშის პირველი სვეტის არჩევის ალბათობა ტოლი იყოს. მაშინ მეორე სვეტის არჩევის ალბათობაა.

მეორე მოთამაშის მიერ I მოთამაშის გადახდის ოდენობა უდრის:

I მოთამაშის მოგების და II მოთამაშის ზარალის უკიდურესი მნიშვნელობა შეესაბამება პირობებს:

;

.

ამრიგად, I და II მოთამაშეების ოპტიმალური შერეული სტრატეგიები, შესაბამისად, არის:

5.5. 2× თამაშების გეომეტრიული ამოხსნან

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

თამაშის გამოსავლის პოვნის ძირითადი ეტაპები შემდეგია.

ჩვენ ვანერგავთ კოორდინატთა სისტემას თვითმფრინავზე. დავდოთ ხაზის სეგმენტი ღერძზე. ამ სეგმენტის მარცხენა და მარჯვენა ბოლოებიდან ვხატავთ პერპენდიკულარებს.

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

I მოთამაშის ასეთი ანაზღაურება სტრატეგიის არჩევისას იქნება და , ხოლო სტრატეგიის არჩევისას იქნება და .

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

ოპტიმალური შერეული სტრატეგიის პოვნა I მოთამაშისთვის

,

რომელიც შეესაბამება I მოთამაშის ანაზღაურების ქვედა საზღვარზე მდებარე წერტილს მაქსიმალური ორდინატით.

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

ამრიგად, თამაში დაყვანილია თამაშად და განხილულ მაგალითში II მოთამაშის ოპტიმალური შერეული სტრატეგიაა

,

სადაც ალბათობა იგივეა რაც თამაშში:

5.6. თამაშის გადაჭრამ× ნ

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

მოდით, მოცემული იყოს განზომილების ანაზღაურებადი მატრიცა:

.

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

II მოთამაშის მიერ არჩეული თითოეული ნაბიჯისთვის, I მოთამაშის ანაზღაურება განისაზღვრება დამოკიდებულებებით:

ჩვენ ვყოფთ უტოლობების ორივე მხარეს და ვნერგავთ ახალ აღნიშვნას:

Თანასწორობა

მიიღებს ფორმას:

იმის გამო, რომ მოთამაშე I მსურს მაქსიმალურად გაზარდოს ანაზღაურება, საპასუხო უნდა იყოს მინიმუმამდე დაყვანილი. შემდეგ ხაზოვანი პროგრამირების პრობლემა I მოთამაშისთვის მიიღებს ფორმას:

შეზღუდვების ქვეშ

II მოთამაშის პრობლემა ანალოგიურად არის აგებული, როგორც ორმაგი:

შეზღუდვების ქვეშ

ამოცანების ამოხსნისას სიმპლექსის მეთოდით ვიღებთ:

,

5.7. მატრიცული თამაშების ამოხსნის თავისებურებები

ოპტიმალური სტრატეგიების პოვნის პრობლემის გადაჭრამდე უნდა შემოწმდეს ორი პირობა:

შესაძლებელია თუ არა გადახდის მატრიცის გამარტივება;

აქვს თუ არა ანაზღაურების მატრიცას უნაგირის წერტილი.

განვიხილოთ გადახდის მატრიცის გამარტივების შესაძლებლობა:

იმის გამო, რომ ფეხბურთელი ვეძებ ყველაზე დიდი გამარჯვება, მაშინ -ე სტრიქონი შეიძლება წაიშალოს ანაზღაურების მატრიციდან, რადგან ის არასოდეს გამოიყენებს ამ ნაბიჯს, თუ შემდეგი მიმართება დაკმაყოფილდება ნებისმიერი სხვა -ე ხაზით:

ანალოგიურად, მინიმალური ზარალისკენ მიისწრაფვის, მოთამაშე II არასოდეს აირჩევს ანაზღაურების მატრიცაში მე-მე სვეტს, როგორც სვლას და ეს სვეტი შეიძლება გადაიკვეთოს, თუ შემდეგი მიმართება მოქმედებს ნებისმიერ სხვა მე-ე სვეტთან:

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

მაგალითი

ანაზღაურების მატრიცის გათვალისწინებით:

.

გადახდის მატრიცის გამარტივება:

უნაგირის წერტილის არსებობა:

5.8. ბუნებასთან თამაში

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

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

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

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

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

მაგალითი

მოგების მატრიცა:

.

რისკის მატრიცა:

შესაძლებელია ორი პრობლემის განცხადება გადაწყვეტის არჩევის შესახებ ბუნებასთან მატრიცულ თამაშში :

მოგების მაქსიმიზაცია;

რისკის მინიმიზაცია.

გადაწყვეტილების პრობლემა შეიძლება დაყენდეს ორიდან ერთ-ერთ პირობაზე:

- რისკის ქვეშ როდესაც ცნობილია ბუნების სტრატეგიების ალბათობის განაწილების ფუნქცია, მაგალითად, თითოეული შემოთავაზებული კონკრეტული ეკონომიკური სიტუაციის წარმოშობის შემთხვევითი ცვლადი;

- გაურკვევლობის პირობებში როდესაც ასეთი ალბათობის განაწილების ფუნქცია უცნობია.

5.9. ამოცანების ამოხსნა სტატისტიკური ამონახსნების თეორიაში

რისკის ქვეშ

რისკის ქვეშ მყოფი გადაწყვეტილებების მიღებისას მოთამაშე I იცის ალბათობა ბუნების მდგომარეობების დაწყება.

მაშინ მიზანშეწონილია I მოთამაშემ აირჩიოს სტრატეგია, რომლისთვისაც ანაზღაურების საშუალო ღირებულება, აღებული ხაზის გასწვრივ, არის მაქსიმალური :

.

რისკის მატრიცით ამ პრობლემის გადაჭრისას, ჩვენ ვიღებთ იგივე გამოსავალს მინიმალური საშუალო რისკი :

.

5.10. ამოცანების ამოხსნა სტატისტიკური ამონახსნების თეორიაში

გაურკვევლობის პირობებში

გაურკვევლობის პირობებში გადაწყვეტილების მიღებისას შეგიძლიათ გამოიყენოთ შემდეგი კრიტერიუმები :

უოლდის მაქსიმინის კრიტერიუმი;

კრიტერიუმი მინიმალური რისკიველური;

პესიმიზმის კრიტერიუმი - ჰურვიცის ოპტიმიზმი;

ლაპლასის არასაკმარისი მიზეზის პრინციპი.

განვიხილოთ მაქსიმინ უოლდის კრიტერიუმი .

ბუნებასთან თამაში ტარდება ისე, როგორც გონივრულ აგრესიულ მოწინააღმდეგესთან, ანუ გადაზღვევის მიდგომა ხორციელდება ანაზღაურების მატრიცისთვის უკიდურესი პესიმიზმის პოზიციიდან:

.

განვიხილოთ Savage მინიმალური რისკის კრიტერიუმი .

წინა მიდგომის მსგავსად, უკიდურესი პესიმიზმის პოზიციიდან რისკის მატრიცისთვის:

.

განვიხილოთ პესიმიზმის კრიტერიუმი - ჰურვიცის ოპტიმიზმი .

ის იძლევა შესაძლებლობას არ იხელმძღვანელოთ არც უკიდურესი პესიმიზმით და არც უკიდურესი ოპტიმიზმით:

სად არის პესიმიზმის ხარისხი;

at - უკიდურესი ოპტიმიზმი,

at - უკიდურესი პესიმიზმი.

განვიხილოთ ლაპლასის არასაკმარისი მიზეზის პრინციპი .

ვარაუდობენ, რომ ბუნების ყველა მდგომარეობა თანაბრად სავარაუდოა:

,

.

დასკვნები მეხუთე განყოფილებაში

მატრიცულ თამაშში მონაწილეობს ორი მოთამაშე და ანაზღაურების ფუნქცია, რომელიც ემსახურება დამარცხებული მოთამაშისგან გამარჯვებულის გადახდის ოდენობის განსაზღვრას, წარმოდგენილია ანაზღაურების მატრიცის სახით. შეთანხმდნენ, რომ მოთამაშე I ირჩევს ანაზღაურების მატრიცის ერთ-ერთ მწკრივს, როგორც სვლას, ხოლო მოთამაშე II ირჩევს მის ერთ-ერთ სვეტს. შემდეგ ამ მატრიცის არჩეული მწკრივისა და სვეტის კვეთაზე არის I მოთამაშის გადახდის რიცხვითი მნიშვნელობა II მოთამაშისგან (თუ ეს მნიშვნელობა დადებითია, მაშინ მე ნამდვილად მოვიგე მოთამაშე, ხოლო თუ უარყოფითია, მაშინ II მოთამაშე არსებითად მოიგო).

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

2×2 თამაშებისთვის ოპტიმალური შერეული სტრატეგიების პოვნა ხდება ცნობილი ფორმულების გამოყენებით ოპტიმალური ალბათობების გამოთვლით. 2×n თამაშების გეომეტრიული ამოხსნის გამოყენებით, მათში ოპტიმალური შერეული სტრატეგიების განსაზღვრა მცირდება 2×2 თამაშებისთვის ოპტიმალური შერეული სტრატეგიების პოვნამდე. m×n თამაშების ამოსახსნელად გამოიყენება წრფივი პროგრამირების მეთოდი მათში ოპტიმალური შერეული სტრატეგიების მოსაძებნად.

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

თუ მოთამაშე II არის გაურკვეველი ფაქტორების ერთობლიობა, რომელიც დამოკიდებულია ობიექტურ რეალობაზე და არ აქვს ანტაგონისტური კონფლიქტის შეღებვა, მაშინ ასეთ თამაშს უწოდებენ თამაშს ბუნებასთან და მის გადასაჭრელად გამოიყენება სტატისტიკური გადაწყვეტილებების თეორიის პრობლემები. შემდეგ, ანაზღაურების მატრიცასთან ერთად, შემოღებულია რისკის მატრიცა და შესაძლებელია მატრიცულ თამაშში გადაწყვეტის არჩევის პრობლემის ორი ფორმულირება ბუნებასთან: მოგების მაქსიმიზაცია და რისკის მინიმუმამდე შემცირება.

სტატისტიკური გადაწყვეტილებების თეორიის ამოცანების გადაჭრა რისკის პირობებში გვიჩვენებს, რომ მიზანშეწონილია I მოთამაშისთვის აირჩიოს სტრატეგია, რომლისთვისაც ანაზღაურების საშუალო მნიშვნელობა (მოლოდინი) ანაზღაურების მატრიცის ხაზის გასწვრივ არის მაქსიმალური, ან ( რაც იგივეა) რისკის მატრიცის ხაზით აღებული რისკის საშუალო მნიშვნელობა (მოლოდინი) მინიმალურია. გაურკვევლობის პირობებში გადაწყვეტილების მიღებისას გამოიყენება შემდეგი კრიტერიუმები: უოლდის მაქსიმალური კრიტერიუმი, Savage-ის მინიმალური რისკის კრიტერიუმი, ჰურვიცის პესიმიზმი-ოპტიმიზმის კრიტერიუმი, ლაპლასის არასაკმარისი მიზეზის პრინციპი.

კითხვები თვითშემოწმებისთვის

როგორ არის განსაზღვრული თამაშის თეორიის ძირითადი ცნებები: მოძრაობა, სტრატეგია და ანაზღაურებადი ფუნქცია?

როგორ არის წარმოდგენილი ანაზღაურების ფუნქცია მატრიცულ თამაშში?

რატომ ჰქვია მატრიცულ თამაშს ნულოვანი ჯამი?

როგორია მატრიცის თამაშის პროცესი?

რომელ თამაშს ჰქვია m×n თამაში?

რა არის მატრიცული თამაშის ოპტიმალური სტრატეგია?

რა არის ოპტიმალური სტრატეგია მატრიცული თამაშისათვის, რომელსაც ეწოდება სუფთა?

რას ნიშნავს ანაზღაურების მატრიცის უნაგირის წერტილი?

რა არის ოპტიმალური სტრატეგია მატრიცული თამაშისთვის, რომელსაც ეწოდება შერეული?

როგორია მოთამაშის შერეული სტრატეგია?

რა ანაზღაურება აქვს I მოთამაშეს მეორე მოთამაშისგან, რომელმაც აირჩია შერეული სტრატეგიები?

რომელ შერეულ სტრატეგიებს ეწოდება ოპტიმალური?

რას ნიშნავს გაუნაწილებელი განსხვავება?

რა მეთოდი გამოიყენება 2×2 თამაშების ოპტიმალური შერეული სტრატეგიების მოსაძებნად?

როგორ მოიძებნება ოპტიმალური შერეული სტრატეგიები 2×n თამაშებისთვის?

რა მეთოდი გამოიყენება m×n თამაშების ოპტიმალური შერეული სტრატეგიების მოსაძებნად?

რა თვისებები აქვს მატრიცული თამაშების ამოხსნას?

რას ნიშნავს გადახდის მატრიცის გამარტივება და რა პირობებში შეიძლება მისი განხორციელება?

რომელი მატრიცული თამაშია უფრო ადვილად ამოსახსნელი, როცა ანაზღაურების მატრიცას აქვს ან არ აქვს სადა წერტილი?

თამაშის თეორიის რა პრობლემებია დაკავშირებული სტატისტიკური გადაწყვეტილებების თეორიის პრობლემებთან?

როგორ გარდაიქმნება ანაზღაურებადი მატრიცა რისკის მატრიცაში?

გადაწყვეტილებების არჩევის პრობლემის რა ორი ფორმულირებაა შესაძლებელი ბუნებასთან მატრიცულ თამაშში?

რა ორი პირობით შეიძლება დადგეს გადაწყვეტილების მიღების პრობლემები ბუნებასთან მატრიცულ თამაშში?

რა სტრატეგია არის მიზანშეწონილი, რომ მოთამაშე I აირჩიოს რისკის ქვეშ არსებული სტატისტიკური გადაწყვეტილებების თეორიის პრობლემის გადაჭრისას?

რა გადაწყვეტილების მიღების კრიტერიუმები შეიძლება გამოვიყენოთ სტატისტიკური გადაწყვეტილებების თეორიის პრობლემების გადაჭრისას გაურკვევლობის პირობებში?

პრობლემის გადაჭრის მაგალითები

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

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

ინვერსიული მატრიცა გამოითვლება:

მნიშვნელობები ნაპოვნია:

.

ალბათობა გამოითვლება:

გაყიდვებიდან მიღებული საშუალო შემოსავალი განისაზღვრება:

.

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

ხარჯები 1 კონვ. ერთეულები სექტემბერ-ოქტომბრის პროდუქტები იყო: პირველი ჯგუფისთვის (გულ-სისხლძარღვთა სამკურნალო საშუალებები და ანალგეტიკები) - 20 მანეთი; მეორე ჯგუფისთვის (ინფექციური, ხველების საწინააღმდეგო საშუალებები) - 15 რუბლი.

რამდენიმეზე დაკვირვების მიხედვით ბოლო წლებშიკომპანიის მარკეტინგის სამსახურმა დაადგინა, რომ თბილ ამინდში განხილული ორი თვის განმავლობაში მას შეუძლია გაყიდოს 3050 ჩვეულებრივი ერთეული. ერთეულები პირველი ჯგუფის პროდუქტები და 1100 კონვ. ერთეულები მეორე ჯგუფის პროდუქტები; ცივ პირობებში - 1525 არბ. ერთეულები პირველი ჯგუფის პროდუქტები და 3690 კონვ. ერთეულები მეორე ჯგუფი.

ამინდის შესაძლო ცვლილებებთან დაკავშირებით, ამოცანაა განისაზღვროს კომპანიის სტრატეგია პროდუქციის წარმოებაში, რომელიც უზრუნველყოფს მაქსიმალურ შემოსავალს გაყიდვიდან 40 რუბლის გასაყიდად. 1 კონვ. ერთეულები პირველი ჯგუფის პროდუქტები და 30 გვ. - მეორე ჯგუფი.

გადაწყვეტა. ფირმას აქვს ორი სტრატეგია:

წელს თბილი ამინდი იქნება;

ცივი ამინდი იქნება.

თუ კომპანია მიიღებს სტრატეგიას და რეალურად თბილი ამინდია (ბუნების სტრატეგია), მაშინ წარმოებული პროდუქცია (პირველი ჯგუფის წამლები 3050 ჩვეულებრივი და მეორე ჯგუფის 1100 ჩვეულებრივი ერთეული) სრულად იქნება რეალიზებული და შემოსავალი იქნება. იყოს

3050×(40-20)+1100×(30-15)=77500 რ.

გრილი ამინდის პირობებში (ბუნების სტრატეგია) მეორე ჯგუფის წამლები სრულად გაიყიდება, პირველი ჯგუფი კი მხოლოდ 1525 ჩვეულებრივი ერთეულის ოდენობით. ერთეულები და ზოგიერთი წამალი გაუყიდველი დარჩება. შემოსავალი იქნება

1525×(40-20)+1100×(30-15)-20×()=16500 რ.

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

1525×(40-20)+3690×(30-15)=85850 რ.

თბილ ამინდში შემოსავალი იქნება

1525×(40-20)+1100×(30-15)-() ×15=8150 რ.

თუ გავითვალისწინებთ ფირმას და ამინდს, როგორც ორ მოთამაშეს, ვიღებთ ანაზღაურების მატრიცას

,

თამაშის ფასი დიაპაზონშია

ანაზღაურების მატრიციდან ჩანს, რომ ყველა პირობით, კომპანიის შემოსავალი იქნება მინიმუმ 16,500 რუბლი, მაგრამ თუ ამინდის პირობები ემთხვევა არჩეულ სტრატეგიას, მაშინ კომპანიის შემოსავალი შეიძლება იყოს 77,500 რუბლი.

მოდი ვიპოვოთ თამაშის გამოსავალი.

ფირმის მიერ სტრატეგიის გამოყენების ალბათობა აღვნიშნოთ, როგორც სტრატეგია - მეშვეობით და . თამაშის გრაფიკულად გადაჭრა, ჩვენ ვიღებთ , ხოლო თამაშის ფასი რ.

ოპტიმალური წარმოების გეგმა წამლებიიქნება

ამრიგად, ფირმამ მიზანშეწონილია 2379 ჩვეულებრივი ერთეულის წარმოება სექტემბერსა და ოქტომბერში. ერთეულები პირველი ჯგუფის პრეპარატები და 2239.6 ჩვეულებრივი ერთეული. ერთეულები მეორე ჯგუფის წამლები, შემდეგ ნებისმიერ ამინდში იგი მიიღებს შემოსავალს მინიმუმ 46,986 რუბლი.

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

ვალდეს კრიტერიუმი:

ჰურვიცის კრიტერიუმი: განსაზღვრულობისთვის, ჩვენ ვეთანხმებით, შემდეგ კომპანიის სტრატეგიას

სტრატეგიისთვის

მიზანშეწონილია ფირმამ გამოიყენოს სტრატეგია.

სავაჟის კრიტერიუმი. პირველ სვეტში მაქსიმალური ელემენტია 77500, მეორე სვეტში არის 85850.

რისკის მატრიცის ელემენტები გვხვდება გამოხატულებიდან

,

სად,,

რისკის მატრიცას აქვს ფორმა

,

მიზანშეწონილია გამოიყენოთ სტრატეგია ან .

ამიტომ მიზანშეწონილია ფირმამ გამოიყენოს სტრატეგია ან .

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

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

განსახილველი პრობლემისთვის ცნობილი იყოს, რომ თბილი და ცივი ამინდის ალბათობა ტოლია და 0,5-ის ტოლია, მაშინ ფირმის ოპტიმალური სტრატეგია განისაზღვრება შემდეგნაირად:

ფირმამ სასურველია გამოიყენოს სტრატეგია ან.

ამოცანები დამოუკიდებელი მუშაობისთვის

1. საწარმოს შეუძლია აწარმოოს სამი სახის პროდუქტი (A, B და C), ხოლო მიიღოს მოგება, რომელიც დამოკიდებულია მოთხოვნაზე. მოთხოვნამ, თავის მხრივ, შეიძლება მიიღოს ოთხი მდგომარეობიდან ერთ-ერთი (I, II, III და IV). შემდეგ მატრიცაში ელემენტები ახასიათებენ მოგებას, რომელსაც საწარმო მიიღებს --ე პროდუქტის გამოშვებისას და --ე მოთხოვნის მდგომარეობას:

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

უნაგირის წერტილი

IN თამაშის თეორიას.ტ. ( უნაგირის ელემენტი) არის სვეტის უდიდესი ელემენტი თამაშის მატრიცები, რომელიც ასევე არის შესაბამისი მწკრივის ყველაზე პატარა ელემენტი (in ორკაციანი ნულოვანი ჯამის თამაში). ამრიგად, ამ დროს ერთი მოთამაშის მაქსიმუმი უდრის მეორის მინიმქსს; S.t. არის წერტილი წონასწორობა.

მინიმალური თეორემა

მინიმალური სტრატეგია ე.წ მინიმალური სტრატეგია.

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

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

დაკარგვის ფუნქცია

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

მოთამაშის ოპტიმალური შერეული სტრატეგიაარის მისი სუფთა სტრატეგიების გამოყენების სრული ნაკრები თამაშის მრავალჯერად გამეორებაში იმავე პირობებში მოცემული ალბათობით.

მოთამაშის შერეული სტრატეგია არის მისი სუფთა სტრატეგიების გამოყენების სრული ნაკრები თამაშის მრავალჯერადი გამეორების შემთხვევაში იმავე პირობებში მოცემული ალბათობით.

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

2. თამაშის ფასი უნიკალურია.

Doc-in:ვთქვათ არის 2 თამაშის ფასი ვდა , რომლებიც მიიღწევა წყვილზე და შესაბამისად, მაშინ

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

Doc-in:
, სად

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