Jogos de Estratégia

    Nesta aplicação vamos utilizar notação matricial e produto entre matrizes para encontrar a melhor estratégia para cada jogador em um jogo, no qual cada oponente tem que escolher um de seus movimentos a cada jogada e, dependendo das escolhas, cada um receberá um determinado pagamento.

    Definição: Um jogo de matriz de dois jogadores com soma zero é um tipo de jogo no qual cada jogador tem um número finito de possíveis movimentos, de modo que podemos arranjar os possíveis movimentos e os correspondentes ganhos ou perdas de cada jogador em uma tabela ou matriz de pagamentos, que é conhecida pelos dois jogadores. O termo soma zero significa que, a cada jogada, o ganho de um jogador é igual a perda do outro.
    Neste tipo de jogo, a cada rodada, cada um dos jogadores escolhe, aleatória ou estrategicamente, um entre seus possíveis movimentos, sem que o outro jogador saiba sua escolha. Uma vez tomadas as decisões, elas são anunciadas e a tabela de pagamentos é utilizada para determinar a compensação de um jogador ao outro. Essa compensação não precisa ser em dinheiro, mas em qualquer espécie de bem consumível que possa assumir um valor numérico.

    Exemplo: A tabela abaixo representa um jogo de matriz de dois jogadores com soma zero. Nesta notação, os valores da tabela representam os pagamentos do jogador Y para o jogador X. Se a entrada na tabela for negativa, o pagamento será do jogador X para o jogador Y.

---

    Em um jogo como o descrito acima, se os movimentos dos jogadores são escolhidos aleatoriamente, o jogo depende da sorte. Mas, se os jogadores puderem decidir o movimento a se fazer, então cada um tentará usar a melhor estratégia para maximizar os seu ganhos ou minimizar suas perdas.
 
    Considere um jogo de matriz de dois jogadores com soma zero. Seja m o número de possíveis movimentos do jogador X e $n$ o número de possíveis movimentos do jogador Y. Se o jogador X faz o movimento $i$, para $i=1, 2, ..., m$, e o jogador Y faz o movimento $j$, para $j=1, 2, ..., n$, então $a_{ij}$ é o pagamento do jogador Y para o jogador X. Caso $a_{ij}$ seja negativa, então o pagamento é do jogador X para o jogador Y. Podemos arranjar esses mn possíveis pagamentos em uma matriz $m \times n$.

$$A = \left[ \begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{array} \right]$$
$A$ é denotada matriz de pagamento do jogo.

    Suponhamos que cada jogador tem uma certa probabilidade de fazer cada movimento. Sejam:
       
        $p_i$ = probabilidade do jogador X fazer o movimento $i \;(i = 1, ..., m)$.
        $q_j$ = probabilidade do jogador Y fazer o movimento $j \; (j = 1, ..., n)$.

    Com as probabilidades $p_i$ e $q_j$ nós formamos dois vetores:
  $$p = \left[ \begin{array}{cccc} p_1 & p_2 & \dots & p_m \end{array}\right]\;\;\;\;\;\; e \;\;\;\;\;\; q = \left[ \begin{array}{c} q_1 \\ q_2 \\ \vdots \\ q_n \end{array}\right]$$

    O vetor $p$ é a estratégia do jogador X e o vetor $q$ é a estratégia do jogador Y. Se $p_i$ é a probabilidade do jogador X fazer o movimento $i$ e $q_j$ a probabilidade do jogador Y fazer o movimento $j$, então, da teoria de probabilidade, $p_iq_j$ é a probabilidade, em uma rodada do jogo, de acontecer os movimentos $i$ e $j$, dos jogadores X e Y, respectivamente. O pagamento recebido pelo jogador X para esse par de movimentos é $a_{ij}$. Multiplicando cada possível pagamento com a probabilidade associada e somando sobre todos os pagamentos possíveis, obtemos:

