Agentes que Negociam...





Negociação... O que é?
Utilidades... E Estratégias
Equilíbrio de Nash
Negociando de acordo com a Utilidade
Negociando Recursos


Leilões
Cenas dos Próximos Capítulos
1
Algumas Observações
Importantes



“Não há SMA de um só agente...”
Diferentes agentes tem diferentes
influências no ambiente... Lembram da
figurinha?
Agentes estão conectados por relações
(muitas vezes de dependência), e têm
objetivos próprios.
2
Recordando...
Interação
Objetivos
Recursos
Habilidades
Independência
Compatíveis
Suficientes
Suficientes
Colab. Simples
Compatíveis
Suficientes
Insuficientes
Colab.
Coordenada
Compatíveis
Insuficientes
Insuficientes
Obstrução
Compatíveis
Insuficientes
Suficientes
Compet. Indiv.
Incompatíveis
Suficientes
Suficientes
Compet. Coletiva
Incompatíveis
Suficientes
Insuficientes
Conflito Recursos Incompatíveis
Insuficientes
Suficientes
Conflito Coletivo
Insuficientes
Insuficientes
Incompatíveis
3
Voltando ao tema...

O problema da negociação...


De Tarefas
De Recursos
4
Negociando...

De acordo com o Aurélio...


Negociar significa manter relações para
concluir tratados ou convênios
Para SMA...

Negociação é uma forma de interação entre
agentes self-interested. Em outras palavras,
é o processo de conseguir um acordo para
cooperação entre agentes buscando seus
objetivos pessoais.
5
Negociamos ...

Para Determinar




A distribuição das Tarefas
A distribuição dos Recursos
A coordenação das atividades
Entre


Dois Agentes
Entre múltiplos agentes
6
O Processo deve Ser

Eficiente


Em geral, os agentes ficam “mais felizes” depois da
negociação
Estável

Racionalidade Individual


Racionalidade de grupo


Deve ser preferível atuar em grupo
É melhor participar deste grupo do que de outro
Racionalidade de coligação

Ninguém quer sair da coligação
7
O Processo deve Ser... II

Distribuído


Simétrico



Um coordenador central pode ser um gargalo
de desempenho
Atributos irrelevantes não devem influenciar
na decisão
Rápido
Simples
8
Como possibilitar?

Precisamos definir...



A linguagem utilizada pelos participantes
Como cada um decide suas posições?
Os Protocolos seguidos pelos agentes.
9
Duas Abordagens principais

Baseada em Teoria dos Jogos




Análise das Situações
Determina precisamente uma estratégia
Hipóteses Restritas
Baseada em Guias


Teorias Informais
Não há hipóteses restritivas
10
Alguns Conceitos Básicos
Representando Preferências

Função de Utilidade


i e j são dois agentes
 = {1, 2,...,n}

x é um estado do mundo.
As preferências dos agentes são capturadas
pela função de utilidade.
i :   j :  

12
Por exemplo...



Imagine que eu seja um agente querendo
ir prá casa.
1 = chego em casa em 20min
2 = pego a caxangá e chego em 1 hora... 


Em qual dos casos eu fico mais feliz?
Definimos uma função de utilidade
i (1 ) = 10 i (2 ) = 1
13
Num encontro Multiagente...

Um avião está indo para Índia quando é
seqüestrado e pousa no Paquistão. Os seqüestradores querem liberar 800 prisioneiros das
prisões indianas. (A = acordo, E = Explodir, R
= Resgate)
g(A,A) = 2 g(A,E) = -2 g(R,A) =0 g(R,E )= -3
s(E,A) = -1 s(E,R) = 0 s(A,A) =2 s(E,R)= 0
O que você faria no lugar do governo indiano?
14
Matriz de Recompensa
g
Acordo
Resgate
s
Acordo
2
2
Explode
0
0
-2
-1
0
-3
15
Uma forma de Decidir

Estratégias Dominantes


Uma estratégia 1 domina 2 para o agente
i se todo o elemento de 1 é preferido a
todos os elementos de 2.
1 domina fortemente 2 se 1  1 , 2
 2 , 1 >i 2
16
Estratégias Dominantes..II


