Teoria del gioco come branca della ricerca operativa, è la teoria dei modelli matematici per prendere decisioni ottimali in condizioni di incertezza o conflitto di più parti con interessi diversi. La teoria dei giochi studia le strategie ottimali nelle situazioni di gioco. Questi includono situazioni relative alla selezione delle soluzioni di produzione più vantaggiose per un sistema di esperimenti scientifici ed economici, all'organizzazione del controllo statistico e alle relazioni economiche tra imprese industriali e altri settori. Formalizzando matematicamente le situazioni di conflitto, queste possono essere rappresentate come un gioco a due, a tre, ecc. giocatori, ognuno dei quali persegue l'obiettivo di massimizzare il proprio vantaggio, le proprie vincite a scapito dell'altro.

La sezione "Teoria dei giochi" è rappresentata da tre calcolatori on-line:

1. Strategie ottimali dei giocatori. In tali problemi viene specificata una matrice di pagamento. È necessario trovare strategie pure o miste dei giocatori e, prezzo del gioco. Per risolvere è necessario specificare la dimensione della matrice e il metodo di soluzione. Il servizio implementa i seguenti metodi per risolvere una partita a due giocatori:
   1. Minimassimo. Se hai bisogno di trovare la strategia pura dei giocatori o rispondere a una domanda sul punto di sella di un gioco, scegli questo metodo di soluzione.
   2. Metodo del semplice. Utilizzato per risolvere giochi di strategia mista utilizzando metodi di programmazione lineare.
   3. Metodo grafico. Utilizzato per risolvere giochi di strategia mista. Se c’è un punto di sella, la soluzione si ferma. Esempio: data una matrice dei payoff, trova le strategie miste ottimali dei giocatori e il prezzo del gioco utilizzando il metodo grafico per risolvere il gioco.
   4. Metodo iterativo di Brown-Robinson. Il metodo iterativo viene utilizzato quando il metodo grafico non è applicabile e quando quello algebrico e metodi matriciali. Questo metodo fornisce un valore approssimativo del prezzo del gioco e il valore reale può essere ottenuto con qualsiasi grado di precisione desiderato. Questo metodo non è sufficiente per trovare strategie ottimali, ma permette di tracciarne le dinamiche gioco a turni e determinare il prezzo del gioco per ciascuno dei giocatori ad ogni passaggio.
   Ad esempio, il compito potrebbe sembrare “indicare le strategie ottimali dei giocatori per il gioco date dalla matrice dei payoff”.
   Tutti i metodi utilizzano un controllo per righe e colonne dominanti.
2. Gioco bimatrice. Di solito in un gioco del genere vengono specificate due matrici della stessa dimensione di vincite del primo e del secondo giocatore. Le righe di queste matrici corrispondono alle strategie del primo giocatore e le colonne delle matrici corrispondono alle strategie del secondo giocatore. In questo caso, la prima matrice rappresenta le vincite del primo giocatore, e la seconda matrice rappresenta le vincite del secondo.
3. Giochi con la natura. Viene utilizzato quando è necessario selezionare una decisione gestionale secondo i criteri di Maximax, Bayes, Laplace, Wald, Savage, Hurwitz.
   Per il criterio di Bayes sarà necessario inserire anche le probabilità di accadimento degli eventi. Se non vengono specificati lasciare i valori predefiniti (ci saranno eventi equivalenti).
   Per il criterio di Hurwitz, indicare il livello di ottimismo λ. Se questo parametro non è specificato nelle condizioni, è possibile utilizzare i valori 0, 0,5 e 1.

Molti problemi richiedono la ricerca di soluzioni utilizzando i computer. I servizi e le funzioni di cui sopra sono uno degli strumenti.

Teoria del gioco - una serie di metodi matematici per risolvere situazioni di conflitto (conflitti di interessi). Nella teoria dei giochi, viene chiamato un gioco modello matematico situazione di conflitto. Oggetto di particolare interesse nella teoria dei giochi è lo studio delle strategie decisionali dei partecipanti al gioco in condizioni di incertezza. L'incertezza deriva dal fatto che due o più parti perseguono obiettivi opposti e i risultati di qualsiasi azione di ciascuna parte dipendono dalle mosse del partner. Allo stesso tempo, ciascuna parte si sforza di prendere decisioni ottimali che realizzino al massimo gli obiettivi prefissati.

La teoria dei giochi viene applicata in modo più coerente in economia, dove sorgono situazioni di conflitto, ad esempio, nel rapporto tra fornitore e consumatore, acquirente e venditore, banca e cliente. L'applicazione della teoria dei giochi può essere trovata anche in politica, sociologia, biologia e arte militare.

Dalla storia della teoria dei giochi

Storia della teoria dei giochi come disciplina indipendente iniziò nel 1944, quando John von Neumann e Oscar Morgenstern pubblicarono il libro “La teoria dei giochi e il comportamento economico”. Sebbene esempi di teoria dei giochi siano già stati incontrati in precedenza: il trattato del Talmud babilonese sulla divisione della proprietà di un marito defunto tra le sue mogli, i giochi di carte nel XVIII secolo, lo sviluppo della teoria degli scacchi all'inizio del XX secolo, la dimostrazione del teorema minimax dello stesso John von Neumann nel 1928, senza il quale non esisterebbe la teoria dei giochi.

Negli anni '50 del XX secolo, Melvin Drescher e Meryl Flood di Rand Corporation John Nash, il primo ad applicare sperimentalmente il dilemma del prigioniero, sviluppò il concetto di equilibrio di Nash nei suoi lavori sullo stato di equilibrio nei giochi a due.

Reinhard Salten pubblicò nel 1965 il libro "Il trattamento dell'oligopolio nella teoria dei giochi su richiesta" ("Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit"), con il quale l'applicazione della teoria dei giochi in economia ricevette un nuovo impulso. Un passo avanti nell’evoluzione della teoria dei giochi è associato al lavoro di John Maynard Smith, “Evolutionary Stable Strategy” (1974). Il dilemma del prigioniero è stato reso popolare nel libro di Robert Axelrod del 1984 The Evolution of Cooperazione. Nel 1994, John Nash, John Harsanyi e Reinhard Salten furono insigniti del Premio Nobel per i loro contributi alla teoria dei giochi.

La teoria dei giochi nella vita e negli affari

Soffermiamoci più in dettaglio sull'essenza di una situazione di conflitto (scontro di interessi) nel senso in cui è intesa nella teoria dei giochi per l'ulteriore modellazione di varie situazioni nella vita e negli affari. Lascia che un individuo sia in una posizione che porta a uno dei numerosi risultati possibili e che l'individuo abbia alcune preferenze personali riguardo a questi risultati. Ma sebbene possa in una certa misura controllare le variabili che determinano il risultato, non ha un potere completo su di esse. A volte il controllo è nelle mani di più individui che, come lui, hanno alcune preferenze in relazione ai possibili risultati, ma in generale gli interessi di questi individui non sono coerenti. In altri casi, l'esito finale può dipendere sia dal caso (che nelle scienze giuridiche viene talvolta chiamato disastri naturali) e da altri individui. La teoria dei giochi sistematizza le osservazioni di tali situazioni e la formulazione di principi generali per guidare azioni intelligenti in tali situazioni.

Per certi aspetti, il nome "teoria dei giochi" è infelice, poiché suggerisce che la teoria dei giochi si occupi solo di incontri socialmente insignificanti che accadono nei giochi di società, ma tuttavia la teoria ha un significato molto più ampio.

