7/30/2019 Sisteme multiagent. Teoria jocurilor 2
1/107
Modelarea i analizasistemelor multi-agent
5. Teoria jocurilor (II)
Florin Leon
Universitatea TehnicGheorgheAsachi din IaiFacultatea de Automatici Calculatoare
http://florinleon.byethost24.com/curs_masma.htm
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
2/107
Teoria jocurilor (II)Jocuri de sum general cu doi ageni1. Reducerea la jocuri de sum nul2. Echilibru Nash pur
3. Echilibru Nash mixt4. Jocuri cooperante
Jocuri cooperante cu n ageni5. Reprezentarea jocurilor n forma caracteristic
6. Nucleul7. Valoarea Shapley8. Nucleolus
2Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
3/107
Teoria jocurilor (II)Jocuri de sum general cu doi ageni1. Reducerea la jocuri de sum nul2. Echilibru Nash pur
3. Echilibru Nash mixt4. Jocuri cooperante
Jocuri cooperante cu n ageni5. Reprezentarea jocurilor n forma caracteristic
6. Nucleul7. Valoarea Shapley8. Nucleolus
3Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
4/107
Jocuri bimatriceale Jocurile de sum general (sau nenul)
se mai numesc i bimatriceale
Pentru jocurile de sum nul, R=C
4Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
5/107
Reducerea la un joc de sumnul Un joc bimatriceal cu matricele Ri Cpoate fi redus
la un joc de sum nul dac exist > 0i , Efiindmatricea unitate (Eij= 1), astfel nct:
Pentru exemplul anterior:
5Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
6/107
Exemplu de calcul (I)
6
Jocul nu poate fi redus
= 2, = 1i se obin din ecuaiile
corespunztoare primei linii i
se verific n ecuaiilecorespunztoare liniei a doua
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
7/107
Exemplu de calcul (IIa)
7
Dac = 1/5 i =2, atunci:
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
8/107
Exemplu de calcul (IIb) Jocul se reduce la un joc de sumnul cu matricea:
Este un exemplu rezolvat n cursul anterior, cu strategiile deechilibru mixt R: (4/7, 3/7) i C: (2/7, 0, 5/7, 0, 0), iar valoareajocului este v= 1/7
Ctigul ateptat al lui Colin este: E[PC] =v=1/7
Avem: E[PR]+=E[PC] Ctigul ateptat al lui Rose este:
E[PR] = 1/ (v) = 5 (1/7 + 2) = 75/7
8
= 1/5, =2
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
9/107
Teoria jocurilor (II)
Jocuri de sum general cu doi ageni1. Reducerea la jocuri de sum nul2. Echilibru Nash pur
3. Echilibru Nash mixt4. Jocuri cooperante
Jocuri cooperante cu n ageni5. Reprezentarea jocurilor n forma caracteristic
6. Nucleul7. Valoarea Shapley8. Nucleolus
9Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
10/107
Echilibrul Nash O combinaiede strategii este un echilibru Nash dac
fiecare agent i maximizeaz ctigul, date fiindstrategiile folosite de ceilali ageni
Echilibrul Nash identific acele combinaii de strategiicare sunt stabile, n sensul c fiecare agent estemulumit cu aciunea aleas, date fiind aciunilecelorlali
Comportamentul generat de un echilibru Nash estede ateptat s persiste n timp
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
11/107
Echilibrul Nash Echilibru Nash pentru o strategie pur
11
),(),( ***iiiiii
ssussu
Ctigul(utilitatea)agentului i
Strategia dinechilibrul Nash
Strategiaagentului i
Strategiilecelorlali agenicu excepia lui i
Determinist,care nu implic
probabiliti
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
12/107
Echilibrul Nash Echilibrul Nash pentru o strategie pur
Echilibrul Nash este strict dac:
Strile din care niciun agent nu-i poatemri ctigul prin schimbareaunilateral a strategiei
12
),(),( ***iiiiii
ssussu
),(),( ***iiiiii
ssussu
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
13/107
Calculul echilibrelor Nash pure Se evideniaz maximele pe linii pentru primul agent
cu {
Se evideniaz maximele pe coloane pentru al doileaagent cu } Strile ncadrate de { } sunt echilibre Nash pure
13Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
14/107
Exemple
14
Dilema inculpailor
Btlia sexelor
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
15/107
Tragedia punii comunale engl. the tragedy of the commons Punea este folosit n comun de 6 rani,
fiecare cu cte o vac
15Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
16/107
Tragedia punii comunale
Fiecare vac d 20 de litri de lapte pe zi Capacitatea punii este de 8 vaci Pentru fiecare vac peste 8, producia de
lapte scade cu 2 litri Exist mai puin iarb de pscut pentru fiecare
vac, deci i mai puin lapte
16Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
17/107
17
20 litri 20 litri
20 litri
20 litri20 litri
20 litri
Producia zilnic total de lapte: 120 litriFlorin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
18/107
18
ranii vor s-i maximizeze producia de lapte
20 litri
20 litri
20 litri20 litri
20 litri
Producia zilnic total de lapte: 140 litri (7 vaci)
40 litri
O s cumpr nc o vac
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
19/107
19
Acum s-a atins capacitatea maxim a punii. Dar ranii nu se opresc.
20 litri
20 litri20 litri
20 litri
Producia zilnic total de lapte: 160 litri (8 vaci)
40 litri 40 litri
Atunci i eu o s-mi cumpr
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
20/107
20
18 litri18 litri
18 litri
Producia zilnic total de lapte: 162 litri (9 vaci)
36 litri 36 litri
O s-mi iau nc una
36 litri
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
21/107
21
32 litri16 litri
16 litri
Producia zilnic total de lapte: 160 litri (10 vaci)
32 litri 32 litri
32 litri
Vaca produc e acum mai puin,dar 2 vaci o s rezolve problema
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
22/107
22
28 litri
14 litri
Producia zilnic total de lapte: 154 litri (11 vaci)
28 litri 28 litri
28 litri
O s-mi cumpr nc una 28 litri
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
23/107
23
24 litri
Producia zilnic total de lapte: 144 litri (12 vaci)
24 litri 24 litri
24 litri
24 litri
Toat lumea i cumprnc o vac, deci i eu
24 litri
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
24/107
24
20 litri
Producia zilnic total de lapte: 130 litri (10 vaci)
30 litri 20 litri
nc pot crete produciadac iau i a treia vac
20 litri
20 litri
20 litri
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
25/107
25
-100
-50
0
50
100
150
200
0 2 4 6 8 10 12 14 16 18 20
Total Cow
ranii vor continua scumpere vaci pn cnd sunt15 vaci n total pe pune
Nivelul iniial
Ctigul sau pierdereapentru un ran la
cumprarea unei noi vaci
Numrul total de vaci
Producia totalpentru toate vacile
Producia maxim de laptepentru pune: 162 litri/zi
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
26/107
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
27/107
Soluii? Acord de cooperare ntre rani
mprirea profitului pentru cele 3 vaci n plus
Consolidare
O firm gestioneaz toate vacile i devine un singur centru deprofit
Reglementri ale statului Stabilirea unui numr maxim de vaci pe pune sau impunerea
redistribuirii profitului
Proiectarea mecanismelor (engl. mechanism design) Stimulente i penalizri pentru agenii individuali astfel nct s fie
tentai s ating optimul social Problem nc deschis
27Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
28/107
Beneficiul social ibeneficiul individual
Partajarea (sharing-ul) n reele P2P Poluarea ... n general, managementul resurselor din
proprietatea comun
28Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
29/107
Teoria jocurilor (II)
Jocuri de sum general cu doi ageni1. Reducerea la jocuri de sum nul2. Echilibru Nash pur
3. Echilibru Nash mixt4. Jocuri cooperante
Jocuri cooperante cu n ageni5. Reprezentarea jocurilor n forma caracteristic
6. Nucleul7. Valoarea Shapley8. Nucleolus
29Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
30/107
30
Jocul ajutorului social
Guvernul vrea s ajute un om srac doar dac acestavrea s munceasc
Sracul i caut de lucru doar dac nu ia ajutor de lastat
engl. the welfare game
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
31/107
31
Jocul ajutorului social
(Aid, Try to work) nu este EN PauperpreferBe idle(Aid, Be Idle) nu este EN: Govt preferNo Aid(No Aid, Be Idle) nu este EN: Pauper preferTry to Work(No Aid, Try to Work) nu este EN: Govt preferAidJocul nu are echilibru Nash!
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
32/107
32
Jocul ajutorului social
(Aid, Try to work) nu este EN PauperpreferBe idle(Aid, Be idle) nu este EN: GovtpreferNo aid(No Aid, Be Idle) nu este EN: Pauper preferTry to Work(No Aid, Try to Work) nu este EN: Govt preferAidJocul nu are echilibru Nash!
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
33/107
33
Jocul ajutorului social
(Aid, Try to work) nu este EN PauperpreferBe idle(Aid, Be idle) nu este EN: GovtpreferNo aid(No Aid, Be idle) nu este EN: PauperpreferTry towork(No Aid, Try to work) nu este EN: Govt preferAidJocul nu are echilibru Nash!
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
34/107
34
Jocul ajutorului social
(Aid, Try to work) nu este EN PauperpreferBe idle(Aid, Be idle) nu este EN: GovtpreferNo Aid(No Aid, Be idle) nu este EN: PauperpreferTry to work(No Aid, Try to work) nu este EN: GovtpreferAidJocul nu are echilibru Nash (pur)!
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
35/107
35
Strategii pure i mixte Strategie pur
Agentul ialege strategia sij din mulimeaSi Strategie mixt
Agentul ialege strategia sijcu probabilitateapij
pij 0, jpij = 1
Orice strategie pur este de asemenea i o strategie
mixt Un joc finit are ntotdeauna cel puin un echilibru
Nash pur sau mixt O strategie mixt are ntotdeauna un echilibru Nash
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
36/107
36
Strategii mixte
Ctigul n strategii mixte este ctigul ateptat Fie 1 ctigul cu strategia s1i 4 cu strategia s2
Strategia mixt (0.3, 0.7) d ctigul ateptat0.3 1 + 0.7 4 = 3.1 Un ctig sigur de 3.1 este echivalent cu un ctig
ateptat ntr-un joc cu ctiguri de 1 i 4 cu
probabilitile 0.3 respectiv 0.7
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
37/107
37
Strategii mixte: interpretare
Jocuri n care se pot aplica simultan strategii multiple Pariurile pe mai muli cai
Instane multiple ale aceluiai joc Scenariu de rzboi: qij% din piloi urmeaz strategiasij
Acelai joc repetat la infinit Pentru un singur joc: distribuia de probabilitate este
estimarea oponenilor asupra deciziei unui agent
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
38/107
Metoda resturilor
engl. oddment method Metod simpl pentru calculul echilibrelor
Nash mixte Dac jocul are un echilibru Nash pur,
metoda nu se aplic
38Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
39/107
Strategiile pentru Pauper
39Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
40/107
Strategiile pentru Government
40Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
41/107
41
Echilibrul Nash n jocul ajutoruluisocial cu strategie mixt (I)
DacGovernment alege o probabilitate de 0.5 pentruAid, Pauper nu poate profita de pe urma acestei deciziin alegerea uneia din aciunile Work sau Be idle
Ctigul Pauper(Work) = 0.5 2 + (10.5) 1 = 1.5
Ctigul Pauper (Be idle) = 0.5 3 + (10.5) 0 = 1.5
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
42/107
42
Echilibrul Nash n jocul ajutoruluisocial cu strategie mixt (II)
DacPauper alege Try to work cu probabilitatea 0.2,Government va fi indiferent ntreAidiNo aid Ctigul Govt(Aid) = 0.2 3 + (10.2) (1) =0.2 Ctigul Govt(No aid) = 0.2 (1) + (10.2) 0 =0.2
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
43/107
43
Echilibrul Nash n jocul ajutoruluisocial cu strategie mixt (III)
Pentru probabilitile 0.5 i 0.2, att Governmentcti Pauperau ctiguri egale pentru ambele aciuni,ceea ce permite existena unui echilibru Nash
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
44/107
Metoda 2
Determinarea strategiei pentru Pauper 3 x+ (1) (1x) = (1) x+ 0 (1x) x = 0.2, 1x = 0.8
Determinarea strategiei pentru Government 2 y+ 1 (1y)= 3 y+ 0 (1y) y = 0.5, 1y = 0.5
44Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
45/107
45
Stabilitatea
Dar dac un agent prsete strategia deechilibru, oponentul poate profita pentru a
ctiga mai mult dect ar ctiga la echilibru
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
46/107
46
Optimalitatea Pareto
Un rezultat (x0,y0)este optim Pareto(sau dominant sau neinferior) dacNU EXIST alt rezultat (x,y)unde: Ambii ageni au un ctig mai mare
x>x0iy> y0
Un agent are ctig mai mare iar cellalt areacelai ctig x>x0iy= y0 , sau x=x0 iy> y0
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
47/107
Optimalitatea Pareto
Un rezultat este optim Pareto dac este: mai bun sau la fel dect alt rezultat din toate
punctele de vederei
mai bun strict din cel puin un punct de vedere
47Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
48/107
48
Stri optime Pareto
ntr-o stare optim Pareto, agenii nu au motivaia dea devia n coaliie
De exemplu: dilema inculpailor Ambii ageni au ctig mai marempreundac ambii neag
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
49/107
49
Interpretare Optimalitatea Paretonseamn o situaie mai bun
pentru cel puin un agent fr a dezavantaja niciunalt agent
Optimalitatea Pareto nu nseamn egalitate De exemplu mprirea unui tort ntre 3 persoaneA, B, C A ia 70%, B ia 30%, C nu ia nimic Aceast stare este un echilibru optim Pareto, deoarece
pentru a-i da lui C ceva, A sau B ar trebui s renune la ceva
Totui, implic alocarea tuturor resurselor O stare n care A ia 50%, B ia 30% iC nu ia nimic nu este
optim Pareto C poate lua 20% fr a-i afecta pe A sau B
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
50/107
50
Aplicaii ale optimalitii Pareto
Probleme de optimizare Traficul n reele de calculatoare
Planificarea task-urilor
Planificarea produciei
Proiectarea componentelor
Procesele de reacii chimice
Economie Analiza eficienei de pia
mbuntirea sistemului de impozitare
Etc.
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
51/107
Interpretarea grafic
51
Pentru jocul:
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
52/107
Ctiguri neliniare
52
Ctigul ateptat pentruA
Toi agenii joac 1 cuprobabilitatea xi 2 cu
probabilitatea 1x
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
53/107
Soluia diferenial
53Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
54/107
Exploatarea soluiei difereniale Presupunem c Bi Cfolosesc strategia cux*= 1/3 Apoate exploata acest fapt alegnd y= 0
54< 0
> 0.385
_
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
55/107
Interpretarea grafic
55Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
56/107
Exemplu mai complex
56
Intersecia se poatedetermina prin
metode numerice
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
57/107
Teoria jocurilor (II)
Jocuri de sum general cu doi ageni1. Reducerea la jocuri de sum nul2. Echilibru Nash pur
3. Echilibru Nash mixt4. Jocuri cooperante
Jocuri cooperante cu n ageni5. Reprezentarea jocurilor n forma caracteristic
6. Nucleul7. Valoarea Shapley8. Nucleolus
57Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
58/107
Cooperarea
n jocurile anterioare, agenii erau raionali i egoiti Prin cooperare, ageni pot obine un ctig mai mare
Rezultatul n care suma utilitilor este maxim
Problema estemprirea ctigului suplimentarobinut
Soluia corectreprezint poziiile de negociere alecelor doi ageni Poziia de negociere abilitatea de negociere
58Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
59/107
Exemplul 1
Dac nu exist cooperare, jocul are: Echilibre Nash pure: (10, 40) i (40, 10) Echilibru Nash mixt: Renault (0.5, 0.5) i Peugeot (0.8, 0.2),
cu ctig0 pentru ambele companii
59Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
60/107
Cooperarea
Matricea sum(engl.sum matrix) a jocului reflectctigul total care poate fi obinut prin cooperare
Matricea ameninrilor(engl.threat matrix) esteutilizat pentru descrierea puterii de negociere a
agenilor
60Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
61/107
Interpretare
Prima linie cuprinde doar valori pozitive, deci Rare o poziieputernic de negociere (indiferent ce ar alege P, Rctig maimult)
Dac nu se ajunge la o nelegere, Ramenin c va alege F Pctig 10 n loc de 40
Pare o poziie slab de negociere deoarece ameninarea de a
alege Fpoate fi contracarat de ctre Rprin folosirea strategieimixte (0.5, 0.5), care este de asemenea un echilibru Pctig 0 n loc de 40
Difereniala ameninrii(engl.threat differential) estevaloareajoculuipentru matricea ameninrilor, n acest caz, 30
61Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
62/107
Soluia Soluia pentru un joc cooperant cu doi ageni:
Ctigul total este valoarea maxim din matricea sum Diferena de ctig dintre ageni este difereniala ameninrii
Pentru exemplul anterior: Ctigul total = 50 Diferena ctigurilor= 30 R+ P= 50 i RP= 30 Prin urmare, Robine 40 iar Pobine 10
Nu conteazstrategiile jucate, att timp ct se obine ctigul
total i se respect modul de mprire a acestuia Pentru strategiile (R:F/ P:M), ctigurile agenilor sunt cele date direct de
rezultatul jocului Pentru strategiile (R:M/ P:F), Ptrebuie s i plteasc 30 de uniti lui R
62Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
63/107
Exemplul 2
Ctigul total maxim este 5 Matricea ameninrilor este:
Difereniala ameninrii este 1, deoarece combinaia destrategii (1,2) reprezint un punct a
Soluia jocului: Rctig 3, Cctig 2 Agenii joac (R:2 / C:1)i Colin i pltete 2 uniti lui Rose
63Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
64/107
Exemplul 3 S considerm urmtoruljoc cooperant:
Ctigultotal maxim este 9 Matricea ameninrii este:
Are un echilibru mixt, cu strategiile (2/3, 1/3) pentru Rose i(5/6, 1/6) pentru Colin iar valoarea jocului este 4/3
Rose obine 31/6 Colin obine 23/6 darctigul su este mai mic cu 1/6 dect
ctigulobinut fr cooperare, prin echilibrul Nash pur (4) Cooperarea nu asigur ntotdeauna un ctig mai mare pentru
fiecare agent
64Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
65/107
Teoria jocurilor (II)
Jocuri de sum general cu doi ageni1. Reducerea la jocuri de sum nul2. Echilibru Nash pur
3. Echilibru Nash mixt4. Jocuri cooperante
Jocuri cooperante cu n ageni5. Reprezentarea jocurilor n forma caracteristic
6. Nucleul7. Valoarea Shapley8. Nucleolus
65Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
66/107
Fie mulimea de ageni { P1, P2, ..., Pn } Marea coaliie este mulimea tuturor agenilor:G= { P1, ,Pn }
Ocoaliiereprezint orice submulime nevid a lui G Fiecare coaliie ncearcs-i maximizeze ctigul Funcia caracteristic vnregistreaz ctigul maxim
pentru fiecare coaliie (valoarea coaliiei) Joc superaditiv:
v(ST) v(S) + v(T), unde Si Tsunt coaliii fr agenicomuni
Definiii
66Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
67/107
Oalocare(engl. imputation) este mulimea dectiguri (x1,x2, ...,xn) care satisface urmtoarelecondiii: Suma ctigurilor este maximul posibil Fiecare agent obine un ctig cel puin
la fel de bun ca acela obinut dac nuar coopera
O alocare este o mprire eficienti individualraional
Alocare
67Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
68/107
Exemplul 1 Fie un joc cu 3 ageni: P1, P2, P3 Fiecare poate alege cap (H) sau pajur (T) Dac doi ageni aleg la fel iar al treilea diferit, acesta va plti
cte 1 unitate fiecruia din ceilali doi. Altfel, toi agenii primesc0 n total ({P1, P2, P3}) = 0 (mpreun nu pot ctiga nimic) Presupunem c se formeaz coaliia S= {P2, P3} Contra-coaliia va fi Sc= {P1} Rezult un joc de sum nul cu matricea:
68Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
69/107
Coloanele 2 i 3 sunt dominate(0 < 1 i2 < 1)
Valoarea jocului este1 (echilibru minimax mixt) ({P1}) =1(ct se ateapt s ctige P1) ({P2, P3}) = 1(ct se ateapt s ctige coaliia S) Datorit simetriei jocului, funcia caracteristic este:
Alocri:xi 1, i= 1, 2, 3;x1 +x2 +x3= 0
Exemplul 1
69
Sdorete s-imaximizeze ctigul
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
70/107
Exemplul 2 ({P1, P2, P3}) este
ctigul total maximcare poate fi ctigat
din cele 8 combinaii({P1, P2, P3}) = 1
70Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
71/107
Exemplul 2 Fie S= {P1, P3} i Sc= {P2}
Sc: (1/3, 2/3)
S: (1/3, 0, 2/3, 0)
v({P1, P3}) = 4/3, v({P2}) =1/3 Analog:
v({P1, P2}) = 1, v({P3}) = 0
v({P2, P3}) = 3/4, v({P1}) = 1/4
71Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
72/107
Teoria jocurilor (II)
Jocuri de sum general cu doi ageni1. Reducerea la jocuri de sum nul2. Echilibru Nash pur
3. Echilibru Nash mixt4. Jocuri cooperante
Jocuri cooperante cu n ageni5. Reprezentarea jocurilor n forma caracteristic
6. Nucleul7. Valoarea Shapley8. Nucleolus
72Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
73/107
Nucleul Nucleul(engl. core) unui joc cu nagenieste mulimea
alocrilor nedominate
Nucleul unui joc cu funcia caracteristic veste mulimea tuturor
alocrilor x= (x1,x2, ...,xn) astfel nct pentru orice coaliieS= {Pi1, Pi2,,Pim}avem:xi1 +xi2 + +xim v(S)
Orice alocare din nucleu poate fi privit ca o soluie a jocului
Nucleul este stabil
Dac o alocare nu se afl n nucleu, atunci exist cel puin ocoaliie ai crei membri nu obin ctigul maxim pe care l-arputea obine altfel. Aceti ageni prefer o alt alocare
73Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
74/107
Exemplul 1
3 studeni doresc s cumpere o carte, care cost 110$
Pentru 2 cri sau 3 cri cumprate mpreun, existo reducere de 10$, respectiv 20$ / exemplar
Valorile coaliiilor exprim banii economisii
74Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
75/107
Exemplul 1
Fie x= (x1,x2,x3) o alocare din nucleu. Atunci:
75Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
76/107
Exemplul 2
Fiind un joc de sum nul, are nucleul vid (jocul este instabil)
Fie x= (x1,x2,x3)o alocare din nucleu Vom avea: Deoarece xeste o alocare:
Prin urmare:
Similar obinemx1 1 ix2 1 Dar valorile obinutecontrazic condiia:x1+x2+x3= 0 n concluzie, xnu poate fi o alocare i deci nucleul este vid Nu exist o alocare astfel nct fiecare agent s fie mulumit
76Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
77/107
Exemplul 3 Un vnztor Svrea s vnd un cal. Pentru S, dac
nu este vndut, calul nu valoreaz nimic Un fermier Fi un mcelar Bvor s l cumpere Pentru F, calul valoreaz 1000$ Pentru B, calul valoreaz 500$
77Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
78/107
Exemplul 3
78Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
79/107
Exemplul 3
79
Bnu primete nimic, dar
prezena lui este importantpentru poziia de negocierea vnztoruluiS
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
80/107
Normalizarea unui joc
Albert, Bobbie i Colin doresc s cumpere ocarte de 110$
Albert are un card de reduceri Costul crilor este urmtorul:
80Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
81/107
Normalizarea unui joc
81Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
82/107
Interpretarea grafic a nucleului
82Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
83/107
Western Union (W),Hughes Aircraft (H) iGeneral Telephone (G)i pot lansa satelii decomunicaie individuali,sau pot folosi mpreunnite satelii, n diversecombinaii
Costurile sunt exprimaten milioane de dolari
83
Nucleu vid
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
84/107
Teoria jocurilor (II)
Jocuri de sum general cu doi ageni1. Reducerea la jocuri de sum nul2. Echilibru Nash pur
3. Echilibru Nash mixt4. Jocuri cooperante
Jocuri cooperante cu n ageni5. Reprezentarea jocurilor n forma caracteristic
6. Nucleul7. Valoarea Shapley8. Nucleolus
84Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
85/107
Valoarea Shapley
Nucleul ofer o mulime de soluii pentru un joc Unele jocuri nu au nucleu Nu exist o modalitate de a evalua corectitudinea
alocrilor din nucleu Ideea de baz a valorii Shapley:
Fiecare agent trebuie s primeasc un ctig corespunztorcontribuiei sale marginale la coaliie
Pentru nageni, exist n!ordonri n care un agentse poate altura celorlali Valoarea Shapley reprezint media dup toate ordonrile
posibile
85Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
86/107
Valoarea Shapley: definiie
86Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
87/107
Exemplul 1
Fie un joc cu doi ageni i urmtoarea formcaracteristic: v({}) = 0, v({1}) = 1, v({2}) = 3,v({1, 2}) = 6
Sunt 2! permutri posibile: (1, 2) i (2, 1) Valorile Shapley:
87Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
88/107
Exemplul 2
88Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
Calculul valorii Shapley pentru
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
89/107
Calculul valorii Shapley pentruun singur agent
89Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
90/107
Exemplu
90Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
91/107
Proprieti
Valoarea Shapley exist ntotdeauna, este unic ieste ntotdeauna fezabil (suma ctigurilor ageniloreste maxim)
Poate s nu aparin nucleului, chiar dac jocul arenucleun acest caz, este instabil
Presupune un efort de calcul mare Poate fi folosit pentru un numr mic de ageni
Dar exist metode de calcul aproximative ntr-un sistem multi-agent real, chiar calculul valorilor
sub-coaliiilor poate fi foarte complex
91Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
92/107
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
93/107
Pentru fiecare alocare xi coaliie S, definim excesullui Sn xastfel:
Excesul poate fi considerat o msura nefericiriicoaliiei Sn cazul alocrii x
Scopul este de a gsi alocarea care minimizeaz
cel mai mare exces es(x) ncercm s facem cea mai nefericit coaliie ct mai
puin nefericit
Modul de calcul
93Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
94/107
Fie jocul cu urmtoarea form caracteristic:v(A) = v(B) = v(C) = 0
v(AB) = 60, v(AC) = 80, v(BC) = 100, v(ABC) = 105
ncepem cu o alocare arbitrar, x= (20, 35, 50) Calculm excesele:
Exemplul 1
94Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
95/107
Exemplul 1 Excesul cel mai mare este eBC(x) = 15 l putem minimiza prin alegerea unei alocri care ofer
un ctig mai mare coaliiei BC(mai puin luiA)
Deoarece eAC(x) > eAB(x), putem lua 5 de laAi s idm lui C Obinem o nou alocare y= (15, 35, 55)
Rezultatul obinut este minimul: orice exces micorat ncontinuare va conduce la mrirea altuia
95Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
96/107
Interpretarea geometric
Nucleolus estepunctul cel maiinterior al nucleului
96Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
97/107
Exemplul 2 Fie jocul cu urmtoarea form caracteristic:
v(A) = v(B) = v(C) = 0
v(AB) = 4, v(AC) = 0, v(BC) = 3, v(ABC) = 6
ncepem cux= (2, 3, 1)
97
cel mai mare exces
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
98/107
Exemplul 2 eABC(x) nu poate fi minimizat (excesul marii coaliii este
ntotdeauna 0) Alegem urmtorul exces maxim:
eC(x) = eAB(x) = eBC(x) =1 Lum 0.5 de laAi dm lui B Obinem nucleolus y= (1.5, 3.5, 1)
98Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
99/107
Interpretarea geometric
99Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
100/107
Proprieti Exist ntotdeauna i este unic Se afl n nucleu dac nucleul nu este vid este stabil Se calculeaz iterativ, rezolvnd succesiv o serie de programe
liniare
Pentru 3 ageni, exist formule directe (vezi suportul de curs)
100Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
Comparaie valoarea Shapley -
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
101/107
Co pa a e a oa ea S ap eynucleolus
Valoarea Shapley -
101
Nucleolus -
Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
102/107
Aplicaii n viaa real
Distribuirea costurilor hidroelectrice n India
102Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
103/107
Costurile
103Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
104/107
Valorile coaliiilor
104Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
105/107
Valorile Shapley
105Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
Nucleul, nucleolus,
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
106/107
, ,valoarea Shapley
106Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm
7/30/2019 Sisteme multiagent. Teoria jocurilor 2
107/107
Distribuia costurilor
Tamil Nadu (T) ar trebui s plteasc n jur de 75%
Andhra Pradesh (A) restul de 25% Kerala-Mysore (K) are resurse importante i deci nu ar trebui
s plteasc nimic
Top Related