Tomando Decisões Coletivamente... AKA Negociação!

Tomando Decisões Coletivamente... AKA Negociação!

Ao final desta aula a gente deveEntender 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

“É 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?

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çõesParticipantes

◦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çãoEleiçã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 candidatosImagine 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ática15

Eleições SequenciaisPodemos 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

LEILÕESMAIS UMA FORMA DE TOMAR DECISÕES COLETIVAS...

19

E se a gente for alocar recursos?

Leilões cada vez mais popularesAlocação de recursos escassosDesejados por vários agentesMecanismos de alocação

eficiente

20

LeilõesConjunto 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çõesPrivatização de estataisVender concessões de telefoniaDireito de exploração de petróleoContratos governamentais ou de

empresas de grande porteImóveis, gado, produtos agrícolas,

carros, peças de arte, antiguidadesVenda de commodities em bolsa

de valores

24

Quando usar leilões?

25

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 vendaPara prevenir acordos desonestos

entre vendedor e comprador

ConceitosVeremos as principais características de definição de leilões

Atores e suas funçõesLeiloeiro

◦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

LEILÕES DE UM ÚNICO ITEM

Já que vimos os principais conceitos, veremos agora os tipos de leilão mais conhecidos

Tipos de leilãoInglêsHolandêsAmericanoVickrey

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

VickreyCaracterí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 EsperadoCom 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 leiloeirosPara Leiloeiros Avessos ao Risco

◦English e Vickrey41

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/

Leilão

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

43

LEILÕES MÚLTIPLOSE quando os recursos vêm em Lotes?

44

Leilões CombinatóriosLeilõ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 VCGCada 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 MultiatributoMinimiza restrição perde-ganha

de negociação distributivaFunção de utilidade

◦Preferência do consumidor◦Características relevantes do

produto

47

Atuando em vários leilõesObtenção do menor preçoExploração de todos os

benefíciosTorna o mercado mais eficientePraticamente impossível para um

ser humano

48

Double AuctionsA iniciativa de lances parte tanto

do vendedor quanto do comprador

Utilizado em bolsas de valoresDefiniçã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õesO grande desafio é encontrar o

melhor produto pelo melhor preço◦Na internet a quantidade de opções

é imensaAcompanhar a evolução do leilão Gerenciar vários leilões ao

mesmo tempoDefinir o valor do lance quando

se está competindo com tantos compradores anônimos

51

Aplicação do paradigma de SMA a leilõesO 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çãoForma 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õesSão vários os tipos de leilãoLeilões são cada vez mais usados

em e-commercePara auxiliar os compradores

podemos usar agentesLeilões são úteis em SMA

também para alocação de tarefas e recursos

54