Resumo Técnico: Um Benchmark para Jogos de Negociação Multi-Parte a partir de Dados Reais

1. O Problema

A maioria dos modelos computacionais de negociação existentes (em Teoria dos Jogos e Aprendizado por Reforço Multiagente - MARL) opera sob a premissa de que a negociação é um processo de barganha sobre um único resultado final (ex: divisão de itens ou preço), onde as ofertas são não vinculativas até a aceitação.

No entanto, o artigo argumenta que muitas negociações reais de alto risco (como crises humanitárias ou conferências climáticas) não seguem esse modelo. Elas ocorrem como sequências de compromissos vinculativos em nível de ação. Nesses cenários:

• As partes fazem compromissos bilaterais ou em pequenos grupos que são vinculativos (não podem ser desfeitos).
• Cada acordo restringe as opções futuras, remodelando as oportunidades de barganha subsequentes.
• A recompensa (payoff) é frequentemente concedida apenas no final do horizonte temporal (recompensa terminal), tornando difícil avaliar o valor de compromissos intermediários.
• A estratégia envolve não apenas o acordo final, mas a ordem dos parceiros, a sequência de compromissos e como compromissos intermediários interagem.

Este regime de "negociação sequencial multi-parte com compromissos vinculativos" é subestudado e carece de benchmarks padronizados para avaliar algoritmos de decisão.

2. Metodologia

Os autores propõem um framework modular composto por um gerador de jogos configurável, um protocolo de negociação de referência e uma suíte de avaliação.

2.1 Formalização do Jogo

• Agentes e Compromissos: $N_P$ jogadores negociam em $T$ turnos. Cada jogador possui um vetor de compromissos binários ($C_n$), onde $C_{nj}=1$ indica que o jogador $n$ se compromete a realizar a ação $j$. Os compromissos são vinculativos (0 $\to$ 1, nunca 1 $\to$ 0).
• Objetivos e Recompensas: Existem $N_G$ objetivos. A utilidade de um jogador para um objetivo depende de quais compromissos foram feitos.
  • Tipos de Objetivos: Lineares (satisfação proporcional ao número de compromissos feitos) e "Tudo ou Nada" (satisfação binária apenas se todos os compromissos necessários forem feitos).
  • Recompensa Terminal: As utilidades são calculadas apenas no estado final $C(T)$. Não há recompensas intermediárias.
• Geração de Jogos: Um gerador configurável cria instâncias variando propriedades estruturais:
  • Escala: Número de jogadores, objetivos e compromissos.
  • Alinhamento de Incentivos: De cooperativo (utilidades similares) a adversário (utilidades opostas).
  • Estrutura de Payoff: Balanceada, dominada por positivos ou dominada por negativos.
  • Complexidade e Não-linearidade: Número de compromissos necessários por objetivo e fração de objetivos "tudo ou nada".
  • Estrutura de Preferências: Controlada por fatores latentes que definem a correlação entre utilidades em diferentes questões.

2.2 Protocolo de Negociação

O benchmark assume um protocolo de referência para isolar a dificuldade da instância e avaliar aproximações de funções de valor:

• Informação: Perfeita (todos conhecem as preferências de todos).
• Dinâmica: Sequencial e bilateral (um par negocia por vez).
• Fases por Turno:
  1. Seleção de Parceiro: O proponente escolhe um parceiro para maximizar seu payoff esperado (usando MCTS com uma função de valor aproximada).
  2. Oferta: O proponente formula uma atualização de compromisso conjunta (máximo $k$ novos compromissos por jogador).
  3. Decisão: O parceiro aceita se sua utilidade não piorar (jogo de ultimato).

2.3 Aproximações de Função de Valor ("Lentes")

Como calcular o valor exato é intratável em grandes jogos, o estudo compara três aproximações simples que atuam como "lentes" enviesadas para avaliar compromissos parciais:

1. Recompensa Miópica (Myopic Reward): Avalia o estado apenas pelo impacto imediato no payoff atual, ignorando o futuro.
2. Limite Superior (Upper Bound / Otimista): Assume que todos os objetivos positivos serão alcançados de qualquer forma. O foco é evitar compromissos que gerem exposição a penalidades negativas futuras.
3. Limite Inferior (Lower Bound / Pessimista): Assume que ameaças credíveis (objetivos negativos para o jogador, mas não para outros) serão realizadas. Foca em garantir progresso positivo e ser robusto a cenários adversos.

2.4 Avaliação

• Jogos Pequenos: Solução exata via Programação Dinâmica para calcular o erro $L_1$ em relação ao ótimo.
• Jogos Grandes e Reais: Comparação pareada contra uma linha de base de "Sem Negociação" (onde jogadores agem unilateralmente).
• Dados Reais: Instâncias derivadas de artigos de posição do Harvard Negotiation Challenge (exercício climático), convertidos em jogos computacionais.

3. Principais Contribuições

1. Gerador de Jogos Controlável: Uma ferramenta para gerar sistematicamente paisagens de negociação com diferentes níveis de dificuldade estratégica (alinhamento, complexidade, não-linearidade).
2. Protocolo e Suíte de Avaliação: Um procedimento de referência fixo que permite isolar a dificuldade da instância e comparar diferentes heurísticas de decisão em condições controladas.
3. Análise de Regimes via "Lentes" de Valor: Demonstra que nenhuma aproximação de valor domina universalmente; o desempenho depende criticamente da estrutura do jogo.
4. Instâncias Realistas: Integração de dados do mundo real (negociações climáticas) para validar se os padrões sintéticos se transferem para cenários complexos e baseados em documentos.

4. Resultados Chave

Os experimentos mapearam onde cada estratégia de avaliação falha ou tem sucesso:

• Dependência do Regime:
  • Jogos Balanceados (Misto): A Recompensa Miópica tende a performar melhor. Como há conflito estratégico e utilidades mistas, assumir otimismo ou pessimismo extremo (Upper/Lower) é frágil.
  • Jogos Dominados por Negativos (Adversários): O Limite Superior (Otimista) é superior. Sua cautela em evitar exposição a penalidades negativas é crucial, especialmente em cenários com "pílulas envenenadas" (ofertas que parecem boas localmente, mas geram grandes penalidades futuras).
  • Jogos Dominados por Positivos: O Limite Inferior (Pessimista) performa melhor. Assume que ameaças credíveis ocorrerão, incentivando o bloqueio de progresso positivo sempre que possível.
• Impacto da Não-Linearidade: A dificuldade aumenta significativamente com a proporção de objetivos "tudo ou nada", pois torna a avaliação de progresso parcial muito mais incerta.
• Dados Reais (Clima): Em jogos derivados do Harvard Negotiation Challenge (dominados por positivos e lineares), o Limite Inferior e a Recompensa Miópica superaram a linha de base. O Limite Superior performou mal devido à sua excessiva cautela.
• LLMs: Um baseline de Large Language Model (zero-shot) obteve os piores resultados, indicando que modelos de linguagem atuais ainda não conseguem navegar eficazmente nessas complexidades multi-agente sem mecanismos de valor robustos.

5. Significado e Conclusão

O trabalho estabelece que a negociação multi-parte com compromissos vinculativos é um regime distinto que exige estratégias diferentes das usadas em barganha de resultado único.

• Insight Principal: Não existe uma "lente" de valor universal. A eficácia de um agente depende de sua capacidade de inferir o regime estrutural do jogo (ex: é um jogo de evitar penalidades ou de maximizar ganhos?) e adaptar sua avaliação de estado.
• Direções Futuras: O benchmark aponta para a necessidade de agentes que aprendam estimativas de valor de estado mais precisas e generalizáveis, ou métodos adaptativos que inferam o regime online.
• Relevância: O benchmark é modular e permite extensões para observabilidade parcial e dinâmicas mais complexas, servindo como um terreno de prova essencial para o desenvolvimento de IA em negociações complexas do mundo real.

O código e os dados estão disponíveis publicamente para fomentar pesquisas futuras nesta área.