1 Agentes que Negociam... Negociação... O que é? Utilidades... E Estratégias Equilíbrio de Nash...

1

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

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

Recordando...Interação Objetivos Recursos Habilidade

sIndependê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 Incompatíveis Insuficientes Insuficientes

4

Voltando ao tema... O problema da negociação...

De Tarefas De Recursos

5

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.

6

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

7

O Processo deve Ser Eficiente

Em geral, os agentes ficam “mais felizes” depois da negociação

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

8

O Processo deve Ser... II Distribuído

Um coordenador central pode ser um gargalo de desempenho

Simétrico Atributos irrelevantes não devem

influenciar na decisão Rápido Simples

9

Como possibilitar? Precisamos definir...

A linguagem utilizada pelos participantes

Como cada um decide suas posições? Os Protocolos seguidos pelos agentes.

10

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

Alguns Conceitos Básicos

12

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 :

13

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

14

Num encontro Multiagente...

Um avião está indo para Índia quando é seqüestrado e pousa no Paquistão. Os seqües-tradores 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?

15

Matriz de Recompensa gs

Acordo Resgate

Acordo 22

00

Explode -2-1

0-3

16

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

17

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

18

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.

19

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.

1 i 2 se e somente se 2 j 1

Interações de soma Zero. Quando a i (1) + j (1) = 0

Ex. um jogo de xadrez Vamos ver um exemplo?

20

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.

21

Recompensas... ij

confessa Cala

confessa 22

05

Cala 50

33

22

Decidindo o que fazer... Se eu calar, a maior recompensa é

zero Se eu confessar, o a maior

recompensa é dois... Então... É melhor confessar!

23

Voltando para a questão... Alguns Conceitos básicos de Negociação

Conjunto de Negociação Conjunto das propostas que valem a pena fazer

Protocolo Define que propostas são as legais

Coleção de Estratégias Normalmente a estratégia dos agentes é

privada Regra de Acordo

Define quando o consenso é atingido

Alocando Tarefas...

25

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

26

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>

27

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. 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 conflito.

28

Esquematicamente

Utilidade do Cd para j

Utilidade do Cd para i

Cd

Acordos do conjunto de negociação

29

Assim... O conjunto de possibilidades a

colocar em negociação consiste nos conjuntos de acordos que são Individual racional Pareto ótimo

30

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.

31

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.

32

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.

33

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

34

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íveisAtômicos

ClusterParesMulti-Contratos

35

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

36

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

37

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.

38

Parâmetros no design de Protocolos...

Sucesso Garantido... Em algum momento! Maximização do Bem-Estar Social

Maximiza a soma das utilidades dos participantes Pareto-Eficiê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

39

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

40

Dimensões dos Protocolos Determinação do Vencedor

Preço mais alto ou segundo preço Lances

Ofertas abertas (open-cry) Ofertas fechadas (sealed bid)

Mecanismo Utilizado Um lance (one shot) Crescente Descendente

41

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

42

Leilões Holandeses (Dutch) Características

Ofertas Abertas Descendente

Não Há estratégias dominantes Também sujeitos à Maldição do

Vencedor.

43

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 ...

44

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

45

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

Contra-especulação...

46

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

47

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