Leilão combinatório - Combinatorial auction

Parte de uma série sobre
Leilões
Tipos
All-pay Amsterdam Anglo-holandês Troca dupla Melhor / não melhor brasileiro Calcutá Vela chinês Lance de caixa de clique Combinatorial Valor comum Aceitação diferida Preço discriminatório Dobro holandês inglês Avançar francês Primeiro preço generalizado Segundo preço generalizado japonês Multi-atributo Multi unidade Sem reserva Classificação Reverter escocês Selado de primeiro preço Ascendente simultâneo Preço único Semáforo Preço uniforme Lance único Valor das receitas Vickrey Vickrey – Clarke – Groves Walrasian ianque
Licitação
Sombreamento Calor licitantis Busca de cancelamento Pular Rigging Sniping Suicídio Colusão tácita
Contextos
Algoritmos Automóveis Arte Caridade Crianças Jogadores de críquete Nomes de domínio Flores Empréstimos Fraude Escravos Espectro Selos Virgindade Vinho Esposas
Teoria
Bens digitais Preço da anarquia Equivalência de receita Maldição do vencedor
Conectados
Ebidding Mercado eletrônico privado Programas
v t e

Um leilão combinatório é um tipo de mercado inteligente no qual os participantes podem dar lances em combinações de itens heterogêneos discretos, ou “pacotes”, em vez de itens individuais ou quantidades contínuas. Esses pacotes também podem ser chamados de lotes e todo o leilão um leilão de vários lotes . Os leilões combinatórios são aplicáveis ​​quando os licitantes possuem avaliações não aditivas em pacotes de itens, ou seja, eles avaliam combinações de itens mais ou menos do que a soma de suas avaliações de elementos individuais da combinação.

Os leilões combinatórios simples têm sido usados ​​por muitos anos em leilões de imóveis , onde um procedimento comum é aceitar lances para pacotes de itens. Eles têm sido usados ​​recentemente para transporte de cargas de caminhão, rotas de ônibus, compras industriais e na alocação de espectro de rádio para comunicações sem fio. Nos últimos anos, as equipes de aquisição aplicaram leilões combinatórios reversos na aquisição de bens e serviços. Esse aplicativo é frequentemente conhecido como otimização de sourcing. Uma vez que a aquisição de construção frequentemente envolve negociações sobre vários componentes, leilões reversos combinatórios são sugeridos para reduzir custos neste setor.

Embora permitam que os licitantes sejam mais expressivos, os leilões combinatórios apresentam desafios computacionais e teóricos do jogo em comparação com os leilões tradicionais. Um exemplo de problema computacional é como determinar com eficiência a alocação, uma vez que os lances tenham sido submetidos ao leiloeiro. Isso é chamado de problema de determinação do vencedor.

O problema de determinação do vencedor pode ser declarado da seguinte forma: dado um conjunto de lances em um leilão combinatório, encontre uma alocação de itens aos licitantes - incluindo a possibilidade de o leiloeiro reter alguns itens - que maximiza a receita do leiloeiro. Esse problema é difícil para grandes instâncias. Especificamente, é NP-difícil , o que significa que se conjectura que não existe um algoritmo de tempo polinomial que encontre a alocação ótima. O problema do leilão combinatório pode ser modelado como um problema de empacotamento de conjuntos . Portanto, muitos algoritmos têm sido propostos para encontrar soluções aproximadas para o problema de leilão combinatório. Por exemplo, Hsieh (2010) propôs uma abordagem de relaxação Lagrangiana para problemas combinatórios de leilão reverso.

Muitos desses aspectos dos leilões combinatórios, incluindo alguns exemplos do mundo real, também são discutidos no livro abrangente editado por Cramton, Shoham e Steinberg (2006).

História

Os leilões combinatórios foram propostos inicialmente por Rassenti, Smith e Bulfin (1982), para a alocação de slots de aterrissagem em aeroportos . Seu artigo introduziu muitas idéias-chave sobre leilões combinatórios, incluindo a formulação de programação matemática do problema do leiloeiro, a conexão entre o problema de determinação do vencedor e o problema de empacotamento , a questão da complexidade computacional, o uso de técnicas de economia experimental para teste combinatório leilões, e consideração de questões de compatibilidade de incentivos e revelação de demanda em leilões combinatórios.

Leilão de relógio combinatório

Um caso especial de leilão combinatório é o leilão de relógio combinatório (CCA), que combina um leilão de relógio, durante o qual os licitantes podem fornecer suas confirmações em resposta aos preços crescentes, com um leilão de lance selado subsequente, no qual os licitantes enviam lances de pacote selado . O leiloeiro usa os lances finais para calcular a alocação de melhor valor e os pagamentos de Vickrey .

Veja também

• Otimização (matemática)
• Teoria dos jogos combinatórios
• Leilão de primeiro preço

Referências

Leitura adicional

• Peter Cramton, Yoav Shoham e Richard Steinberg (2006). Leilões Combinatórios . MIT Press . ISBN  0-262-03342-9 . Um livro contribuído com ampla cobertura do tópico.
• de Vries, S .; Vohra, R. (2003). "Leilões combinatórios: Uma pesquisa" (PDF) . INFORMS Journal on Computing . 15 (3): 284–309. CiteSeerX  10.1.1.23.8046 . doi : 10.1287 / ijoc.15.3.284.16077 . ISSN  1526-5528 . Um pouco desatualizado, mas uma pesquisa clássica.
• Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoria Algorítmica dos Jogos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.. Um livro contribuído com um bom capítulo introdutório sobre leilões combinatórios de uma perspectiva da teoria da ciência da computação; consulte o Capítulo 11.
• Rassenti, Stephen J .; Smith, Vernon L .; Bulfin, Robert L. (1982). "Um mecanismo de leilão combinatório para alocação de slots de tempo em aeroportos" (PDF) . Bell Journal of Economics . 13 (2): 402–417. doi : 10.2307 / 3003463 . JSTOR  3003463 . Trabalho inicial que popularizou a ideia de leilão combinatório.
• Rothkopf, M .; Pekec, A .; Harstad, R. (1998). "Leilões combinatórios gerenciáveis ​​computacionalmente". Ciência da Administração . 44 (8): 1131–1147. CiteSeerX  10.1.1.723.9753 . doi : 10.1287 / mnsc.44.8.1131 . Um artigo inicial influente sobre considerações computacionais.
• Hammami, Farouk; Rekik, Monia; Coelho, Leandro C. (2019). “Abordagens de solução exata e heurística para o problema de licitação em licitações de transporte com frota heterogênea”. Pesquisa de Transporte Parte E: Revisão de Logística e Transporte . 127 : 150–177. doi : 10.1016 / j.tre.2019.05.009 . Uma aplicação de leilões combinatórios para aquisição de serviços de transporte.
• Hsieh, Fu-Shiung (2010). “Leilão reverso combinatório baseado na revelação dos multiplicadores de Lagrange” (PDF) . Sistemas de Apoio à Decisão . 48 (2): 323–330. doi : 10.1016 / j.dss.2009.08.009 .
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Sistemas multiagentes: Fundamentos algorítmicos, teóricos dos jogos e lógicos . Nova York: Cambridge University Press . ISBN 978-0-521-89943-7.Uma visão geral na forma de livro didático; consulte a Seção 11.3. Para download gratuito online .