Maggiore è la dimensione della matrice dei payoff del gioco, più complessa sarà l'analisi. Pertanto, prima di decidere qualsiasi cosa gioco di matrici In primo luogo, è opportuno escludere le strategie dominate dai giocatori (se presenti), riducendo così la dimensione della matrice dei pagamenti. Ma anche escludendo le strategie dominate, ogni giocatore può comunque avere più di due strategie pure (w, pag> 2), quando non è possibile applicare il metodo grafico-analitico.

È stato sviluppato un metodo relativamente semplice che consiste nel ridurre il gioco delle matrici al problema programmazione lineare, che, a sua volta, può essere risolto con metodi ben noti (ad esempio, il metodo del simplesso) o utilizzando numerosi strumenti di modellazione computerizzata (ad esempio, utilizzando il modulo "Ricerca di soluzioni" MS Excel).

Come dimostrato per la prima volta da J. von Neumann, che non è solo il creatore della teoria dei giochi, ma anche uno degli sviluppatori della teoria della programmazione lineare, qualsiasi fine del gioco due persone a somma zero possono essere rappresentate come un problema di programmazione lineare. Questo metodo può essere applicato a qualsiasi gioco a matrice, compresi quelli semplici, la cui soluzione è stata discussa nel paragrafo precedente.

Per considerare il metodo per ridurre un gioco a matrici a un problema di programmazione lineare, è necessario conoscere un'altra proprietà dei giochi a matrici, che si chiama regola affine. Strategie ottimali nei giochi di matrici A e B, i cui elementi delle matrici dei pagamenti sono legati dall'uguaglianza

Dove X> 0, e p è un numero reale qualsiasi, hanno le stesse situazioni di equilibrio (sia in strategie pure che miste), e i prezzi dei giochi soddisfano la seguente condizione: vB = XvA+r.

Questa regola ha significato pratico, poiché molti algoritmi per la risoluzione dei giochi a matrice si basano sul presupposto che tutti gli elementi della matrice dei payoff siano positivi, il che, a sua volta, garantisce un prezzo positivo del gioco. Nel caso in cui la matrice abbia elementi non positivi, è possibile aggiungere a tutti gli elementi della matrice qualsiasi numero maggiore del valore assoluto massimo degli elementi negativi della matrice.

Assumiamo che il prezzo di un gioco abbia una matrice di pagamento Un txp positivo (e > 0). Se così non fosse, allora secondo la regola affine è sempre possibile selezionare un numero p tale che sommandolo a tutti gli elementi della matrice dei payoff si ottiene una matrice con elementi positivi e, quindi, assicura un valore positivo per il prezzo Del gioco. In questo caso, le strategie miste ottimali di entrambi i giocatori non cambiano.

Dalla definizione di una strategia mista ottimale segue che il primo giocatore, aderendo alla sua strategia mista ottimale, vincerà non meno di o per qualsiasi strategia del secondo giocatore (comprese quelle pure), e il secondo giocatore, aderendo alla sua strategia mista ottimale strategia mista, perderà non più di o per qualsiasi strategia del primo giocatore (comprese quelle pulite). Ne consegue che strategie miste X = = (x v x t), y = (y v ..., A n) rispettivamente il primo e il secondo giocatore e il prezzo del gioco o devono soddisfare le relazioni

Dividiamo tutte le equazioni e disuguaglianze in questi sistemi per e (questo può essere fatto, poiché assumendo o > 0) e introduciamo la notazione:

Allora otteniamo

Poiché il primo giocatore cerca di massimizzare il costo del gioco scegliendo i valori x[y quindi il valore reciproco 1/o dovrebbe essere minimizzato scegliendo r g Pertanto, la soluzione del primo problema si riduce a trovare tali valori non negativi R., 2=1,..., Quello al quale

Poiché il secondo giocatore cerca di trovare tali valori sì) e quindi qy in modo che il costo del gioco sia minimo, allora la soluzione del secondo problema si riduce a trovare tali valori non negativi q jj j = 1, ..., p e al quale

Si sono così ottenuti problemi di programmazione lineare duale (LP), che possono essere risolti, ad esempio, utilizzando il metodo del simplesso.

Risolti questi problemi, otteniamo i valori p®, i = 1,t q® y j = 1,..., P.

Quindi il valore del prezzo del gioco o viene determinato dalla condizione

Strategie miste ottimali, ovvero x® e r/?, si ottengono dalle formule

Esempio 4.7. Considera una variante del gioco "Fight for Markets". Due aziende concorrenti A e B decidono di finanziare tre progetti tecnici innovativi. Ogni azienda può investire 100 DSN. unità L’azienda B sta cercando di occupare un mercato in cui l’azienda A è tradizionalmente leader. Nel caso di sviluppo e sviluppo degli stessi progetti, la società A realizzerà un profitto, mentre la società B subirà delle perdite. Se gli investimenti sono diretti a progetti diversi, la società A subirà perdite associate alla ridistribuzione del mercato e il profitto dell'impresa B corrisponderà alla perdita dell'impresa A. È necessario trovare strategie ottimali imprese. L'utile dell'impresa A in diverse situazioni strategiche è presentato nella tabella:

Soluzione dentro MS Excel

Risolviamo il problema utilizzando il programma MS Excel. Al tavolo MS Excel vengono introdotti gli elementi della matrice di pagamento del gioco e, utilizzando le funzioni MIN() e MAX(), il minimo e valori massimi rispettivamente per righe e colonne, quindi utilizzando le stesse funzioni si trovano il maximin e il minimax (Tabella 4.2). Poiché questi valori non coincidono, non esiste un punto di sella nel gioco, ovvero non può essere risolto con strategie pure. Il valore del prezzo del gioco deve essere compreso nell'intervallo (-5; 10).

Tabella 4.2

Verifica della presenza di un punto di sella in un gioco

