Giochi a due giocatori

I giochi aleatori a un giocatore confrontano una decisione con il caso. Nei giochi a due giocatori entrambi i decisori scelgono simultaneamente un’azione, e il risultato dipende dalla coppia di scelte: è il dominio della teoria dei giochi (von Neumann, Nash). Questa sezione introduce gli strumenti fondamentali — la matrice di payoff, la dominanza tra strategie, l’equilibrio di Nash e le strategie miste — e li mette alla prova su tre esempi classici: un gioco fantasy risolto con le strategie miste, il dilemma del prigioniero e il gioco a somma zero “pari o dispari”.

• Matrice di payoff
• Strategia dominante e dominata
• Equilibrio di Nash
• Strategia mista
• Esempio — Strega e Gigante
• Esempio — Dilemma del prigioniero
• Esempio — Pari o dispari

Random one-player games pit a decision against chance. In two-player games both decision-makers choose an action simultaneously, and the result depends on the pair of choices: this is the domain of game theory (von Neumann, Nash). This section introduces the fundamental tools — the payoff matrix, dominance between strategies, the Nash equilibrium and mixed strategies — and puts them to the test on three classic examples: a fantasy game solved with mixed strategies, the prisoner’s dilemma and the “odds or evens” zero-sum game.

• Matrice di payoff
• Strategia dominante e dominata
• Equilibrio di Nash
• Strategia mista
• Esempio — Strega e Gigante
• Esempio — Dilemma del prigioniero
• Esempio — Pari o dispari

Nei giochi a due giocatori entrambi i decisori scelgono simultaneamente un’azione e il risultato dipende dalla coppia di scelte: è il dominio della teoria dei giochi (von Neumann, Nash). Il primo strumento per rappresentarli è la matrice di payoff.

Definizione — Matrice di payoff

Un gioco a due giocatori finito si rappresenta con una matrice di payoff $m\times n$: le righe sono le strategie pure del Giocatore 1, le colonne quelle del Giocatore 2. Ogni cella contiene la coppia $(v_1; v_2)$ delle vincite per i due giocatori in corrispondenza di quel profilo di scelte.

Se $v_1(s)+v_2(s)=0$ per ogni profilo $s$, il gioco è a somma zero (quel che uno guadagna l’altro lo perde).

Collegamenti

Argomenti: Probabilita
Concetti: Gioco a somma zero · Matrice di payoff · Teoria dei giochi
Metodi: Gioco somma zero
Competenze: Modellizzare
Persone: Von Neumann

In two-player games both decision-makers choose an action simultaneously and the result depends on the pair of choices: this is the domain of game theory (von Neumann, Nash). The first tool for representing them is the payoff matrix.

Definition — Payoff matrix

A finite two-player game is represented by an $m\times n$ payoff matrix: the rows are Player 1’s pure strategies, the columns Player 2’s. Each cell contains the pair $(v_1; v_2)$ of the winnings for the two players corresponding to that profile of choices.

If $v_1(s)+v_2(s)=0$ for every profile $s$, the game is zero-sum (what one gains the other loses).

Links

Topics: Probability
Concepts: Zero-sum game · Payoff matrix · Game theory
Methods: Zero-sum game
Skills: Modelling
People: Von Neumann

Prima di cercare l’equilibrio conviene semplificare il gioco eliminando le scelte che nessun giocatore razionale farebbe mai.

Definizione — Strategia dominante / dominata

Una strategia (riga o colonna) domina un’altra se i suoi payoff sono $\geq$ in tutte le posizioni dell’avversario. Una strategia dominata può essere razionalmente eliminata: nessun giocatore razionale la gioca.

Collegamenti

Argomenti: Probabilita
Concetti: Strategia dominante · Strategia dominata · Teoria dei giochi
Metodi: Strategia dominante
Competenze: Ragionare per casi

Before looking for the equilibrium it is worth simplifying the game by eliminating the choices that no rational player would ever make.

Definition — Dominant / dominated strategy

A strategy (row or column) dominates another if its payoffs are $\geq$ in every position of the opponent. A dominated strategy can be rationally eliminated: no rational player plays it.

Links

Topics: Probabilita
Concepts: Strategia dominante · Strategia dominata · Teoria dei giochi
Methods: Strategia dominante
Skills: Ragionare per casi

L’idea centrale della teoria dei giochi è quella di configurazione stabile: nessuno ha interesse a cambiare mossa da solo.

Definizione — Equilibrio di Nash, strategie pure

