Définition de l’équilibre de Nash

Projet, rapport de stage, et mémoire de fin d’études APPLICATION DE LA THEORIE DES JEUX DE PARTAGE DES RESSOURCE D’UN RÉSEAU DE FILE D’ATTENTE en PDF

Définition de l’équilibre de Nash

On suppose l’existence d’une sorte de norme sociale pour chaque interaction stratégique. Alors pour être effectivement stable, cette norme doit au moins satisfaire à ce critère : Aucun joueur n’a intérêt à dévier individuellement du comportement dicté par la norme, sinon la norme pourrait être violée puisqu’il existe au moins un individu qui, anticipant que tout le reste de la société va suivre la norme, lui a intérêt à la violer. 

Exemple : On a posé une norme : Tout conducteur doit rouler à droite. Aucun conducteur n’aura donc intérêt à rouler à gauche si tout le monde roule à droite. L’équilibre de Nash est une traduction mathématique de cette notion de stabilité. Définition 1.26 Un profil de stratégie 4∗= (4∗ )∈ˆ ∈e est un équilibre de Nash du jeu sous forme stratégique M si et seulement si : ∀ ∈\, ∀4 ∈e ∶ (4∗,4*∗)≥(4,4*∗)  . Ainsi, comme si les joueurs de mettent d’accord sur un profil à jouer, alors ce profil est un équilibre de Nash : sinon, au moins un joueur aura intérêt à changer individuellement sa stratégie, et donc à ne pas respecter l’accord établi avec les autres joueurs.

En d’autre terme, l’équilibre de Nash est un profil de stratégies pour lequel il n’existe pas de déviation profitable pour tous les joueurs. C’est donc un point tel que, si tous les joueurs savent qu’on va jouer un tel profil de stratégie, alors chacun a effectivement intérêt à le jouer. C’est pourquoi cette notion d’équilibre a un rôle important.

Un des problèmes importants de la recherche actuelle est de trouver par quel méthode où procéder et sous quelles conditions, les comportements des joueurs convergent vers un équilibre de Nash, et sinon, vers quoi il y a convergence.

Problème de marchandage

Un problème de marchandage est défini par un couple (=,) où ∈= et = un sous-ensemble de ℝ satisfaisant les propriétés suivantes : [1.12] [1.13] – = est convexe et fermé – = est borné supérieurement : ∃;̅ ∈ℝtel que ;<;̅ pour tout ; de = – est dominé au sens de Pareto : ∃;∈= tel que ;> pour tout de 1 à & = est non vide car il contient au moins le point de désaccord (ou le statu quo). La convexité de = reflète le fait que l’ensemble des alternatives est un continu et que les joueurs n’ont pas un penchant pour le risque. = borné garantit un limite sur le gain des joueurs, et la domination au sens de Pareto invoque qu’un gain potentiel existe vraiment. L’ensemble de tous les problèmes de marchandage (=,) vérifiant ces exigences sera noté par ℬ.

Ensemble de marchandage

Définition 1.46 Un ensemble de marchandage consiste en tout point de =, individuellement rationnel et Paretoefficient.

La raison pour laquelle Von Neumann et Morgenstern ont suggéré que des joueurs rationnels ne signeront pas un contrat qui n’est pas individuellement rationnel est bien évidente. Plutôt que de signer un tel accord, au moins un des joueurs préférerait ne pas être du même avis et empocher en conséquence le gain de désaccord.

La raison pour laquelle ils excluraient des contrats qui ne seraient pas Pareto-efficients est à peine légèrement moins évidente. Soit un point @ qui n’est pas Pareto-efficient. Dans ce cas, ; représente une amélioration réalisable par rapport à @, et si on proposait un contrat procurant le résultat @, au moins un des joueurs aurait une incitation à proposer un contrat procurant le résultat; et l’autre n’aurait aucune objection rationnelle à formuler. La Figure 1.03 fait voir les ensembles de marchandages pour les ensembles =,k et l de la Figure 1.02 dans le cas où le point de désaccord est =(1,0).

Solution de Nash à un problème de marchandage

John Nash a soutenu qu’on pouvait dire davantage sur le couple de gains, objet d’accord de deux joueurs rationnels, que la simple affirmation qu’il doit se trouver dans l’ensemble de marchandage. Il a donné une liste d’axiomes que ce couple devrait satisfaire dans le cas d’un problème de marchandage et prouvé alors qu’un seul couple de gains obéit aux axiomes. Ce couple est qualifié de solution de marchandage de Nash au problème.

Table des matières