Per utilizzare un algoritmo per risolvere un gioco riducendolo a un problema di programmazione lineare, applichiamo una regola affine. Utilizzando la funzione MIN(), troviamo il valore minimo degli elementi della matrice di pagamento (-20). Il modulo di questo numero è definito come ABS(MHH(...)). Utilizzando una trasformazione affine con parametri X = 1 e p = 20 otteniamo una nuova matrice dei pagamenti (Tabella 4.3).

Tabella 4.3

Ridurre il gioco ad un problema di programmazione lineare

A destra della matrice dei pagamenti sono indicate arbitrariamente le variabili richieste R.(in questa fase è possibile specificare eventuali valori). Nelle celle sotto la matrice dei pagamenti, i valori vengono determinati utilizzando la funzione SUMPRODUCT()

che verrà utilizzato nei vincoli del problema LI. Questi valori sono selezionati casualmente p.t sono riportati in tabella. 4.3.

Nella cella designata come “Funzione obiettivo”, inserire la formula SOMMA(...), corrispondente all'espressione per la funzione obiettivo

Nella cella denominata “Prezzo del gioco”, inserisci una formula per determinare il prezzo del gioco attraverso il valore della funzione obiettivo:

Nelle celle contrassegnate come x esso vengono introdotte formule per trasformare inversamente le variabili e trovare gli elementi richiesti della strategia mista del primo giocatore x io= u Pj.

Formulazione del primo problema di programmazione lineare: trovare il valore

neanche io RU fornire un minimo di funzioni YjPi * pip in condizioni ^ a ij p i > 1,

La soluzione ad un problema di programmazione lineare viene effettuata utilizzando il modulo “Ricerca soluzioni” del programma MS Excel(l'uso di questo modulo è già stato discusso nel capitolo 2). Il campo “Imposta cella obiettivo” specifica l'indirizzo della cella contenente il valore della funzione obiettivo; selezionare la modalità “Uguale a: valore minimo”. Nel campo “Cellule modificabili” è indicata una matrice delle variabili desiderate r g Facendo clic sul pulsante “Aggiungi” e selezionando un array corrispondente ai vincoli dell'attività, la condizione corrispondente viene impostata nel campo “Vincoli”. Facendo clic sul pulsante “Parametri” si accede alla finestra di dialogo “Parametri ricerca soluzione”, nella quale si selezionano i parametri “Modello lineare” e “Valori non negativi”; i valori degli altri parametri rimangono invariati. Dopo aver chiuso la finestra “Opzioni di ricerca soluzioni” (utilizzando il file OK) Facendo clic sul pulsante “Esegui” nella finestra “Cerca una soluzione”, viene avviato il processo iterativo di ricerca di una soluzione al problema LP.

Al termine di questo processo, viene visualizzata la finestra "Risultati della ricerca della soluzione". Se tutte le condizioni del problema sono state formulate correttamente, tutti i dati, le formule e i parametri sono stati inseriti correttamente, la finestra indicherà “Soluzione trovata. Tutte le restrizioni e le condizioni di ottimalità sono soddisfatte.” In questo caso, per salvare la soluzione è necessario fare clic su OK. I risultati del calcolo sono presentati nella tabella. 4.4.

Il problema LP è risolto in modo simile per il secondo giocatore (Tabella 4.5). Si prega di notare che in questo caso per comodità tecnica, l'array delle variabili richieste è disposto in riga (poiché le strategie del secondo giocatore corrispondono alle colonne della matrice dei payoff), e le celle con restrizioni sono disposte in colonna. Il problema è risolto al massimo e formulato come segue: trova i valori q jt

fornendo la massima funzionalità? IO)* condizioni P R I massime ^ un i) q- q) > 0.

Tabella 4.4

Risultati della risoluzione del problema LP per il primo giocatore

Risultati della risoluzione del problema LP per il secondo giocatore

Tabella 4.5

Nel caso di applicazione preliminare della regola affine, il vero valore del prezzo del gioco si ottiene sottraendo il numero p, che è stato utilizzato per calibrare gli elementi della matrice dei payoff. Soluzione finale del gioco:

I risultati mostrano che la strategia ottimale della società A è la distribuzione dei fondi destinati agli investimenti nelle proporzioni del 29, 60 e 11%, vale a dire 29, 60 e 11 giorni. unità In questo caso, la società A realizzerà un profitto non di meno 0,5 den. unità La società A riceverà il valore di profitto minimo (0,5 unità monetarie) a condizione che la società B aderisca alla sua strategia di investimento del progetto ottimale, vale a dire 39, 25, 36%, cioè investire in progetti da 39, 25 e 36 den. unità rispettivamente. Se la società B si discosta da questa strategia (persegue un modello di investimento diverso), i profitti della società A aumenteranno.

L'analisi della soluzione mostra che per l'azienda B questo gioco non è redditizio (la perdita attesa è di circa 0,5 unità monetarie). Tuttavia, se la società B considera questa perdita relativamente insignificante rispetto al raggiungimento del suo obiettivo: entrare nel mercato tradizionalmente controllato dalla società A, allora, aderendo alla sua strategia ottimale di allocazione degli investimenti, la società B perderà non più di 0,5 den. unità Se la società A si comporta in modo irrazionale, le perdite della società B diminuiranno.

Pertanto, qualsiasi gioco di matrici può essere risolto riducendo il gioco a due problemi di programmazione lineare. Tuttavia, ciò richiede una grande quantità di calcoli, che aumenta con il numero di strategie del giocatore puro. Pertanto, prima di tutto, utilizzando il metodo di eliminazione delle strategie dominate, se possibile, dovresti ridurre il numero di strategie del puro giocatore. Eccezione Debole Le strategie dominate possono portare alla perdita di alcune soluzioni. Se solo fortemente strategie dominate, l’insieme delle soluzioni di gioco non cambierà. Quindi dovresti verificare in tutti i casi la presenza di un punto di sella, cioè verifica del rispetto della condizione min a- = min ma ha...

