Marcelo Albuquerque Fernandes Más
PUC-Rio - Certificação Digital Nº 0420990/CB
U m E studo S obre L eilões de D em anda U nitária
D issertação de Mestrado
Dissertação apresentada como requisito parcial para obtenção do
g rau de M estre pelo P rog rama de P ós– g raduação em Informática
do Departamento de Informática da P U C – R io
O rientador: P rof. E duardo S any L aber
R io de J aneiro
S etembro de 2 0 0 6
Marcelo Albuquerque Fernandes Más
PUC-Rio - Certificação Digital Nº 0420990/CB
Um Estudo Sobre Leilões de Demanda Unitária
Dissertação apresentada como requisito parcial para obtenção do
grau de Mestre pelo Programa de Pós–graduação em Informática
do Departamento de Informática do Centro T écnico Cientı́fi co
da PUC–Rio. A prov ada pela Comissão Ex aminadora abaix o assinada.
P rof. Eduardo Sany Laber
Orientador
Departamento de Informática — PUC–Rio
P rof. Marcus V inı́cius Soledade P og g i de Arag ão
Departamento de Informática — PUC–Rio
P rof. C laudson Ferreira B ornstein
Univ ersidade F ederal do Rio de Janeiro — UF RJ
P rof. J osé Eug ênio Leal
Coordenador Setorial do Centro
T écnico Cientı́fi co — PUC–Rio
Rio de Janeiro, 06 de Setembro de 2006
Todos os direitos reservados. E´ p roib ida a rep rodu ç ão total
ou p arc ial do trab alh o sem au toriz aç ão da u n iversidade, do
au tor e do orien tador.
Marcelo Albuquerque Fernandes Más
PUC-Rio - Certificação Digital Nº 0420990/CB
G radu ou -se em E n g en h aria de C om p u taç ão p ela P U C -R io
(P on tifı́c ia U n iversidade C atólic a do R io de J an eiro) em 2 0 0 4 .
Tem in teresse n a p esq u isa de alg oritm os, esp ec ialm en te n as
áreas de G rafos e de Teoria de J og os, ten do p artic ip ado do
G R A C O 2 0 0 5 (II S im p ósio B rasileiro sob re G rafos, A lg oritm os e A n álise C om b in atória) A tu alm en te trab alh a n a M ic rosoft c om o E n g en h eiro de D esen volvim en to de S oftw are.
Ficha Catalográfica
Más, Marcelo Albuquerque Fernandes
Um estudo sobre leilões de demanda unitária / Marcelo
Albuquerque Fernandes Más; orientador: Eduardo Sany Laber.
— Rio de Janeiro : PUC–Rio, Departamento de Informática,
2006.
v., 8 2 f: il. ; 29 ,7 cm
1 . Dissertação (mestrado) - Pontifı́cia Universidade
Católica do Rio de Janeiro, Departamento de Informática.
Inclui referências bibliográficas.
1 . Informática – Tese. 2. Leilões Competitivos. 3 . Leilões
Reveladores. 4 . Algoritmos Aleatorizados. I. Laber, Eduardo
Sany. II. Pontifı́cia Universidade Católica do Rio de Janeiro.
Departamento de Informática. III. Tı́tulo.
C D D : 004
PUC-Rio - Certificação Digital Nº 0420990/CB
Agradecimentos
Gostaria de agradecer ao CNPq pela bolsa de estudos número
1 3 3 56 4/ 2004-5 concedida entre Agosto/ 2004 e Julho/ 2005 e à F APERJ pela
bolsa de estudos número E-26 / 1 51 .49 4/ 2005 concedida de Agosto/ 2005 a
Julho/ 2006 .
Resumo
PUC-Rio - Certificação Digital Nº 0420990/CB
Más, Marcelo Albuquerque Fernandes; Laber, Eduardo Sany. Um
E stu d o S o b re L e ilõ e s d e D e ma n d a Un itá ria . Rio de Janeiro, 2006. 8 2p. Dissertação de Mestrado — Departamento de Informática, Pontifı́cia Universidade Católica do Rio de Janeiro.
Este trabalho se concentra no desenvolvimento de mecanismos de leilões
reveladores aleatorizados que buscam max imizar simultaneamente a receita
e a efi ciência econômica, ou função social, de leilões de demanda unitária.
Em um leilão de demanda unitária, um conjunto de k bens é leiloado para
um conjunto de n consumidores, com a restrição de que nenhum consumidor
pode comprar mais de um bem. É apresentado um arcabouço para o
desenvolvimento de mecanismos reveladores aleatorizados de complex idade
polinomial derivados do mecanismo de V ick rey-Clark e-Groves, ou V CG.
Ao invés de utilizar preços de reserva, estas variantes do V CG utilizam
como parâmetro o número de bens que devem ser efetivamente vendidos.
Os mecanismos se diferenciam entre si pela maneira como é feito o cálculo do
número de bens que devem ser vendidos e permitem um balanço interessante
entre receita e efi ciência econômica, ao mesmo tempo que melhoram os
resultados teóricos alcançados para o problema de Leilões de Demanda
Unitária (09).
Palav ras– ch av e
Leilões Competitivos; Leilões Reveladores; Algoritmos Aleatorizados
Abstract
PUC-Rio - Certificação Digital Nº 0420990/CB
Más, Marcelo Albuquerque Fernandes; Laber, Eduardo Sany. A
Study on Unit-Demand Auc tions. Rio de Janeiro, 2006. 82p.
MsC Thesis — Department of Informática, Pontifı́cia Universidade
Católica do Rio de Janeiro.
This work focuses on the development of randomized truthful mechanisms
that seek to maximize both the revenue and the economic effi ciency, or
social welfare, of unit-demand auctions. In a unit-demand auction a set of
k items is auctioned to a set of n consumers and no consumer can purchase
more than one item. A framework is presented for devising polynomial-time
randomized truthful mechanisms that are based on a new variant of the
Vickrey-Clarke-Groves (VCG) mechanism. Instead of using reserve prices,
this variant of VCG uses the number of objects that we wish to sell as
a parameter. The mechanisms obtained diff er from each other in the way
they select the number of items to be sold and allow an interesting trade-off
between revenue and economic effi ciency, while improving upon the stateof-the-art results for the Unit-Demand Auction problem (09).
K eyw ords
Competitive Auctions; Truthful Auctions; Randomized Algorithms
PUC-Rio - Certificação Digital Nº 0420990/CB
Sumário
1 Introdução
1.1 Resultados Obtidos
1.2 Organização da Tese
11
14
15
2 Leilões
2.1 Leilões Unitários
2.1.1 Leilão Inglês
2.1.2 Mecanismo Ótimo de Rodada Única
2.1.3 Mecanismo V ick rey
2.2 Leilões de Múltiplos B ens
2.2.1 Leilões de B ens Digitais
2.2.2 Leilões Combinatórios G erais
2.2.3 Leilões do FCC
2.3 Leilões de Demanda Unitária
2.3.1 Mecanismo Ótimo
2.3.2 Mecanismo V CG
2.3.3 Um Mecanismo com G arantia de Receita
16
18
19
20
21
23
23
24
25
26
26
27
31
3 Modelagem por G rafos para Leilões de Demanda Unitária
3.1 Redes de Fluxo Unitárias
3.1.1 Redes Residuais
3.1.2 Caminh os Aumentantes
3.1.3 Fluxo Máximo
3.1.4 Fluxo de Custo Mı́nimo
34
37
40
41
41
42
4 N ovos Mecanismos para Leilões de Demanda Unitária
4.1 O Modelo
4.2 Resultados
4.3 Resultados Teóricos de G rafos
4.3.1 Emparelh amentos de Aproximação
4.4 Mecanismos Reveladores para Leilões de Demanda Unitária
4.4.1 Um Mecanismo Orientado à Receita
4.4.2 Favorecendo a Eficiência
46
46
47
48
49
51
54
57
5
Resultados Experimentais
5 .1 Ambiente de Testes
5 .2 Instâncias de Testes
5 .2.1 Resumo das Instâncias Criadas
5 .3 Emparelh amento Ótimo de Tamanh o Fixo
5 .3.1 Implementações B aseadas em Redes de Fluxo
5 .3.2 Usando o Método H úngaro
5 .3.3 Comparando os Algoritmos
5 .4 Calculando o Mecanismo V CG
5 .4.1 Modificação do Método H úngaro
61
61
61
62
64
64
64
66
67
67
5.4.2 Comparação
5.5 Calculando o Emparelhamento de Custo Máximo com Preço Único
5.5.1 Melhorias no Desempenho
5.6 Resultados dos Testes
5.6.1 Metodologia Utilizada
5.6.2 Resultados Utilizando as Versões Originais dos Mecanismos
5.6.3 Resultados Usando as Versões Modificadas dos Mecanismos
5.6.4 Leilões com Número Reduzido de Consumidores
70
71
72
74
74
75
76
77
6
79
Conclusões
PUC-Rio - Certificação Digital Nº 0420990/CB
Referências Bibliográficas
81
Lista de figuras
2.1
2.2
2.4
Lances são valores públicos e avaliações são valores privados.
O lucro de um consumidor é igual a sua avaliação pelo bem que
lhe foi alocado menos o preço pago pelo bem.
A arrecadação é igual à soma dos preços dos bens vendidos,
enquanto a eficiência econômica é dada pela soma das avaliações
de cada consumidor pelo conjunto de bens que lhe foi alocado.
Mecanismo Vickrey para o Exemplo 1
19
22
3.1
3.2
3.3
Utilizando grafos de fl uxo para modelar um leilão
Caminhos mais curtos sucessivos
Eliminação de ciclos negativos
40
44
44
4.1
Estrutura de FMLDU
53
5.1
5.2
5.3
5.4
5.5
Método húngaro Modificado – Passo 1
Método húngaro Modificado – Passo 2
Método húngaro Modificado – Passo 3
Método húngaro Modificado – Passo 4
Emparelhamento ótimo de preço único
68
69
69
69
72
PUC-Rio - Certificação Digital Nº 0420990/CB
2.3
17
18
Lista de tabelas
PUC-Rio - Certificação Digital Nº 0420990/CB
5.1
5.2
5.3
Parâmetros das classes
D escrição das meta-in stân cias
T emp o em ms p ara calcu lar emp arelhamen tos de cu sto máx imo
u tiliz an do o método hú n garo, o algoritmo de camin hos mais cu rtos
su cessiv os e o algoritmo de elimin ação de ciclos n egativ os
5.4 T emp o em ms p ara calcu lar os p reços do mecan ismo V CG u tiliz an do
o método hú n garo p adrão e o modificado
5.5 T emp o em ms p ara calcu lar os p reços do mecan ismo V CG u tiliz an do
o método hú n garo modificado e amb os algoritmos de redes de fl u x o
5.6 T emp o em ms p ara calcu lar alocações ótimas de p reço ú n ico u tiliz an do
a imp lemen tação p adrão e a melhorada
5.7 R eceita u tiliz an do as v ersões origin ais dos n ossos mecan ismos
5.8 E ficiên cia u tiliz an do as v ersões origin ais dos n ossos mecan ismos
5.9 R eceita u tiliz an do as v ersões modificadas dos n ossos mecan ismos
5.10 E ficiên cia u tiliz an do as v ersões modificadas dos n ossos mecan ismos
5.11 R eceita q u an do ex iste o mesmo n ú mero de b en s e con su midores
5.12 E ficiên cia q u an do ex iste o mesmo n ú mero de b en s e con su midores
63
63
67
70
71
74
75
76
76
77
78
78