Gestione governativa dell'Università della città di Mosca

Dipartimento di Gestione

Dipartimento di Matematica Applicata

Saggio

per disciplina accademica

"Metodi matematici per lo studio dei sistemi di controllo"

Sull'argomento: "Giochi bimatrix. Ricerca di situazioni di equilibrio"

1. Giochi bimatrice

Assolutamente qualsiasi attività di gestione non può esistere senza situazioni di conflitto. Queste sono situazioni in cui due o più parti con interessi diversi si scontrano. È del tutto naturale che ciascuna parte voglia risolvere il conflitto a proprio favore e ottenere il massimo beneficio. Risolvere un problema del genere può essere complicato dal fatto che la parte in conflitto non ha informazioni complete sul conflitto nel suo complesso. In altre parole, possiamo dire che in una situazione di conflitto è necessario prendere la decisione ottimale in condizioni di incertezza.

Per risolvere questo tipo di problemi viene utilizzata la modellazione matematica. Introduciamo alcuni concetti base. Un modello matematico di un gioco conflittuale è chiamato gioco. Le parti in conflitto sono i giocatori, l’azione del giocatore è la mossa, l’insieme delle mosse è la strategia, il risultato del gioco è la vittoria.

Un passaggio obbligatorio prima di risolvere un problema è identificare alcune regole. Di norma, queste regole sono un insieme di requisiti e restrizioni sulle azioni dei giocatori, sullo scambio di informazioni tra giocatori sulle azioni degli avversari, sulle funzioni delle vincite degli avversari, ecc. Le regole devono essere chiare, altrimenti la partita non avrà luogo.

Ad oggi, esistono diversi modi per classificare i giochi. La divisione principale è in giochi a coppie finite non cooperativi con payoff (matrice, posizionale, bi-matrice) e giochi di coalizione. In questo saggio esamineremo i giochi bimatrix.

Giochi con importo fisso– giochi in cui gli interessi dei giocatori, pur non coincidendo, non sono del tutto opposti. Un caso speciale sono i giochi bimatrice.

Un gioco bimatrice lo è fine del gioco due giocatori con somma diversa da zero, in cui i guadagni di ciascun giocatore sono specificati da matrici separatamente per il giocatore corrispondente (in ciascuna matrice, la riga corrisponde alla strategia del giocatore 1, la colonna alla strategia del giocatore 2, a all'intersezione della riga e della colonna nella prima matrice c'è la vincita del giocatore 1, nella seconda matrice - la vincita del giocatore 2.)

Consideriamo un gioco di coppie in cui ogni partecipante ha le seguenti opportunità di scegliere la propria linea di comportamento:

il giocatore A – può scegliere una qualsiasi delle strategie A 1, ..., A m;

giocatore B – una qualsiasi delle strategie B 1, ..., B n;

Se il giocatore A sceglie la strategia A i, giocatore B – B j, alla fine il profitto del giocatore A sarà a ij, giocatore B – b ij. I pagamenti dei giocatori A e B possono essere scritti sotto forma di due tabelle.

Pertanto, se gli interessi dei giocatori sono diversi, ma non necessariamente opposti, vengono utilizzate due matrici di payoff per descrivere il gioco. Questo fatto ha dato il nome a questi giochi: bimatrix.

2. Stato di equilibrio in matrici bimatrice

La soluzione a un gioco bimatrice è una soluzione che in un senso o nell'altro si adatta a entrambi i giocatori. Questa formulazione è molto vaga, poiché in bi giochi di matrici ah, è abbastanza difficile formulare chiaramente gli obiettivi per i giocatori. Una delle opzioni possibili è il desiderio del giocatore di danneggiare il suo avversario a scapito delle proprie vincite, altrimenti l'obiettivo sarà l'opposto.

Solitamente vengono considerati due approcci per risolvere un gioco bimatrice. Il primo è la ricerca di situazioni di equilibrio: si cercano condizioni quando il gioco è in un certo equilibrio, che non è redditizio per nessuno dei giocatori violarlo individualmente. Il secondo è la ricerca di situazioni paretiane ottimali: trovare condizioni in cui i giocatori congiuntamente non possono aumentare il profitto di un giocatore senza ridurre il profitto dell’altro.

Concentriamoci sul primo approccio.

Questo approccio utilizza strategie miste, ad es. caso in cui i giocatori si alternano strategie pure con determinate probabilità.

Lasciamo che il giocatore A scelga la strategia A 1, con probabilità p 1, A 2 – p 2, ..., A m – p m, e

