Leilão Vickrey - Vickrey 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 Vickrey ou leilão de segundo preço de lance selado ( SPSBA ) é um tipo de leilão de lance selado . Os licitantes enviam lances por escrito sem saber o lance das outras pessoas no leilão. O licitante com lance mais alto vence, mas o preço pago é o segundo lance mais alto. Esse tipo de leilão é estrategicamente semelhante a um leilão inglês e dá aos licitantes um incentivo para oferecer seu valor real . O leilão foi descrito pela primeira vez academicamente pelo professor William Vickrey da Universidade de Columbia em 1961, embora tenha sido usado por colecionadores de selos desde 1893. Em 1797, Johann Wolfgang von Goethe vendeu um manuscrito usando um leilão de segundo preço de lance lacrado.

O artigo original de Vickrey considerou principalmente leilões onde apenas um único bem indivisível está sendo vendido. Os termos leilão de Vickrey e leilão de lance selado de segundo preço são, neste caso apenas, equivalentes e usados ​​indistintamente. No caso de vários bens idênticos, os licitantes apresentam curvas de demanda inversas e pagam o custo de oportunidade.

Os leilões de Vickrey são muito estudados na literatura econômica, mas incomuns na prática. Existem variantes generalizadas do leilão Vickrey para leilões multiunidades , como o leilão generalizado de segundo preço usado nos programas de publicidade online do Google e Yahoo! (Não compatível com incentivos ) e o leilão Vickrey – Clarke – Groves (compatível com incentivos).

Propriedades

Compatibilidade de auto-revelação / incentivo

Em um leilão de Vickrey com valores privados, cada licitante maximiza sua utilidade esperada dando lances (revelando) sua avaliação do item à venda. Esse tipo de leilão às vezes é usado para negociação de pool específico no mercado de títulos lastreados em hipotecas (MBS) da agência.

Eficiência ex-post

Um leilão Vickrey é eficiente na decisão (o vencedor é o licitante com a maior avaliação) nas circunstâncias mais gerais; assim, fornece um modelo de linha de base contra o qual as propriedades de eficiência de outros tipos de leilões podem ser postuladas. Só é eficiente ex-post (soma das transferências igual a zero) se o vendedor for incluído como "jogador zero", cuja transferência é igual ao negativo da soma das transferências dos outros jogadores (ou seja, os lances).

Fraquezas

• Não permite a descoberta de preço , ou seja, a descoberta do preço de mercado se os compradores não tiverem certeza de suas próprias avaliações, sem leilões sequenciais.
• Os vendedores podem usar lances de shill para aumentar o lucro.

O mecanismo Vickrey – Clarke – Groves (VCG) tem as deficiências adicionais:

• É vulnerável a conluio de licitantes . Se todos os licitantes no leilão de Vickrey revelarem suas avaliações uns aos outros, eles podem reduzir algumas ou todas as suas avaliações, preservando ao mesmo tempo quem vence o leilão.
• É vulnerável a uma versão de lance shill em que um comprador usa várias identidades no leilão para maximizar seu lucro.
• Não maximiza necessariamente as receitas do vendedor; a receita do vendedor pode até ser zero em leilões VCG. Se o objetivo de realizar o leilão é maximizar o lucro para o vendedor, em vez de apenas alocar recursos entre os compradores, então o VCG pode ser uma escolha ruim.
• As receitas do vendedor não são monotônicas em relação aos conjuntos de licitantes e ofertas.

A não monotonicidade das receitas do vendedor com relação aos lances (sem a introdução do mecanismo de custo de oportunidade VCG descrito no final deste artigo) pode ser demonstrada pelo exemplo a seguir. Considere 3 licitantes A, B e C, e dois itens homogêneos licitados, Y e Z.

• A quer os itens e dá um lance de $ 2 pelo pacote de Y e Z.
• B e C oferecem US $ 2 cada para um único item (lance US $ 2 para Y ou Z), pois eles realmente querem um item, mas não se importam se eles têm o segundo.

Agora, Y e Z são alocados para B e C, mas o preço é $ 0, como pode ser verificado removendo B ou C respectivamente. Se C licitar $ 0 em vez de $ 2, o vendedor ganhará $ 2 em vez de $ 0. Como a receita do vendedor pode aumentar quando os lances aumentam ou diminuem, as receitas do vendedor não são monotônicas com respeito aos lances.

Prova de domínio de licitação verdadeira

A estratégia dominante em um leilão de Vickrey com um item único e indivisível é que cada licitante lance seu valor real do item.

Seja o valor do licitante i para o item. Seja o lance do licitante i para o item. A recompensa para o licitante i é${\ displaystyle v_ {i}}$${\ displaystyle b_ {i}}$${\ displaystyle {\ begin {cases} v_ {i} - \ max _ {j \ neq i} b_ {j} & {\ text {if}} b_ {i}> \ max _ {j \ neq i} b_ {j} \\ 0 & {\ text {caso contrário}} \ end {casos}}}$

