-
Notifications
You must be signed in to change notification settings - Fork 16
/
game_theory.theory.txt
59 lines (54 loc) · 3.69 KB
/
game_theory.theory.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
GAME_THEORY
n-person game :
- représenté par une array de dimension n, "playoff matrix"
- chaque dimension représente une action possible (uniformément aléatoire)
- case représente gain/perte de combinaison d'actions
- si valeurs de matrices sont seulement m, -m et 0, il s'agit d'un "zero-sum gam"
- ex de 2-person zero-sum game :
- J1 == "Joueur 1"
- P/F/C == Pierre/Feuille/Ciseau
J2
P F C
P 0 -1 1
J1 F 1 0 -1
C -1 1 0
- choix d'une ou plusieurs colonnes par une dimension : "strategy"
- "pure strategy" : 100% sur une seule colonne
- "mixed strategy" : % sur plusieurs colonnes
- probablité de chaque case = multiplication de prob. de colonne sur chaque dimension
- expected value pour un ensemble de strategies données : ∑ (P(case) * case)
- peut être aussi calculée :
- soit :
- R la rows matrix des P des rows
- C la column matrix des P des columns
- P la playoff matrix
- par R*P*C
Solving a game :
- étant donné strategy d'une autre dimension, deviner strategy de dimension restante maximisant l'expected value
- connait R ou C, et doit deviner le second, tel qu'expected value est maximisée
- ex sur matrice 3*3, en connaissant C :
[ x y z ] * [ . . . ] * [ . ] = [ x y z ] * [ . ] = .x + .y + .z
[ . . . ] [ . ] [ . ]
[ . . . ] [ . ] [ . ]
Sum(x,y,z) = 1, et 0 <= x,y,z <= 1
Donc il faut mettre 1 au terme ayant le plus grand coefficient et 0 aux autres
- donc toujours une pure strategy est la réponse
- donc si l'on souhaite minimiser expected value, en sachant qu'autre dimension cherchera à maximiser :
- "minimax criterion"
- "reduction by dominance" :
- enlève de P les dimension-wise rows (DWR) dont chaque valeur est < un autre DWR ("domination")
- fait pareil pour chaque dimension
- puis :
- si P restante est 2*2, et que dimension inconnue est R :
- obtenir les équations de toute stratégy de C, sachant qu'il s'agit toujours de pure strategy :
- [ x 1-x ] * [ . . ] * [ 1 ] = .x + .
[ . . ] [ 0 ]
- pareil avec [ 0 ] = .x + .
[ 1 ]
- C choisira l'équation donnant max., donc pour minimiser -> choisir interesection des équations
- soit résoudre .x + . = .x + .
- x résultant est le minimax pour [ x 1-x ]
- l'expected value du minimax de chaque dimension est toujours la même, il s'agit de l'"expected value of the game"
- "maximax criterion" possible aussi, où l'on cherche alors max