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 com interesses próprios chegarem a
um acordo sobre o emprego de seus recursos e
objetivos a atingir
Trocando em miúdos, que conflitos são estes?
2
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

3
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,...

4
MERCADO
 Um
ambiente onde
vendedores e
compradores se
encontram com o
objetivo de vender e
comprar
 Exemplo de modos
de compra possíveis
em um mercado
5
FORMAS DE COMPRA 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)
6
“Processo de tomada de decisão conjunta entre dois
negociantes. É comunicação, direta ou implícita,
entre indivíduos que estão tentando chegar a um acordo
para benefício mútuo” (H. Peyton Young)
NEGOCIAÇÃO BILATERAL
CONCEITOS ENVOLVIDOS EM UMA
NEGOCIAÇÃO BILATERAL
Comprador
• Você tem o novo CD do U2?
• Você poderia fazer por 15?
• Sim e ele custa 20 reais!
Vendedor
• Não, mas posso fazer por 17.
• Fechado!
8
CONCEITOS ENVOLVIDOS EM UMA
NEGOCIAÇÃO BILATERAL
Vendedor
Comprador
• Você tem o novo CD do U2?
• Sim e ele custa 20 reais!
• Você poderia fazer por 15
• Não, mas posso fazer por 17.
• Fechado!
Jogadores
Proposta
Bem em Negociação
Ações
9
CONCEITOS ENVOLVIDOS
EM UMA
Intervalo de Acordo
NEGOCIAÇÃO BILATERAL
Comprador
15
18
Fluxo Vendedor
Fluxo Comprador
17
15
20
Vendedor
Valores de Reserva
20
10
PROBLEMAS DE MODELAGEM DE
UMA NEGOCIAÇÃO BILATERAL
PROBLEMAS DE MODELAGEM DE UMA
NEGOCIAÇÃO
 Avaliando
os modelos de negociação
 Identificamos 4 problemas comuns
Como modelar as proposta?
Como avaliar uma proposta?
Quais são as possíveis ações do agente?
Como o agente decide o que fazer?
12
COMO MODELAR AS PROPOSTAS?
 Objetivo

definir a representação estruturada do bem em
negociação
 Quais
atributos descrevem uma proposta?
 Qual a natureza destes atributos?


características do produto (cor, tamanho, etc.)
característica da proposta em si (preço, tempo
de entrega, etc.)
13
COMO AVALIAR UMA PROPOSTA?
 Objetivo

dar capacidade ao agente de comparar duas
propostas
 Caso
a proposta tenha mais de um atributo,
eles tem a mesma importância?

pesos para cada atributo; pesos para cada tipo de
atributo
 Qual

o conjunto de classificação de proposta?
conjunto numérico [0; 1]; conjunto discreto (ruim,
bom, muito bom)
 Como

mapear uma proposta neste conjunto?
teoria da utilidade?
14
QUAIS SÃO AS POSSÍVEIS AÇÕES DO
AGENTE?

Objetivo


As ações básicas de um agente negociador são


determinar o grau de autonomia do agente negociador
aceitar uma proposta; rejeitar/gerar contraproposta; sair
Além destas o agente poderia




enviar ultimato
sugerir um produto alternativo
mudar quantidade do bem em negociação
...
15
COMO O AGENTE DECIDE O QUE FAZER?
 Objetivo:
 Definir as regras de comportamento do agente
 Quais são as informações que o agente pode
utilizar para tomar sua decisão?





propostas do oponente
propostas feitas por ele
Momento da negociação
negociações realizadas (mesmo oponente ou produto)
...

que condições implicam em ações
 Como
estas informações são mapeadas em
ações?
16
MODELOS DE NEGOCIAÇÃO BILATERAL
FRAMEWORK COMUM
Modelo de referência: Peyman Faratin!
 Modelo das propostas


atributos que caracterizam uma proposta e podem ser
negociados


ex.: preço, tempo de entrega, etc.
cada atributo possui o seu intervalo de acordo
ex.: preço [100 reais; 300 reais]
 tempo de entrega [1 dia; 3 dias]

18
FRAMEWORK COMUM
 Avaliação
