Tomando Decisões Coletivamente...
AKA Negociação!
Ao final desta aula a gente deve
Entender o conceito de Negociação e sua
utilidade para o design de SMA
 Compreender quando podemos aplicar a
ideia de votação
 Entender o que está envolvido em
participar de coalisões.

2
PARA COMEÇAR... O
QUE É NEGOCIAÇÃO
MESMO?
3
O que é Negociação?
“É um processo de tomada de decisão conjunta. É
comunicação, direta ou implícita, entre indivíduos
que estão tentando chegar a um acordo para
benefício mútuo. O significado original da palavra é
simplesmente fazer negócios, mas negociação é
também a atividade central na diplomacia, na
política, na religião, no direito, e na família. A
negociação engloba conversações de controle de
armas, a interpretação de textos religiosos e
disputas de guarda de crianças. Todos negociam.”
H. Raiffa
O que é Negociação?

Fundamental: resolver conflitos!
◦ forma de agentes self-interested chegarem a
um acordo sobre o emprego de seus recursos
e objetivos a atingir

Trocando em miúdos, que conflitos são
estes?
5
Para que negociar?

Recursos (disponibilidade)
◦ Exemplos
 Orçamento familiar
 Banco de dados distribuídos

Bens e valores (tangíveis e intangíveis)
◦ Exemplos
 Disputa de terras
 Compra de um produto no comércio eletrônico
 Leilões
6
Para que negociar?

Opiniões
◦ Falta visão do todo
◦ Exemplos
 Diplomacia e conflito familiar (pai-filho)
 Modelo de usuários em tutores inteligentes

Tarefas (coordenação de esforços)
◦ Requer descobrir as relações de dependência entre
o vários agentes
◦ Exemplos
 Desenvolvimento de um projeto (quem faz o que quando)
 Jogo de futebol, patrulha,...
7
Mercado
Um ambiente onde
vendedores e compradores se
encontram com o objetivo de
alocar recursos escassos
 Exemplo de modos negociação
possíveis em um mercado

8
Formas de negócio em um mercado
Um vendedor e um comprador negociam
diretamente (negociação bilateral)
 Muitos compradores e um vendedor
participam de um leilão clássico (negociação
multilateral 1-N)
 Muitos vendedores e um comprador
participam de um leilão invertido
(negociação multilateral N-1)
 Muitos compradores e muitos vendedores
formam um mercado (negociação
multilateral M-N)

9
TOMANDO DECISÕES
EM CONJUNTO VOTAÇÕES
10
Duas variáveis importantes a
considerar...

É possível tomar uma decisão em Grupo?
◦ Que objetivo queremos atingir?
◦ Que ponto de vista adotar?

Há recursos para todos?
◦ Como alocá-los?
11
Votações

Participantes
◦ Conjunto de Agentes, os eleitores
◦ Para já, vamos assumir um número impar de
eleitores
◦ Candidatos: as decisões que levam a estados
do mundo que tem utilidades bem definidas
para os agentes.
◦ Dado que cada agente tem uma ordem de
preferência para os candidatos, que ordem
devemos escolher?
12
Duas formas...

Função de Bem estar social
◦ Ranqueia os candidatos do preferido pela
maioria dos agentes até o preferido pelo
menor número
 Assume que os agentes são benevolentes...
 Pode não ser a melhor escolha, lembram?

Função de Escolha social
◦ O resultado é um candidato só.
13
Procedimentos de votação

Eleição
◦ Cada eleitor submete sua ordem de
preferência
◦ O vencedor é o preferido pela maioria dos
votantes.

Quando só há dois candidatos:
◦ Votação pela maioria absoluta

Se houver mais de dois...
◦ A coisa pode complicar!
14
Eleições com mais de dois
candidatos

Imagine que temos 3 candidatos C1, C2 e
C3
◦ Agente 1 prefere C1>C2>c3
◦ Agente 2 prefere C2>C1>C3
◦ Agente 3 prefere C3>C2>C1

O resultado aqui seria um empate... Mas...
◦ Quem quer que escolhêssemos, seria não
desejado pela maioria. (Paradoxo de
Condorcet)

Votação Tática
15
Eleições Sequenciais

Podemos organizar as eleições em pares
(como nos campeonatos): quem ganhar,
vai disputar outra eleição com o próximo
candidato
◦ Organização Linear
◦ Arvore Binária

A ordem das eleições influencia no
resultado!
16
Propriedades Relevantes dos
Mecanismos de Votação (I)

Condição de Pareto
◦ Se todos eleitores preferem um candidato A
ao candidato B, A deve ganhar de B na
votação.

