joc de suma zero
strategii
castig
matricea pozitiilor
punct de echilibru
solutia stabila
minimax
strategii mixte
teorema minimax
Strategia MAXIMIN
joc de suma zero strategii castig matricea pozitiilor punct de echilibru solutia stabila minimax strategii mixte teorema minimax |
Sa consideram un joc de suma zero in care ceea ce eu castig celalalt pierde. Fiecare jucator dispune de trei strategii posibile pe care le numim A, B, si C (sa presupunem ca exista trei carti avand imprimate literele respective). Premiile sau platile constau in distribuirea a zece monede, ce se vor imparti in functie de strategiile alese de ambii jucatori si care sunt prezentate in urmatorul tabel numit matricea pozitiilor. Castigurile mele, pe care le pot primi, sunt aratate pe un fond verde. Rezultatele celuilalt jucator apar pe fond rosiatic. Pentru orice combinare de strategii, rezultatele ambilor jucatori insumeaza zece.
|
MATRICEA CASTIGURILOR MELE |
MATRICEA CASTIGURILOR CELUILALT JUCATOR | |||||||||
| Strategia celuilalt jucator | Strategia celuilalt jucator | |||||||||
| A | B | C | A | B | C | |||||
|
Strategia mea |
A | 9 | 1 | 2 | Strategia mea | A | 1 | 9 | 8 | |
| B | 6 | 5 | 4 | B | 4 | 5 | 6 | |||
| C | 7 | 8 | 3 | C | 3 | 2 | 7 | |||
De exemplu. Daca eu joc cartea C si celalalt jucator alege cartea B atunci eu voi primi opt monede, iar celalalt jucator va primi doua.
Acesta este un joc de suma zero. Se numeste joc de suma zero acel joc in care ceea ce castiga un jucator este exact ceea ce pierde celalalt.
Pentru a afla ce strategie imi convine mai mult vom analiza matricea ce indica castigurile mele, cea pe fond verde. Ignor strategia (cartea) care va fi aleasa de celalalt jucator. O forma de a analiza jocul in luarea deciziei mele este gasirea rezultatului minim pe care il pot obtine cu fiecare carte. In urmatorul tabel s-a adaugat o coloana indicand rezultatele minime.
|
MATRICEA CASTIGURILOR MELE |
|||||
| Strategia celuilalt jucator | |||||
| A | B | C | mInimi | ||
|
Strategia mea |
A | 9 | 1 | 2 | 1 |
| B | 6 | 5 | 4 | 4 | |
| C | 7 | 8 | 3 | 3 | |
De fapt,
Dintre toate aceste posibile rezultate minime cel pe care il prefer este 4, fiind maximul minimilor. Strategia MAXIMIN consta in alegerea cartii B, aceasta strategie garantandu-mi ca, drept minim, voi obtine 4.
Putem prevedea strategia celuilalt jucator? Sa presupunem ca celalalt jucator vrea si el sa aleaga strategia MAXIMIN. Vom arata acum doar castigurile celuilalt jucator din care reiese castigul minim pe care-l poate obtine pentru fiecare din strategiile sale. Sublinime maximul minimilor si strategia sa maximin.
|
MATRICEA CASTIGURILOR CELUILALT JUCATOR |
||||
| Strategia celuilalt jucator | ||||
| A | B | C | ||
|
Strategia mea |
A | 1 | 9 | 8 |
| B | 4 | 5 | 6 | |
| C | 3 | 2 | 7 | |
| minimi | 1 | 2 | 6 | |
De fapt,
Strategia sa MAXIMIN consta in jucarea cartii C cu care se garanteaza ca va obtine cel putin 6.
Acesta este un joc cu solutie stabila. Niciunul din jucatori nu simte tentatia sa schimbe strategia. Sa presupunem ca jocul se repeta de mai multe ori. Eu voi juca intotdeauna strategia mea maximin (B), iar celalalt va juca intotdeauna strategia sa maximin (C). Fiecare stie ce va juca celalalt in urmatorul joc. Niciunul nu va fi tentat sa-si schimbe strategia deoarece cel care se decide in acest sens va pierde.
Se numeste punct de echilibru punctul in care strategiile maximin ale ambilor jucatori coincid.
Nu toate jocurile au un punct de echilibru, o solutie stabila. Stabilitatea jocului anterior dispare prin simpla schimbare a ordinii casutelor BB si BC:
|
MATRICEA CASTIGURILOR MELE |
MATRICEA CASTIGURILOR CELUILALT JUCATOR | |||||||||
| Strategia celuilalt jucator | Strategia celuilalt jucator | |||||||||
| A | B | C | A | B | C | |||||
|
Strategia mea |
A | 9 | 1 | 2 | Strategia mea | A | 1 | 9 | 8 | |
| B | 6 | 4 | 5 | B | 4 | 6 | 5 | |||
| C | 7 | 8 | 3 | C | 3 | 2 | 7 | |||
In acest nou tabel strategia mea maximin continua sa fie B, iar strategia maximin a celuilalt jucator continua sa fie C. Dar solutia acum nu este stabila. Daca jucam de diferite ori si eu imi repet strategia maximin B, celalalt va fi tentat sa-si schimbe strategia, trecand de la C la B obtinand un castig mai mare, 6 in loc de 5.
Bineinteles ca daca celalalt incepe sa aleaga sistematic strategia B eu prefer sa-mi schimb strategia la C pentru a obtine 8. Atunci el va dori sa se intoarca la strategia sa C si asa mai departe.
Cand jocurile ce nu au o solutie stabila se repeta este bine sa se utilizeze strategii mixte. Strategiile mixte constau in atribuirea fiecarei strategii o probabilitate. In jocul pe care il analizam o strategie mixta ar putea fi descrisa sub urmatoarea forma: "Pentru a alege cartea pe care o voi juca voi arunca un zar. Daca zarul arata 1, voi alege cartea A; daca zarul arata un 2 sau un 3, voi alege cartea B; daca zarul arata un 4, un 5 sau un 6, voi alege cartea C". Cu alte cuvinte, voi alege cartea A cu o probabilitate de 1/6, cartea B cu o probabilitate de 1/3 si cartea C cu o probabilitate de 1/2.
Teorema maximin afirma ca in toate jocurile bipersonale de suma zero in care este posibil sa se joace si strategii mixte nu numai pure, strategiile maximin ale fiecarui jucator coincid intotdeauna intr-o solutie stabila, un punct de echilibru. Aceasta teorema a fost demonstrata matematic de catre John Von Neumann intr-un articol publicat in 1928.