Aplicatii Web bazate pe semantica, agenti si servicii

Universitatea Politehnica BucurestiAnul universitar 2007-2008, MasterAdina Magda Florea

http://turing.cs.pub.ro/webs_07

Curs 6 Negociere in SMA

Negociere bazata pe teoria jocurilor Negociere pentru alocarea taskurilor Negociere euristica

1. Despre negociere

Agenti motivati colectiv = cooperareAgenti motivati individual = competitieNegociere = interactiune -> contract Negocierea include:

un limbaj de comunicare un protocol de negociere un proces de decizie: concesii, criterii de acceptare/refuz

Single party or multi-party negotiation: one to many or many to many (eBay http://www.ebay.com )

Tehnici de negociereTehnici de negociere Negociere bazata pe teoria jocurilor Negociere euristica Negociere bazata pe argumentare

3

Criterii de evaluare protocol negociere Agentii se comporta rational Comportare rationalaComportare rationala = un agent prefera o

utilitate / plata (utility / payoff) mai mare fata de una mai mica

Functa de utilitate ui: R = {s1, s2, …} ui(s) ui(s’) (s s’)– ordonarea preferintelor

asupra rezultatelor4

2. Negociere bazata pe teoria jocurilor

Doi agenti au 2 actiuni posibile: D si C ( Ac={C,D} ) Mediul se comporta astfel:

t: Ac x Ac t(D,D)=s1 t(D,C)=s2 t(C,D)=s3 t(C,C)=s4

sau

t(D,D)=s1 t(D,C)=s1 t(C,D)=s1 t(C,C)=s1

u1(s1)=4, u1(s2)=4, u1(s3)=1, u1(s4)=1

u2(s1)=4, u2(s2)=1, u2(s3)=4, u2(s4)=1

u1(D,D)=4, u1(D,C)=4, u1(C,D)=1, u1(C,C)=1

u2(D,D)=4, u2(D,C)=1, u2(C,D)=4, u2(C,C)=1

Agent1 D,D D,C C,D C,C

5

u1(D,D)=4, u1(D,C)=4, u1(C,D)=1, u1(C,C)=1

u2(D,D)=4, u2(D,C)=1, u2(C,D)=4, u2(C,C)=1

Agent1 D,D D,C C,D C,C

Matricea de plata (utilitate)

6

J1 Player D C J2 D 4, 4 4, 1 Player C 1, 4 1, 1

7

Comportare rationalaComportare rationala = utilitate (payoff) mai mare preferata fata de una mai mica

Maximizarea platiiMaximizarea platii: plata individuala, plata de grup, sau bunastare sociala

Bunastare socialaBunastare sociala Suma utilitatii agentilor pentru o anumita

situatie/solutie Masoara binele general Problema: cum compar utilitatile

2.1 Criterii in negociere

8

Eficienta ParetoEficienta Pareto O solutie x, i.e., un vector de plata p(x1, …, xn), este eficient

Pareto (Pareto optimal) daca nu exista alta solutie x' a.i. cel putin un agent are o utilitate mai mare in x' decat in x si nici un agent nu are o utilitate mai mica in x' decat in x.

Masoara bunastarea globala dar nu necesita compararea utilitatilor

Bunastarea sociala eficienta Pareto Rationalitate individuala (IR)Rationalitate individuala (IR)

IR a participarii unui agent = Plata agentului in urma participarii la negociere nu este mai mica decat plata lui daca nu ar participa la negociere

O negociere este IR daca este IR pentru toti agentii

Eficienta Pareto

StabilitateStabilitate un protocol este stabil daca o data ce agentii au ajuns la o

solutie ei nu deviaza de la aceasta Strategie dominanta = agentul are o utilitate mai mare folosind

aceasta strategie indiferent de ce strategii folosesc ceilati agenti

t: Ac x Ac s = t(ActA, ActB) rezultatul (starea) actiunilor ActA a

agentului A si ActB a agentului B.

O strategie S1 = {s11, s12, …, s1n} domina o alta strategie S2 = {s21, s22, …, s2n} daca orice rezultat sS1 este preferat (este mai bun) oricarui rezultat s'S2.

9

Strategie dominanta

Echilibru Nash Doua strategii, S1 a agentului A si S2 a agentului B sunt in

echilibru Nash : daca agentul A urmeaza S1 atunci agentul B nu poate obtine un

castig mai mare decat acela obtinut daca urmeaza S2 si daca agent B urmeaza S2 atunci agentul A nu poate obtine un

castig mai mare decat acela obtinut daca urmeaza S1. Multime de strategii {S1, …, Sk} folosite de agentii A1, ..., Ak sunt in

echilibru Nash daca, penru orice agent Ai, strategia Si este cea mai buna strategie a lui Ai daca ceilalti agenti folosesc { S1, S2, …, Si-1, Si+1,…, Sk.}.

Probleme: nici un echilibru Nash multiple echilibre Nash

10

Echilibru Nash

Dilema prizonierului

11

J2 player Defect Cooperate J1 Defect 2, 2 5, 0 player Cooperate 0, 5 3, 3

J2 player I A J1 I 2, 1 0, 0 player A 0, 0 1, 2

Alt exemplu

Turneul AxelrodStrategii ALL-D – D tot timpul RANDOM –C sau D cu probabilitate egala TIT-FOR-TAT

- C in primul tur- In turul t>1 ce a ales oponentul in t-1

TESTER- D in primul tur- Daca oponentul a ales D atunci TIT-FOR-TAT- Altfel joaca 2 tururi C si 1 tur D

JOSS- TIT-FOR-TAT – dar cu 10% D

12

Strategii in jocuri repetate

Ordoneaza iesirile posibile (rezultatele posibile) pe baza preferintelor individuale ale agentilor

A - set de n agenti - set de m rezultate posibile Fiecare agent i A are o relatie de preferinat stricta

<i : x , asimetrica si tranzitivaRegula alegerii sociale Intrare:Intrare: relatiile de preferinta ale agentilor

(<1, …, <n) Iesire:Iesire: elementele din ordonate in functie de

intrare – relatia de preferinta sociala <*13

2.2 Vot – regula de alegere sociala

Proprietati de dorit pentru o regula de preferinta sociala:

Ordonarea <* trebuie sa existe pentru orice intrare posibila (preferinta individuala)

<* trebuie sa fie definita pentru orice pereche (o, o') <* trebuie sa fie asimetrica si tranzitiva peste Iesirile trebuie sa fie Pareto optimale:

dacai A, o <i o' atunci o <* o' Nici un agent nu trebuie sa fie dictator

dictator = o <i o' implica o <* o' pentru toate preferintele celorlalti agenti

Arrow's impossibility theoremArrow's impossibility theoremNici o regula sociala nu poate satisface toate conditiile

14

Protocol pluralist – protocol de votare majoritara – toate alternativele sunt comparate simultan; castiga cea care are cel mai mare numar de voturi

Problema – alternative irelevante

Protocol binar – alternativele votate in perechi, cea care pierde este eliminata, cea care castiga intra in competitie cu restul

Problema – agende diferite15

Protocoale de votare

- 35% agenti c>d>b>a- 33% agenti a>c>d>b- 32% agenti b>a>c>d

Agenda 1: (b,d), d, (d,a) a, (c,a) a Agenda 2: (c,a) a, (d,a) a, (a,b) b Agenda 3: (a,b) b, (b,c) c (c,d) c Agenda 4: (c,a) a (a,b) b, (b,d) d

16

Protocolul Borda

Multe alternative – protocolul binar este lent

Borda – Contoare atribuite alternativelor = | | puncte pentru cea mai mare preferinta, | |-1 puncte pt urmatoarea, etc.

Contoarele se insumeaza pt fiecare alternativa si castiga cea cu punctaj maxim

Problema: nu acelasi castigator daca cea mai proasta alternativa este eliminata

17

Protocol Borda - exemplu Agent Preferinta Agent Preferinta

1 a>b>c>d 1 a>b>c2 b>c>d>a 2 b>c>a3 c>d>a>b 3 c>a>b4 a>b>c>d 4 a>b>c5 b>c>d>a 5 b>c>a6 c>d>a>b 6 c>a>b7 a>b>c>d 7 a>b>c

c obtine 20, b 19, a 18, d 13 elimin d – a 15, b 14, c 13

18

Protocoale simple Centralizate Licitatii cu valoare privata Liciatii cu valoare comuna Licitatii cu valoare corelata

19

2.3 Licitatii

English (first-price open cry) auction – fiecare participant anunta deschis pretul pe care il liciteaza. Cel mai mare pret castiga Strategie dominanta: putin mai mult decat ultimul pret, ma

opresc cand ajung la valoarea privata – in licitatii cu valoare privata

In licitatii cu valoare corelata; creste constant pretul pana decizie stop

First-price sealed-bid auction – fiecare participant anunta pretul in plic inchis. Castiga cel cu pret maxim Nu exista stragie dominanta; ofera cel mult pana la valoare

lui privata

20

Protocoale de licitatii

Dutch (descending) auction - the auctioneer continuously lowers the price until one of the bidders takes the item at the current price. Echivalenta cu licitatia first-price sealed-bid

Vickrey (second-price sealed-bid) auction – trimite oferta in plic inchis. Castiga cel care a facut cea mai mare oferta dar plateste al doilea pret Strategia dominanta: valoarea lui privata

Probleme in licitatii

21

n bunuri g, g = 1,n, in cantitati nelimitate preturi p=[p1, …, pn], unde pg R este pretul bunului g

2 tipuri de agenti: producatori si consumatoriConsumatori:Consumatori: vector de consum xi=[xi1,…,xin], xig R+ este cantitatea de bunuri g

alocata consumatorului i. functie de utilitate – ui(xi) – preferinta consumatorului i asupra

vectorului de consum repartitia initiala de bunuri ei=[ei1,…,ein], eig este cantitatea din g

repartiazata initial consumatorului iProducatori:Producatori: vector de productie yj=[yj1,…,yjn], yjg este cantitatea din bunul g pe

care producatorul j o produce Multime de productii posibile Yj – vectori cu cantitatile posibil de

produs22

2.4 Echilibrul pietei

Profitul producatorului j = p . yj, cu yj Yj. ij procentul din productia lui j detinuta de consmatorul i Profitul producatorilor este impartit intre consumatori in

functie de aceste procente Piata evolueaza Preturile se schimba Planurile de productie si de consum se schimba (tentativ)

pana: se ajunge la echilibru – are loc productia si consumul

efectiv

23

(p*, x*, y*) este in echilibru Walras daca:

se consuma cat se produce

fiecare consumator i isi maximimizeaza preferintele cu preturile stabilite

fiecare producator j isi maximizeaza profitul cu preturile stabilite

24

j

ji

ii

i yex **

)(maxargθ..,

*** ii

.ypepxpRxi xux

jj

*ijiini

jYyj ypy

jj

.*maxarg*

Algoritmul "Distributed price tatonnement"

Algoritm pentru facilitator:- pg=1 pentru orice g[1..n]

- g un numar pozitiv pentru g [1..n]

repeat- anunta p consumatorilor si producatorilor- primeste un plan de productie yj de la fiecare producator j

- anunta planurile yj consumatorilor

- primeste un plan de consum xi de la fiecare consumator i

- for g=1 to n dopg = pg + g(i(xig - eig) - jyjg)

until |i(xig-eig)- jyjg| < pt oricare g [1..n]

- Anunta producatorii si consumatorii ca s-a ajuns la echilibru25

Algoritm pentru consumatorul i:

- repeat- primeste p de la facilitator- primeste un plan de productie yj pt fiecare j de la facilitator- anunta facilitatorului un plan de consum xi Rn

+ care maximizeaza ui(xi) tinand cont de constrangerile de bugetp.xi p.ei + jijp.yj until facilitatorul anunta echilibrul- schimba si consuma

Algoritm pentru producatorul j:repeat- primeste p de la facilitator- anunta facilitatorului un plan de productie yj Yj care maximizeaza p.yjuntil facilitatorul anunta echilibrul- schimba si consuma

26

Alocare prin redistribuirea taskurilor Alocare prin retea de contracte

- Contract Net- Iterated Contract Net

Se afla intre negociere teoretica si euristica

27

3. Alocarea taskurilor prin negociere

Domeniu orientat task = un triplet <T, Ag, c> unde T – o multime de taskuri; Ag = {1, . . . ,n} – multimea de agenti care participa la negociere; c:P(T) R+ - functie de cost definita pentru orice submultime de

taskuri din T Functia de cost trebuie sa satisfaca 2 restrictii:

monotona costul unui task trebuie sa fie diferit de 0

O intalnire intr-un domeniu orientat task<T, Ag, c> are loc atunci cand agentilor din Ag li se atribuie taskuri de executat din T

Atribuire taskuri R = {E1, . . ., En}, Ei T, i Ag

28

3.1 Redistribuirea taskurilor

Intrebare: intr-o intalnire, poate un agent sa obtina o utilitate mai mare prin redistribuirea taskurilor?

Fie:Ag = {a1, a2, a3} T = {t1, t2, t3, t4, t5}IntalnireR = {E1, E2, E3} cu E1 = {t1, t3}, E2 = {t2}, E3 = {t4, t5} Afacere (redistribuire) = {D1, D2, D3} cu D1 = {t1, t2}, D2 = {t3, t4}, D3 = {t5}

Costul unei afaceri costul pt a1 c(D1) costul pt a2 c(D2) costul pt a3 c(D3)

Utilitatea unei afaceri = cat castiga agentul din afacereutilityi() = c(Ei) – c(Di), i = 1, 2, 3

29

O afacere 1 domina o afacere 2 daca si numai daca:

(1) Afacerea 1 este cel putin la fel de buna ca 2 pentru orice agent i {1,2} utilityi(1 ) utilityi( 2 )

(2) 1 este mai buna decat 2 pentru cel putin un agent i {1,2} utilityi(1 ) > utilityi( 2 )

O afacere domina slab o alta afacere daca (1) este adevarata O afacere este individual rationala (IR) daca domina afacerea

conflictuala O afacere care nu este dominata de nici o alta afacere este Pareto

optimala Redistribuirea taskurilor = gasirea unei afaceri Pareto optimala

30

Protocolul de concesiune monotonaNegociere in mai multe runde1. In prima runda (u=1), a1 si a2 propun afaceri din multimea

de negociere: 1 si 2 2. daca a1 propune 1 si a2 propune 2 a.i:

(i) utility1(2 ) utility1( 1 )sau

(ii) utility2(1 ) utility2( 2 )atunci s-a realizat contractul si stop

3. altfel u u+14. daca a1 propune 1 si a2 propune 2 a.i.:

utility1(2u ) utility1( 2u-1 ) siutility2(1u ) utility1( 1u-1 )

5. atunci executa pasul 26. altfel negocierea se termina cu conflict stopgarantat sa se termine 31

Problema: alocarea taskurilor ajunge intr-un maxim local

Agenti nesinceri Agentii pot minti despre taskurile pe care le au:

taskuri fantoma ascund taskuri

Diferente fata de negocierea bazata pe teoria jocurilor Un agent poate refuza un contract IR Un agent poate accepta un contract care nu este IR

32

33

3.2 Contract Net

Initiator si licitatori/contractori

34

FIPA - Contract net• Initiatorul solicita propuneri –cfp: specifica taskul si conditii asupra lui,de la n participanti (contractori)• Cei n participanti genereaza raspunsuri:- i refuza (refuse)- j=n-i propun (propose), inclusiv conditii• cfp include un deadline pt raspunsuri(apoi sunt automat excluse)• Initiatorul evalueaza propunerile si selecteaza l (intre 1 si j) agenti – li se trimite mesaj de accept-proposal si mesaj de reject-proposal la k=j-l agenti• Propunerile angajeaza participantii• Un participant trebuie sa raspunda cu:- inform-done sau -inform-result (daca a executat taskul) sau -failure.Interactiunea este identificata printr-un unic parametru conversation-id

Exemplu

(cfp  :sender (agent-identifier :name j)   :receiver (set (agent-identifier :name i))  :content    "((action (agent-identifier :name i)      (sell plum 50))     (any ?x (and (= (price plum) ?x) (< ?x 10))))"  :ontology fruit-market  :language fipa-sl)

Agentul j ii cere lui i propuneri de vanzarea 50 cutii de prune si conditii de pret

Exemplu

(propose   :sender (agent-identifier :name j)   :receiver (set (agent-identifier :name i))  :content    "((action j (sell plum 50))     (= (any ?x (and (= (price plum) ?x) (< ?x 10))) 5)"  :ontology fruit-market  :in-reply-to proposal2  :language fipa-sl)

Agentul j propune lui i sa-i vanda 50 cutii prune la pret de 5

Exemplu

(accept-proposal  :sender (agent-identifier :name i)  :receiver (set (agent-identifier :name j))  :in-reply-to bid089  :content    "   ((action (agent-identifier :name j)

(sell plum 50))      (= (price plum) 5))) "  :language fipa-sl)