$$E(p,q) = a_{11}p_1q_1 + a_{12}p_1q_2 + ... + a_{1n}p_1q_n + a_{21}p_2q_1 + a_{22}p_2q_2 + ... + a_{mn}p_mq_n$$
    Essa expressão é uma média ponderada dos pagamentos para o jogador X, chamada pagamento esperado. A denotação $E(p,q)$ indica que seu valor depende tanto das estratégias do jogador X, quanto do jogador Y. Podemos mostrar que, se o jogo é jogado muitas vezes, o pagamento médio recebido pelo jogador X é $E(p, q)$. Da maneira como foi definido, temos:

$$E(p,q) = pAq = \left[ \begin{array}{cccc} p_1 & p_2 & \dots & p_m \end{array}\right] \; \left[ \begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{array} \right] \; \left[ \begin{array}{c} q_1 \\ q_2 \\ \vdots \\ q_n \end{array}\right]$$
    $E(p, q)$ é o pagamento esperado para o jogador X e $-E(p,q)$ é o pagamento esperado para o jogador Y.

    Suponha agora, que cada jogador pode escolher suas estratégias, ou seja, alterar as probabilidades de cada um dos seus possíveis movimentos, sem que o outro jogador saiba a sua estratégia.
    Cada jogador irá tentar escolher a melhor estratégia, sabendo que o outro também o fará. Assim, o jogador X escolhe uma estratégia $p$ tal que $E(p, q)$ é máximo, para a melhor estratégia $q$ escolhida pelo jogador Y. De mesmo modo, o jogador Y escolhe uma estratégia $q$ tal que $E(p,q)$ é mínimo, para a melhor estratégia $p$ escolhida pelo jogador X.

    Teorema:  Existem estratégias $p^*$ e $q^*$ tais que:
    $$E(p^*, q) \geq E(p^*, q^*) \geq E(p, q^*)$$
para quaisquer estratégias $p$ e $$.

   As estratégias $p^*$ e $q^*$ são as melhores estratégias para os jogadores X e Y, respectivamente, chamadas estratégias ótimas. O pagamento esperado $E(p^*, q^*)$ é chamado valor do jogo, obtido quando ambos os jogadores utilizam quaisquer estratégias ótimas.

    Definição: Seja A uma matriz. Uma entrada $a_{rs}$ da matriz A é um ponto de sela, se
        $(i)\; a_{rs}$ é a menor entrada de sua linha e
        $(ii)\; a_{rs}$ é a maior entrada de sua coluna.

    Um jogo em que a matriz de pagamento possui um ponto de sela é chamado estritamente determinado.

    Uma estratégia ótima para o jogador X seria escolher um movimento que maximize o seu menor ganho, caso o jogador Y faça uma estratégia ótima. Agora, uma estratégia ótima para o jogador Y é escolher o movimento que minimize sua maior perda, caso o jogador X faça uma estratégia ótima. Disso, vemos que um ponto de sela da matriz de pagamento de um jogo é um ponto ótimo, ou seja, se $a_{rs}$ é um ponto de sela da matriz de pagamento do jogo, então, escolher sempre o movimento $r$ é uma estratégia ótima para o jogador X e escolher sempre o movimento $s$ é uma estratégia ótima para o jogador Y.

    Exemplo: Duas emissoras de televisão, X e Y, pretendem exibir programas em um mesmo horário. Elas podem escolher entre 4 programas cada uma, sendo que as emissora não sabem o que cada uma irá exibir. Uma pesquisa, feita por ambas as emissoras, revelou quais seriam as probabilidades de audiência para a emissora X, com cada uma das possíveis combinações dos dois programas exibidos. A seguinte matriz mostra o resultado da pesquisa, onde a entrada $a_{ij}$ representa a porcentagem de audiência que a emissora X terá, caso ela exiba o programa $i$ e a emissora Y exiba o programa $j$.

