Strategie dominantă

În teoria jocurilor, strategia dominantă (denumită deseori simplu dominare) este cea mai bună strategie posibilă pentru un jucător, indiferent de modul în care jucătorii adverși pot juca. Multe jocuri simple pot fi rezolvate cu ajutorul strategiei dominante. De cealaltă parte, intranztivitatea, apare în jocurile unde o strategie poate fi mai bună sau mai rea decât o alta pentru un anume jucător, funcție de cum joacă adversarul. 

Terminologie

Când un jucător încearcă să aleagă "cea mai bună" strategie dintre opțiunile disponibile, acel jucător va compara două strategii A și B pentru a-și da seama care este mai bună. Rezultatul comparației poate fi:

• B domină A: alegând B se obține mereu un rezultat cel puțin la fel de bun ca în cazul alegerii A. Există 2 posibilități:
  • B domină strict A: alegând B se obține mereu un rezultat mai bun decât alegând A, indiferent de ce fac ceilalți jucători.
  • B domină slab A: alegând B se obține un rezultat care, cel puțin într-un caz, este mai bun decât dacă am fi ales A. În toate celelalte cazuri rezultatul alegerii lui B trebuie să fie cel puțin egal cu cel al lui A. 
• B și A sunt intranzitive: B nici nu domină, nici nu este dominat de A. Alegerea lui A este mai bună în unele cazuri, în timp ce alegerea lui B este mai bună în altele, în funcție de modul în care adversarul alege să joace. De exemplu, B este "hârtia" în timp ce A este "foarfeca", în jocul "Piatră, hârtie, foarfecă".
• B este dominată de A: alegând B nu se obține niciodată un rezultat mai bun decât alegând A, indiferent de cum joacă celălalt jucător. Există 2 posibilități:
  • B este slab dominată de A: alegând B, există cel puțin un caz în care rezultatul obținut de B este mai prost decât rezultatul obținut de A, ținându-se cont de posibilitățile oponentului. În toate celelalte cazuri, B este egal cu A (i.e. Strategia A domină slab strategia B).
  • B este strict dominată de A: alegând B se obține în toate cazurile un rezultat mai prost decât dacă s-ar fi ales A, indiferent de modul în care joacă adversarul. (Strategia A domină strict B).

Această noțiune poate fi generalizată dincolo de compararea a două strategii.

• Strategia B este strict dominantă dacă strategia B domină strict oricare altă strategie posibilă.
• Strategia B este slab dominantă dacă strategia B domină toate celelalte strategii, cu excepția unora pe care le domină slab
• Strategia B este strict dominată dacă există o altă strategie care domină strict B
• Strategia B este slab dominată dacă există o altă strategie care domină slab B

Strategie: Este rezultatul unui plan complet de contingență pentru un jucător într-un anumit joc. Un astfel de plan specifică complet comportamentul jucătorului, descriind fiecare acțiune pe care jucătorul ar lua-o într-o anumită situație (sau într-un anumit punct de decizie). Deci o strategie reprezintă toate deciziile pe care jucătorul le va lua în cazul fiecărei informații furnizate de celălalt jucător (i.e. decizii a jucătorului advers)

Raționalitate: ipoteza că fiecare jucător acționează într-un mod care este proiectat pentru maximizarea câștigurilor personale. Aceste câștiguri pot fi sub formă monetară, utilitară, de minimizare a disconfortului (sau a altui aspect negativ) etc., fundamentală rămânând ideea că jucătorii vor acționa pentru maximizarea beneficiilor personale

Cunoștințe comune: ipoteza că fiecare jucător cunoaște jocul în care participă, regulile lui și beneficiile asociate cu fiecare acțiune posibilă, și realizează faptul că și ceilalți jucători au același nivel de înțelegere. Această premiză permite unui jucător să emită judecăți de valoare asupra acțiunilor altui jucător, luându-le în considerare în luarea propriilor decizii (pe baza ipotezei raționalității prezentată precedent)

Dominația și echilibrul Nash

	C	D
C	1, 1	0, 0
D	0, 0	0, 0

Dacă o strategie strict dominantă există pentru un jucător, acel jucător va juca respectiva strategie în fiecare echilibru Nash al jocului. Dacă ambii jucători au o strategie strict dominantă, jocul are un singur echilibru Nash unic. Cu toate acestea, echilibrul Nash nu este în mod necesar și "eficient", în sensul că există combinații de strategii ale celor doi jucători care ar fi mai bune pentru ambii, însă care nu reprezintă un echilibru. Jocul clasic folosit pentru ilustrarea acestui concept este Dilema prizonierului.