La seguente situazione economica può dare un’idea dell’applicazione della teoria dei giochi. Supponiamo che vi siano diversi imprenditori, ciascuno dei quali si sforza di ottenere il massimo profitto, pur avendo solo un potere limitato sulle variabili che determinano questo profitto. Un imprenditore non ha alcun potere sulle variabili che un altro imprenditore controlla, ma che possono influenzare notevolmente il reddito del primo. Trattare questa situazione come un gioco può sollevare la seguente obiezione. Il modello di gioco presuppone che ogni imprenditore faccia una scelta nell'area possibili elezioni e da queste singole scelte si determinano i profitti. Evidentemente ciò non può quasi accadere nella realtà, poiché in questo caso nell'industria non sarebbero necessari complessi apparati gestionali. Esistono semplicemente una serie di decisioni e modifiche di queste decisioni che dipendono dalle scelte fatte dagli altri partecipanti al sistema economico (giocatori). Ma in linea di principio si può immaginare che qualche amministratore anticipi tutte le possibili contingenze e dettaglii l’azione da intraprendere in ciascun caso, piuttosto che risolvere ogni problema man mano che si presenta.

Un conflitto militare, per definizione, è uno scontro di interessi in cui nessuna delle due parti ha il controllo completo sulle variabili che determinano l’esito, che viene deciso da una serie di battaglie. Puoi semplicemente considerare il risultato come una vittoria o una perdita e assegnargli i valori numerici 1 e 0.

Una delle situazioni di conflitto più semplici che possono essere scritte e risolte nella teoria dei giochi è un duello, che è un conflitto tra due giocatori 1 e 2, aventi rispettivamente P E Q colpi. Per ogni giocatore c'è una funzione che indica la probabilità che il giocatore abbia tirato io in un determinato momento T darà un colpo che sarà fatale.

Di conseguenza, la teoria dei giochi arriva alla seguente formulazione di una certa classe di conflitti di interessi: ci sono N giocatori, e ognuno deve scegliere un'opzione da un centinaio di set specifici e, quando fa una scelta, il giocatore non ha informazioni sulle scelte degli altri giocatori. L'area di possibile scelta del giocatore può contenere elementi come "giocare all'asso di picche", "produrre carri armati invece di automobili", o più in generale, una strategia che definisce tutte le azioni da intraprendere in tutte le circostanze possibili. Ogni giocatore si trova di fronte a un compito: quale scelta dovrebbe fare affinché la sua influenza privata sul risultato gli porti la massima vincita possibile?

Modello matematico nella teoria dei giochi e formalizzazione dei problemi

Come abbiamo già notato, il gioco è un modello matematico di una situazione di conflitto e richiede i seguenti componenti:

1. parti interessate;
2. possibili azioni da ciascuna parte;
3. interessi delle parti.

Le parti interessate al gioco sono chiamate giocatori , ognuno di essi può compiere almeno due azioni (se il giocatore ha a disposizione una sola azione, allora non partecipa effettivamente al gioco, poiché è noto in anticipo cosa farà). Il risultato del gioco si chiama vittoria .

Non sempre esiste una vera situazione di conflitto, ma il gioco (nel concetto di teoria dei giochi) procede sempre di conseguenza certe regole , che determinano precisamente:

1. opzioni per le azioni dei giocatori;
2. la quantità di informazioni che ciascun giocatore ha sul comportamento del proprio partner;
3. il profitto a cui porta ogni serie di azioni.

Esempi di giochi formalizzati includono il calcio, gioco di carte, scacchi.

Ma in economia, emerge un modello di comportamento dei giocatori, ad esempio, quando diverse aziende si sforzano di prendere una posizione più vantaggiosa nel mercato, diversi individui cercano di dividere tra loro una parte del bene (risorse, finanze) in modo che tutti ottengano il più possibile . I protagonisti delle situazioni di conflitto economico, che possono essere modellate come un gioco, sono aziende, banche, individui e altri agenti economici. A sua volta, in condizioni di guerra, il modello di gioco viene utilizzato, ad esempio, nella scelta dell'arma migliore (tra esistente o potenziale) per sconfiggere il nemico o proteggersi dagli attacchi.

Il gioco è caratterizzato dall’incertezza del risultato . I motivi di incertezza possono essere suddivisi nei seguenti gruppi:

1. combinatorio (come negli scacchi);
2. l'influenza di fattori casuali (come nel gioco "testa o croce", dadi, giochi di carte);
3. strategico (il giocatore non sa quale azione intraprenderà il nemico).

Strategia del giocatore è un insieme di regole che determinano le sue azioni ad ogni mossa a seconda della situazione attuale.

Lo scopo della teoria dei giochi è determinare la strategia ottimale per ciascun giocatore. Determinare una tale strategia significa risolvere il gioco. Ottimalità della strategia si ottiene quando uno dei giocatori ottiene la vincita massima, mentre il secondo si attiene alla sua strategia. E il secondo giocatore dovrebbe subire una perdita minima se il primo si attiene alla sua strategia.

Classificazione dei giochi

1. Classificazione per numero di giocatori (gioco di due o più persone). I giochi a due occupano un posto centrale in tutta la teoria dei giochi. Il concetto centrale della teoria dei giochi per i giochi a due persone è una generalizzazione dell’idea molto significativa di equilibrio che appare naturalmente nei giochi a due persone. Per quanto riguarda i giochi N individui, allora una parte della teoria dei giochi è dedicata ai giochi in cui è vietata la cooperazione tra i giocatori. In un'altra parte della teoria dei giochi N si presuppone che gli individui siano in grado di cooperare per il reciproco vantaggio (vedere più avanti in questo paragrafo sulla non-cooperativa e giochi cooperativi OH).
2. Classificazione in base al numero di giocatori e alle loro strategie (il numero di strategie è almeno due, potrebbe essere infinito).
3. Classificazione per quantità di informazioni relativo alle mosse passate: giochi con informazioni complete e informazioni incomplete. Lascia che ci sia il giocatore 1 - acquirente e il giocatore 2 - venditore. Se il giocatore 1 non dispone di informazioni complete sulle azioni del giocatore 2, allora il giocatore 1 potrebbe non distinguere tra le due alternative tra le quali deve fare una scelta. Ad esempio, scegliere tra due tipologie di un prodotto e non sapere quale, secondo alcune caratteristiche, sarà il prodotto UN prodotto peggiore B, il giocatore 1 potrebbe non vedere la differenza tra le alternative.
4. Classificazione secondo i principi della divisione delle vincite : cooperativa, coalizione da un lato e non cooperativa, non coalizione dall'altro. IN gioco non cooperativo , o altrimenti - gioco non cooperativo , i giocatori scelgono le strategie simultaneamente senza sapere quale strategia sceglierà il secondo giocatore. La comunicazione tra i giocatori è impossibile. IN gioco cooperativo , o altrimenti - gioco di coalizione , i giocatori possono formare coalizioni e intraprendere azioni collettive per aumentare le proprie vincite.
5. Gioco finito per due persone a somma zero o lo è un gioco antagonista gioco di strategia con un’informativa completa, che coinvolga soggetti con interessi opposti. I giochi antagonisti lo sono giochi di matrici .

Un classico esempio della teoria dei giochi è il dilemma del prigioniero.

I due sospettati vengono presi in custodia e separati l'uno dall'altro. Il procuratore distrettuale è convinto che si siano impegnati crimine grave, ma non ha prove sufficienti per accusarli in tribunale. Dice a ciascun prigioniero che ha due alternative: confessare il crimine che la polizia ritiene abbia commesso o non confessare. Se entrambi non confessano, il procuratore distrettuale li accuserà di qualche reato minore, come piccoli furti o possesso illegale di armi, ed entrambi riceveranno una piccola condanna. Se entrambi confessano, saranno processati, ma lui non richiederà la pena più dura. Se uno confessa e l’altro no, a chi ha confessato verrà commutata la pena per l’estradizione di un complice, mentre a chi persiste verrà “il massimo”.