Una coppia di strategie pure $(s_1^*, s_2^*)$ è un equilibrio di Nash se nessun giocatore guadagna deviando unilateralmente: dato $s_2^*$, $s_1^*$ è ottima per G1; dato $s_1^*$, $s_2^*$ è ottima per G2. In strategie pure può non esistere; in strategie miste esiste sempre per giochi finiti (Nash, 1950).

Collegamenti

Argomenti: Probabilita
Concetti: Equilibrio di nash · Teoria dei giochi
Metodi: Equilibrio nash
Competenze: Modellizzare
Persone: Nash

The central idea of game theory is that of a stable configuration: nobody has any interest in changing their move on their own.

Definition — Nash equilibrium, pure strategies

A pair of pure strategies $(s_1^*, s_2^*)$ is a Nash equilibrium if no player gains by deviating unilaterally: given $s_2^*$, $s_1^*$ is optimal for G1; given $s_1^*$, $s_2^*$ is optimal for G2. In pure strategies it may fail to exist; in mixed strategies it always exists for finite games (Nash, 1950).

Links

Topics: Probabilita
Concepts: Equilibrio di nash · Teoria dei giochi
Methods: Equilibrio nash
Skills: Modellizzare
People: Nash

Quando nessuna scelta fissa è ottima, conviene randomizzare: giocare le proprie azioni con probabilità stabilite. È qui che la teoria dei giochi incontra il valore atteso.

Definizione — Strategia mista

Un giocatore adotta una strategia mista quando sceglie le proprie azioni con una distribuzione di probabilità fissata $(p_1,\ldots,p_n)$. La vincita attesa diventa la media pesata dei payoff sulle azioni, ed è lineare nelle probabilità. Ottimizzare significa scegliere $(p_i)$ in modo da massimizzare la propria vincita attesa dato il comportamento (eventualmente misto) dell’avversario.

Collegamenti

Argomenti: Probabilita
Concetti: Equilibrio di nash · Strategia mista · Valore atteso
Metodi: Strategia mista
Competenze: Calcolo probabilita · Modellizzare

When no fixed choice is optimal, it is worth randomising: playing one’s own actions with set probabilities. This is where game theory meets expected value.

Definition — Mixed strategy

A player adopts a mixed strategy when they choose their actions with a fixed probability distribution $(p_1,\ldots,p_n)$. The expected winnings become the weighted average of the payoffs over the actions, and it is linear in the probabilities. Optimising means choosing $(p_i)$ so as to maximise one’s own expected winnings given the (possibly mixed) behaviour of the opponent.

Links

Topics: Probabilita
Concepts: Equilibrio di nash · Strategia mista · Valore atteso
Methods: Strategia mista
Skills: Calcolo probabilita · Modellizzare

Un gioco fantasy a due giocatori: fissata la strategia mista di uno, si cerca la risposta ottima dell’altro calcolando la sua vincita attesa in funzione della probabilità di gioco.

Esempio — Strega/Gigante vs Cavaliere/Drago

Giocatore 1 sceglie Strega (S) o Gigante (G); Giocatore 2 sceglie Cavaliere (C) o Drago (D). Le giocate sono indipendenti (entrambi giocano in cieco). La matrice di payoff $(v_1; v_2)$ è:

G1 / G2	Cavaliere	Drago
Strega	$(1; -2)$	$(-2; 3)$
Gigante	$(3; -1)$	$(-3; -3)$

Supponi che G1 abbia già fissato la strategia mista $P(S)=1/3$, $P(G)=2/3$. Trova la strategia ottima di G2 (parametro $p=P(C)$, $1-p=P(D)$).

Probabilità congiunte (giocate indipendenti): $P(S,C)=\tfrac{1}{3}p,\quad P(S,D)=\tfrac{1}{3}(1-p),\quad P(G,C)=\tfrac{2}{3}p,\quad P(G,D)=\tfrac{2}{3}(1-p).$

Vincita media di G2 (somma sui quattro profili dei payoff $v_2$ per le rispettive probabilità):

\bar V_2(p) &= (-2)\cdot\tfrac{1}{3}p + 3\cdot\tfrac{1}{3}(1-p) + (-1)\cdot\tfrac{2}{3}p + (-3)\cdot\tfrac{2}{3}(1-p) \\ &= -\tfrac{2}{3}p + 1 - p -\tfrac{2}{3}p - 2(1-p) \\ &= -\tfrac{7}{3}p + 1 - 2 + 2p \\ &= \tfrac{-7+6}{3}p - 1 \\ &= -1 - \tfrac{p}{3}. \end{align*}$$ **Conclusione (retta calante in $p$).** $\bar V_2(p)=-1-p/3$ è *decrescente* in $p$: G2 minimizza la propria perdita scegliendo $p=0$, cioè *sempre Drago*. La vincita ottima di G2 vale $\bar V_2(0)=-1$ (paga sempre $1$ EUR in media).