da propostas: função de utilidade
para múltiplos atributos
preço
Proposta P
preço
imposto
temp.
imposto
temp.
wpreço
wimposto

Aval [0; 1]
wtemp.
1
Funções de aval. de atrib.
19
0
15
20
GERAÇÃO DE PROPOSTAS
 Táticas dependentes de Tempo
 Ideais para negociações com limites
conseguir um acordo
 Ex.: polinomial, exponencial
de tempo para
 Táticas dependentes de comportamento
 Ideal para negociação sem um limite rígido para
conseguir um acordo.
 O Agente pode imitar o comportamento do oponente e
conseguir “sempre” um melhor acordo
 Ex.: Tit-for-tat
 Táticas dependentes de recurso
 Ideal para ambientes com recursos limitados.
 Ex. pequeno número de vendedores
20
AÇÕES

Mecanismo de decisão




Recebe a proposta R
Gera um proposta G seguindo a tática
Compara as propostas R e G
Ações

Aceitar


Rejeitar + contraproposta


se R é pior do que G e envio G
Ultimatum


se R é melhor do que ou equivalente a G e fim
se o tempo expirou
Desistir
se meu valor de reserva foi ultrapassado
 ou o tempo acabou sem acordo

21
MODELOS DE NEGOCIAÇÃO BILATERAL
Kasbah
Representação único atributo
(preço)
da Proposta
Faratin
RAP
múltiplos atributos múltiplos atributos
(produto + acordo)
Avaliação da
Proposta
preço representa
a avaliação de
proposta
combinação
ponderada dos
atributos
Idem Faratin
Possíveis
Ações
aceitar, sair
rejeitar/gerar
contraproposta
Idem Kasbah
Idem Kasbah +
ultimato + sugestão
produto alternativo
comparação
Idem Kasbah
entre propostas
recebida e gerada
dependentes de
Contraproposta dependentes de
tempo
tempo/comportam.
recurso
Tomada de
Decisão
Idem Faratin, mas
muda em ultimato
22
dependentes de
tempo/comportam.
recurso
LEILÕES
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

24
ALGUNS FATORES ALTERAM O
PROTOCOLO...

Valor público


Valor privado


Ex.: uma casa
Valor de reserva



Ex.: uma torta
Valor correlato


Ex.: uma nota de R$ 1,00
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
25
TIPOS DE LANCES

Open-Cry
Order book
 Transaction history


Sealed Bid

Não revelam informação
26
MECANISMO UTILIZADO

One-Shot


Crescente


Apenas um lance é dado
Lances começam baixos
Descendente
Lances começam altos
 O valor pode aumentar, caso haja empate

27
MECANISMO DE DETERMINAÇÃO DE
PREÇO

Primeiro preço


Ex.: Yahoo!, Arremate
Segundo preço

Ex.: eBay
28
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

29
TIPOS DE LEILÃO
Já que vimos os principais conceitos, veremos
agora os tipos de leilão mais conhecidos
TIPOS DE LEILÃO
Inglês
 Holandês
 Americano
 Vickrey

31
LEILÕES INGLESES (ENGLISH AUCTIONS)

Características
Open Cry
 First Price
 Ascendente


Que estratégia utilizar?


Aumentar o lance em pequenos incrementos, e depois se
retirar
Maldição do Vencedor
32
LEILÕES HOLANDESES (DUTCH)
 Características


Open Cry
Descendente
 Que

estratégia utilizar?
Não há estratégias dominantes
O
preço começa alto e vai diminuindo, até
que haja apenas um lance, se houver mais
de um, o preço sobe
 Também sujeitos à Maldição do Vencedor
33
AMERICANO

Características
First Price
 Sealed Bid
 One Shot


Que estratégia utilizar?

Agente deve oferecer um pouco menos do que o valor
estimado... Mas quanto menos?
34
VICKREY

Características
Second Price
 Sealed Bid
 One shot


Que estratégia utilizar?
Oferecer o valor real da mercadoria
 Pode gerar comportamento anti-social ...

35
ARGUMENTAÇÃO