Il giocatore B utilizza la strategia B 1 con probabilità q 1, B 2 – q 2, ..., B n – q n, e

Come criterio per il "successo" del gioco, prendiamo le aspettative matematiche delle vincite dei giocatori, che vengono calcolate utilizzando le formule:

Possiamo quindi formulare la definizione di base:

Distribuzione di probabilità P * (

Se esiste una situazione di equilibrio, la deviazione da essa è svantaggiosa per il giocatore stesso.

Anche il teorema di J. Nash è vero. Ogni gioco bimatrice ha almeno una situazione di equilibrio in strategie miste.

3. Principio generale per la risoluzione dei giochi bimatrice

Tutte le strategie pure del giocatore A vengono successivamente sostituite nella prima disuguaglianza del sistema, assumendo che B aderisca alla sua strategia ottima. Tutte le strategie pure del giocatore B vengono sostituite nella seconda disuguaglianza, assumendo che A aderisca alla sua strategia ottima.

Il sistema risultante di m+n disuguaglianze, la cui soluzione dà il valore degli elementi ottimi strategie miste(P*,Q*) e pagamenti ricevuti dai giocatori nel punto di equilibrio.

Esempio: lotta per il mercato.

La soluzione del problema

v A =-10×1q 1 +2×1*(1-q 1)+(1-p 1)q 1 -(1-p 1)(1-q 1)=-14×1q 1 +3× 1+2q 1 -1

v B =5×1q 1 -2×1*(1-q 1)-(1-p 1)q 1 +(1-p 1)(1-q 1)=9×1q 1 -3×1- 2q1+1

p 1 =1 allora v A =2-12q 1

p 1 =0 allora v A =-1+2q 1

q 1 =1 allora v B =-1+6×1

q 1 =0 allora v B =1–3×1

Componiamo 4 sistemi, trasformiamo, otteniamo.

65. Nel metodo grafico per risolvere giochi 3*3 per trovare strategie ottimali per i giocatori:
a) si costruiscono due triangoli (*risposta*)
b) viene costruito un triangolo.
c) i triangoli non sono affatto costruiti.
66. Il grafico dell'inviluppo inferiore per il metodo grafico di risoluzione dei giochi 2*m rappresenta nel caso generale la funzione:
a) monotonicamente decrescente.
b) monotonicamente crescente.
c) non motorio.
67. Se in un gioco antagonista su un segmento la funzione di payoff del 1° giocatore F(x,y) è uguale a 2*x+C, allora a seconda di C:
a) non ci sono mai punti di sella.
b) ci sono sempre dei punti di sella (*risposta*)
c) un'altra opzione
68. Come si può impostare un problema decisionale in condizioni di incertezza su insiemi finiti:
a) due matrici.
b) vincite.
c) qualcos'altro (*risposta*)
69. In un gioco antagonistico di dimensione arbitraria, il profitto del primo giocatore è:
un numero.
b) molti.
c) vettore, o insieme ordinato.
d) funzione (*risposta*)
70. In un gioco a matrice 3*3 ci sono due componenti della strategia mista del giocatore:
a) determinare la terza (*risposta*)
b) non definire.
71. Un gioco bimatrice può essere definito:
a) due matrici della stessa dimensione con elementi arbitrari,
b) due matrici non necessariamente della stessa dimensione,
c) una matrice.
72. In un gioco di matrici, l'elemento aij è:
a) perdita del 2° giocatore quando usa la strategia j-esima, e del 2° - i-esima strategia(*risposta*)
B) strategia ottimale 2° giocatore quando utilizzato nemico i o j-esima strategia,
c) le vincite del 1° giocatore quando utilizza la strategia j-esima e del 2° - la strategia i-esima,
73. L'elemento di matrice aij corrisponde al punto di sella. Sono possibili le seguenti situazioni:
a) ottimale.
b) pulito.
c) non esiste una risposta chiara (*risposta*)
84. Se tutte le colonne nella matrice sono uguali e hanno la forma (4 3 0 2), allora quale strategia è ottimale per il 2° giocatore?
un primo. b) terzo. c) qualsiasi (*risposta*)
85. Qual è il numero massimo di punti di sella in un gioco 3*3 (la matrice può contenere qualsiasi numero):
a)3.
b)9.
c)27 (*risposta*)
86. Sia X=(1;5) l'insieme delle strategie della 1a
giocatore, Y=(2;8) - insieme di strategie del 2° giocatore. La coppia (1,2)
essere un punto di sella in questo gioco:
a) sempre.
b) qualche volta (*risposta*)
c) mai.
87. Ci sono esattamente 2 situazioni di equilibrio in un gioco bimatrice di dimensione 3*3?
a) Sempre.
b) qualche volta (*risposta*)
c) mai.
88. Supponiamo che in un gioco a matrice di dimensione 2*3 una delle strategie miste del 1° giocatore abbia la forma (0.3, 0.7), e una delle strategie miste del 2° giocatore abbia la forma (0.3, x, x) . Qual è il numero x?
a)0,7 b)0,4 c)qualcos'altro (*risposta*)
89. Il gioco Matrix è caso speciale bimatrice, in cui vale sempre quanto segue:
a) la matrice A è uguale alla matrice B, presa con il segno opposto.
b) la matrice A è uguale alla matrice B.
c) Il prodotto delle matrici A e B è la matrice identità.
90. In un gioco bimatrice, l'elemento rappresenta:
a) le vincite del 2° giocatore quando utilizza la strategia i-esima e del 1° - la strategia j-esima,
b) la strategia ottimale del 2° giocatore quando l'avversario utilizza la strategia i-esima o j-esima/
c) qualcos'altro (*risposta*)
91. In un gioco bimatrice, l'elemento ac corrisponde a una situazione di equilibrio. Sono possibili le seguenti situazioni:
a) la colonna ha elementi uguali a questo elemento (*risposta*)
b) questo elemento è più piccolo di alcuni nella colonna.
c) questo elemento è il più piccolo della colonna.
92. In un gioco a matrice, conoscendo le strategie di ciascun giocatore e la funzione di payoff,
il prezzo del gioco in strategie pure può essere trovato:
a) sempre.
b) qualche volta (*risposta*)
c) la domanda non è corretta.