Se vale, allora i giocatori hanno strategie ottimali pure e la soluzione viene ottenuta automaticamente. Altrimenti, le strategie ottimali saranno miste. Per i giochi a matrice semplice, in cui almeno uno dei giocatori ha solo due strategie, può essere utilizzato il metodo di soluzione grafico-analitica discusso nella sezione 4.2. Per più giochi impegnativiè necessario utilizzare un metodo per ridurre il gioco ad un problema di programmazione lineare e gli strumenti adeguati per risolvere questo problema.

Per concludere questa sezione, notiamo che semplificare la matrice dei payoff eliminando le strategie dominate è importante se il gioco viene risolto manualmente. Se si utilizza un computer per trovare strategie ottimali, allora lo sforzo e il tempo spesi nella ricerca di strategie dominate potrebbero essere sprecati, poiché l'analisi numerica delle matrici originale e semplificata viene eseguita utilizzando lo stesso algoritmo e la differenza nel tempo di calcolo è insignificante .

Verifichiamo se la matrice dei pagamenti ha un punto di sella. Se sì, scriviamo la soluzione del gioco in strategie pure, altrimenti continuiamo ad analizzare la matrice;

Rimuoviamo, se presenti, righe dominate e colonne dominanti. Al loro posto, nelle strategie ottimali dei giocatori, le componenti corrispondenti saranno pari a zero.

H. Risolviamo il gioco delle matrici utilizzando uno dei metodi più noti: metodi di programmazione lineare, metodo approssimato o graficamente (se almeno uno dei giocatori ha solo due strategie pure).

Qualsiasi gioco a matrice può essere ridotto a una coppia di problemi di programmazione lineare doppia simmetrica, il che significa che il metodo del simplesso può essere utilizzato per trovare strategie ottimali per i giocatori e prezzi di gioco.

Un esempio di soluzione personalizzata.

Esempio. Trovare una soluzione al gioco data dalla matrice dei payoff

Innanzitutto controlliamo se la matrice ha un punto di sella. L'elemento più piccolo -3 della prima riga non lo è più grande nella terza colonna; l'elemento più piccolo -1 della seconda riga non è l'elemento più grande della prima colonna; infine, l'elemento più piccolo 2 della terza riga è anche il più grande della terza colonna. Di conseguenza, la matrice ha un punto di sella (3, 3), dove si trova l'elemento UN zz = 2. Ciò significa che il gioco ha una soluzione in strategie pure, ovvero:

- strategia ottimale del primo giocatore;

- strategia ottimale del secondo giocatore;

v= 2 - prezzo del gioco.

Esempio. Trovare una soluzione al gioco data dalla matrice dei payoff

.

Non esiste un punto di sella nella matrice, quindi il gioco ha una soluzione in strategie miste.

Controlliamo se la matrice ha righe e colonne dominanti. Poiché tutti gli elementi della prima riga non sono maggiori dei corrispondenti elementi della terza riga, la prima riga è dominata e può essere cancellata. Puoi anche rimuovere la terza colonna che domina la seconda, così come la quinta la colonna che domina le prime tre colonne. Di conseguenza, otteniamo la matrice

Aggiungendo a tutti gli elementi della matrice UN", ad esempio, il numero c = 3, otteniamo la matrice

.

tutti gli elementi dei quali sono non negativi e gli elementi della seconda riga sono strettamente positivi.

Creiamo una coppia di problemi duali simmetrici, in modo che il problema originale sia un problema di massimizzazione standard, la matrice dei coefficienti di questo problema coincide con la matrice dei payoff UN",· ed i coefficienti per le incognite nella funzione obiettivo ed i termini liberi delle disuguaglianze sarebbero pari ad uno.

Risolviamo il problema 1 utilizzando il metodo del simplesso. È dato sotto forma di compito generale. Riduciamolo a quello principale utilizzando ulteriori incognite X 4 ≥0, X 5 ≥0. Di conseguenza, otteniamo il seguente problema.

X J ≥ 0 (J = 1,…,5),

F(X) = x1 + x2 +x3 → sì.

Il problema è canonico e, applicando ad esso l'algoritmo del metodo del simplesso, otteniamo tabelle del simplesso della forma

Dalla colonna delle variabili di base e dalla riga dell'indice scriviamo i piani ottimali per una coppia di problemi duali, vale a dire:

f(X*)= g(Y*)=

Dalle soluzioni dei problemi duali si ottiene il prezzo del gioco e le strategie ottimali dei giocatori nel gioco con la matrice UN":

v"= = ;

=v" = = ;

= v" = =

Gioco di matrici UN" avranno le stesse strategie ottimali E , come nel gioco delle matrici UN", e il prezzo del gioco

v"= v"- c = - 3 = .

E infine, il gioco originale con matrice A ha strategie ottimali

P*= E Q*=

e il prezzo del gioco v= v"= .

Strategie ottimali R* E Q* abbiamo ottenuto dalle strategie ottimali E , aggiungendo zeri al posto delle righe e delle colonne cancellate.

Puoi verificare la correttezza della soluzione di gioco utilizzando il criterio di ottimalità della strategia. Per fare ciò, le componenti delle strategie ottimali trovate dovrebbero essere sostituite nelle disuguaglianze M(P i , Q*) ≤ v≤ M(P*, Q j) R* E Q*, componenti delle strategie pure R io (i = 1, 2, 3) e Q J (j = 1, 2, 3, 4, 5)

e il prezzo del gioco v = .

Si noti che il problema della teoria dei giochi dovrebbe essere ridotto a una coppia di problemi con doppio LP solo quando tutti gli elementi almeno una riga della matrice dei pagamenti strettamente positivo . In questo caso entrambi i problemi avranno piani ottimali, dai quali si potranno ricavare le strategie ottimali dei giocatori. Altrimenti, nel problema originale la funzione obiettivo potrebbe rivelarsi illimitata, e nel problema duale non ci sarà un unico piano. Quindi, nell'esempio seguente, se creiamo una coppia di problemi duali in un gioco con una matrice

,

quindi nel Problema 1 la funzione obiettivo non sarà limitata dall'alto all'insieme dei piani, e nel Problema 2 non ci saranno affatto piani, tuttavia, come abbiamo visto sopra, il gioco con la matrice UN" ha una soluzione.