REMERCIEMENTS
NOTATIONS
TABLE DES MATIERES
INTRODUCTION ET POSITION DU PROBLEME
CHAPITRE 1. LA THEORIE DES JEUX ET LA THEORIE DES MARCHANDAGES
1.1 Introduction à la théorie des jeux
1.2 Notion de convexité
1.2.1 Combinaisons convexes
1.2.2 Ensemble convexe
1.2.3 Hyperplan d’appui
1.2.4 Fonction concave et fonction convexe
1.3 Jeu stratégique
1.3.1 Description
1.3.2 Typologie
1.3.3 Jeu sous forme stratégique
1.4 Concepts de solution d’un jeu sous forme stratégique
1.4.1 Optimum de Pareto
1.4.2 Elimination répétée des stratégies dominées
1.4.3 Equilibre de Nash
1.4.4 Comportement prudent
1.5 Jeu en stratégie mixte
1.5.1 Equilibre de Nash en stratégie mixte
1.5.2 Ensemble infini de stratégies
1.6 Zone des gains coopératifs
1.6.1 Définition
1.6.2 Exemple illustratif
1.6.3 Gain transférable
1.7 Ensemble de marchandage
1.7.1 Efficience au sens de Pareto
1.7.2 Rationalité individuelle
1.7.3 Ensemble de marchandage
1.8 Solution de Nash à un problème de marchandage
1.8.2 Problème de marchandage
1.8.3 Solution de marchandage
1.8.4 Axiomes de Nash
1.8.5 Produit de Nash
1.9 Conclusion
CHAPITRE 2. ETAT DE L’ART SUR LE RESEAU DE FILES D’ATTENTE A
RESSOURCE PARTAGEE ET L’INSENSIBILITE
2.1 Introduction
2.2 Chaînes de Markov en temps discret
2.2.1 Définition d’une chaîne de Markov
2.2.2 Mesure de probabilité invariante
2.3 Chaîne de Markov en temps continu
2.3.1 Distribution exponentielle
2.3.2 Processus de Markov
2.3.3 Equation de Chapman-Kolmogorov
2.3.4 Générateur infinitésimal
2.3.5 Distribution stationnaire
2.4 Eléments de théorie des files d’attente
2.4.1 Définition d’une file d’attente
2.4.2 File M/M/1
2.5 Réseaux de files d’attente
2.5.1 Réseaux de Jackson
2.5.2 Réseaux de Whittle
2.6 Insensibilité dans les réseaux de file d’attente
2.7 Réseaux de files Processor Sharing
2.7.1 File Processor Sharing
2.7.2 Réseaux de files Processor Sharing
2.8 Insensibilité de la discipline PS
2.9 Réseau de Whittle et la discipline PS
2.9.1 Insensibilité des réseaux de Whittle à discipline PS
2.9.2 Réseaux de files PS et réseaux de Whittle
2.10 Performances du réseau de files PS : 2.10.2 Temps de séjour moyen à un nœud ¢
2.10.3 Temps de séjour moyen à un ensemble de nœuds
2.10.4 Temps de séjour conditionnel
2.11 Conclusion
CHAPITRE 3. PARTAGE DE RESSOURCES AU MARCHANDAGE D’UN RESEAU DE
FILES D’ATTENTE
3.1 Introduction
3.2 File d’attente selon le marchandage de Nash
3.2.1 Présentation du modèle et formulation du jeu
3.2.2 Solution du problème de marchandage
3.2.3 Equilibre et insensibilité
3.2.4 Distribution stationnaire et les performances du système
3.3 Limite de la solution de Nash et la solution égalitarisme
3.3.1 Solution axiomatique de Nash .
3.3.2 Limite de la solution axiomatique de Nash
3.3.3 Solution égalitarisme
3.3.4 Proposition de solution algorithmique
3.4 Réseau de files d’attente au marchandage
3.4.1 Présentation du modèle et formulation du jeu
3.4.2 Résolution algorithmique
3.5 Conclusion
CHAPITRE 4. PARTAGE DYNAMIQUE A PARTIR D’UN JEU STOCHASTIQUE
REPETE 5
4.1 Introduction
4.2 Autre aspect du jeu de marchandage
4.2.1 Rappel sur le jeu de marchandage
4.2.2 Notion de paiements
4.2.3 Fonction gain et équilibre du jeu
4.3 Jeu répété
4.3.1 Définitions
4.3.2 Jeu répété escompté
4.4 Jeu stochastique
4.4.1 Définitions
4.4.2 Politiques et stratégies locales
4.4.3 Equilibre dans un jeu stochastique
4.5 Modélisation des clients et du réseau de files d’attente
4.5.1 Principe de notre modèle
4.5.2 Formulation du jeu
4.5.3 Marchandage de la ressource du serveur
4.5.4 Etude du jeu stochastique du joueur
4.5.5 Performances du modèle
4.6 Résolution algorithmique du problème .
4.6.1 Algorithme du jeu stochastique du côté des joueurs
4.6.2 Algorithme du jeu de marchandage du côté du serveur de chaque file d’attente
4.7 Conclusion
CHAPITRE 5. APPLICATIONS AUX RESEAUX DE FILES D’ATTENTE DE PAQUETS.
COMPARAISON DES MODELES ETABLIS AUX MODELES CLASSIQUES
5.1 Introduction
5.2 Présentation de l’outil de simulation RIVERBED Modeler
5.2.1 RIVERBED Modeler
5.2.2 Conception d’un réseau sous RIVERBED
5.2.3 Comportement des procédures
5.2.4 Collectes et présentations des résultats
5.3 Modélisation sous RIVERBED Modeler
5.3.1 Clients et files d’attente
5.3.2 Modèle classique FIFO
5.3.3 Modélisation du partage de ressources
5.4 Résultats des simulations pour le cas d’une seule file d’attente
5.4.1 Présentation de la simulation
5.4.2 Etude d’une file d’attente stable
5.4.3 Etude d’une file d’attente instable
5.4.4 Impact de la capacité du serveur de la file d’attente
5.5 Résultats de la simulation pour le cas d’un réseau de files d’attente
5.5.1 Présentation de la simulation
5.5.2 Comparaison des performances des deux réseaux
5.6 Conclusion
CONCLUSION GENERALE
ANNEXES
BIBLIOGRAPHIE
FICHE DE RENSEIGNEMENTS

Télécharger le rapport complet