Collegamenti

Argomenti: Probabilita
Concetti: Matrice di payoff · Strategia mista · Valore atteso
Metodi: Strategia mista · Valore atteso
Competenze: Calcolo probabilita · Modellizzare

A two-player fantasy game: with one player’s mixed strategy fixed, we look for the other’s best response by computing their expected winnings as a function of the probability of play.

Example — Strega/Gigante vs Cavaliere/Drago

Player 1 chooses Strega (S) or Gigante (G); Player 2 chooses Cavaliere (C) or Drago (D). The plays are independent (both play blind). The payoff matrix $(v_1; v_2)$ is:

G1 / G2	Cavaliere	Drago
Strega	$(1; -2)$	$(-2; 3)$
Gigante	$(3; -1)$	$(-3; -3)$

Suppose G1 has already fixed the mixed strategy $P(S)=1/3$, $P(G)=2/3$. Find G2’s optimal strategy (parameter $p=P(C)$, $1-p=P(D)$).

Joint probabilities (independent plays): $P(S,C)=\tfrac{1}{3}p,\quad P(S,D)=\tfrac{1}{3}(1-p),\quad P(G,C)=\tfrac{2}{3}p,\quad P(G,D)=\tfrac{2}{3}(1-p).$

G2’s expected winnings (sum over the four profiles of the payoffs $v_2$ times their respective probabilities):

\bar V_2(p) &= (-2)\cdot\tfrac{1}{3}p + 3\cdot\tfrac{1}{3}(1-p) + (-1)\cdot\tfrac{2}{3}p + (-3)\cdot\tfrac{2}{3}(1-p) \\ &= -\tfrac{2}{3}p + 1 - p -\tfrac{2}{3}p - 2(1-p) \\ &= -\tfrac{7}{3}p + 1 - 2 + 2p \\ &= \tfrac{-7+6}{3}p - 1 \\ &= -1 - \tfrac{p}{3}. \end{align*}$$ **Conclusion (line decreasing in $p$).** $\bar V_2(p)=-1-p/3$ is *decreasing* in $p$: G2 minimises their loss by choosing $p=0$, that is *always Drago*. G2's optimal winnings are $\bar V_2(0)=-1$ (they always pay $1$ EUR on average).

Links

Topics: Probabilita
Concepts: Matrice di payoff · Strategia mista · Valore atteso
Methods: Strategia mista · Valore atteso
Skills: Calcolo probabilita · Modellizzare

Il più celebre gioco della teoria: due giocatori razionali, ciascuno con una strategia dominante, finiscono in un esito peggiore per entrambi rispetto a quello cooperativo.

Esempio — Strategia dominante: dilemma del prigioniero (forma classica)

Due sospettati interrogati separatamente. Ciascuno può Confessare (C) o Tacere (T). Se entrambi tacciono: $1$ anno di carcere ciascuno. Se entrambi confessano: $5$ anni. Se uno confessa e l’altro tace: chi confessa esce libero ($0$), chi tace prende $10$ anni. Payoff = $-$anni (vogliamo massimizzare):

G1 / G2	Tacere	Confessare
Tacere	$(-1;-1)$	$(-10; 0)$
Confessare	$(0;-10)$	$(-5;-5)$

Analisi delle dominanze per G1.

• Se G2 sceglie T: G1 preferisce C ($0 > -1$).
• Se G2 sceglie C: G1 preferisce C ($-5 > -10$).

Quindi C domina T per G1. Per simmetria C domina T anche per G2.

Equilibrio di Nash: entrambi confessano (C, C) con payoff $(-5;-5)$. È un equilibrio in strategie pure — ma paretianamente inefficiente: l’esito (T, T) con payoff $(-1;-1)$ sarebbe stato migliore per entrambi. Il dilemma mostra che l’equilibrio razionale individuale può portare a un esito collettivo subottimale.

Collegamenti

Argomenti: Probabilita
Concetti: Equilibrio di nash · Matrice di payoff · Strategia dominante
Metodi: Equilibrio nash · Strategia dominante
Competenze: Ragionare per casi

The most famous game in the theory: two rational players, each with a dominant strategy, end up in an outcome worse for both than the cooperative one.

