Desenho de Mecanismos

O desenho de mecanismos, por vezes denominado teoria inversa dos jogos, é a engenharia de regras para a interação, de modo que agentes egoístas, agindo racionalmente, produzam os resultados desejados pelo projetista.

Definition

O desenho de mecanismos é o estudo de como definir as regras de uma interação multiagente — quem pode fazer o quê e como os resultados e pagamentos são determinados — de modo que o comportamento de equilíbrio de agentes racionais e egoístas atinja um objetivo desejado, como eficiência ou veracidade.

Scope

Este tópico abrange o desenho de protocolos de interação para agentes estratégicos: escolha social e agregação de preferências, os objetivos de eficiência e compatibilidade de incentivos (veracidade), o princípio da revelação, leilões (incluindo o leilão de segundo preço de Vickrey e o mecanismo de Vickrey-Clarke-Groves), e os aspetos algorítmicos e computacionais da implementação de mecanismos. Aborda como alinhar os incentivos individuais com os objetivos coletivos. A análise descritiva de como os agentes se comportam em jogos fixos é tratada na teoria dos jogos.

Core questions

• Como podem as regras de interação ser concebidas para que os agentes tenham um incentivo para relatar as suas verdadeiras preferências?
• O que o princípio da revelação diz sobre restringir a atenção a mecanismos verídicos?
• Como os leilões alocam bens de forma eficiente entre agentes com valorações privadas?
• Quais são os custos computacionais da implementação de mecanismos desejáveis?

Key concepts

• escolha social e agregação de preferências
• compatibilidade de incentivos (veracidade)
• implementação de estratégia dominante
• princípio da revelação
• leilões
• leilão de segundo preço de Vickrey
• mecanismo de Vickrey-Clarke-Groves (VCG)
• eficiência e racionalidade individual

Key theories

Compatibilidade de incentivos e o leilão de segundo preço

O leilão de segundo preço (em envelope fechado) de Vickrey, onde o vencedor paga o segundo lance mais alto, torna a licitação verídica uma estratégia dominante, ilustrando como um desenho cuidadoso das regras pode elicitar um comportamento honesto de agentes egoístas.

Mecanismos de Vickrey-Clarke-Groves

A família VCG generaliza a ideia do segundo preço para problemas complexos de alocação, cobrando de cada agente a sua externalidade para que o relato verídico seja uma estratégia dominante e o resultado eficiente seja selecionado.

Princípio da revelação

O princípio da revelação mostra que qualquer resultado alcançável por algum mecanismo também pode ser alcançado por um mecanismo direto verídico, permitindo que os projetistas se concentrem em mecanismos compatíveis com incentivos sem perda de generalidade.

Clinical relevance

O desenho de mecanismos sustenta a publicidade online e os leilões de pesquisa patrocinada, leilões de espectro e recursos, mercados eletrónicos e sistemas de correspondência, e a alocação de recursos computacionais, ao projetar regras sob as quais agentes estratégicos são levados a resultados eficientes e verdadeiros.

History

O desenho de mecanismos surgiu da teoria económica, com a análise de leilões de Vickrey (1961) e as posteriores contribuições de Clarke e Groves formando a família VCG. A partir do final da década de 1990, a ciência da computação adicionou o estudo da tratabilidade computacional e da aproximação, dando origem ao desenho de mecanismos algorítmicos, apresentado em textos como Algorithmic Game Theory (2007).

Key figures

• William Vickrey
• Edward H. Clarke
• Theodore Groves
• Noam Nisan
• Tim Roughgarden

Seminal works

• vickrey1961
• shoham2009
• nisan2007

Frequently asked questions

Por que o desenho de mecanismos é chamado de teoria inversa dos jogos?

A teoria dos jogos toma as regras de uma interação como dadas e analisa como agentes racionais se comportarão. O desenho de mecanismos funciona ao contrário: começa com um resultado desejado e projeta as regras para que o comportamento racional dos agentes produza esse resultado, daí o rótulo de teoria inversa dos jogos.

Por que um leilão de segundo preço incentiva a licitação verídica?

Num leilão de segundo preço de Vickrey, o vencedor paga o segundo lance mais alto em vez do seu próprio. Isso remove qualquer incentivo para subestimar um lance: licitar o seu valor verdadeiro só pode ajudá-lo a ganhar quando vale a pena e nunca o faz pagar a mais, então a licitação honesta torna-se uma estratégia dominante.