Algoritmos para determinação de vencedores e precificação em leilões combinatóriais

Resumo

Os leilões são considerados a maneira mais generalizada de alocação e precificação de bens e serviços quando se desconhece o valor real destes. Tradicionalmente, em um leilão é negociado um item ou grupo de itens onde os agentes envolvidos, conhecidos como licitantes, podem apenas submeter lances sobre um item ou um pacote de itens. Este tipo de negociação pode não levar a eficiência econômica do mercado porque os licitantes podem não ser capazes de expressar suas preferências completamente. Para contornar esta questão, os leilões combinatoriais permitem que os licitantes submetam diversos lances para vários subconjuntos de itens, não necessariamente disjuntos, podendo assim expressar a complementariedade e a substituibilidade entre os itens desejados. Os desafios destes tipos de leilões são o tamanho das instâncias que, geralmente são exponenciais nos números de lances efetuados, e o problema de determinação de vencedores que é NP-difícil (mesmo com uma entrada polinomial), o que exige um grande esforço computacional. Estamos interessados em estratégias recentes para tratar estes problemas, como algoritmos exatos especializados e heurísticas que possam garantir propriedades econômicas desejáveis, como obtenção de determinados equilíbrios e precificação justas. Para isso, propomos a investigação e desenvolvimento de métodos exatos e heurísticos, sua discussão e comparação com resultados recentes da literatura, além de experimentos computacionais para comprovação da eficácia e eficiência dos métodos. (AU)