Agentes que Negociam...




Negociação... O que é?
Utilidades... E Estratégias
Equilíbrio de Nash
Negociando Recursos


Negociando mais...


Leilões
Protocolos
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
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.
3
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

Formação de coligações
4
O Processo deve Ser

Eficiente


Maximiza o somatório das utilidades.
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
5
Como possibilitar?

Precisamos definir...



A linguagem utilizada pelos participantes
Como cada um decide suas posições?
Os Protocolos seguidos pelos agentes.
6
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 :  

7
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?
E... Se tiver mais de um agente envolvido?
8
Encontros...

Suponha que agentes i e j (capazes de duas
ações C ou D) têm a seguinte função:
i(D,D) = 1 i(D,C) = 1 i(C,D) = 4 i(C,C) = 4
j(D,D) = 1 j(D,C) = 4 j(C,D) = 1 j(C,C) = 4
O que você faria no lugar de i?
9
Matriz de Recompensa
i
D
C
j
D
4
4
C
1
4
4
1
1
1
10
Estratégias Dominantes

Que ações tomar?



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
Nem sempre teremos estratégias fortemente
dominantes! As vezes precisamos ter estratégias
fracamente dominantes.
11
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.
12
Pensando mais um pouco...

Interações Competitivas...


Suponha que temos dois agentes i e j, onde i
prefere um estado 1 sss j prefere 2.
Interações de soma Zero.



Quando a i (1) + j (1) = 0
Ex. um jogo de xadrez
Vamos ver um exemplo?
13
Exemplos de Interações
Competitivas

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.
14
Recompensas...
i
D
C
j
D
2
2
C
0
5
5
0
3
3
15
Decidindo o que fazer...




Se eu cooperar, a maior recompensa é
zero
Se eu desertar, a maior recompensa é
dois...
Então... É melhor desertar!
O dilema do prisioneiro também pode
ser jogado interativamente...
16
Algumas Estratégias...

All-D


Randômico


Sempre deserta
O nome já explica... 
Tit-for-Tat


Coopere no primeiro round
No round t faça o que seu oponente fez
no round t-1
17
Mais estratégias...


Tester: explorador de programas que não
castigavam deserção. Deserta na primeira
rodada. Se o oponente não retaliasse,
jogava Tit-for-tat, senão, cooperava por
dois rounds e desertava no terceiro.
Joss-Tit-for-tat, porém desertava 10% das
vezes em que deveria cooperar...
18
Mas...

E quando computar utilidades for muito
caro?


Negociar envolve planejamento...
E um modelo do oponente!

Vários aspectos sob negociação...
19
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
20
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.
21
Voltando...



Consensos dependem da capacidade de
negociação e argumentação dos agentes
envolvidos...
Negociação governada por protocolos...
Como desenvolver estratégias para os
agentes utilizarem enquanto negociam?
22
Parâmetros (Possíveis) no
design de Protocolos...


Sucesso Garantido... Em algum momento!
Maximização do Bem-Estar Social


A soma das utilidades é maximizada
Pareto-Eficiência

Não há nenhum outro resultado que vá tornar
um agente melhor de vida sem prejudicar os
outros.
23
Parâmetros (Possíveis) no
design de Protocolos...

Individualmente Racional


Estabilidade


Jogar limpo é o melhor a fazer
Um protocolo é estável se incentiva os agentes a se
comportarem de uma determinada forma
Simplicidade e Distribuição


É fácil ver qual a melhor forma de agir
Não há autoridade central
24
Alocando Recursos... Os
Leilões


Forma de Negociação cada vez mais comum...
Duas classes de Agentes:



Leiloeiro
Compradores
Alguns fatores alteram o protocolo...



Valor público?
Ou privado?
Valor Correlato
25
Dimensões dos Protocolos

Determinação do Vencedor


Lances



First x Second Price
Open-Cry
Sealed Bid
Mecanismo Utilizado



One Shot
Crescente
Descendente
26
Leilões Ingleses (English
Auctions)

Características




Open Cry
First Price
Ascending
Que estratégia utilizar?


Aumentar o lance em pequenos incrementos,
e depois se retirar
Maldição do Vencedor
27
Leilões Holandeses (Dutch)

Características




Open Cry
Descending
Não Há estratégias dominantes
Também sujeitos à Maldição do
Vencedor.
28
Outros

First Price Sealed Bid



One Shot
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 ...
29
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
30
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!
Contra-especulação...
31
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
32
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.
33
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.
34
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.
35
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
36
Dois tipos fundamentais de
domínio


Orientados a Tarefas (DOT)
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.
37
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.
38
Mais sobre acordos

Um acordo 1 domina 2 se





1 é tão bom quanto 2 para todos os agentes.
1 é melhor que 2 para algum agente.
1 domina fracamente 2 se a primeira
condição se verifica.
Um acordo que não é dominado por nenhum
outro é chamado de pareto-optimal.
 é individual racional se domina
fracamente o acordo de conflito
39
Assim...

O conjunto de possibilidades a colocar
em negociação consiste nos conjuntos
de acordos que são


Individual racional
Pareto optimal
40
Um protocolo...

Protocolo de Concessão Monotônico



Negociação acontece em rounds.
No primeiro, ambos os agentes propõem
acordos no conjunto de negociação
Um acorde é alcançado se




Utility1 (2 )  utility1(1) ou
Utility2 (1 )  utility2(2)
Sem consenso, a negociação continua
Negociação termina com o conflict deal.
41
Como proceder...


Propor o melhor deal.
Quem deve ceder?


Depende da “vontade” de um agente
arriscar conflito.
Maior a vontade se a diferença entre a
proposta e o conflict deal for baixa.
42
Definindo Risco
Riskit= utilidade perdida aceitando a
oferta/ utilidade perdida causando
conflito
1 se
utility (jt) = 0
Riskit=
utility (it) - utility (jt) /
utility (it)
43
Quanto ceder?




O menos necessário para mudar o
balanço de risco
Protocolo exponencial!
Equilíbrio de Nash
Agentes podem enrolar... Criando
tarefas fantasmas... Ou escondendo
tarefas!
44
Domínios Orientados a Valor

Um DOV é uma tupla <E, Ag, J, C> onde






E é o conjunto de estados do ambientes
Ag é o conjunto de Agentes participantes do
processo
J é a coleção de planos conjuntos
C : JxAg  R é o custo de realização.
Um encontro é o par <e,W>
Agentes negociam tanto sobre o estado a que
querem chegar quanto sobre os meios para
atingi-lo.
45
Cenas dos Próximos Capítulos

Hoje vimos...



Formas de expressar as preferências
dos agentes...
Conceito de estratégias
Algumas formas de negociação...



Domínios Orientados a Tarefa
Domínios Orientados a Valor
Veremos...

Argumentação e Colaboração
46