Fontes para a teoria algorítmica evolutiva dos jogos

Eu uso o termo do título em um sentido muito amplo.

Há uma quantidade significativa de trabalho sobre a teoria dos jogos evolucionários, incluindo seus fundamentos matemáticos. Fui recomendado "Jogos Evolucionários e Dinâmica de População", mas ainda não o mergulhei.

Há também uma quantidade significativa de trabalho sobre a teoria algorítmica dos jogos, que é um tópico popular neste site.

O que eu gostaria de ver é um trabalho que faz declarações de complexidade ou convergência computacional sobre determinadas dinâmicas evolutivas.

Exemplos (redigidos muito livremente):

1. Dada uma população e um esquema evolutivo, podemos dar um arrependimento probabilístico à otimização da população a longo prazo (comparada ao melhor indivíduo produzido?). Isso parece estar fortemente relacionado a conjuntos de especialistas e problemas de bandidos. E nas configurações não estacionárias?
2. Dado um conjunto de populações de espécies diferentes que interagem em seu ambiente, jogando praticamente qualquer tipo de jogo com vários jogadores, que afirmações podemos fazer sobre a eventual estabilidade de suas estratégias ou distribuição de estratégias, dadas suas estratégias evolutivas.
3. Em qualquer tipo de ambiente com muitos "nichos" (uma maneira abrangente de expressar isso, eu entendo), seja em termos de relacionamento direto com o meio ambiente ou em termos de relacionamento com outras espécies, que afirmações podemos fazer sobre como as populações irão distribuir através desses nichos.
4. Qualquer problema que eu não tenha perguntado, mas deveria - estou abordando isso com pouco AGT, TCS, algoritmos genéticos, teoria dos jogos evolucionários ou formação em biologia da população; Estou fazendo minhas perguntas de um ponto de vista de otimização / aprendizado de máquina / estatísticas, que pode estar errado ou incompleto.

Este é um dos tópicos em que tenho procurado conexões há algum tempo. No entanto, eles não parecem todos os predominantes. As pessoas que trabalham com biologia e economia teóricas que usam EGT geralmente aderem à teoria de sistemas dinâmicos e não usam a lente algorítmica. Assim, a maioria dos resultados é do estilo AMath / Física, e não dos algoritmos e do estilo matemático discreto. Se você deseja seguir a abordagem de sistemas dinâmicos, há uma pesquisa de Hofbauer e Sigmund que é mais curta e mais recente que o livro deles (mencionei isso e alguns comentários positivos em uma resposta anterior) ).

Um dos locais em que a dinâmica do replicador tem sido usada em resultados relacionados à complexidade é Marcello Pelillo e co-autores como uma heurística para resolver o max-clique (reduza o max-clique à programação quadrática, resolve a programação quadrática usando a dinâmica do replicador como sua heurística) :

[1] Immanuel M. Bomze e Marcello Pelillo [2000]. "Aproximando o clique de peso máximo usando a dinâmica do replicador." Transações IEEE em redes neurais 11 (6)

[2] Marcello Pelillo e Andrea Torsello [2006]. "Dinâmica de jogo payoff-monotônico e o problema de clique máximo". Neural Computation 18: 1215-1258.

$\Sigma^P_2$$\Sigma^P_2$

[3] Kousha Etessami e Andreas Lochbihler [2008] "A complexidade computacional das estratégias evolutivamente estáveis". Revista Internacional de Teoria dos Jogos , 37 (1): 93-113. (Disponível pela primeira vez em 2004 como relatório técnico da ECCC TR04-055).

[4] Vincent Conitzer [2013] "A complexidade computacional exata das estratégias evolutivamente estáveis". 9ª Conferência sobre Economia da Web e Internet (WINE) . ( pdf ).

Atualmente, muitas das perguntas interessantes do EGT são sobre jogos em gráficos e, embora existam alguns resultados interessantes do sistema dinâmico, como (veja também esta pergunta para extensões dessa abordagem):

[5] Hisashi Ohtsuki e Martin Nowak [2006] "A equação do replicador em gráficos". _ Revista de Biologia Teórica_, 243 (1), 86-97 ( link , publicação no blog )

A maior parte do trabalho passa pela modelagem baseada em agentes (consulte esta resposta para obter um contexto de modelagem de propagação de doenças). Esses modelos geralmente são muito mais receptivos às declarações de complexidade e convergência. Veja mais informações no livro a seguir:

[6] Yoav Shoham e Kevin Leyton-Brown [2009], "Sistemas multiagentes: fundamentos algorítmicos, teóricos dos jogos e lógicos", imprensa da Universidade de Cambridge.

Eu acho que o aprendizado de máquina é uma maneira bastante direta de abordar a EGT, já que é um ponto natural entre a física relevante (mecânica estatística) e a ciência da computação. Definitivamente isso foi feito, levaria um pouco para encontrar uma boa referência, mas uma referência aleatória (que também mostra que o pessoal da EGT considerou outros conceitos populares de equilíbrio, como equilíbrio correlacionado):

[7] Sergiu Hart e Andreu Mas-Colell [2000], "Um procedimento adaptativo simples que leva ao equilíbrio correlacionado", Econometrica 68 (5): 1127-1150

[8] Antonella Ianni [2001], "Aprendizagem de equilíbrios correlatos em jogos populacionais", Mathematics Social Sciences 42 (3): 271-294.

[9] Ludek Cigler e Boi Faltings [2011], "Atingindo os equilíbrios correlatos por meio da aprendizagem de vários agentes", AAMAS 2011: 509-516

Eu definitivamente espero que outras pessoas dêem respostas mais específicas, já que essa é uma pergunta sobre a qual eu sempre quis saber mais.

Como outros já disseram, há menos do que você esperaria. Alguns artigos relacionados tangencialmente:

"Pesos multiplicativos em jogos de coordenação e a teoria da evolução" de Chastain, Livnat, Papadimitriou e Vazirani. Este artigo argumenta que a dinâmica evolutiva (em um modelo simples) é equivalente a um jogo de coordenação entre os genes sendo jogados com o algoritmo de aprendizado de pesos multiplicativos. Eles analisam a variante de 2 genes, em um modelo simplificado.

Observe que o algoritmo de pesos multiplicativos é uma dinâmica natural conhecida por convergir para o equilíbrio de Nash em jogos de soma zero, jogos de potencial não atômico e outros (veja, por exemplo, Freund e Schapire )

"O preço da anarquia estocástica", de Chung, Ligett, Pruhs e eu (de algum tempo atrás). Aqui, estudamos estados estocásticos estáveis ​​de um jogo, relacionados à ESS. Não nos preocupamos com a complexidade de encontrá-los, mas mostramos que, em alguns jogos, o preço da anarquia é mais baixo do que o conjunto de equilíbrios estocásticos estáveis ​​em comparação com os equilíbrios arbitrários de Nash.

Eu aprendi com a escola de Ashlock . A grande vantagem que obtive foi a utilidade de tirar as$n^2$ tabela de resultados entre agentes e use o K-Means para agrupar as linhas em grupos de estratégia para análise.