Problemas com Negociação Tradicional
Não se pode justificar escolhas
 Não se pode mudar de idéia
 Parte do princípio que agentes tem uma visão
perfeita do todo!

36
DIFERENTES ABORDAGENS PARA FINS
DIFERENTES...

Negociando bens e valores e tarefas
Negociação Bilateral
 Leilões


Influenciando o oponente

Argumentação
Baseada em Lógica
 Baseada em Diálogos

37
CONSTRUINDO UM ARGUMENTADOR
Mecanismos para enviar propostas
 Técnicas para avaliar propostas



Qual a utilidade da proposta recebida?
Mecanismos para gerar/responder propostas

Como melhorá-la?
38
ARGUMENTAÇÃO BASEADA EM LÓGICA
 Base
|- (sentença, Justificativas)
 Base é um conjunto de sentenças acordadas
pelos agentes.
 Argumentos podem ser contra ou a favor uma
determinada proposição.
 Dois tipos básicos de argumento
Não trivial – derivado de um conjunto consistente de
justificativas
 Tautológico – se o conjunto de justificativas é vazio

39
DIÁLOGOS PARA ARGUMENTAÇÃO
Um diálogo pode ser visto como uma série de
contribuições – argumentos
 Cada contribuição... Um movimento

Um diálogo é uma seqüência de turnos
 Cada turno apresenta um argumento diferente
 Argumento corrente derruba o anterior
 Diálogo termina quando não é mais possível argumentar.

40
ROTEIRO

Agentes Trabalhando Juntos
Resolução Cooperativa de Problemas Distribuídos
 Compartilhamento de Tarefas e Resultados
 Compartilhamento de Tarefas Usando Contract-Net
 Funcionamento do Contract-Net


Coordenação em SMA
O Que é Coordenação
 Quando Ações Devem Ser Coordenadas
 Relações Entre Ações
 Algumas Formas de Coordenação

AGENTES TRABALHANDO JUNTOS
Como desenvolver agentes que podem trabalhar
juntos de maneira eficiente?
 O conceito de cooperação de SD é suficiente?

Não !
 Agentes devem agir de maneira “estratégica”: agentes
heterogêneos, interesses próprios (diferentes
objetivos), etc.
 Autonomia dos agentes !


Agentes que trabalham juntos devem
compartilhar Tarefas, Informações e
Coordenar Atividades
RESOLUÇÃO COOPERATIVA DE PROBLEMAS
DISTRIBUÍDOS
Agentes com diferentes habilidades trabalhando
juntos de maneira a resolver problemas que estão
além das suas capacidades individuais
 Assume existência de agentes benevolentes:

Sempre compartilham mesmos objetivos (não há
espaço para conflitos)
 Ajudam sempre que necessário


No entanto, a área de sistemas multi-agentes
estuda sociedade de agentes autônomos, com
interesses próprios !

Pergunta chave: por que e como agentes cooperam?
RESOLUÇÃO COOPERATIVA DE PROBLEMAS
DISTRIBUÍDOS

Decomposição do problema
Decomposição hierárquica até atingir granularidade
desejada
 Escolher mecanismo de decomposição
 Capacidade dos agentes deve ser conhecida


Solução do sub-problema
Sub-problemas resolvidos individualmente
 Agentes podem compartilhar informações


Síntese da solução

Soluções individuais integradas hierarquicamente em
apenas uma
COMPARTILHAMENTO DE TAREFAS E
RESULTADOS

Problema decomposto em sub-problemas menores
alocados para agentes diferentes

Alocação das tarefas depende da arquitetura dos
agentes:
Caso mais simples: agentes com mesmas habilidades e sem
autonomia
 Estabelecimento de acordos: agentes com habilidades
distintas e autônomos


Agentes compartilhando informações relevantes
para resolução de sub-problemas
Pró-ativa: Agente envia informação por acreditar que
essa informação auxiliará outro agente
 Reativa:Agente envia informação como resposta a
uma solicitação