A estratégia de overbidding é dominada por lances verdadeiros. Suponha que o licitante i licite . ${\ displaystyle b_ {i}> v_ {i}}$

Nesse caso , o licitante ganharia o item com um lance verdadeiro e também com um lance excessivo. O valor do lance não altera o retorno, portanto, as duas estratégias têm recompensas iguais neste caso. ${\ displaystyle \ max _ {j \ neq i} b_ {j} <v_ {i}}$

Se, então, o licitante perderia o item de qualquer maneira, então as estratégias teriam recompensas iguais neste caso. ${\ displaystyle \ max _ {j \ neq i} b_ {j}> b_ {i}}$

Se então ao menos a estratégia de overbidding vencesse o leilão. O retorno seria negativo para a estratégia de overbidding porque eles pagaram mais do que o valor do item, enquanto o retorno para um lance verdadeiro seria zero. Assim, a estratégia de licitar mais alto do que a verdadeira avaliação de alguém é dominada pela estratégia de licitar com sinceridade. ${\ displaystyle v_ {i} <\ max _ {j \ neq i} b_ {j} <b_ {i}}$

A estratégia de licitação insuficiente é dominada por licitações verdadeiras. Suponha que o licitante i licite . ${\ displaystyle b_ {i} <v_ {i}}$

Se, então, o licitante perderia o item com um lance verdadeiro e também com um lance inferior, então as estratégias têm recompensas iguais para esse caso. ${\ displaystyle \ max _ {j \ neq i} b_ {j}> v_ {i}}$

Se, então, o licitante ganharia o item de qualquer maneira, então as estratégias teriam recompensas iguais neste caso. ${\ displaystyle \ max _ {j \ neq i} b_ {j} <b_ {i}}$

Se, então, apenas a estratégia de licitar com sinceridade vencesse o leilão. A recompensa para a estratégia verdadeira seria positiva, pois eles pagaram menos do que o valor do item, enquanto a recompensa para um lance inferior seria zero. Assim, a estratégia de licitação insuficiente é dominada pela estratégia de licitação verdadeira. ${\ displaystyle b_ {i} <\ max _ {j \ neq i} b_ {j} <v_ {i}}$

Os lances verdadeiros dominam as outras estratégias possíveis (underbidding e overbidding), portanto, é uma estratégia ideal.

Equivalência de receita do leilão Vickrey e leilão de primeiro preço selado

Os dois leilões mais comuns são o leilão de primeiro preço selado (ou lance alto) e o leilão de preço aberto crescente (ou inglês). No primeiro caso, cada comprador apresenta uma oferta lacrada. O licitante com lance mais alto recebe o item e paga seu lance. No último, o leiloeiro anuncia preços de venda sucessivamente mais altos e continua até que ninguém esteja disposto a aceitar um preço mais alto. Suponha que a avaliação de um comprador seja e o preço atual pedido seja . Se , então, o comprador perde ao levantar a mão. Se e o comprador não for o licitante atual, é mais lucrativo fazer um lance do que deixar outra pessoa ser o vencedor. Portanto, é uma estratégia dominante para um comprador sair da licitação quando o preço pedido atinge sua avaliação. Assim, tal como no leilão de segundo preço selado de Vickrey, o preço pago pelo comprador com a maior avaliação é igual ao segundo maior valor. ${\ displaystyle v}$${\ displaystyle b}$${\ displaystyle v <b}$${\ displaystyle v> b}$

Considere então o pagamento esperado no leilão de segundo preço selado. Vickrey considerou o caso de dois compradores e presumiu que o valor de cada comprador era um empate independente de uma distribuição uniforme com suporte . Com os compradores fazendo lances de acordo com suas estratégias dominantes, um comprador com avaliação ganha se o valor de seu oponente . Suponha que esse seja o valor alto. Em seguida, o pagamento vencedor é distribuído uniformemente no intervalo e, portanto, o pagamento esperado do vencedor é ${\ displaystyle [0,1]}$${\ displaystyle v}$${\ displaystyle x <v}$${\ displaystyle v}$${\ displaystyle [0, v]}$

${\ displaystyle e (v) = {\ tfrac {1} {2}} v}$.

Agora argumentamos que no leilão de primeiro preço selado, o lance de equilíbrio de um comprador com avaliação é ${\ displaystyle v}$

${\ displaystyle B (v) = e (v) = {\ tfrac {1} {2}} v}$.

Ou seja, o pagamento do vencedor no leilão de primeiro preço selado é igual à receita esperada no leilão de segundo preço selado.

Prova de equivalência de receita

Suponha que o comprador 2 dê um lance de acordo com a estratégia , onde é o lance do comprador para uma avaliação . Precisamos mostrar que a melhor resposta do comprador 1 é usar a mesma estratégia. ${\ displaystyle B (v) = v / 2}$${\ displaystyle B (v)}$${\ displaystyle v}$