Se questo compito strategico è formulato in termini di conclusione, si riduce a quanto segue:

Pertanto, se entrambi i detenuti non confessano, riceveranno 1 anno ciascuno. Se entrambi confessano, ciascuno riceverà 8 anni. E se uno confessa e l'altro non confessa, chi ha confessato scapperà con tre mesi di prigione e chi non confessa riceverà 10 anni. La matrice sopra riportata riflette correttamente il dilemma del prigioniero: ognuno si trova di fronte alla questione se confessare o non confessare. Il gioco che il procuratore distrettuale propone ai detenuti è gioco non cooperativo o altrimenti - gioco non cooperativo . Se entrambi i detenuti avessero l’opportunità di cooperare (ad es. il gioco sarebbe cooperativo o altro gioco di coalizione ), allora entrambi non avrebbero confessato e sarebbero stati condannati a un anno di prigione ciascuno.

Esempi di utilizzo degli strumenti matematici della teoria dei giochi

Passiamo ora a considerare soluzioni ad esempi di classi comuni di giochi, per i quali esistono metodi di ricerca e soluzione nella teoria dei giochi.

Un esempio di formalizzazione di un gioco non cooperativo (non cooperativo) di due persone

Nel paragrafo precedente, abbiamo già visto un esempio di gioco non cooperativo (non cooperativo) (dilemma del prigioniero). Rafforziamo le nostre competenze. A questo scopo è adatta anche una trama classica ispirata a “Le avventure di Sherlock Holmes” di Arthur Conan Doyle. Si può, ovviamente, obiettare: l'esempio non è tratto dalla vita, ma dalla letteratura, ma Conan Doyle non si è affermato come scrittore di fantascienza! Classico anche perché il compito è stato portato a termine da Oskar Morgenstern, come abbiamo già stabilito, uno dei fondatori della teoria dei giochi.

Esempio 1. Verrà fornito un breve riassunto di un frammento di una delle "Avventure di Sherlock Holmes". Secondo i noti concetti della teoria dei giochi, crea un modello di una situazione di conflitto e scrivi formalmente il gioco.

Sherlock Holmes intende viaggiare da Londra a Dover con l'ulteriore obiettivo di raggiungere il continente (europeo) per sfuggire al professor Moriarty, che lo insegue. Salito sul treno, vide il professor Moriarty sulla banchina della stazione. Sherlock Holmes ammette che Moriarty può scegliere un treno speciale e sorpassarlo. Sherlock Holmes ha due alternative: proseguire il viaggio verso Dover oppure scendere alla stazione di Canterbury, che è l'unica stazione intermedia del suo percorso. Accettiamo che il suo avversario sia abbastanza intelligente da determinare le capacità di Holmes, quindi ha le stesse due alternative. Entrambi gli avversari devono scegliere una stazione in cui scendere dal treno, senza sapere quale decisione prenderà ciascuno. Se, come risultato della decisione, entrambi finiscono nella stessa stazione, allora possiamo sicuramente presumere che Sherlock Holmes verrà ucciso dal professor Moriarty. Se Sherlock Holmes raggiungerà Dover sano e salvo, sarà salvato.

Soluzione. Possiamo considerare gli eroi di Conan Doyle come partecipanti al gioco, cioè giocatori. Disponibile per ogni giocatore io (io=1,2) due strategie pure:

• scendere a Dover (strategia Si1 ( io=1,2) );
• scendere ad una stazione intermedia (strategia Si2 ( io=1,2) )

A seconda di quale delle due strategie sceglie ciascuno dei due giocatori, verrà creata una speciale combinazione di strategie in coppia S = (S1 , S 2 ) .

Ogni combinazione può essere associata a un evento: l'esito del tentato omicidio di Sherlock Holmes da parte del professor Moriarty. Creiamo una matrice di questo gioco con possibili eventi.

Sotto ciascuno degli eventi c'è un indice che indica l'acquisizione del professor Moriarty e calcolato in base alla salvezza di Holmes. Entrambi gli eroi scelgono una strategia contemporaneamente, non sapendo quale sceglierà il nemico. Pertanto, il gioco non è cooperativo perché, in primo luogo, i giocatori si trovano su treni diversi e, in secondo luogo, hanno interessi opposti.

Un esempio di formalizzazione e soluzione di un gioco cooperativo (di coalizione). N persone

A questo punto, la parte pratica, cioè il processo di risoluzione di un problema di esempio, sarà preceduta da una parte teorica, in cui conosceremo i concetti della teoria dei giochi per la risoluzione dei giochi cooperativi (non cooperativi). Per questo compito, la teoria dei giochi suggerisce:

• funzione caratteristica (per dirla semplicemente, riflette l'entità del vantaggio derivante dall'unione dei giocatori in una coalizione);
• il concetto di additività (la proprietà delle quantità, consistente nel fatto che il valore di una quantità corrispondente all'intero oggetto è uguale alla somma dei valori delle quantità corrispondenti alle sue parti in una determinata classe di partizioni dell'oggetto in parti) e superadditività (il valore di una quantità corrispondente all'intero oggetto è maggiore della somma dei valori delle quantità, corrispondenti alle sue parti) della funzione caratteristica.

La superadditività della funzione caratteristica suggerisce che aderire ad una coalizione è vantaggioso per i giocatori, poiché in questo caso il valore del payoff della coalizione aumenta con il numero di giocatori.

Per formalizzare il gioco, dobbiamo introdurre notazioni formali per i concetti di cui sopra.

Per il gioco N indichiamo l'insieme di tutti i suoi giocatori come N= (1,2,...,n) Qualsiasi sottoinsieme non vuoto dell'insieme N indichiamolo come T(compreso se stesso N e tutti i sottoinsiemi costituiti da un elemento). C'è una lezione sul sito " Insiemi e operazioni sugli insiemi", che si apre in una nuova finestra quando si fa clic sul collegamento.

La funzione caratteristica è indicata come v e il suo dominio di definizione è costituito da possibili sottoinsiemi dell'insieme N. v(T) - il valore della funzione caratteristica per un particolare sottoinsieme, ad esempio il reddito ricevuto da una coalizione, eventualmente inclusa quella composta da un giocatore. Questo è importante perché la teoria dei giochi richiede di verificare la presenza di superadditività per i valori della funzione caratteristica di tutte le coalizioni disgiunte.

Per due coalizioni di sottoinsiemi non vuoti T1 E T2 L'additività della funzione caratteristica di un gioco cooperativo (di coalizione) si scrive come segue:

E la superadditività è così:

Esempio 2. Tre studenti delle scuole di musica lavorano part-time in diversi club; ricevono il loro reddito dai visitatori del club. Determinare se è vantaggioso per loro unire le forze (se sì, a quali condizioni), utilizzando i concetti della teoria dei giochi per risolvere giochi cooperativi N persone, con i seguenti dati iniziali.

In media, le loro entrate per serata erano:

• il violinista ne ha 600 unità;
• il chitarrista ne ha 700;
• il cantante ha 900 unità.

Nel tentativo di aumentare le entrate, gli studenti hanno creato vari gruppi nel corso di diversi mesi. I risultati hanno mostrato che, collaborando, avrebbero potuto aumentare le entrate serali di:

• violinista+chitarrista hanno guadagnato 1500 unità;
• violinista + cantante hanno guadagnato 1800 unità;
• chitarrista + cantante hanno guadagnato 1900 unità;
• violinista+chitarrista+cantante hanno guadagnato 3000 unità.

Soluzione. In questo esempio, il numero di giocatori nel gioco N= 3, quindi, il dominio di definizione della funzione caratteristica del gioco è costituito da 2³ = 8 possibili sottoinsiemi dell'insieme di tutti i giocatori. Elenchiamo tutte le possibili coalizioni T:

• coalizioni di un elemento, ognuna delle quali è composta da un giocatore - un musicista: T{1} , T{2} , T{3} ;
• coalizione di due elementi: T{1,2} , T{1,3} , T{2,3} ;
• una coalizione di tre elementi: T{1,2,3} .

Assegneremo un numero di serie ad ogni giocatore:

• violinista - 1° suonatore;
• chitarrista - 2° musicista;
• cantante - 3° giocatore.

Sulla base dei dati del problema, determiniamo la funzione caratteristica del gioco v:

v(T(1)) = 600 ; v(T(2)) = 700 ; v(T(3)) = 900 ; questi valori della funzione caratteristica sono determinati in base ai profitti rispettivamente del primo, secondo e terzo giocatore, quando non si uniscono in una coalizione;

v(T(1,2)) = 1500 ; v(T(1,3)) = 1800 ; v(T(2,3)) = 1900 ; questi valori della funzione caratteristica sono determinati dalle entrate di ciascuna coppia di giocatori uniti in una coalizione;

v(T(1,2,3)) = 3000 ; questo valore della funzione caratteristica è determinato dal ricavo medio nel caso in cui i giocatori si uniscano a tre.

Abbiamo quindi elencato tutte le possibili coalizioni di giocatori; ce ne sono otto, come dovrebbe essere, poiché il dominio di definizione della funzione caratteristica del gioco consiste esattamente di otto possibili sottoinsiemi dell'insieme di tutti i giocatori. Questo è ciò che richiede la teoria dei giochi, poiché occorre verificare la presenza di superadditività per i valori della funzione caratteristica di tutte le coalizioni disgiunte.

Come vengono soddisfatte le condizioni di superadditività in questo esempio? Determiniamo come i giocatori formano coalizioni disgiunte T1 E T2 . Se alcuni giocatori fanno parte di una coalizione T1 , allora tutti gli altri giocatori fanno parte della coalizione T2 e per definizione, questa coalizione è formata dalla differenza tra l'intero insieme di giocatori e l'insieme T1 . Allora se T1 - una coalizione di un giocatore, poi in una coalizione T2 ci saranno un secondo e un terzo giocatore se fanno parte di una coalizione T1 ci saranno il primo e il terzo giocatore, poi la coalizione T2 sarà composto solo dal secondo giocatore e così via.

Se ci sono più parti (persone) in conflitto, ciascuna delle quali prende una determinata decisione determinata da un determinato insieme di regole, e ciascuna delle persone conosce lo stato finale della situazione di conflitto con pagamenti predeterminati per ciascuna delle parti, allora un gioco si dice che abbia luogo.

Il compito della teoria dei giochi è scegliere una linea di comportamento per un dato giocatore, la cui deviazione può solo ridurre le sue vincite.

Alcune definizioni del gioco

La valutazione quantitativa dei risultati del gioco si chiama pagamento.

Raddoppia (due persone) è detto gioco a somma zero se la somma dei pagamenti è zero, cioè se la perdita di un giocatore è uguale al guadagno dell'altro.

Viene chiamata una descrizione inequivocabile della scelta di un giocatore in ciascuna delle possibili situazioni in cui deve effettuare una mossa personale strategia del giocatore .

La strategia di un giocatore è detta ottimale se, quando il gioco viene ripetuto più volte, fornisce al giocatore il massimo profitto medio possibile (o, che è la stessa cosa, il minimo profitto medio possibile).

Gioco definito da una matrice UN avendo M linee e N colonne è chiamato gioco di dimensioni a coppie finite M* N;

Dove io=
- strategia del primo giocatore con mstrategia; J=- strategia del secondo giocatore avente n strategie; ij– le vincite del primo giocatore io-strategia quando utilizzata dal secondo J-esima strategia (o, che è la stessa cosa, la perdita della seconda nella sua J-esima strategia, se utilizzata per prima io esimo);

A =   ij– matrice di pagamento del gioco.

1.1 Giocare con strategie pure

Prezzo del gioco basso (per il primo giocatore)

 = massimo (min ij). (1.2)

io J

Prezzo massimo del gioco (per il secondo giocatore):

= min (massimo ij) . (1.3)

J io

Se  =  , il gioco è chiamato gioco del punto di sella (1.4), o gioco con strategie pure. In cui V =  =  chiamato un gioco prezioso ( V- prezzo del gioco).

Esempio. Data la matrice dei pagamenti del gioco a 2 persone A. Determinare le strategie ottimali per ciascun giocatore e il prezzo del gioco:

(1.4)

massimo 10 9 12 6

io

min 6

J

- strategia del primo giocatore (fila).

Strategia del secondo giocatore (colonne).

- prezzo del gioco.

Pertanto, il gioco ha un punto di sella. Strategia J = 4 – strategia ottimale per il secondo giocatore io=2 - per il primo. Abbiamo un gioco con strategie pure.

1.2 Giochi con strategie miste

Se la matrice dei pagamenti non ha un punto di sella, ad es.
, e nessuno nel gioco può scegliere un piano come strategia ottimale, i giocatori passano a “strategie miste”. Inoltre, ogni giocatore utilizza ciascuna delle sue strategie più volte durante il gioco.

Un vettore, ciascuno dei cui componenti mostra la frequenza relativa dell'utilizzo da parte del giocatore della corrispondente strategia pura, è chiamato strategia mista di questo giocatore.

X= (X 1 …X io …X M) – strategia mista del primo giocatore.

U= (A 1 ... sì J ... sì N) – strategia mista del secondo giocatore.

Xio , sì J– frequenze relative (probabilità) dei giocatori che utilizzano le loro strategie.

Condizioni d'uso delle strategie miste

. (1.5)

Se X* = (X 1 * ….X io*... X M*) – strategia ottimale scelta dal primo giocatore; Y* = (A 1 * …A J*... A N*) è la strategia ottimale scelta dal secondo giocatore, quindi il numero è il costo della partita.

(1.6)

In ordine per il numero V era il prezzo del gioco, e X* E A* - strategie ottimali, necessarie e sufficienti per soddisfare le disuguaglianze

(1.7)

Se uno dei giocatori utilizza la strategia mista ottimale, il suo profitto sarà pari al costo del gioco V indipendentemente dalla frequenza con cui il secondo giocatore utilizzerà le strategie incluse in quella ottimale, comprese le strategie pure.

Ridurre i problemi di teoria dei giochi a problemi di programmazione lineare.

Esempio. Trova una soluzione al gioco definita dalla matrice dei payoff UN.

A = (1.8)

sì 1 sì 2 sì 3

Soluzione:

Creiamo una doppia coppia di problemi di programmazione lineare.

Per il primo giocatore

(1.9)

A 1 +A 2 +A 3 = 1 (1.10)

Liberarsi dalla variabile V(prezzo del gioco), dividere i lati sinistro e destro delle espressioni (1.9), (1.10) in V. Avendo accettato A J /V per una nuova variabile z io, noi abbiamo nuovo sistema vincoli (1.11) e funzione obiettivo (1.12)

(1.11)

. (1.12)

Allo stesso modo, otteniamo il modello di gioco per il secondo giocatore:

(1.13)

X 1 +X 2 +X 3 = 1 . (1.14)

Riduzione del modello (1.13), (1.14) a una forma senza variabile V, noi abbiamo

(1.15)

, (1.16)

Dove
.

Se dobbiamo determinare la strategia di comportamento del primo giocatore, ad es. frequenza relativa di utilizzo delle sue strategie ( X 1 ….X io …X M), utilizzeremo il modello del secondo giocatore, perché queste variabili sono nel suo modello di payoff (1.13), (1.14).

Riduciamo (1.15), (1.16) alla forma canonica

(1.17)

Contenuti 1 informazioni generali 2 1.1 Giochi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Mosse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Strategie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Gioco di matrici. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Punto del percorso. Strategie pure 7 2.1 Esempi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Esempio 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Esempio 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Strategie miste 9 3.1 Gioco 2×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Esempi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Esempio 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Esempio 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Interpretazione geometrica. . . . . . . . . . . . . . . . . . . . 12 3.2 Giochi 2×n e m×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Esempio 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Informazioni generali dalla teoria dei giochi 1.1. Giochi La teoria dei giochi è una teoria matematica delle situazioni di conflitto, ad es. situazioni in cui gli interessi di due o più parti che perseguono obiettivi diversi si scontrano. Un gioco è una situazione di conflitto regolata da determinate regole, che devono indicare: possibili opzioni per le azioni dei partecipanti; il risultato quantitativo del gioco o del pagamento (vincita, perdita) a cui porta una determinata serie di mosse; di ciascuna parte riguardo al comportamento dell’altra. Un gioco di doppio è un gioco a cui partecipano solo due parti (due giocatori). Un gioco accoppiato a somma zero è un gioco accoppiato in cui la somma dei pagamenti è zero, cioè La perdita di un giocatore è uguale al guadagno del secondo. A seconda dell'atteggiamento di ciascun giocatore nei confronti del valore della funzione di profitto, i giochi accoppiati sono suddivisi: Gioco accoppiato a somma zero (antagonista) - un gioco accoppiato in cui l'importo dei pagamenti è uguale a zero, ad es. La perdita di un giocatore è uguale al guadagno del secondo. Un gioco non antagonista è un gioco di coppia in cui i giocatori perseguono obiettivi diversi, ma non direttamente opposti. 21.2. Mosse Mossa - scelta di una delle azioni previste dalle regole del gioco. Le mosse sono di due tipi: Mossa personale - + scelta consapevole una delle azioni previste dalle regole del gioco + l'implementazione di questa scelta Mossa casuale - Una mossa casuale è una scelta tra una serie di possibilità, effettuata non dalla decisione del giocatore, ma da un meccanismo di selezione casuale. Di seguito consideriamo i giochi abbinati a somma zero contenenti solo mosse personali. Ciascuna parte non dispone di informazioni sul comportamento dell'altra. 31.3. Strategie La strategia di un giocatore è un insieme di regole che determinano la scelta delle azioni per ogni mossa personale di questo giocatore, a seconda della situazione che si presenta durante il gioco. A seconda del numero di strategie possibili, i giochi si dividono in finiti e infiniti. Gioco senza fine- un gioco in cui almeno uno dei giocatori ha un numero infinito di strategie. Un gioco finito è un gioco in cui ogni giocatore ha solo un numero finito di strategie. Il numero di mosse consecutive di ciascun giocatore determina la divisione delle partite in mosse singole, mosse multiple o posizionali. + In una partita ad un turno, ogni giocatore fa solo una scelta tra le opzioni possibili e poi determina l'esito della partita. + Un gioco multi-mossa, o posizionale, si sviluppa nel tempo, rappresentando una serie di fasi successive, ognuna delle quali avviene dopo la mossa di uno dei giocatori e un corrispondente cambiamento della situazione. In una partita a un turno, ogni giocatore fa una sola scelta tra possibili opzioni e quindi determina l'esito del gioco. La strategia ottimale di un giocatore è una strategia che, quando il gioco viene ripetuto più volte, fornisce a questo giocatore la massima vincita media possibile (o, che è lo stesso, la minima perdita media possibile). Nella teoria dei giochi, tutte le raccomandazioni vengono formulate sulla base del presupposto di un comportamento ragionevole dei giocatori. Gli errori di calcolo e gli errori dei giocatori, inevitabili in ogni situazione di conflitto, così come gli elementi di eccitazione e rischio non vengono presi in considerazione nella teoria dei giochi. 41.4. Gioco a matrice Un gioco a matrice è un gioco finito a somma zero con una mossa Un gioco a matrice è un modello teorico dei giochi di una situazione di conflitto in cui gli avversari, per raggiungere obiettivi diametralmente opposti, fanno una scelta (mossa) da un gioco finito. numero modi possibili azioni In base ai metodi di azione (strategie) scelti, viene determinato il risultato raggiunto. Diamo un'occhiata a un esempio. Supponiamo che ci siano due giocatori A e B, uno dei quali può scegliere i-esima strategia da m delle sue possibili strategie A1, A2, ...Am, e la seconda sceglie la j-esima strategia tra le sue possibili strategie B1, B2, ...Bm. Di conseguenza, il primo giocatore vince il valore aij e il secondo giocatore perde questo valore. Dai numeri aij creiamo una matrice   a11 a11 · · · a1n  a21 a22 · · · a2n    A = (aij) =  .. .. ..   . . . .  am1 am2 · · · amn La matrice A = (aij), i = 1, m, j = 1, n è detta matrice dei payoff o matrice dei giochi m × n. In questa matrice, le righe rappresentano sempre le strategie del giocatore vincente (massimizzatore) A, cioè del giocatore che si sforza di massimizzare le sue vincite. Le colonne sono assegnate alle strategie del giocatore perdente B, cioè del giocatore che cerca di minimizzare il criterio di efficienza. La normalizzazione di un gioco è il processo di riduzione di un gioco posizionale a un gioco a matrice. Un gioco in forma normale è un gioco posizionale ridotto a un gioco a matrice. Ricordiamo che un gioco posizionale a più mosse è un modello teorico del gioco di a situazione di conflitto in cui gli avversari fanno in sequenza una scelta (mossa) da un numero finito di possibili linee d'azione in ogni fase di sviluppo di questa situazione. La soluzione del gioco è trovare le strategie ottimali di entrambi i giocatori e determinare il prezzo del gioco. Il prezzo del gioco è il guadagno (perdita) atteso dei giocatori. La soluzione del gioco può essere trovata sia nelle strategie pure, quando il giocatore deve seguire un'unica strategia, sia in quelle miste, quando il giocatore deve utilizzare due o più strategie pure con determinate probabilità. Questi ultimi in questo caso si chiamano attivi. 5 La strategia mista di un giocatore è un vettore, ciascuna componente del quale mostra la frequenza di utilizzo da parte del giocatore della corrispondente strategia pura. Massimizzazione o prezzo più basso del gioco - numero α = max min aij i j Strategia di massimizzazione (linea) - la strategia che il giocatore ha scelto per massimizzare la sua vincita minima. Ovviamente, quando si sceglie la strategia di massimizzazione più cauta, il giocatore A si garantisce (indipendentemente dal comportamento dell’avversario) un profitto garantito di almeno α. Massimino o prezzo superiore del gioco - numero β = min max aij j i Strategia Minimax (colonna) - la strategia che il giocatore ha scelto per minimizzare la sua perdita massima. Ovviamente, quando si sceglie la strategia minimax più cauta, il giocatore B non consente in nessun caso al giocatore A di vincere più di β. Il prezzo più basso del gioco non supera sempre il prezzo più alto del gioco α = max min aij 6 min max aij = β i j j i Teorema 1 (il teorema principale della teoria dei giochi di matrici). Ogni gioco finito ha almeno una soluzione, possibilmente nel regno delle strategie miste. 6 2. Giochi con punto di sella. Soluzione in strategie pure Un gioco con un punto di sella è un gioco per il quale α = max min aij = min max aij = β i j j i Per i giochi con un punto di sella, trovare una soluzione consiste nello scegliere le strategie maximin e minimax che sono ottimali., Puro costo del gioco - il valore totale del prezzo inferiore e superiore del gioco α=β=ν 2.1. Esempi Esempio 1 Trovare una soluzione nelle strategie pure del gioco date dalla matrice   8 4 7 A= 6 5 9  7 7 8 Soluzione: determinare il prezzo superiore e inferiore del gioco. Per fare ciò, troviamo il minimo dei numeri aij in i-esima riga αi = min aij j e il massimo dei numeri aij nella jesima colonna βj = max aij i Scriviamo i numeri αi (minimi di riga) accanto alla matrice dei pagamenti a destra sotto forma di colonna aggiuntiva. Scriviamo i numeri βi (massimi delle colonne) sotto la matrice sotto forma di una riga aggiuntiva: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Trova il massimo dei numeri αi α = max αi = 7 i e il minimo dei numeri βj β = min βj = 7 j α = β - il gioco ha un punto di sella. La strategia ottimale per il giocatore è la strategia A3, e per il giocatore B è la strategia B2, prezzo netto del gioco ν = 7 Esempio 2 La matrice dei pagamenti è data:   2 2 1 1 2  0 1 1 1 1  A=  1 1 1 1 2   1 2 1 1 2 Trova una soluzione al gioco in strategie pure. Soluzione: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Il gioco ha sei punti di sella. Le strategie ottimali saranno: A1 e B3 o B4 A3 e B3 o B4 A4 e B3 o B4 8 3. Soluzione del gioco in strategie miste Quando α = β. Nel caso in cui, quando scelgono le proprie strategie, entrambi i giocatori non abbiano informazioni sulla scelta dell'altro, il gioco ha una soluzione in strategie miste. SA = (p1, p2, ..., pm) - strategia mista del giocatore A, in cui le strategie A1, A2, ..., Am vengono applicate con probabilità ∑ m p1, p2, ..., pm, pi = 1, pi > 0, i = 1, m i=1 SB = (q1, q2, ..., qn) - strategia mista del giocatore B, in cui le strategie B1, B2, ..., Bm vengono applicate con probabilità ∑ n q1, q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 Se: SA∗ è la strategia ottima del giocatore A, SB∗ è la strategia ottima del giocatore B, allora il costo del gioco è ∑ n ∑ m ν = aij · p∗i · qi∗ j=1 i=1 Il seguente teorema risponde alla domanda su come trovare una soluzione per i giochi 2 × 2, 2 × n, m × 2 Teorema 2 (come trovare una soluzione per i giochi 2 × 2, 2 × n, m × 2). Se uno dei giocatori utilizza una strategia mista ottimale, allora il suo profitto sarà pari al costo del gioco ν, indipendentemente dalla probabilità con cui il secondo giocatore utilizzerà le strategie incluse in quella ottimale (comprese le strategie pure). 9 3.1. Gioco 2 × 2 Consideriamo un gioco 2 × 2 con la matrice: () a11 a21 a21 a22 Supponiamo che il gioco non abbia soluzioni in strategie pure. Troviamo le strategie ottime SA∗ e SB∗. Per prima cosa definiamo la strategia SA∗ = (p∗1 , p∗2). Secondo il teorema, se il partito A aderisce alla strategia ν, allora, indipendentemente dalla linea di condotta del partito B, il profitto rimarrà uguale al costo del gioco ν. Di conseguenza, se il lato A aderisce alla strategia ottima SA∗ = (p∗1, p∗2), allora il lato B può applicare qualsiasi delle sue strategie senza modificare il suo payoff. Quindi, quando il giocatore B utilizza la strategia pura B1 o B2, riceverà un profitto medio pari al costo del gioco: a11 p∗1 + a21 p∗2 = ν ← per la strategia B1 a12 p∗1 + a22 p∗ 2 = ν ← per la strategia B2 Tenendo conto si noti che p∗1 + p∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Prezzo del gioco: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 La strategia ottima del giocatore B si trova in modo simile: SB∗ = (q1∗ , q2∗). Tenendo conto che q1∗ + q2∗ = 1: q1∗ = a2 2−a1 2 a11 +a22 −a12 −a21 q2∗ = a1 1−a2 1 a11 +a22 −a12 −a21 3.1.1. Esempi Esempio 3 Trovare la soluzione del gioco con matrice () −1 1 A= 1 −1 10 Soluzione: il gioco non ha punto di sella, poiché α= -1, β = 1, α ̸= β. Cerchiamo una soluzione con strategie miste. Usando le formule per p∗ e q∗, otteniamo p∗1 = p∗2 = 0.5 e q1∗ = q2∗ = 0.5, ν = 0 Quindi, SA∗ = (0.5, 0.5) SB∗ = (0.5, 0.5 ) Esempio 4 Trovare la soluzione del gioco con matrice () 2 5 A= 6 4 Soluzione: il gioco non ha punto di sella, poiché α= 4, β = 5, α ̸= β. Cerchiamo una soluzione con strategie miste. Usando le formule per p∗ e q∗, otteniamo p∗1 = 0.4, p∗2 = 0.6 e q1∗ = 0.2 q2∗ = 0.8, ν = 4.4 Quindi, SA∗ = (0.4, 0.6) SB∗ = ( 0,2, 0,8) 11 3.1.2. Interpretazione geometrica Al gioco 2×2 può essere data una semplice interpretazione geometrica. Prendiamo una singola sezione dell'asse delle ascisse, ogni punto della quale associamo una strategia mista S = (p1 , p2) = (p1 , 1 − p1) e la probabilità p1 della strategia A1 sarà uguale alla distanza da punto SA all'estremità destra della sezione e la probabilità p2, strategia A2 - la distanza dall'estremità sinistra. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ In particolare, l'estremità sinistra della sezione (punto con ascissa = 0) corrisponde alla strategia A1, estremità destra del segmento (x = 1) - strategia A2 Alle estremità del segmento vengono ripristinate due perpendicolari all'asse x: asse I − I - il profitto per la strategia A1 viene posticipato; II - il pagamento per la strategia A2 viene posticipato. Lasciamo che il giocatore B applichi la strategia B1; dà sugli assi I − I e II − II, rispettivamente, punti di ordinate a11 e a21. Tracciamo una linea retta B1 − B1′ passante per questi punti. Per ogni strategia mista SA = (p1, p2), la vincita del giocatore è determinata dal punto N sulla retta B1 − B1′, corrispondente al punto SA sull’asse x che divide il segmento nel rapporto p2: p1. Ovviamente, la retta B2 − B2′, che determina il profitto della strategia B2, può essere costruita esattamente nello stesso modo. 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ È necessario trovare la strategia ottima SA∗ , ovvero in modo tale che il profitto minimo del giocatore A (dato il comportamento peggiore per lui da parte del giocatore B) si trasformi in un massimo. Per fare ciò, costruisci un limite inferiore per il profitto del giocatore A per le strategie B1, B2, cioè linea spezzata B1 N B2′ ;. Su questo confine si trova il profitto minimo del giocatore A per qualsiasi delle sue strategie miste, punto N, in cui questo profitto raggiunge il massimo e determina la decisione e il prezzo del gioco. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P L'ordinata del punto N non è altro che il costo del gioco ν, la sua ascissa è pari a ∗2 e la distanza dall'estremità destra del segmento è pari a ∗1, cioè la distanza dal punto SA∗ agli estremi del segmento sono pari alle probabilità ∗2 e ∗1 delle strategie A2 e A1 della strategia mista ottimale del giocatore A. in questo caso la soluzione del gioco era determinata dalla punto di intersezione delle strategie B1 e B2. Di seguito è riportato un caso in cui strategia ottimale la strategia del giocatore è pura A2. In questo caso la strategia A2 (per qualsiasi strategia nemica) è più redditizia della strategia A1, 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I .I . .x .I . .X. 2∗ P. A∗S = A2. 2∗ P. A∗ S = A2 A destra è mostrato il caso in cui il giocatore B ha una strategia ovviamente non redditizia. L'interpretazione geometrica permette anche di visualizzare il prezzo più basso del gioco α e il prezzo più alto β .y .I .I I .B2. .B1′ .N .B1 .B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P Nello stesso grafico possiamo anche dare un'interpretazione geometrica delle strategie ottime del giocatore B. È facile verificare che la quota q1∗ della strategia B1 della strategia mista ottima SB∗ = (q1∗ , q2∗) è pari al rapporto tra la lunghezza del segmento KB2 e la somma delle lunghezze dei segmenti KB1 e KB2 sull'asse I − I: .y .I .I I .B2 .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P 14 KB2 q1∗ = KB2 + KB1 o LB2′ q1∗ = LB2′ + LB1′ La strategia ottimale SB∗ = (q1∗ , q2∗) può essere trovata in un altro modo, se scambiamo i giocatori B e B, e invece del massimo del limite inferiore delle vincite, considera il minimo del limite superiore. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. Giochi 2 × n e m × 2 La soluzione dei giochi 2 × n e m × 2 si basa sul seguente teorema. Teorema 3. Per qualsiasi il gioco definitivo m × n esiste una soluzione in cui il numero di strategie attive di ciascun lato non supera il più piccolo dei numeri m e n. Secondo questo teorema, un gioco 2×n ha sempre una soluzione in cui ogni giocatore ha al più due strategie attive. Una volta trovate queste strategie, il gioco 2×n si trasforma in un gioco 2×2, che può essere risolto in modo elementare. La ricerca delle strategie attive può essere effettuata graficamente: 1) si costruisce un'interpretazione grafica; 2) viene determinato il limite inferiore della vincita; 3) vengono identificate due strategie del secondo giocatore al limite inferiore della vincita, che corrispondono a due linee che si intersecano nel punto con l'ordinata massima (se più di due linee si intersecano in questo punto, viene presa una coppia qualsiasi) - queste strategie rappresentano le strategie attive del giocatore B. Pertanto, il gioco 2 × n si riduce al gioco 2 × 2. Anche il gioco m × 2 può essere risolto, con la differenza che non è il limite inferiore, ma quello superiore del payoff costruito, e non il massimo, ma su di esso si cerca il minimo. Esempio 5 Trovare una soluzione al gioco () 7 9 8 A= 10 6 9 Soluzione: utilizzando il metodo geometrico, selezioniamo le strategie attive. Le linee dirette B1 − B1′, B2 − B2′ e B3 − B3′ corrispondono alle strategie B1, B2, B3. La linea tratteggiata B1 N B2 rappresenta il limite inferiore delle vincite del giocatore. Il gioco ha soluzione S∗A = (23, 31); S∗B = (0,5; 0,5; 0); v = 8. 16 .y .I .I I . 1'BB . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .X. 2∗ P. A∗ S . 1∗ P 17 Indice del gioco, 2 mossa, 3 2 × 2, 10 personale, 3 2 × 2, 9 casuale, 3 geometria, 12 prezzo netto del gioco, 7 esempi, 10 2 × n, 9, 16 m × 2, 9 , 16 infinite, 4 in forma normale, 5 finite, 4 multi-mossa, 4 a una mossa, 4 matrice, 5 accoppiate, 2 a somma zero, 2 antagoniste, 2 non antagoniste, 2 soluzione, 5 in strategie miste, 5 , 9 in strategie pure, 5 con punto di sella, 7 prezzo, 5 superiore, 6 inferiore, 6 puro, 7 maximin, 6 matrice di gioco, 5 payoff, 5 minimax, 6 normalizzazione del gioco, 5 strategia, 4 maximin, 6 minimax, 6 ottimale, 4 misto, 5 teoria dei giochi, 2 18