Nei giochi con somma diversa da zero Tutti i partecipanti al gioco possono vincere o perdere. Gioco bimatriceè un gioco a somma finita non nulla tra due giocatori. In questo caso, per ogni situazione di gioco A i B j, ogni giocatore ha la propria vincita a ij per il primo giocatore e b ij per il secondo giocatore. Ad esempio, il comportamento dei produttori nei mercati imperfettamente competitivi si riduce a un gioco bimatrice. Usando un calcolatore online puoi trovare una soluzione gioco bimatrice, così come le situazioni Situazioni Pareto-ottime e Nash stabili.

Consideriamo situazione di conflitto, in cui ciascuno dei due partecipanti ha le seguenti opportunità di scegliere la propria linea di comportamento:

• il giocatore A – può scegliere una qualsiasi delle strategie A 1,…, A m,
• giocatore B – una qualsiasi delle strategie B 1,…, B n.

Allo stesso tempo, la loro scelta congiunta viene valutata in modo abbastanza definitivo: se il giocatore A sceglie la i-esima strategia A i e il giocatore B sceglie la k-esima strategia B k , alla fine il profitto del giocatore A sarà pari a un certo numero a ik , e la vincita del giocatore B sarà uguale a un certo numero, in generale, a un altro numero b ik .
Esaminando in sequenza tutte le strategie del giocatore A e tutte le strategie del giocatore B, possiamo riempire due tavoli con le loro vincite.

La prima delle tabelle descrive il profitto del giocatore A, mentre la seconda descrive il profitto del giocatore B. Tipicamente, queste tabelle sono scritte sotto forma di matrice.
Qui A è la matrice dei payoff del giocatore A, B è la matrice dei payoff del giocatore B.

Pertanto, nel caso in cui gli interessi dei giocatori siano diversi (ma non necessariamente opposti), si ottengono due matrici di pagamenti: una è la matrice dei pagamenti al giocatore A, l'altra è la matrice dei pagamenti al giocatore B. Pertanto, il il nome che di solito viene assegnato a un gioco del genere sembra del tutto naturale - bimatrice.

equilibrio di Nash– equilibrio, quando ciascun partecipante al gioco sceglie una strategia ottimale per lui, a condizione che gli altri partecipanti al gioco aderiscano a una determinata strategia.
L’equilibrio di Nash non è sempre il più ottimale per i partecipanti. In questo caso, dicono che l'equilibrio non lo è Pareto-ottimale.
Strategia pura– una certa reazione del giocatore a possibili opzioni comportamento degli altri giocatori.
Strategia mista– una reazione probabilistica (non definita con precisione) di un giocatore al comportamento di altri giocatori.