Observe primeiro que, se o comprador 2 usar a estratégia , o lance máximo do comprador 2 é e, portanto, o comprador 1 ganha com probabilidade 1 com qualquer lance de 1/2 ou mais. Considere então um lance no intervalo . Deixe o valor do comprador 2 ser . Então, o comprador 1 ganha se , isto é, se . De acordo com a suposição de Vickrey de valores uniformemente distribuídos, a probabilidade de vitória é . O retorno esperado do comprador 1 é, portanto, ${\ displaystyle B (v) = v / 2}$${\ displaystyle B (1) = 1/2}$${\ displaystyle b}$${\ displaystyle [0,1 / 2]}$${\ displaystyle x}$${\ displaystyle B (x) = x / 2 <b}$${\ displaystyle x <2b}$${\ displaystyle w (b) = 2b}$

${\ displaystyle U (b) = w (b) (vb) = 2b (vb) = {\ tfrac {1} {2}} [{{v} ^ {2}} - {{(v-2b)} ^ {2}}]}$

Observe que atinge seu máximo em . ${\ displaystyle U (b)}$${\ displaystyle b = v / 2 = B (v)}$

Use em roteamento de rede

No roteamento de rede , os mecanismos VCG são uma família de esquemas de pagamento baseados no conceito de valor agregado . A ideia básica de um mecanismo VCG no roteamento de rede é pagar ao dono de cada link ou nó (dependendo do modelo de rede) que faz parte da solução, seu custo declarado mais seu valor agregado. Em muitos problemas de roteamento, esse mecanismo não é apenas à prova de estratégia , mas também o mínimo entre todos os mecanismos à prova de estratégia.

No caso de fluxos de rede, unicast ou multicast , um fluxo de custo mínimo (MCF) no gráfico G é calculado com base nos custos declarados d _k de cada um dos links e o pagamento é calculado da seguinte forma:

Cada link (ou nó) no MCF é pago ${\ displaystyle \ scriptstyle e_ {k}}$

${\ displaystyle p_ {k} = d_ {k} + MCF (G-e_ {k}) - MCF (G)}$,

onde MCF ( G ) indica o custo do fluxo de custo mínimo no gráfico G e G  -  e _k indica o gráfico G sem o link e _k . Links que não estão no MCF não são pagos. Esse problema de roteamento é um dos casos em que o VCG é à prova de estratégia e mínimo.

Em 2004, foi mostrado que o pagamento excessivo de VCG esperado de um gráfico aleatório Erdős-Rényi com n nós e probabilidade de borda p , se aproxima ${\ displaystyle \ scriptstyle G \ in G (n, p)}$

${\ displaystyle {\ frac {p} {2-p}}}$

à medida que n , se aproxima , para . Antes desse resultado, sabia-se que o pagamento excessivo de VCG em G ( n ,  p ) é ${\ displaystyle \ scriptstyle \ infty}$${\ displaystyle np = \ omega ({\ sqrt {n \ log n}})}$

${\ displaystyle \ Omega \ left ({\ frac {1} {np}} \ right)}$

e

${\ displaystyle O (1) \,}$

com alta probabilidade dada

${\ displaystyle np = \ omega (\ log n). \,}$

Generalizações

A generalização mais óbvia para bens múltiplos ou divisíveis é fazer com que todos os licitantes vencedores paguem o valor do lance não vencedor mais alto. Isso é conhecido como leilão de preço uniforme . O leilão de preço uniforme não resulta, no entanto, em licitantes oferecendo suas verdadeiras avaliações como fazem em um leilão de segundo preço, a menos que cada licitante tenha demanda por apenas uma unidade. Uma generalização do leilão Vickrey que mantém o incentivo para licitar com sinceridade é conhecida como mecanismo Vickrey – Clarke – Groves (VCG). A ideia no VCG é que os itens sejam atribuídos para maximizar a soma das utilidades; então, cada licitante paga o "custo de oportunidade" que sua presença apresenta a todos os outros jogadores. Este custo de oportunidade para um licitante é definido como o total de lances de todos os outros licitantes que teriam vencido se o primeiro licitante não tivesse licitado, menos o total de lances de todos os outros licitantes vencedores reais.

Um tipo diferente de generalização é definir um preço de reserva - um preço mínimo abaixo do qual o item não é vendido. Em alguns casos, definir um preço de reserva pode aumentar substancialmente a receita do leiloeiro. Este é um exemplo de projeto de mecanismo ótimo Bayesiano .

Veja também

• Teoria do leilão
• Leilão de lance selado de primeiro preço
• Leilão VCG

Referências

• Vijay Krishna, Auction Theory , Academic Press, 2002.
• Peter Cramton, Yoav Shoham, Richard Steinberg (Eds), Combinatorial Auctions , MIT Press, 2006, Capítulo 1. ISBN  0-262-03342-9 .
• Paul Milgrom, Putting Auction Theory to Work , Cambridge University Press, 2004.
• Teck Ho, "Consumo e Produção" UC Berkeley, Haas Class of 2010.

Notas