Vencedor de Condorcet
◦ Se um candidato A ganhar de todos os outros
em uma eleição em pares, ele deve ser o
vencedor.
17
Propriedades dos Mecanismos de
Votação (II)

Independência de Alternativas Irrelevantes
◦ Não adianta introduzir candidatos
irrelevantes, o vencedor deve permanecer o
mesmo.

Ditaduras
◦ A preferência de um eleitor vence – não
importa que as preferências da maioria sejam
diferentes!
18
E se a gente for alocar recursos?
LEILÕES
MAIS UMA FORMA DE
TOMAR DECISÕES
COLETIVAS...
19
Leilões cada vez mais populares
Alocação de recursos escassos
 Desejados por vários agentes
 Mecanismos de alocação eficiente

20
Leilões

Conjunto de regras que definem:
◦
◦
◦
◦
Ganhador
Preço
Ofertas
Comportamento
21
Leilões
Importante mecanismo de vendas
 Permite a venda de objetos raros
 Ambiente simples e bem-definido

◦ Pode ser usados para testar hipóteses
◦ Base para trabalhos teóricos

Enorme volume de recursos transacionado através de leilões
◦ Crescimento imenso com a internet

Negociação intermediada
22
Leilões – da economia à negociação automática

Existem desde a História Antiga
◦ Venda do Império Romano
Estudos formais começaram nos anos 60
 Leilões em e-Commerce

◦ Desde 1995
 Antes disso havia leilões em newsgroups (1993)
◦ Em 1998 já havia mais de 500
◦ O que é vendido?
 Desde miniatura de star wars, a raros automóveis e
câmeras digitais
23
Aplicações
Privatização de estatais
 Vender concessões de telefonia
 Direito de exploração de petróleo
 Contratos governamentais ou de
empresas de grande porte
 Imóveis, gado, produtos agrícolas, carros,
peças de arte, antiguidades
 Venda de commodities em bolsa de
valores

24
Quando usar leilões?
Quando o problema é alocar recursos
 Quando a negociação é de um para muitos
 Quando a negociação é de muitos para um
 Quando se possui informações incompletas
 Quando se deseja rapidez de venda
 Para prevenir acordos desonestos entre
vendedor e comprador

25
Conceitos
Veremos as principais características de definição de
leilões
Atores e suas funções

Leiloeiro
◦ Receber os lances
◦ Gerar informações intermediárias
◦ Realizar a troca

Compradores (arrematantes)
◦ Dar lances
◦ Caso seja o vencedor, compra o produto
27
Alguns fatores alteram o
protocolo...

Valor público
◦ Ex.: uma nota de R$ 1,00

Valor privado
◦ Ex.: uma torta

Valor correlato
◦ Ex.: uma casa

Valor de reserva
◦ Preço mínimo pelo qual o produto será vendido
◦ Preço máximo que o comprador está disposto a pagar

Valor de venda
◦ Preço que se for atingido, automaticamente determina o vencedor
28
Tipos de lances

Open-Cry
◦ Order book
◦ Transaction history

Sealed Bid
◦ Não revelam informação
29
Mecanismo Utilizado

One-Shot
◦ Apenas um lance é dado

Crescente
◦ Lances começam baixos

Descendente
◦ Lances começam altos
◦ O valor pode aumentar, caso haja empate
30
Mecanismo de determinação de preço

Primeiro preço
◦ Ex.:Yahoo!, Arremate

Segundo preço
◦ Ex.: eBay
31
Mecanismo de determinação de encerramento do
Leilão

Temporal
◦ Ex.: eBay, Arremate

Por evento
◦ Ex.: Amazon
 Encerramento após 10 minutos sem lances
 Diminui as vantagens de dar lances de última hora
32
Já que vimos os principais conceitos, veremos agora os tipos
de leilão mais conhecidos
LEILÕES DE UM ÚNICO
ITEM
Tipos de leilão
Inglês
 Holandês
 Americano
 Vickrey

34
Leilões Ingleses (English Auctions)

Características
◦ Open Cry
◦ First Price
◦ Ascendente

Protocolo
◦ Leiloeiro começa sugerindo o valor de reserva
 Se ninguém der mais, o leiloeiro fica com o bem por esta valor
– pode ser 0
◦ Arrematantes dão lances
◦ Quando não houver mais lances, o bem fica com quem
deu o lance maior
35
Leilões Ingleses (II)

Que estratégia utilizar?
◦ Aumentar o lance em pequenos incrementos,
e depois se retirar quando o lance atingir seu
valor de reserva