Esempio n. 1. La lotta per i mercati.
L’impresa a intende vendere una partita di beni in uno dei due mercati controllati da un’impresa più grande b. A tal fine, esegue lavoro preparatorio associati a determinati costi. Se l’impresa b indovina in quale mercato l’impresa a venderà il suo prodotto, adotterà delle contromisure per impedirle di “catturare” il mercato (questa opzione significa la sconfitta dell’impresa a); in caso contrario, vince l'impresa a. Supponiamo che per l'impresa a la penetrazione nel primo mercato sia più redditizia della penetrazione nel secondo, ma la lotta nel primo mercato richiede anche più fondi da parte sua. Ad esempio, la vittoria di un'impresa nel primo mercato le porta il doppio del profitto di una vittoria nel secondo, ma una sconfitta nel primo mercato lo rovina completamente.
Creiamo un modello matematico di questo conflitto, considerando l'azienda a come giocatore 1 e l'azienda b come giocatore 2. Strategie per il giocatore 1: UN 1 – penetrazione del mercato 1, UN 2 – penetrazione del mercato 2; Strategie del giocatore 2: IN 1 – contromisure nel mercato 1, IN 2 – contromisure nel mercato 2. Supponiamo che per l'impresa a la sua vittoria nel 1° mercato sia valutata a 2 unità, e la sua vittoria nel 2° mercato sia valutata a 1 unità; La sconfitta dell’impresa a nel 1° mercato è stimata a -10, e nel 2° mercato a -1. Per l’impresa b, la vittoria è rispettivamente di 5 e 1 unità, mentre la sconfitta è di -2 e -1. Di conseguenza, otteniamo un gioco bimatrice µ con matrici dei payoff
.
Secondo il teorema, questo gioco può avere situazioni di equilibrio puro o completamente misto. Non ci sono situazioni di equilibrio nelle strategie pure qui. Assicuriamoci ora che questo gioco abbia una situazione di equilibrio completamente mista. Noi troviamo , .
Quindi, il gioco in esame presenta un'unica situazione di equilibrio (x 0 ;y 0), dove , . Può essere implementato ripetendo il gioco più volte (cioè ripetendo più volte la situazione descritta) come segue: l’impresa a dovrebbe utilizzare le strategie pure 1 e 2 con frequenze di 2/9 e 7/9, e l’impresa b dovrebbe utilizzare strategie pure 1 e 2 con frequenze 3/14 e 11/14. Qualsiasi azienda che devia da questa strategia mista riduce il suo profitto atteso.

Esempio n.2. Trovare situazioni Pareto ottimali e situazioni stabili di Nash per un gioco bimatrice.

Esempio n.3. Ci sono 2 imprese: la prima può produrre uno dei due prodotti A 1 e A 2, la seconda può produrre uno dei due prodotti B 1, B 2. Se la prima impresa produce prodotti A i (i = 1, 2) e la seconda - B j (j = 1, 2), allora il profitto di queste imprese (a seconda che questi prodotti siano complementari o competitivi) è determinato da tabella n. 1:

Prove per il controllo finale

1. È possibile impostare un gioco antagonista:

a) un insieme di strategie per entrambi i giocatori e un punto di sella.

b) un insieme di strategie per entrambi i giocatori e la funzione di payoff del primo giocatore.

2. Il prezzo del gioco esiste sempre per i giochi a matrice in strategie miste.

a) sì.

3.Se tutte le colonne nella matrice dei payoff sono uguali e hanno la forma (4 5 0 1), quale strategia è ottimale per il primo giocatore?

un primo.

b) secondo.

c) uno qualsiasi dei quattro.

4. Supponiamo che in un gioco a matrice una delle strategie miste del 1° giocatore abbia la forma (0.3, 0.7), e una delle strategie miste del 2° giocatore abbia la forma (0.4, 0, 0.6). Qual è la dimensione di questa matrice?

a) 2*3.

c) un'altra dimensione.

5. Il principio della dominanza consente di rimuovere dalla matrice in un solo passaggio:

a) intere linee.

b) numeri individuali.

6. Nel metodo grafico per la risoluzione dei giochi 2*m, si trova direttamente dal grafico:

a) strategie ottimali di entrambi i giocatori.

b) il prezzo del gioco e le strategie ottimali del 2° giocatore.

c) il prezzo del gioco e le strategie ottimali del 1° giocatore.

7. Il grafico dell'inviluppo inferiore per il metodo grafico di risoluzione dei giochi 2*m è nel caso generale:

un rotto.

b) dritto.

c) parabola.

8. In un gioco a matrice 2*2 ci sono due componenti della strategia mista del giocatore:

a) determinare i valori reciproci.

b) indipendente.

9. In un gioco di matrici, l'elemento aij è:

a) le vincite del 1° giocatore quando utilizza la strategia i-esima e del 2° - la strategia j-esima.

b) la strategia ottimale del 1° giocatore quando l'avversario utilizza la strategia i-esima o j-esima.

c) la perdita del 1° giocatore quando utilizza la j-esima strategia e del 2° - la i-esima strategia.

10.L'elemento di matrice aij corrisponde al punto di sella. Sono possibili le seguenti situazioni:

a) questo elemento è rigorosamente il più piccolo di tutti nella riga.

b) questo elemento è il secondo in ordine nella riga.

11. Nel metodo Brown-Robinson, ogni giocatore, quando sceglie una strategia nella fase successiva, è guidato da:

a) le strategie del nemico nelle fasi precedenti.

b) le tue strategie nei passaggi precedenti.

c) qualcos'altro.

12. Secondo il criterio dell'aspettativa matematica, ogni giocatore parte dal fatto che:

a) accadrà la situazione peggiore per lui.

c) tutte o alcune situazioni sono possibili con alcune probabilità date.

13. Sia un gioco di matrici dato da una matrice in cui tutti gli elementi sono negativi. Il prezzo del gioco è positivo:

b) no.

c) non esiste una risposta chiara.

14. Il prezzo del gioco è:

un numero.

b) vettore.

c) matrice.

15.Qual è il numero massimo di punti di sella che possono esserci in un gioco di dimensione 5*5 (la matrice può contenere qualsiasi numero):

16. Supponiamo che in un gioco a matrice di dimensione 2*3 una delle strategie miste del 1° giocatore abbia la forma (0.3, 0.7), e una delle strategie miste del 2° giocatore abbia la forma (0.3, x, 0.5) . Qual è il numero x?

c) un altro numero.

17. Per quale dimensione della matrice del gioco il criterio di Wald si trasforma nel criterio di Laplace?

c) solo negli altri casi.

18. Il prezzo massimo del gioco è sempre inferiore al prezzo minimo del gioco.

b) no.

b) la domanda non è corretta.

19. Quali strategie ci sono in un gioco a matrice:

a) pulito.

b) misto.

c) entrambi.

20. In alcuni giochi antagonisti, i valori della funzione di profitto di entrambi i giocatori per alcuni valori delle variabili possono essere uguali a 1?

a) sempre.

b) a volte.

c) mai.

21. In un gioco a matrice, supponiamo che una delle strategie miste del 1° giocatore sia della forma (0.3, 0.7), e che una delle strategie miste del 2° giocatore sia della forma (0.4, 0.1,0.1,0.4) . Qual è la dimensione di questa matrice?

c) un'altra dimensione.

22. Il principio della dominanza consente di rimuovere dalla matrice in un solo passaggio:

a) intere colonne,

b) numeri individuali.

c) sottomatrici di dimensioni minori.

23. In un gioco a matrice 3*3 ci sono due componenti della strategia mista del giocatore:

a) determinare il terzo.

b) non definire.

24. In un gioco di matrici, l'elemento aij è:

a) perdita del 2° giocatore quando utilizza la strategia j-esima e del 2° - la strategia i-esima.

b) la strategia ottimale del 2° giocatore quando l'avversario utilizza la strategia i-esima o j-esima,

c) le vincite del 1° giocatore quando utilizza la strategia j-esima e del 2° - la strategia i-esima,

25. L'elemento di matrice aij corrisponde al punto di sella. Sono possibili le seguenti situazioni:

a) questo elemento è il più grande della colonna.

b) questo elemento è rigorosamente il più grande in ordine nella riga.

c) la stringa contiene elementi sia maggiori che minori di questo elemento.

26. Secondo il criterio di Wald, ciascun giocatore presuppone che:

a) accadrà la situazione peggiore per lui.

b) tutte le situazioni sono ugualmente possibili.

c) tutte le situazioni sono possibili con determinate probabilità.

27. Il prezzo più basso è inferiore al prezzo più alto del gioco:

b) non sempre.

c) mai.

28. La somma delle componenti di una strategia mista per un gioco a matrice è sempre:

a) equivale a 1.

b) non negativo.

c) positivo.

d) non sempre.

29. Supponiamo che in un gioco a matrice di dimensione 2*3 una delle strategie miste del 1° giocatore abbia la forma (0.3, 0.7), e una delle strategie miste del 2° giocatore abbia la forma (0.2, x, x) . Qual è il numero x?