$$A = \left[ \begin{array}{cccc} 30 & 45 & 20 & 35 \\ 60 & 70 & 25 & 30 \\ 35 & 60 & 30 & 40 \\ 45 & 40 & 25 & 60 \end{array}\right]$$
    Assim, por exemplo, se a emissora X decide exibir o programa 2 e a emissora Y decide exibir seu programa 1, então, 60% da audiência será da emissora X e 40% da emissora Y.

    Esse é um exemplo de um jogo de matriz de dois jogadores com soma zero, onde os jogadores são as emissoras de TV. Se esse jogo é estritamente determinado, então a matriz A de pagamento do jogo tem um ponto de sela.
    Observe que a entrada $a_{33} = 30$ é um ponto de sela da matriz A, pois é o maior valor de sua coluna e o menor de sua linha. Assim, uma estratégia ótima para a emissora X é exibir o programa 3 e para a emissora Y é exibir o programa 3. Isso dará uma audiência de 30% para a emissora X e 70% para a emissora Y.

    É estranho que essa seja uma estratégia ótima para X, pois é claro que outras entradas da matriz dariam uma maior audiência para ela, mas observe que isso depende também da escolha da emissora Y. Se por acaso, a emissora X exibe seu programa 2, as possibilidades são que ela tenha 60%, 70%, 25% ou 30% de audiência, se Y exibir os programas 1, 2, 3 ou 4, respectivamente. Assim, o pior para a emissora X seria se a Y escolhesse o programa 3, o que daria apenas 25% de audiência para X. Agora, se a emissora X escolhe exibir seu programa 3, então o pior seria se a emissora Y escolhesse o programa 3, o que daria 30% de audiência para X. Observe que, a audiência no pior caso para a emissora X, se ela escolher um outro programa que não seja o 3, é sempre menor que 30%.
    A estratégia ótima da emissora X é analisar os possíveis casos, supondo que a Y vai escolher o que é mais vantajoso para ela. Ou seja, suponha que a emissora Y sempre escolhe o seu programa que dará a menor audiência para X. Analisando a matriz A, essas menores audiências serão 20%, 25%, 30% ou 25%, caso X escolha os programas 1,2,3 ou 4, respectivamente. Então, a melhor escolha para X é aquela em que a sua menor audiência é máxima, dentre as 4 menores audiências possíveis, ou seja, escolher o programa 3, que lhe dará 30% de audiência.
    Por outro lado, a emissora Y analisa suas escolhas, observando os maiores valores em cada coluna de A, ou seja, fixando a sua escolha e supondo que X escolherá o programa que lhe dará a maior audiência. Analisando a matriz A, os possíveis casos seriam 60%, 70%, 30% ou 60% de audiência para X, se Y escolher os programas 1,2,3 ou 4, respectivamente. O melhor caso para Y, então, é escolher o programa 3, que dará 30% de audiência para X e 70% para Y.
    Em resumo, a estratégia ótima para X é escolher a linha da matriz A, cuja menor entrada é a maior possível, dentre as menores entradas de cada linha e a estratégia ótima para Y é escolher a coluna, cuja maior entrada é a menor possível, dentre as maiores entradas de cada coluna. Por esse motivo, um ponto de sela da matriz A ocorre quando ambos os jogadores escolhem estratégias ótimas.

    Voltar ao Topo.

---

    Considere um jogo de matriz de dois jogadores com soma zero, em que a matriz de pagamento é uma matriz $2 \times 2$.

$$A = \left[ \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right]$$
    Este é um caso em que podemos encontrar estratégias ótimas, mesmo que o jogo não seja estritamente determinado, ou seja, que a matriz $A$ não tenha um ponto de sela.
    Vamos calcular o pagamento esperado para duas estratégias quaisquer p e q, dos jogadores X e Y, respectivamente.

$$E(p,q) = pAq = \left[ \begin{array}{cc} p_1 & p_2 \end{array}\right] \; \left[ \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right] \; \left[ \begin{array}{c} q_1 \\ q_2 \end{array}\right] \Longrightarrow$$
$$\Longrightarrow E(p,q) = a_{11}p_1q_1 + a_{12}p_1q_2 + a_{21}p_2q_1 + a_{22}p_2q_2$$
    Sabemos que a soma de todas as probabilidades possíveis deve ser 1. Assim, $p_1 + p_2 = 1 \Longrightarrow p_2 = 1 - p_1$ e $q_1 + q_2 = 1 \Longrightarrow q_2 = 1 - q_1$. Substituindo essas relações na expressão para $E(p,q)$, obtemos:

