Uma Mente Brilhante - John Nash e uma loura entram num bar...
Bem... segundo o filme, o John Nash já estava no bar quando a loura entrou. Mas nem isto é uma anedota de bar, nem o rigor da história é importante. Esta página é uma introdução ao Equilíbrio de Nash, inspirada numa cena do filme Uma Mente Brilhante.
O problema - quem convidar para dançar?
Eis uma cena do filme onde se dá uma descrição da intuição por trás do Equilíbrio de Nash. Nunca bebi umas cervejas com Nash, não sei da veracidade da história, claro. Duvido que seja certa pois, tanto quanto a entenda, a explicação no filme está errada. No filme a solução sugerida é cooperativa, o Equilíbrio de Nash é para um jogo não cooperativo, ou seja é uma visão melhorada sobre a competição. Ainda assim, se o leitor/a quiser ver o vídeo, compensa, para visualizar o problema.
Há que definir o "jogo" de forma rigorosa.
Num bar temos 5 homens que vão tentar cada um encontrar uma parceira de dança para a noite. A única forma de um determinado homem ficar com a parceira que convidar é se for o único a convidá-la (sim, as mulheres neste jogo são completamente passivas, um "jogo" real seria bem mais complexo). O emparelhamento é feito numa única ronda, quem não tenha par na primeira tentativa fica sem par. Todos os homens têm preferência por uma das mulheres, "a loura", as restantes mulheres são alternativas válidas e iguais entre si.
No filme alguns dos homens afirmam que segundo Adam Smith se obterá o melhor resultado possível se for "cada um por si". Ora o que o Nash do filme explica, e bem, é que se cada homem apostar na sua escolha preferida ("a loura") o resultado é que cada um deles ficará sem parceira. Uma estratégia que resulta em zero emparelhamentos é o pior resultado possível, que a estratégia ideal resulte no pior resultado possível não parece. Vamos ignorar a solução cooperativa dada no filme e procurar uma melhor estratégia, que ainda seja competitiva. Adam Smith não afirmou que se deve ser o mais egoísta possível,1 o problema não está em cada homem querer o melhor para si.
A intuição básica por trás do equilíbrio de Nash está em que, num jogo não cooperativo, cada um deve deve procurar o seu interesse pessoal tendo em conta que os outros fazem o mesmo. O erro na estratégia simples, de tentar a loura, está em não contar com as estratégias dos concorrentes. Como pode então cada homem maximizar a sua probabilidade de ter parceira de dança, e preferencialmente a loura, sabendo que os outros têm exatamente o mesmo objetivo?
Já vimos que apostarem todos em convidar a loura resulta numa certeza de fracasso para cada um. Mas a estratégia ideal também não será de ignorar por completo a loura. Porquê? Porque se "os outros" não a convidam, então "eu" convido, sou o único e tenho-a por parceira de dança. Ora, se escolher a loura não é a melhor estratégia mas não escolher a loura também não é, o que sobra? Sobra cada um definir uma certa probabilidade de convidar a loura e cada uma das outras. Fazer um sorteio e convidar aquela que a sorte lhe dite. Esta família de estratégias inclui as anteriores mas potencialmente pode ser melhor que qualquer das outras duas. Qualquer que seja a parceira que a sorte "me" dite convidar - incluindo a loura! - talvez "eu" seja o único a convidá-la. Portanto, em termos de probabilidade de ter sucesso em convidar a loura esta é uma melhor estratégia, com esta estratégia talvez tenha sucesso ao convidar a loura (ou outra das mulheres), o que é melhor que o insucesso garantido das duas estratégias anteriores.
Tentemos formalizar esta ideia.
Formalização
Uma estratégia é então não uma decisão concreta ("convidar a loura") mas um conjunto de probabilidades de convidar cada uma das mulheres. A esta estratégia "probabilística" chama-se estratégia mista. Para {$N=5$} homens, e mulheres, a candidata a estratégia ideal é então uma lista ordenada de probabilidades: {$\mathbf{p}=(p_1, p_2, p_3, p_4, p_5)$}, em que {$p_1$} é a probabilidade de convidar a 1ª mulher (p.ex. a loura) e {$p_i, i=2,\dotsc,N$} a probabilidade de convidar cada uma das outras. Supondo que esta é a estratégia ideal, então todos os homens a vão usar.
É necessário quantificar a preferência dos homens para a poder incluir na determinação da estratégia. Para isso vamos usar uma lista ordenada de utilidades (no sentido usual em economia) de ficar com cada parceira: {$\mathbf{u}=(u_1, u_2, u_3, u_4, u_5)$}, em que {$u_1$} é a utilidade de dançar com a 1ª mulher e assim sucessivamente. Vamos igualmente supor que as preferências são iguais para todos os homens. Num caso como este a quantificação da "utilidade" é muito subjetiva, para efeito ilustrativo vamos considerar que a utilidade da primeira escolha é o dobro das outras e representar isso com {$\mathbf{u}=(2, 1, 1, 1, 1)$}.
Ainda que se presuma que a estratégia usada será a mesma por todos, temos de analisar o jogo do ponto de vista de cada jogador, pois a premissa é de que cada jogador pretende maximizar a utilidade para si. Sendo todos os jogadores iguais, basta indicar que o jogador em foco tem a estratégia {$\mathbf{q}=(q_1, q_2, q_3, q_4, q_5)$}. Qual a utilidade esperada, {$u_q$}, para este jogador? Se convidar a mulher 1, com probabilidade {$p_1$}, será bem sucedido, com utilidade {$u_1=2$}, se e só se nenhum dos outros {$N-1=4$} homens convidar a mesma mulher, o que tem probabilidade {$(1-p_1)^4$} de suceder. A utilidade esperada deste caso é assim {$u_1 q_1 (1-p_1)^4$}. O raciocínio é idêntico para todas os restantes casos, pelo que a utilidade esperada total é a soma dessas parcelas: {$$ \tag{1} u = \sum_{i=1}^5{u_i q_i (1-p_i)^4}$$}
As probabilidades não são independentes pois a sua soma tem de ser um, {$\sum_i{q_i}=1$}, {$\sum_i{p_i}=1$} Destacando por exemplo a quinta parcela, {$q_5$}, obtemos, {$q_5=1-\sum_{i=1}^4{q_i}$}, {$p_5=1-\sum_{i=1}^4{p_i}$}, que substituindo em (1) resulta em: {$$ \tag{2} u = \sum_{i=1}^4{u_i q_i (1-p_i)^4} + u_5 \left(1-\sum_{i=1}^4{q_i}\right) \left(\sum_{i=1}^4{p_i}\right)^4$$}
O máximo do valor esperado será no ponto onde as derivadas de {$u$} se anulem, ou seja, "basta" resolver as equações: {$$ \tag{3}\frac{du}{dq_i}=0 \iff u_i(1-p_i)^4-u_5\left(\sum_{j=1}^4{p_j}\right)^4=0,\,i=1,\dotsc,4$$}
Um facto que poderá ser surpreendente é que ao tentar estabelecer equações para maximizar a utilidade para um jogador em foco, com estratégia {$\mathbf{q}$}, obtivémos equações apenas nas variáveis da estratégia {$\mathbf{p}$} dos "outros" jogadores! Formalmente isso não é um problema, pois por hipótese todos os jogadores usarão a mesma estratégia, logo determinar uma ou a outra é indiferente. Notemos que com todos os jogadores a tentarem maximizar a sua utilidade usando uma estratégia ideal, de facto é impossível obter vantagem - por o jogo ser simétrico - o mais que conseguem fazer é ter uma estratégia que impede qualquer um outro jogador de ter vantagem em jogar diferente.
Note-se que as equações (3) são quatro equações polinomiais em quatro variáveis pelo que se esperam {$4^4=256$} soluções! Antes de nos preocuparmos com isso, revisitemos o problema, para o escrever de forma um pouco mais genérica. Para generalizar para {$N$} jogadores basta notar que em cada parcela da utilidade esperada (1) apenas se altera a probabilidade de todos os outros não convidarem a mulher {$i$} para {$(1-p_i)^{N-1}$}, pelo que a utilidade fica: {$$ \tag{4} u = \sum_{i=1}^N{u_i q_i (1-p_i)^{N-1}}$$} Notamos ainda que as normalizações, {$\sum_i{q_i}=1$} e {$\sum_i{p_i}=1$}, podem ser feitas extraindo qualquer um dos termos, não necessariamente o último. Assim, para {$k$} qualquer tem-se {$q_k=1-\sum_{i\ne k}{q_i}$}, {$p_k=1-\sum_{i \ne k}{p_i}$}, que substituindo em (4) resulta em: {$$ \tag{5} u = \sum_{i \ne k}{u_i q_i (1-p_i)^{N-1}} + u_k \left(1-\sum_{i \ne k}{q_i}\right) \left(\sum_{i \ne k}{p_i}\right)^{N-1}$$}
As equações a resolver, do anulamento das derivadas, são então: {$$ \tag{6}\frac{du}{dq_i}=0 \iff u_i(1-p_i)^{N-1}-u_k\left(\sum_{j \ne k}{p_j}\right)^{N-1}=0,\,i=1,\dotsc,N,\,i \ne k$$}
Resolução
Neste ponto incentivo o leitor a voltar ao início e, como exercício, refazer as equações para o caso {$N=2$}, para o qual a estratégia ótima resultante é {$\mathbf{p}=(\frac{u_1}{u_1+u_2}, \frac{1}{u_1+u_2})=(\frac23,\frac13)$}.
A segunda parcela de todas as equações (6) é a mesma, o que permite dizer que para dois valores de {$i$} diferentes, se tem {$\frac{du}{dq_i}=0=\frac{du}{dq_j}$} {$\iff$} {$u_i(1-p_i)^{N-1}-u_k\left(\sum_{m \ne k}{p_m}\right)^{N-1}$} {$=$} {$u_j(1-p_j)^{N-1}-u_k\left(\sum_{m \ne k}{p_m}\right)^{N-1}$} {$\iff$} {$u_i(1-p_i)^{N-1}=u_j(1-p_j)^{N-1}$}.
Note-se que tendo-se cancelado a dependência em {$k$} e por generalidade de {$k$} nas equações (6), esta relação é válida para todo {$i,j=1,\dotsc,N$}. Daqui resulta {$u_i(1-p_i)^{N-1}=u_j(1-p_j)^{N-1}$} {$\iff$} {$u_i^{\frac{1}{N-1}}(1-p_i)=u_j^{\frac{1}{N-1}}(1-p_j)$}
Definindo uma "utilidade relativa" como {$\xi_{ij}=\frac{u_i^{\frac{1}{N-1}}}{u_j^{\frac{1}{N-1}}}$}, obtemos {$u_i^{\frac{1}{N-1}}(1-p_i)=u_j^{\frac{1}{N-1}}(1-p_j)$} {$\iff$} {$(1-p_i)=\xi_{ji}(1-p_j)$} {$\iff$} {$$ \tag{7} p_i=1-\xi_{ji}(1-p_j)$$}
Exprimindo todas as probabilidades em função de uma delas, {$p_n$}, e usando a normalização obtemos: {$\sum_i{pi}=1$} {$\iff$} {$\sum_i{1-\xi_{ni}(1-p_n)}=1$} {$\iff$} {$N - (1-p_n) \sum_i{\xi_{ni}}=1$} {$\iff$} {$$ \tag{8}p_n = 1- \frac{N-1}{\sum_i{\xi_{ni}}}$$}
Por generalidade da escolha de {$n$} esta solução é válida para qualquer {$n=1,\dots,N$}, pelo que obtivemos uma solução geral para a estratégia ideal, em função das utilidades de cada escolha.
Alguns casos particulares
Voltemos à utilidade em que se dá preferência à primeira escolha, e as restantes são tidas por idênticas, {$\mathbf{u}=(2, 1, 1, 1, \dotsc)$}. Temos {$\xi_{1i}=\sqrt[N-1]{2},\,i \ne 1$} e {$\xi_{ii}=1$}. Logo {$\sum_i{\xi_{1i}}$} {$=$} {$\xi_{11}+\sum_{i\ge2}{\xi_{1i}}$} {$=$} {$1+(N-1)\sqrt[N-1]{2}$}. Logo {$$p_1 = 1- \frac{N-1}{1+(N-1)\sqrt[N-1]{2}}$$} As restantes probabilidade têm de ser todas iguais, logo, por normalização {$p_1+(N-1)p_n = 1$} {$\iff$} {$$p_n = \frac{1}{1+(N-1)\sqrt[N-1]{2}},\,n \ge 2$$}
Para o caso de Nash e seus quatro amigos, resulta {$p_1(5)=1-\frac{4}{1+2^\frac94}\approx 0.305$} e {$p_n(5)=\frac{1}{1+2^\frac94}\approx 0.174,\,n \ge 2$}. Note-se que a probabilidade de apostar em convidar a loura é menor que o dobro das outras, ao contrário do caso com apenas dois jogadores. De facto a probabilidade relativa de apostar na primeira escolha {$\left\lbrace \frac{p_1(N)}{p_n(N)} \right\rbrace_{N \ge 2}$} é estritamente decrescente, com {$\lim_N{\frac{p_1(N)}{p_n(N)}} = 1 + \log{2} \approx 1.69$}.
Leituras
- Nash Jr., John F., "Equilibrium points in n-person games", 1950 - o artigo original de Nash. Bem mais breve que esta página!...
1 Creio que Adam Smith também não afirmou que "cada um por si" é a melhor estratégia para a sociedade, essa será uma interpretação simplista posterior. De certa forma tal como os homens desta história interpretaram mal a procura do interesse pessoal. Mas essa é outra história. ⇑