Minimax

teoremă
(Redirecționat de la Teorema minimax)
Acest articol se referă la conceptul din teoria jocurilor. Pentru alte sensuri, vedeți Minimax (dezambiguizare).

Minimax (numit uneori minmax) este o regulă de decizie utilizată în teoria jocurilor, statistică și filosofie și care constă în minimizarea pierderii maxime posibile. Alternativ, abordarea poate fi și cea a maximizării câștigului minim (maximin). A început din teoria jocului cu sumă zero cu doi jucători, acoperind atât cazurile în care jucătorii fac mutări alternativ și cele în care fac mutări simultan. Regula a fost extinsă și la jocuri mai complexe și la procese generale de luare a deciziilor în condiții de incertitudine.

Teoria jocurilor

modificare

În teoria jocurilor simultane, o strategie minimax este o strategie mixtă care face parte din soluția unui joc cu sumă zero. În jocurile cu sumă zero, soluția minimax este aceeași cu echilibrul Nash.

Teorema Minimax

modificare

Teorema minimax afirmă că:

Oricare ar fi jocul cu sumă zero cu strategii finite și doi jucători, există o valoare V și o strategie mixtă pentru fiecare jucător, astfel încât (a) Dată fiind strategia lui 2, câștigul lui 1 este V, și (b) Dată fiind strategia lui 1, câștigul lui 2 este -V.

Echivalent, strategia jucătorului 1 îi garantează un câștig de V indiferent de strategia jucătorului 2, și în același timp jucătorul 2 își poate garanta un câștig de -V. Numele de minimax apare deoarece fiecare jucător încearcă, la fiecare pas, să minimizeze câștigul maxim al celuilalt — deoarece jocul este cu sumă zero, își maximizează astfel propriul câștig minim.

Această teoremă a fost enunțată de John von Neumann[1], care a afirmat: "Din câte pot vedea, nu poate să existe o teorie a jocurilor … fără acea teoremă … am considerat că nimic nu merita publicat până când nu a fost demonstrată teorema minimax".[2]

B alege B1 B alege B2 B alege B3
A alege A1     +3     -2     +2
A alege A2     -1      0     +4
A alege A3     -4     -3     +1

Următorul exemplu de joc cu sumă zero, în care A și B mută simultan, ilustrează soluțiile minimax. Se presupune că fiecare jucător are la dispoziție trei variante, și se consideră matricea câștigurilor A afișată la dreapta. Se presupune că matricea câștigurilor lui B este aceeași matrice, cu semnele schimbate. Atunci, alegerea minimax pentru A este A2 deoarece cel mai prost rezultat posibil este să piardă 1, în timp ce alegerea minimax pentru B este B2 deoarece cel mai slab rezultat pe care îl poate obține este 0. Totuși, această soluție nu este stabilă, deoarece dacă B crede că A va alege A2, atunci B va alege B1 pentru a câștiga 1; apoi dacă A crede că B va alege B1 atunci A va alege A1 pentru a câștiga 3; apoi B va alege B2; și în cele din urmă ambii jucători vor realiza dificultatea deciziei, deci este necesară o strategie mai stabilă.

Unele variante sunt dominate de altele și pot fi eliminate: A nu va alege A3 deoarece și A1 și A2 produc rezultate mai bune, indiferent de ce alege B; B nu va alege B3 deoarece B2 va produce un rezultat mai bun, indiferent ce alege A.

A poate evita o pierdere așteptată de peste 1/3 alegând A1 cu probabilitatea 1/6 și A2 cu probabilitatea 5/6, indiferent ce alege B. B poate asigura un câștig așteptat de cel puțin 1/3 folosind o strategie aleatoare de alegere, cu B1 cu probabilitatea 1/3 și B2 cu probabilitatea 2/3, indiferent ce alege A. Aceste strategii minimax mixte sunt stabile și nu mai pot fi îmbunătățite.

  1. ^ Von Neumann, J: Zur theorie der gesellschaftsspiele Math. Annalen. 100 (1928) 295-320
  2. ^ John L Casti (). Five golden rules: great theories of 20th-century mathematics – and why they matter. New York: Wiley-Interscience. p. p. 19. ISBN 0-471-00261-5.