EXEMPLO: CONSTRUÇÃO DE EDIFÍCIO
Construtor
Solicita análise de solo
para construção
apropriada das fundações
Carregador de material
Analisador de so
EXEMPLO: CONSTRUÇÃO DE EDIFÍCIO
Construtor
Analisador de so
Resultado da análise de
solo
Carregador de material
EXEMPLO: CONSTRUÇÃO DE EDIFÍCIO
Construtor
Solicita material
Carregador de material
Analisador de so
EXEMPLO: CONSTRUÇÃO DE EDIFÍCIO
Construtor
Entrega material
Carregador de material
Analisador de so
COMPARTILHAMENTO DE TAREFAS
USANDO CONTRACT-NET

Protocolo de alto nível voltado para obtenção de
uma estratégia de cooperação eficiente
Desenvolvido por R. G. Smith em 1979 e baseado em
protocolos de mercado público
 Visa o compartilhamento de tarefas entre vários
agentes


Composto por 4 etapas:

Anuncio da tarefa, encaminhamento de proposta,
análise das propostas e emissão do “contrato”
FUNCIONAMENTO DO CONTRACT-NET
(1) Agente
reconhece
existência de
tarefa que não
pode
desempenhar
sozinho
FUNCIONAMENTO DO CONTRACT-NET
(2) Agente
anuncia a tarefa
para os demais
agentes
FUNCIONAMENTO DO CONTRACT-NET
(2) Agentes
enviam suas
FUNCIONAMENTO DO CONTRACT-NET
(3) Propostas
recebidas são
analisadas e a
melhor é
escolhida
(4) Uma proposta
é escolhida e o
contrato é emitido
COORDENAÇÃO EM SMA

O que acontece quando agentes possuem ações
inter-dependentes?

Necessário gerenciar inter-dependências !
Mecanismos de coordenação são essenciais
quando agente possuem atividades que
interagem entre si
 Exemplos de atividades:

Duas pessoas tentando sair de uma sala por uma
porta estreita
 Funcionário precisa de assinatura de gerente para
enviar um documento
 Aluno A encontra artigo de interesse de B e
encaminha-o (atividade pró-ativa)

ENTÃO, O QUE É COORDENAÇÃO?
Quando agentes trabalham juntos é necessário
gerenciar algumas tarefas complementares
 Tarefas de coordenação:



Fazem parte do sistema organizacional e possibilitam
a execução das tarefas produtivas
Então, coordenação é o conjunto de tarefas
suplementares que devem ser executadas
em um SMA, as quais não seriam
necessárias caso existisse apenas um único
agente
QUANDO AÇÕES DEVEM SER
COORDENADAS?

Informações e resultados disponíveis apenas
através de outros agentes


Recursos limitados


Tempo, espaço, dinheiro, ferramentas ...
Otimização de custos


Ex.: Agente construtor precisa que alguém lhe
forneça material
Eliminação de tarefas desnecessárias e redundantes
Agentes com objetivos inter-dependentes
cooperando entre si

Ex.: Dois agentes trabalhando no mundo dos blocos
(sem competição!)
RELAÇÕES ENTRE AÇÕES
Algumas ações quando executadas
simultaneamente podem levar a conflitos ou
aumento da performance
 Relações negativas: impossibilitam a execução
de algumas ações



Relações positivas: favorecem ações fazendo
com que uma se beneficie de outra


Incompatibilidade de objetivos, limitação de recursos
Maior eficiências do que se ações fossem executadas
independentemente
Em SMA, coordenação acontece em tempo de
execução

Agentes devem reconhecer relações e tratá-las
RELAÇÕES ENTRE AÇÕES
Relações
Entre Ações
Relações
Negativas
Conflito de
Recursos
Recursos
Consumíveis
Incompatibilidad
e de Objetivos
Recursos Não
Consumíveis
Relações
Positivas
Relação de
Igualdade
Relação de
Favor
Relações de
Conseqüência
ALGUMAS FORMAS DE COORDENAÇÃO

Coordenação via Sincronização
Maneira mais simples e limitada de coordenação
(originária de SD)
 Descreve precisamente a seqüência de ações
concorrentes


Coordenação via Planejamento
Fases de elaboração de planos e execução do plano
escolhido
 Limitados com relação a eventos não previstos e