Nem sempre teremos estratégias
fortemente dominantes! As vezes
precisamos ter estratégias fracamente
dominantes.
Uma estratégia 1 domina fracamente 2
todo o elemento de 1 é tão preferido
quanto os elementos de 2.

1  1 , 2  2 , 1 i 2
17
Equilíbrio de Nash

Duas estratégias estão em EN se:



Considerando que agente i executa S1 agente
j não pode fazer melhor que executar S2.
Considerando que o agente j vai executar S2 i
não pode fazer melhor que S1
No equilíbrio, os agentes não têm incentivo
de se desviar... O problema é que nem todas
as situações tem EN. E algumas situações
têm mais de um EN.
18
Pensando mais um pouco...

Interações estritamente Competitivas...

Quando temos dois agentes i e j, onde um i
prefere um estado 1 sss j prefere 2.


Interações de soma Zero.



1 i 2 se e somente se 2 j 1
Quando a i (1) + j (1) = 0
Ex. um jogo de xadrez
Vamos ver um exemplo?
19
Um Problema Famoso...

O dilema do Prisioneiro



Dois homens são acusados de um crime e
mantidos incomunicáveis. Se um confessar e
outro não – um vai ser livre e o outro preso
por 3 anos
Se ambos confessarem ambos serão presos
por dois anos
Se nenhum confessar ambos serão presos
por um ano.
20
Recompensas...
i
confessa
Cala
j
confessa
2
2
Cala
0
5
5
0
3
3
21
Decidindo o que fazer...



Se eu calar, a maior recompensa é zero
Se eu confessar, o a maior recompensa
é dois...
Então... É melhor confessar!
22
Voltando para a questão...

Alguns Conceitos básicos de Negociação

Conjunto de Negociação


Protocolo


Define que propostas são as legais
Coleção de Estratégias


Conjunto das propostas que valem a pena fazer
Normalmente a estratégia dos agentes é privada
Regra de Acordo

Define quando o consenso é atingido
23
Alocando Tarefas...
Domínios Orientados a
Tarefas

Representados por uma tupla <T,Ag,C>



T é o conjunto de todas as tarefas
Ag = {1,..,n} é o conjunto de participantes
C é a função de custo para cada subconjunto
de tarefas.


A função de custos é monotônica
O custo de fazer nada é zero
25
Acordos... (Deals)


Um acordo é uma alocação de tarefas.
A utilidade do acordo  é a diferença
entre o custo das tarefas que o agente
faria inicialmente (Ti) e as tarefas que
lhe foram atribuídas.


Utilityi() n= c(Ti) –c(i)
Se os agentes não chegarem a um acordo
temos o conflict deal.

Cd = <Ti, Tj>
26
Mais sobre acordos

Um acordo 1 domina 2 se




1 domina fracamente 2 se a primeira condição se
verifica.
Um acordo que não é dominado por nenhum outro é
chamado de pareto-optimal.


1 é tão bom quanto 2 para todos os agentes.
1 é melhor que 2 para algum agente.
Assim, está na hora de parar de negociar!!!
 é individual racional se domina fracamente o
acordo de conflito. Caso contrário, há pelo menos
um agente que se sairia melhor com o acordo de
27
conflito.
Esquematicamente
Acordos do conjunto
de negociação
Utilidade do Cd para i
Cd
Utilidade do Cd para j
28
Assim...

O conjunto de possibilidades a colocar
em negociação consiste nos conjuntos
de acordos que são


Individual racional
Pareto ótimo
29
Um Protocolo Famoso... A
Contract net


A1 reconhece que tem um problema
A1 anuncia que precisa de um serviço




Pode envolver um broadcast geral... Um
limitado... Ou um contato direto.
Ai,...,Aj respondem, oferecendo seus
préstimos.
A1 contrata o serviço, via award.
Quando o contratado termina, envia um
relatório ao contratante.
30
Quando recebemos as
mensagens...

Processando um anúncio...



Agente decide se é candidato...
Guarda os detalhes da tarefa, para
poder competir por elas...
Processando a oferta

Gerentes guardam as ofertas até o
deadline. Depois a tarefa é alocada a um
competidor.
31
Quando recebemos as
mensagens...