Dal popolare blog americano Cracked.

La teoria dei giochi riguarda lo studio dei modi per eseguire la mossa migliore e, di conseguenza, ottenere la maggior parte possibile della torta vincente tagliandone una parte agli altri giocatori. Ti insegna ad analizzare molti fattori e a trarre conclusioni logicamente equilibrate. Penso che dovrebbe essere studiato dopo i numeri e prima dell'alfabeto. Semplicemente perché troppe persone prendono decisioni importanti basandosi sull'intuizione, su profezie segrete, sulla posizione delle stelle e simili. Ho studiato a fondo la teoria dei giochi e ora voglio parlarti delle sue basi. Forse questo aggiungerà un po’ di buon senso alla tua vita.

1. Il dilemma del prigioniero

Berto e Robert sono stati arrestati per rapina in banca dopo non aver utilizzato correttamente un'auto rubata per scappare. La polizia non può provare che siano stati loro a rapinare la banca, ma li ha colti in flagrante a bordo di un'auto rubata. Sono stati portati in stanze diverse e a ciascuno è stato offerto un patto: consegnare un complice e mandarlo in prigione per 10 anni, e essere rilasciato lui stesso. Ma se entrambi si tradiscono a vicenda, ciascuno riceverà 7 anni. Se nessuno dice niente, entrambi andranno in prigione per 2 anni solo per furto d'auto.