Agentul i accepta pe j

Exemplu

(reject-proposal   :sender (agent-identifier :name i)   :receiver (set (agent-identifier :name k))  :content    "((action (agent-identifier :name k)       (sell plum 50))      (= (price plum) 20)      (price-too-high 20))"  :in-reply-to bid080)

Agentul i il refuza pe k

39

FIPA – Iterated Contract net

Produce o solutie buna dar nu optima (de obicei)

Modele de negociere informale Nu exista un mediator central Protocolul trebuie sa fie cunoscut de agenti (nu

exista protocoale predefinite) Nu exista un curs optim de urmat prescris Accent pe procesul de decizie al agentului

40

4. Negociere euristica

Obiectul negocierii (NO): aspectele asupra carora trebuie ajuns la un contract

NO: obiect, actiune, serviciuNO03: NO

Name: Paint_House Cost: Value:100, Type: integer, Modif=Yes; Deadline: Value: May_12, Type: date, Modif=No; Quality: Value: high, Type: one of (low, average, high), Modif=Yes

(Request NO) – cere un obiect de negociere (Accept name(NO)) – accepta cererea pentru NO (Reject name(NO)) – refuza cererea pentru NO (ModReq name(NO) value(NO,X,V1)) – modifica cererea

prin modificarea atributului X al NO la o valoare V1 Necesita definirea unui limbaj si a unui protocol

41

42

Initiator Participant

Request NO

Reject NO

Accept NO

ModReq NO' val

Reject NO'

Accept NO'' val

ModReq NO'' val

Failure

Inform done

Protocol pentru primitivele definite