Processando o Award


Ganhador começa os procedimentos para
executar a tarefa.
Requerimentos e Informação

O conteúdo que chega é adicionado à
base de conhecimento do agente.
32
No entanto...


A Contract Net assume um ambiente
cooperativo... O que nem sempre ocorre!
Um problema de alocação tem...




Um conjunto de agentes
Um conjunto de tarefas
Uma função de custo
Uma alocação inicial
33
Alocando Tarefas



Um contratante passa a tarefa a frente se
o que ele tem que pagar é menos que o
custo de fazê-la sozinho
Um contratado aceita uma tarefa se a
recompensa é maior que o custo de fazê-la.
Vários tipos de contratos possíveis
Atômicos
Cluster
Pares
Multi-Contratos
34
Alocação de Tarefas... E
mentiras



Agentes podem exagerar os custos da
tarefa...
Mas exageros podem tornar contratos
não Individual-Racional
Agentes podem



Esconder tarefas
Criar tarefas fantasmas
Gerar tarefas sob demanda
35
Agora... E esse babado de
concordar?

Quando o problema é alocar recursos...


Leilões
Se precisamos coordenar tarefas,
decidir o que e quando fazer...


Coordenação
Argumentação
36
Um parêntese...

Negociação
Ato de Discutir com o objetivo de atingir um
consenso.

Argumentação
Apresentar argumentos contra ou a favor de
algo, com o intuito de convencer alguém de
nossa própria opinião.
37
Parâmetros no design de
Protocolos...


Sucesso Garantido... Em algum momento!
Maximização do Bem-Estar Social


Pareto-Eficiência



Não há nenhum outro resultado que vá tornar um
agente melhor de vida sem prejudicar os outros.
Individualmente Racional


Maximiza a soma das utilidades dos participantes
Jogar limpo é o melhor a fazer
Estabilidade
Simplicidade e Distribuição
38
Alocando Recursos... Os
Leilões


Forma de Negociação cada vez mais comum... Por
ser um cenário de interação simples!
Duas classes de Agentes:



Leiloeiro
Compradores
Alguns fatores alteram o protocolo...



Valor público?
Ou privado?
Valor Correlato
39
Dimensões dos Protocolos

Determinação do Vencedor


Lances



Preço mais alto ou segundo preço
Ofertas abertas (open-cry)
Ofertas fechadas (sealed bid)
Mecanismo Utilizado



Um lance (one shot)
Crescente
Descendente
40
Leilões Ingleses (English
Auctions)

Características




Ofertas Abertas
Preço mais alto
Ascendente
Que estratégia utilizar?


Aumentar o lance em pequenos incrementos,
e depois se retirar
Maldição do Vencedor
41
Leilões Holandeses (Dutch)

Características




Ofertas Abertas
Descendente
Não Há estratégias dominantes
Também sujeitos à Maldição do
Vencedor.
42
Outros

First Price Sealed Bid



Um lance
Agente deve oferecer um pouco menos do
que o valor estimado... Mas quanto menos?
Vickrey



Second Price Sealed Bid
Oferecer o valor real da mercadoria.
Pode gerar comportamento anti-social ...
43
Lucro esperado

Com compradores risk-neutral


Com compradores avessos ao risco


Os 4 tipos geram lucros parecidos
Dutch e First Price Sealed são os
melhores
Para Leiloeiros Avessos ao Risco

English e Vickrey
44
Mentiras e Conluios


Nada impede que os compradores se juntem...
Uma solução...


Mas o leiloeiro também pode ser desonesto!



Impedir os compradores de se identificarem...
Shills
Troca de valores
Contra-especulação...
45
Negociando...


Para situações mais complexas, leilões
não bastam...
Qualquer negociação tem 4 componentes:




Conjunto de negociação
Um protocolo
Uma coleção de estratégias
Uma regra que determina quando o consenso
foi atingido
46
Complicando...

Quantas questões estão sendo discutidas?


Comprar um carro x Pechinchar no preço da cerveja
Quem está envolvido?



Um prá um
Muitos prá um
Muitos prá muitos

Podemos ter até n(n-1)/2 threads de negociação
47