Maldição do Vencedor
◦ Ganhou porque era bom ou porque ninguém
deu o mesmo valor ao bem??
36
Leilões Holandeses (Dutch)

Características
◦ Open Cry
◦ Descendente

Protocolo
◦ Leiloeiro começa ofertando o bem a um preço artificialmente
alto
◦ Leiloeiro vai decrementando o valor, até que algum arrematante
faça uma oferta
◦ Se houver empate o preço sobe
37
Leilões Holandeses

Que estratégia utilizar?
◦ Não há estratégias dominantes

Também sujeitos à Maldição do Vencedor
38
Americano

Características
◦
◦
◦
◦

First Price
Sealed Bid
One Shot
Só há um round
Que estratégia utilizar?
◦ Agente deve oferecer um pouco menos do que o
valor estimado... Mas quanto menos?
39
Vickrey

Características
◦
◦
◦
◦

Second Price
Sealed Bid
One shot
One round
Que estratégia utilizar?
◦ Oferecer o valor real da mercadoria
◦ Pode gerar comportamento anti-social ...
40
Lucro Esperado

Com compradores risk-neutral
◦ Os 4 tipos geram lucros parecidos para o
leiloeiro

Com compradores avessos ao risco (i.e.
querem garantir a compra)
◦ Dutch e First Price Sealed são os melhores para
os leiloeiros

Para Leiloeiros Avessos ao Risco
◦ English e Vickrey
41
Mentiras e Conluios
Nada impede que os compradores se juntem...
 Uma solução...

◦ Impedir os compradores de se identificarem...

Mas o leiloeiro também pode ser desonesto!
◦ Shills
◦ Troca de valores – em leilões Vickrey, principalmente

Contra-especulação...
42
Comparação
Característica/
Lance
Mecanismo
Preço
Maldição do
vencedor
Inglês
Open cry
Ascendente
First price
Sim
Holandês
Open cry
Descendente
Fisrt price
Sim
Vickrey
Sealed
bid
One shot
Second
price
Não
Americano
Sealed
bid
One shot
Fisrt price
Não
Leilão
43
E quando os recursos vêm em Lotes?
LEILÕES MÚLTIPLOS
44
Leilões Combinatórios
Leilões de conjuntos de itens (que podem
ou não ser homogêneos)
 Cada agente tem uma função de avaliação
dos conjuntos de bens
 Como maximizá-la para todos os agentes?

45
Mecanismo VCG
Cada agente tem que pagar à sociedade
um incentivo – a diferença entre a
utilidade sem ele e com ele
 Para o caso de só haver um bem no
conjunto, podemos mostrar que este
leilão combinatório vira um Vickrey.

46
Leilões Multiatributo
Minimiza restrição perde-ganha de
negociação distributiva
 Função de utilidade

◦ Preferência do consumidor
◦ Características relevantes do produto
47
Atuando em vários leilões
Obtenção do menor preço
 Exploração de todos os benefícios
 Torna o mercado mais eficiente
 Praticamente impossível para um ser
humano

48
Double Auctions
A iniciativa de lances parte tanto do
vendedor quanto do comprador
 Utilizado em bolsas de valores
 Definição do preço:

◦ Valor médio
◦ Valor do lance de compra
◦ Valor do lance de venda
49
SÓ PARA FECHAR....
50
Aplicação do paradigma de SMA a
leilões

O grande desafio é encontrar o melhor
produto pelo melhor preço
◦ Na internet a quantidade de opções é imensa
Acompanhar a evolução do leilão
 Gerenciar vários leilões ao mesmo tempo
 Definir o valor do lance quando se está
competindo com tantos compradores
anônimos

51
Aplicação do paradigma de SMA a
leilões
O mecanismo de leilão pode ser visto
como a solução para o problema da
alocação de recursos ou tarefas a um
conjunto de agentes
 Leilões podem ser vistos como um
processo de negociações automáticas
implementada como uma rede de agentes
inteligentes

◦ Vendedores e compradores interagem num
mercado eletrônico
52
Leilão é uma negociação
Forma de Negociação cada vez mais
comum... Por ser um cenário de interação
simples!
 Sendo assim, possui três elementos
principais

◦ O protocolo
◦ O objeto a ser acordado
◦ A estratégia do agente
53
Conclusões
São vários os tipos de leilão
 Leilões são cada vez mais usados em ecommerce
 Para auxiliar os compradores podemos
usar agentes
 Leilões são úteis em SMA também para
alocação de tarefas e recursos

54