Em design de mecanismos, um ramo da economia, um mecanismo orçamentariamente viável é um mecanismo no qual o pagamento total feito pelo leiloeiro é limitado no máximo por um orçamento predefinido e fixo. Foram primeiro apresentados por Yaron Singer, e desenvolvidos por vários outros.

Visão geral e conceitos básicos O design de mecanismos com orçamento viável é um subcampo do design de mecanismos algorítmicos que se concentra em leilões do tipo pregão onde o leiloeiro (comprador) tem um orçamento estritamente limitado. Ao contrário do design de mecanismos padrão, que muitas vezes busca maximizar o bem-estar social ou a receita sem um limite rígido ao pagamento total, os mecanismos orçamentariamente viáveis devem garantir que a soma dos pagamentos aos agentes estratégicos (vendedores) não exceda um orçamento fixo . Essa área é particularmente relevante para os setores de crowdsourcing, compra de dados para aprendizado de máquina e conservação ambiental, onde uma agência central precisa contratar serviços de agentes com custos privados, mas respeitar limites orçamentários.

Modelo Em um cenário típico de orçamento viável, há um conjunto de vendedores, , cada qual com uma unidade de um bem ou serviço. Cada vendedor tem um custo privado para prestar seus serviços. O comprador possui uma função de avaliação, que atribui um valor a cada subconjunto de vendedores. O objetivo é projetar um mecanismo — composto por uma regra de alocação e uma regra de pagamento — que satisfaça diversas propriedades essenciais:

Veracidade (Compatibilidade de Incentivos): Os vendedores maximizam sua utilidade ao relatarem seus custos reais, .

Racionalidade individual: Nenhum vendedor recebe menos do que seu custo declarado.

Viabilidade orçamentária: o pagamento total não ultrapassa o orçamento .

Eficiência (Aproximação): O mecanismo visa maximizar a avaliação relativo ao subconjunto ideal que poderia ser adquirido se os custos fossem de conhecimento público.

A dificuldade da restrição orçamentária Projetar mecanismos viáveis sujeitos à uma restrição orçamentária é significativamente mais difiícil do que leilões sem restrições (como os que usam o mecanismo VCG ), porque a restrição orçamentária conecta as regras de alocação e de pagamento. Em leilões padrão, muitas vezes é possível determinar a alocação ideal e, em seguida, calcular os pagamentos; em leilões com orçamento viável, uma alocação que parece ideal pode exigir pagamentos que violem o orçamento, necessitando de uma abordagem de maximização de lucros com limites cuidadosamente calculados.

Desenvolvimentos Fundamentais O campo foi estabelecido por Yaron Singer em 2010. Singer demonstrou que para qualquer função de conjunto submodular, ou seja, uma função com retornos marginais decrescentes em relação à valoração de items, existe um mecanismo com aproximação por um fator constante e implementa o mecanismo de participação proporcional. Trabalhos subsequentes expandiram esses resultados para classes de valoração mais complexas: Funções subaditivas: Funções em que o valor da união de dois conjuntos não é maior que a soma de seus valores individuais. Os primeiros resultados forneceram uma aproximação , enquanto trabalhos mais recentes aprimoraram para ao conectar o problema à lacuna de integralidade dos programas lineares e ao núcleo aproximado na teoria dos jogos cooperativos .

Aplicações Mecanismos economicamente viáveis são amplamente implementados em aplicações de crowdsourcing, como rotulagem e aquisição de dados, selecionando dados para treinar modelos de IA com um orçamento limitado.

Ver também

Design de mecanismos Leilão Pregão

Referências

Categoria:Teoria dos jogos Categoria:Teoria da escolha social