Sisteme multiagent. Teoria jocurilor 1

Modelarea şi analiza sistemelor multi-agent

4. Modelarea raţionalităţii agenţilor cu ajutorul teoriei jocurilor (I) Florin Leon

Universitatea Tehnică „Gheorghe Asachi” din Iaşi Facultatea de Automatică şi Calculatoare

http://florinleon.byethost24.com/curs_masma.htm

Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

2

Modelarea raţionalităţii agenţilor cu ajutorul teoriei jocurilor (I)

Jocuri de sumă nulă cu doi jucători

1. Introducere

2. Dominanţa

3. Diagramele de mişcare

4. Echilibru minimax pur

5. Echilibru minimax mixt

6. Jocuri matriceale (2 x n) şi (m x 2)

7. Jocuri matriceale (m x n)


3



1. Introducere

2. Dominanţa







4

Teoria jocurilor

Studiază interacţiunile strategice între jucători raţionali care aleg diferite acţiuni pentru a-şi maximiza profitul

Mai formal, reprezintă studiul modelelor matematice de conflict şi cooperare între decidenţi inteligenţi şi raţionali


5

Bazele teoriei jocurilor

Teoria jocurilor este o abordare interdisciplinară menită să studieze comportamentul uman

John von Neumann, Oskar Morgenstern: Theory of Games and Economic Behavior (1944)


Întrebări fundamentale

Ce înseamnă alegerea raţională a unor strategii când rezultatele depind de strategiile necunoscute alese de alţii?

În jocuri care permit câştiguri colective, este raţională cooperarea sau urmărirea scopurilor individuale? Când este raţională cooperarea şi când este raţional comportamentul egoist?

Sunt diferite interacţiunile continue de cele singulare?

Pot apărea spontan reguli de cooperare din interacţiunile indivizilor egoişti?

Este „raţional” comportamentul uman real? Care sunt diferenţele: sunt oamenii mai cooperanţi sau mai egoişti decât ar fi „raţional”?

6 Florin Leon, Modelarea si analiza sistemelor multi-agent, http://florinleon.byethost24.com/curs_masma.htm

7

Raţionalitatea

Teoria jocurilor studiază modul în care se comportă jucătorii raţionali

Potrivită pentru modelarea agenţilor inteligenţi

Fiecare agent încearcă să-şi maximizeze recompensele (venituri, profituri, alte beneficii)

Ajută studiul alocării resurselor

Restrânge numărul posibilităţilor de analizat (comportamentul raţional este mai predictibil decât cel iraţional)

Furnizează un criteriu pentru evaluarea eficienţei unui sistem economic (ineficienţă: reducerea recompenselor unora fără compensaţii suplimentare pentru alţii)


8

Interacţiunile indivizilor

În economia neoclasică, se consideră că indivizii raţionali interacţionează cu un sistem de instituţii (constrângeri): drepturi de proprietate, schimburi bazate pe bani, competitivitatea economică

Indivizii nu interacţionează direct, ci pe baza „condiţiilor pieţei”

Teoria jocurilor analizează interacţiunile directe, nu prin intermediul „pieţei”

„Jocurile” sunt o metaforă pentru probleme care presupun luarea unor decizii sau alegerea unei strategii

Se poate aplica la jocuri propriu-zise, dar şi la interacţiuni din lumea reală: competiţia economică, strategiile militare, poluarea mediului etc.


9

Maximizarea recompenselor

Fiecare jucător / agent trebuie să-şi maximizeze recompensele într-un mediu influenţat de strategiile celorlalţi agenţi

Alegerile unui agent depind de alegerile tuturor celorlalţi agenţi

Fiecare jucător încearcă să-şi maximizeze profitul indiferent de acţiunile celorlalţi jucători

Conflicte, cooperare

Decizii sociale: cu cine şi cum să coopereze

Alegerea raţională a strategiilor poate presupune şi maximizarea recompenselor grupului de agenţi


10

Aplicaţii

Oriunde există interacţiuni strategice între jucători raţionali Economie

Strategii geo-politice

Psihologie

Sociologie

Ştiinţa calculatoarelor (reţele etc.)


11

Elementele unui joc

Un joc este orice situaţie în care:

Există cel puţin 2 jucători

Fiecare jucător are la dispoziţie un număr de strategii posibile

Strategiile alese de fiecare jucător determină rezultatul (engl. “outcome”) jocului

Pentru fiecare rezultat, există un profit (engl. “payoff”) numeric pentru fiecare jucător


12

Dilema inculpaţilor

engl. “prisoner’s dilemma” Jucători

2 inculpaţi

Acţiuni Inculpatul 1: Mărturiseşte, Neagă Inculpatul 2: Mărturiseşte, Neagă

Strategii Inculpaţii îşi aleg acţiunile simultan,

fără a cunoaşte acţiunea celuilalt

Rezultate Numărul de ani de închisoare

Profitul Mai puţini ani profit mai mare


13

Reprezentarea în forma normală (strategică)

O matrice care conţine jucătorii, strategiile şi profiturile

Se presupune că jucătorii acţionează simultan

