Optimisation et Compétition

Evripidis Bampis

Universite d’Evry

Nous allons considérer des problèmes d’optimisation en présence d’agents en compétition. Chaque agent possèdera une fonction objectif individuelle et adoptera une stratégie optimisant sa propre fonction objectif au détriment parfois de l’optimum global (social). Dans un tel contexte, des notions et des outils de la théorie des jeux sont utilisés ou enrichis et motivent des nouvelles variantes de certains problèmes d’optimisation classiques.

Nous allons présenter quelques exemples où optimisation et compétition offrent de telles variantes intéressantes, notamment autour des notions de l’équilibre, de la véracité ou des enchères.

Vous avez donc un problème NP-complet et vous voulez quand même produire une solution avec certaines bonnes propriétés. Une direction est de trouver un minimum local, pour une certaine notion de voisinage fixée. Se posent alors les questions de la qualité de ces minima locaux, de leur existence et de la complexité pour en trouver. Nous allons tenter de répondre à ces questions pour les jeux d’ordonnancement, où l’objectif est de minimiser la charge maximale d’un groupe de machines ou d’une collection de liaisons réseau.

Propriétés et apprentissages d’équilibres

Corinne Touati

Laboratoire d’Informatique de Grenoble

Nous considérons un scénario (jeu) dans lequel chaque agent (joueur) possède un ensemble fini de choix ou d’actions (stratégies) possibles. La valeur de la fonction objectif (utilité) de chaque agent dépend non seulement de l’action qu’il a choisie mais également de l’ensemble des autres agents ayant fait le même choix. Un tel jeu est appelé "jeu d’allocation". En utilisant les outils de la théorie des jeux, nous montrons deux résultats complémentaires. Tout d’abord, dans le cas général, des individus rationnels, c’est-à-dire cherchant à optimiser leur propre fonction objectif, agiront au détriment de l’optimum global. Nous montrerons que en révélant aux agents des valeurs modifiées de leur fonction objectif, on peut sous certaines conditions faire coïncider leur optimum individuel (pour les valeurs modifiées) et optimum global (pour les vraies valeurs des objectifs). Nous montrerons également un mécanisme simple d’apprentissage des équilibres, c’est-à-dire un algorithme distribué implanté dans chaque agent qui converge vers l’optimum individuel. Cet algorithme est basé sur des techniques d’approximation stochastique.

Transit price negotiation : Decentralized learning of optimal strategies with incomplete information

Chahinez Hamlaoui

PRISM universite de Versailles

We present a distributed learning algorithm for optimizing transit prices in the inter-domain routing framework. We present a combined game theoretical and distributed algorithmic analysis, where the notion of Nash equilibrium with the first approach meets the notion of stability in the second. We show that providers can learn how to strategically set their prices according to a Nash equilibrium ; even when assuming incomplete information. We validate our theoretical model by simulations confirming the expected outcome. Moreover, we observe that some unilateral deviations from the proposed rule do not seem to affect the dynamic of the system.

La coupe maximum : un jeu tranchant pour les équilibres forts !

Jerome Monnot

LAMSADE, CNRS Université Paris Dauphine

(travail effectué en collaboration avec Laurent Gourvès)

Dans cet exposé, on traite d’un jeu stratégique défini à partir du problème MAX CUT. MAX CUT consiste à partitioner l’ensemble des sommets d’un graphe simple en deux afin de maximiser le nombre d’arêtes ayant une extrémité dans chaque partie. Pour le jeu, chaque joueur est un sommet qui choisit sa partie en cherchant à maximiser les arêtes de la coupe qui lui sont incidentes. Un équilibre de Nash existe toujours pour ce jeu et dans le pire cas la coupe induite est la moitié de la coupe optimale. Le concept d’équilibre fort est une restriction de l’équilibre de Nash pour lequel aucun sous groupe de joueurs ne dévier et tous les membres du sous groupe y gagnent. On montre qu’un équilibre fort existe toujours et qu’il induit une coupe au moins égale aux 2/3 de la coupe optimale. Cependant, dans le pire des cas, il faut considérer des coalitions de taille au moins racine carrée du nombre de joueurs pour espérer améliorer la coupe induite.