Si scopre che se Berto rimane in silenzio, ma Robert lo denuncia, Berto andrà in prigione per 10 anni e Robert sarà libero.

Ogni prigioniero è un giocatore e il vantaggio di ognuno può essere espresso come una "formula" (ciò che ottengono entrambi, ciò che ottiene l'altro). Ad esempio, se ti colpissi, il mio schema vincente sarebbe questo (ottengo una vittoria dura, tu soffri molto dolore). Poiché ogni detenuto ha due opzioni, possiamo presentare i risultati in una tabella.

Applicazione pratica: identificazione dei sociopatici

Qui vediamo l’applicazione principale della teoria dei giochi: identificare i sociopatici che pensano solo a se stessi. La vera teoria dei giochi è un potente strumento analitico e il dilettantismo spesso funge da bandiera rossa che segnala qualcuno che non ha il senso dell’onore. Le persone che fanno calcoli intuitivi credono che sia meglio fare qualcosa di brutto perché si tradurrà in una pena detentiva più breve, qualunque cosa faccia l'altro giocatore. Tecnicamente questo è corretto, ma solo se sei una persona miope che punta i numeri più in alto vite umane. Questo è il motivo per cui la teoria dei giochi è così popolare in finanza.

Il vero problema del dilemma del prigioniero è che ignora i dati. Ad esempio, non considera la possibilità che tu incontri amici, parenti o addirittura creditori della persona che hai mandato in prigione per 10 anni.

La cosa peggiore è che tutti coloro che sono coinvolti nel dilemma del prigioniero si comportano come se non ne avessero mai sentito parlare.

E la cosa migliore è restare in silenzio, e dopo due anni, insieme ad un buon amico, usare gli stessi soldi.

2. Strategia dominante

Questa è una situazione in cui le tue azioni danno il massimo profitto, indipendentemente dalle azioni del tuo avversario. Qualunque cosa accada, hai fatto tutto bene. Questo è il motivo per cui molte persone con il dilemma del prigioniero credono che il tradimento porti al risultato "migliore" indipendentemente da ciò che fa l'altra persona, e l'ignoranza della realtà insita in questo metodo lo fa sembrare semplicissimo.

La maggior parte dei giochi a cui giochiamo non hanno strategie strettamente dominanti perché altrimenti sarebbero terribili. Immagina se facessi sempre la stessa cosa. Non esiste una strategia dominante nel gioco sasso-carta-forbici. Ma se giocassi con una persona che indossa i guanti da forno e può mostrare solo sasso o carta, avresti una strategia dominante: la carta. La tua carta avvolgerà la sua pietra o risulterà in un pareggio e non potrai perdere perché il tuo avversario non può mostrare le forbici. Ora che hai una strategia dominante, saresti uno sciocco a provare qualcosa di diverso.

3. Battaglia dei sessi

I giochi sono più interessanti quando non hanno una strategia strettamente dominante. Ad esempio, la battaglia dei sessi. Anjali e Borislav escono insieme, ma non possono scegliere tra balletto e boxe. Anjali ama la boxe perché le piace vedere il sangue scorrere per la gioia di una folla urlante di spettatori che pensano di essere civili solo perché hanno pagato per spaccare la testa a qualcuno.

Borislav vuole guardare il balletto perché capisce cosa passano le ballerine grande quantità infortuni e gli allenamenti più difficili, sapendo che un infortunio può mettere fine a tutto. I ballerini sono i più grandi atleti della Terra. Una ballerina può darti un calcio in testa, ma non lo farà mai, perché la sua gamba vale molto più della tua faccia.

Ognuno di loro vuole andare al proprio evento preferito, ma non vuole goderselo da solo, quindi otteniamo lo schema per la loro vincita: il valore più grande è fare ciò che gli piace, valore più piccolo- semplicemente stare con un'altra persona e zero - stare da soli.

Alcune persone suggeriscono una politica del rischio calcolato ostinata: se fai quello che vuoi, qualunque cosa accada, l'altra persona dovrà conformarsi alla tua scelta o perdere tutto. Come ho già detto, la teoria dei giochi semplificata è ottima per identificare gli sciocchi.

Applicazione pratica: evitare angoli acuti

Naturalmente, questa strategia ha anche i suoi notevoli svantaggi. Prima di tutto, se consideri i tuoi appuntamenti come una "battaglia tra i sessi", non funzionerà. Lasciatevi in ​​modo che ognuno di voi possa trovare qualcuno che gli piace. E il secondo problema è che in questa situazione i partecipanti sono così insicuri di se stessi da non poterlo fare.

La strategia veramente vincente per ognuno è fare quello che vuole. e dopo, o il giorno dopo, quando saranno liberi, andremo insieme in un bar. Oppure alternare boxe e balletto finché non avviene una rivoluzione nel mondo dello spettacolo e viene inventato il balletto di boxe.

4. Equilibrio di Nash

Un equilibrio di Nash è un insieme di mosse in cui nessuno vuole fare qualcosa di diverso dopo che si sono verificate. E se riusciamo a farlo funzionare, la teoria dei giochi sostituirà l’intero sistema filosofico, religioso e finanziario del pianeta, perché “il desiderio di non andare in rovina” è diventato per l’umanità una forza trainante più potente del fuoco.

Dividiamo rapidamente $ 100. Tu ed io decidiamo quante delle centinaia di cui abbiamo bisogno e allo stesso tempo annunciamo gli importi. Se il totale è inferiore a cento, ognuno ottiene ciò che desidera. Se il totale è superiore a cento, quello che ha chiesto la somma minore ottiene la somma che desidera, mentre la persona più avida ottiene ciò che resta. Se chiediamo la stessa cifra, ognuno riceverà 50$. Quanto chiederai? Come dividerai i soldi? C'è solo una mossa vincente.

Richiedere $51 ti darà l'importo massimo, indipendentemente da ciò che sceglie il tuo avversario. Se ne chiede di più, riceverai $ 51. Se chiede $ 50 o $ 51, riceverai $ 50. E se chiede meno di 50$, riceverai 51$. In ogni caso, non esiste altra opzione che ti farà guadagnare più soldi di questa. Equilibrio di Nash: una situazione in cui entrambi scegliamo 51$.

Applicazione pratica: pensare prima

Questo è il punto centrale della teoria dei giochi. Non devi vincere e tanto meno danneggiare gli altri giocatori, ma devi fare la mossa migliore per te stesso, indipendentemente da ciò che chi ti circonda ha in serbo per te. Ed è ancora meglio se questa mossa è vantaggiosa per gli altri giocatori. Questo è il tipo di matematica che potrebbe cambiare la società.

Una variazione interessante di questa idea è il bere, che può essere chiamato equilibrio di Nash dipendente dal tempo. Quando bevi abbastanza, non ti preoccupi delle azioni degli altri, qualunque cosa facciano, ma il giorno dopo ti penti davvero di non aver fatto qualcosa di diverso.

5. Gioco del lancio

Il sorteggio viene effettuato tra il Giocatore 1 e il Giocatore 2. Ogni giocatore sceglie simultaneamente testa o croce. Se indovinano, il Giocatore 1 riceve il centesimo del Giocatore 2. In caso contrario, il Giocatore 2 riceve la moneta del Giocatore 1.

La matrice vincente è semplice...

...strategia ottimale: gioca in modo completamente casuale.È più difficile di quanto pensi perché la scelta deve essere completamente casuale. Se hai una preferenza per testa o croce, il tuo avversario può usarla per prendere i tuoi soldi.

Naturalmente, il vero problema qui è che sarebbe molto meglio se si lanciassero solo un centesimo a vicenda. Di conseguenza, i loro profitti sarebbero gli stessi e il trauma che ne deriverebbe potrebbe aiutare queste persone sfortunate a provare qualcosa di diverso dalla terribile noia. Dopotutto, questo partita peggiore mai esistente. E questo è il modello ideale per i calci di rigore.

Applicazione pratica: Penalità

Nel calcio, nell'hockey e in molti altri giochi, i tempi supplementari sono i calci di rigore. E sarebbero più interessanti se si basassero su quante volte i giocatori in piena forma potrebbero fare la ruota, perché sarebbe almeno un indicatore della loro abilità fisica e sarebbe divertente da guardare. I portieri non possono determinare chiaramente il movimento della palla o del disco all'inizio del suo movimento, perché, sfortunatamente, i robot non partecipano ancora alle nostre competizioni sportive. Il portiere deve scegliere la direzione sinistra o destra e sperare che la sua scelta corrisponda alla scelta dell'avversario che tira in porta. Questo ha qualcosa in comune con il gioco delle monete.

Tuttavia, tieni presente che questo non è un perfetto esempio di somiglianza con il gioco di testa e croce, perché anche con la giusta direzione, il portiere potrebbe non prendere la palla e l'attaccante potrebbe non centrare la porta.

Allora qual è la nostra conclusione secondo la teoria dei giochi? I giochi con la palla dovrebbero terminare in modalità "multi-palla", in cui ogni minuto uno contro uno ai giocatori viene data una palla/disco extra finché una delle due parti non raggiunge un determinato risultato, che è un'indicazione della vera abilità dei giocatori, e non una spettacolare coincidenza casuale.

In fin dei conti, la teoria dei giochi dovrebbe essere utilizzata per rendere il gioco più intelligente. Il che significa che è meglio.