Pentru dilema inculpaţilor:


14

Jocuri de sumă nulă

Numite şi „jocuri de sumă zero”

Pentru orice rezultat al jocului, profiturile jucătorilor au suma 0

Câştigul lui Rose (“rows”) = – câştigul lui Colin (“columns”)

Pentru un joc de sumă generală, sunt necesare perechi

Pentru un joc de sumă nulă, (2) este echivalent cu (2, –2)

În limba română ar putea fi Laura şi Cristi


15



1. Introducere

2. Dominanţa







16

Dominare. Definiţii

O strategie S domină o strategie T (T este dominată de S) dacă orice rezultat al lui S este cel puţin la fel de bun ca rezultatul corespunzător al lui T

Un jucător raţional nu trebuie să joace niciodată o strategie dominată

Dacă fiecare jucător are o strategie dominantă şi o joacă, atunci combinaţia acestora şi profiturile corespunzătoare constituie echilibrul strategiilor dominante ale jocului


17

Exemple


18

Exemple


19

Exemple


20

Echilibrul strategiilor dominante


21



1. Introducere

2. Dominanţa







22

Diagrame de mişcare

În fiecare linie, trasăm o săgeată de la fiecare intrare către intrarea minimă de pe linie

Colin vrea să-şi maximizeze profitul, minimizând negatul profitului lui Rose

În fiecare coloană, trasăm o săgeată de la fiecare intrare către intrarea maximă de pe coloană

Rose vrea să-şi maximizeze profitul


23

Diagrame de mişcare


24

Exemplu mai complex


25



1. Introducere

2. Dominanţa







26

Echilibru minimax pur

Un rezultat al unui joc matriceal este numit punct şa (engl. “saddle point”) sau echilibru minimax pur dacă este minimul liniei şi maximul coloanei sale

Echilibrul minimax este un caz particular al echilibrului Nash pentru jocuri de sumă generală (vezi cursul 5)


27

Rezultate teoretice

Principiul punctului şa: Dacă o matrice are un punct şa, ambii jucători trebuie să joace strategia indicată de acesta

Pentru orice joc matriceal, există un număr v numit valoarea jocului, astfel încât Rose are o strategie care garantează că va câştiga cel puţin v, iar Colin are o strategie care garantează că Rose nu va câştiga mai mult decât v

Teoremă: Într-un joc de sumă nulă cu doi jucători, dacă intrarea (Ri, Cj) este un echilibru de strategii dominante, atunci aceasta este şi un echilibru minimax pur


28

Exemple


29

Teoremă

Oricare 2 puncte şa dintr-un joc matriceal au aceeaşi valoare

Demonstraţie:

Presupunem că a şi b sunt puncte şa

Deci a = b

a ≤ c a ≥ d b ≤ d b ≥ c

a ≤ c ≤ b b ≤ d ≤ a

a ≤ c ≤ b ≤ d ≤ a


30



1. Introducere

2. Dominanţa







31

Jocuri fără echilibru minimax pur


32

Echilibru minimax mixt

von Neumann a demonstrat că pentru orice joc de sumă nulă cu doi jucători se poate găsi întotdeauna un echilibru minimax mixt

Strategie mixtă = combinaţie de strategii cu probabilităţi fixe

De exemplu, jucătorul alege strategia A cu probabilitatea de 25% şi strategia B cu probabilitatea de 75%


33

Exemplu


34

Strategii mixte

Strategia lui Rose: (y, 1-y)

Strategia lui Colin: (x, 1-x)

Profitul aşteptat al lui Rose: E[P] = y G xT

Rose încearcă să maximizeze E[P] variind y

Colin încearcă să minimizeze E[P] variind x


35

Model de calcul: Colin (I)

Profiturile aşteptate ale strategiilor lui Rose:

3 situaţii posibile pentru Colin


36

Model de calcul: Colin (II)

Rose ar alege y = 1 şi ar câştiga mai mult de -1/2

Rose ar alege y = 0 şi ar câştiga mai mult de -1/2


37

Profiturile R1 şi R2


38

Model de calcul: Rose

La fel se poate calcula strategia optimă a lui Rose


39

Metoda resturilor (I)

engl. “oddment method”


40

Metoda resturilor (II)

Metoda funcţionează numai pentru jocuri 2 x 2 fără echilibru pur!


41

Jocuri cu echilibru pur

Diferenţele au acelaşi semn

Prima linie domină linia a doua

Strategia (3/4, 1/4) nu este optimă pentru Colin

Rose alege sigur R1 iar Colin ar trebui să aleagă C1


42

Teorema Minimax

Orice joc de sumă nulă m x n cu doi jucători are o soluţie, un număr unic v numit valoarea jocului şi există strategii optime (pure sau mixte) pentru Rose şi Colin astfel încât:

Dacă Rose joacă strategia optimă, profitul său aşteptat nu va fi mai mic decât v, indiferent ce joacă Colin

Dacă Colin joacă strategia optimă, negatul profitului său aşteptat nu va fi mai mare decât v, indiferent ce joacă Rose


43



1. Introducere

2. Dominanţa