Strategiile strict dominate nu pot fi parte a unui echilibru Nash, și, prin urmare,este irațională jucarea lor de către un jucător. Pe de altă parte, strategiile slab dominate pot fi parte a unui echilibru Nash. Un exemplu ilustrativ este matricea de mai sus. 

Strategia C domină slab strategia D. Dacă se alege C, avem funcție de ce joacă oponentul: 1 dacă oponentul joacă (de asemenea) C, 0 dacă oponentul joacă D. Deci este mai bine a juca C cel puțin într-un caz decât a juca D, când se obține 0 indiferent de strategia aleasă de adversar. Prin urmare, C domină slab D. Cu toate acestea, $(D,D)$ este un echilibru Nash. Presupunând că ambii jucători aleg strategia D, nici un jucător nu-și va putea îmbunătăți situația unilateral, rezultatul rămânând 0 pentru fiecare jucător. Acesta satisface cerințele unui echilibru Nash. Presupunând că ambii jucători aleg C, nici un jucător nu-și va putea îmbunătăți situația unilateral, căci o astfel de schimbare i-ar aduce ca rezultat 0 în loc de 1. Deci și acesta satisface cerințele unui echilibru Nash.

Eliminarea iterativă a strategiilor strict dominate (IESDS)

Eliminarea iterativă (sau ștergerea) a strategiilor dominate este o metodă comună pentru rezolvarea jocurilor iterative. În primul rând cel puțin o strategie dominată este înlăturată din planul de joc al fiecărui jucător, de vreme ce niciun jucător rațional nu ar juca astfel de strategii. Astfel rezultă un nou joc, mai redus ca opțiuni. Acum, anumite strategii, care nu erau dominate înainte, pot deveni dominate în acest joc mai redus. Procesul se reia până când nu mai există strategie dominată pentru vreun jucător. Acest proces este valid de vreme ce se presupune că jucătorii sunt raționali și au cunoștință despre capacitatea de raționare a fiecăruia dintre ei. 

Există două versiuni ale acestui proces. O versiune presupune doar eliminarea strategiilor strict dominate. Dacă, după completarea acestui proces, rămâne câte-o singură strategie valabilă pentru fiecare jucător, acel set de strategii reprezintă unicul echilibru Nash.

O altă versiune implică eliminarea atât a strategiilor strict dominate cât și a celor slab dominate. Dacă, după completarea acestui proces, rămâne câte-o singură strategie valabilă pentru fiecare jucător, acest set de strategii reprezintă, de asemenea, un echilibru Nash. Totuși, spre deosebire de prima versiune a procesului, eliminarea strategiilor slab dominate poate elimina potențiale echilibre Nash. Ca urmare, echilibrul Nash găsit prin eliminarea și a strategiilor slab dominate poate să nu fie singurul echilibru Nash al jocului (în anumite jocuri, inclusiv ordinea eliminării strategiilor dominate slabe poate oferi, la sfârșitul procesului, echilibre Nash diferite).

În orice caz, dacă prin iterarea eliminării strategiilor dominate rămâne o singură strategie valabilă pentru fiecare jucător, acel joc se numește a fi rezolvabil prin dominanță.

Note

• Fudenberg, Drew; Tirole, Jean (1993). Game Theory. MIT Press. 
• Gibbons, Robert (1992). Game Theory for Applied Economists. Princeton University Press. ISBN 0-691-00395-5. 
• Ginits, Herbert (2000). Game Theory Evolving. Princeton University Press. ISBN 0-691-00943-0. 
• Leyton-Brown, Kevin; Shoham, Yoav (2008). Essentials of Game Theory: A Concise, Multidisciplinary Introduction. San Rafael, CA: Morgan & Claypool Publishers. ISBN 978-1-59829-593-1. . Un 88-pagina matematice introducere; a se vedea Secțiunea 3.3. Gratuit on-line Arhivat în 15 august 2000, la Wayback Machine. de la mai multe universități.
• Rapoport, A. (1966). Two-Person Game Theory: The Essential Ideas. University of Michigan Press. 
• Jim Ratliff Jocul de Curs de Teorie: Dominația Strategică
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press. ISBN 978-0-521-89943-7. . O referință cuprinzătoare dintr-un calcul de perspectivă; a se vedea Secțiunile 3.4.3, 4.5. Descărcabil gratuit on-line.

Acest articol cuprinde material de la Dominant strategy de la PlanetMath, licențiat cu Creative Commons Atribuire/Distribuire în condiții identice.