La strategia mista ottimale del primo giocatore (player UN) ha la forma

,

strategia mista ottimale del secondo giocatore (player B) ha la forma:

.

Poiché questo gioco di matrici è stato semplificato eliminando strategie ovviamente non redditizie e la sua soluzione finale ha la forma:

Risolvere i giochi graficamente.

Il metodo grafico è applicabile ai giochi in cui almeno un giocatore ha solo due strategie.

Esempio 1.

Il gioco non ha punti di sella. La soluzione ottimale dovrebbe essere ricercata nel campo delle strategie miste. Costruiamo segmenti sul piano corrispondenti alle strategie del secondo giocatore.

Il limite inferiore della vincita per il giocatore A è la linea tratteggiata IN 3 HF 4 ,. Strategie IN 3 , E IN 4 sono le strategie attive del giocatore B. Il punto della loro intersezione A determina le strategie ottimali dei giocatori e il prezzo del gioco. Non è vantaggioso per il secondo giocatore utilizzare strategie IN 1 E IN 2 , A 1 = sì 2 = 0. La soluzione del gioco si riduce alla soluzione del gioco con matrice (2x2).

X 1 = 2/5, X 2 = 3/5; sì 3 = 3/5, A 4 = 2/5; v = 11/5.

Risposta.

X (2/5, 3/5) e Y (0, 0,3/5, 2/5), il prezzo del gioco è v = 11/5.

se il primo giocatore con probabilità 2/5 utilizzerà la prima strategia e con probabilità 3/5 la seconda, allora con sufficiente grandi quantità nei giochi con questa matrice, le sue vincite in media saranno almeno 11/5;

se il secondo giocatore utilizza la terza strategia con una probabilità di 3/5, il quarto con una probabilità di 2/5 e non utilizza la prima e la seconda strategia, allora con un numero sufficientemente grande di giochi con una determinata matrice la sua perdita su la media non sarà superiore a 11/5.

Esempio 2. Trovare la soluzione del gioco data dalla matrice

Il gioco non ha punti di sella. La soluzione ottimale dovrebbe essere ricercata nel campo delle strategie miste. Costruiamo segmenti sul piano corrispondenti alle strategie del primo giocatore.

Il limite superiore di perdita per il giocatore B è la linea tratteggiata UN 1 circa 4 . Strategie UN 1 E UN 2 sono le strategie attive del giocatore A. Il punto della loro intersezione A determina le strategie ottimali dei giocatori e il prezzo del gioco. Non è redditizio per il primo giocatore applicare strategie UN 3 E UN 4 , pertanto, la probabilità del loro utilizzo è zero, vale a dire X 2 =x 3 = 0. La soluzione del gioco si riduce alla soluzione del gioco con la matrice (2x2)

Utilizzando le formule (1)–(3) troviamo le strategie ottimali e il prezzo del gioco:

X 1 = 7/8, X 4 = 1/8; A 1 = 3/8, A 2 = 5/8; v = 27/8.

Risposta. Strategie ottimali per giocatori misti

X (7/8, 0, 0, 1/8) e Y (3/8, 5/8), il prezzo del gioco è v = 27/8.

Questa risposta significa quanto segue:

se il primo giocatore con una probabilità di 7/8 utilizza la prima strategia, con una probabilità di 1/8 la quarta e non utilizza la seconda e la terza strategia, allora con un numero sufficientemente elevato di giochi con una determinata matrice le sue vincite su la media sarà almeno 27/8;

se il secondo giocatore utilizza la prima strategia con una probabilità di 3/8 e la seconda con una probabilità di 5/8, allora con un numero sufficientemente elevato di giochi con questa matrice la sua perdita media non sarà superiore a 27/8.

L’uso della tecnologia informatica nello studio dell’argomento: “Giochi antagonisti”.

Per risolvere graficamente un gioco a matrici, vengono utilizzati Microsoft Word e Microsoft Excel, mentre per risolvere un gioco a matrici utilizzando metodi di programmazione lineare, viene utilizzata l'opzione "Cerca una soluzione" di Microsoft Excel. È anche possibile utilizzare per i calcoli il programma MATLAB, che è un linguaggio informatico tecnico di alto livello e un ambiente interattivo per lo sviluppo di algoritmi, la visualizzazione e l'analisi dei dati e i calcoli numerici.

Opzioni per compiti per lavoro indipendente.

Trova le strategie e il prezzo ottimali del gioco dati dalla matrice di pagamento UN.

Piano.

6.1. Relazione tra giochi di matrici e programmazione lineare.

6.2. Algoritmo per la risoluzione di giochi di matrici utilizzando la programmazione lineare.

Relazione tra giochi di matrici e programmazione lineare

La teoria dei giochi è strettamente correlata alla programmazione lineare, poiché ogni gioco finito per due persone a somma zero può essere rappresentato come un problema di programmazione lineare. G. Dantzig sottolinea che il creatore della teoria dei giochi, J. Von Neumann, che per primo introdusse il metodo del simplesso nella programmazione lineare (1947), stabilì questa relazione e ulteriormente sostanziato e sviluppato il concetto di dualità nella programmazione lineare.

Supponiamo che ci venga assegnato un gioco a due, specificato dalla matrice dei payoff. Quindi la strategia mista ottimale del primo giocatore è determinata dalle condizioni

, . (6.1)

Questo problema può essere formulato come un problema di programmazione lineare. Permettere

Quindi è possibile compilare un modello matematico del problema per il primo giocatore. Basandosi sulle strategie pure del secondo giocatore, la funzione obiettivo del gioco è:

(6.2)

sotto restrizioni

Per il secondo giocatore il problema è scritto come

, .

Rapporto intermedio:

Allora il problema prenderà forma

(6.3)

sotto restrizioni

.

Il problema per il secondo giocatore (6.3) è doppio rispetto a quello per il primo giocatore (6.2). Il problema per il secondo giocatore può essere risolto, ad esempio, utilizzando il metodo simplex standard e per il primo giocatore utilizzando il metodo dual simplex. La scelta del metodo è determinata da quale problema ha meno restrizioni, che a sua volta dipende dal numero di strategie pure di ciascun giocatore.