$$E(p,q) = a_{11}p_1q_1 + a_{12}p_1(1 - q_1) + a_{21}(1 - p_1)q_1 + a_{22}(1-p_1)(1-q_1) \Longrightarrow$$
$$\Longrightarrow E(p,q) = [(a_{11} + a_{22} - a_{12} - a_{21})p_1 - (a_{22} - a_{21})]q_1 + (a_{12} - a_{22})p_1 + a_{22}$$
    Na última passagem, rearranjamos a equação para colocar em evidência os termos com $q_1$. Se substituirmos:

$$p_1 = p_1^* = \frac{a_{22} - a_{21}}{a_{11} + a_{22} - a_{12} - a_{21}}$$
    O coeficiente do termo com $q_1$ se anula e o pagamento esperado se reduz a:

$$E(p^*,q) = \frac{a_{11}a_{22} - a_{12}a_{21}}{a_{11} + a_{22} - a_{12} - a_{21}}$$
    Esse pagamento esperado não depende da estratégia $q$ do jogador Y, e portanto, a estratégia $p^*$ é ótima para o jogador X. De mesma forma, podemos verificar que uma estratégia ótima para o jogador Y é determinada por:

$$q_1 = q_1^* = \frac{a_{22} - a_{21}}{a_{11} + a_{22} - a_{12} - a_{21}}$$
    Que substituindo na equação para o pagamento esperado, resulta em:

$$E(p,q^*) = \frac{a_{11}a_{22} - a_{12}a_{21}}{a_{11} + a_{22} - a_{12} - a_{21}}$$
    Isso mostra que $E(p^*,q) = E(p^*,q^*) = E(p,q^*)$, para quaisquer estratégias $p$ e $q$. As estratégias $p^* = [p_1^* \;\; 1-p_1^*]$ e $q^* = [q_1^* \;\; 1-q_1^*]$ são ótimas para os jogadores X e Y, respectivamente. Neste caso, o valor do jogo é:

$$E(p^*, q^*) = \frac{a_{11}a_{22} - a_{12}a_{21}}{a_{11} + a_{22} - a_{12} - a_{21}}$$
    Ou seja, cada jogador, se escolher uma estratégia ótima, pode forçar o valor do jogo a ser o pagamento esperado, qualquer que seja a estratégia escolhida pelo outro jogador. Isso só é valido para jogos em que a matriz de pagamento é $2 \times 2$.

    Exemplo: Considere um jogo de matriz com soma zero, em que dois jogadores X e Y devem escolher um entre dois de seus movimentos. O jogo tem a seguinte matriz de pagamento para o jogador X:

$$A = \left[ \begin{array}{cc} 5 & 7 \\ 6 & -2 \end{array}\right]$$
    A matriz $A$ não tem um ponto de sela, logo o jogo não é estritamente determinado. Como visto anteriormente, uma estratégia ótima para o jogador X é $p^* = [p_1^* \;\; p_2^*]$, onde:

$$p_1^* = \frac{a_{22} - a_{21}}{a_{11} + a_{22} - a_{12} - a_{21}} = \frac{-2 - 6}{5 - 2 - 7 - 6} = \frac{-8}{-10} = \frac{4}{5}$$
$$p_2^* = 1 - p_1^* = 1 - \frac{4}{5} = \frac{1}{5}$$
    O valor do jogo nesse caso, para qualquer estratégia q do jogador Y, será:

$$E(p^*, q) = \frac{a_{11}a_{22} - a_{12}a_{21}}{a_{11} + a_{22} - a_{12} - a_{21}} = \frac{(5)(-2) - (7)(6)}{5 - 2 - 7 - 6} = \frac{-52}{-10} = 5,2$$
    Ou seja, uma estratégia ótima para o jogador X é escolher em $\frac{4}{5}$ das jogadas o seu movimento 1 e $\frac{1}{5}$ das vezes o seu movimento 2, isso lhe garantirá uma média de $5,2$ em dinheiro, ou outra unidade de pagamento, por rodada do jogo, qualquer que seja a estratégia $q$ escolhida pelo jogador Y.


    Voltar ao Topo.