Projeto Ótimo de Leilão Discreto de Um Único Parâmetro

Estudamos o clássico cenário de leilão de item único de Myerson, mas sob a suposição de que os valores dos compradores para o item estão distribuídos em suportes finitos. Utilizando a dualidade forte de LP e teoria poliedral, rederivamos vários resultados-chave sobre o leilão que maximiza a receita, incluindo a caracterização através da maximização do bem-estar virtual e a optimalidade de mecanismos determinísticos, assim como uma nova equivalência genérica entre compatibilidade de incentivos de estratégia dominante e bayesiana. Inspirados nisso, abstraímos nossa abordagem para lidar com cenários de leilão mais gerais, onde o espaço de viabilidade pode ser dado por restrições convexas arbitrárias, e o objetivo é uma combinação convexa de receita e bem-estar social. Caracterizamos os leilões ótimos desses sistemas como maximizadores de bem-estar virtual generalizados, fazendo uso de suas condições KKT, e apresentamos um análogo da fórmula de pagamento de Myerson para cenários gerais de leilão discreto de um único parâmetro. Além disso, provamos que a unimodalidade total do espaço de viabilidade é uma condição suficiente para garantir a optimalidade de leilões com regras de alocação integrais. Finalmente, demonstramos essa abordagem KKT aplicando-a a um cenário onde os licitantes estão interessados em comprar fluxos viáveis em árvores com restrições de capacidade, e fornecemos uma descrição combinatória do leilão ótimo (randomizado, em geral).