Equilíbrio correlacionado - Correlated equilibrium

Equilíbrio correlacionado
Um conceito de solução na teoria dos jogos
Relação
Superconjunto de	equilíbrio de Nash
Significado
Proposto por	Robert Aumann
Exemplo	Frango

Na teoria dos jogos , um equilíbrio correlacionado é um conceito de solução mais geral do que o conhecido equilíbrio de Nash . Foi discutido pela primeira vez pelo matemático Robert Aumann em 1974. A ideia é que cada jogador escolha sua ação de acordo com sua observação privada do valor do mesmo sinal público. Uma estratégia atribui uma ação a cada observação possível que um jogador pode fazer. Se nenhum jogador quiser se desviar de sua estratégia (assumindo que os outros também não se desviem), a distribuição da qual os sinais são extraídos é chamada de equilíbrio correlacionado.

Definição formal

Um jogo estratégico para um jogador é caracterizado por um conjunto de ações e função de utilidade para cada jogador . Quando o jogador escolhe a estratégia e os jogadores restantes escolhem um perfil de estratégia descrito pelo -tuple , a utilidade do jogador sim . ${\ displaystyle N}$${\ displaystyle \ displaystyle (N, A_ {i}, u_ {i})}$${\ displaystyle A_ {i}}$${\ displaystyle u_ {i}}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle a_ {i} \ in A_ {i}}$${\ displaystyle N-1}$${\ displaystyle a _ {- i}}$${\ displaystyle i}$${\ displaystyle \ displaystyle u_ {i} (a_ {i}, a _ {- i})}$

Uma modificação de estratégia para o jogador é uma função . Ou seja, diz ao jogador para modificar seu comportamento, jogando a ação quando instruído a jogar . ${\ displaystyle i}$${\ displaystyle \ phi _ {i} \ dois pontos A_ {i} \ a A_ {i}}$${\ displaystyle \ phi _ {i}}$${\ displaystyle i}$${\ displaystyle \ phi _ {i} (a_ {i})}$${\ displaystyle a_ {i}}$

Deixe ser um espaço de probabilidade contável . Para cada jogador , vamos ser sua partição informações, ser 's posterior e deixe , atribuindo o mesmo valor para os estados na mesma célula de ' s partição informações. Então, é um equilíbrio correlacionado do jogo estratégico para cada jogador e para cada modificação de estratégia : ${\ displaystyle (\ Omega, \ pi)}$ ${\ displaystyle i}$${\ displaystyle P_ {i}}$${\ displaystyle q_ {i}}$${\ displaystyle i}$${\ displaystyle s_ {i} \ colon \ Omega \ rightarrow A_ {i}}$${\ displaystyle i}$${\ displaystyle ((\ Omega, \ pi), P_ {i}, s_ {i})}$${\ displaystyle (N, A_ {i}, u_ {i})}$${\ displaystyle i}$${\ displaystyle \ phi _ {i}}$

${\ displaystyle \ sum _ {\ omega \ in \ Omega} q_ {i} (\ omega) u_ {i} (s_ {i} (\ omega), s _ {- i} (\ omega)) \ geq \ sum _ {\ omega \ in \ Omega} q_ {i} (\ omega) u_ {i} \ left (\ phi _ {i} \ left (s_ {i} (\ omega) \ right), s _ {- i} (\ omega) \ right)}$

Em outras palavras, é um equilíbrio correlacionado se nenhum jogador pode melhorar sua utilidade esperada por meio de uma modificação de estratégia. ${\ displaystyle ((\ Omega, \ pi), P_ {i})}$

Um exemplo

	D são	C hicken out
D são	0, 0	7, 2
C hicken out	2, 7	6, 6
Um jogo de frango

Considere o jogo da galinha na foto. Neste jogo, dois indivíduos estão se desafiando para uma competição em que cada um pode ousar ou se acovardar . Se um vai Ousar, é melhor que o outro se acovarde. Mas se um vai acovardar, é melhor que o outro Ouse. Isso leva a uma situação interessante em que cada um quer ousar, mas apenas se o outro se acovardar.

Neste jogo, existem três equilíbrios de Nash . Os dois equilíbrios de Nash de estratégia pura são ( D , C ) e ( C , D ). Também existe um equilíbrio de estratégia mista, em que ambos os jogadores vacilam com probabilidade de 2/3.

Agora considere um terceiro (ou algum evento natural) que tira uma das três cartas rotuladas: ( C , C ), ( D , C ) e ( C , D ), com a mesma probabilidade, ou seja, probabilidade 1/3 para cada cartão. Depois de retirar a carta, o terceiro informa aos jogadores a estratégia atribuída a eles na carta (mas não a estratégia atribuída ao oponente). Suponha que um jogador seja atribuído a D , ele não gostaria de se desviar supondo que o outro jogador jogou sua estratégia atribuída, uma vez que receberá 7 (o maior pagamento possível). Suponha que um jogador é atribuído C . Então, o outro jogador jogará C com probabilidade 1/2 e D com probabilidade 1/2. A utilidade esperada de Daring é 7 (1/2) + 0 (1/2) = 3,5 e a utilidade esperada de acovardar é 2 (1/2) + 6 (1/2) = 4. Assim, o jogador iria prefere amaldiçoar.

Como nenhum dos jogadores tem incentivo para se desviar, esse é um equilíbrio correlacionado. O payoff esperado para este equilíbrio é 7 (1/3) + 2 (1/3) + 6 (1/3) = 5, que é maior do que o payoff esperado do equilíbrio de Nash de estratégia mista.

O seguinte equilíbrio correlacionado tem uma recompensa ainda maior para ambos os jogadores: Recomendar ( C , C ) com probabilidade 1/2 e ( D , C ) e ( C , D ) com probabilidade 1/4 cada. Então, quando um jogador é recomendado para jogar C , ele sabe que o outro jogador vai jogar D com probabilidade (condicional) 1/3 e C com probabilidade 2/3, e obtém o retorno esperado 14/3, que é igual a (não menos que) o retorno esperado quando ela interpreta D . Nesse equilíbrio correlacionado, ambos os jogadores obtêm 5,25 na expectativa. Pode-se mostrar que este é o equilíbrio correlacionado com a soma máxima dos payoffs esperados para os dois jogadores.

Aprendendo equilíbrios correlacionados

Uma das vantagens dos equilíbrios correlacionados é que eles são computacionalmente menos caros do que os equilíbrios de Nash . Isso pode ser capturado pelo fato de que o cálculo de um equilíbrio correlacionado requer apenas a resolução de um programa linear, ao passo que a resolução de um equilíbrio de Nash requer encontrar seu ponto fixo completamente. Outra maneira de ver isso é que é possível que dois jogadores respondam às jogadas históricas de um jogo um do outro e acabem convergindo para um equilíbrio correlacionado.

Referências

Origens