Il modello matematico del problema (6.2) può essere semplificato dividendo tutti ( N+ 1) restrizioni su v. Questo è possibile con v N. 0. Quando v= 0, si consiglia di aggiungere un qualsiasi numero positivo a tutti gli elementi della matrice dei payoff, che garantisce il valore positivo del gioco modificato. Il valore effettivo del gioco si ottiene sottraendo questo numero positivo dal valore modificato. Se v < 0, то надо сменить знаки неравенств.

Credere v> 0, il sistema di restrizioni può essere scritto:

Credere X i = x io / v e se v® max, quindi 1/ v® min, otteniamo un problema di programmazione lineare della forma

sotto restrizioni

.

Allo stesso modo, in base alle strategie pure del primo giocatore o secondo le regole per comporre problemi duali, prendendo come iniziale il modello matematico del primo giocatore, il modello matematico del secondo giocatore si scrive nella forma

sotto restrizioni

,

Dove S(Y)massimo = l(X)min = 1/v, Sì = sì j/N.

Gli esempi sopra riportati di risoluzione di un gioco con strategie miste illustrano chiaramente i principi teorici dei giochi a matrici e la complessità del calcolo manuale anche con una matrice 2x2. Per automatizzare i calcoli, è possibile utilizzare prodotti software il cui metodo di calcolo si basa sulla risoluzione di un sistema di equazioni lineari http://www.uchimatchast.ru/.

Qualsiasi gioco finito per due persone a somma zero può essere rappresentato come un problema di programmazione lineare. In questo caso è possibile risolvere il problema sia con strategie pure che miste. Nel caso delle strategie pure, la probabilità di una delle strategie sarà pari a uno e la probabilità delle restanti strategie, naturalmente, sarà pari a zero.

Le probabilità ottimali delle strategie del giocatore A possono essere determinate risolvendo il seguente problema di massimismo.

Formuliamo il problema di un gioco di matrici. Due aziende concorrenti A e B producono prodotti. Per aumentare le vendite, il prodotto viene fornito in varie confezioni. L'azienda A utilizza cartone A 1, cellophane A 2, plastica A 3. L'azienda B utilizza gli stessi materiali di imballaggio. Tuttavia, le aziende hanno utilizzato diversi tipi design della confezione. L'azienda A ha registrato un aumento/diminuzione dell'afflusso di clienti a seconda della confezione del prodotto e della strategia di comportamento del concorrente B. Queste statistiche sono presentate nella tabella.

La soluzione del problema si basa sull'ottenimento del miglior risultato dal peggiore per ciascun giocatore, ottenibile mediante una determinata strategia comportamentale. Dalla tabella presentata consegue che questo problema non può essere risolto sulla base di pure strategie (non esiste un punto di sella). La soluzione del problema è compresa tra -2 e 2. In questo caso ci sono strategie miste e poiché il numero di strategie per il giocatore A è tre, questo problema può essere risolto utilizzando la programmazione lineare (LP) utilizzando il metodo algebrico. Va notato che questo problema non può essere risolto graficamente, poiché il numero di strategie per ciascun giocatore è superiore a due.

In accordo con i dati presentati nella tabella, il problema LP per il giocatore A è scritto come segue

massimizzare:
(numero massimo di clienti) soggetto alle seguenti restrizioni:

5.3.3.1 Risoluzione del problema LP utilizzando il metodo del simplesso

Portiamo il sistema dei vincoli a forma canonica; per questo è necessario trasformare le disuguaglianze in uguaglianze, con l'aggiunta di variabili aggiuntive. Se la disuguaglianza trasformata contiene un segno ≥, allora al passaggio all'uguaglianza i segni di tutti i suoi coefficienti e termini liberi cambiano al contrario. Quindi il sistema verrà scritto come:

Procediamo alla formazione della tabella simplex iniziale. I coefficienti della funzione obiettivo vengono inseriti nella riga F della tabella. Poiché dobbiamo trovare il massimo della funzione obiettivo, nella tabella vengono inseriti i coefficienti con il segno opposto

Dai dati dell'attività creiamo la tabella simplex iniziale.

Poiché nella colonna dei termini liberi non sono presenti elementi negativi, è stata trovata una soluzione fattibile. La linea M contiene elementi negativi, il che significa che la soluzione risultante non è ottimale. Definiamo la colonna principale. Per fare ciò, troveremo nella riga M l'elemento negativo con il valore assoluto massimo: questo è -1. La riga iniziale sarà quella per cui il rapporto tra il termine libero e l'elemento corrispondente della colonna iniziale è minimo . La linea iniziale è R 1 e l'elemento iniziale è 1.

Nella tabella che abbiamo compilato ci sono elementi negativi nella colonna dei termini liberi, tra questi troviamo il massimo in modulo - questo è l'elemento: -3, imposta la riga iniziale - X 11. In questa riga troviamo anche l'elemento negativo massimo in modulo: -5 si trova nella colonna X 5, che sarà la colonna principale. La variabile nella riga iniziale è esclusa dalla base e la variabile corrispondente alla colonna iniziale è inclusa nella base. Ricalcoliamo la tabella del simplesso:

Nella tabella che abbiamo compilato ci sono elementi negativi nella colonna dei termini liberi, tra questi troviamo il massimo in modulo - questo è l'elemento: -4,4, imposta la riga iniziale - X 10. In questa riga troviamo anche l'elemento negativo massimo in modulo: -7.6 si trova nella colonna X 4, che sarà la colonna principale. La variabile nella riga iniziale è esclusa dalla base e la variabile corrispondente alla colonna iniziale è inclusa nella base. Ricalcoliamo la tabella del simplesso:

Nella tabella che abbiamo compilato ci sono elementi negativi nella colonna dei termini liberi, tra questi troviamo il massimo in modulo - questo è l'elemento: -2.11, imposta la riga iniziale - X 9. In questa riga troviamo anche l'elemento negativo massimo in modulo: - 2.82 si trova nella colonna X 2, che sarà la colonna principale. La variabile nella riga iniziale è esclusa dalla base e la variabile corrispondente alla colonna iniziale è inclusa nella base. Ricalcoliamo la tabella del simplesso:

Non essendo presenti elementi negativi nella riga F, è stata trovata la soluzione ottimale F = -0,75 con valori variabili uguali: X 2 = 0,75, X 4 = 0,4, X 5 = 0,29, X 3 = 0, 3.

In accordo con i dati presentati nella tabella, il problema LP per il giocatore B è scritto come segue:

massimizzare:
(numero minimo di clienti) soggetto alle seguenti restrizioni:

Portiamo il sistema dei vincoli a forma canonica; per questo è necessario trasformare le disuguaglianze in uguaglianze, con l'aggiunta di variabili aggiuntive.

Se la disuguaglianza trasformata contiene un segno ≥, allora al passaggio all'uguaglianza i segni di tutti i suoi coefficienti e termini liberi cambiano al contrario.

Quindi il sistema verrà scritto come:

Procediamo alla formazione della tabella simplex iniziale. I coefficienti della funzione obiettivo vengono inseriti nella riga F della tabella.

Poiché c'erano uguaglianze nell'insieme originale di condizioni, abbiamo introdotto le variabili artificiali R. Ciò significa che dobbiamo aggiungere un'ulteriore riga M alla tabella del simplesso, i cui elementi sono calcolati come la somma degli elementi corrispondenti delle condizioni di uguaglianza (quelle che, dopo essere state ridotte alla forma canonica, contengono variabili artificiali R) prese con il segno opposto.

Dai dati dell'attività creiamo la tabella simplex iniziale.

Poiché nella colonna dei termini liberi non sono presenti elementi negativi, è stata trovata una soluzione fattibile. La linea M contiene elementi negativi, il che significa che la soluzione risultante non è ottimale. Definiamo la colonna principale. Per fare ciò, troviamo nella riga M l'elemento negativo massimo in valore assoluto: questo è -1. La riga iniziale sarà quella per cui il rapporto tra il termine libero e l'elemento corrispondente della colonna iniziale è minimo. La linea iniziale è R 1 e l'elemento iniziale è 1.

Nella tabella che abbiamo compilato ci sono elementi negativi nella colonna dei termini liberi, tra questi troviamo il massimo in modulo - questo è l'elemento: -3, imposta la riga iniziale - X 9. In questa riga troviamo anche l'elemento negativo massimo in modulo: -6 si trova nella colonna X 5, che sarà la colonna principale. La variabile nella riga iniziale è esclusa dalla base e la variabile corrispondente alla colonna iniziale è inclusa nella base. Ricalcoliamo la tabella del simplesso:

Non ci sono elementi negativi nella stringa M. Consideriamo la linea F in cui sono presenti elementi negativi, ciò significa che la soluzione risultante non è ottimale. Definiamo la colonna principale. Per fare ciò, troviamo nella riga F il massimo elemento negativo in valore assoluto: questo è -1. La riga iniziale sarà quella per cui il rapporto positivo tra il termine libero e l'elemento corrispondente della colonna iniziale è minimo. La linea principale è X 11 e l'elemento principale è: 1,83.

Non ci sono elementi negativi nella stringa M. Consideriamo la linea F in cui sono presenti elementi negativi, ciò significa che la soluzione risultante non è ottimale. Definiamo la colonna principale. Per fare ciò, troviamo nella riga F il massimo elemento negativo in valore assoluto: questo è -3,92. La riga iniziale sarà quella per cui il rapporto positivo tra il termine libero e l'elemento corrispondente della colonna iniziale è minimo. La linea iniziale è X 10 e l'elemento iniziale è: 9,75.

Poiché nella stringa F non sono presenti elementi negativi, è stata trovata la soluzione ottima. Poiché il problema originario era trovare il minimo, la soluzione ottima è il termine libero della stringa F, preso con il segno opposto. La soluzione ottimale è stata trovata F=-0,75 a parità di valori delle variabili: X 5 =0,53, X 4 =0,12, X 2 =0,75, X 3 =0,35.

I calcoli hanno mostrato. Il valore del gioco, sia dal lato del giocatore A che dal lato del giocatore B, è lo stesso ed è pari a -0,75.

Un gioco a somma zero in cui ogni giocatore ha a disposizione un insieme finito di strategie. Le regole del gioco a matrice sono determinate dalla matrice dei pagamenti, i cui elementi sono le vincite del primo giocatore, che sono anche le perdite del secondo giocatore.

Gioco di matrici è un gioco antagonista. Il primo giocatore riceve la vincita massima garantita (indipendentemente dal comportamento del secondo giocatore), pari al prezzo del gioco, allo stesso modo il secondo giocatore ottiene la perdita minima garantita;

Sotto strategia è inteso come un insieme di regole (principi) che determinano la scelta dell'azione per ogni mossa personale del giocatore, a seconda della situazione attuale.

Ora tutto in ordine e in dettaglio.

Matrice dei pagamenti, strategie pure, prezzo del gioco

IN gioco di matrici le sue regole sono determinate matrice dei pagamenti .

Considera un gioco in cui ci sono due partecipanti: il primo giocatore e il secondo giocatore. Lascia che il primo giocatore abbia a sua disposizione M strategie pure, e a disposizione del secondo giocatore - N strategie pure. Poiché il gioco viene considerato, è naturale che in questo gioco ci siano vittorie e perdite.

IN matrice dei pagamenti gli elementi sono numeri che esprimono le vittorie e le sconfitte dei giocatori. Le vincite e le perdite possono essere espresse in punti, quantità di denaro o altre unità.

Creiamo una matrice di pagamento:

Se il primo giocatore sceglie io-esima strategia pura, e il secondo giocatore - J l'esima strategia pura, allora sarà il profitto del primo giocatore UNij unità, e lo è anche la perdita del secondo giocatore UNij unità.

