View
102
Download
0
Category
Preview:
Citation preview
1
Agentes que Negociam... Negociação... O que é? Utilidades... E Estratégias Equilíbrio de Nash Negociando Recursos
Leilões Negociando mais...
Protocolos Cenas dos Próximos Capítulos
2
Algumas Observações Importantes
““Não há SMA de um só agente...”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.
3
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.
4
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
5
O Processo deve Ser Eficiente
Maximiza o somatório das utilidades. Estável
Racionalidade Individual Deve ser preferível atuar em grupo
Racionalidade de grupo É melhor participar deste grupo do que de outro
Racionalidade de coligação Ninguém quer sair da coligação
6
Como possibilitar? Precisamos definir...
A linguagem utilizada pelos participantes
Como cada um decide suas posições? Os Protocolos seguidos pelos agentes.
7
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 :
8
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?
9
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) = 4O que você faria no lugar de i?
10
Matriz de Recompensa ij
D C
D 44
14
C 41
11
11
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.
12
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.
13
Pensando mais um pouco...
Interações Competitivas... Suponha que temos dois agentes i e j,
onde um 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?
14
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.
15
Recompensas... ij
D C
D 22
05
C 50
33
16
Decidindo o que fazer... Se eu cooperar, o maior payoff é
zero Se eu desertar, o maior payoff é
dois... Então... É melhor desertar! O dilema do prisioneiro também
pode ser jogado interativamente...
17
Algumas Estratégias... All-D
Sempre deserta Randômico
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
18
Mais estratégias... Tester: explorador de programas que
não castigavam deserção. Deserta na primera 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...
19
Mas... E quando computar utilidades for
muito caro? Negociar envolve planejamento... E um modelo do oponente!
Vários aspectos sob negociação...
20
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
21
Um parêntese... Negociação
Ato de Discutir com o objetivo de atingir um consenso.
ArgumentaçãoApresentar argumentos contra ou a favor
de algo, com o intuito de convencer alguém de nossa própria opinião.
22
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?
23
Parâmetros no design de Protocolos...
Sucesso Garantido... Em algum momento! Maximização do Bem-Estar Social Pareto-Efficiência
Não há nenhum outro resultado que vá tornar um agente melhor de vida sem prejudicar os outros.
Individualmente Racional Jogar limpo é o melhor a fazer
Estabilidade Simplicidade e Distribuição
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
First x Second Price Lances
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
Os 4 tipos geram lucros parecidos Com compradores avessos ao risco
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 (i
t) - 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
Recommended