Example — Dominant strategy: the prisoner's dilemma (classic form)

Two suspects interrogated separately. Each can Tacere (T, stay silent) or Confessare (C, confess). If both stay silent: $1$ year in prison each. If both confess: $5$ years. If one confesses and the other stays silent: the one who confesses goes free ($0$), the one who stays silent gets $10$ years. Payoff = $-$years (we want to maximise):

G1 / G2	Tacere	Confessare
Tacere	$(-1;-1)$	$(-10; 0)$
Confessare	$(0;-10)$	$(-5;-5)$

Dominance analysis for G1.

• If G2 chooses T: G1 prefers C ($0 > -1$).
• If G2 chooses C: G1 prefers C ($-5 > -10$).

So C dominates T for G1. By symmetry C dominates T for G2 too.

Nash equilibrium: both confess (C, C) with payoff $(-5;-5)$. It is a pure-strategy equilibrium — but Pareto inefficient: the outcome (T, T) with payoff $(-1;-1)$ would have been better for both. The dilemma shows that individually rational equilibrium can lead to a suboptimal collective outcome.

Links

Topics: Probabilita
Concepts: Equilibrio di nash · Matrice di payoff · Strategia dominante
Methods: Equilibrio nash · Strategia dominante
Skills: Ragionare per casi

Un gioco a somma zero senza equilibrio in strategie pure: l’unica scelta stabile è randomizzare in parti uguali. È il modello base dell’equilibrio in strategie miste.

Esempio — Gioco a somma zero: pari o dispari

Due giocatori mostrano simultaneamente $1$ o $2$ dita. G1 vince $1$ EUR se la somma è pari; G2 vince $1$ EUR se è dispari. Matrice di payoff (per G1):

G1 / G2	1	2
1	$+1$	$-1$
2	$-1$	$+1$

(I payoff di G2 sono gli opposti: gioco a somma zero.)

Strategie pure: nessuna dominante; nessun equilibrio in strategie pure (se G1 fissa una scelta, G2 ne deduce la propria mossa vincente).

Strategie miste: G1 gioca “1” con prob $p$, G2 con prob $q$. Vincita attesa di G1: $\bar V_1(p,q) = pq - p(1-q) - (1-p)q + (1-p)(1-q) = (2p-1)(2q-1).$ G2 sceglie $q$ per minimizzare $\bar V_1$; se $p\neq 1/2$, G2 sceglie $q$ ai limiti per spingere $\bar V_1$ negativo. La sola scelta robusta per G1 è $p=1/2$ (G1 indifferente all’avversario). Per simmetria $q=1/2$.

Equilibrio di Nash in strategie miste: entrambi giocano $1/2$-$1/2$. Vincita attesa di ciascuno: $\bar V = 0$ (gioco equo).

Collegamenti

Argomenti: Probabilita
Concetti: Equilibrio di nash · Gioco a somma zero · Strategia mista
Metodi: Equilibrio nash · Gioco somma zero · Strategia mista
Competenze: Calcolo probabilita · Modellizzare

A zero-sum game with no pure-strategy equilibrium: the only stable choice is to randomise in equal parts. It is the basic model of mixed-strategy equilibrium.

Example — Zero-sum game: odds or evens

Two players simultaneously show $1$ or $2$ fingers. G1 wins $1$ EUR if the sum is even; G2 wins $1$ EUR if it is odd. Payoff matrix (for G1):

G1 / G2	1	2
1	$+1$	$-1$
2	$-1$	$+1$

(G2’s payoffs are the opposites: zero-sum game.)

Pure strategies: none dominant; no pure-strategy equilibrium (if G1 fixes a choice, G2 deduces their own winning move).

Mixed strategies: G1 plays “1” with probability $p$, G2 with probability $q$. G1’s expected winnings: $\bar V_1(p,q) = pq - p(1-q) - (1-p)q + (1-p)(1-q) = (2p-1)(2q-1).$ G2 chooses $q$ to minimise $\bar V_1$; if $p\neq 1/2$, G2 chooses $q$ at the extremes to push $\bar V_1$ negative. The only robust choice for G1 is $p=1/2$ (G1 indifferent to the opponent). By symmetry $q=1/2$.

Mixed-strategy Nash equilibrium: both play $1/2$-$1/2$. Expected winnings of each: $\bar V = 0$ (fair game).

Links

Topics: Probabilita
Concepts: Equilibrio di nash · Gioco a somma zero · Strategia mista
Methods: Equilibrio nash · Gioco somma zero · Strategia mista
Skills: Calcolo probabilita · Modellizzare