44

Rezultat

Jocurile (2 x n) şi (m x 2) pot fi întotdeauna reduse la jocuri (2 x 2) şi deci pot fi rezolvate prin metodele prezentate anterior


45

Jocuri (m x 2)


46

Exemplu

Profitul minim al lui Rose

Strategia optimă a lui Colin

x1 = R1 ∩ R2

5 x1 – 3 = 2 – 2 x1

x1 = 5/7


47

Reducerea la (2 x 2)

Strategia optimă a lui Colin este (5/7, 2/7)

Dacă Colin alege punctul x1, Rose poate răspunde doar cu R1 şi R2

R3 i-ar aduce profit mai mic

Deci Rose nu va juca R3 deloc

Jocul se reduce la (2 x 2)


48

Rezolvare

Valoarea jocului se poate afla şi calculând, de exemplu: R1(x1) = 2 · 5/7 – 3 · 2/7 = 4/7


49

Exemplul 2


50

Rezolvare

Contează doar R4 şi R5, care se intersectează în punctul x:

Strategia optimă a lui Colin este (3/5, 2/5)

Valoarea jocului este: 3/5 + 6 · (1 – 3/5) = 3 (pe R4)

Jocul se reduce la (2 x 2)


51

Jocuri (2 x n)

Se transpune matricea şi se transformă jocul în (n x 2)

G’ = – GT

Prin transpunere, Colin devine „noua Rose” iar Rose devine „noul Colin”

Se rezolvă cu metoda prezentată anterior


52

Exemplu


53

Rezolvare

Intervin 4 segmente: R2, R3, R1, R5

Minimul este R1 ∩ R3

x0 = 4/7

Strategia optimă a noului Colin este (4/7, 3/7)

Valoarea jocului este 1/7


54

Jocul devine (2 x 2)

Strategia optimă pentru noua Rose este:

(R1, R2, R3, R4, R5) = (2/7, 0, 5/7, 0, 0)

Pentru jocul iniţial, strategiile optime sunt:

Rose: (4/7, 3/7)

Colin: (2/7, 0, 5/7, 0, 0)

Rezolvare


55



1. Introducere

2. Dominanţa







56

Jocul culorilor


57

Exemplu

Jocul culorilor nu are echilibru minimax pur


58

Programare liniară

Jocurile matriceale (m x n) nu pot fi reduse la jocuri (2 x 2)

Se rezolvă prin metode de programare liniară

Pentru cazul n-dimensional, este nevoie de ajutorul calculatorului


59

Rezolvare

Vom considera mai întâi un joc (2 x 5) pentru a ilustra metoda şi a verifica rezultatele

Strategia lui Colin este dată de probabilităţile (x1,..., x5)


60

Transformarea pentru PL (I)

Profiturile posibile ale lui Rose

Rose doreşte profitul maxim

Colin încearcă minimizarea acestuia


61

Transformarea pentru PL (II)


62

Rezolvarea cu Excel (I)


63

Rezolvarea cu Excel (II)

Din meniu: Tools Solver (sau Data Solver)

Dacă Solver nu există în meniul Tools, se adaugă din Tools Add-Ins


64

Rezolvarea cu Excel (III)


65

Soluţia

Valoarea jocului:

1/7

Strategia optimă a lui Colin:

(2/7, 0, 5/7, 0, 0)

Strategia optimă a lui Rose:

(4/7, 3/7)

valorile negate ale multiplicatorilor Lagrange


66

Exemplu de joc (m x n)

Colin: (4/13, 4/13, 5/13)

Rose: (5/13, 2/13, 6/13)

Valoarea jocului: -1/13


67

Jocul culorilor

Colin: (1/2, 1/2, 0)

Rose: (1/2, 1/2, 0)

Valoarea jocului: 0

nimeni nu trebuie să joace cartea „2”


68

Problema pescarilor (I)

În Jamaica pescarii pescuiesc la ţărm sau în larg (sau ambele) în funcţie de curenţi

Strategia optimă a pescarilor: (0.67, 0, 0.33)

Strategia optimă a curentului (!): (0.31, 0.69)


69

Problema pescarilor (II)

Pescarii urmează această strategie cu un profit de 13.3

Curenţii sunt prezenţi în 25% din timp

Valoare apropiată de 31%, dar nu egală

Pescarii ar putea alege strategia (0,1,0) cu un profit de 14.35


70

Avantajul soluţiei minimax

Însă cu strategia (0.67, 0, 0.33) ei îşi garantează un profit de cel puţin 13.3

Dacă ar alege strategia (0,1,0) şi într-un an curenţii ar fi prezenţi 35% din timp, ar câştiga doar 11.85

Avantajul principal al soluţiei minimax este garantarea unui profit minim, independent de deciziile celorlalţi jucători


Referinţe

Raymond Chan

Games and Strategic Thinking Department of Mathematics, The Chinese University of Hong Kong

http://www.math.cuhk.edu.hk/course/0910/ugb253na


Sisteme multiagent. Teoria jocurilor 1

Documents

Transcript of Sisteme multiagent. Teoria jocurilor 1