situações muito complexas


Coordenação Reativa

Não existe fase de planejamento, fazem uso do ciclo
percepção-ação do agente
SINCRONIZAÇÃO DE AÇÕES

Definir a relação de tempo existente entre as
ações de modo que:
Sejam executadas na ordem correta
 Produzam o resultado esperado

Deve ser aplicada quando o objetivo é prover
coerência e evitar interferência entre ações
 Situações típicas:


Sincronização de movimentos


Ex.: dois agentes andando de bicicleta
Sincronização para acesso a recurso

Ex.: controle de acesso a uma máquina
COORDENAÇÃO VIA PLANEJAMENTO

Problema de planejamento em SMA é mais
complexo do que o caso tradicional
Ações de vários agentes devem ser levadas em
consideração
 Maior necessidade de replanejamento
 Maior interdependência entre ações, dificultando
ordenamento das ações, etc...


Em SMA, planejamento pode se quebrado em 3
fases:

Elaboração de planos, sincronização/coordenação e
execução de planos
MODOS DE PLANEJAMENTO

Planejamento centralizado para múltiplos
agentes


Único agente responsável por elaborar plano
Coordenação centralizada para planos
parciais
Tarefa de elaboração de plano distribuída
 Único agente responsável for sincronizar/coordenar
sub-planos


Coordenação distribuída para planos
parciais
Tarefa de elaboração de plano distribuída
 Cada agente deverá ter a iniciativa de sincronizar
seu sub-plano com os demais agentes

PLANEJAMENTO CENTRALIZADO PARA
MÚLTIPLOS AGENTES
Apenas um agente capaz de planejar e organizar
ações para todos os agentes
 Demais agentes são simplesmente executores de
planos
 Construção do plano composta por 3 etapas:

Encontrar um plano parcial geral
 Determinar pontos do plano que podem ser
executados em paralelo (Identificação de sub-planos)
 Incluir pontos de sincronização
 Alocar os sub-planos para os demais agentes

PLANEJAMENTO CENTRALIZADO PARA
MÚLTIPLOS AGENTES
Coordenador do plano
Plano
Plano
Plano
Executor
Executor
Plano
Executor
Executor
COORDENAÇÃO CENTRALIZADA PARA
PLANOS PARCIAIS
Apenas a etapa de coordenação é centralizada
 Cada agente desenvolve seu próprio plano parcial
e o encaminha para o coordenador
 Coordenador tenta sintetizar todos os sub-planos
em um único plano coerente



Identificar conflitos e eliminá-los via ordenação de
ações ou inclusão pontos de sincronização
Coordenador capaz de identificar tanto relações
positivas quando negativas
COORDENAÇÃO CENTRALIZADA PARA
PLANOS PARCIAIS
Coordenador
Plano coordenado
Obj. A
Obj. D
Plano parcial
Obj. B
Planejador
/
Executor
Planejador
/
Executor
Obj. C
Planejador
/
Executor
Planejador
/
Executor
COORDENAÇÃO DISTRIBUÍDA PARA
PLANOS PARCIAIS

Não existe o papel de coordenador em nenhuma
das etapas
Cada agente planeja individualmente as ações que
deseja executar de acordo com seus objetivos
 Maior dificuldade é identificar relações entre as ações
que compõem os diversos sub-planos
 Agentes devem trocar informações sobre os seus
planos e objetivos

COORDENAÇÃO DISTRIBUÍDA PARA
PLANOS PARCIAIS
V. Lesser e E. Durfee desenvolveram o modelo
Partial Global Planning (PGP)
 PGP é uma estrutura contendo informações sobre
os planos do agente, seu objetivos, custos
associados, resultados esperados, etc.
 Agentes trocam PGP e tentam identificar:

Agentes cujos objetivos façam parte de um objetivo de
grupo
 Planos que possam ser combinados

COORDENAÇÃO DISTRIBUÍDA PARA
PLANOS PARCIAIS
Obj. A
Pedidos, informações
e planos parciais
Executor/
Planejador
Obj. B
Executor/
Planejador
Obj. C
Executor/
Planejador