Separação entre equilíbrios correlatos grosseiros e equilíbrios correlatos

16

Estou procurando exemplos de técnicas para provar os limites dos preços da anarquia que têm o poder de separar o preço da anarquia sobre equilíbrios correlatos grosseiros (o conjunto limitador da dinâmica de não-arrependimento externo) do preço da anarquia sobre os equilíbrios correlatos (os limites conjunto de dinâmicas sem troca-arrependimento). As separações naturais desse tipo são conhecidas?

Uma obstrução para separar essas duas classes é que a maneira mais natural (e comum) de provar o preço dos limites da anarquia é observar apenas que, em equilíbrio, nenhum jogador tem qualquer incentivo para se desviar de sua ação no OPT e, de alguma forma, usar isso conectar o bem-estar social em alguma configuração ao bem-estar social do OPT. Infelizmente, qualquer prova de que o preço da anarquia sobre os equilíbrios correlatos grosseiros é pequeno, que considera apenas os desvios de cada jogador em uma única ação alternativa (digamos, a ação da OPT) também vale para os equilíbrios correlatos e, portanto, não pode fornecer uma separação. Isso ocorre porque a única diferença entre um equilíbrio correlato grosso e um equilíbrio correlato é a capacidade de um jogador em um equilíbrio correlacionado considerar simultaneamentedesvios múltiplos , condicionados ao sinal do perfil lúdico extraído da distribuição de equilíbrio.

Essas separações são conhecidas?

Aaron Roth
fonte

Respostas:

7

Corrija M >> 1 >> e observe o seguinte jogo de coordenação de dois jogadores (ambos os jogadores têm o mesmo utilitário):

M   | 1+e  | 2e   |  e

1+e |  1   |  e   |  0

2e  |  e   |  M   | 1+e

e   |  0   | 1+e  | 1

A segunda e a quarta linha e coluna são estritamente dominadas, de modo que qualquer equilíbrio correlacionado não pode tê-las em seu suporte, portanto, seria no sub-jogo:

M  |  2e

2e |  M

para o qual todo equilíbrio correlacionado daria a cada jogador mais do que M / 2 de utilidade.

Por outro lado, considere a distribuição de probabilidade conjunta, fornecendo probabilidade 1/2 para cada um dos 1s e, portanto, utilidade 1 para cada jogador. A alegação é que este é um equilíbrio grosseiro. Em um equilíbrio aproximado, os possíveis desvios do jogador da linha são para uma das estratégias puras, independentemente do resultado da distribuição conjunta. Agora, se apenas se souber que o player da coluna está misturando uniformemente entre a 2ª e a 4ª coluna, o utilitário máximo que o player de linha pode obter é 0,5 + e <1, portanto, o desvio não é lucrativo.

Noam
fonte