Auditing Algorithmic Collusion from Strategy Graphs

Resumo Técnico: Auditoria de Colusão Algorítmica a partir de Grafos de Estratégia

Definição do Problema
Detectar a colusão algorítmica é difícil porque os reguladores muitas vezes carecem de acesso aos algoritmos proprietários das empresas, aos dados de treinamento e ao histórico completo de mercado. Embora existam regimes de informação extremos — ou acesso total ao código-fonte ou apenas traços de preços limitados — este artigo investiga um regime de informação intermediário. Neste regime, um auditor pode consultar políticas de preços "congeladas" (a ação gananciosa selecionada em cada estado de mercado), mas carece de conhecimento das funções de demanda, benchmarks numéricos de preços, níveis de lucro competitivo/monopolista ou da metodologia específica de treinamento. A questão central é se a topologia estrutural dessas políticas congeladas contém sinais robustos de colusão sem a necessidade de reconstruir o ambiente econômico subjacente.

Metodologia
Os autores propõem uma abordagem baseada na teoria dos grafos para auditoria. Eles modelam a interação de $n$ agentes em um jogo de preços repetido onde cada agente condiciona suas decisões a um histórico truncado de perfis de preços. Uma política determinística conjunta induz um grafo de estratégia $G(\pi)$, uma relação funcional onde os nós representam estados conjuntos do mercado e as arestas direcionadas representam a transição para o próximo estado quando todos os agentes executam suas ações gananciosas.

A metodologia central envolve:

1. Derivação da Verdade Fundamental (Ground Truth): Os autores analisam primeiro um conjunto analiticamente conhecido de 101 equilíbrios de Nash em um jogo de duopólio de três preços com demanda logit. Eles categorizam esses equilíbrios por seu "Índice de Colusão" ($\Delta$), uma métrica baseada em lucro que varia de 0 (competitivo) a 1 (monopólio).
2. Definição de Métricas: A partir da lógica estrutural de estratégias de recompensa e punição (onde desvios são punidos antes do retorno à cooperação), eles derivam cinco métricas de teoria dos grafos computadas no maior componente fracamente conectado (WCC) do grafo de estratégia:
   • Intermediação Máxima ($B_{max}$): O maior número de caminhos de retorno que passam por um único nó não-atrator (gargalo).
   • Grau de Entrada do Atrator ($D_A$): O número médio de estados que transitam diretamente para o atrator (o ciclo que representa o resultado de longo prazo).
   • Comprimento Médio do Caminho ($L_A$): O número médio de etapas necessárias para que qualquer estado alcance o atrator.
   • Fração da Bacia ($\beta$): A proporção do espaço de estados total contida no maior WCC.
   • Número de Atratores ($K$): A contagem de ciclos distintos no grafo.
3. Validação Empírica: Essas métricas são testadas em políticas aprendidas por dois algoritmos distintos:
   • Q-learning de Calvano et al. (2020): Treinado em um ambiente de 15 preços sob variados fatores de desconto ($\gamma \in [0.1, 0.95]$), gerando 1.800 pares de políticas.
   • Q-learning Descentralizado (Arslan e Yükel, 2017): Treinado em um ambiente de 5 preços.
   • Teste de Rematch (Recombinação): Políticas treinadas independentemente são recombinadas entre si para quebrar a colusão, criando um conjunto de dados de resultados competitivos sob um fator de desconto elevado.

Principais Resultados
O estudo descobre que características topológicas específicas do grafo de estratégia correlacionam-se fortemente com o Índice de Colusão baseado em lucro, mesmo na ausência de rótulos de preços ou estimativas de demanda:

• Intermediação Máxima: Mostra uma forte correlação positiva com o Índice de Colusão ($\rho \approx +0.67$ em execuções agrupadas de Calvano; $\rho \approx +0.94$ no conjunto de equilíbrio analítico). Grafos colusivos exibem "gargalos" onde estados de punição residem nos caminhos de retorno da maioria dos estados transientes.
• Grau de Entrada do Atrator: Mostra uma forte correlação negativa ($\rho \approx -0.67$). Em equilíbrios colusivos, menos estados transitam diretamente para o atrator de preço alto porque os desvios devem passar primeiro por uma fase de punição.
• Comprimento Médio do Caminho: Mostra uma correlação positiva ($\rho \approx +0.57$), refletindo as etapas adicionais necessárias para retornar à cooperação após uma fase de punição.
• Fração da Bacia e Número de Atratores: Estas métricas são menos informativas no cenário padrão de Calvano (onde políticas competitivas tendem a formar grafos de bacia única), mas tornam-se significativas quando o espaço de estados é fragmentado, como no caso do Q-learning descentralizado ou no experimento de rematch.

Os resultados sustentam-se através de diferentes algoritmos de aprendizado e desenhos experimentais. Notavelmente, as métricas dependem exclusivamente da topologia não rotulada do grafo; elas não requerem conhecimento dos preços específicos, lucros ou da magnitude do fator de desconto.

Significância e Alegações
O artigo afirma fornecer uma "base promissora para auditar sistemas de preços algorítmicos sob informação limitada". Sua principal contribuição é demonstrar que a estrutura das políticas de preços congeladas contém sinais robustos de colusão.

• Viabilidade de Auditoria: As métricas propostas sugerem que uma autoridade não precisa reconstruir o processo de treinamento ou acessar o código proprietário para identificar potencial colusão. Em vez disso, consultar a resposta da política a todos os estados factíveis para construir o grafo de estratégia é suficiente para gerar uma triagem estrutural.
• Detecção Sem Benchmarks: Diferente dos índices baseados em lucro, estas métricas de grafo não exigem benchmarks competitivos ou monopolistas, que são frequentemente indisponíveis para reguladores.
• Escopo e Limitações: Os autores declaram explicitamente que esta é uma triagem estrutural, não um achado definitivo de colusão. As métricas detectam esquemas de "recompensa e punição" que retornam à cooperação, mas podem falhar em identificar equilíbrios de "gatilho de memória infinita" (grim trigger), onde o sistema reverte permanentemente à competição após um desvio (pois estes escondem o ramo colusivo em um componente subordinado). Além disso, a validação atual é limitada a políticas finitas, determinísticas e congeladas em ambientes logit estilizados; a aplicabilidade a políticas estocásticas, adaptativas ou de alta dimensão permanece uma questão aberta.

Em suma, o artigo argumenta que a topologia de um grafo de estratégia — especificamente a concentração de caminhos de retorno através de estados de punição — serve como uma assinatura topológica da colusão algorítmica, oferecendo uma ferramenta prática para reguladores que operam sob restrições de informação.