Strategiile de dominanță și redundanță
Luați în considerare mai multe metode de a simplifica matricea de plată.
Prima metodă. utilizate pentru a reduce dimensiunea matricei se bazează pe una dintre cele mai importante concepte în teoria jocurilor - noțiunea de strategii de dominanță.
Dacă elementul rând Înțelept cel puțin (≥) Rândul i-lea j-lea. atunci spunem că rândul i-lea domină rândul j-lea. Prin urmare, un jucător nu folosește strategia-j-lea, ca victoria sa la strategia i-lea nu este mai mică decât la strategia j-a, indiferent de modul în care jucătorul jocul B.
În mod similar, în cazul în care cel puțin (≥) coloana j-lea element de coloană-înțelept i-lea. atunci spunem că coloana j-lea domină coloana i-lea. Prin urmare, jucătorul B nu utilizează strategia i-lea, ca și pierderea (câștig egal cu jucătorului A) nu mai este la strategia-j-lea (≤), decât în strategia i-lea, indiferent de modul în care jucătorul joacă A. Strategii, peste care este dominat de alte strategii trebuie să fie eliminate, și pentru a le atribui probabilitate zero. La valoarea jocului nu va afecta. Dar dimensiunea matricei meniurile jocului. Prin această decizie, și aveți nevoie pentru a începe jocul.
Un caz special de poziție dominantă este dublirovaniestrategy.
Dacă jocul matrice taxe cont cuprinde mai multe rânduri identice (coloane), unele dintre ele să lăsați doar o singură linie, iar rândurile rămase (coloane) se aruncă. Strategiile atribuie probabilitate scoase din uz de zero.
Simplificarea (reducerea dimensiunii) matricea de plată prin eliminarea strategiilor pure evident nefavorabile posibil ținând cont de următoarea teoremă privind strategiile dominante:
Fie I - un joc în care i-lea strategie matrice primul jucător domină i + 1 și G - joc a cărui matrice obținută din matricea I, cu excepția i + 1 strategie (linie). apoi:
1. Prețul de joc I este egal cu prețul jocului G;
2. mixtă optimă strategie Q * = (q1 *, q2 *, ..., qn *) al doilea jucător în joc G este, de asemenea, strategia mixtă optimă în joc I;
3. În cazul în care P * = (p1 *, p2 *, ..., pi *. P * i + 2, ..., pm *) cea mai bună strategie de amestec de primul jucător în joc G, atunci este amestecat strategia P * = (p1 *, p2 *, ..., pi *. * p i + 2, ..., pm *) este optim în joc I.
Din cele de mai sus, rezultă că primul și cel de-al doilea nu are sens să folosească o strategie dominată, astfel încât toate strategiile dominate pot fi eliminate, și anume de fapt, a scăzut rânduri și coloane din matricea originală, care corespunde acestor rânduri. Această conversie reduce dimensiunea originalului matricei de plată A, pentru a simplifica astfel, căutarea soluțiilor optime.
Luați în considerare câteva exemple de utilizare a jocurilor calculator matrice de decizie.
Exemplul 1. O matrice joc plată date ca:
Simplificarea jocului (simplifica matricea de plăți).
siruri de 1 si a 4 sunt egale. De aceea, am renunța la linia patra. P4 probabilitate = 0. Obținem matricea:
2a linie domină 3a string (6> 3, 5> 4, 8 = 8, 7> 6). De aceea se debaraseze al treilea rând. P3 probabilitate = 0. Obținem matricea:
2a coloana domina coloana 3 (9 = 9, 5 <8). Поэтому отбросим 3-й столбец. Вероятность q3 = 0. Получим матрицу:
Liniile nu sunt comparabile una cu cealaltă (8> 6, 4 <7), столбцы тоже (8 <9, 6> 5; 8> 4, 6 <7; 9> 4, 5 <7). Дальнейшее упрощение невозможно. Мы свели игру 4×4 к игре 2×3.
Exemplul 2: Jocuri Matrix
Primul pas: A1 domină A2. 2- expunged lea rând, ca rezultat obținem p2 = matricea 0 și plata:
Pasul 2: A1 dominant A3. 1- eliminându-lea rând, rezultatul este matricea p1 = 0 și plata:
Pasul 3: B2 B1 domină expunged coloană 1- lea, rezultatul este q1 = 0 și plata matrice:
etapa a 4: B3 B4 domină expunged 2 - lea coloană, rezultatul este q3 = 0 și matricea de plată:
5-lea pas: A3 dominat de A4. expunged 4 - lea rând, rezultatul este p4 = 0 și matricea de plată:
Pasul 2: B2 domină B4 expunged coloana a patra, rezultatul este q4 = 0 și plata matrice:
Ca urmare a simplificării plății matricei a arătat că jocul are o soluție optimă unică în strategiile pure, ceea ce ei spun vectori de probabilitate P și Q.
Ca urmare a simplificării plății matricei sa stabilit prezența unui punct de șa și soluția optimă obținută în strategii pure: Un prim jucător trebuie să funcționeze tot timpul, prin selectarea strategiei A3. iar jucătorul B selectează strategia B2.
Același rezultat se obține în cazul în care utilizați Maximin strategie.
V * = max min aij = max = 6
V * = min max aij = min = 6
V * = V * = 6, A32 elementul de matrice este un punct de șa.
Notă. În cazul în care jocul este m × n are un punct de șa, mereu am obține, după simplificarea jocului matrice de plată 1 × 1.
Continuăm luarea în considerare a metodelor pentru a simplifica matricea de plată.
O altă metodă pentru câștigurile matricei de transformare (matrice de plată) pe baza teorema dovedită în teoria jocurilor transformări afine.
Teorema privind transformările afine. Transformarea afină (transformare similaritate și forfecare) matricea payoff, adică conversia tuturor elementelor matricei A a formei: a'ij = k * aij + b, unde k ≠ 0 și b - orice constantă, nu se schimbă soluția jocului. În plus, prețul jocului V transformat „poate fi derivată din prețul jocului inițial V prin aceeași regulă: V“ = kV + b
Acest lucru înseamnă, în special, că sarcina de joc, practic, nu contează ce unități se măsoară câștigurile, cum ar fi în ruble sau în alte valute.
Adaosul (scădere) a unei sume fixe b pentru fiecare aij element al matricei O plată se va schimba cu aceeași valoare câștigul (pierderea) a fiecărui jucător, fără a schimba soluțiile de joc. Această caracteristică poate fi utilizată pentru a transforma matricea originală a jocului într-o formă mai convenabilă. De exemplu, în cazul în care elementele de matrice payoff reprezintă fracțiuni cu un numitor comun, Aij matricei poate fi multiplicată cu fiecare element printr-o constantă, prin care elementele matricei transformate ar fi numere întregi; în cazul în care majoritatea celulelor sunt umplute cu elemente de matrice identice, atunci ele pot fi deduse din fiecare element al matricei de zerouri, care sunt egale cu elementele matricei corespunzătoare. În plus, prețul de joc V „este întotdeauna posibil să se facă un rezultat pozitiv, și anume, V „> 0, pe care le folosim în reducerea problemelor de joc la o problemă de programare liniară.
La sfârșitul acestei secțiuni vom da o formulă de conversie din valoarea convertită a jocului V „la V inițial:
Exemplul 3. Set de joc matrice taxe cont:
Este necesar să se simplifice matricea jocului.
1 - lea pas: se înmulțește fiecare dintre elementele matricei A pentru k = 0,01, obținem:
2 - lea PAS: fiecare element al matricei A „adăuga b = 4, obținem matricea:
Astfel, am primit din matricea de plată cu elemente pozitive și mici în magnitudine. Lucrul cu o astfel de matrice este mai simplă decât matricea originală. Elementele matricei A 'preparat prin transformarea:
Exemplul 4. O jocuri cu matrice de plată este dată în formă. Simplificarea jocului (pentru a simplifica matricea de plăți) pentru a găsi soluția optimă.