Teoria dos Jogos para Agentes

A teoria dos jogos oferece a estrutura matemática para analisar a interação estratégica entre agentes racionais, prevendo como tomadores de decisão autointeressados se comportam quando o resultado de cada um depende das escolhas dos outros.

Definition

A teoria dos jogos estuda situações em que múltiplos agentes racionais escolhem ações cujos pagamentos dependem das escolhas de todos os agentes, e caracteriza o comportamento conjunto estável ou racional através de conceitos de solução como equilíbrios.

Scope

Este tópico aborda os fundamentos da teoria dos jogos utilizados na IA multiagente: jogos na forma normal e extensiva, estratégias dominantes, o equilíbrio de Nash e sua existência, estratégias mistas e exemplos-chave como o dilema do prisioneiro e jogos de soma zero; juntamente com questões algorítmicas de computação de equilíbrios. Ele trata de como os agentes raciocinam uns sobre os outros e quais comportamentos conjuntos são estáveis. A engenharia de regras de interação é tratada sob o design de mecanismos, e o aprendizado para jogar jogos pertence ao subcampo de aprendizado de máquina.

Core questions

• Como as interações estratégicas são representadas como jogos na forma normal ou extensiva?
• Quais conceitos de solução (estratégias dominantes, equilíbrio de Nash) preveem como agentes racionais se comportam?
• Quando a existência de um equilíbrio é garantida, possivelmente em estratégias mistas?
• Quão difícil é computar equilíbrios, e como isso afeta seu uso por agentes?

Key concepts

• jogos na forma normal e extensiva
• pagamentos e estratégias
• estratégia dominante
• equilíbrio de Nash
• estratégias mistas
• jogos de soma zero e minimax
• dilema do prisioneiro
• computação de equilíbrio

Key theories

Equilíbrio de Nash

Um equilíbrio de Nash é um perfil de estratégias no qual nenhum agente pode melhorar seu pagamento alterando unilateralmente sua própria estratégia; Nash provou que todo jogo finito possui pelo menos um tal equilíbrio, possivelmente em estratégias mistas.

Minimax em jogos de soma zero

Em jogos de soma zero para dois jogadores, o teorema minimax de von Neumann garante um valor e estratégias ótimas (possivelmente randomizadas) para ambos os jogadores, conectando a teoria dos jogos à tomada de decisões adversariais.

Estratégias dominantes e dilemas

A análise de jogos via estratégias dominantes explica resultados como o dilema do prisioneiro, onde escolhas individualmente racionais levam a um resultado coletivamente pior, ilustrando a tensão entre a racionalidade individual e a de grupo.

Clinical relevance

A análise da teoria dos jogos informa o design de leilões e mercados, estratégias de segurança e patrulhamento, roteamento e congestionamento de redes, e negociação automatizada, prevendo como agentes estratégicos atuarão e identificando resultados estáveis em ambientes competitivos.

History

A teoria dos jogos foi fundada por von Neumann e Morgenstern (1944) e estendida pelo conceito de equilíbrio de Nash (1950). Tornou-se central para a economia e, a partir da década de 1990, para a IA e a ciência da computação através da teoria dos jogos algorítmica, que estuda a complexidade computacional dos equilíbrios e seu uso em sistemas multiagente.

Key figures

• John von Neumann
• Oskar Morgenstern
• John F. Nash
• Yoav Shoham
• Kevin Leyton-Brown

Seminal works

• nash1950
• vonneumann1944
• shoham2009

Frequently asked questions

O que é um equilíbrio de Nash?

Um equilíbrio de Nash é uma combinação de estratégias, uma por agente, tal que nenhum agente individual pode se sair melhor mudando apenas sua própria estratégia enquanto os outros mantêm as suas fixas. Ele captura uma noção de comportamento racional estável e mutuamente consistente.

Por que o dilema do prisioneiro é importante para agentes de IA?

O dilema do prisioneiro mostra que agentes agindo em seu próprio interesse racional podem chegar a um resultado que é pior para todos eles do que se tivessem cooperado. Ele destaca por que o design de incentivos e mecanismos de coordenação é importante ao construir sistemas de agentes autointeressados.