1
Mémoire - Marchandage et partage d'objets
Bastien Ibanez - Lucas Bugeaud - (Valentin Autie) 5 mai
2021
Table des matières
1
2
|
Introduction au principe de marchandage
1.1 Motivations
1.2 Quelques exemples de marchandages
1.3 Exemple d'étude
Les jeux de marchandage selon J.F Nash
|
3
3
3
4
5
|
|
2.1
|
Mise en place du modèle
|
5
|
|
|
2.1.1 Notations
|
5
|
|
|
2.1.2 Théorie de l'utilité
|
5
|
|
|
2.1.3 Définition du modèle
|
6
|
|
|
2.1.4 Les propriétés de Nash
|
6
|
|
2.2
|
Existence et unicité de la solution de Nash
|
7
|
|
2.3
|
Exemple d'application réelle de cette théorie
|
9
|
|
2.4
|
Conclusion sur la partie théorique de la solution de
Nash
|
10
|
3
|
Développement numérique du jeu de
marchandage
|
11
|
|
3.1
|
De la théorie au numérique
|
11
|
|
3.2
|
Exhibition de la frontière de Pareto
|
11
|
|
3.3
|
Solution du jeu de Nash
|
14
|
4
|
Étude numérique : voiture
partagée "uberisée"
|
19
|
|
4.1
|
Rappel introductif
|
19
|
|
4.2
|
Notations
|
20
|
|
4.3
|
Choix de la dimension 1
|
20
|
|
4.4
|
Perspectives d'études
|
20
|
|
4.5
|
Application de l'algorithme à un cas simple
|
21
|
|
4.6
|
La problématique du mensonge
|
23
|
|
|
4.6.1 Jeu à information parfaite
|
23
|
|
|
4.6.2 Nombre d'occurrence de chaque solution en information
parfaite
|
25
|
|
|
4.6.3 Jeu à information imparfaite
|
26
|
|
4.7
|
Étude statistique de la nature de la solution de Nash
dans notre modèle
|
29
|
|
4.8
|
Conclusion de la partie numérique sur la solution de
Nash
|
32
|
2
5
|
La solution de Nash : une solution
faisant débat
5.1 Remise en cause de la solution de Nash via l'axiome
d'indépendance aux alterna-
tives non pertinentes
5.2 Axiome de monotonicité de Kalai-Smorodinsky
|
34
34
37
|
6
|
Conclusion
|
|
42
|
7
|
Bibliographie
|
|
43
|
8
|
Appendice
|
|
44
|
|
8.1 Codes et résultats consoles annexe de la partie 4
|
44
|
|
8.2 Code réalisé tout au long de ce mémoire
|
48
|
|
8.2.1 Fichier
|
Nash_solver.py
|
48
|
|
8.2.2 Fichier
|
Fonctions_distances.py
|
54
|
|
8.2.3 Fichier
|
Etude_probleme_voiture_partagee
56
|
|
|
8.2.4 Fichier
|
Applications_theorie_des_jeux.py
|
72
|
|
8.2.5 Fichier
|
Applications_statistiques.py
|
82
|
3
Ce mémoire traite la notion de jeu de marchandage
apparue en 1950 suite aux recherches faites par le mathématicien J.F
Nash qui s'intéressait à la collaboration pour un profit mutuel
entre deux individus. Il se décompose en trois parties majeures. Dans la
première, nous introduisons, expliquons et démontrons la
démarche suivie par J.F Nash pour trouver une solution à cette
collaboration entre deux individus. La deuxième partie nous donne
l'occasion d'implémenter une telle solution et de la mettre en pratique
dans un problème que nous avons imaginé. Le problème
consiste à étudier une situation lors de laquelle une voiture
doit rendre service à deux usagers en les amenant à la
destination qu'il souhaite tout en ayant la possibilité de les prendre
conjointement. L'enjeu de cette partie est d'étudier la viabilité
de la solution de Nash appliquée à une problématique
actuelle. Enfin dans la troisième partie, nous allons voir que la
démarche consistant à se reposer sur l'utilisation d'axiomes pour
trouver une solution n'est pas unique et qu'il est possible de proposer
d'autres axiomes permettant de trouver une solution différente et dans
certains cas plus pertinente.
1 Introduction au principe de marchandage
1.1 Motivations
Un jeu de marchandage s'intéresse à la
manière dont deux agents (ou plusieurs par extension du jeu initial) se
partagent leurs biens. Il peut s'agir d'une production agricole, d'un bien
matériel tel que du mobilier, un objet de valeur,... voire d'un bien
"immatériel" tel que de l'argent, du temps, de l'énergie... Un
jeu de marchandage est donc un jeu de négociation, où chacun des
agents a un intérêt pour ce que l'autre possède et est
prêt à céder tout ou une partie de ce qu'il possède.
Un exemple simple est le cas d'un acheteur et d'un vendeur négociant le
prix d'un objet auquel le premier attribut plus de valeur que le second. Il
n'existe alors pas qu'un prix sur lequel les joueurs peuvent trouver un
arrangement "convenable".
Plus généralement, on se posera la question de
savoir s'il est possible, lorsque les agents ont une multitude de partages
possibles, de parvenir à une répartition unique qui ne souffre
pas de meilleures alternatives possibles.
Cette première partie présente la solution
proposée par John Nash en 1953. La démarche entreprise est
axiomatique, elle consiste donc à poser un certain nombre d'axiomes que
la solution doit satisfaire. Bien choisis, ces axiomes permettent de
révéler l'existence voire l'unicité d'une solution.
1.2 Quelques exemples de marchandages
Afin de se familiariser avec la notion de marchandage, il est
utile d'expliciter quelques exemples simples de jeu de marchandage. Un premier
jeu de marchandage fait par exemple intervenir le lègue d'un
héritage entre les individus d'une même famille. Ces derniers
doivent se répartir des biens matériels (maisons, mobiliers,
objets de valeurs) ainsi que des biens immatériels (argent, actions)
auxquels ils n'attribuent pas la même utilité. Les
possibilités de partage sont dénombrables et chacune d'elle
attribue une certaine utilité à chacun des individus. Un jeu de
marchandage consiste dans ce cas à trouver le "meilleur" partage parmi
tous ceux possibles. La question logique qui s'ensuit consiste à se
demander ce qui définit un partage comme étant le "meilleur". La
démarche axiomatique proposée par J.F Nash pour résoudre
ce type de jeu consiste justement à définir cela.
Prenons un autre exemple simple faisant intervenir un artiste
et son client potentiel. L'artiste a peint un tableau qu'il souhaite
désormais vendre, et le client souhaite l'acheter. Les deux
protagonistes doivent s'entendre sur un prix. En fonction du montant, chacun
éprouve une utilité qui
4
lui est propre. Pour évaluer le prix de son oeuvre,
l'artiste prend en considération le temps qu'il a mis a faire l'oeuvre,
son attrait pour l'argent ainsi qu'un tas d'autres facteurs. Il en va de
même pour le client qui considère le temps qu'il a mis à
gagner cet argent, son niveau de satisfaction s'il arrive à prendre
possession de l'oeuvre etc... Le jeu de marchandage consiste donc ici à
trouver le prix sur lequel les deux personnes devraient arriver à
s'entendre sous peine de ne pas faire affaire.
1.3 Exemple d'étude
Parmi les jeux de marchandages que nous avons pu imaginer,
nous en avons choisi un qui deviendra notre objet d'étude principal.
Nous l'avons construit et amélioré au fur et à mesure. Le
processus de modélisation s'est donc fait en plusieurs étapes. A
l'origine, nous voulions prendre l'exemple d'une voiture autonome qui
était un bien partagé entre plusieurs utilisateurs. Le jeu se
développait de la façon suivante : à tout moment, deux
utilisateurs de la voiture pouvaient simultanément avoir recours
à son utilisation pour se rendre quelque part. L'utilisation de la
voiture était donc évidemment un gain de temps pour les deux
usagers dont l'utilité dépendait du temps nécessaire pour
se rendre à leur destination. La voiture étant un bien
partagé entre ces deux utilisateurs, chacun était donc
obligé de concéder un peu de son utilité. L'utilisation de
la voiture utilisée séparément était un gain de
temps pour les deux usagers. Cependant, le fait que la voiture soit un bien
partagé implique un devoir moral à chacun des utilisateurs, ces
derniers sont donc obligés de concéder un peu de leur
utilité afin que l'autre puisse profiter de l'utilisation de la voiture.
On peut dénombrer neuf alternatives possibles, nous en listerons 4
d'entre-elles, les autres se devinant facilement :
-- la voiture vient chercher J1 puis J2, dépose J1 puis
J2
-- la voiture va chercher J1, le dépose, elle va
ensuite chercher J2 pour le déposer
-- la voiture va chercher J1 et J2 doit se rendre à
pied à destination
-- chacun des joueurs se rend à pied à sa
destination.
Finalement, après avoir calculé les couples
utilités procurées par chacune des alternatives, il revenait au
logiciel de la voiture la responsabilité de faire l'arbitrage entre les
alternatives et choisir la plus pertinente au sens du jeu de marchandage, ce
choix sera d'ailleurs l'enjeu de la première partie qui consistera
à présenter la solution proposée par J.F Nash.
Le jeu tel que présenté représentait
quelques limites. En effet, nous verrons par la suite, que la résolution
du jeu selon Nash répond à une logique précise qui
implique qu'en connaissance de tous les facteurs intervenant dans un jeu, il
est facile pour le joueur de connaître la solution induite. Le mensonge
fait donc partie intégrante du jeu de marchandage si un joueur souhaite
tourner le résultat à son avantage. Or, conceptuellement, une
voiture partagée induit une entente préalable entre les
utilisateurs, la malhonnêteté n'est donc pas un facteur
très réaliste. Un autre facteur un peu limitant concernait le
positionnement de la voiture. On imaginait que la voiture non-utilisée
se trouvait en permanence à un endroit fixe (tel un parking), or le fait
de rajouter un facteur aléatoire concernant le positionnement de la
voiture qui influerait sur la stratégie des joueurs était un
aspect intéressant à rajouter dans le modèle.
C'est pour cela que le modèle s'est tourné vers
un exemple de compagnie VTC (voiture de transport avec chauffeur, bien que la
notion de chauffeur ne soit pas essentielle ici) comme peut l'être Uber.
Les principes fondamentaux du modèle ne change pas, la voiture Uber
reçoit deux demandes simultanées et doit déterminer quelle
option parmi les 9 disponibles est la plus pertinente, encore une fois du point
de vue d'un jeu de marchandage. Le modèle ainsi posé offre
davantage de possibilités quant à l'introduction de jeux de
mensonges/vérités notamment.
Bien entendu, le modèle possède des limites que
nous exposeront ultérieurement.
5
2 Les jeux de marchandage selon J.F Nash 2.1 Mise en
place du modèle
2.1.1 Notations
On adoptera dans la suite les notations suivantes : -- pour
x, y E II82, on note :
x y lorsque x1 y1 et x2
y2
x « y lorsque x1 <
y1 et x2 < y2
x < y lorsque x y et x
y
xy E 1I82 le produit terme à terme
de x et y
2.1.2 Théorie de l'utilité
Nous verrons par la suite que pour résoudre un jeu de
marchandage, il est nécessaire de mesurer l'utilité que chacun
des agents obtient à chaque issue possible du jeu. Ainsi, la
théorie de l'utilité théorisée par John von Neumann
et Oskar Morgenstern dans Theory of Games and Economic Behavior (1944) permet
de modéliser les préférences d'un agent par une fonction
d'utilité.
Soit C := {c1, ...cN} l'ensemble
des issues pour N co, et L := (p1, ...,pN)
une loterie quelconque, avec øNi«1 pi
= 1, où pn représente la
probabilité de la réalisation de l'issue cn.
Le choix présenté à un agent peut ainsi être
représenté comme une liste de probabilités
associées à chaque issue possible du jeu. On note L
l'ensemble des loteries simples sur l'ensemble des issues C. On
considère à présent la relation de
préférence > sur les L, cette
dernière doit vérifier les axiomes suivants :
1. Complétude :
VL,L' E L, L L'
L
On peut toujours déterminer la préférence
ou l'indifférence de l'individu entre deux loteries
2. Transitivité :
VL,L',L" E L,
(L>L'etL'>L")
L > L"
Elle traduit l'ordre de préférence entre
différentes loteries de manière cohérente.
3. Continuité : Pour les loteries L, L' et L», les
ensembles
{á E [0,1], áL + (1 --
á)L' >
L"} {á E [0, 1],
áL + (1 -- á)L' <
L"}
sont fermés.
Cet axiome traduit le fait que pour un changement très
faible de probabilité, l'agent garde les mêmes
préférences.
4. Indépendance :
VL,L',L" E L,á
E]0,1[, L > L'
e=> áL' + (1 --
á)L"
Grâce à ces axiomes, il est possible de montrer
l'existence d'une fonction d'utilité associée à la
relation de préférence >. A fortiori, on
pourra l'écrire comme une fonction d'utilité de type vNM.
6
Définition 1 (Fonction d'utilité vNM)
La fonction d'utilité U : G ]8 a une forme
d'espérance d'utilité s'il existe un vecteur
(u1, ...uN) tel que pour toute loterie simple L = (p1, ...,pN) E G on a : U(L)
= øNi«1 piui. Une fonction d'utilité respectant
cette propriété est dite fonction d'utilité von
Neumann-Morgenstern (vNM).
On peut à présent exposer le théorème
de Von Neumann et Morgenstern :
Théorème 2.1 (von Neumann-Morgenstern)
Supposons qu'une relation de préférence
¾ sur les loteries satisfassent les 4 axiomes
précédents; alors ¾ peut être
représentée par une fonction d'utilité de type
vNM.
Ajoutons quelques propriétés cohérentes
et utiles qui découlent de la construction d'une telle fonction :
u(L) > u(L') H L
L'.
u(L) < u(L') H L ã
L'.
u(L) = u(L') H L L'.
d 0 p 1, u[pL + (1 --
p)L'] = pu(L) + (1 -- p)u(L')
Remarque 1 Une fonction d'utilité
représentant une relation de préférence ¾
ainsi définie n'est pas unique.
2.1.3 Définition du modèle
Définition 2 Un jeu de
marchandage à deux joueurs est un couple (A, d) tel que :
A est une partie convexe et compacte de
]]82, appelée l'ensemble des
alternatives
d est un élément de A, appelé point de
désaccord
il existe x E A tel que x » d On note J l'ensemble de
ces jeux.
Dans la suite, on écrira simplement jeu pour
désigner un jeu de marchandage à deux joueurs. On note
Définition 3 Une règle
de marchandage est une application qui à tout jeu (A, d) E J associe
un unique point de A.
2.1.4 Les propriétés de Nash
Dans cette partie, on se donne une règle de
marchandage. On tentera également d'expliquer la
légitimité du choix de tels axiomes dans la construction d'une
solution.
1. L'efficacité
Définition 4 (b est dite
efficace lorsque pour tout jeu (A, d) E J , il n'existe aucun x E A
tel que x > (b(A, d).
L'efficacité de la solution semble être un
pré-requis indispensable à sa construction. L'objectif est en
effet d'améliorer la situation des deux joueurs, l'existence d'une
solution meilleure n'a donc pas lieu d'être.
2. La symétrie
Définition 5 (b est dite
symétrique lorsque pour tout jeu (A, d) E J tel que
si (x1, x2) E A alors (x2, x1) E A
d1 = d2
7
on a 01(A,d) = 02(A,d)
La symétrie sous-entend que l'arbitre ne donne de
préférence à aucun des deux joueurs lorsque le jeu est
symétrique.
3. L'invariance par transformation affine
Définition 6 0 est dite
invariante par transformation affine lorsque pour tout jeu (A, d) E J
, et pour tous a, b E R2 avec a » (0,
0),
0(aA + b, ad + b) = a0(A, d) + b
L'invariance par transformation affine signifie que l'en
modifiant de la même manière l'ensemble des alternatives et le
point de désaccord, la solution obtenue sera identique à la
solution initiale modifiée similairement.
4. L'indépendance des alternatives non pertinentes
Définition 7 0 est dite
indépendante des alternatives non pertinentes lorsque pour tout
jeu (A, d) E J et A' c R2,
(A c A' et 0(A', d) E A)
0(A', d) = 0(A, d)
Cette notion peut être illustré par le fait qu'en
retirant une alternative non pertinente à A', la
solution restera la même.
2.2 Existence et unicité de la solution de
Nash
Lemme 1 Soit (A, d) un jeu. La
fonction
f : x E R2 1--0'
x1x2.
admet un unique maximiseur sur Ad := {x -- d | x E
A, x . d}. Preuve 1 Ad est :
non vide car (A, d) est un jeu,
fermé car intersection des fermés A -- d et
{y E R2 | y . (0, 0)},
borné car inclus dans le borné A --
d.
f étant continue, elle admet donc un maximum sur
A--d. Montrons à présent que ce maximum est unique.
On suppose que f admet deux maximiseurs distincts x et y sur
Ad.x`y
2 E Ad, car Ad convexe
par intersection de d'ensembles convexes. Or on a :
f(x+y) (x1 +
y1l (x2 + y2) (1)
11\\ 2 J 2
J 2 J 1
= 4(x1x2 +
y1y2 + x1y2 + x2y2)
(2)
1
= 4(2x1x2 +
2y1y2 + (x1 -- y1)(y2 --
x2)) > f(x) (3)
Ceci contredit le fait que x est maximiseur de f sur Ad.
Justifions l'inégalité (3). D'une part, par
hypothèse, f(y) = f(x), d'où
1 1
4(2x1x2 +
2y1y2) = 4(2f(x) +
2f(y)) = f(x).
D'autre part, comme (A, d) est un jeu, il existe z E A tel
que z » d. Alors (z1 -- d1)(z2 -- d2) > 0, et donc f(x), f(y)
> f(z -- d) > 0. En particulier, x1, x2, y1, y2 > 0
et y2 = x1
y1 x2. De plus, si
y1 = x1, alors y2 = x2 et donc y = x : comme x et y sont
distincts, on doit avoir y1 0 x1. On en conclut que :
(x1 -- y1)(y2 -- x2) = (x1 -- y1)(x1
x2 -- x2)
y1
8
x2(x1 -- y1)2 y1
> 0
Théorème 2.2 Il existe
unique règle de marchandage à la fois efficace,
symétrique, invariante par transformation affine et indépendante
des alternatives non pertinentes. Elle est donnée par :
(A, d) E J argmax (x1 -- d1)(x2 -- d2)
xEA, x,,d
Preuve 2 Soit ? une règle
respectant les quatre propriétés et (A, d) un jeu. On pose m
:= argmaxxEA, x,,d(x1 -- d1)(x2 -- d2). On
va montrer que ?(A, d) = m.
Étape 1
On rappelle que m » (0, 0).
L'invariance de ? par transformation affine assure que :
?(A, d) = ?(A -- d, (0, 0))
= m?( 1 (A -- d), (0, 0))
m
Posons Amd :=
1m(A -- d). Il suffit donc de montrer que
?(Amd , (0, 0)) = (1,
1).
Étape 2 Montrons
que
sup x1x2 1. xEAd ,
x,,(0,0)
Soit x E Amd tel que x .
(0, 0). Alors il existe y E A -- d tel que x =
1my. Mais alors, y . (0,0) et il existe
z E A tel que z -- d = y. On a alors z . d et donc, d'après le lemme 1,
(z1 -- d1)(z2 -- d2) m1m2. D'où x1x2 =
m11 (z1 -- d1) m21 (z2 -- d2)
1.
Étape 3
Montrons que
dx E Amd , x1 + x2 2.
Supposons qu'il existe x E Amd tel
que x1+x2 > 2. Amd étant convexe, il
contient l'ensemble des points du segment entre (1,1) et x.
Considérons la fonction
Q : p E [0;1] f(p(1,1) +
(1 -- p)x)
où, pour rappel, f est la fonction qui à
tout élément de 1182 associe le produit de ses
composantes. On calcule :
dp E [0;1], Q(p) = (p + (1 -- p)x1)(p +
(1 -- p)x2)
= p2 + (x1 + x2)p(1 -- p) + x1x2(1
-- p)2
= (1 -- 2(x1 + x2) + x1x2)p2 +
2((x1 + x2) -- 2x1x2)p + x1x2
9
On remarque que Q est un trinôme, donc
dérivable, et que Q'(0) = 2((x1 + x2) --
2x1x2). On distingue alors deux cas :
soit x . (0, 0), auquel cas x1x2 = f(x)
1 d'après le résultat de l'étape 2 ;
soit l'une des composantes de x est strictement
négative, auquel cas l'autre doit être supérieure à
2, car x1 + x2 > 2 et alors x1x2 < 0.
Dans tous les cas, Q'(0) > 0. Q'
étant continue, il existe e > 0 tel que Q' est strictement
positive et donc strictement croissante sur [0; e]. On suppose aussi e
assez petit pour que y := f(1,1)+(1--e)x
» (0, 0). Mais alors f(y) = Q(e) > Q(0) =
1, ce qui contredit l'étape 3.
Étape 4
Amd est compact, car image du
compact A par la fonction continue x E 1I82
1m(x -- d). En particulier,
Amd est borné, et par équivalence des
normes sur 1R2,
3c > 0, dx E Amd , |x1| +
|x2| c.
On en déduit que pour tout x E Amd
, par inégalité triangulaire,
|x1 -- x2| |x1| + |x2| c
|x1 + x2| |x1| + |x2| c, et en particulier x1 + x2 .
--c.
En ajoutant le résultat de l'étape 3, on
peut dire que Amd est contenu dans R := {x E
JR2 | x1 + x2 2, |x1 -- x2| c, x1 + x2 .
--c}.
Étape 5
On vérifie que (R,(0,0)) est un jeu :
on vérifie aisément que R est convexe,
fermé et borné,
on a bien (0,0) E R,
enfin, (1,1) E R et
(1,1) » (0, 0).
Or pour tout (x1, x2) E R, on a (x2, x1) E R. Par
symétrie de ?, il existe á E 1I8 tel que ?(R,
(0,0)) = (á, á). Si á < 1,
alors (á, á) « (1,1), ce qui est exclu par
efficacité de ?. Si á > 1, alors á + á
> 2, ce qui est aussi exclu car (á, á) E R. On a donc
á = 1. On conclut grâce à l'indépendance de
? des alternatives non pertinentes : comme Amd c R et
?(R, (0,0)) = (1,1) E Amd
, alors
?(Amd , (0,0)) = ?(R,
(0, 0)) = (1, 1).
2.3 Exemple d'application réelle de cette
théorie
Pour conclure cette partie théorique voici un exemple
de jeu de marchandage faisant intervenir les concepts développés
jusqu'à maintenant et qui puisse s'appliquer à une situation
réelle, tout en mettant en évidence certaines limites.
Prenons le cadre de l'Union Européenne. Supposons que
la commission européenne ait pour mission de répartir des vaccins
aux États membres dans le cadre de la crise du COVID-19. Elle se doit
d'avoir un jugement impartial entre les pays, elle joue donc le rôle du
juge. Les pays sont les joueurs qui veulent maximiser les vaccins reçus,
et donc maximiser leur utilité. Cette utilité liée aux
vaccins est d'autant plus grande que l'état du système de
santé du pays en question est sous-développé et que le
nombre de cas positifs au COVID-19 y résidant est grand. Si les pays ne
se mettent pas d'accord, personne n'aura de vaccin car ceux-ci ont entre temps
été achetés aux laboratoires par d'autres pays hors Union
Européenne. La solution de Nash appliquée à ce
problème permettrait d'avoir une répartition des vaccins juste et
la plus efficace possible.
10
Cette utilisation de la solution de Nash est imaginable, il
faut néanmoins en énoncer certaines limites. Il se peut en effet
que dans la réalité elle soit politiquement inapplicable. Par
exemple si la France et l'Allemagne ne reçoivent que très peu de
vaccins en raison de leurs bons systèmes de santé, ils seront
davantage à même de bloquer cette décision car ils font
partie des pays ayant le plus d'influence au sein de l'Union Européenne.
Malgré tout, la solution de Nash pourrait servir d'indicateur sur la
voie à suivre. Par ailleurs, on peut aussi imaginer que des pays
choisissent de mentir à la commission sur l'état de leur
système de santé ainsi que le nombre de cas de COVID dans leur
pays. Ce mensonge influerait sur la solution de Nash et augmenterait le nombre
de doses reçues par le pays. On peut imaginer encore une fois que pour
dissuader cette éventualité, la commission enverrait des
inspecteurs européens dans les différents pays pour
vérifier l'utilité annoncée et en cas de duperie la pays
se verrait infliger une amende.
Cette exemple met en lumière la grande
applicabilité de cette théorie, bien qu'à première
vue elle paraisse plutôt théorique.
2.4 Conclusion sur la partie théorique de la
solution de Nash
Cette partie a été l'occasion de
présenter la démarche axiomatique entreprise par J.F Nash pour
trouver une solution au problème de marchandage ainsi qu'à
démontrer l'existence de la solution qu'induit ce choix des axiomes. On
remarque que le choix des axiomes relève avant tout d'un choix
arbitraire destiné à faire émerger une solution, il n'est
pas exclu que certains de ces axiomes fassent l'objet de remises en question.
De plus, le dernier exemple évoqué donne un premier aperçu
des difficultés que peut rencontrer l'application de cette
théorie à des cas pratiques. L'enjeu de notre mémoire
consiste désormais à numériser une telle solution pour
pouvoir l'appliquer à des cas concrets, en valider certains aspects et
en montrer ses limites.
11
3 Développement numérique du jeu de
marchandage
Remarque : Toute cette partie numérique fait
référence au fichier "Nash_solver" Il est aussi possible de se
référer aux sections 8.2.1 et 8.2.2 mises en annexe.
3.1 De la théorie au numérique
Nous avons montré comment il était possible de
trouver la solution de Nash pour un jeu (A,d). Afin de pouvoir
implémenter et développer l'exemple décrit en
introduction, il est nécessaire de construire l'algorithme permettant la
résolution d'un jeu de marchandage. On a vu que tout jeu était
décrit à l'aide du couple (A,d), où A est un ensemble
convexe et d est le point de désutilité. Dans un jeu à
deux joueurs, l'ensemble A est l'enveloppe convexe des couples
d'utilités des joueurs. L'ensemble A sera donc du type list
(voire même list de list où cette
dernière comporte les utilités de chacun des joueurs). Le point
de désutilité d sera quant à lui du type
array qui permet des manipulations plus faciles, notamment quant il s'agit
de translater les points d'un ensemble selon le vecteur d afin de
centrer l'ensemble A en [0,0].
Nous allons dans un premier temps présenter les
étapes clés qui ont permis la construction de l'algorithme de
résolution du jeu de Nash. Nous illustrerons ces parties grâce aux
données suivantes, tirées au hasard :
L = [[444, 968], [261,
220], [646, 985], [815, 878],
[929, 122],
[638,
|
136],
|
[536,
|
550],
|
[435,
|
992],
|
[346, 161],
|
[372,
|
283],
|
[608,
|
674],
|
[569,
|
491],
|
[255,
|
962],
|
[670,198],
|
[958,
|
304]]
|
d = [1,28]
Voici premier plot de nos points, le point de
désaccord est mis en évidence en rouge.
FIGURE 1 - Ensemble des points choisis pour l'illustration
3.2 Exhibition de la frontière de
Pareto
En premier lieu, la solution de Nash se trouve
nécessairement sur la frontière de Pareto qui constitue
l'ensemble des meilleures alternatives possibles pour les joueurs. Il convient
donc de
12
FIGURE 2 - Premier tri de la liste (de droite à gauche
et bas en haut)
trier la liste des couples d'utilité pour garder
uniquement ceux constituant cette frontière.
1. Première étape: trier la
liste
Il est tout d'abord nécessaire de faire un premier tri
afin de pouvoir facilement manipuler la liste de points. La figure
montre bien le choix de tri qui a été fait. On remarque que tous
les points désignés par une flèche orientée vers le
bas ne seront pas retenus car strictement Pareto-dominés par
ceux qui l'entourent (ce ne sont pas les seuls, nous le verrons par la suite)
Voici les fonctions utiles à ce premier tri :
1
2 def first_component(a): # renvoie l'abscisse d'un point de
R2
3 return a[0]
4 def second_component(a): # renvoie
l'ordonnee d'un point de R2
5 return a[1]
6
7 def double_sort(L):
8 S = sorted(L, key = second_component, reverse = True)
9 S.sort(key = first_component, reverse = True) # la
méthode "sort" ãÑ conserve
l'ordre lorsque la cle est la meme
10 return S
11 # prend en entree une liste de points de R2
renvoie
12 # la liste triee par ordre decroissant par rapport a la
premiere
ãÑ composante
13 # les points de premiere composante egale sont tries par
rapport a la
ãÑ seconde
Voici l'état de la liste qui en résulte :
L = [[958, 304], [929, 122], [815, 878], [670, 198], [646, 985],
[638, 136], [608, 674], [569,
491], [536, 550], [444, 968], [435, 992], [372, 283], [346, 161],
[261, 220], [255, 962]]
2. Seconde étape : Frontière de
Pareto
Après avoir trié intelligemment la liste, il
nous faut exclure les points Pareto-dominés de notre liste. Dans un
premier temps, la fonction first_selection élimine les points
désignés
13
par les flèches orientées vers le bas, qui sont
comme évoqué précédemment, Pareto-dominés
par leurs voisins. Cela ne suffit pas, car parmi les points restants, certains
peuvent se situer en-dessous de la droite reliant ses deux voisins, auquel cas,
il est dominé par toutes combinaisons linéaires de ces derniers.
Les fonctions above et second_selection permettent de
terminer d'exhiber de la frontière de Pareto.
14 def first_selection(L):
15 S = [L[0]] # L etant triee par
"double_sort", L[0] sera forcement
le ãÑ premier element de la
sous-liste
16 n = len(L)
17 i = 1
18 j = 0
19 while i < n:
20 if L[i][0] < S[j][0] and L[i][1] >
S[j][1]:
21 S.append(L[i])
22 j+=1
23 i+=1
24 return S
25 # prend en entree une liste triee par la
fonction "double_sort"
26 # renvoie une sous-liste strictement
décroissante pour la premiere
27 # composante et strictement croissante
pour la seconde
28
29 def above(a,b,c):
30 return b[1] >
(a[1]*(b[0]-c[0])/(a[0]-c[0])) + ãÑ
(c[1]*(a[0]-b[0])/(a[0]-c[0]))
31 # prend en entree trois points
strictement decroissants/croissants
32 # pour la premiere/seconde composante
renvoie "True" ssi le point du ãÑ
milieu
33 # est strictement au-dessus de la droite
passant par les deux autres
34
35 def second_selection(L):
36 if len(L) == 1: return L
37 S = [L[0],L[1]]
38 n = len(L)
39 i = 2
40 j = 0
41 while i < n:
42 if above(S[j],S[j+1],L[i]):
43 S.append(L[i])
44 j+=1
45 i+=1
46 else:
47 S.pop()
48 if j == 0:
49 S.append(L[i])
50 i+=1
51 else:
52 j-=1
53 return(S)
14
54 # prend en entree une liste strictement
decroissante/croissante pour la
ãÑ premiere/
55 # seconde composante renvoie la
sous-liste privee des points ãÑ
Pareto-domines
56 # par une combinaison d'autres
points
Notre exemple de liste n'étant pas assez exhaustif, il ne
met pas en avant la différence apportée par la fonction
second_selection, voici donc deux print tirés d'une
liste plus
exhaustive, et qui illustre bien le passage de la première
à la seconde sélection.
On exhibe par ailleurs la frontière de Pareto de notre
liste initiale sur la figure. Voici la liste finale :
L = [[958,304],
[815,878], [646,985],
[435,992]]
3.3 Solution du jeu de Nash
Après avoir réussi à réduire la
liste en incluant uniquement les points appartenant à la
frontière de Pareto, il nous est désormais possible de trouver la
solution du problème selon Nash. On rappelle pour cela que la solution
de Nash maximise la fonction produit de la frontière de
Pareto. Autrement dit, il faut trouver la combinaison linéaire de
deux points appartenant à la frontière (ou un point appartenant
directement à la frontière s'il s'agit du maximiseur) qui
maximise l'aire du rectangle dont une des diagonales rejoint le point de
désaccord et le maximiseur en question. Pour cela, les fonctions
x_max et y_max sont utilisées afin de trouver
l'abscisse et l'ordonnée respectives du point qui maximise la fonction
produit sur une droite passant par deux points. Le maximum ne se situe pas
nécessairement entre les deux points.
57 def y_max(a,b): # a est sous la forme
[x1,y1]
58 a_1, a_2, b_1, b_2 = a[0], a[1] ,b[0]
,b[1]
59 p_cut = b_1/(b_1-a_1)
60 return (p_cut*a_2 + (1-p_cut)*b_2)/2
61
62 def x_max(a,b):
63 a_1, a_2 ,b_1 ,b_2 = a[0], a[1] ,b[0]
,b[1]
64 p_cut = b_2/(b_2-a_2)
65 return (p_cut*a_1 + (1-p_cut)*b_1)/2
Il est à présent possible de trouver la solution de
Nash par dichotomie. Brièvement, nous comparons deux points de
l'enveloppe :
1. Soit le maximum de la fonction produit se trouve entre les
deux points, dans ce cas le point représente la solution de Nash
2. Soit le maximum de la fonction produit se trouve à
gauche du segment reliant les deux points, deux possibilités s'ouvrent
à nous:
(a) Il reste plus de deux points étudiables sur la
frontière de Pareto se trouvant à gauche des points actuels, dans
ce cas on continue de procéder par dichotomie sur l'ensemble des points
à gauche
(b) Autrement, le point de gauche constitue la solution de
Nash
3. Le raisonnement est similaire pour le cas où le
maximum de la fonction produit se trouve à droite du segment reliant les
deux points
FIGURE 3 - Ensemble L après first_selection
FIGURE 4 - Ensemble L après second_selection
FIGURE 5 - Frontière de Pareto de notre liste initiale
15
16
Voici les fonctions qui nous permettent de trouver la solution
finale :
(à noter que la fonction solution_rec renvoie un
array avec: la solution, les deux points issus de la combinaison amenant au
résultat ainsi que les coefficients de la combinaison ([1,0] si le point
appartient à l'enveloppe))
66 def y_max(a,b): # a est sous la forme [x1,y1]
67 a_1, a_2, b_1, b_2 = a[0], a[1] ,b[0] ,b[1]
68 p_cut = b_1/(b_1-a_1)
69 return (p_cut*a_2 + (1-p_cut)*b_2)/2
70 # prend en entree deux points strictement
decroissants/croissants pour la
ãÑ premiere
71 # /seconde composante renvoie l'ordonnee
du maximiseur de la "fonction produit"
72 # la droite passant par ces deux points
73
74 def x_max(a,b):
75 a_1, a_2 ,b_1 ,b_2 = a[0], a[1] ,b[0] ,b[1]
76 p_cut = b_2/(b_2-a_2)
77 return (p_cut*a_1 + (1-p_cut)*b_1)/2
78
79 # prend en entrée une liste traitee par
"frontier_points"
80 # renvoie le point de l'enveloppe convexe
de la liste qui maximise la "fonction
ãÑ produit"
81 def solution_rec(L):
82 n = len(L)
83 if n == 0:
84 print("Echec de la recurrence")
85 if n == 1:
86 return np.array([[L[0][0],L[0][1]],[0,0],[0,0],[1,0]])
87 else:
88 m = n//2
89 a, b = L[m-1], L[m]
90 y = y_max(a,b)
91 if y < a[1]:
92 if n > 2:
93 return solution_rec(L[:m])
94 else:
95 s = np.array([a[0],a[1]])
96 a = np.array([a[0],a[1]])
97 b = np.array([b[0],b[1]])
98 c = np.array([1,0])
99 return np.array([s,a,b,c])
100 if y > b[1]:
101 if n > 2:
102 return solution_rec(L[m:])
103 else:
104 s = np.array([b[0],b[1]])
105 a = np.array([a[0],a[1]])
106 b = np.array([b[0],b[1]])
107 c = np.array([0,1])
108 return np.array([s,a,b,c])
109 else:
110 x = x_max(a,b)
111 p = (x - b[0]) / (a[0]-b[0])
112 s = np.array([x,y])
113 a = np.array([a[0],a[1]])
114 b = np.array([b[0],b[1]])
115 c = np.array([p,1-p])
116 return np.array([s,a,b,c])
117
Important : Dans ce dernier paragraphe, la
solution de Nash était avant tout le maximum de la fonction
produit de la frontière de Pareto dans un ensemble centré
en [0,0], c'est à dire que le point de désaccord est
nécessairement [0,0]. Pour trouver la solution de Nash d'un
problème quelconque, il est nécessaire d'introduire une fonction
shift qui permet de centrer l'ensemble, d'en exhiber le maximum de la
fonction produit, et de l'incrémenter à nouveau de la valeur du
point de désaccord. Voici les fonctions en question :
118 def shift(L,v):
119 L_shifted = []
120 for i in range(len(L)):
121
P = np.array([ L[i][0] + v[0], L[i][1] + v[1] ])
17
122 L_shifted.append(P)
123 return L_shifted
124
125 def true_solution(A,d):
126 L = shift(A+[d], (-1)*d)
127 F = frontier_points(L)
128 s = solution_rec(F)
129 s_list =[]
130 for i in range (3):
131 s_list.append(shift(to_list(s[i]),d)) #
la fonction shift prends en ãÑ
argument des listes, d'où
l'utilisation de la fonction "to_list"
132 # le point solution, le point a et le
point b sont incrémentés du point d
L=[]
133
134 for i in range (len(s_list)): # on remet
les valeurs de la solution
ãÑ incrémentées
par le point d
135 p = [s_list[i][0][0], s_list[i][0][1]]
136 L.append(p)
137 L.append([s[3][0],s[3][1]])
138 return L
Nous avons désormais les outils nécessaires
permettant de trouver la solution de Nash à notre exemple de
départ : la solution est le point de la liste initiale
: [815, 878]
Voici un autre résultat d'un exemple quelconque
où la solution est une combinaison de deux points : La solution
est une combinaison linéaire du point [955.0, 779.0] chargé du
poids 0.29 et du point [819.0, 913.0] chargé du poids 0.71
La solution est le point [859.1, 873.49]
18
On peut maintenant écrire une fonction qui permet
d'afficher un plot de notre solution, voici le résultat de notre exemple
:
FIGURE 6 - Plot final de la solution de Nash
19
4 Étude numérique : voiture partagée
"uberisée" 4.1 Rappel introductif
Dans un premier temps, remettons en contexte l'exemple
décrit en introduction. Le jeu s'articule autour de deux joueurs se
trouvant chacun à un endroit et souhaitant se rendre à un endroit
différent. Une voiture reçoit les requêtes des joueurs,
à peu près simultanément par soucis de simplification et
neuf possibilités s'offrent à elle, parmi lesquelles notamment
:
-- la voiture vient chercher J1 puis J2, dépose J1 puis
J2
-- la voiture va chercher J1, le dépose, elle va ensuite
chercher J2 pour le déposer
-- la voiture va chercher J1 et J2 doit se rendre à pied
à destination
-- chacun des joueurs se rend à pied à sa
destination.
Cet exemple ne correspond pas exactement à ce à
quoi on pourrait s'attendre intuitivement d'un jeu de marchandage. Le
schéma de pensée s'orienterait davantage autour d'une discussion
entre deux joueurs au sujet du partage de biens disponibles, le partage serait
tranché par un arbitre désintéressé en suivant les
4 axiomes décrits pas J.F Nash. Le partage d'un héritage entre
plusieurs membres d'une famille se prête bien à cette description.
Ces exemples ont été évoqués dans la partie 1.2
Remettons donc en place les différents
paramètres constituant un jeu de marchandage qui se prêtent ici
à notre modèle.
L'utilité des joueurs est sûrement le point le
plus contestable. En effet, dans un jeu de marchandage classique, deux options
sont imaginables : les acteurs ont soit, chacun quelque chose à partager
(exemple: un agriculteur partage avec le supermarché local une partie de
sa récolte contre de l'argent), soit un ensemble de biens qui leur ait
collectivement légué et qu'ils se répartissent entre eux
(l'exemple déjà cité précédemment d'un
héritage).
Ici, les biens partageables ne sont pas matériels mais
plutôt immatériels voire idéologiques. En effet, la
première ressource que les acteurs se partagent est le temps. Aller
chercher un joueur puis prendre le suivant dans la foulée est, dans la
plupart du temps, une perte de temps pour le premier. On peut alors imaginer
que l'utilité d'un joueur soit maximale à condition qu'il soit le
seul client du chauffeur. Dans un cas pareil, le jeu de marchandage n'a pas de
raison d'être car un joueur ne rentre dans un jeu de marchandage que s'il
y trouve un intérêt. Il est donc nécessaire de
conceptualiser cet intérêt par un facteur
supplémentaire qui incite le joueur à participer au jeu. Le
facteur imaginé ici, est idéologique, il se matérialise
sous la forme d'un marqueur de bonne volonté pour lequel les
joueurs consentiraient à contribuer au principe de partage de
l'utilisation d'une même voiture. Les raisons seraient par exemple, soit
écologiques ou soit de l'ordre d'une solidarité exprimée
vis-à-vis d'une petite entreprise ne possédant pas encore
beaucoup de véhicules. Ce postulat ne constitue pas un frein majeur
à la transposition de notre exemple dans la réalité
étant donné que des principes de covoiturages et autres
façons diverses de partager des voitures sont déjà
implantés dans notre société.
On s'autorise à modéliser l'utilité des
joueurs en fonction uniquement du temps qu'ils mettent à se rendre
à l'endroit désiré. Le facteur de bonne volonté est
implicitement suggéré dans l'existence même du jeu par le
fait que chacun des joueurs accepte de concéder un peu de leur temps
pour en faire gagner à l'autre. Des fonctions d'utilité concaves
en la variable de temporalité permettent le bon fonctionnement de
l'exemple. En effet, les joueurs souhaitent malgré tout minimiser leurs
temps de trajet, ainsi la composition d'une fonction concave avec le temps de
trajet permet d'obtenir un ensemble convexe.
20
A présent loti de notre ensemble convexe, il convient
de fixer le point de désaccord indispensable au jeu de marchandage. Il
parait naturel que l'une des alternatives suggérant le fait que les deux
joueurs soient obligés de se rendre à pied à leur
destination constitue le point de désaccord évident de notre jeu.
On complète la théorie en attribuant à la voiture (ou
indifféremment au chauffeur) le rôle d'arbitre
désintéressé du jeu dont le rôle est de prendre la
meilleure décision en connaissance des utilités des joueurs, de
leurs positions et leur endroit d'arrivée.
4.2 Notations
Les notations en dimension 1 sont les suivantes
:
-- x1 = la position de départ du
joueur 1
-- x2 = la position de départ du
joueur 2
-- y1 = l'endroit d'arrivée du
joueur 1
-- y2 = l'endroit d'arrivée du
joueur 2
-- v = la position de départ de la voiture.
Nous allons étudier un cas simplifié de notre
exemple en nous concentrant sur le segment [0,1]. L'utilité
attribuée à chaque joueur est une fonction concave qui va
dépendre du temps. On choisit arbitrairement la fonction
uipt1, t2q «
't2 i . On distingue
également le temps parcouru en voiture tv et le
temps parcouru à pied tm :
tipx, yq « tm,ipx, yq `
tv,ipx, yq où
4.3 Choix de la dimension 1
|
"tv,ipx, yq «
d1px, yq « |x ' y|
tm,ipx,yq « Ktv,ipx,yq
|
Ce choix simplifie légèrement le calcul des
distances mais a pour défaut de recourir souvent aux mêmes
alternatives. Il faut par exemple que deux points x1
et x2 soient complètement
opposés pour que la voiture choisissent d'en prendre un et de le
déposer avant de prendre le second.
Exemple : dans cette configuration, mise à part
un changement majeur, la solution sera quasi-
systématiquement : La voiture ira chercher J2 puis J1,
déposera J1 puis J2
Un choix de dimension 2 sur une grille aurait sûrement
permis à d'autres alternatives de ressortir
plus régulièrement.
4.4 Perspectives d'études
Ce jeu nous offre plusieurs possibilités. Dans un
premier temps, il nous faut coder les solutions du jeu en fonction des
paramètres initiaux. Nous allons laisser apparaître les
résultats de la console ainsi que les graphiques qui permettent
d'illustrer le fonctionnement de certaines fonctions. Le code dans son
intégralité est laissé disponible en annexe.
Rendre possible le calcul numérique de ces solutions
nous permet également d'en tester les limites. En effet, nous avons
laissé entendre en introduction qu'un joueur (ou les deux) pouvait
choisir de mentir sur la position d'arrivée qu'il indiquait à la
voiture, cela induit inévitablement le calcul d'une solution
différente lui permettant dans certains cas d'obtenir davantage
d'utilité, au détriment parfois de l'utilité de l'autre
joueur. Le recours à des concepts de théorie des jeux vont nous
permettre d'étudier les effets ainsi que la récurrence de cet
aspect du modèle.
Il est également intéressant de se mettre
à la place de la compagnie. En effet, sa problématique consiste
à traiter au mieux la gestion de ses voitures afin d'en utiliser le
moins possible, en prenant
21
en charge plusieurs utilisateurs à la fois. Cette
dernière envisage de considérer la solution de Nash pour
résoudre cette problématique.
L'étude des comportements tel que le mensonge peut lui
permettre de juger la pertinence de l'application d'un jeu de marchandage
à son business (qui consiste dans la mesure de ses capacités
à satisfaire ses clients).
On a vu également que la solution théorique
n'aboutissait pas systématiquement sur un point appartenant à
l'ensemble des alternatives. Cela implique le recours au hasard lorsque la
solution est issue de la combinaison de deux possibilités. On peut
imaginer que la compagnie souhaiterait savoir si avec une probabilité
raisonnable elle peut espérer obtenir des solutions pures.
4.5 Application de l'algorithme à un cas simple
Remarque: Cette partie numérique fait
référence aux fichiers "Etude_probleme_voiture_partagee" et
"Applications_theorie_des_jeux" Il est aussi possible de se
référer aux sections 8.2.3 et 8.2.4 mises en annexe..
Dans un premier temps, nous allons étudier un cas
fixé nous permettant d'imager les résultats renvoyés par
notre code. Pour cela, imaginons la situation suivante pour laquelle les deux
joueurs se situent dans des quartiers différents délimités
par les sous-segments [0,0.2] et [0.3,0.35] et souhaitent tous deux se rendre
sur leur lieu de travail se situant dans une zone industrielle située
dans [0.7,1.0]. Les joueurs sont positionnés arbitrairement en
x1 = 0.02 et x2 = 0.34. Ils souhaitent se
rendre en y1 = 0.84 et en y2 = 0.71. La
voiture est placée en v = 0.5. Rappelons
également que la fonction d'utilité est la même pour les
deux joueurs à savoir: ui(t1, t2) =
10--t2 i et que le temps de marche est défini comme
tm,i(x, y) = Ktv,i(x,
y) où on choisira K = 5. La marche est donc un facteur
pénalisant dans le calcul de l'utilité du joueur même si
elle n'intervient pas encore car les deux joueurs annonce ici l'endroit
où ils souhaitent véritablement se rendre en voiture.
Voici le message affiché par la console ainsi que
le plot de la résolution :
139
140 Solution du jeu classique
141
142 La voiture est placée en 0.5 sur
[0,1]
143
144 Le joueur 1 est placée en 0.02 sur
[0,1] et souhaite se rendre en 0.84
à
145
146 Le joueur 2 est placée en 0.34 sur
[0,1] et souhaite se rendre en 0.71
147
148 Le point de désaccord correspondant
au fait que les deux joueurs se rendent
ãÑ pied
149 est [-6.81 6.578]
150 Avec une réalisation classique du
jeu, l'action suivante sera choisie :
151 La voiture ira chercher J2, le
déposera, puis ira chercher J1 et le déposera
152
153 J1 en retire une utilité de 5.838
154
155 J2 en retire une utilité de 9.719
156
22
FIGURE 7 - Plot de notre solution simple
On remarque qu'une autre configuration peut également
nous donner une solution mixte. On imagine que dans un tel cas, l'entreprise
serait obligée de tirer une des deux solutions au hasard. D'un point de
vue pratique, ce n'est pas une configuration souhaitable pour l'entreprise qui
préfère obtenir une solution simple parmi les alternatives
proposées.
157 Solution du jeu classique
158
159 La voiture est placée en 0.2 sur
[0,1]
160
161 Le joueur 1 est placée en 0.05 sur
[0,1] et souhaite se rendre en 0.89
162
163 Le joueur 2 est placée en 0.6 sur
[0,1] et souhaite se rendre en 0.91
164
165 Le point de désaccord correspondant
au fait que les deux joueurs se rendent à
ãÑ pied est [-7.64 7.6 ]
166 Avec une réalisation classique du
jeu, l'action suivante sera choisie :
167 0.6 fois du temps, on aura l'action : La
voiture ira chercher .31 puis .32, ãÑ
déposera .31 puis .32
168
169 0.4 fois du temps, on aura l'action : La
voiture ira chercher .32, le déposera, ãÑ
puis ira chercher .31 et le déposera
170
171 .31 en retire une utilité de 7.1
172
173 .32 en retire une utilité de 9.19
23
4.6 La problématique du mensonge
4.6.1 Jeu à information parfaite
Continuons l'analyse en donnant la possibilité au
joueur de mentir sur sa position d'arrivée. S'il décide de
mentir, le joueur est déposé à l'endroit qu'il a
annoncé et doit donc parcourir la distance restante à pied. Le
joueur cherche donc d'abord à connaître le point d'arrivée
le plus favorable qui lui permette de maximiser son utilité.
Pour implémenter la recherche de ce y et limiter le
nombre et le temps de calcul, nous avons opté pour une méthode de
dichotomie à trois variables permettant de trouver une bonne
approximation de l'utilité maximum en fonction du point d'arrivée
du joueur sur le segment. On choisit d'ajouter une variable à la
méthode de dichotomie à deux variables car cette dernière
n'est pas adaptée en tant que tel pour trouver un extrema. La
méthode consiste ici à évaluer l'utilité (recherche
sollicitant beaucoup de calculs) en 3 points :
a < p < m < q < b
Ainsi, chercher le maximum a sur l'intervalle [a,b] se
réduit aux 3 possibilités suivantes :
u(p) > u(m) alors a E]a, m[
u(m) < u(q) alors a E]m, b[
u(p) . u(m) et u(m) . u(q) alors a E]p,
q[
Le schéma suivant illustre deux des trois
possibilités évoquées, l'intervalle [a,b] est
divisé par deux à chaque itération. (La fonction de
dichotomie codée pour ce problème apparaît dans
l'appendice)
(a) u(p) > u(m) et donc a Psa, mr
(b) u(m) < u(q) et donc a Psm,
br
FIGURE 8 - Illustration de la méthode de dichotomie
à 3 variables
Maintenant que le choix de la méthode a
été expliqué, nous pouvons présenter les
résultats correspondant à notre exemple initial.
Dans un jeu à information parfaite, les joueurs savent
si l'autre ment ou non. Dans ce cas il est possible pour le joueur jouant en
second de déterminer la destination annoncée par le premier
joueur quand il décide de mentir et donc de trouver le meilleur endroit
pour mentir en conséquence. On construit deux modèles, un premier
dans lequel le joueur 1 joue en premier, et un second où c'est le joueur
2 qui prend la main. Les différents résultats sur les
utilités des joueurs permettent de construire un arbre
décisionnel permettant de trouver la solution de Nash grâce
à un raisonnement par induction à rebours. Les résultats
de la console sont présentés ci-contre, on joint également
en appendice, les graphiques illustrant la recherche des y optimaux,
ces derniers laissent apparaître les points qui ont été
calculés durant la compilation.
24
174 Valeurs du jeu à
175
176 Quand les deux joueurs disent la
vérité :
177 Utilité de .31 : 5.838
178 Utilité de .32 : 9.719
179
180 Quand .31 ment et que .32 dit la
vérité :
181 Utilité de .31 : 6.464
182 Utilité de .32 : 9.181
183 .31 annonce vouloir aller en 0.546 au
lieu de 0.84
184 La différence d'utilité de
.31 équivaut à : 0.626
185 La différence d'utilité de
.32 équivaut à : -0.538
186
187 Quand .32 ment et que .31 dit la
vérité :
188 Utilité de .31 : 6.024
189 Utilité de .32 : 9.73
190 .32 annonce vouloir aller en 0.687 au
lieu de 0.71
191 La différence d'utilité de
.31 équivaut à : 0.186
192 La différence d'utilité de
.32 équivaut à : 0.011
193
194 Quand les deux joueurs mentent de
manière ingénue (ils se contentent de faire
ãÑ leur meilleur mensonge quand l'autre dit la
vérité') :
195 Utilité de .31 : 7.539
196 Utilité de .32 : 9.501
197 .31 annonce vouloir aller en 0.546 au lieu
de 0.84
198 .32 annonce vouloir aller en 0.687 au lieu
de 0.71
199 La différence d'utilité de .31
équivaut à : 1.701
200 La différence d'utilité de
.32 équivaut à : -0.218
201
202 Quand le joueur 2 a décidé de
mentir alors qu'il savait que le joueur 1 mentait
ãÑ :
203 Utilité de .31 : 7.238
204 Utilité de .32 : 9.718
205 .31 annonce vouloir aller en 0.766 au lieu
de 0.84
206 .32 annonce vouloir aller en 0.687 au lieu
de 0.71
207 La différence d'utilité de .31
équivaut à : 1.4
208 La différence d'utilité de
.32 équivaut à : -0.001
209
210 Quand le joueur 1 a décidé de
mentir alors qu'il savait que le joueur 2 mentait
ãÑ :
211 Utilité de .31 : 6.177
212 Utilité de .32 : 9.743
213 .31 annonce vouloir aller en 0.546 au lieu
de 0.84
214 .32 annonce vouloir aller en 0.668 au lieu
de 0.71
215 La différence d'utilité de
.31 équivaut à : 0.339
216 La différence d'utilité de
.32 équivaut à : 0.024
Ces résultats permettent donc de construire
l'arbre décisionnel suivant, cet arbre est une des
manières de trouver la solution de Nash au jeu. La fonction
print_jeu_decouvert (jointe en appendice) permet également cela
quand on lui fournit des couples d'utilité. On remarque que
dans les deux cas quand ils ont connaissances de toutes les
informations, et surtout du choix de l'autre, les joueurs décident de
mentir. Ce résultat semble logique étant donné que mentir
est, par construction, plus avantageux que de dire la vérité.
L'enjeu est d'étudier si cette décision reste rationnelle quand
on prive le joueur de certaines informations. Ça sera l'objet d'une
partie ultérieure.
25
(a) Arbre décisionnel quand J1 joue en premier (b) Arbre
décisionnel quand J2 joue en premier
FIGURE 9 - Arbres décisionnel et résolution
à rebours
4.6.2 Nombre d'occurrence de chaque solution en
information parfaite
Afin de compléter l'analyse du jeu à
information parfaite, on peut s'intéresser au taux d'apparition des
solutions. En effet, quatre solutions sont possibles, deux où un seul
joueur ment, une où les deux mentent ainsi qu'une dernière
où les deux ne mentent pas. On peut vraisemblablement supposer que la
seconde n'apparaîtra presque jamais étant donné la
manière dont a été construit le problème.
Effectivement, compte tenu de la pénalité relative
accordée au fait de marcher (le facteur K=5 fixé plus haut), un
joueur qui sait que le premier n'a pas menti devrait pouvoir trouver une
solution qui l'avantage. Dans le cas contraire, aucun des deux joueurs ne ment,
mais cette éventualité devrait survenir de façon
marginale.
L'algorithme destiné à compter le nombre de ces
occurrences est décomposé en deux fonctions majeures (mises en
appendice), la première fonction nash_joueur_i_premier_joueur
permet de calculer une solution par induction à rebours, la fonction est
d'ailleurs déjà utilisée dans la fonction
print_jeu_decouvert qu'on a utilisé précédemment, la
seconde fonction occur-rence_type_solution_jeu_decouvert retourne
quant à elle une liste de valeurs s P {0, 1,
2, 3} correspondant aux 4 possibilités. Sur deux
échantillons de 200 valeurs toutes comprises entre 0 et 3 (un
échantillon correspondant à un des joueurs jouant en premier) on
obtient les résultats suivant :
217 Quand le joueur 1 joue en premier
218 Nombre de fois oil les deux individus
mentent : 179
26
219
Nombre de fois oil le premier ment et que le second ne ment
pas
|
:
|
15
|
220
|
Nombre de fois oil le premier ne ment pas et que le second
ment
|
:
|
4
|
221
|
Nombre de fois oil les deux disent la vérité :
2
|
|
|
222
|
Quand le joueur 2 joue en premier
|
|
|
223
|
Nombre de fois oil les deux individus mentent : 130
|
|
|
224
|
Nombre de fois oil le premier ment et que le second ne ment
pas
|
:
|
44
|
225
|
Nombre de fois oil le premier ne ment pas et que le second
ment
|
:
|
7
|
226
|
Nombre de fois oil les deux disent la vérité :
19
|
|
|
|
On constate dans ce modèle que presque 9 fois sur 10
les joueurs trouvent un intérêt à mentir. Cet exemple
reflète une première limite à la solution de Nash. Cette
dernière est en effet très sensible à l'utilité que
les individus indiquent à l'arbitre, c'est d'ailleurs un problème
déjà soulevé lorsque l'exemple 2.3 sur l'union
européenne avait été proposé. Un joueur peut donc
influer sur le calcul de son utilité (ici en jouant sur le temps de
parcours), pour en changer le résultat et améliorer ses gains.
4.6.3 Jeu à information imparfaite
Le jeu à information parfaite présente
l'avantage d'être simple à calculer, mais il reflète mal la
réalité, en effet, il n'existe pas à priori de raisons
pour un joueur de connaître la position de départ de l'autre ainsi
que sa destination et encore moins son choix de mentir ou de dire la
vérité. C'est la raison qui nous pousse à introduire et
utiliser la notion de jeux à information imparfaite. La notion de "jeux"
fait ici écho aux choix des joueurs de mentir ou de dire la
vérité, le fait d'ignorer la position de l'autre joueur ainsi que
sa destination relève quant à lui en partie de la notion de
"croyance", on appuiera un peu plus précisément ce
phénomène dans l'exemple suivant.
Considérons ici un jeu reprenant certains
éléments du précédent. Le joueur 1 est au courant
que le joueur 2 habite sur [0.3,0.35] (0.34 en réalité), le
joueur 2, lui, sait que le joueur 1 se trouve sur [0,0.2] (0.02 en
réalité). Tout deux souhaitent se rendre sur le segment [0.7,1]
(0.84 pour le joueur 1 et 0.71 pour le joueur 2) et sont au courant de ce fait,
tout en ignorant précisément la destination précise.
La difficulté est de choisir les deux points sur
lesquels les joueurs hésitent à mentir sachant qu'ils ignorent
beaucoup d'informations. Il n'y a pas de meilleures façons de faire, on
a opté pour un calcul empirique des yi. Nous proposons de
décrire une des itération qui sera répétée
plusieurs fois : pour trouver l'endroit où le joueur 1 ment, on prend
les valeurs de x1 « 0.02 et
y1 « 0.84 qu'il connaît puis on
tire aléatoirement x2 et y2
sur leur intervalle respectif (selon une loi uniforme) et finalement
on calcule les deux y1 optimaux dans le jeu à
information parfaite, c'est à dire ceux choisis par le joueur quand il
sait que l'autre dit la vérité et également quand il ment.
On obtient deux y correspondant à chacune des deux
situations.
Ce processus est itéré n fois et produit deux
échantillons de yi. Le y choisi pour le joueur 1 est celui
obtenu en faisant la moyenne sur les 2n valeurs de y
générées. On procède de manière
similaire pour trouver le y du joueur 2.
En résumé, on a donc calculé la moyenne
des destinations choisies par un joueur quand il sait que l'autre dit la
vérité ainsi que lorsqu'il sait que l'autre ment. On pourrait
continuer longtemps en s'intéressant à la destination choisie
quand le joueur sait que l'autre sait qu'il ment et qu'il va mentir en
conséquence etc... le processus est à la fois infini et devient
de plus en plus complexe au fur et à mesure que l'on rajoute des
stratégies. Sur un échantillon de 300 tirages, on obtient les
valeurs suivantes (remarque : un jeu de données a également
été fourni pour trouver les mêmes
y)
27
-- y1 quand J1 ment simplement vaut en moyenne: 0.787
-- y1 quand J1 ment en sachant que J2 ment vaut en
moyenne: 0.678
-- y2 quand J2 ment simplement vaut en moyenne: 0.685
-- y2 quand J2 ment en sachant que J2 ment vaut en
moyenne: 0.659 En prenant la moyenne respective des y1 et y2,
on en vient à prendre :
-- y1 « 0.732
-- y2 « 0.679
On rappelle qu'initialement le joueur 1 souhaite se rendre en
0.84 et le joueur 2 en 0.71. On remarque que le joueur 1 doit concéder
plus de distance de marche s'il veut influencer le jeu à sa faveur.
C'est un résultat logique intuitivement étant donné qu'il
se trouve plus loin de la voiture et souhaite se rendre plus loin que le joueur
2. En appliquant notre algorithme aux valeurs trouvées, nous trouvons
les nos 4 couples d'utilités répertoriés dans le jeu mis
sous forme normale :
Les résultats quant aux utilités obtenues sont
les suivants :
6.27
9.72
Vérité
J1
J2
Mensonge
Vérité
5.84
9.72
9.76
9.69
9.76
6.14
Mensonge
On observe l'existence d'une solution de Nash unique pour
laquelle les deux joueurs préfèrent encore une fois mentir en
permanence.
Un autre test a été fait en diminuant encore
davantage l'utilité due au fait de marcher. En effet nous avons fait
passer le facteur K de 5 à 10, et pour autant les résultats ne
diffèrent que marginalement comme en atteste le tableau suivant.
5.94
9.72
Vérité
J1
J2
Mensonge
Vérité
5.84
9.72
9.6
9.73
9.73
5.94
Mensonge
Ce résultat unanime s'explique en grande partie par les
paramètres établis initialement. En effet, on s'aperçoit
que lorsque le joueur 2 ment, il augmente considérablement
l'utilité du joueur 1. Quand il ment, il rapproche son point de
destination, et ce phénomène "arrange" le joueur 1 car il
participe à changer les paramètres initiaux qui n'étaient
pas à la base favorable au premier joueur.
Le fait que le jeu précédent soit à
information imparfaite n'apporte pas de changement radical vis à vis du
fait qu'on ait enlevé de l'information aux joueurs. C'est pourquoi nous
allons changer le jeu en ajoutant des facteurs de désinformation aux
joueurs. Considérons donc la situation suivante :
-- Une première zone d'habitation se trouve en [0,0.1]
-- Une seconde zone d'habitation se trouve en [0.9,1]
-- Une zone industrielle se trouve en [0.5,0.6]
28
A présent les joueurs 1 et 2 n'ont respectivement pas
connaissance de X2 et X1,
ils savent néanmoins que l'autre joueur se situe nécessairement
dans l'une des deux zones d'habitation. On considère le jeu suivant :
chacun des joueurs se situe dans l'une des deux zones d'habitation avec une
probabilité p pour la zone [0,0.1] et 1-p pour la zone
[0.9,1], distribués selon une loi uniforme sur chacun de ces
intervalles. En introduisant ces facteurs p et 1-p, on introduit le concept de
croyance mentionné plus haut. Ainsi, les deux joueurs
souhaitent se rendre dans la zone industrielle mais ignorent où se
trouve le second joueur. On s'intéresse au comportement des deux
joueurs.
Afin d'obtenir des valeurs numériques, nous
procédons de la manière suivante : un joueur ne trouve un
intérêt à mentir que si l'autre joueur se trouve dans
l'autre zone d'habitation, ainsi son choix de y se fait en considérant
que l'autre joueur est soit en 0.05 soit en 0.95 (correspondant aux moyennes
des deux segments d'habitation) selon que lui-même soit dans la zone 2 ou
la zone 1 (choix possible grâce à notre fonction permettant de
trouver un y optimal par dichotomie). Nous sommes ainsi capable de calculer les
différentes destinations optimales des deux joueurs en fonction de la
zone où ils se trouvent.
Afin de rester dans un cadre généraliste, on
prend X1 et X2 égaux
aux moyennes des segments sur lesquels ils se trouvent. Grâce aux valeurs
numériques on obtient donc l'arbre suivant :
FIGURE 10 - Arbre décisionnel quand J1 et J2 ignorent
où se trouve le second joueurs
La stratégie d'équilibre est facilement
identifiable dans cet arbre. On observe en effet que pour chacun des noeuds
terminaux du joueur 2, le mensonge domine la stratégie de dire la
vérité
29
(strictement à un noeud près tout à
gauche). Il ne reste plus qu'à considérer les noeuds terminaux
où le joueur 2 ment pour s'apercevoir que le joueur 1 a toujours
intérêt à mentir. La stratégie d'équilibre
consiste donc à mentir peu importe les croyances p et q de chacun des
deux joueurs. Cet équilibre est en fait un équilibre
bayésien parfait.
4.7 Étude statistique de la nature de la
solution de Nash dans notre modèle
Remarque: Cette partie numérique fait
référence aux fichiers "Etude_probleme_voiture_partagee" et
"Applications_statistiques", un jeu de donnée à également
été fourni pour trouver les mêmes p-valeurs. Il est aussi
possible de se référer à la section 8.2.5 mise en
annexe.
Introduisons le nouveau cadre d'étude suivant : le
patron de l'entreprise de VTC souhaite prendre connaissance de la part des cas
où la solution de Nash induirait le recours à un tirage au sort
entre deux possibilités. En effet, en ayant recours à la solution
de Nash d'un modèle de marchandage, son objectif ne consiste pas
à recourir au tirage au sort entre deux alternatives existantes, mais
bel et bien à sélectionner une alternative existante. C'est
pourquoi nous allons faire une étude statistique pour étudier la
redondance de l'utilisation du tirage au sort dans le modèle. Si cette
dernière devait prendre une part trop importante dans les
résultats, l'entreprise serait sûrement contrainte de changer de
méthode. Nous différencierons une solution comme étant
mixte ou pure si elle a recours ou non au tirage au sort.
Notre entreprise a décidé qu'elle ne souhaitait
pas que le modèle lui fournisse une solution mixte plus de 10% du temps.
Nous allons par l'utilisation du test de Student juger si l'utilisation du jeu
de marchandage satisfait les contraintes de l'entreprise.
Pour notre test, nous utilisons un échantillon Xi
P t0, 1un ({Xi « 1u :« {la
ième solution est pure}) de n variables
aléatoires indépendantes générées par le
calcul de la solution de Nash à partir des variables x1,
x2, y1, y2, v tirées selon la loi
Upr0, 1sq.
Nous avons choisi d'utiliser le test paramétrique de
Student qui a l'avantage d'être plus puissant qu'un test non
paramétrique tel que le test de la moyenne (dont les résultats
n'étaient pas satisfaisant) afin de nous permettre d'estimer la
fréquence d'obtention d'une solution pure. Nous allons donc effectuer
notre test sur les hypothèses suivantes :
f
H0 : u à 90% H1 : u ï 90%
Étant donné que nous cherchons un estimateur de la moyenne, il
convient de prendre l'estima-
teur empirique ÏXn «
1 øn i«0 Xi qui d'après la loi forte des
grands nombres est un estimateur n
consistant de u. Au seuil á, la
région de rejet du test est donc la suivante :
Rá «
ÏXn ã
ká(
Tandis que l'erreur de première espèce est
définie par :
á :« sup Pup
ÏXn ã
káq( « sup Pup
ÏXn ã
káq(
H0 u90%
N'ayant pas de loi évident sur Xn et
afin de trouver le ká adéquat nous allons
nous ramener à une statistique de Student et en évaluer le
quantile. Rappelons la chose suivante:
Studentpn ' 1q
ç0
T « a
X{pn ' 1q
Expression pour laquelle :
ç0 Np0,1q et X
÷2n-1
Premièrement, d'après le théorème
central limite :
ç0 :« ?n à
|
ÏXn ' u
|
Np0,1q
|
|
|
|
Ensuite, pour le calcul de la loi Khi-2 nous aurons besoin de
l'estimateur ó, noté ó2,
encore une fois choisi par estimation empirique de part sa consistance :
pó2 « 1
n ' 1
|
ÿn i=1
|
pXi '
ÏXnq2
|
|
Nous pouvons ainsi calculer notre X :
X « pn ' 1qpó2
ó2
Par simplification, nous pouvons réécrire notre
statistique de test de la façon suivante :
?np
T «
ÏXn ' uq
b 1
ó
(n-1)pó2
Studentpn ' 1q
?np ÏXn '
uq
1
«
óp
.
Étant donné que nous avons transformé
notre statistique de test, il convient de redéfinir notre erreur de
première espèce :
á :« sup Pup
ÏXnã káq(
(4)
%0
á « sup "upT
ã
?npká'uqq*(5)
óp
óp
á « Pu=90%pT ã
?npká ' 0.9q
q (6)
30
En effet le passage de (5) à (6) se justifie par le
fait que la probabilité est d'autant plus grande que le terme
%/n(kQ -u) est élevé
et donc que u est petit, c'est pourquoi le sup est atteint en u
« 0.9.
Étant donné que nous connaissons la loi de T,
il est possible de trouver le quantile associé, on a donc :
qá (n-1) «
?npká ' 0.9q
óp
óp
?n
Et donc :
ká « 0.9 `
qT (n-1)
á
Et notre zone de rejet s'écrit donc :
Rá « { ã 0.9 +
qâ (T-1)
l ?n
Grâce à ça, on est désormais capable
de trouver la p-valeur de notre test :
31
p-valeur « â :« inf }á P
r0; 1s | Xn ã 0.9 ` qa
pn'1q ::n } (7)
l
« inf }á P r0;1s |l
pÏXn ' 0.9q ã
qa pn'1q } (8)
« inf }á P r0;1s | FT
pn'1qp~n pÏXn '
0.9qq ã FTpn'1qpq«
pn'1qq } (9)
" ?n *
« inf á P r0;1s | FTpn'1qp
óp p ÏXn ' 0.9qq
ã á (10)
?n
áà « FTpn'1qp
óp
|
p Xn ' 0.9qq (11)
|
|
Le passage de (8) à (9) se justifie par la stricte
croissance de la fonction de répartition de la loi de Student.
Pour notre échantillon de taille 1000, nous obtenons une
p-valeur de 0.999
Cette très grande p-valeur nous conforte dans le fait
de ne pas rejeter 1-10 et de conclure que l'entreprise peut raisonnablement
entreprendre d'utiliser la solution de Nash pour répondre à sa
problématique compte tenu de son seuil d'exigence. Malgré tout,
elle devra accepter de recourir à l'aléatoire un nombre non
négligeable de fois, ce qui est constitue assurément une limite
à l'utilisation de la solution de Nash.
Encore une fois, étant donnée la formulation de
notre hypothèse nulle, la p-valeur élevée nous prête
à penser que nous ne devons pas rejeter 1-10. Par conséquent,
étant données les exigences de l'entreprise, la solution de Nash
semble y répondre efficacement.
Les p-valeurs de notre test précédent sont
critiquables car elles dépendent très largement de
l'échantillon qui a été généré
aléatoirement. Ainsi, elles sont susceptibles de beaucoup fluctuer en
fonction de l'échantillon généré. Il nous est
même possible d'influencer le résultat en faveur de ce qu'on
souhaite montrer en faisant simplement varier la taille de cet
échantillon car la p-valeur est croissante et tend vers 1 quand la
taille de l'échantillon grandit. De plus, l'écart qu'on peut
constater entre les différents calculs de p-valeurs s'explique par la
grande sensibilité du test. Ainsi un écart léger
écart en dessous du seuil fixé se traduit immédiatement
par une très faible p-valeur. Or la moyenne des échantillons
générés tend à se distribuer selon une loi
gaussienne autour de 90%, il n'est donc pas rare que certaines moyennes soit
inférieures à ce seuil. En couplant le résultat
donné par la p-valeur (qu'on a par ailleurs calculé 1000 fois et
dont on a affiché un histogramme pour se rendre compte de sa
distribution) et la moyenne de l'échantillon, on peut affirmer que 9
fois sur 10 en moyenne, la solution donnée à l'entreprise est une
solution pure.
32
FIGURE 11 - Histogramme de 1000 p-valeur issues du test de
Student
FIGURE 12 - Histogramme de 1000 moyennes résultant de
solutions différentes
4.8 Conclusion de la partie numérique sur la solution de
Nash
L'application de la solution de Nash décrite en
première partie à notre étude numérique au sujet de
la voiture partagée est riche d'enseignements. On a d'abord pu constater
que la solution était assez facilement implémentable grâce
à des fonctions judicieusement choisies. L'algorithme a par ailleurs
l'avantage d'être stable dans son utilisation. Un autre avantage de la
solution de Nash est le fait qu'elle se transpose aisément à
notre étude à condition de poser les bonnes hypothèses,
concernant notamment son applicabilité dans la réalité.
Enfin, l'avantage majeur de cette solution est présent avant tout dans
son existence ainsi que dans son unicité, il aurait été
compliqué d'envisager un modèle vraisemblable et applicable si la
solution fournie n'était pas unique.
Malgré ces avantages, cet exemple a mis en
lumière deux limites à la solution de Nash. Le premier concerne
la construction de l'ensemble des possibilités sur lequel la solution de
Nash doit trancher. Cette dernière joue un rôle essentiel qui
détermine entièrement la solution et rend la solution sensible
à tout modification. On a vu que l'utilisateur de la voiture
partagée pouvait trouver un intérêt à modifier des
paramètres qui le concernait pour tourner la solution à son
avantage. La seconde concerne la possibilité d'obtenir une solution
mixte. Cette possibilité est indispensable pour être certain
d'obtenir une solution, elle reste néanmoins difficilement exploitable
quand on essaie de transposer le modèle à la
réalité et contraint ses utilisateurs à recourir à
l'aléa.
Cette partie nous a donc éclairé sur certaines
problématiques qu'on pouvait rencontrer avec
33
l'utilisation pratique de la solution de Nash. Par ailleurs,
on peut se demander si la construction même de cette solution n'est pas
susceptible d'être remise en question. La démarche axiomatique
permet certes de trouver l'existence d'une solution, mais le choix des axiomes
relève avant tout d'une décision arbitraire de celui qui les
incorpore au modèle. N'existe-t-il pas d'autres axiomes permettant de
trouver également une solution unique, différente de celle
trouvée jusqu'à présent? Cette question est l'objet de la
partie suivante.
34
5 La solution de Nash : une solution faisant
débat
5.1 Remise en cause de la solution de Nash via
l'axiome d'indépendance aux alternatives non pertinentes
Nous avons vu précédemment que la solution de
Nash au problème de marchandage à 2 joueurs est applicable dans
nombre de domaines. En effet nous avons pu l'employer dans des situations tel
le partage de voiture, un problème qui semble pertinent dans un monde
où l'écologie prend de plus en plus d'importance. Cette solution,
unique de par les conditions qui lui sont appliquées, se heurte à
des problèmes de cohésion lorsque nous l'utilisons dans certaines
situations. Nous nous proposons dans cette partie d'explorer ces situations, de
réfléchir à pourquoi la solution de Nash est non
pertinente dans ces cas et de finalement proposer une solution alternative qui
serait mieux adaptée.
Pour mieux pouvoir illustrer nos propos, nous allons dans un
premier temps rappeler les caractéristiques de la solution de Nash dans
un jeu de marchandage à 2 joueurs.
A chaque jeu de marchandage opposant deux joueurs, on associe
la paire (A, d). A est un sous-espace du plan. d = (d1, d2) sera le
point de désaccord où di est le niveau d'utilité
du joueur i si les deux n'arrivent pas à coopérer.
(A,d) doit au préalable vérifier 4 conditions :
Il existe au moins un point x de A tel que xi > di
pour i = 1,2. Le marchandage doit donc être profitable aux 2
joueurs.
A est convexe : Si deux solutions de A permettent de
construire la solution alors on peut ajouter des probabilités pour le
choix entre ces deux événements pour parvenir à la
solution.
A est compact.
d , x Vx E A. Si ce n'est pas le cas on peut
ignorer tout point de A ne satisfaisant pas cette condition.
On va appeler J l'ensemble des couples (A,d)
remplissant les conditions ci-dessus.
On peut à présent énoncer les axiomes
qui permettent d'obtenir une fonction 0(A, d) qui renvoie l'unique
solution de Nash au problème :
Pareto optimalité : V (A, d) E J, y E A tq y . 0(A,
d) et y 0(A, d)
Symétrie : V T : 1182
1182 définie par T (x1, x2) = (x2, x1), V (A, d) E
J, 0(T(A),T(d)) = T(0(A, d))
Invariance par transformation affine : V(A, d) E J
, et pour tous a, b E 1182 avec a »
(0, 0), 0(aA + b, ad + b) = a0(A, d) + b
Nous arrivons maintenant à l'axiome en question dont on
va étudier la pertinence :
Indépendance des alternatives non pertinentes : V
(A, d) E J , VA' c 1182, A c A'
et 0(A', d) E A 0(A', d) = 0(A, d)
C'est ce 4ième axiome qui
définit la solution de Nash ainsi que son unicité.
35
Cet axiome signifie que si la solution de Nash n'est pas
modifiée lorsque l'on retire une alternative de l'ensemble des
alternatives possible , cela signifie que l'accord trouvé entre les 2
joueurs restera le même que l'on prenne l'ensemble avec ou sans cette
alternative. Celle-ci est considérée comme non pertinente.
Supposons par exemple que chaque année Lucas et
Bastien doivent faire un choix sur le jour de départ de leurs vacances.
Ayant le choix entre lundi, mardi et mercredi, ils ne choisissent jamais
mercredi. Ils choisissent donc un mélange entre des départs le
lundi et le mardi. Alors, d'après ce 4ième axiome de Nash,
l'accord passé pour la date de départ sera le même qu'ils
aient le choix entre les 3 jours ou juste lundi et mardi.
Bien que cet axiome puisse paraître dans un premier
temps raisonnable, une multitude de cas démontrent facilement sa limite.
Avant de pouvoir présenter un exemple qui exhibe une solution dont la
pertinence puisse être remise en question, nous allons devoir introduire
de nouvelles notations.
Soit (A, d) E J et soit M(A)
= (M1(A), M2(A)) tel que :
M1(A) = sup{x E R :
3y E R, (x,y) E A} M2(A)
= sup{y E R : 3x E
R,(x,y) E A}
On définit la fonction gA(x)
définie pour x M1(A) par :
" y si (x, y) est le point Pareto-optimal de
(A, d) gA(x) = M2(A)
sinon
Ici gA(x) est le maximum que le joueur 2 peut
obtenir si le joueur 1 obtient au moins x. Grâce à la
première condition vérifiée par (A,d), nous avons bien
Mi(A) > di pour i=1,2. . Ainsi par
compacité de A, M1(A) et M2(A) sont
finis et atteints par des points de A.
Avec ces nouvelles notations observons ensemble un exemple
concret.
Prenons 2 étudiants passant 2 épreuves. Ils
représenterons nos 2 joueurs pour le jeu de marchandage suivant. L'un ne
connaît que la première matière et l'autre que la seconde.
A moins de s'entraider ils ne valideront pas et donc le point de
désaccord sera d=(0,0).
Prenons 2 ensembles des alternatives différents
A1 et A2 avec A1 = {(20, 0),
(0, 20), (15, 15)} et A2 = {(20,
0), (0, 20), (20, 14)} tel que
(A1, d) et (A2, d) appartiennent bien
à J . On peut supposer ici que l'utilité des joueurs
correspond à leur moyenne à ces examens avec 20 étant la
note maximale. Par exemple si l'on prend le point 21 x (20,
0) + 21 x (0, 20) cela représente le fait que
chaque joueur va aider l'autre de tel sorte à ce qu'ils ont tous les
deux 10 de moyenne. Le fait de faire réviser l'autre entraîne une
désutilité aux étudiants car cela leur prend du temps
qu'ils auraient pu utiliser eux-mêmes pour réviser.
Si x est l'utilité du Joueur 1 et y
celle du Joueur 2, on peut remarquer que :
" V x E [0 20] 3 y tel que (x, y) E
A2
,,Si 3 y' E 1R tel que
(x,y') E A1 alors y >
y'
Donc gA1(x) est ici
inférieure à gA2(x). En d'autres
termes le maximum que le joueur 2 peut obtenir si le joueur 1 obtient au moins
x est supérieur avec l'ensemble d'alternatives A2
plutôt qu'avec A1.
Nous pouvons donc logiquement émettre l'idée
que l'étudiant 2 va demander un arrangement plus avantageux avec
l'ensemble A2 par rapport à l'ensemble A1 car celui-ci
peut y obtenir une
36
meilleure note sans que celle du joueur 1 ne change.
Si pour tout niveau d'utilité que pourrait demander le
joueur 1, le maximum possible pour le joueur 2 peut en même temps
être supérieur, alors le niveau d'utilité assigné au
joueur 2 devrait logiquement se voir grandir.
Nous allons maintenant, grâce à notre algorithme,
calculer les 2 solutions de Nash de ce jeu avec les ensembles d'alternatives
A1 et A2.
Voici ce que nous obtenons :
FIGURE 13 - Solution de Nash avec A1 et
A2
Comme nous pouvons l'observer sur le graphique ci-dessus, la
solution de Nash en prenant A1 est (15,15) tandis qu'avec A2
la solution est (20,14). En utilisant la solution de Nash et donc l'axiome
d'indépendance des alternatives non pertinentes, l'étudiant 2
obtient une utilité inférieure avec A2 comparé
à A1, ce qui contredit ce que nous avons dit
précédemment. En effet ces solutions ne remplissent pas l'attente
du Joueur 2 qui voulait pouvoir avoir une meilleure utilité avec A2
comparé à A1. Cet exemple met en lumière le
fait que la solution au jeu de marchandage à 2 joueurs trouvé par
Nash peut ne pas avoir de sens dans certains problèmes.
Nous pouvons maintenant nous poser la question : existe-il
une solution unique au problème de marchandage qui donnerait un
aboutissement du marchandage rationnel même dans les cas comme l'exemple
ci-dessus?
37
5.2 Axiome de monotonicité de
Kalai-Smorodinsky
25 ans après que Nash ait proposé ses axiomes
pour trouver une unique solution au problème de marchandage, les
économistes Ehud Kalai et Meir Smorodinsky ont proposé un
4ième axiome alternatif : l'axiome de
monotonicité.
-- Axiome de monotonicité : Si (A1, d)
et (A2, d) E J tel que M1(A1) =
M1(A2) et
gA1 gA2 alors
02(A1, d) 02(A2, d) avec 0(A,
d) = (01(A, d), 02(A, d))
Cet axiome explique que si l'utilité maximum
atteignable du Joueur 2 ( 02(A1, d) étant
l'utilité du joueur 2 avec l'ensemble des alternatives A1 et le
point de désutilité d ) est améliorée
alors le niveau d'utilité du joueur 2 de la solution doit aussi
être amélioré, et cela que pour toute utilité que le
joueur 1 puisse demander. A travers l'axiome de monotonicité, Kalai et
Smoro-dinsky affirment que la solution au problème de marchandage doit
dépendre de tout l'ensemble des alternatives, c'est-à-dire
qu'aucune alternative ne doit être considéré comme
insignifiante et doit donc être prise en compte pour l'obtention de la
solution.
Retournons à Lucas et Bastien qui marchandent sur les
dates de leur départ en vacances chaque année. Reprenons les
mêmes jours qu'avant mais cette fois-ci supposons que Bastien
préfère largement partir mercredi plutôt que mardi et
préfère légèrement partir mardi plutôt que
lundi (mercredi » mardi > lundi). Lucas, lui,
prèfère largement lundi à mardi lui-même
préféré largement à mercredi (lundi
»mardi » mercredi). Supposons qu'ils ont conclu un
certain marché qui consiste à ne partir que des lundis et des
mardis. Si l'on retire mercredi des choix possibles, l'accord peut tout
à fait changer car mercredi pouvait servir d'outil de négotiation
à Bastien : "J'accepte de ne jamais partir mercredi, le jour qui
m'arrange le plus, mais alors je veux partir plus souvent mardi en
conséquence.". Cette logique contredit Nash et son axiome
d'indépendance des alternatives non pertinentes. En effet, pour Nash, la
répartition entre les lundis et les mardis reste la même, que
Bastien ait accès à son jour préféré ou
non.
Je pense que la solution de Kalai est plus réaliste
dans la société d'aujourd'hui. En effet, une stratégie
connue en marketing est d'ajouter des alternatives pour pouvoir rendre les
alternatives recherchées plus acceptables au client. Si on me propose
une maison à un certain prix, je vais penser que le prix est correct si
l'agence me propose pour le même prix une maison beaucoup plus petite.
C'est pour cela que les économistes Kalai et
Smorodinsky remplace le 4ième axiome de
Nash par l'axiome de monotonicité ci-dessus. Désormais, un joueur
ayant de meilleures options devrait obtenir un meilleur accord. Ce nouvel
axiome, en remplaçant l'axiome d'indépendance des alternatives
non pertinentes, permet en gardant les 3 autres axiomes ainsi que les
conditions sur (A,d) de trouver une nouvelle solution unique au jeu de
marchandage à 2 joueurs.
Théorème 5.1 (Unicité de la
solution monotonique) Il existe une unique solution u qui
satisfait l'axiome de monotonicité.
Soit (A, d) E J et L(M(A), d) la droite joignant d
à M(A). L'élément maximum de A sur cette droite est u(A,
d) avec M(A) = (M1(A), M2(A)).
On obtient donc la relation suivante :
u1 -- d1
=
u2 -- d2
38
M1(A) -- d1
M2(A) -- d2
FIGURE 14 - Solution monotonique (u1,u2)
Preuve 3 Nous allons prouver ici que u
est bien solution unique du problème de marchandage à 2
joueurs.
-- Étape 1
Montrons dans un premier temps que la solution monotonique
est bien définie.
Fixons (A, d) E J un jeu normalisé.
(A, d) est normalisé si (d1, d2)
= (0,0) et (M1(A), M2(A)) =
(1,1). Il n'y a pas perte de généralité
car grâce à l'axiome d'invariance par transformation affine, nous
pouvons facilement retrouver la solution dans le cadre
général.
L(M(A), d) a une pente positive de sorte que l'ordre
partiel sur R2 induit un ordre total sur L(M(A), d). Cela
implique que si L(M(A), d) coupe A, alors il y a un unique
élément maximum de A dans lui-même, et u(A) est bien
défini. L(M(A), d) coupant A vient du fait qu'il existe un point
(M1(A), y) E A tel que y . d2, qu'il existe un point (x,
M2(A)) E A tel que x . d1, que d < M(A) et A est
convexe.
On rappelle qu'une relation binaire . est un ordre
partiel sur l'ensemble A si pour tous
39
éléments x, y et z de A :
x ï y et y ï z ñ
x ï z (transitivité)
x ï x (réflexivité)
x ï y et y ï x ñ
x « y (antisymétrie)
Si, de plus, x ï y ou y ï x,
alors la relation est un ordre total sur A.
Étape 2
Nous allons maintenant montrer que u est une solution au
problème de marchandage à 2 joueurs et qu'elle satisfait l'axiome
de monotonicité.
u est symétrique : en effet pour tout jeu
pA, dq P J , si px, yq P A ñ
py, xq P A et d1 « d2, alors u1pA,
dq « u2pA, dq.
De plus, u satisfait l'axiome d'optimalité de Pareto
car A est convexe et compact.
u est invariante par transformation affine car pour tout
jeu pA, dq P J , pour tous a, b P R2 avec a
" p0, 0q, upaA ` b, ad ` bq
« aupA, dq ` b.
La monotonicité va se prouver
géométriquement.
Soit Lá est une droite de pente a avec
0 ï a ï 2 passant par d. Si
po1paq, o2paqq est le point
d'intersection de Lá avec la frontière de tx
P R2 : Dy P A, x ì 0 et x
ï yu, alors si /3 a, o2p/3q
ì o2paq et si
po12'paq,o22'paqq
est le point correspondant pour pA2,dq, on a que
o1 páq ì op1'
p2' 1 . On rappelle que dans le cadre de
cet axiome gA1 ï gA2.
Étape 3
Prouvons finalement que u est l'unique solution qui
satisfait la condition de monotonicité. Soit pA, 0q un
jeu normalisé et f une solution monotonique.
p1, 0q, upA', 0qu
un
Soit A' « tx P
R2 : Dy P A tel que x ì 0 et x
ï yu. pA', 0q est bien un
jeu normalisé avec A A' tel qu'il n'existe pas de
point y tel que y ì fpA', 0q et y
%o fpA', 0q. Donc fpA, 0q
« fpA', 0q. Les points
p0,1q et p1,0q sont dans A'.
Soit A'' « tp0,1q,
convexe. Alors pA'', 0q est
un jeu normalisé symétrique pour les 2 joueurs avec A''
A'. Nous avons donc fpA'',
0q « upA', 0q.
On remarque aussi que A' ne contient aucun
point y tel que y ì fpA'', 0q et y
%o fpA'', 0q. Donc fpA, 0q
« upA', 0q « upA,
0q.
Revenons à notre exemple des étudiants. Ceux-ci
doivent se mettre d'accord pour de l'entraide concernant 2 examens à
passer. Dans ce problème notre point de désaccord était
d « p0, 0q et on avait à notre disposition deux
ensembles d'alternatives : A1 « tp20, 0q,
p0, 20q, p15, 15qu et A2 «
tp20, 0q, p0, 20q, p20, 14qu. Les
solutions de Nash avec A1 et A2 étaient respectivement
p15, 15q et p20, 14q. D'après Kalai et Smorodinsky, la
solution du Joueur 2 devrait être supérieure avec A2 car
la moyenne maximum atteignable par le joueur 2 peut obtenir si le joueur 1
obtient au moins la moyenne x est supérieure avec A2.
Calculons les solutions monotoniques de ce problème et voyons si cela
résout notre problème concernant la solution de Nash.
Tout d'abord pour A1 nous devons donc résoudre
le problème suivant :
" « M1pA1q ' d1
'
p
1q '
u2
d2 M2
A
d2
max pu1, u2q P ]I82 + |
u1 ' d1
En remplaçant on obtient :
" max px, y, zq P ]I83 120x
` 15z « 20 }
20y ` 15z 20
40
sachant que x + y + z = 1 et que
x, y, z 0
On obtient donc :
max { (x, y, z) E 1183 | x
= y}
sachant que x + y + z = 1 et
que x, y, z 0 De façon similaire pour A2 nous obtenons
:
"max (u1,u2) E 118+ |
2 1
u1 -- d1 M1(A2)
-- d1
=
u2 -- d2 M2(A2) --
d2
En remplaçant on obtient :
"
3 20x + 20z 20
max (x, y, z) E 118 I =
20y + 14z 20
sachant que x + y + z = 1 et que
x, y, z 0
On obtient ainsi :
max { (x, y, z) E 1183 | 20x
+ 6z = 20y}
sachant que x + y + z = 1 et que
x, y, z 0
Pour A1 nous obtenons encore une fois (15,
15) mais pour A2 nous trouvons ici (15.38,
15.38). Nous constatons bien que l'utilité du Joueur 2 est
supérieure pour A2 avec son utilité obtenue via la
solution de Nash pour le même ensemble d'alternatives. Cela résout
en effet la problématique soulevée par Ehud Kalai et Meir
Smorodinsky, le joueur 2 ayant une meilleure utilité dans le cas
où il a plus de choix possibles.
41
FIGURE 15 - Solutions de Nash et Kalai avec A1 et
A2
Dans ce problème en question la solution de Kalai
paraît beaucoup plus logique que la solution de Nash. En effet dans
l'ensemble des alternatives A2, l'étudiant 1 peut se permettre
d'aider l'étudiant 2 à avoir 14 de moyenne tout en gardant 20 de
moyenne. Avec l'ensemble des alternatives A1, il lui est impossible
d'atteindre 20 de moyenne tout en aidant l'étudiant 2 à avoir 14.
Avec A2, l'étudiant peut "gratuitement" avoir 14 de moyenne, le
joueur 1 étant indifférent entre l'aider où non vu qu'il a
20 de toute façon. Cela devrait donc se traduire par un avantage pour le
joueur 2 au moment des négociations, ce que la solution de Nash manque
de prendre en compte.
Après cette partie il est légitime de se
demander laquelle de ces 2 solutions est la plus juste. Cela va dépendre
de notre préférence pour l'un des axiomes interchangeables. Si
nous considérons que l'ajout d'une alternative qui ne sera jamais
choisie ne va pas modifier l'accord trouvé entre les 2 joueurs, alors la
solution de Nash est pertinente via l'axiome d'indépendance des
alternatives non pertinentes. Si au contraire nous acceptons le fait que bien
que cette alternative ne soit pas choisie, elle modifie le pouvoir de
négociation des joueurs, il sera intéressant de choisir la
solution de Kalai avec l'axiome de monotonicité. Dans ce cas là,
si l'utilité maximum d'un joueur augmente, et cela pour toute
utilité que l'autre joueur puisse demander, alors son utilité
augmentera. Nous pouvons faire l'interprétation qu'un juge, dont le
rôle est de trouver l'accord entre les deux joueurs, va être
impartial entre les deux joueurs mais partial sur le choix des axiomes
utilisés et donc sur la solution choisie. Cela pourrait
représenter sa propre notion de ce qui est juste. Ces
préférences peuvent être apparenté au type de
société dans lequel l'échange prend place, celle-ci ayant
des caractéristiques sociales et morales spécifiques.
42
6 Conclusion
Nous avons vu avec ce mémoire que le principe de
marchandage est un cadre créé par J.F Nash pour pouvoir
rigoureusement développer une théorie permettant d'encadrer
l'échange entre 2 agents. Il a essayé de décrire le
comportement de ces agents au travers d'axiomes mathématiques, lesquels
ont été soigneusement choisis pour qu'ils puissent permettre,
ensemble, l'acquisition de certaines propriétés essentielles
concernant l'arrangement trouvé entre les deux individus.
Incorporés au modèle développé par J.F Nash, ces
axiomes rendent l'existence d'un accord systématique et unique, deux
caractéristiques indispensables à l'application concrète
du principe de marchandage.
Ces axiomes procurent à la solution des
propriétés géométriques avantageant sa construction
algorithmique et permettant ainsi une étude approfondie de ses
applications à des exemples concrets. L'étude du concept de
voiture partagée géré par une entreprise était un
exemple, original, de l'application concrète qu'il était possible
de faire avec la solution obtenue par J.F Nash. Néanmoins, elle n'est
pas une solution "miracle" car elle comporte certains défauts à
une application dans la réalité. La possible
malhonnêteté d'un ou des agents en est un premier. En effet, de la
véracité des informations qu'il soumet à l'arbitre (ici
l'entreprise) dépend la solution obtenue. On a vu que lorsque l'agent
choisit de modifier légèrement des paramètres sur lesquels
il a un pouvoir de décision, à savoir sa destination dans notre
cas, le résultat pouvait changer radicalement, au point que mentir
formait souvent une stratégie dominante. Le deuxième
défaut étudié a été le fait que la solution
n'appartenait pas forcément à un élément du cadre
initial mais pouvait être le mixte entre deux d'entre eux. Le cadre
théorique ne se soucie pas de cette éventualité, par
contre elle peut rendre difficile une application concrète du principe
de marchandage. C'est la raison pour laquelle on a étudié le fait
que l'entreprise devait prendre en compte cette éventualité avant
de décider si elle devait ou non appliquer le principe de marchandage
à sa problématique initiale. Il est nécessaire
malgré tout de préciser que le fait de ne pas appliquer cette
solution ne signifie pas que dans le cadre imaginé, il en existe une
meilleure. On a vu par la suite que la solution de Nash pouvait être
confrontée à celle de Kalai, mais parfois (et c'est le cas nous
le pensons ici) il vaut mieux changer le cadre plutôt que d'essayer de
trouver une meilleure solution (positionnement plus stratégique des
voitures par l'entreprise par exemple).
Nous avons pu mettre en lumière la différence
entre la solution de Nash et la solution de Ka-lai pour un jeu de marchandages
à 2 joueurs. Ceci est fort intéressant car nous constatons que
contrairement à d'autres champs comme les mathématiques, les
sciences économiques tel que celle des jeux de marchandages sont
relativement récentes (1950 pour Nash et 1975 pour Kalai). Nous avons
constaté que le choix des axiomes dépendait non pas d'une
vérité universelle mais de la vision de son créateur et de
certaines propriétés à appliquer à leur solution.
En effet, au cours de l'étude de leurs travaux, nous avons
constaté que ces économistes étaient autant
préoccupés par les caractéristiques mathématiques
avantageuses de leur solution, comme l'unicité, que par la vraisemblance
de cette solution à la réalité. Les axiomes choisis
servent à décrire la manière de réfléchir
des agents, mais surtout à créer un modèle
mathématique qui a du sens. Nous avons vu via l'exemple de la
distribution de vaccins dans l'Union Européenne qu'en
réalité il y a beaucoup plus de paramètres à
prendre en compte et que la solution de Nash ou de Kalai sont difficiles
à appliquer. Néanmoins, ces 2 solutions restent pertinentes et
peuvent servir de repères pour prendre une décision. Il serait
intéressant pour des décideurs de prendre en compte plusieurs
solutions différentes comme les solutions de Nash et Kalai pour ensuite
prendre une décision concernant un jeu de marchandage. Bien qu'ils
soient différents, les axiomes mis en place par les différents
économistes ont tous du sens et peuvent mettre en lumière
certains comportements.
43
Avis personnels :
Lucas : Ayant eu la matière Théorie des Jeux
durant ma Licence de Mathématiques puis Théorie des Contrats au
premier semestre de cette année, j'étais d'avis à choisir
un sujet de mémoire dans ce domaine ayant aimé ces
matières. Le sujet Marchandage et partage d'objets a donc
été le choix évident pour moi. Ce mémoire nous a
appris à nous organiser à plusieurs autour d'un projet. Chercher
par soi-même des concepts théoriques sans avoir un cours à
l'Université sur lequel on peut se baser n'est pas chose
évidente, et avoir appris à lire et comprendre des papiers de
chercheurs est, je pense, un outil pertinent à avoir pour la suite de
mes études et surtout pour ma future carrière professionnelle.
Les concepts étant parfois compliqué à saisir, j'ai
compris l'importance des exemples de de la "vulgarisation scientifique" des
notions avancées. En effet ce mémoire ne s'adresse pas
forcément aux personnes déjà compétentes dans ce
domaine d'étude et donc, comme nous au départ, vont avoir besoin
de de contexte pour bien saisir toutes les nuances du modèle
créé par Nash. C'est cela qui, à mon avis, rend le sujet
intéressant.
Bastien : Ce mémoire a été enrichissant
à bien des égards. Il m'a permis de comprendre la démarche
que pouvait entreprendre un scientifique lorsqu'il souhaitait trouver une
solution à un problème posé. J'ai donc
éprouvé un réel intérêt envers ce
procédé axiomatique qui relève parfois d'une logique
personnelle pouvant être remise en question sans pour autant être
fausse. Ce mémoire a aussi été l'occasion pour moi de
beaucoup coder avec certaines problématiques en tête, la
première étant le fait d'essayer de rendre un code le plus
intelligible possible, tâche ô combien ardue. Une deuxième
consistait à découper un gros problème en plusieurs plus
petits et plus facilement réalisables. Enfin, une dernière
problématique concernait l'application d'algorithmes sur des cas
pratiques à des fins théoriques. Face à toutes les
idées d'applications qu'on pouvait imaginer, il a fallu à chaque
fois penser des façons de procéder et choisir celle qui nous
semblait être la meilleure. On a malheureusement dû se
séparer de beaucoup d'idées intéressantes mais
également très chronophages.
7 Bibliographie
Nash, J. (1950). The Bargaining Problem. Consulté sur
https ://
www.semanticscholar.org/paper/The-Bargaining-Problem-Nash/c38e70179b9c33a19824fd157adb8291cfbef1c2
Nash, J. (1953). Two-Person Cooperative Games. Consulté
sur https ://
www.jstor.org/stable/1906951
?seq=1
Kalai, E., & Smorodinsky, M. (1975). Other Solutions to
Nash's Bargaining Problem. Consulté sur https ://
www.semanticscholar.org/paper/OTHER-SOLUTIONS-TO-NASH%27S-BARGAINING-PROBLEM-Kalai-Smorodinsky/ea620f7be68a48d3bcc9b260fecdfd6e54f14270
?p2df
Ozdaglar, A. (2010). Game Theory with Engineering Applications
Lecture 14 : Nash Bargaining Solution. Consulté sur https ://
ocw.mit.edu/courses/electrical-engineering-and-computer-
science/6-254-game-theory-with-engineering-applications-spring-2010/lecture-notes/MIT6_254S10_lec14.pdf
44
8 Appendice
8.1 Codes et résultats consoles annexe de la partie 4
1. Fonction de dichotomie pour la recherche d'extrema 3
Lien pour retourner sur la page contenant la référence
23
227 def joueur_ment_y_maximum_dichotomie
ãÑ
(joueur,a,b,x1,x2,y1,y2,v,decimale,tolerance) :
228 u_et_y = [[],[]]
229 if joueur == 1 : # le while suivant
trouve le max quand J2 ment,
ãÑ on inverse donc si c'est J1
qui ment
230 c = x1
231 x1 = x2
232 x2 = c
233 d = y1
234 y1 = y2
235 y2 = d
236 i = 0
237 while (b-a) > 10**(-tolerance) and (i
< 50):
238 p = a + (b-a)/4
239 m = a + (b-a)/2
240 q = a + 3*(b-a)/4
241
242 u_p =
solution_rapide(x1,x2,y1,p,v,decimale)[0][1] - ãÑ
abs(utilite_marche(p, y2, decimale))
243 u_q =
solution_rapide(x1,x2,y1,q,v,decimale)[0][1] - ãÑ
abs(utilite_marche(q, y2, decimale))
244 u_m =
solution_rapide(x1,x2,y1,m,v,decimale)[0][1] - ãÑ
abs(utilite_marche(m, y2, decimale))
245
246 u_et_y[0].append(u_p),
u_et_y[0].append(u_q), ãÑ
u_et_y[0].append(u_m)
247 u_et_y[1].append(p), u_et_y[1].append(q),
u_et_y[1].append(m)
248
249 if u_p > u_m:
250 b = m
251 elif u_m < u_q:
252 a = m
253 else:
254 a = p
255 b = q
256 i+=1
257 y_sol = (a+b)/2
258 u_sol = solution_rapide
(x1,x2,y1,y_sol,v,decimale)[0][1] -
ãÑ abs(utilite_marche(y_sol, y2,
decimale))
259
260 u_et_y[0].append(u_sol)
261 u_et_y[1].append(y_sol)
262 return [y_sol,u_sol,u_et_y] # u_et_y
sert au plot
45
2. Fonction print_jeu_decouvert
Lien pour retourner sur la page contenant la
référence 24
263 def print_jeu_decouvert
(x1,x2,y1,y2,v,decimale):
264 B=[]
265 B.append(str("\nQuand .31 est le premier
à jouer, .31 décidera de
ãÑ mentir et .32
également"))
266 B.append(str("\nQuand .31 est le premier
à jouer, .31 décidera de ãÑ
mentir mais .32 préférera dire la vérité"))
267 B.append(str("\nQuand .31 est le premier
à jouer, .31 décidera de
dire ãÑ la vérité mais .32
préférera mentir"))
268 B.append(str("\nQuand .31 est le premier
à jouer, .31 décidera de
dire ãÑ la vérité et .32
également"))
269
270 B.append(str("\nQuand .32 est le premier
à jouer, .32 décidera de ãÑ
mentir et .31 également"))
271 B.append(str("\nQuand .32 est le premier
à jouer, .32 décidera de ãÑ
mentir mais .31 préférera dire la vérité"))
272 B.append(str("\nQuand .32 est le premier
à jouer, .32 décidera de
dire ãÑ la vérité mais .31
préférera mentir"))
273 B.append(str("\nQuand .32 est le premier
à jouer, .32 décidera de
dire ãÑ la vérité et .31
également"))
274 print(" \n Solution de Nash du jeu à
découvert
275 liste_1 = creation_4_couples_utilites
ãÑ
(1,x1,x2,y1,y2,v,decimale,tolerance)
276 s_1,i_1 = nash_joueur_i_premier_joueur(1,
liste_1)[:2]
277 print(B[i_1])
278 liste_2 = creation_4_couples_utilites
ãÑ
(1,x1,x2,y1,y2,v,decimale,tolerance)
279 s_2,i_2 = nash_joueur_i_premier_joueur(2,
liste_2)[:2]
280 print(B[i_2+4])
3. Cliquer pour revenir à la page correspondante
281 def nash_info_parfaite
(premier_joueur,S): # prend en argument le
ãÑ return de
creation_4_couples_utilites
282 s_mm,s_vm,s_mv,s_vv = S[0], S[1], S[2],
S[3]
283 if premier_joueur == 1 :
284 joueur = 2
285 s_1 = comparaison(joueur,s_mv,s_vv)
286 s_2 = comparaison(joueur,s_mm,s_vm)
287 s = comparaison(premier_joueur, s_1, s_2)
288 else :
289 joueur = 1
290 s_1 = comparaison(joueur,s_mv,s_vv)
291 s_2 = comparaison(joueur,s_mm,s_vm)
292 s = comparaison(premier_joueur, s_1, s_2)
293 return s
4. Cliquer pour revenir à la page correspondante
46
FIGURE 16 - Graphique : recherche par dichotomie quand aucun
des joueurs ment
FIGURE 17 - Graphique: recherche par dichotomie quand un joueur
sait que l'autre ment
47
294 def occurrence_type_solution_jeu_decouvert
(taille_echantillon = 100, ãÑ decimale = 2,
tolerance = 100, joueur = 1): # joueur ==> premier à
295 occurrence_J1 = []
296 for i in range
(taille_echantillon):
297 x1, x2, y1, y2, v =
random_5_points(decimale) #
random_5_points ãÑ -> 5 points
x1,x2,y1,y2,v en évitant que x1=y1 et x2=y2 car
ãÑ problématique
298 liste = creation_4_couples_utilites
ãÑ
(joueur,x1,x2,y1,y2,v,decimale,tolerance) # -> créer les 4
ãÑ couples
d'utilité
299
ãÑ
occurrence_J1.append(nash_joueur_i_premier_joueur(joueur,liste)[1])
300 return occurrence_J1
48
8.2 Code réalisé tout au long de ce
mémoire
Le code a été écrit sur spyder,
certaines syntaxe sont donc propres à cet IDE. 8.2.1
Fichier "Nash_solver.py"
301 # Le programme suivant vise a calculer
la solution de Nash d'un jeu de ãÑ
marchandage a deux joueurs dont l'ensemble d'alternatives est l'enveloppe
ãÑ convexe d'un nombre fini de
points.
302
303 from numpy import array
304 from matplotlib.pyplot import plot, figure,
title, grid, legend, show
305 from matplotlib.patches import Rectangle
306
307
308 # renvoie l'abscisse d'un point de
R2
309 def first_component(a):
310 return a[0]
311
312 # renvoie l'ordonnee d'un point de
R2
313 def second_component(a):
314 return a[1]
315
316 # prend en entree une liste de points de
R2 renvoie
317 # la liste triee par ordre decroissant
par rapport a la premiere composante
318 # les points de premiere composante
egale sont tries par rapport a la seconde
319 def double_sort(L):
320 S = sorted(L, key = second_component,
reverse = True)
321 S.sort(key = first_component, reverse =
True) # la méthode "sort"
ãÑ conserve
322 # l'ordre lorque la cle est
ãÑ la meme
323 return S #O(len(L))
324
325 # prend en entree une liste triee par la
fonction "double_sort"
326 # renvoie une sous-liste strictement
décroissante pour la premiere
327 # composante et strictement croissante
pour la seconde
328 def first_selection(L):
329 S = [L[0]] # L etant triee par
"double_sort", L[0] sera forcement
330 # le premier element de la
sous-liste
331 n = len(L)
332 i = 1
333 j = 0
334 while i < n:
335 if L[i][0] < S[j][0] and L[i][1] >
S[j][1]:
336 S.append(L[i])
337 j+=1
338 i+=1
339 return S #O(len(L))
340
49
341 # prend en entree trois points strictement
decroissants/croissants
342 # pour la premiere/seconde composante renvoie "True" ssi
le point du milieu
343 # est strictement au-dessus de la droite passant par les
deux autres
344 def above(a,b,c):
345 return b[1] > (a[1]*(b[0]-c[0])/(a[0]-c[0]))
+ ãÑ (c[1]*(a[0]-b[0])/(a[0]-c[0]))
346
347 # prend en entree une liste strictement
decroissante/croissante pour la ãÑ
premiere/
348 # seconde composante renvoie la sous-liste privee des
points Pareto-domines
349 # par une combinaison d'autres points
350 def second_selection(L):
351 if len(L) == 1: return L
352 S = [L[0],L[1]]
353 n = len(L)
354 i = 2
355 j = 0
356 while i < n:
357 if above(S[j],S[j+1],L[i]):
358 S.append(L[i])
359 j+=1
360 i+=1
361 else:
362 S.pop()
363 if j == 0:
364 S.append(L[i])
365 i+=1
366 else:
367 j-=1
368 return(S) # O(len(L))
369
370 # prend en entree une liste de points de R2
371 # renvoie la liste triee des points constituant la
frontiere de Pareto de ãÑ l'enveloppe
convexe de l'ensemble des points
372 def frontier_points(L):
373 S_0 = double_sort(L)
374 S_1 = first_selection(S_0)
375 S_2 = second_selection(S_1)
376 return S_2 # O(len(L))
377
378 # prend en entree deux points strictement
decroissants/croissants pour la
ãÑ premiere
379 # /seconde composante renvoie l'ordonnee du maximiseur de
la "fonction produit"
380 # la droite passant par ces deux points
381
382 def y_max(a,b): # a est sous la forme [x1,y1]
383 a_1, a_2, b_1, b_2 = a[0], a[1] ,b[0] ,b[1]
384 p_cut = b_1/(b_1-a_1)
50
385 return (p_cut*a_2 + (1-p_cut)*b_2)/2
386
387 # idem "y_max"; renvoie
l'abscisse
388 def x_max(a,b):
389 a_1, a_2 ,b_1 ,b_2 = a[0], a[1] ,b[0] ,b[1]
390 p_cut = b_2/(b_2-a_2)
391 return (p_cut*a_1 + (1-p_cut)*b_1)/2
392
393 # prend en entrée une liste traitee par
"frontier_points"
394 # renvoie le point de
l'enveloppe convexe de la liste qui maximise la
"fonction
ãÑ produit"
395 def solution_rec(L):
396 n = len(L)
397 if n == 0:
398 print("Echec de la recurrence")
399 if n == 1:
400 return array([[L[0][0],L[0][1]],[0,0],[0,0],[1,0]])
401 else:
402 m = n//2
403 a, b = L[m-1], L[m]
404 y = y_max(a,b)
405 if y < a[1]:
406 if n > 2:
407 return solution_rec(L[:m])
408 else:
409 s = array([a[0],a[1]])
410 a = array([a[0],a[1]])
411 b = array([b[0],b[1]])
412 c = array([1,0])
413 return array([s,a,b,c])
414 if y > b[1]:
415 if n > 2:
416 return solution_rec(L[m:])
417 else:
418 s = array([b[0],b[1]])
419 a = array([a[0],a[1]])
421 c = array([0,1])
422 return array([s,a,b,c])
423 else:
424 x = x_max(a,b)
425
420 b = array([b[0],b[1]])
p = (x - b[0]) / (a[0]-b[0])
426 s = array([x,y])
427 a = array([a[0],a[1]])
428 b = array([b[0],b[1]])
429 c = array([p,1-p])
430 return array([s,a,b,c]) #
O(len(L))
431
432 # prend en entree une liste de points et un vecteur de
R2
51
433 # renvoie la liste decalee par le vecteur
434 def shift(L,v):
435 L_shifted = []
436 for i in range(len(L)):
437 P = array([ L[i][0] + v[0], L[i][1] + v[1] ])
438 L_shifted.append(P)
439 return L_shifted # O(len(L))
440
441 # prend en entree une liste de points de R2
442 # renvoie deux listes constituees respectivement de
ses abscisses et ordonnees
443 def get_lists(L):
444 X = []
445 Y = []
446 for i in range(len(L)):
447 tmp = L[i]
448 X.append(tmp[0])
449 Y.append(tmp[1])
450 return [X,Y] # O(len(L))
451
452 # prend en entree une liste d'alternatives et un point
de desaccord
453 # affiche la representation du jeu sur le plan ainsi
que sa solution de Nash
454 def plot_solution(A,d):
455 L = shift(A+[d], (-1)*d)
456 F = frontier_points(L)
457 s = solution_rec(F)[0]
458 A_lists = get_lists(A)
459 F_lists = get_lists(shift(F,d))
460 fig = figure()
461 ax = fig.add_subplot(111)
462 plot(A_lists[0], A_lists[1], '.k')
463 plot(d[0], d[1], '+b', label="point de
désaccord")
464 plot(F_lists[0], F_lists[1], '--y', c = "deepskyblue",
label="frontière de
ãÑ Pareto")
465 plot(s[0]+d[0], s[1]+d[1], '*r', label="solution de
Nash")
466 ax.add_patch(Rectangle(d,s[0], s[1], linewidth = 0.5,
edgecolor = 'black',
ãÑ fill = False,hatch='/'))
467 grid()
468 title("Représentation graphique du jeu")
469 legend()
470 show()
471
472 def to_list (s):
473 n = len(s)
474 if n%2 != 0:
475 print('Raté')
476 return 0
477 m = int(n/2)
478 L = []
479 for i in range (m):
52
480 x = [s[2*i],s[2*i+1]]
481 L.append(x)
482 return L # O(len(L))
483
484 def true_solution(A,d):
485 L = shift(A+[d], (-1)*d)
486 F = frontier_points(L)
487 s = solution_rec(F)
488 s_list =[]
489 for i in range (3):
490 s_list.append(shift(to_list(s[i]),d))
491
492 L=[]
493 for i in range (len(s_list)):
494 p = [s_list[i][0][0], s_list[i][0][1]]
495 L.append(p)
496 L.append([s[3][0],s[3][1]])
497 return L # O(len(L))
498
499
500 def print_solution(s): # prend en
entrée le résultat de true_solution
501 sol =
[round(s[0][0],2),round(s[0][1],2)]
502 a =
[round(s[1][0],2),round(s[1][1],2)]
503 b =
[round(s[2][0],2),round(s[2][1],2)]
504 p = round(s[3][0],2)
505 q = round(1 - p,2)
506
507 if p == 1:
508 print ("La solution est le point de la
liste initiale : ", sol)
509 elif p == 0:
510 print ("La solution est le point de la
liste initiale : ", sol)
511 else :
512 print("La solution est une combinaison
linéaire du point " + str(a)\
513 + " chargé du poids " + str(p) + "
et du point " + str(b) + \
514 " chargé du poids " + str(q))
515 print("La solution est le point ",
sol)
516
517
518
519
520
521
522
523
524
525
#%%
#'''
|
'''
|
|
|
|
Partie 3
|
|
|
'''
|
L =
|
[[444,
|
968],
|
[261,
|
220],
|
[646,
|
985],
|
[815,
|
878],
|
[929,
|
122],\
|
|
[638,
|
136],
|
[536,
|
550],
|
[435,
|
992],
|
[346,
|
161],
|
[372,
|
283],\
|
|
[608,
|
674],
|
[569,
|
491],
|
[255,
|
962],
|
[670,
|
198],
|
[958,
|
304]]
|
d =
|
[1, 28]
|
|
|
|
|
|
|
|
|
526
527 L_list = get_lists (L)
528
53
529 figure()
530 plot(L_list[0],L_list[1],'o', c = 'b')
531 plot(d[0],d[1],'o', c = 'r')
532
533 L_double_sort = double_sort(L)
534 L_double_sort_list =
get_lists(L_double_sort)
535 figure()
536
plot(L_double_sort_list[0],L_double_sort_list[1],'o', c = 'b')
537 plot(d[0],d[1],'o', c = 'r')
538 title('Points restants après le
triage par "double sort"')
539
540 L_frontier =
frontier_points(L_double_sort)
541 L_frontier_list =
get_lists(L_frontier)
542 figure()
543
plot(L_frontier_list[0],L_frontier_list[1],'o', c = 'b')
544 plot(d[0],d[1],'o', c = 'r')
545 title('Points restants après le
triage par "frontier point"')
546
547 d = array([d[0],d[1]])
548 S = true_solution(L,d)
549 print_solution(S)
550 plot_solution(L, d)
#'''
54
8.2.2 Fichier "Fonctions_distances.py"
551 from numpy import array
552
553 def marche(x):
554 return 5*x
555
556 def dist(x,y): # simple calcul de la distance
euclidienne
557 return abs(y-x)
558
559 def cp3 (x,z,y): # calcul de la distance entre deux
points en imposant un
ãÑ checkpoint
560 return dist(x,z) + dist(z,y)
561
562 def cp4 (x,v,w,y):
563 return cp3(x,v,w)+dist(w,y)
564
565 def cp5 (x,u,v,w,y):
566 return cp4(x,u,v,w)+dist(w,y)
567
568 def dist_v(x,y): # calcul de la distance parcourue en
voiture en faisant
ãÑ x -> y
569 return dist(x,y)
570
571 def cp3_v (x,z,y): # calcul de la distance parcourue en
voiture
572 return cp3(x,z,y)
573
574 def cp4_v (x,v,w,y):
575 return cp4(x,v,w,y)
576
577 def cp5_v (x,u,v,w,y):
578 return cp5(x,u,v,w,y)
579
580 def dist_m(x,y): # calcul de la distance parcourue en
marchant, en ãÑ considérant
que dist_m = marche(d_v)
581 return marche(dist_v(x,y))
582
583 def cp3_m (x,z,y): # calcul de la distance parcourue en
marchant en
ãÑ faisant x -> z ->
y
584 return marche(cp3_v(x,z,y))
585
586 def cp4_m (x,v,w,y): # calcul de la distance parcourue en
marchant en
ãÑ faisant x -> v -> w
-> y
587 return marche(cp4_v(x,v,w,y))
588
589 def cp5_m (x,u,v,w,y):
590 return marche(cp5_v(x,u,v,w,y))
591
592 #%%
55
593 # renvoie un vecteur de dimension 2x9 des distances
négatives
594 # quand on est dans le cas à 9 solutions sur un
segment [0,1]
595 # le premier vecteur est celui des 9 distances du
joueur 1
596 # le second vecteur est celui des 9 distances du
joueur 2
597
598 def vect_temps (v,x1,x2,y1,y2):
599
600 d11 = cp4_v (v,x1,x2,y1)
601 d12 = d11 + dist_v (y1,y2)
602
603 d22 = cp4_v (v,x1,x2,y2)
604 d21 = d22 + dist_v (y2,y1)
605
606 d31 = cp4_v (v,x2,x1,y1)
607 d32 = d31 + dist_v (y1,y2)
608
609 d41 = cp4_v (v,x2,x1,y2)
610 d42 = d41 + dist_v (y2,y1)
611
612 d52 = cp3_v (v,x2,y2)
613 d51 = d52 + cp3_v(y2,x1,y1)
614
615 d61 = cp3_v (v,x1,y1)
616 d62 = d61 + cp3_v(y1,x2,y2)
617
618 d71 = dist_m (x1,y1) # le joueur 1 y va à
pied
619 d72 = cp3_v (v,x2,y2)
620
621 d81 = cp3_v (v,x1,y1) # le joueur 2 y va à
pied
622 d82 = dist_m (x2,y2)
623
624 d91 = dist_m(x1, y1) # les deux joueurs y vont
à pied
625 d92 = dist_m(x2, y2)
626
627 D =
ãÑ
array([[d11,d21,d31,d41,d51,d61,d71,d81,d91],[d12,d22,d32,d42,d52,d62,d72,d82,d92]])
628
629 return D
56
8.2.3 Fichier
"Etude_probleme_voiture_partagee"
630 from numpy import array
631 from matplotlib import pyplot as plt
632 from random import randint
633 from sympy import symbols, solve
634
635 import Nash_solver as ns
636 import Fonctions_distances as fd
637 #%%
638
639 ''' Jeu classique '''
640 v = 0.21
641 x1 = 0.2
642 x2 = 0.1
643 y1 = 0.98
644 y2 = 0.66
645 decimale = 2
646 a = 0
647 b = 1
648 tolerance = 100
649
650 n = 4
651 m = 1000
652 joueur = 1
653 i = 0
654
655 #%%
656 ''' Fonctions "utilitaires"
'''
657
658 # fonctions pour transformer un array de
coordonnées de points en liste
659 # on entre neuf points (correspondands
aux alternatives) sous forme d'array de
ãÑ dimension 2
660 # dimension 1 : abcisses des 9
alternatives
661 # dimension 2 : ordonnées des 9
alternatives
662 def array_to_list_simple (D):
663 C = []
664 for i in range (9): # on remplit la
liste
665 C.append([D[0][i],D[1][i]])
666 return C
667
668 # même fonction ou on entre
plusieurs combinaisons de 9 points
669 # exemple : si on veut entrer 1000
combinaisons différentes on aura un array
670 # de dimension 2000
671 def array_to_list (D):
672 lengthD = int(len(D)/2) # on prend la
partie entière divisée par deux,
les ãÑ paires de lignes sont
regroupées
673 C = []
674 for i in range(lengthD): #
création de la liste sour le format qui
675
57
C.append([]) # nous intéresse pour le
calcul de la solution
ãÑ de Nash
676 for j in range (9):
677 C[i].append([])
678 for i in range (lengthD): # on remplit
la liste
679 for j in range (9):
C[i][j] = [D[2*i][j],D[2*i+1][j]]
680
681 return C
682
683
684 def round_list_coordonnees_nx2 (D,decimale =
2): # D =
ãÑ
((2.1223,3.3314],(2.44141,4.43134],...]
685 for i in range (len(D)):
686 D[i][0] = round(D[i][0],decimale)
687 D[i][1] = round(D[i][1],decimale)
688 return D # D =
ãÑ
((2.12,3.33],(2.44,4.43],...]
689
690 def get_coordonnees (L): # L =
((x1,x2,x3,...],(y1,y2,y3,...]]
691 M = []
692 for i in range (len(L[0])):
M.append([L[0][i],L[1][i]])
693
694 return M # M =
((x1,y1],(x2,y2],(x3,y3],...]
695
696 #%%
697 ''' Fonctions servant à
l'affichage de la solution de Nash '''
ãÑ
698
699 def print_donnees (x1,x2,y1,y2,v = 0.5):
700 print("v = ",v)
701 print("x1 = ",x1)
702 print("x2 = ",x2)
703 print("y1 = ",y1)
704 print("y2 = ",y2)
705
706 def utilite (x):
707 return 5-x*x
708
709 def utilite_list_couple (L):
710 D = []
711 for i in range (len(L)):
712 A1 = utilite(L[i][0])
713 A2 = utilite(L[i][1])
714 A = [A1,A2]
715 D.append(A)
716 return D # O(len(L))
717
718 def coordonnees_utilites (x1,x2,y1,y2,v =
0.5,decimale = 2):
719 D =
fd.vect_temps(v,x1,x2,y1,y2) # sans mensonges
58
720 D1 = array_to_list_simple(D) # rappel : liste de
coordonnées de 9 points
721 D2 = utilite_list_couple(D1) # application de la fonction
d'utilité
722 D_f = round_list_coordonnees_nx2(D2,decimale) # on essaye
de garder n
ãÑ décimales
723 return D_f # D_f =
[[u_x_1,u_y_1],[u_x_2,u_y_2],[u_x_3,u_y_3],...]
724
725 def desaccord (D): # prend en argument la solution de
coordonnees_utilites
726 return array([D[8][0],D[8][1]]) # point de
désaccord
727
728 def solution (D, d):
729 return ns.true_solution(D,d)
730 # array([[x_sol,y_sol],[x_a,y_a],[x_b,y_b],
[p,1-p]])
731 # x_sol = utilité joueur 1, y_sol =
utilité joueur 2
732
733 def solution_rounded (s, decimale = 2): # prend en
argument la solution de la
ãÑ fonction "solution"
734 for i in range (4): # s = array(solution =
[3.2313,3.234], a
ãÑ =[2.2313,4.1414], b =[.,.],
p=[.,.])
735 s[i][0] = round(s[i][0],decimale)
736 s[i][1] = round(s[i][1],decimale)
737 return s # s = array(solution = [3.23,3.23], a
=[2.23,4.14], b =[.,.], ãÑ
p=[.,.])
738
739 ''' Fonction "résumé" du cas
d'étude de la voiture partagée
'''
ãÑ
740
741 def solution_rapide (x1,x2,y1,y2,v = 0.5,decimale = 2):
742 D = coordonnees_utilites (x1,x2,y1,y2,v,decimale)
743 d = desaccord (D)
744 s = solution (D, d)
745 s = solution_rounded (s) # s = array(solution =
[3.23,3.23], a
ãÑ =[2.23,4.14], b =[.,.],
p=[.,.])
746 return s
747
748 def print_solution_voiture(s,D): # prend en entrée
le résultat de true_solution ãÑ
et la liste des 9 coordonnées d'utilité
749 sol = [s[0][0],s[0][1]]
750 a = [s[1][0],s[1][1]]
751 b = [s[2][0],s[2][1]]
752 p = round(s[3][0],2)
753 q = round(1 - p,2)
754 B=[]
755 B.append(str("La voiture ira chercher J1 puis J2,
déposera J1 puis J2"))
756 B.append(str("La voiture ira chercher J1 puis J2,
déposera J2 puis J1"))
757 B.append(str("La voiture ira chercher J2 puis J1,
déposera J1 puis J2"))
758 B.append(str("La voiture ira chercher J2 puis J1,
déposera J2 puis J1") )
759 B.append(str("La voiture ira chercher J2, le déposera,
puis ira chercher J1
ãÑ et le déposera"))
760 B.append(str("La voiture ira chercher .31,
le déposera, puis ira chercher .32
59
ãÑ et le déposera"))
761 B.append(str("La voiture ira chercher .32 et
le déposera, .31 se rendra à
ãÑ pied"))
762 B.append(str("La voiture ira chercher .31 et
le déposera, .32 se rendra à
ãÑ pied"))
763 B.append(str("La voiture n'ira chercher
personne, les deux joueurs se
ãÑ rendront à pied
à leur destination"))
764
765 if sol in D:
766 i = 0
767 while sol != D[i]:
768 i+= 1
769 if i>=9 :
770 print("Soucis 1")
771 break
772 print(B[i])
773 else :
774 i = 0
775 j = 0
776 while a != D[i]:
777 i+= 1
778 if i>=9 :
779 print("Soucis 2")
780 break
781 while b != D[j]:
782 j+= 1
783 if j>=9 :
784 print("Soucis 3")
785 break
786 print(str(p) + " fois du temps, on aura
l'action : " + B[i] + "\n \n" +
787 str(q) + " fois du temps, on aura
l'action : " + B[j])
788
789
790 def print_solution_jeu_classique
(x1,x2,y1,y2,v = 0.5,decimale = 2):
791
792 print_donnees (x1,x2,y1,y2,v)
793 print("\n Solution du jeu
classique ãÑ \n")
794
795 print("La voiture est placée en " +
str(v) + " sur [0,1] \n")
796
797 print("Le joueur 1 est placée en " +
str(x1) + \
798 " sur [0,1] et souhaite se rendre en " +
str(y1) + " \n")
799 print("Le joueur 2 est placée en " +
str(x2) + \
800 " sur [0,1] et souhaite se rendre en " +
str(y2) + " \n")
801
802 D = coordonnees_utilites
(x1,x2,y1,y2,v,decimale)
803 d = desaccord(D)
60
804 s = solution(D,d)
805 s = solution_rounded(s)
806 u1 = s[0][0]
807 u2 = s[0][1]
808
809 print("Le point de désaccord
correspondant au fait que les deux joueurs
se ãÑ rendent à pied est ",\
810 d)
811 print("Avec une réalisation classique
du jeu, l'action suivante sera ãÑ choisie :
")
812 print_solution_voiture(s,D)
813 print("\nJ1 en retire une utilité de
", u1)
814 print("\nJ2 en retire une utilité de
", u2)
815 ns.plot_solution(D,d)
816
817
818 ''' Jeu mensonge '''
819
820 def desutilite_marche (x,y,decimale = 2):
821 return
round(-(fd.dist_m(x,y))**(2),decimale)
822
823 def y_max_joueur_quand_il_ment
(joueur,a,b,x1,x2,y1,y2,v = 0.5,decimale = ãÑ
2,tolerance = 100) :
824 u_et_y = [[],[]]
825 if joueur == 1 : # le while suivant
trouve le max quand J2 ment, on
ãÑ inverse donc si c'est J1
qui ment
826 c = x1
827 x1 = x2
828 x2 = c
829 d = y1
830 y1 = y2
831 y2 = d
832 i = 0
833 while (b-a) > 10**(-tolerance) and (i
< 50):
834 p = a + (b-a)/4
835 m = a + (b-a)/2
836 q = a + 3*(b-a)/4
837
838 u_p =
solution_rapide(x1,x2,y1,p,v,decimale)[0][1] + ãÑ
desutilite_marche(p, y2, decimale)
839 u_q =
solution_rapide(x1,x2,y1,q,v,decimale)[0][1] + ãÑ
desutilite_marche(q, y2, decimale)
840 u_m =
solution_rapide(x1,x2,y1,m,v,decimale)[0][1] + ãÑ
desutilite_marche(m, y2, decimale)
841
842 u_et_y[0].append(u_p),
u_et_y[0].append(u_q), u_et_y[0].append(u_m)
843 u_et_y[1].append(p), u_et_y[1].append(q),
u_et_y[1].append(m)
844
845 if u_p > u_m:
61
846 b = m
847 elif u_m < u_q:
848 a = m
849 else:
850 a = p
851 b = q
852 i+=1
853 y_sol = (a+b)/2
854 u_sol = solution_rapide
(x1,x2,y1,y_sol,v,decimale)[0][1] +
ãÑ desutilite_marche(y_sol, y2,
decimale)
855
856 u_et_y[0].append(u_sol)
857 u_et_y[1].append(y_sol)
858 return [y_sol,u_sol,u_et_y] # u_et_y
sert au plot
859
860
861 def plot_recherche_max_joueur1et2
(x1,x2,y1,y2,v = 0.5,decimale = 2,tolerance = ãÑ
100,titre = "Utilité des joueurs en fonction de leur point
ãÑ d'arrivée",a=0,b=1):
862 s1 = y_max_joueur_quand_il_ment
(1,a,b,x1,x2,y1,y2,v,decimale,tolerance)
863 s2 = y_max_joueur_quand_il_ment
(2,a,b,x1,x2,y1,y2,v,decimale,tolerance)
864
865 u_verite = solution_rapide
(x1,x2,y1,y2,v,decimale)[0]
866
867 plt.figure(0)
868 plt.plot(s1[2][1],s1[2][0], '.k',color =
"deeppink", label = "Utilité J1")
869 plt.plot(s2[2][1],s2[2][0], '.k',color =
"deepskyblue", label = "Utilité
ãÑ J2")
870 plt.scatter(s1[0], s1[1], c = 'red', label =
'Max de J1 : ' +
ãÑ str(round(s1[1],decimale)))
871 plt.scatter(s2[0], s2[1], c = 'blue', label
= 'Max de J2 : ' + ãÑ
str(round(s2[1],decimale)))
872 plt.plot([a, b], [u_verite[0], u_verite[0]],
'--', label = 'Utilité J1 sans
ãÑ mentir', c = 'deeppink',
lw=1)
873 plt.plot([a, b], [u_verite[1], u_verite[1]],
'--', label = 'Utilité J2 sans
ãÑ mentir', c = 'deepskyblue',
lw=1)
874 plt.xlabel ('Starting point')
875 plt.ylabel ('Utility')
876 plt.title (titre)
877 plt.legend(loc = 'best', shadow=True,
borderpad=1)
878 plt.grid()
879 plt.show()
880
881 # similaire a la fonction
précédente mais concerne seulement 1 joueur
882 def plot_recherche_max_joueur1
(x1,x2,y1,y2,v = 0.5,decimale = 2,tolerance = ãÑ
100,titre = "Utilité du joueur en fonction de son point
ãÑ d'arrivée",a=0,b=1):
883 s1 = y_max_joueur_quand_il_ment
(1,a,b,x1,x2,y1,y2,v,decimale,tolerance)
884
62
885 u_verite = solution_rapide
(x1,x2,y1,y2,v,decimale)[0]
886
887 plt.figure(1)
888 plt.plot(s1[2][1],s1[2][0], '.k',color =
"deeppink", label = "Utilité J1")
889 plt.scatter(s1[0], s1[1], c = 'red', label =
'Max de J1 : ' +
ãÑ str(round(s1[1],decimale)))
890 plt.plot([a, b], [u_verite[0], u_verite[0]],
'--', label = 'Utilité J1 sans ãÑ
mentir', c = 'deeppink', lw=1)
891 plt.xlabel ('Starting point')
892 plt.ylabel ('Utility')
893 plt.title (titre)
894 plt.legend(loc = 'best', shadow=True,
borderpad=1)
895
896
897 def plot_recherche_max_joueur2
(x1,x2,y1,y2,v = 0.5,decimale = 2,tolerance = ãÑ
100,titre = "Utilité du joueur en fonction de son point
ãÑ d'arrivée",a=0,b=1):
898 s2 = y_max_joueur_quand_il_ment
(2,a,b,x1,x2,y1,y2,v,decimale,tolerance)
899
900 u_verite = solution_rapide
(x1,x2,y1,y2,v,decimale)[0]
901
902 plt.figure(1)
903 plt.plot(s2[2][1],s2[2][0], '.k',color =
"deepskyblue", label = "Utilité
ãÑ J")
904 plt.scatter(s2[0], s2[1], c = 'blue', label
= 'Max de J2 : ' +
ãÑ str(round(s2[1],decimale)))
905 plt.plot([a, b], [u_verite[1], u_verite[1]],
'--', label = 'Utilité J2 sans
ãÑ mentir', c = 'deepskyblue',
lw=1)
906 plt.xlabel ('Starting point')
907 plt.ylabel ('Utility')
908 plt.title (titre)
909 plt.legend(loc = 'best', shadow=True,
borderpad=1)
910 plt.grid()
911
912 def J1_et_J2_verite (x1,x2,y1,y2,v =
0.5,decimale = 2):
913 u_verite = solution_rapide
(x1,x2,y1,y2,v,decimale)
914 return u_verite #
array([[x_sol,y_sol],[x_a,y_a],[x_b,y_b], [p,1-p]])
915
916 def J1_ment (x1,x2,y1,y2,v = 0.5,decimale =
2,tolerance = 100):
917 s_J1_ment =
y_max_joueur_quand_il_ment ãÑ
(1,a,b,x1,x2,y1,y2,v,decimale,tolerance)
918 y_J1_ment = s_J1_ment[0]
919 s_J1_ment_bis = solution_rapide
(x1,x2,s_J1_ment[0],y2,v,decimale)
920 u1_J1_menteur = s_J1_ment[1] #
utilité de J1 quand il ment
921 u2_J1_ment = s_J1_ment_bis[0][1] #
utilité de J2 quand J1 ment et que J2 ne
ãÑ ment pas
922 return [u1_J1_menteur, u2_J1_ment,
y_J1_ment]
923
924 def J2_ment
(x1,x2,y1,y2,v,decimale,tolerance):
63
925 s_J2_ment = y_max_joueur_quand_il_ment
ãÑ
(2,a,b,x1,x2,y1,y2,v,decimale,tolerance)
926 y_J2_ment = s_J2_ment[0]
927 s_J2_ment_bis = solution_rapide
(x1,x2,y1,s_J2_ment[0],v,decimale)
928 u1_J2_ment = s_J2_ment_bis[0][0] # utilité de J1
quand J2 ment et que J1 ne
ãÑ ment pas
929 u2_J2_menteur = s_J2_ment[1] # utilité de J2 quand
il ment
930 return [u1_J2_ment, u2_J2_menteur,
y_J2_ment]
931
932 def J1_et_J2_mentent_ingenument
(J1_ment_obj,J2_ment_obj):
933 y_J1_ment = J1_ment_obj [2]
934 y_J2_ment = J2_ment_obj [2]
935 solution = solution_rapide(x1, x2, y_J1_ment, y_J2_ment, v,
decimale)
936 u1 = solution[0][0]
937 u2 = solution[0][1]
938 return [u1,u2,y_J1_ment,y_J2_ment]
939
940 def J1_et_J2_mentent_decouvert
(x1,x2,y1,y2,v = 0.5,decimale = 2,tolerance = ãÑ
100,a=0,b=1):
941 s_J1_ment = y_max_joueur_quand_il_ment
ãÑ
(1,a,b,x1,x2,y1,y2,v,decimale,tolerance)
942 s_J2_ment =
y_max_joueur_quand_il_ment ãÑ
(2,a,b,x1,x2,y1,y2,v,decimale,tolerance)
943 y_J1_ment = s_J1_ment[0] # choix du point
d'arrivée de J1 quand il ment
944 y_J2_ment = s_J2_ment[0] # choix du point
d'arrivée de J2 quand il ment
945
946 s_J2_ment_sachant_J1_ment =
y_max_joueur_quand_il_ment ãÑ(2,a,b,x1,x2,y_J1_ment,y2,v,decimale,tolerance)
947 y2_J2_ment_sachant_J1_ment = s_J2_ment_sachant_J1_ment[0]
948 s_J2_ment_sachant_J1_ment_bis = solution_rapide
ãÑ
(x1,x2,y_J1_ment,y2_J2_ment_sachant_J1_ment,v,decimale)
949 u1_J2_ment_sachant_J1_ment =
s_J2_ment_sachant_J1_ment_bis[0][0]
950 u2_J2_ment_sachant_J1_ment = s_J2_ment_sachant_J1_ment[1]
951
952 s_J1_ment_sachant_J2_ment =
y_max_joueur_quand_il_ment ãÑ(1,a,b,x1,x2,y1,y_J2_ment,v,decimale,tolerance)
953 y1_J1_ment_sachant_J2_ment = s_J1_ment_sachant_J2_ment[0]
954 s_J1_ment_sachant_J2_ment_bis = solution_rapide
ãÑ
(x1,x2,y1_J1_ment_sachant_J2_ment,y_J2_ment,v,decimale)
955 u1_J1_ment_sachant_J2_ment = s_J1_ment_sachant_J2_ment[1]
956 u2_J1_ment_sachant_J2_ment =
s_J1_ment_sachant_J2_ment_bis[0][1]
957
958
ãÑ
#plot_recherche_max_joueur1(x1,x2,y1,y_J2_ment,v,decimale,tolerance,"Utilité
ãÑ du joueur en fonction de son point
d'arrivée sachant que l'autre ment")
959
#plot_recherche_max_joueur2(x1,x2,y_J1_ment,y2,v,decimale,tolerance)
960
64
961 return
ãÑ
[[u1_J2_ment_sachant_J1_ment,u2_J2_ment_sachant_J1_ment],[u1_J1_ment_sachant_J2_ment,u2_
ãÑ
[y_J1_ment,y2_J2_ment_sachant_J1_ment],[y1_J1_ment_sachant_J2_ment,y_J2_ment]]
962
963 def print_utilites_jeu_info_parfaite
(x1,x2,y1,y2,v = 0.5,decimale = 2):
964 J1_et_J2_verite_var = J1_et_J2_verite
(x1,x2,y1,y2,v,decimale)
965 J1_ment_var = J1_ment
(x1,x2,y1,y2,v,decimale,tolerance)
966 J2_ment_var = J2_ment
(x1,x2,y1,y2,v,decimale,tolerance)
967 J1_et_J2_mentent_ingenument_var =
J1_et_J2_mentent_ingenument(J1_ment_var,
ãÑ J2_ment_var)
968 J1_et_J2_mentent_decouvert_var =
J1_et_J2_mentent_decouvert ãÑ
(x1,x2,y1,y2,v,decimale,tolerance)
969
970 u1 = J1_et_J2_verite_var [0][0]
971 u2 = J1_et_J2_verite_var [0][1]
972 u1_J1_ment = J1_ment_var [0]
973 u2_J1_ment = J1_ment_var [1]
974 u1_J2_ment = J2_ment_var [0]
975 u2_J2_ment = J2_ment_var [1]
976 u1_J1_ment_J2_ment =
J1_et_J2_mentent_ingenument_var [0]
977 u2_J1_ment_J2_ment =
J1_et_J2_mentent_ingenument_var [1]
978 u1_J1_ment_sachant_J2_ment =
J1_et_J2_mentent_decouvert_var [1][0]
979 u2_J1_ment_sachant_J2_ment =
J1_et_J2_mentent_decouvert_var [1][1]
980 u1_J2_ment_sachant_J1_ment =
J1_et_J2_mentent_decouvert_var [0][0]
981 u2_J2_ment_sachant_J1_ment =
J1_et_J2_mentent_decouvert_var [0][1]
982
983 y1_J1_ment = round(J1_ment_var
[2],decimale)
984 y2_J2_ment = round(J2_ment_var
[2],decimale)
985 y1_J1_ment_J2_ment =
round(J1_et_J2_mentent_ingenument_var [2],decimale)
986 y2_J1_ment_J2_ment =
round(J1_et_J2_mentent_ingenument_var [3],decimale)
987 y1_J1_ment_sachant_J2_ment =
round(J1_et_J2_mentent_decouvert_var
ãÑ [2][0],decimale)
988 y2_J1_ment_sachant_J2_ment =
round(J1_et_J2_mentent_decouvert_var ãÑ
[2][1],decimale)
989 y1_J2_ment_sachant_J1_ment =
round(J1_et_J2_mentent_decouvert_var ãÑ
[3][0],decimale)
990 y2_J2_ment_sachant_J1_ment =
round(J1_et_J2_mentent_decouvert_var ãÑ
[3][1],decimale)
991
992
993 print("\n Valeurs du jeu à
information parfaite
ãÑ \n")
994
995 print("\nQuand les deux joueurs disent la
vérité : ")
996 print("Utilité de J1 : ", u1)
997 print("Utilité de J2 : ", u2)
998
999 print("\nQuand J1 ment et que J2 dit la
vérité : ")
1000 print("Utilité de J1 : ",
u1_J1_ment)
65
1001 print("Utilité de J2 : ", u2_J1_ment)
1002 print("J1 annonce vouloir aller en " + str(y1_J1_ment) + "
au lieu de " +
ãÑ str(y1))
1003 print("La différence d'utilité de J1
équivaut à : " , round(u1_J1_ment
- ãÑ u1, decimale))
1004 print("La différence d'utilité de J2
équivaut à : " , round(u2_J1_ment
- ãÑ u2, decimale))
1005
1006 print("\nQuand J2 ment et que J1 dit la vérité
: ")
1007 print("Utilité de J1 : ", u1_J2_ment)
1008 print("Utilité de J2 : ", u2_J2_ment)
1009 print("J2 annonce vouloir aller en " + str(y2_J2_ment) + "
au lieu de " +
ãÑ str(y2))
1010 print("La différence d'utilité de J1
équivaut à : " , round(u1_J2_ment -
ãÑ u1, decimale))
1011 print("La différence d'utilité de J2
équivaut à : " , round(u2_J2_ment -
ãÑ u2, decimale))
1012
1013 print("\nQuand les deux joueurs mentent de manière
ingénue (ils se ãÑ contentent de faire
leur meilleur mensonge quand l'autre dit la ãÑ
vérité') : ")
1014 print("Utilité de J1 : ", u1_J1_ment_J2_ment)
1015 print("Utilité de J2 : ", u2_J1_ment_J2_ment)
1016 print("J1 annonce vouloir aller en " +
str(y1_J1_ment_J2_ment) + " au lieu
ãÑ de " + str(y1))
1017 print("J2 annonce vouloir aller en " +
str(y2_J1_ment_J2_ment) + " au lieu
ãÑ de " + str(y2))
1018 print("La différence d'utilité de J1
équivaut à : " ,
ãÑ round(u1_J1_ment_J2_ment - u1,
decimale))
1019 print("La différence d'utilité de J2
équivaut à : " ,
ãÑ round(u2_J1_ment_J2_ment - u2,
decimale))
1020
1021
1022 print("\nQuand le joueur 2 a décidé de mentir
alors qu'il savait que le ãÑ joueur 1 mentait
: ")
1023 print("Utilité de J1 : ",
u1_J2_ment_sachant_J1_ment)
1024 print("Utilité de J2 : ",
u2_J2_ment_sachant_J1_ment)
1025 print("J1 annonce vouloir aller en " +
str(y1_J2_ment_sachant_J1_ment) + "
ãÑ au lieu de " + str(y1))
1026 print("J2 annonce vouloir aller en " +
str(y2_J2_ment_sachant_J1_ment) + "
ãÑ au lieu de " + str(y2))
1027 print("La différence d'utilité de J1
équivaut à : " ,
ãÑ
round(u1_J2_ment_sachant_J1_ment - u1, decimale))
1028 print("La différence d'utilité de J2
équivaut à : " ,
ãÑ
round(u2_J2_ment_sachant_J1_ment - u2, decimale))
1029
1030
1031 print("\nQuand le joueur 1 a décidé de mentir
alors qu'il savait que le ãÑ joueur 2 mentait
: ")
66
1032 print("Utilité de J1 : ",
u1_J1_ment_sachant_J2_ment)
1033 print("Utilité de J2 : ",
u2_J1_ment_sachant_J2_ment)
1034 print("J1 annonce vouloir aller en " +
str(y1_J1_ment_sachant_J2_ment) + "
ãÑ au lieu de " + str(y1))
1035 print("J2 annonce vouloir aller en " +
str(y2_J1_ment_sachant_J2_ment) + "
ãÑ au lieu de " + str(y2))
1036 print("La différence
d'utilité de J1 équivaut à : " ,
ãÑ
round(u1_J1_ment_sachant_J2_ment - u1, decimale))
1037 print("La différence
d'utilité de J2 équivaut à : " ,
ãÑ
round(u2_J1_ment_sachant_J2_ment - u2, decimale))
1038
1039
1040 ''' Fonctions permettant de
trouver la solution de Nash au
ãÑ jeu à info
parfaite '''
1041
1042 def comparaison (joueur,s1,s2):
1043 if s1[joueur-1] <= s2[joueur-1] :
1044 return s2
1045 elif s1[joueur-1] > s2[joueur-1] : #
pourquoi le -1 : indice de J1 = 0,
ãÑ indice de J2 = 1
1046 return s1
1047 # on compare deux couples
d'utilité pour le joueur 1 ou 2
1048 # on prend en argument 1 ou 2
correspondant au joueur
1049 # ainsi que les deux couples (u11,
u12) et (u21, u22) d'utilité qu'on souhaite
ãÑ comparer
1050
1051 def nash_info_parfaite
(premier_joueur,S): # prend en argument le return
de ãÑ
creation_4_couples_utilites
1052 s_mm,s_vm,s_mv,s_vv = S[0], S[1], S[2],
S[3]
1053 if premier_joueur == 1 :
1054 joueur = 2
1055 s_1 = comparaison(joueur,s_mv,s_vv)
1056 s_2 = comparaison(joueur,s_mm,s_vm)
1057 s = comparaison(premier_joueur, s_1,
s_2)
1058 else :
1059 joueur = 1
1060 s_1 = comparaison(joueur,s_mv,s_vv)
1061 s_2 = comparaison(joueur,s_mm,s_vm)
1062 s = comparaison(premier_joueur, s_1,
s_2)
1063 return s
1064 # Pour trouver toutes les solutions de
Nash il faut faire tourner la fonction
ãÑ quand J1 joue en premier
1065 # et quand J2 joue en premier, si on
trouve la meme elle est unique, sinon il y
ãÑ a en a deux.
1066
1067 def indice (s,L):
1068 i = 0
1069 while (s != L[i]):
1070 if i >= len(L):
67
1071 break
1072 i+=1
1073 return i
1074
1075 # Fonction très utile permettant
de calculer directement les 4 couples
ãÑ d'utilité du
problème
1076 # en fonction des paramètres de
base
1077 def creation_4_couples_utilites
(joueur,x1,x2,y1,y2,v = 0.5,decimale = ãÑ
2,tolerance = 100) :
1078 if joueur == 1:
1079 s_mm =
J1_et_J2_mentent_decouvert(x1,x2,y1,y2,v,decimale,tolerance)[0]
1080 s_vm =
J1_ment(x1,x2,y1,y2,v,decimale,tolerance)[:2]
1081 s_mv =
J2_ment(x1,x2,y1,y2,v,decimale,tolerance)[:2]
1082 s_vv =
J1_et_J2_verite(x1,x2,y1,y2,v,decimale)[0]
1083 list_sol = [s_mm,s_vm,s_mv,s_vv]
1084 else :
1085 s_mm =
J1_et_J2_mentent_decouvert(x1,x2,y1,y2,v,decimale,tolerance)[1]
1086 s_vm =
J2_ment(x1,x2,y1,y2,v,decimale,tolerance)
1087 s_mv =
J1_ment(x1,x2,y1,y2,v,decimale,tolerance)
1088 s_vv =
J1_et_J2_verite(x1,x2,y1,y2,v,decimale)[0]
1089 list_sol = [s_mm,s_vm,s_mv,s_vv]
1090 return list_sol
1091
1092 ''' Jeu info parfaite, solution de
Nash en fonction du
ãÑ joueur qui joue en premier
'''
1093
1094 def nash_joueur_i_premier_joueur
(joueur,liste):
1095 sol = nash_info_parfaite(joueur,liste)
1096 i = indice(sol,liste) # on prend un
indice pour la fonction print
ãÑ suivante
1097 return [sol,i]
1098 # sol = couple d'utilité
solution 1099 # i = indice de la réponse (0 3)
:
1100 # 0 : mensonge puis mensonge
1101 # 1 : verité puis
mensonge
1102 # 2 : mensonge puis verite
1103 # 3 : verite puis verite
1104
1105 # Un utilise le principe
d'indifference quand une solution mixte existe
1106 # la fonction n'a pas
été utilisée durant le mémoire malheureusement
1107 def solution_mixte_nash (S):
1108 s1 = nash_info_parfaite(1, S)
1109 s2 = nash_info_parfaite(2, S)
1110 if s1 == s2:
1111 return s1
1112 elif s1!=s2 and (abs(indice(s1,S) -
indice(s2,S))%2 != 0):
1113 x = symbols('x')
1114 eq1 = x*S[0][1] + (1-x)*S[1][1] -
(x*S[2][1] + (1-x)*S[3][1])
1115 p = solve(eq1)
68
1116
1117 y = symbols('y')
1118 eq2 = y*S[0][0] + (1-y)*S[2][0] -
(y*S[1][0] + (1-y)*S[3][0])
1119 q = solve(eq2)
1120 return p,q
1121 '''
1122 S =
[[3,2],[2,3],[2,3],[3,2]]
1123 #S =
[[5,3],[2,2],[1,1],[4,6]]
1124 print(solution_mixte_nash(S))
#'''
1125
1126 # fonction "print" affichant la
solution de Nash lorsqu'on a le choix entre 4
ãÑ couples
d'utilité
1127 def print_jeu_decouvert (x1,x2,y1,y2,v =
0.5,decimale = 2):
1128 B=[]
1129 B.append(str("\nQuand J1 est le premier
à jouer, J1 décidera de mentir et
ãÑ J2 également"))
1130 B.append(str("\nQuand J1 est le premier
à jouer, J1 décidera de mentir mais
ãÑ J2 préfèrera dire
la vérité"))
1131 B.append(str("\nQuand J1 est le premier
à jouer, J1 décidera de dire la
ãÑ vérité mais J2
préfèrera mentir"))
1132 B.append(str("\nQuand J1 est le premier
à jouer, J1 décidera de dire
la ãÑ vérité et J2
également"))
1133
1134 B.append(str("\nQuand J2 est le premier
à jouer, J2 décidera de mentir
et ãÑ J1 également"))
1135 B.append(str("\nQuand J2 est le premier
à jouer, J2 décidera de mentir
mais ãÑ J1 préfèrera dire la
vérité"))
1136 B.append(str("\nQuand J2 est le premier
à jouer, J2 décidera de dire
la ãÑ vérité mais J1
préfèrera mentir"))
1137 B.append(str("\nQuand J2 est le premier
à jouer, J2 décidera de dire
la ãÑ vérité et J1
également"))
1138
1139 print(" \n Solution de Nash du jeu
à découvert
ãÑ ")
1140 liste_1 = creation_4_couples_utilites
(1,x1,x2,y1,y2,v,decimale,tolerance)
1141 s_1,i_1 = nash_joueur_i_premier_joueur(1,
liste_1)[:2]
1142 print(B[i_1])
1143 liste_2 = creation_4_couples_utilites
(1,x1,x2,y1,y2,v,decimale,tolerance)
1144 s_2,i_2 = nash_joueur_i_premier_joueur(2,
liste_2)[:2]
1145 print(B[i_2+4])
1146
1147 # fonction pour définir 5 points
aléatoires, on veut éviter d'avoir x1 = y1
et
ãÑ x2 = y2, car
1148 # ils n'ont pas
d'interêt dans le problème et le font planter.
1149 def random_5_points(decimale = 2):
1150 x1 =
randint(0,10**decimale)/10**decimale
1151 x2 =
randint(0,10**decimale)/10**decimale
1152 y1 = x1
1153 y2 = x2
69
1154 v = x1
1155 while (y1 == x1) or (y2 == x2) or (v == x1):
1156 y1 = randint(0,10**decimale)/10**decimale
1157 y2 = randint(0,10**decimale)/10**decimale
1158 v = randint(0,10**decimale)/10**decimale #'''
1159 return x1, x2, y1, y2, v
1160
1161 # fonction servant la partie théorie des jeux
pour compter le nombre de fois ãÑ
qu'un individu ment
1162 def occurrence_type_solution_jeu_decouvert
(taille_echantillon = 100, decimale ãÑ = 2,
tolerance = 100, joueur = 1):
1163 occurrence_J1 = []
1164 for i in range (taille_echantillon):
1165 x1, x2, y1, y2, v = random_5_points(decimale)
1166 liste = creation_4_couples_utilites
ãÑ
(joueur,x1,x2,y1,y2,v,decimale,tolerance)
1167
occurrence_J1.append(nash_joueur_i_premier_joueur(joueur,liste)[1])
1168 return occurrence_J1
1169
1170 # fonction servant la partie statistique du
mémoire, on ne s'intéressera
que ãÑ au premier
élément renvoyé par la fonction
1171 # qui n'est autre qu'une liste de 0 et 1 suivant le fait
que la solution est ãÑ pure ou
mixte
1172 def echantillon_test_stat_solution_pure (m): # taille de
l'échantillon
1173 liste, s_list, s_pure, s_mixte, x1_pure, x2_pure, y1_pure,
y2_pure, v_pure,
ãÑ \
1174 x1_mixte, x2_mixte, y1_mixte, y2_mixte, v_mixte =
ãÑ [],[],[],[],[],[],[],\
1175 [],[],[],[],[],[],[]
1176 for i in range (m):
1177 x1, x2, y1, y2, v = random_5_points(decimale)
1178 s = solution_rapide(x1,x2,y1,y2,v,decimale)
1179 s_list.append(s)
1180 if (s[3][0] == 0.0) or (s[3][0] == 1.0) :
1181 liste.append(1), s_pure.append(s), x1_pure.append(x1), \
1182 x2_pure.append(x2), y1_pure.append(y1),
y2_pure.append(y2),
ãÑ v_pure.append(v)
1183 else:
1184 liste.append(0), s_mixte.append(s), x1_mixte.append(x1),
\
1185 x2_mixte.append(x2), y1_mixte.append(y1),
y2_mixte.append(y2),
ãÑ v_mixte.append(v)
1186 return liste,s_list, s_pure, x1_pure, x2_pure, y1_pure,
y2_pure, v_pure, \
1187 s_mixte, x1_mixte, x2_mixte, y1_mixte, y2_mixte, v_mixte
1188 # 0 : liste de 0 et de 1 correspondant des solutions
mixtes ou pures
1189 # 1 : liste de toutes les solutions : [point solution,
point A, point B, le
ãÑ facteur p]
1190 # 2 : liste des solutions uniquement pures
1191 # 3 - 7 : valeurs des coordonnées quand la
solution est pure 1192 # 8 : liste des solutions uniquement
mixtes
70
1193 # 9 - 13 : valeurs des coordonnées quand la
solution est mixte 1194
1195 def n_echantillon (m,n):
1196 L_liste_pure_mixte = [J
1197 L_s_list = [J
1198 L_s_pure = [J
1199 L_x1_pure = [J
1200 L_x2_pure = [J
1201 L_y1_pure = [J
1202 L_y2_pure = [J
1203 L_v_pure = [J
1204 L_s_mixte = [J
1205 L_x1_mixte = [J
1206 L_x2_mixte = [J
1207 L_y1_mixte = [J
1208 L_y2_mixte = [J
1209 L_v_mixte = [J
1210
1211 for i in range (n):
1212 liste_pure_mixte, s_list, s_pure, x1_pure, x2_pure, y1_pure,
y2_pure, ãÑ v_pure, s_mixte, x1_mixte,
x2_mixte, y1_mixte, y2_mixte, v_mixte = ãÑ
echantillon_test_stat_solution_pure (m)
1213
1214 L_liste_pure_mixte.append(liste_pure_mixte)
1215 L_s_list.append(s_list)
1216 L_s_pure.append(s_pure)
1217 L_x1_pure.append(x1_pure)
1218 L_x2_pure.append(x2_pure)
1219 L_y1_pure.append(y1_pure)
1220 L_y2_pure.append(y2_pure)
1221 L_v_pure.append(v_pure)
1222 L_s_mixte.append(s_mixte)
1223 L_x1_mixte.append(x1_mixte)
1224 L_x2_mixte.append(x2_mixte)
1225 L_y1_mixte.append(y1_mixte)
1226 L_y2_mixte.append(y2_mixte)
1227 L_v_mixte.append(v_mixte)
1228
1229 return L_liste_pure_mixte,L_s_list, L_s_pure, L_x1_pure,
L_x2_pure, \
1230 L_y1_pure, L_y2_pure, L_v_pure, L_s_mixte, L_x1_mixte,
L_x2_mixte, ãÑ L_y1_mixte, \
1231 L_y2_mixte, L_v_mixte
1232 # Nous renvoie 14 listes contenant chacunes les n
sous-listes suivantes :
1233
1234 # 0 : liste de 0 et de 1 correspondant à des
solutions mixtes ou pures
1235 # 1 : liste de toutes les solutions : [point solution,
point A, point B, le
ãÑ facteur p]
1236 # 2 : liste des solutions uniquement pures
1237 # 3 - 7 : valeurs des coordonnées quand la
solution est pure
71
1238
|
#
|
8
|
: liste des solutions uniquement mixtes
|
1239
|
#
|
9
|
- 13 : valeurs des coordonnées quand la solution est
mixte
|
72
8.2.4 Fichier
"Applications_theorie_des_jeux.py"
1240 from random import uniform
1241 from numpy import mean
1242
1243 import Etude_probleme_voiture_partagee
as ev
1244
1245 #%%
1246 ''' Partie 4.5 - Cas simple
n°1
'''
ãÑ
1247
1248 x1, x2, y1, y2, v = 0.02, 0.34, 0.84,
0.71, 0.5
1249 tolerance = 100
1250
1251
1252 s = ev.solution_rapide
(x1,x2,y1,y2,v)
1253
1254 D = ev.coordonnees_utilites(x1, x2, y1,
y2, v)
1255 ev.print_solution_voiture(s, D)
1256 ev.print_solution_jeu_classique
(x1,x2,y1,y2,v)
1257
1258 #%%
1259 ''' Partie 4.5 - Cas simple
n°2
'''
ãÑ
1260
1261 x1, x2, y1, y2, v = 0.05, 0.60, 0.89,
0.91, 0.2
1262 tolerance = 100
1263
1264 #'''
1265 s = ev.solution_rapide
(x1,x2,y1,y2,v)
1266
1267 D = ev.coordonnees_utilites(x1, x2, y1,
y2, v)
1268 ev.print_solution_voiture(s, D)
1269 ev.print_solution_jeu_classique
(x1,x2,y1,y2,v)
1270
1271 #%%
1272 ''' Partie 4.6.1 - infos
parfaites
'''
ãÑ
1273 #'''
1274 x1, x2, y1, y2, v = 0.02, 0.34, 0.84,
0.71, 0.5
1275 decimale, tolerance = 2, 100
1276 a, b = 0, 1
1277
1278
1279 #s =
ãÑ
ev.joueur_ment_y_maximum_dichotomie(1,a,b,x1,x2,y1,y2,v,decimale,tolerance)
1280 #print(s)
1281
#ev.plot_solution_menteur(a,b,x1,x2,y1,y2,v,decimale,tolerance)
1282
73
1283 s = ev.solution_rapide
(x1,x2,y1,y2,v,decimale)
1284
1285 D = ev.coordonnees_utilites(x1, x2, y1,
y2, v, decimale)
1286
1287 ev.print_solution_voiture(s, D)
1288 ev.print_solution_jeu_classique
(x1,x2,y1,y2,v,decimale)
1289
ev.print_jeu_decouvert(x1,x2,y1,y2,v,decimale)
1290 ev.plot_recherche_max_joueur1et2
(x1,x2,y1,y2,v,decimale,tolerance,"Utilité des
ãÑ joueurs en fonction de leur
point d'arrivée",a,b)
1291
ev.print_utilites_jeu_info_parfaite(x1,x2,y1,y2,v,decimale)
#''' 1292 1293 1294 #%%
1295 ''' Partie 4.6.2 - occurrence des
mensonges
'''
ãÑ
1296 #'''
1297 L =
ev.occurrence_type_solution_jeu_decouvert(taille_echantillon = 200, joueur
ãÑ = 1)
1298
1299 print(" Quand le joueur 1 joue en
premier
")
1300 zero1 = L.count(0)
1301 print("Nombre de fois oil les deux
individus mentent : ", zero1)
1302 un1 = L.count(1)
1303 print("Nombre de fois oil le premier ment
et que le second ne ment pas : ", un1)
1304 deux1 = L.count(2)
1305 print("Nombre de fois oil le premier ne
ment pas et que le second ment : ",
ãÑ deux1)
1306 trois1 = L.count(3)
1307 print("Nombre de fois oil les deux disent
la vérité : ", trois1)
1308
1309 L =
ev.occurrence_type_solution_jeu_decouvert(taille_echantillon = 200, joueur
ãÑ = 2)
1310
1311 print(" Quand le joueur 2 joue en
premier
")
1312 zero2 = L.count(0)
1313 print("Nombre de fois oil les deux
individus mentent : ", zero2)
1314 un2 = L.count(1)
1315 print("Nombre de fois oil le premier ment
et que le second ne ment pas : ", un2)
1316 deux2 = L.count(2)
1317 print("Nombre de fois oil le premier ne
ment pas et que le second ment : ",
ãÑ deux2)
1318 trois2 = L.count(3)
1319 print("Nombre de fois oil les deux disent
la vérité : ", trois2) #'''
1320
1321 #%%
1322 ''' Partie 4.6.3 - infos
imparfaites
'''
ãÑ
1323 #'''
1324 m = 300
74
1325 i = 0
1326 decimale, tolerance = 3, 100
1327 a, b = 0, 1
1328
1329 y1_les_deux_mentent = []
1330 y2_les_deux_mentent = []
1331 y1_J1_ment_sachant_J2_ment_List = []
1332 y2_J2_ment_sachant_J1_ment_List = []
1333
1334 for i in range (m):
1335 x1_u, x2_u = uniform(0,0.2),
uniform(0.3,0.35)
1336 x1_v, x2_v = 0.02, 0.34 # correspond
l'endroit où se trouve vraiment le
ãÑ joueur
1337
1338 y1_u, y2_u = uniform(0.7,1.0),
uniform(0.7,1.0)
1339 y1_v, y2_v = 0.84, 0.71 # correspond la
vraie destination du joueur
1340 v = 0.5 1341
1342 # Calcul de
l'approximation de y1 # 1343
1344 J1_et_J2_verite = ev.J1_et_J2_verite
(x1_v,x2_u,y1_v,y2_u,v,decimale)
# ãÑ y1_v correspond au vrai y, y2_u
correspond un y tiré uniformément
1345 J1_ment = ev.J1_ment
(x1_v,x2_u,y1_v,y2_u,v,decimale,tolerance)
1346 J2_ment = ev.J2_ment
(x1_v,x2_u,y1_v,y2_u,v,decimale,tolerance)
1347 J1_et_J2_mentent_ingenument =
ev.J1_et_J2_mentent_ingenument(J1_ment,
ãÑ J2_ment)
1348 J1_et_J2_mentent_decouvert =
ev.J1_et_J2_mentent_decouvert ãÑ
(x1_v,x2_u,y1_v,y2_u,v,decimale,tolerance)
1349
1350 y1_J1_ment_J2_ment =
round(J1_et_J2_mentent_ingenument [2],decimale)
1351 y1_J1_ment_sachant_J2_ment =
round(J1_et_J2_mentent_decouvert
ãÑ [3][0],decimale)
1352
1353
y1_les_deux_mentent.append(y1_J1_ment_J2_ment)
1354
y1_J1_ment_sachant_J2_ment_List.append(y1_J1_ment_sachant_J2_ment)
1355
1356 # Calcul de
l'approximation de y2 # 1357
1358 J1_et_J2_verite = ev.J1_et_J2_verite
(x1_u,x2_v,y1_u,y2_v,v,decimale)
# ãÑ y2_v correspond au vrai y, y1_u
correspond un y tiré uniformément
1359 J1_ment = ev.J1_ment
(x1_u,x2_v,y1_u,y2_v,v,decimale,tolerance)
1360 J2_ment = ev.J2_ment
(x1_u,x2_v,y1_u,y2_v,v,decimale,tolerance)
1361 J1_et_J2_mentent_ingenument =
ev.J1_et_J2_mentent_ingenument(J1_ment,
ãÑ J2_ment)
1362 J1_et_J2_mentent_decouvert =
ev.J1_et_J2_mentent_decouvert ãÑ
(x1_u,x2_v,y1_u,y2_v,v,decimale,tolerance)
1363
1364 y2_J1_ment_J2_ment =
round(J1_et_J2_mentent_ingenument [3],decimale)
1365 y2_J2_ment_sachant_J1_ment =
round(J1_et_J2_mentent_decouvert
75
ãÑ [2][1],decimale)
1366
1367 y2_les_deux_mentent.append(y2_J1_ment_J2_ment)
1368
y2_J2_ment_sachant_J1_ment_List.append(y2_J2_ment_sachant_J1_ment)
#'''
1369 #'''
1370 MOYENNE_y1_les_deux_mentent =
mean(y1_les_deux_mentent)
1371 MOYENNE_y2_les_deux_mentent =
mean(y2_les_deux_mentent)
1372 MOYENNE_y1_J1_ment_sachant_J2_ment_List =
mean(y1_J1_ment_sachant_J2_ment_List)
1373 MOYENNE_y2_J2_ment_sachant_J1_ment_List =
mean(y2_J2_ment_sachant_J1_ment_List)
1374
1375 print("Moyenne des y1 quand J1 ment et que J2 dit la
vérité = ",
ãÑ
round(MOYENNE_y1_les_deux_mentent,3))
1376 print("Moyenne des y2 quand J2 ment et que J1 dit la
vérité = ",
ãÑ
round(MOYENNE_y2_les_deux_mentent,3))
1377 print("Moyenne des y1 quand J1 ment et qu'il sait que J2
ment = ",
ãÑ
round(MOYENNE_y1_J1_ment_sachant_J2_ment_List,3))
1378 print("Moyenne des y2 quand J2 ment et qu'il sait que J1
ment = ",
ãÑ
round(MOYENNE_y2_J2_ment_sachant_J1_ment_List,3)) #'''
1379 #%%
1380 #'''
1381
1382 y_1_app = (1/2)*(MOYENNE_y1_les_deux_mentent +
ãÑ
MOYENNE_y1_J1_ment_sachant_J2_ment_List) 1383 y_2_app =
(1/2)*(MOYENNE_y2_les_deux_mentent +
ãÑ
MOYENNE_y2_J2_ment_sachant_J1_ment_List) 1384 v = 0.5
1385
1386 y1, y2 = 0.84, 0.71
1387 print("On prend donc comme valeur de y1 : ", y_1_app)
1388 print("On prend donc comme valeur de y2 : ", y_2_app)
#'''
1389
1390
1391 #%%
1392 #'''
1393 y_1_app = 0.7323850000000001 1394 y_2_app = 0.671815
1395 v = 0.5 #'''
1396
1397 x1, x2 = 0.02, 0.34 # correspond l'endroit où se
trouve vraiment le joueur
1398 y1, y2 = 0.84, 0.71 # correspond la vraie destination du
joueur
1399
1400 # Solution du jeu info imparfaite #
1401
1402 VV = ev.solution_rapide(x1,x2,y1,y2,v = 0.5,decimale = 2)
1403 VM = ev.solution_rapide(x1,x2,y1,y_2_app,v = 0.5,decimale =
2)
1404 MV = ev.solution_rapide(x1,x2,y_1_app,y2,v = 0.5,decimale =
2)
1405 MM = ev.solution_rapide(x2,x2,y_1_app,y_2_app,v =
0.5,decimale = 2)
1406
76
1407
1408 print("\n Solution du jeu à info imparfaite
ãÑ \n")
1409
1410 print("\n Quand les deux joueurs disent
la vérité : \n")
1411 print("J1 obtient une utilité de :", VV[0][0])
1412 print("J2 obtient une utilité de :", VV[0][1])
1413
1414 print("\n Quand J1 dit la vérité et que J2
ment : \n")
1415 print("J1 obtient une utilité de :", VM[0][0])
1416 print("J2 obtient une utilité de :", VM[0][1])
1417
1418 print("\n Quand J2 dit la vérité et que J1
ment : \n")
1419 print("J1 obtient une utilité de :", MV[0][0])
1420 print("J2 obtient une utilité de :", MV[0][1])
1421
1422 print("\n Quand les deux joueurs mentent
: \n")
1423 print("J1 obtient une utilité de :", MM[0][0])
1424 print("J2 obtient une utilité de :", MM[0][1])
1425
1426 #print(ev.solution_mixte_nash
([VV[0],VM[0],MV[0],MM[0]])) #'''
1427
1428 #%%
1429 a = 0
1430 b = 1
1431 v = 0.5
1432 zonehab11 = 0
1433 zonehab12 = 0.1
1434 zonehab21 = 0.9
1435 zonehab22 = 1
1436 zone1 = [zonehab11,zonehab12]
1437 zone2 = [zonehab21,zonehab22]
1438
1439 p_zone1 = 0.3
1440 p_zone2 = 1-p_zone1
1441
1442 zoneind1 = 0.5
1443 zoneind2 = 0.6
1444 zoneindustielle = [zoneind1,zoneind2]
1445
1446 x_zone1_moyen, x_zone2_moyen = mean(zone1),
mean(zone2)
1447 y_moyen = mean(zoneindustielle)
1448
1449
1450 ''' Première étude '''
1451
1452 ''' Un a ici 16 couples
d'utilités à trouver, il faut distinguer les cas
en
ãÑ fonction
77
1453 de la zone où se trouve le
joueur, il faut également penser que les endroits où
ãÑ ils
1454 décident de mentir dépend
de là où ils se trouvent (ex: si J1 est dans la zone
ãÑ 1,
l'endroit
1455 de son mensonge sera choisi en
considérant que J2 est dans la zone opposée, ie.
ãÑ la zone 2 '''
1456
1457 y1,y2 = y_moyen, y_moyen
1458
1459 ''' '''
1460 ''' J1 zone 1 - J2 zone 1 = K1
'''
1461 ''' '''
1462 x1 = x_zone1_moyen 1463 x2
= x_zone1_moyen
1464 ''' Aucun joueur ne ment
'''
1465
1466 solution_verite_K1 = ev.solution_rapide
(x1,x2,y1,y2,v) 1467 u1_verite_K1 = solution_verite_K1[0][0]
1468 u2_verite_K1 = solution_verite_K1[0][1]
1469
1470 ''' J1 ment, J2 vérité
''' 1471 y1_J1ment_J2zone2 =
ev.y_max_joueur_quand_il_ment
ãÑ
(1,a,b,x1,x_zone2_moyen,y1,y2,v)[0]
1472
1473 solution_J1ment_J2verite_K1 =
ev.solution_rapide (x1,x2,y1_J1ment_J2zone2,y2,v)
1474 u1_J1ment_J2verite_K1 =
solution_J1ment_J2verite_K1[0][0]
1475 u2_J1ment_J2verite_K1 =
solution_J1ment_J2verite_K1[0][1]
1476
1477 ''' J1 vérité, J2 ment
''' 1478 y2_J2ment_J1zone2 =
ev.y_max_joueur_quand_il_ment ãÑ
(2,a,b,x_zone2_moyen,x2,y1,y2,v)[0]
1479
1480 solution_J2ment_J1verite_K1 =
ev.solution_rapide (x1,x2,y1,y2_J2ment_J1zone2,v) 1481
u1_J2ment_J1verite_K1 = solution_J2ment_J1verite_K1[0][0] 1482
u2_J2ment_J1verite_K1 = solution_J2ment_J1verite_K1[0][1]
1483
1484 ''' J1 ment, J2 ment '''
1485
1486 solution_J1ment_J2ment_K1 =
ev.solution_rapide
ãÑ
(x1,x2,y1_J1ment_J2zone2,y2_J2ment_J1zone2,v)
1487 u1_J1ment_J2ment_K1 =
solution_J1ment_J2ment_K1[0][0]
1488 u2_J1ment_J2ment_K1 =
solution_J1ment_J2ment_K1[0][1]
1489 print ("\n ") 1490
print ("Quand les joueurs se situe dans la même
zone 1")
1491 print (" ") 1492 print ("\nSi
les deux joueurs décident de dire la vérité")
1493 print ("J1 aura une utilité de :", u1_verite_K1)
1494 print ("J2 aura une utilité de :", u2_verite_K1)
1495 print ("\nSi J1 décide de mentir et J2 dire la
vérité")
78
1496 print ("J1 aura une utilité de :",
u1_J1ment_J2verite_K1) 1497 print ("J2 aura une utilité
de :", u2_J1ment_J2verite_K1) 1498 print ("\nSi J1
décide de dire la vérité et J2 mentir")
1499 print ("J1 aura une utilité de :",
u1_J2ment_J1verite_K1) 1500 print ("J2 aura une utilité
de :", u2_J2ment_J1verite_K1) 1501 print ("\nSi les deux
joueurs décident de mentir") 1502 print ("J1
aura une utilité de :", u1_J1ment_J2ment_K1) 1503 print
("J2 aura une utilité de :", u2_J1ment_J2ment_K1)
1504
1505 ''' '''
1506 ''' J1 zone 1 - J2 zone 2 =
K2 '''
1507 ''' '''
1508 x1 = x_zone1_moyen 1509 x2
= x_zone2_moyen
1510 ''' Aucun joueur ne ment
'''
1511
1512 solution_verite_K2 = ev.solution_rapide
(x1,x2,y1,y2,v) 1513 u1_verite_K2 = solution_verite_K2[0][0]
1514 u2_verite_K2 = solution_verite_K2[0][1]
1515
1516 ''' J1 ment, J2 vérité
''' 1517 y1_J1ment_J2zone2 =
ev.y_max_joueur_quand_il_ment
ãÑ
(1,a,b,x1,x_zone2_moyen,y1,y2,v)[0]
1518
1519 solution_J1ment_J2verite_K2 =
ev.solution_rapide (x1,x2,y1_J1ment_J2zone2,y2,v)
1520 u1_J1ment_J2verite_K2 =
solution_J1ment_J2verite_K2[0][0]
1521 u2_J1ment_J2verite_K2 =
solution_J1ment_J2verite_K2[0][1]
1522
1523 ''' J1 vérité,
J2 ment ''' 1524 y2_J2ment_J1zone1
= ev.y_max_joueur_quand_il_ment ãÑ
(2,a,b,x_zone1_moyen,x2,y1,y2,v)[0]
1525
1526 solution_J2ment_J1verite_K2 =
ev.solution_rapide (x1,x2,y1,y2_J2ment_J1zone1,v) 1527
u1_J2ment_J1verite_K2 = solution_J2ment_J1verite_K2[0][0] 1528
u2_J2ment_J1verite_K2 = solution_J2ment_J1verite_K2[0][1]
1529
1530 ''' J1 ment, J2 ment
'''
1531
1532 solution_J1ment_J2ment_K2 =
ev.solution_rapide
ãÑ
(x1,x2,y1_J1ment_J2zone2,y2_J2ment_J1zone1,v) 1533
u1_J1ment_J2ment_K2 = solution_J1ment_J2ment_K2[0][0] 1534
u2_J1ment_J2ment_K2 = solution_J1ment_J2ment_K2[0][1]
1535
1536 print ("\n ")
1537 print ("Quand le joueur 1 se trouve
dans la zone 1 et le joueur 2 dans la zone
ãÑ 2")
1538 print (" ")
1539 print ("\nSi les deux joueurs
décident de dire la vérité") 1540 print
("J1 aura une utilité de :", u1_verite_K2)
79
1541 print ("J2 aura une utilité de :",
u2_verite_K2)
1542 print ("\nSi J1 décide de mentir et
J2 dire la vérité") 1543 print ("J1 aura une
utilité de :", u1_J1ment_J2verite_K2) 1544 print ("J2
aura une utilité de :", u2_J1ment_J2verite_K2) 1545 print ("\nSi
J1 décide de dire la vérité et J2 mentir")
1546 print ("J1 aura une utilité de :",
u1_J2ment_J1verite_K2) 1547 print ("J2 aura une utilité
de :", u2_J2ment_J1verite_K2) 1548 print ("\nSi les deux
joueurs décident de mentir") 1549 print ("J1
aura une utilité de :", u1_J1ment_J2ment_K2) 1550 print
("J2 aura une utilité de :", u2_J1ment_J2ment_K2)
1551
1552 ''' '''
1553 ''' J1 zone 2 - J2 zone 1
= K3 '''
1554 ''' '''
1555 x1 = x_zone2_moyen 1556 x2
= x_zone1_moyen
1557 ''' Aucun joueur ne ment
'''
1558
1559 solution_verite_K3 = ev.solution_rapide
(x1,x2,y1,y2,v) 1560 u1_verite_K3 = solution_verite_K3[0][0]
1561 u2_verite_K3 = solution_verite_K3[0][1]
1562
1563 ''' J1 ment, J2 vérité
''' 1564 y1_J1ment_J2zone1 =
ev.y_max_joueur_quand_il_ment
ãÑ
(1,a,b,x1,x_zone1_moyen,y1,y2,v)[0]
1565
1566 solution_J1ment_J2verite_K3 =
ev.solution_rapide (x1,x2,y1_J1ment_J2zone1,y2,v)
1567 u1_J1ment_J2verite_K3 =
solution_J1ment_J2verite_K3[0][0]
1568 u2_J1ment_J2verite_K3 =
solution_J1ment_J2verite_K3[0][1]
1569
1570 ''' J1 vérité,
J2 ment ''' 1571 y2_J2ment_J1zone2
= ev.y_max_joueur_quand_il_ment ãÑ
(2,a,b,x_zone2_moyen,x2,y1,y2,v)[0]
1572
1573 solution_J2ment_J1verite_K3 =
ev.solution_rapide (x1,x2,y1,y2_J2ment_J1zone2,v) 1574
u1_J2ment_J1verite_K3 = solution_J2ment_J1verite_K3[0][0] 1575
u2_J2ment_J1verite_K3 = solution_J2ment_J1verite_K3[0][1]
1576
1577 ''' J1 ment, J2 ment
'''
1578
1579 solution_J1ment_J2ment_K3 =
ev.solution_rapide
ãÑ
(x1,x2,y1_J1ment_J2zone1,y2_J2ment_J1zone2,v) 1580
u1_J1ment_J2ment_K3 = solution_J1ment_J2ment_K3[0][0] 1581
u2_J1ment_J2ment_K3 = solution_J1ment_J2ment_K3[0][1]
1582
1583 print ("\n ")
1584 print ("Quand le joueur 1 se trouve dans la
zone 2 et le joueur 2 dans la zone
ãÑ 1")
1585 print (" ")
80
1586 print ("\nSi les deux joueurs
décident de dire la vérité") 1587 print
("J1 aura une utilité de :", u1_verite_K3)
1588 print ("J2 aura une utilité de :",
u2_verite_K3)
1589 print ("\nSi J1 décide de mentir et
J2 dire la vérité") 1590 print ("J1 aura une
utilité de :", u1_J1ment_J2verite_K3) 1591 print ("J2
aura une utilité de :", u2_J1ment_J2verite_K3) 1592 print ("\nSi
J1 décide de dire la vérité et J2 mentir")
1593 print ("J1 aura une utilité de :",
u1_J2ment_J1verite_K3) 1594 print ("J2 aura une utilité
de :", u2_J2ment_J1verite_K3) 1595 print ("\nSi les deux
joueurs décident de mentir") 1596 print ("J1 aura une
utilité de :", u1_J1ment_J2ment_K3) 1597 print ("J2
aura une utilité de :", u2_J1ment_J2ment_K3)
1598
1599 ''' '''
1600 ''' J1 zone 2 - J2 zone 2
= K4 '''
1601 ''' '''
1602 x1 = x_zone2_moyen 1603 x2
= x_zone2_moyen
1604 ''' Aucun joueur ne ment
'''
1605
1606 solution_verite_K4 = ev.solution_rapide
(x1,x2,y1,y2,v) 1607 u1_verite_K4 = solution_verite_K4[0][0]
1608 u2_verite_K4 = solution_verite_K4[0][1]
1609
1610 ''' J1 ment, J2 vérité
''' 1611 y1_J1ment_J2zone1 =
ev.y_max_joueur_quand_il_ment
ãÑ
(1,a,b,x1,x_zone1_moyen,y1,y2,v)[0]
1612
1613 solution_J1ment_J2verite_K4 =
ev.solution_rapide (x1,x2,y1_J1ment_J2zone1,y2,v)
1614 u1_J1ment_J2verite_K4 =
solution_J1ment_J2verite_K4[0][0]
1615 u2_J1ment_J2verite_K4 =
solution_J1ment_J2verite_K4[0][1]
1616
1617 ''' J1 vérité,
J2 ment ''' 1618 y2_J2ment_J1zone1
= ev.y_max_joueur_quand_il_ment ãÑ
(2,a,b,x_zone1_moyen,x2,y1,y2,v)[0]
1619
1620 solution_J2ment_J1verite_K4 =
ev.solution_rapide (x1,x2,y1,y2_J2ment_J1zone1,v) 1621
u1_J2ment_J1verite_K4 = solution_J2ment_J1verite_K4[0][0] 1622
u2_J2ment_J1verite_K4 = solution_J2ment_J1verite_K4[0][1]
1623
1624 ''' J1 ment, J2 ment
'''
1625
1626 solution_J1ment_J2ment_K4 =
ev.solution_rapide
ãÑ
(x1,x2,y1_J1ment_J2zone1,y2_J2ment_J1zone1,v) 1627
u1_J1ment_J2ment_K4 = solution_J1ment_J2ment_K4[0][0] 1628
u2_J1ment_J2ment_K4 = solution_J1ment_J2ment_K4[0][1]
1629
1630 print ("\n ")
1631 print ("Quand les joueurs se situe dans la
même zone 2")
81
1632 1633 1634 1635
|
print print print
|
print
(" ") ("\nSi les deux joueurs décident de dire la
vérité")
("J1 aura une utilité de :", u1_verite_K4)
("J2 aura une utilité de :", u2_verite_K4)
|
1636
|
print
|
("\nSi J1 décide de mentir et J2 dire la
vérité")
|
1637
|
print
|
("J1 aura une utilité de :",
|
u1_J1ment_J2verite_K4)
|
1638
|
print
|
("J2 aura une utilité de :",
|
u2_J1ment_J2verite_K4)
|
1639
|
print
|
("\nSi J1 décide de dire la vérité et J2
mentir")
|
1640
|
print
|
("J1 aura une utilité de :",
|
u1_J2ment_J1verite_K4)
|
1641
|
print
|
("J2 aura une utilité de :",
|
u2_J2ment_J1verite_K4)
|
1642
|
print
|
("\nSi les deux joueurs décident de mentir")
|
1643
|
print
|
("J1 aura une utilité de :",
|
u1_J1ment_J2ment_K4)
|
1644
|
print
|
("J2 aura une utilité de :",
|
u2_J1ment_J2ment_K4)
|
82
8.2.5 Fichier
"Applications_statistiques.py"
1645 from numpy import zeros
1646 from matplotlib import pyplot as plt
1647 from scipy.stats import binom, t
1648 from math import sqrt
1649
1650 import Etude_probleme_voiture_partagee
as ev
1651
1652 #%%
1653 n = 100
1654
1655 def list_to_array(L):
1656 n = len(L)
1657 X = zeros(n)
1658 for i in range (n):
X[i]=L[i]
1659
1660 return X
1661
1662 liste =
ev.echantillon_test_stat_solution_pure (n)[0]
1663
1664 X_sample = list_to_array(liste)
1665 #%%
1666 p=1/2
1667
1668 stat_test_mediane = sum(X_sample)
1669
1670 moyenne_empirique =
(1/n)*sum(X_sample)
1671
1672 variance_empirique =
(1/(n-1))*sum((X_sample-moyenne_empirique)**2)
1673
1674 quantile_p_valeur =
(sqrt(n)/variance_empirique)*(moyenne_empirique-0.90)
1675
1676 p_valeur_mediane =
binom.cdf(stat_test_mediane,n,p)
1677 p_valeur_student =
t.cdf(quantile_p_valeur,n-1)
1678
1679 print("stat_test_mediane =
",stat_test_mediane)
1680 print("stat_test_mediane =
",moyenne_empirique)
1681
1682 print("p_valeur_mediane =
",p_valeur_mediane)
1683 print("p_valeur_student =
",p_valeur_student)
1684
1685 #%%
1686
1687 def m_p_valeur (n,m):
1688 p_mediane = [] # on rentre les
p-valeurs du test 1 de la médiane
1689 p_student = [] # on rentre les
p-valeurs du test 2 de Student
1690 moyenne = [] # on rentre les valeurs
des moyennes
1691 save_nb_solutions_mixtes = [] # sert
étudier les moyennes quand
les ãÑ p-valeurs sont
inférieures un seuil choisi
83
1692
1693 for i in range (m):
1694 liste =
ev.echantillon_test_stat_solution_pure (n)[0]
1695
1696 X_sample = list_to_array(liste)
1697 stat_test_mediane = sum(X_sample)
1698
1699 moyenne_empirique =
(1/n)*stat_test_mediane
1700 moyenne.append(moyenne_empirique)
1701
1702 variance_empirique =
(1/(n-1))*sum((X_sample-moyenne_empirique)**2)
1703
1704 quantile_p_valeur =
ãÑ
(sqrt(n)/variance_empirique)*(moyenne_empirique-0.90)
1705 p = 1/2
1706 p_valeur_mediane =
binom.cdf(stat_test_mediane,n,p)
1707 p_valeur_student =
t.cdf(quantile_p_valeur,n-1)
1708 if p_valeur_student < 0.8:
1709
ãÑ
save_nb_solutions_mixtes.append([p_valeur_student,moyenne_empirique])
1710 p_mediane.append(p_valeur_mediane)
1711 p_student.append(p_valeur_student)
1712
1713 return p_mediane, p_student, moyenne,
save_nb_solutions_mixtes
1714 n, m = 100, 100
1715 p_mediane, p_student, moyenne,
etude_p_valeur = m_p_valeur(n,m)
1716
1717
1718 plt.figure()
1719 plt.hist(p_mediane, edgecolor = "black",
color = "white")
1720 plt.title("Histogramme de " + str(n) + "
p-valeurs correspondant au test de la
ãÑ médiane")
1721
1722 plt.figure()
1723 plt.hist(p_student, edgecolor = "magenta",
color = "white")
1724 plt.title("Histogramme de " + str(n) + "
p-valeurs correspondant au test de
ãÑ Student")
1725
1726 plt.figure()
1727 plt.hist(moyenne, edgecolor = "darkred",
color = "white")
1728 plt.title("Histogramme de " + str(n) + "
moyennes")
|