Perché UNij + (- UN ij) = 0, allora il gioco descritto è un gioco con matrici a somma zero.

L'esempio più semplice di gioco a matrice è il lancio della moneta. Le regole del gioco sono le seguenti. Il primo e il secondo giocatore lanciano una moneta e il risultato è testa o croce. Se "testa" e "testa" o "croce" o "croce" vengono lanciati contemporaneamente, il primo giocatore vincerà un'unità e negli altri casi perderà un'unità (il secondo giocatore vincerà un'unità) . Le stesse due strategie sono a disposizione del secondo giocatore. La matrice di pagamento corrispondente sarà la seguente:

Il compito della teoria dei giochi è determinare la scelta della strategia del primo giocatore, che gli garantirebbe la massima vincita media, così come la scelta della strategia del secondo giocatore, che gli garantirebbe la massima perdita media.

Come si sceglie una strategia in un gioco a matrice?

Consideriamo nuovamente la matrice dei pagamenti:

Innanzitutto, determiniamo l'importo delle vincite per il primo giocatore, se lo utilizza io la strategia pura. Se il primo giocatore usa io la strategia pura, allora è logico supporre che il secondo giocatore utilizzerà una strategia pura per cui il profitto del primo giocatore sarebbe minimo. A sua volta, il primo giocatore utilizzerà una strategia così pura che gli fornirebbe la massima vincita. Sulla base di queste condizioni, le vincite del primo giocatore, che chiameremo v1 , chiamato vincite massime O prezzo più basso del gioco .

A per questi valori il primo giocatore dovrà procedere come segue. Da ciascuna riga, annota il valore dell'elemento minimo e seleziona quello massimo da essi. Pertanto, la vincita del primo giocatore sarà il massimo del minimo. Da qui il nome: maximin vincente. Il numero di riga di questo elemento sarà il numero della strategia pura scelta dal primo giocatore.

Ora determiniamo l'importo della perdita per il secondo giocatore se utilizza J esima strategia. In questo caso, il primo giocatore utilizza la propria strategia pura in cui la perdita del secondo giocatore sarebbe massima. Il secondo giocatore deve scegliere una strategia pura in cui la sua perdita sarebbe minima. La perdita del secondo giocatore, che chiameremo v2 , chiamato perdita minima O prezzo più alto del gioco .

A risolvere problemi sul costo del gioco e determinare la strategia Per determinare questi valori per il secondo giocatore, procedere come segue. Da ciascuna colonna, annota il valore dell'elemento massimo e seleziona il minimo da essi. Pertanto, la perdita del secondo giocatore sarà il minimo del massimo. Da qui il nome: vittoria minimax. Il numero di colonna di questo elemento sarà il numero della strategia pura scelta dal secondo giocatore. Se il secondo giocatore utilizza "minimax", indipendentemente dalla scelta della strategia da parte del primo giocatore, non perderà più di v2 unità.

Esempio 1.

.

Il più grande degli elementi più piccoli delle righe è 2, questo è il prezzo più basso del gioco, la prima riga corrisponde ad esso, quindi la strategia massimizzata del primo giocatore è la prima. Il più piccolo degli elementi più grandi delle colonne è 5, questo è il prezzo massimo del gioco, la seconda colonna corrisponde ad esso, quindi la strategia minimax del secondo giocatore è la seconda.

Ora che abbiamo imparato a trovare il prezzo inferiore e superiore del gioco, le strategie maximin e minimax, è tempo di imparare a definire formalmente questi concetti.

Quindi, la vincita garantita per il primo giocatore è:

Il primo giocatore deve scegliere una strategia pura che gli fornisca il massimo della vincita minima. Questo guadagno (massimo) è indicato come segue:

.

Il primo giocatore usa la sua strategia pura in modo che la perdita del secondo giocatore sia massima. Tale perdita viene indicata come segue:

Il secondo giocatore deve scegliere la sua strategia pura in modo che la sua perdita sia minima. Questa perdita (minimax) è indicata come segue:

.

Un altro esempio della stessa serie.

Esempio 2. Dato un gioco a matrici con una matrice dei payoff

.

Determina la strategia massima del primo giocatore, la strategia minima del secondo giocatore, il prezzo inferiore e superiore del gioco.

Soluzione. A destra della matrice di pagamento scriviamo gli elementi più piccoli nelle sue righe e ne segniamo il massimo, e sotto la matrice - elementi più grandi nelle colonne e seleziona la più piccola:

Il più grande degli elementi più piccoli delle linee è 3, questo è il prezzo più basso del gioco, la seconda linea corrisponde ad esso, quindi la strategia massimizzata del primo giocatore è il secondo. Il più piccolo degli elementi più grandi delle colonne è 5, questo è il prezzo massimo del gioco, la prima colonna corrisponde ad esso, quindi la strategia minimax del secondo giocatore è la prima.

Punto di sella nei giochi a matrice

Se i prezzi superiore e inferiore del gioco sono gli stessi, si considera che il gioco a matrice abbia un punto di sella. È vero anche il contrario: se un gioco a matrice ha un punto di sella, allora i prezzi superiore e inferiore del gioco a matrice sono gli stessi. L'elemento corrispondente è sia il più piccolo della riga che il più grande della colonna ed è pari al prezzo del gioco.

Pertanto, se , allora è la strategia pura ottima del primo giocatore, ed è la strategia pura ottima del secondo giocatore. Cioè, i prezzi di gioco inferiori e superiori uguali vengono raggiunti utilizzando la stessa coppia di strategie.

In questo caso Il gioco a matrice ha una soluzione in strategie pure .

Esempio 3. Dato un gioco a matrici con una matrice dei payoff

.

Soluzione. A destra della matrice di pagamento, scriveremo gli elementi più piccoli nelle sue righe e ne annoteremo il massimo, e sotto la matrice - gli elementi più grandi nelle colonne e ne selezioneremo il minimo:

Il prezzo più basso del gioco coincide con il prezzo più alto del gioco. Pertanto, il prezzo del gioco è 5. Cioè . Il costo del gioco è pari al valore del punto sella. La strategia maxin del primo giocatore è la seconda strategia pura, e la strategia minimax del secondo giocatore è la terza strategia pura. Questo gioco a matrice ha una soluzione in strategie pure.

Risolvi tu stesso un problema di gioco a matrici e poi guarda la soluzione

Esempio 4. Dato un gioco a matrici con una matrice dei payoff

.

Trova il prezzo inferiore e superiore del gioco. Questo gioco a matrice ha un punto di sella?

Giochi a matrice con strategia mista ottimale

Nella maggior parte dei casi, un gioco a matrice non ha un punto di sella, quindi il corrispondente gioco a matrice non ha soluzioni in strategie pure.

Ma ha una soluzione in strategie miste ottimali. Per trovarli è necessario presupporre che il gioco venga ripetuto un numero sufficiente di volte in modo che, in base all'esperienza, si possa indovinare quale strategia è preferibile. Pertanto, la decisione è associata al concetto di probabilità e media (aspettativa matematica). Nella soluzione finale c'è sia un analogo del punto di sella (cioè l'uguaglianza dei prezzi inferiore e superiore del gioco), sia un analogo delle strategie ad essi corrispondenti.

Quindi, affinché il primo giocatore riceva la vincita media massima e il secondo giocatore abbia una perdita media minima, strategie pure dovrebbe essere usato con una certa probabilità.

Se il primo giocatore utilizza strategie pure con probabilità , quindi il vettore è chiamata strategia mista del primo giocatore. In altre parole, si tratta di una “miscela” di pure strategie. In questo caso, la somma di queste probabilità è uguale a uno:

.

Se il secondo giocatore utilizza strategie pure con probabilità , quindi il vettore è chiamata strategia mista del secondo giocatore. In questo caso, la somma di queste probabilità è uguale a uno:

.

Se il primo giocatore utilizza una strategia mista P e il secondo giocatore: una strategia mista Q, allora ha senso valore atteso la vittoria del primo giocatore (la sconfitta del secondo giocatore). Per trovarlo, devi moltiplicare il vettore di strategia mista del primo giocatore (che sarà una matrice ad una riga), la matrice dei payoff e il vettore di strategia mista del secondo giocatore (che sarà una matrice ad una colonna):

.

Esempio 5. Dato un gioco a matrici con una matrice dei payoff

.

Determina l'aspettativa matematica della vittoria del primo giocatore (la perdita del secondo giocatore), se la strategia mista del primo giocatore è , e la strategia mista del secondo giocatore è .

Soluzione. Secondo la formula per l’aspettativa matematica della vincita del primo giocatore (perdita del secondo giocatore), questa è uguale al prodotto del vettore della strategia mista del primo giocatore, della matrice dei pagamenti e del vettore della strategia mista del secondo giocatore:

Per il primo giocatore viene definita una strategia mista tale da fornirgli il massimo profitto medio se il gioco viene ripetuto un numero sufficiente di volte.

Strategia mista ottimale per il secondo giocatore viene definita una strategia mista tale da garantirgli una perdita media minima se il gioco viene ripetuto un numero sufficiente di volte.

Per analogia con la notazione di maximin e minimax nel caso delle strategie pure, le strategie miste ottimali sono denotate come segue (e sono legate all'aspettativa matematica, cioè alla media, della vittoria del primo giocatore e della perdita del secondo):

,

.

In questo caso, per la funzione E c'è un punto di sella , che significa uguaglianza.

Per trovare strategie miste ottimali e un punto di sella, ovvero risolvere un gioco a matrici in strategie miste , è necessario ridurre il gioco delle matrici a un problema di programmazione lineare, cioè a un problema di ottimizzazione, e risolvere il corrispondente problema di programmazione lineare.

Ridurre un gioco di matrici ad un problema di programmazione lineare

Per risolvere un gioco a matrici in strategie miste, è necessario costruire una linea retta problema di programmazione lineare E duplice compito. Nel problema duale viene trasposta la matrice estesa, che memorizza i coefficienti delle variabili nel sistema di vincoli, i termini liberi e i coefficienti delle variabili nella funzione obiettivo. In questo caso, il minimo della funzione obiettivo del problema originale coincide con il massimo del problema duale.

Funzione obiettivo in un problema di programmazione lineare diretta:

.

Sistema di vincoli in un problema di programmazione lineare diretta:

La funzione obiettivo nel problema duale è:

.

Sistema di restrizioni nel problema duale:

Il piano ottimo per un problema di programmazione lineare diretta è indicato con

,

e il piano ottimo per il problema duale è indicato con

Indichiamo le forme lineari per i corrispondenti piani ottimali con e ,

e devono essere trovati come somme delle corrispondenti coordinate dei piani ottimi.

In conformità con le definizioni del paragrafo precedente e le coordinate dei piani ottimali, sono valide le seguenti strategie miste del primo e del secondo giocatore:

.

I matematici teorici lo hanno dimostrato prezzo del gioco si esprime nel modo seguente attraverso le forme lineari dei piani ottimi:

,

cioè è il reciproco delle somme delle coordinate dei piani ottimi.

Noi professionisti possiamo utilizzare questa formula solo per risolvere giochi a matrici in strategie miste. Come formule per trovare strategie miste ottimali rispettivamente il primo e il secondo giocatore:

in cui i secondi fattori sono vettori. Anche le strategie miste ottimali sono, come abbiamo già definito nel paragrafo precedente, vettori. Pertanto moltiplicando il numero (prezzo del gioco) per un vettore (con le coordinate dei piani ottimali) otteniamo anche un vettore.

Esempio 6. Dato un gioco a matrici con una matrice dei payoff

.

Scopri il prezzo del gioco V e strategie miste ottimali e .

Soluzione. Creiamo un problema di programmazione lineare corrispondente a questo gioco di matrici:

Otteniamo una soluzione al problema diretto:

.

Troviamo la forma lineare dei piani ottimali come somma delle coordinate trovate.