Keywords:

sera incluse dans Vangelis Th. Paschos (ed.), Optimisation combinatoire

Dans cet article, nous nous focalisons sur les aspects algorithmiques de la théorie des jeux noncoopératifs. Pour la présentation des notions de base ainsi que pour la notation, nous suivons en général l'exposé de [START_REF] Vorobiev | Mathematical foundations of game theory[END_REF]. Ne sont pas traités ici les problèmes « inverses », c'est-à-dire la conception de mécanismes et la théorie des enchères : cette catégorie constitue un sujet très vaste en soi avec une problématique algorithmique qui lui est propre, dépassant la portée de l'article. Définition 1. Soit I un ensemble, {X i } i∈I un système d'ensembles indexé par I et {R i } i∈I un système de relations binaires R i ⊆ i∈I X i × i∈I X i . On appelle le triplet :

Γ = I, {X i } i∈I , {R i } i∈I (1)
un jeu non-coopératif des joueurs I avec ensemble de stratégies X i et relation de préférence R i pour tout joueur i ∈ I. La relation

P i = R i \ R -1 i
est appelée relation de préférence stricte du joueur i. Les éléments d'un ensemble de stratégies X i sont appelés les choix de i dans le jeu Γ et les combinaisons des choix x ∈ X = i∈I X i sont appelées les situations de Γ. Dans ce qui suit, nous considérons des jeux non-coopératifs d'un nombre fini de joueurs, chacun d'entre eux disposant d'un ensemble fini de stratégies.

Souvent, les relations de préférence R i dans la définition 1 sont représentées par des fonctions de rémunération H i : X -→ R, telles que : xR i y ⇔ H i (x) H i (y). Dans ce cas, un jeu Γ sera spécifié par son ensemble de joueurs I, les stratégies X i de chaque joueur et leurs fonctions de rémunération H i :

Γ = I, {X i } i∈I , {H i } i∈I (2)
La modélisation des préférences en utilisant des fonctions fait l'objet de la théorie de l'utilité qui dépasse le cadre de cet article. On peut toutefois remarquer que si les préférences R i sont des ordres partiels, il existe une représentation « fine » sous forme de H i , c'est-à-dire telle que :

xP i y ⇔ H i (x) > H i (y).
La définition des jeux non-coopératifs amène naturellement à la question d'une relation de préférence « collective » sur les situations. En effet, toute tentative d'interprétation de ces dernières comme des décisions des joueurs induit la question de l'existence de décisions qui peuvent être considérées meilleures que d'autres, voire optimales. Si, dans le cas d'un problème d'optimisation classique -qui peut d'ailleurs être vu comme un jeu dégénéré à un seul joueur -une solution optimale est souvent la valeur (le choix de stratégie/situation) minimisant ou maximisant une fonction réelle (la fonction de rémunération), dans le cas d'un jeu non-coopératif à plusieurs joueurs, un concept d'optimalité analogue n'a rien d'évident. En toute généralité, ce qu'on cherche peut être défini comme suit. Définition 2. Un concept d'optimalité est une fonction ϕ qui associe à tout jeu un sous-ensemble de son ensemble de situations : ϕΓ ⊆ X. Cependant, la définition 2 est assez générale pour comprendre aussi bien des concepts d'optimalité « intuitifs » que des concepts « artificiels » ou triviaux. Mieux vaut donc suivre l'approche inverse : définir une relation de préférence entre les situations d'un jeu et déterminer ϕΓ comme l'ensemble des situations telles qu'il n'y a aucune situation qui leur soit préférable. Ainsi, une classe importante de concepts d'optimalité peut être exprimée par la construction ci-dessous.

Soit K ⊆ I une coalition et x = (x i ) i∈I une situation de Γ. Une situation y = (y i ) i∈I est atteignable à partir de x pour K si et seulement si, ∀i ∈ I, y i = x i ⇒ i ∈ K. Il est facile de voir que cette relation d'atteignabilité est une relation d'équivalence ; la classe d'équivalence des situations atteignables à partir de x pour K sera notée E Γ (x, K).

Pour n'importe quel K ⊆ I et un ensemble d'indices S k , on peut choisir une famille de couples de sous-ensembles de K indexés par S K : L(K) = { L s P , L s R : s ∈ S K }. La relation de préférences sur X, notée R L(K) , peut être alors définie :

xR L(K) y ⇔ s∈S K     i∈L s P xP i y     i∈L s R xR i y    
Puisque xP i y implique xR i y, on peut considérer sans perte de généralité que L s P ∩ L s R = ∅. Une situation x de Γ est alors appelée L(K)-optimale lorsqu'il n'y a aucune situation y ∈ E Γ (x, K) telle que yR L(K) x.

Enfin, soit K(K) un ensemble de coalitions K ⊆ I et soit L(K) = {L(K) : K ∈ K} l'ensemble des familles de couples correspondant aux coalitions de K. Une situation (x) de Γ est appelée L(K)-optimale si elle est L(K)-optimale pour tout K ∈ K. Le concept d'optimalité ϕ L(K) renvoyant Γ à l'ensemble ϕ L(K) Γ de ses situations L(K)-optimales est appelé concept de Koptimalité.

Presque tous les concepts d'optimalité explorés en théorie des jeux non-coopératifs sont des concepts de K-optimalité. Parmi les plus étudiés, on trouve les suivants :

-K-optimalité de Pareto : lorsque, pour tout K ∈ K, il est

S K = K, L i P = {i : i ∈ K}, L i R = K \ {i : i ∈ K} ;
-si K consiste en une seule coalition K, on parle de K-stabilité de Pareto ; -si K = {I}, on appelle le concept correspondant stabilité de Pareto 1 ; -la 2 I -optimalité de Pareto est aussi appelé stabilité au sens fort ; -K-équilibre : lorsque pour tout K ∈ K, il est S K = {α}, L α P = K, L α R = ∅ ; -le 2 I -équilibre est aussi appelé équilibre au sens fort ; -si K = {{i} : i ∈ I}, le K-équilibre correspondant est appelé équilibre de Nash.

Exemple 1. (Le « dilemme du prisonnier ») Soit le jeu : {A, B}, X A = X B = {d, n}, H A , H B , avec : H A (d, d) = H B (d, d) = -8, H A (n, n) = H B (n, n) = -1, H A (d, n) = H B (n, d) = 0 et H A (n, d) = H B (d, n) = -10.
On peut imaginer que les individus A et B sont incarcérés et isolés l'un de l'autre. Ils sont accusés du même crime mais les preuves de l'accusation sont bien maigres. Chacun a le choix soit de dénoncer son complice pour ce crime (choix d), soit de nier toute implication (choix n). S'ils se dénoncent l'un l'autre, alors ils seront condamnés à 8 ans de prison chacun comme complices. Si tous les deux nient avoir commis le crime, alors ils seront jugés sur la base des preuves existantes qui ne justifient qu'une peine de 1 an pour chacun pour des délits mineurs. Si l'un dénonce tandis que l'autre nie sa participation au crime, alors le premier sera relaxé dans cette affaire tandis que l'autre sera désigner comme seul coupable de l'avoir commis et il sera condamné à 10 ans de prison. Il est facile de voir que, dans ce jeu, la situation (d, d) est un équilibre de Nash, tandis que les trois autres (d, n), (n, d), (n, n) sont des stables (optima) de Pareto2 .

Avant de rentrer dans le vif de notre sujet, notons que nous nous sommes intéressés dans ce tour d'horizon surtout aux aspects algorithmiques des jeux combinatoires. Les classes de complexité que nous allons rencontrées sont brièvement définies en annexe A.

Les équilibres de Nash

A. Cournot, au chapitre 7 de ses fameuses Recherches, avait déjà formulé pour certains jeux à deux joueurs un concept d'équilibre dont l'équilibre de Nash est la généralisation directe ( [START_REF] Leonard | Reading Cournot, reading Nash: the creation and stabilisation of Nash equilibrium[END_REF]). Une grande partie de la recherche contemporaine autour de la théorie des jeux non-coopératifs, surtout en algorithmique des jeux, est consacrée à ce dernier concept d'optimalité et à ses variantes. Les principaux résultats exposés dans cet article, concernent également les équilibres de Nash.

Ce concept dans sa formulation actuelle est introduit par Nash dans [START_REF] Nash | Equilibrium points in N-person games[END_REF]. Dans cette note, l'auteur montra que, pour une très large famille de jeux, l'ensemble d'équilibres de Nash n'est pas vide. Basé sur cette propriété fondamentale, il esquissa ensuite ( [START_REF] Nash | The bargaining problem[END_REF]) un vaste programme de réduction des jeux coopératifs aux jeux non-coopératifs.

Intuitivement, une situation est un équilibre de Nash si aucun joueur n'a à gagner s'il modifie « unilatéralement » son choix (c'est-à-dire tant que les autres restent sur leurs choix composant cette situation).

Afin d'introduire les résultats principaux de Nash, il faut rappeler quelques définitions mathématiques. Définition 3. Soit Z un espace linéaire. Un ensemble

Z ⊆ Z est convexe si, pour tout z , z ∈ Z et λ ∈ [0, 1], on a λz + (1 -λ)z ∈ Z. Définition 4. Soit Z un espace linéaire. Une fonction f : Z -→ R est appelée concave (convexe) si, pour tout z , z ∈ Z et λ ∈ [0, 1], il est : λf z + (1 -λ)f z ( )f λz + (1 -λ)z (3) La fonction f est strictement concave (strictement convexe) si l'inégalité (3) est stricte pour z = z et 0 < λ < 1. La fonction f est quasi-concave (quasi-convexe) si l'ensemble {z : f (z) ( )α} est convexe pour tout α ∈ R.
Un jeu de la forme (2) est appelé concave (quasi-concave) si, pour tout joueur i, son ensemble de stratégies X i est un sous-ensemble convexe d'un espace linéaire et si, lorsqu'on fixe les choix des autres joueurs I \ {i} de façon arbitraire, sa fonction de rémunération H i devient une fonction X i -→ R concave (quasi-concave). Il faut remarquer ici que l'on n'est pas obligé d'avoir des H i concaves ou quasi-concaves.

On peut alors formuler le théorème suivant. Théorème 1. Soit un jeu Γ (de la forme (2)) quasi-concave. Si les ensembles X i des stratégies des joueurs sont compacts (dans une topologie quelconque) et si les fonctions de rémunération H i sont continues (dans la topologie correspondante) sur les situations, alors Γ a un équilibre de Nash.

Preuve. Soit une situation quelconque x. La situation qui résulte si, dans x, on remplace le choix de i par x i , sera notée x x i . Soit c i (x) = argmax x i H i (x x i ), c'est-à-dire l'ensemble des choix x * i du joueur i pour lesquels :

H i (x x * i ) = max x i ∈X i {H i (x x i )}. Puisque X i est compact et H i est continue, c i (x) n'
est pas vide ; de plus, à cause de la quasi-concavité de H i sur x i , c i (x) est convexe (et, par la continuité de H i , fermé).

La correspondance entre x et c i (x) est aussi fermée, c'est-à-dire, pour toute suite convergente de situations : x (1) , . . . , x (m) → x (0) et toute suite convergente de choix de i : y

(1) i , . . . , y (m) i → y (0) i telle que pour m = 1, . . . , : y (m) i ∈ c i x (m) (4)
l'inclusion suivante est vraie :

y (0) i ∈ c i x (0) (5)
On peut montrer (5) en sélectionnant un arbitraire x i . L'expression (4) signifie que, pour tout m : m) x i ) et, par conséquent, en passant à la limite :

H i (x (m) y (m) i ) H i (x (
H i x (0) y (0) i H i x (0) x i
ce qui implique la véracité de (5) puisque la dernière relation est valable quel que soit x i . Considérons maintenant l'application c : X -→ 2 X qui établit la correspondance entre chaque situation x et l'ensemble des situations c(x) = i∈I c i (x). L'ensemble c(x) étant un produit cartésien d'ensembles non-vides compacts et convexes, il est lui aussi non-vide, compact et convexe ; par la fermeture des c i (x), il est aussi fermé.

L'application c satisfait donc les conditions du théorème de Kakutani ([2]) d'après lequel c a un point fixe, c'est-à-dire il existe x * ∈ X tel que x * ∈ c(x * ).

Or, pour tout choix de x * i composante de x * , on aura aussi x * i ∈ c i (x * ), c'est-à-dire que, pour tout joueur i : pour tout x i ∈ X i , H i (x * ) H i (x * x i ). On en déduit que l'ensemble des équilibres de Nash pour un jeu comme celui du théorème 1 n'est pas vide.

Ce résultat peut aussi être obtenu si l'on relaxe la condition de concavité de Γ et si l'on modifie légèrement la condition de continuité des fonctions de rémunération comme le montre le théorème suivant que l'on va citer sans démonstration. Théorème 2. Soit un jeu Γ concave (de la forme (2)). Si les ensembles X i des stratégies des joueurs sont compacts (dans une topologie quelconque) et si les fonctions de rémunération H i sont continues (dans la topologie correspondante) lorsque l'on fixe de façon arbitraire les choix de tous les joueurs sauf i et lorsque l'on laisse varier le choix de i et si i∈I H i (x) est continue sur x, alors Γ a un équilibre de Nash.

Extension mixte d'un jeu et équilibres de Nash

Pour tout concept d'optimalité ϕ, on peut poser la question intéressante de la possibilité de transformer un jeu Γ en jeu T (Γ) de façon à ce que ϕΓ ⊆ ϕT (Γ). L'importance particulière des équilibres de Nash provient exactement du fait qu'il existe une transformation T intuitive telle que tout jeu Γ à nombre de joueurs et ensembles de stratégies finis se transforme en jeu satisfaisant les conditions du théorème 1, c'est-à-dire ayant toujours un équilibre de Nash. Définition 5. Soit Γ = I, {X i } i∈I , {H i } i∈I un jeu avec I et X i finis. On appelle extension mixte de Γ le jeu G = I, {X i } i∈I , {H i } i∈I où les X i sont toutes les mesures de probabilité définis par la X-algèbre 2 X i sur X i et indépendantes entre elles et les H i sont des espérances des H i . Les X i sont appelés ensembles de stratégies mixtes de Γ et leurs éléments des choix mixtes. Intuitivement, une extension mixte de Γ est le jeu qui résulte lorsque les joueurs jouent des distributions de probabilités sur leurs ensembles de stratégies plutôt que des choix ; des situations « classiques » x = (x 1 , . . . , x |I| ) apparaissent lorsque tout joueur i joue une distribution dégénérée sur X i où x i est joué avec probabilité un et tous les autres choix de i sont joués avec probabilité zéro.

Toute situation de Γ est donc aussi une situation de G et, pour les situations de Γ, les rémunérations dans G sont les mêmes que dans Γ. Il est aussi facile de voir que les X i et les H i satisfont les conditions du théorème 1 (en fait, les X i sont des simplexes).

Le théorème suivant résume quelques propriétés de base des extensions mixtes par rapport aux équilibres de Nash. Théorème 3. Toute extension mixte d'un jeu comme Γ de la définition 5 a un équilibre de Nash et tous les équilibres de Nash de Γ sont des équilibres de Nash de son extension mixte. Preuve. D'après la définition 5 de G et la remarque ci-dessus, les ensembles :

X i =    p i : p i (x i ) 0 pour x i ∈ X i et x i ∈X i p i (x i ) = 1  
 sont des simplexes dans des espaces euclidiens à dimension finie, et les topologies dans ces espaces sont compactes. Ici, les espaces sont linéaires et leurs enesembles X i sont convexes.

Pour toute situation mixte x , on aura :

H i x = x 1 ∈X 1 • • • x |I| ∈X |I| H i x 1 , . . . , x |I| p 1 (x 1 ) . . . p |I| x |I|
Par conséquent, les fonctions H i : X -→ R sont linéaires sur chacun de leurs arguments et donc concaves.

On appelle les équilibres de Nash d'une extension mixte de Γ équilibres de Nash de Γ en stratégies mixtes ; ceux qui ne sont pas des équilibres de Nash de Γ sont appelés équilibres de Nash mixtes de Γ et ceux qui le sont sont appelés équilibres de Nash purs de Γ.

L'ensemble des équilibres des jeux de la définition 5 en stratégies mixtes comportent un nombre fini de parties connectées.

Problèmes algorithmiques

Trouver un équilibre en stratégies mixtes est un problème total : quel que soit le jeu, il y en a toujours un. Cependant, la preuve de son existence n'utilise pas des arguments constructifs, au moins au sens « polynomial » du terme. Il faut aussi noter que Nash, dans [START_REF] Nash | Non-cooperative games[END_REF], avait déjà donné l'exemple d'un jeu à trois joueurs dont l'unique équilibre (et non sa description) implique des nombres irrationnels ; un algorithme de calcul d'un équilibre de Nash devrait donc calculer plutôt un équilibre de description finie (rationnel) ε-approché, c'est-à-dire une situation telle qu'aucun joueur n'améliore sa rémunération de plus d'un facteur additif de ε, ce facteur étant donné en entrée de l'algorithme.

La complexité d'un algorithme pour le problème ainsi formulé serait alors exprimée comme ordre de grandeur d'une fonction de la taille de la description du jeu et du paramètre de précision ε.

Jeux à description succincte

Pour spécifier un jeu Γ = I, {X i } i∈I , {H i } i∈I à nombre de joueurs et de stratégies finies, il faut |I| i∈I |X i | valeurs pour décrire les rémunérations, plus i∈I |X i | valeurs pour décrire les ensembles de stratégies, plus le nombre |I| des joueurs. Pour une instance du problème de recherche d'équilibre mixte de Γ, il faut aussi la valeur ε du facteur de précision demandée. Dans cette représentation, c'est la description des rémunérations qui est la plus pesante.

Néanmoins, il est souvent possible d'avoir une représentation succincte des H i , par exemple si chaque fonction de rémunération peut être exprimée par une formule courte et calculable en temps polynomial ou si les rémunérations ne dépendent pas vraiment des choix de tous les joueurs mais seulement de certains d'entre eux. Dans ce dernier cas, on peut associer à Γ un graphe

d'influence orienté G Γ (V, E) ([12]) tel que V (G Γ ) = I E(G Γ ) = {(i, j) : H i dépend de la stratégie choisie par j} (dans ce cas, H i : N (i) → R avec N (i) = {i} ∪ {(j, i) : (j, i) ∈ E(G Γ )}). On appelle Γ un jeu défini sur le graphe G Γ .
Dans le cas général, on peut toujours associer à un jeu un graphe orienté complet mais, pour les jeux auxquels il suffit d'associer un graphe de faible connexité, cette représentation constitue une sorte de factorisation en jeux « locaux » plus petits. Si le graphe est de degré borné ∆, alors, pour la description des H i , on n'a pas besoin de plus de |I|m ∆+1 valeurs où m = max i∈I {|X i |}.

Résultats sur la complexité du calcul d'un équilibre mixte

Il est bien connu qu'un équilibre de Nash pour un jeu peut être représenté comme la solution d'un système d'inégalités polynomiales ( [START_REF] Vorobiev | Mathematical foundations of game theory[END_REF]) et il existe des algorithmes l'obtenant en temps polynomial en 1/ε et en log(M )(mn) m 2 n 2 où M est la rémunération de valeur absolue maximum d'un joueur, m est le nombre maximum de choix d'un joueur et n = |I| ( [START_REF] Grigoriev | Solving systems of polynomial inequalities in subexponential time[END_REF]).

La question de l'existence d'un algorithme de calcul d'un équilibre de Nash mixte en temps polynomial est loin d'être résolue à l'heure actuelle (cf. [START_REF] Papadimitriou | Computing equilibria in multi-player games[END_REF] pour des avancées récentes). Dans la plupart des travaux consacrés à cette question, elle est étudiée sous la forme suivante : étant donné une description succincte d'un jeu, trouver un algorithme de calcul d'un ε-équilibre de Nash mixte du jeu en temps polynomial en 1/ε, en nombre des joueurs et en nombre maximum des choix d'un joueur.

Dans [START_REF] Bubyalis | On equilibria in finite games[END_REF][START_REF] Vorobiev | Mathematical foundations of game theory[END_REF], une transformation est décrite de tout jeu à n joueurs en un jeu à 3 joueurs tel qu'il existe une bijection entre les équilibres du jeu initial et du jeu transformé permettant de retrouver en temps polynomial les équilibres du jeu initial à partir des équilibres du jeu transformé. Dans cette transformation, les ensembles de stratégies des trois joueurs sont de taille exponentielle par rapport à la taille de celles du jeu initial.

Deux autres transformations en jeu à trois préservant les équilibres ont été présentées dans [START_REF] Chen | X. 3-NASH is PPAD-complete[END_REF][START_REF] Daskalakis | Three-player games are hard[END_REF]. Elles sont basées sur l'article [START_REF] Goldberg | Reducibility among equilibrium problems[END_REF]. Dans cet article, il est d'abord montré comment transformer un jeu défini sur un graphe à n sommets et de degré ∆ en jeu à ∆ 2 joueurs (un joueur « spécial » plus ∆ 2 -1 joueurs correspondant aux classes chromatiques du graphe obtenu après rajout sur le graphe initial d'un arc (i, k) pour chaque chemin (i, j), (j, k) dans le graphe initial). Il est ensuite montré comment obtenir, à partir d'un jeu général, un jeu défini sur un graphe de degré 3 dont chaque joueur-sommet dispose de deux choix. En combinant ces deux réductions, il en résulte que le problème de trouver un équilibre dans un jeu à 3 joueurs est, comme dans le cas général, PPAD-complet 3 . L'existence d'un algorithme polynomial 4 pour ce problème est donc assez improbable.

Dans l'article [START_REF] Kearns | Graphical models for game theory[END_REF], les auteurs ont présenté un algorithme pour trouver un équilibre mixte dans un jeu défini sur un arbre où chaque joueur dispose de deux choix (« zéro » et « un »). L'algorithme effectue deux passages de l'arbre, l'un des feuilles vers la racine, l'autre de la racine vers les feuilles. Au premier passage, chaque sommet transmet à son père une suite de nombres entre 0 et 1 qui définissent une suite d'intervalles partitionnant [0, 1] ; ils précisent ainsi quel choix ils vont jouer si le choix du père varie dans chacun des intervalles de la partition de façon à ce qu'il existe toujours un équilibre de Nash avec ce choix du père. A son tour, la suite des nombres a été calculée à partir des données transmises par les enfants du sommet. Lorsqu'on arrive à la racine, celle-ci précise un choix et le transmet à ses enfants ; pendant le passage vers les feuilles, les sommets déterminent leurs choix en fonction de leur suite de nombres et du choix que leur père leur a annoncé. Cet algorithme est polynomial si l'arbre est de degré borné. L'article [START_REF] Vickrey | Multi-agent algorithms for solving graphical games[END_REF] généralise cet algorithme pour d'autres classes de graphes.

Dans les cas de jeux à deux joueurs à somme nulle (c'est-à-dire lorsque, pour tout

(x 1 , x 2 ) ∈ X, H 1 (x 1 , x 2 ) + H 2 (x 1 , x 2 ) = 0)
, le problème de la recherche d'un équilibre de Nash mixte peut être formulé comme un programme linéaire, soluble en temps polynomial.

La question du cas général de jeux à deux joueurs reste ouverte ( [START_REF] Koller | The complexity of two-person zero-sum games in extensive form[END_REF]). Une méthode de solution a été proposée dans [START_REF] Lemke | Equilibrium points of bimatrix games[END_REF] ; néanmoins, cette méthode peut être exponentielle, même pour quelques jeux à somme nulle ( [START_REF] Savani | Exponentially many steps for finding a Nash equilibrium in a bimatrix game[END_REF]). L'article [START_REF] Singh | Nash convergence of gradient dynamics in general-sum games[END_REF] propose aussi des heuristiques de descente gradient pour ce problème.

Quant aux résultats négatifs sur la question de la complexité, [9] en montre quelques uns. L'essentiel des conclusions de cet article est que chercher un équilibre de Nash en stratégies mixtes avec des propriétés précises devient souvent un problème NP-complet, même pour des jeux symétriques 5 à deux joueurs. Pour ce faire, les auteurs de l'article ont construit une réduction d'une formule en forme conjonctive normale en jeu symétrique à deux joueurs, c'est-à-dire tel que la rémunération de l'un des joueurs sur toute situation (x 1 , x 2 ) est égale à la rémunération de l'autre sur la situation (x 2 , x 1 ).

Dans ce qui suit, nous présentons la réduction décrite dans [START_REF] Conitzer | Complexity results about Nash equilibria[END_REF] qui est basée sur celle de [9]. Soit ϕ une formule booléenne en forme conjonctive normale. Soit V son ensemble de variables (avec |V | = n), L l'ensemble des littéraux correspondants aux membres de V et C son ensemble de clauses. La fonction v :

L -→ V nous donne la variable correspondant à un littéral, c'est-à-dire v(z i ) = v(-z i ) = z i . On définit Γ(ϕ) comme étant le jeu symétrique à deux joueurs (I = {1, 2}) suivant : soit X = X 1 = X 2 = L ∪ V ∪ C ∪ {f } ; soit les fonctions de rémunération H 1 , H 2 suivantes : H 1 l 1 , l 2 = H 2 l 2 , l 1 = 1 ∀l 1 , l 2 ∈ L avec l 1 = -l 2 H 1 (l, -l) = H 2 (-l, l) = -2 ∀l ∈ L H 1 (l, z) = H 2 (z, l) = -2 ∀l ∈ L, z ∈ X \ L H 1 (v, l) = H 2 (l, z) = 2 ∀v ∈ V, l ∈ L avec v(l) = v H 1 (v, l) = H 2 (l, v) = 2 -n ∀v ∈ V, l ∈ L avec v(l) = v H 1 (v, z) = H 2 (z, v) = -2 ∀v ∈, z ∈ X \ L H 1 (c, l) = H 2 (l, c) = 2 ∀c ∈ C, l ∈ L avec l / ∈ c 3.
Il s'agit de problèmes de TF, leur appartenance à cette classe pouvant être démontré par un argument de parité (du type : si un graphe orienté a un sommet dont la différence entre degré entrant et degré sortant est différente de zéro, alors il doit en avoir un autre aussi).

4. Au sens exposé plus haut.

Des jeux pour lesquels

H1(x1, x2) = H2(x2, x1), pour tout x1 ∈ X1, x2 ∈ X2. H 1 (c, l) = H 2 (l, c) = 2 -n ∀c ∈ C, l ∈ L avec l ∈ c H 1 (c, z) = H 2 (z, c) = -2 ∀c ∈ C, z ∈ X \ L H 1 (f, f ) = H 2 (f, f ) = 0 H 1 (f, z) = H 2 (z, f ) = 1 ∀z ∈ X \ {f }
Le théorème principal peut alors être énoncé. Théorème 4. Le jeu Γ(ϕ) possède un équilibre de Nash mixte dans lequel les deux joueurs jouent l i avec probabilité 1/n où la rémunération de chaque joueur est 1 si et seulement si

(l 1 , l 2 , . . . , l n ) (avec v(l i ) = z i ) satisfait ϕ.
De plus, le seul autre équilibre de Nash (en stratégies mixtes) est celui où les deux joueurs jouent f et reçoivent une rémunération de 0 chacun.

Preuve. On commence par montrer que ces situations mixtes constituent un équilibre de Nash.

Si (l 1 , l 2 , . . . , l n ) (avec v(l i ) = z i ) satisfait ϕ et l'autre joueur joue l i avec une probabilité 1/n, jouer l'un de ces l i nous donne une rémunération de 1. Par ailleurs :

-jouer la négation d'un de ces l i nous donne une rémunération de :

(1/n)×(-2)+(n -1/n)× 1 < 1 ;
-puisque pour un des l i que l'autre joueur joue parfois on a v(l i ) = v, jouer une variable v nous donne la rémunération :

(1/n) × (2 -n) + (n -1/n) × 2 = 1
; -jouer une clause c nous donne une rémunération au plus de :

(1/n)×(2-n)+(n -1/n)×2 =
1 car l'un des l i que l'autre joueur joue parfois est présent dans la clause c puisque l i satisfait ϕ ; -finalement, jouer f donne la rémunération 1. Il s'ensuit que jouer n'importe lequel des l i que l'autre joueur joue parfois est une réponse optimale et donc que si les deux joueurs jouent chacun un de ces l i avec une probabilité 1/n, on a un équilibre de Nash. Il est clair que le cas où les deux joueurs jouent f est aussi un équilibre de Nash car jouer n'importe quel autre choix quand l'autre joueur joue f lui donne la rémunération -2.

Il reste à démontrer qu'il n'existe pas d'autre équilibre de Nash : si l'autre joueur joue toujours f , l'unique « meilleure réponse » est de jouer aussi f puisque jouer n'importe quel autre choix nous donnera une rémunération de -2. Dans le cas contraire, étant donnée une stratégie mixte de l'autre joueur, on considère la rémunération d'un joueur sachant que l'autre ne joue pas f (c'est-à-dire la distribution de probabilités sur les stratégies de l'autre joueur est proportionnelle à la distribution de probabilités constituée par la stratégie mixte de ce joueur, sauf que f est choisi avec une probabilité 0). Si cette rémunération est plus petite que 1, alors le joueur fera mieux en jouant f (ce qui donne une rémunération égale à 1 quand l'autre joueur ne joue pas f , ce qui est aussi mieux que son choix original quand l'autre joueur joue f ). Par conséquent, cela ne peut être un équilibre de Nash.

Pour le cas où l'un des joueurs joue f et l'autre non, il n'y a pas d'équilibre de Nash ; supposons donc que les deux joueurs jouent f avec un probabilité inférieure à 1. Considérons le « bien-être social espéré » H 1 + H 2 étant donné qu'aucun des joueurs ne joue f . Il est facile de vérifier que l'on n'obtiendra aucune situation donnant un bien-être social supérieur à 2. De plus, toute situation dans laquelle un joueur joue un élément de V ou C entraîne un bien-être social strictement inférieur à 2. On en déduit que si un des deux joueurs joue un élément de V ou de C, le bien-être social espéré, en supposant qu'aucun des joueurs ne joue f , est strictement inférieur à 2.

Par linéarité de l'espérance, il s'ensuit que la rémunération espérée d'au moins un des joueurs est strictement inférieure à 1 en supposant que personne ne joue f et, d'après le raisonnement ci-dessus, ce joueur pourrait améliorer sa rémunération en jouant f plutôt qu'une distribution de probabilités sur ses choix autres que f . On en conclue qu'aucun élément de V ou C n'est joué dans un équilibre de Nash.

On peut donc supposer que les deux joueurs ne mettent que des probabilités positives sur les éléments de L ∪ {f }. Si l'autre joueur met des probabilités positives sur f , alors jouer f est un meilleur choix que jouer n'importe quel élément de L (puisque les deux auront une rémunération égale à 1 si l'autre joue un élément de L ; mais jouer f est un meilleur choix si l'autre joue f ). Il s'ensuit que le seul équilibre dans lequel un des joueurs joue f est celui où les deux joueurs jouent f .

On peut maintenant supposer que les deux joueurs ne mettent que des probabilités positives sur les éléments de L. Supposons que, pour un certain l ∈ L, la probabilité qu'un des joueurs joue l ou -l est inférieure à 1/n. Alors, la rémunération espérée de l'autre joueur quand il joue v(l) est strictement supérieure à :

(1/n) × (2 -n) + (n -1/n) × 2 = 1 et
cela ne peut pas être un équilibre de Nash. On en déduit que, pour tout l ∈ L, la probabilité qu'un joueur joue l ou -l est précisément 1/n.

Si le joueur 1 met des probabilités positives sur un élément de L et que le joueur 2 met des probabilités positives sur la négation de ce même élément, les deux joueurs obtiennent une rémunération espérée inférieure à 1 et feraient mieux en jouant f . Donc, dans un équilibre de Nash, si le joueur 1 joue l avec une certaine probabilité, le joueur 2 doit jouer l avec une probabilité de 1/n. On en déduit que, pour chaque variable, il y a exactement un de ses littéraux qui est joué par les deux joueurs avec une probabilité de 1/n. Il s'ensuit que, dans chaque équilibre de Nash (en plus de celui dans lequel les deux joueurs jouent f ), les littéraux qui sont parfois joués correspondent à une affectation de variables.

Finalement, on montre que si cette affectation ne satisfait pas ϕ, alors cette situation n'est plus un équilibre de Nash. Soit c ∈ C une clause qui n'est pas satisfaite par cette affectation, c'est-á-dire qu'aucun de ses littéraux n'est joué. Alors, jouer c donnerait une rémunération égale à 2 et les deux joueurs feraient mieux de le jouer. D'après le théorème 4 que l'on vient de montrer, il existe un équilibre de Nash dans Γ(ϕ) dans lequel chaque joueur a une rémunération 1 si et seulement si ϕ est satisfaisable ; le seul autre équilibre est celui où les deux joueurs jouent 0 et les deux obtiennent une rémunération 0. Cependant, toute définition sensée de l'« optimisation du bien-être social » nous pousserait plutôt à préférer le premier type d'équilibre. Dans ce sens, déterminer si un « bon » équilibre existe, est donc un problème difficile. De plus, ce type d'équilibre est optimal pour le jeu, même quand les joueurs coopèrent, et donc trouver si un tel type d'équilibre existe est un problème difficile. Les corollaires suivants illustrent les points abordés ici (chaque corollaire découle directement du théorème 4). Corollaire 1. Même dans les jeux symétriques à deux joueurs, il est NP-difficile de déterminer s'il existe un équilibre de Nash x donnant un bien-être social espéré (standard) i∈|I| Hi (x) au moins égal à k, même quand k est le bien-être social maximum pouvant être obtenu dans le jeu.

Corollaire 2. Même dans les jeux symétriques à deux joueurs, il est NP-difficile de déterminer si :

1. il existe un équilibre de Nash dans lequel tous les joueurs ont une rémunération totale au moins égale à k, même quand k est le plus grand nombre pour lequel il existe une distribution sur les situations du jeu telle que tous les joueurs ont une rémunération espérée totale au moins égale à k ; 2. il existe un équilibre de Nash qui soit aussi Pareto-stable ; 3. il existe un équilibre de Nash où l'un des joueurs a une rémunération au moins égale à k ; 4. il existe plus d'un équilibre de Nash ; 5. il existe un équilibre de Nash dans lequel l'un des deux joueurs joue parfois un choix particulier x ∈ X 1 ; 6. il existe un équilibre de Nash dans lequel l'un des deux joueurs ne joue jamais x ∈ X 1 .

Les résultats du corollaire 2 nous montrent qu'il est difficile d'obtenir des informations sommaires sur les équilibres de Nash d'un jeu. Le point 4 et des versions moindres des points 1, 5 et 6 ont été démontrées pour la première fois dans [9].

Pour conclure cette section, on note un résultat remarquable de [START_REF] Daskalakis | Three-player games are hard[END_REF] qui concerne les équilibres de Nash en stratégies mixtes pour des jeux définis sur une grille d-dimensionnelle. Il y est démontré que l'on peut savoir en temps polynomial si un tel jeu défini sur une 1-grille a un équilibre pur tandis que le même problème pour d 2 devient NEXP-complet.

Compter le nombre d'équilibres dans un jeu à stratégies mixtes

Comme nous l'avons fait remarquer (page 5), le nombre des parties connectés 6 des équilibres de Nash d'un jeu mixte est fini. La question de dénombrer ces parties a été d'bord étudiée du point de vue de sa complexité algorithmique dans les articles [START_REF] Mclennan | In-Uck. Generic 4x4 two person games have at most 15 Nash equilibria[END_REF][START_REF] Mclennan | On the expected number of Nash equilibria of a normal form game[END_REF]. On peut utiliser directement le théorème 4 pour montrer que déterminer ce nombre dans un jeu de forme normale donné est difficile. Proposition 1. Même dans les jeux symétriques à deux joueurs, compter le nombre d'équilibres de Nash est P-difficile. Preuve. Le nombre d'équilibres de Nash dans notre jeu Γ(ϕ) du théorème 4 est le nombre d'affectations qui satisfont ϕ plus un. Or, il est bien connu que compter le nombre d'affectations satisfaisant une formule CNF est P-difficile ( [START_REF] Vorobiev | Mathematical foundations of game theory[END_REF]).

Puisque chaque équilibre de Nash dans G(ϕ) constitue un ensemble connecté, le nombre d'ensembles connectés est égal au nombre d'affectations satisfaisant ϕ plus un. On en déduit le corollaire suivant. Corollaire 3. Même dans les jeux symétriques à deux joueurs, compter le nombre d'ensembles connectés maximaux d'équilibres de Nash est P-difficile. Il est intéressant de noter ici que les résultats sur la P-difficulté les plus intéressants sont ceux pour lesquels les questions de recherche et d'existence sont faciles (un tel résultat est, par exemple, la P-difficulté du comptage des couplages parfaits dans un graphe bipartie qui se réduit au calcul du permanent d'une matrice).

Jeux de potentiel

Le problème de représentation évoqué dans la sous-section 4.1 est considérablement simplifié dans le cas de jeux de potentiel que nous présentons dans cette section. Cette famille de jeux modélise un large spectre de problèmes en optimisation ; ils ont toujours des équilibres de Nash purs qui coïncident avec des optima locaux de leur potentiel.

Soit Γ = I, {X i } i∈I , {H i } i∈I un jeu à nombre de joueurs et ensembles finis de stratégies. Pour un ensemble K ⊆ I, -K représente l'ensemble complémentaire de S et X K représente le produit cartésien i∈K X i . Pour les ensembles de singletons {i}, X {-i} sera noté X -i . Soit une situation x = (x 1 , . . . , x n ). On note (x -i , z) la situation : (x 1 , . . . , x i-1 , z, x i+1 , . . . , x n ) = x z.

Une fonction P : X -→ R est un potentiel ordinal pour Γ si, pour tout i ∈ I et pour tout x -i ∈ X -i : H i (x -i , x) -H i (x -i , z) > 0 ⇐⇒ P (a -i , x) -P (a -i , z) > 0, pour tout x, z ∈ X i . Définition 6. Γ est un jeu de potentiel ordinal s'il admet un potentiel ordinal (c'est-à-dire s'il est possible de définir un potentiel ordinal pour Γ).

6. C'est-à-dire des sous-ensembles connectés maximaux. Soit w = (ω i ) i∈I un vecteur de nombres positifs que l'on appellera des poids. Une fonction P : X -→ R est un ω-potentiel pour Γ si, pour tout i ∈ I et pour tout s -i ∈ X -i , on a :

H i (s -i , x) -H i (s -i , z) = ω i (P (s -i , x) -P (s -i , z))
pour tout x, z ∈ X i . Définition 7. Γ est un jeu de ω-potentiel s'il admet un ω-potentiel. On dit aussi que P est un potentiel pondéré et que G est un jeu de potentiel pondéré. Une fonction P : X -→ R est un potentiel exact (ou, plus simplement, un potentiel) pour G si elle est un potentiel pondéré pour G avec ω i = 1, pour tout i ∈ I. Définition 8. Γ est un jeu de potentiel exact (ou, plus simplement, un jeu de potentiel) s'il admet un potentiel.

L'existence d'un potentiel ordinal pour un jeu permet de le transformer en un jeu « simplifié » équivalent au sens que le second a les mêmes équilibres de Nash que le jeu initial. Lemme 1. Soit P un potentiel ordinal pour le jeu :

Γ = I = {1, . . . , n}, {X 1 , . . . , X n } , {H 1 , . . . , H n }
L'ensemble des équilibres de Γ coïncide avec l'ensemble des équilibres de G = {1, . . . , n}, {X 1 , . . . , X n } , {H 1 ≡ H 2 . . . ≡ H n ≡ P } le jeu dans lequel on remplace les fonctions de rémunération par la fonction de potentiel. En d'autres termes, s ∈ X est un point d'équilibre de Nash pour Γ si et seulement si, pour tout i ∈ I tel que x ∈ X i :

P (s) P (s -i , x) (6)
On en déduit que si P admet une valeur maximale dans X, alors G possède un équilibre à stratégies pures. Or, cela est le cas de par la construction de P . On peut alors énoncer le théorème suivant. Théorème 5. Tout jeu de potentiel ordinal fini possède un équilibre de Nash pur.

Le théorème 5 peut encore être généralisé, afin de caractériser exactement la classe des jeu ayant des équilibres de Nash purs.

A partir d'un jeu fini Γ, on peut construire un graphe orienté avec comme ensemble de sommets les situations X de Γ et tous les arcs (s, s ) lorsque les situations s et s ne diffèrent que d'une seule composante i et H i (s ) > H i (s). Si ce graphe est acyclique, on dit que les dynamiques de Nash convergent pour Γ. Proposition 2. Si les dynamiques de Nash convergent, alors il existe un équilibre de Nash pur. Preuve. Les puits du graphe sont précisément les équilibres de Nash du jeu.

Un chemin dans le graphe est une séquence γ = (y 0 , y 1 , . . .) telle que, pour tout k 1, il existe un unique joueur i tel que y k = (y k-1 -i , x) pour x = y k-1 i dans X i ; y 0 est appelé le point initial de γ et si γ est fini, alors son dernier élément est appelé le point terminal de γ. Un chemin γ = (y 0 , y 1 , . . .) est un chemin d'amélioration pour Γ si, pour tout k 1, on a H i (y k ) > H i (y k-1 ) où i est le seul joueur changeant de stratégie à l'étape k. On dit que G possède la propriété d'amélioration finie (ou PAF) si tout chemin d'amélioration est fini. Lemme 2. Tout jeu de potentiel ordinal fini possède la PAF. Preuve. Pour tout chemin d'amélioration γ = (y 0 , y 1 , . . .), on a par le lemme 1 : P (y 0 ) < P (y 1 ) < . . . Comme X est un ensemble fini, la séquence γ doit être finie.

Il est clair que dire d'un jeu qu'il possède la PAF et que ses dynamiques de Nash convergent est équivalent. Donc tout chemin d'amélioration maximal doit aboutir à un équilibre de Nash.

Par ailleurs, il est intéressant de remarquer que posséder la PAF n'est pas équivalent à avoir un potentiel ordinal.

Une fonction P : X -→ R est un potentiel ordinal généralisé pour Γ si, pour tout i ∈ I, pour tout s -i ∈ X -i et pour tout x, z ∈ X i :

H i (s -i , x) -H i (s -i , z) > 0 =⇒ P (s -i , x) -P (s -i , z) > 0
Théorème 6. Un jeu fini Γ a la PAF si et seulement si Γ admet un potentiel ordinal généralisé. Preuve. Soit G un jeu qui a la PAF. On définit la relation binaire sur X comme suit : x y si et seulement si x = y et il existe un chemin d'amélioration fini γ ayant comme point initial y et comme point terminal x. La PAF implique la transitivité de la relation .

Soit Z ⊆ X. On dira que Z est représenté s'il existe une fonction Q : Z -→ R telle que, pour tout x, y ∈ Z, x y implique Q(x) > Q(y). Soit Z un sous-ensemble de X représenté et maximal. Nous allons démontrer que Z = X.

Supposons x / ∈ Z. Si x z pour tout z ∈ Z, on peut étendre Q en Z ∪ {x} en définissant Q(x) = 1 + max z∈Z Q(z), ce qui contredit la maximalité de Z. Si z x pour tout z ∈ Z, on étend Q en Z ∪ {x} en définissant Q(x) = min z∈Z Q(z) -1,
-i ∈ X -i , H i (s -i , x) = H i (s -i , z), ∀x = z ∈ X i . Alors Γ a un potentiel ordinal.
En effet, il suffit de remarquer que la condition supplémentaire sur Γ implique que chaque potentiel ordinal généralisé pour Γ est aussi un potentiel ordinal pour Γ. Le corollaire découle donc du lemme 6.

Finalement, une propriété remarquable des jeux de potentiel exact est qu'ils peuvent être « décomposés » par rapport à une « base » de jeux encore plus simples. Définition 9. Un jeu G = I, {X i } i∈I , {H i } i∈I est :

-un jeu de coordination s'il existe une fonction U : X -→ R telle que

H i ≡ U pour tout i ∈ I ; -un jeu fictif si, pour tout i ∈ I et tout x -i ∈ X -i , il existe un k ∈ R tel que H i (x i , x -i ) = k
pour tout x i ∈ X i . Dans un jeu de coordination, les joueurs poursuivent le même but, ce que reflètent les fonctions de rémunération identiques. Dans un jeu fictif, la rémunération d'un joueur ne dépend pas de sa propre stratégie. Théorème 7. Un jeu Γ = I, {X i } i∈I , {H i } i∈I est un jeu de potentiel exact si et seulement si il existe deux familles de fonctions {C i } i∈I et {D i } i∈I telles que :

-

H i = C i + D i pour tout i ∈ I ; -I, {X i } i∈I , {C i } i∈I est
un jeu de coordination ; -I, {X i } i∈I , {D i } i∈I est un jeu fictif. Preuve. La partie directe est triviale : la fonction de rémunération du jeu de coordination est une fonction de potentiel exact pour Γ.

Pour démontrer la partie inverse, on définit P comme étant un potentiel exact pour Γ. Alors, pour tout i ∈ I, H i = P + (H i -P ). Il est clair que I,

{X i } i∈I , {P i ≡ P } i∈I est un jeu de coordination. Soit i ∈ I, x -i ∈ X -i et x i , χ i ∈ X i . Alors H i (x i , X -i ) -H i (χ i , X -i ) = P (x i , X -i ) -P (χ i , X -i ) implique H i (x i , X -i ) -P (x i , X -i ) = H i (χ i , X -i ) -P (χ i , X -i ).
On en déduit immédiatement que le jeu I, {X i } i∈I , {H i -P } i∈I est bien un jeu fictif.

Les jeux de potentiel ordinal peuvent admettre un grand nombre de potentiels ordinaux. Pour les jeux de potentiel exact, tous les potentiels possibles sont liés entre eux selon la proposition suivante. Proposition 3. Soit P 1 et P 2 , deux potentiels pour le jeu G. Alors il existe une constante c telle que P 1 (x) -P 2 (x) = c pour tout x ∈ X. La proposition 3 implique que l'ensemble de profils de stratégies maximisant une fonction de potentiel d'un jeu de potentiel exact ne dépend pas d'une fonction de potentiel particulière. Des stratégies maximisant le potentiel ont été utilisées dans le lemme 1 pour prouver l'existence d'un équilibre de Nash pur pour les jeux de potentiel ordinal. Le « maximiseur de potentiel » défini formellement pour un jeu de potentiel comme :

PM(Γ) = x ∈ X : x ∈ argmax χ∈X {P (
χ)} pour un potentiel P de Γ peut alors être utilisé comme un outil de « raffinement » d'équilibre comme suggéré dans [START_REF] Monderer | Potential games[END_REF].

6 Jeux de congestion

Modèle de Rosenthal

Dans un modèle de congestion, les joueurs utilisent plusieurs ressources sélectionnées dans un « réservoir » commun. Les coûts ou bénéfices qu'un joueur dérive de l'utilisation d'une ressource sont déterminés par le nombre de joueurs utilisant cette ressource. Le but de cette sous-section est de définir le modèle de congestion de Rosenthal ([34]). Dans ce modèle, chaque joueur sélectionne un sous-ensemble de ressources. L'allocation associée à chaque ressource est une fonction qui ne dépend que du nombre de joueurs utilisant cette ressource. La rémunération d'un joueur est la somme des allocations associées à chaque ressource dans son choix de stratégies étant donné les choix des autres joueurs. On peut établir l'existence d'un équilibre de Nash pur en construisant une fonction de potentiel exact pour de tels jeux de congestion (voir ci-après pour une définition formelle de cette famille des jeux). L'article [START_REF] Monderer | Potential games[END_REF] montre que tout jeu de potentiel exact est isomorphique à un jeu de congestion. Leur preuve étant assez complexe, [START_REF] Voorneveld | Congestion games and potentials reconsidered[END_REF] donne une preuve plus courte et plus intuitive basée sur le théorème 7.

Un modèle de congestion est défini par : -un ensemble fini I de joueurs ; -un ensemble fini F de ressources ; -pour chaque joueur i ∈ I, son ensemble de stratégies X i est une famille de sous-ensembles de F ; -pour chaque ressource f ∈ F , w f : {1, . . . , n} → R est la fonction d'allocation de la ressource f avec w f (r), r ∈ {1, . . . , n} les allocations pour chaque utilisateur de la ressource f si le nombre total d'utilisateurs est r. Ce modèle permet de définir un jeu de congestion où I est l'ensemble de joueurs, X i l'ensemble des choix du joueur i ∈ I et

H i : X → R est défini comme suit : pour chaque x = (x 1 , . . . , x n ) ∈ X et pour chaque f ∈ F , on a : n f (x) = |{i ∈ I : f ∈ x i }| le nombre d'utilisateurs de la ressource f si les joueurs choisissent X. Alors, H i (x) = f ∈x i w f (n f (x)).
Cette définition implique que chaque joueur n'est rémunéré qu'en fonction des ressources qu'il utilise et du nombre d'utilisateurs de ces ressources. Remarquons que les fonctions d'allocations peuvent donner des valeurs négatives représentant le coût d'utilisation d'une ressource.

Le résultat principal de l'article [START_REF] Rosenthal | A class of games possessing pure-strategy Nash equilibria[END_REF], formulé en termes de potentiel exact, est donné dans la proposition suivante. La preuve est triviale et peut donc être omise. Proposition 4. Soit Γ un jeu de congestion défini comme ci-dessus. Alors Γ est un jeu de potentiel exact. Une fonction de potentiel est donnée par P : X → R définie pour tout x = (x i ) i∈I ∈ X comme suit :

P (x) = f ∈∪ i∈I X i n f (x)
l=1 w f (l). Puisque X est un ensemble fini, le jeu possède un équilibre de Nash à stratégies pures. Soit Γ = I, {X i } i∈I , {H i } i∈I et Λ = I, (χ i ) i∈I , (U i ) i∈I deux jeux ayant le même ensemble de joueurs. Les jeux, Γ et Λ sont isomorphiques si, pour tout i ∈ I, il existe une bijection

ϕ i : X i → χ i telle que, pour tout (x 1 , . . . , x n ) ∈ X, H i (x 1 , . . . , x n ) = U i (ϕ 1 (x 1 ), . . . , ϕ n (x n )).
Un jeu de congestion dans lequel les ressources ont des allocations non nulles seulement si tous les joueurs les utilisent est clairement un jeu de coordination. De plus, tout jeu de coordination peut être formulé dans cette forme comme le montre la preuve du théorème suivant. Théorème 8. Tout jeu de coordination est isomorphique à un jeu de congestion. Preuve. Soit Γ = I, {X i } i∈I , {H i ≡ U } i∈I un jeu de coordination à n joueurs dans lequel chaque joueur a la même fonction de rémunération U . Pour chaque x ∈ X, on a une ressource différente f (x). On définit le modèle de congestion I, F, {Ξ i } i∈I , {W f } f ∈F suivant :

-

F = ∪ x∈X {f (x)} ; -pour chaque i ∈ I, Ξ i = {g i (x i ) : x i ∈ X i } où la fonction g i (x i ) est définie par g i (x i ) = ∪ x -i ∈X -i {f (x i , x -i )} ; -pour chaque f (x) ∈ F : W f (x) (r) = U (x) si r = |I| 0 sinon -pour tout (x 1 , . . . , x |I| ) = x ∈ X : i∈I g i (x i ) = {f (x)
}. Donc le jeu correspondant à ce modèle de congestion est isomorphique à Γ (l'isomorphisme associe x i à g i (x i )).

Considérons maintenant un jeu de congestion dans lequel les allocations pour une certaine ressource sont non nulles uniquement si elle n'est utilisée que par un seul joueur. Si pour chaque joueur, étant donné les choix de stratégies des autres joueurs, on choisit une ressource et on garde toujours la même sans se soucier de ses propres choix de stratégies, on a un jeu fictif. Théorème 9. Tout jeu fictif est isomorphique à un jeu de congestion. Preuve. Soit Γ = I, {X i } i∈I , {H i } i∈I un jeu fictif. Pour chaque i ∈ I et chaque x -i ∈ X -i on a une ressource différente f (x -i ). On définit le modèle de congestion I, M,

{Ξ i } i∈I , {W f } j∈F avec F = ∪ i∈I ∪ x -i ∈X -i {f (x -i )} pour tout i ∈ I : Ξ i = {h i (x i ) : x i ∈ X i } où : h i (x i ) = {f (X -i ) : x -i ∈ X -i } ∪ {f (χ -j ) : j ∈ I \ {i} et χ -j ∈ X -j est tel que χ i = x i } et pour tout f (x -i ) ∈ M : W f (x -i ) (r) = H i (x i , x -i ) si r = 1 (avec x i ∈ X i arbitraire) 0 sinon
Pour tout i ∈ I, x-i ∈ X -i , et xi ∈ X i : i est l'unique utilisateur de f (x -i ) dans (h j (x j )) j∈I et toutes les autres ressources dans h i (x i ) ont plus d'un utilisateur. En effet, soit i ∈ I,

x-i ∈ X -i , et xi ∈ X i . Alors f (x -i ) ∈ h i (x i ) et, pour tout j ∈ I \ {i} : f (x -i ) / ∈ h j (x j ), donc i est le seul utilisateur de f (x -i ) dans (h j (x j )) j∈I . Soit f ∈ h i (x i ), f = f (x -i ). Alors : -si f = f (χ -i ) pour χ -i ∈ X -i , alors χ -i = x-i implique que χ j = xj pour j ∈ I \ {i}, donc f = f (χ -i ) ∈ h j (x j ) ; -si f = f (χ -j ) pour j ∈ I \ {i} et χ -j ∈ X -j avec χ i = xi , alors f = f (χ -j ) ∈ h j (x j
). Dans les deux cas, f a plus d'un utilisateur. Donc le jeu correspondant à ce modèle de congestion est isomorphique à Γ (l'isomorphisme associe x i à h i (x i )).

Dans les deux théorèmes précédents, on a prouvé que les jeux fictifs et les jeux de coordinations sont des jeux de congestion. En utilisant la décomposition du théorème 7, on obtient le théorème suivant. Théorème 10. Tout jeu de potentiel exact est isomorphique à un jeu de congestion. Preuve. Soit Γ = I, {X i } i∈I , {H i } i∈I un jeu de potentiel exact. On le décompose en un jeu de coordination et un jeu fictif comme dans le théorème 7 et on prend leurs jeux de congestion isomorphiques associés comme dans les théorèmes 8 et 9. Sans perte de généralité, on prend leurs ensembles de ressources disjoints. On peut construire une jeu de congestion isomorphique à Γ en prenant l'union des deux ensembles de ressources, les fonctions d'allocation comme dans les théorèmes 8 et 9 et les ensembles de stratégies

Ξ i = {g i (x i ) ∪ h i (x i ) : x i ∈ X i }.
Dans un jeu de congestion de réseau, les familles de stratégies X i sont assimilées implicitement à des chemins dans un réseau. Soit un réseau G(V, E) 7 , deux noeuds a i , b i ∈ V pour tout joueur i ∈ I et une fonction d'allocation, les arêtes jouant le rôle de ressources. Le sous-ensemble de F disponible comme ensemble d'actions pour le joueur i est l'ensemble de tous les chemins de a i à b i . On suppose que le réseau est orienté. Un jeu de congestion de réseau est symétrique si tous les joueurs ont les mêmes points de départ et d'arrivée a et b. Habituellement, les fonctions d'allocations sont appellees fonctions de retard dans les jeux de congestion de réseau. On présente dans la sous-section suivante les résultats de complexité obtenus dans [START_REF] Fabrikant | The complexity of pure Nash equilibria[END_REF].

Le résultat suivant caractérise la complexité des jeux de congestion dans le modèle de Rozenthal. Théorème 11. Il existe un algorithme polynomial permettant de trouver un équilibre de Nash pur dans les jeux de congestions de réseau symmétriques. Preuve. L'algorithme calcule l'optimum de la fonction P (x) donnée dans le théorème 4. Puisque l'optimum est aussi un optimum local, la situation x résultante est un équilibre de Nash pur. L'algorithme est une réduction vers le problème de flot à coût minimum (minimum-cost flow ). Etant donné un réseau N = V, E, a, b et la fonction de retard (w e ) e∈E , on remplace dans N chaque arête e par n = |I| arêtes parallèles entre les mêmes noeuds, chacune ayant une capacité égale à 1 et avec les coûts w e (1), . . . , w e (n). Il est facile de vérifier que chaque min-cost flow (entier) du nouveau réseau est un état qui minimise P (x).

Le théorème suivant concerne la complexité de recherche d'un équilibre de Nash pur dans les jeux de congestion. Théorème 12 . Il est PLS-complet de trouver un équilibre de Nash pur dans les jeux de congestion de réseau de types suivants :

1. jeux de congestion généraux ; 2. jeux de congestion symétriques ; 3. jeux de congestion de réseau asymétriques. Le lecteur intéressé peut trouver la preuve, assez technique, du théorème 12 dans [START_REF] Fabrikant | The complexity of pure Nash equilibria[END_REF]. On donne ici ses lignes conductrices :

-pour démontrer 1, les auteurs de [START_REF] Fabrikant | The complexity of pure Nash equilibria[END_REF] construisent, à partir d'une instance de posnae3flip 8 , un jeu de congestion tel que ses équilibres de Nash sont les optima locaux de l'instance ;

7. Ce réseau est en fait, un graphe ; le terme « réseau » est utilisé pour éviter la confusion avec les jeux définis sur un graphe présentés plus haut.

8. posnae3flip dénote le problème suivant : « étant donné une instance de not-all-equal-3sat (i.e., une forme conjonctive normale où l'on cherche une affectation de valeurs 0 ou 1 à ses variables qui satisfasse la formule et telle que chaque clause de la formule ait au moins un littéral mis à 1 et au moins un littéral mis à 0) avec des poids sur les clauses et ne contenant que des littéraux positifs, trouver une affectation de variables satisfaisant les -la preuve de 2 est une réduction du cas non symétrique vers le cas symétrique ; -enfin, pour la preuve plus compliquée de 3, les auteurs modifient le problème posnae3flip en un nouveau qu'ils appellent witnessed xpnae3flip ; ensuite, ils montrent que :

-il existe une PLS-réduction de witnessed xpnae3flip vers network congestion game ; witnessed xpnae3flip est PLS-complet.

Autres modèles

Les jeux présentés dans [START_REF] Konishi | Equilibria in a model with partial rivalry[END_REF][START_REF] Milgrom | Putting auction theory to work[END_REF][START_REF] Quint | A model of migration[END_REF] sont similaires dans le sens où les rémunérations des joueurs sont caractérisées par un effet de congestion. Les différentes classes de jeux dont on va parler dans cette sous-section sont identifiées par des ensembles de propriétés concernant la structure des « interactions des stratégies ». En particulier, les auteurs de [START_REF] Konishi | Equilibria in a model with partial rivalry[END_REF] imposent les hypothèses suivantes, présentées ci-après, pour un jeu Γ = I, {X i } i∈I , {H i } i∈I . Hypothèse 1. Il existe un ensemble fini F tel que X i = F pour tout joueur i ∈ I. Cet ensemble F est appelé « ensemble de ressources » et une stratégie pour un joueur i est de choisir un élément de F . Hypothèse 2. Pour toute situation x ∈ X et tout couple de joueurs i, j ∈ I : si x i = x j et x j ∈ X j est telle que x i = x j , alors H i (x j , x -j ) = H i (x j , x -j ). Les auteurs de [START_REF] Konishi | Equilibria in a model with partial rivalry[END_REF] appellent cette hypothèse independence of irrelevant choices (littéralement « indépendance des choix hors de propos ») : pour chaque joueur i ∈ I et chaque situation x, la rémunération de i ne changera pas si l'ensemble de joueurs qui choisissent la même ressource que le joueur i n'est pas modifiée.

Soit x ∈ X, f ∈ F . On note n f (X) le nombre d'utilisateurs de la ressource f dans la situation x. La troisième propriété peut alors être formulée comme suit. Hypothèse 3. Pour tout joueur i ∈ I et toute situation x, χ ∈ X avec x i = χ i : si n f (x) = n f (χ) pour tout f ∈ F , alors H i (x) = H i (χ). L'hypothèse 3 peut être vue comme une sorte de « condition d'anonymat ». Elle reflète l'idée que la rémunération du joueur i dépend du nombre de joueurs choisissant d'utiliser les ressources plutôt que de leur identité.

La quatrième hypothèse, appelée partial rivalry (littéralement « rivalité partielle »), établit le fait que chaque joueur i ne regrettera pas que d'autres joueurs ayant choisi la même ressource que lui en choisissent une autre. Hypothèse 4. Pour tout joueur i ∈ I, chaque situation x ∈ X, chaque joueur j = i tel que x j = x i et chaque x j = x i : H i (x j , x -j ) H i (x j , x -j ). Bien que l'article [START_REF] Milgrom | Putting auction theory to work[END_REF] introduise son modèle d'une manière légèrement différente, la classe de jeux en résultant est la même. Plus spécifiquement, [START_REF] Milgrom | Putting auction theory to work[END_REF] pose les hypothèses 1, 4 et aussi l'hypothèse suivante. Hypothèse 5. Pour tout joueur i ∈ I et tout couple de situations (x, χ) avec

x i = χ i = f , si n f (x) = n f (χ), alors H i (x) = H i (χ).
En d'autres termes, la rémunération du joueur i dépend uniquement du nombre de joueurs ayant choisi la même ressource que lui. En supposant l'hypothèse 1, on peut démontrer directement que l'hypothèse 5 implique les hypothèses 2 et 3. La réciproque est également vraie. Lemme 3. Tout jeu Γ = I, {X i } i∈I , {H i } i∈I satisfaisant les hypothèses 1, 2 et 3 satisfait également l'hypothèse 5.

clauses dont le poids total ne peut être amélioré en flippant une variable » ; on sait d'après [START_REF] Shäffer | Simple local search problems that are hard to solve[END_REF] que ce problème est PLS-complet.

Preuve. Soit Γ = I, {X i } i∈I , {H i } i∈I un jeu satisfaisant les hypothèses 1, 2 et 3. Soit i ∈ I, x, χ ∈ X tels que x i = χ i = f et on suppose que n f (x) = n f (χ). Si |F | = 1, alors l'hypothèse 5 est directement vérifiée. Sinon, par un usage répété de l'hypothèse 2, on sait que, pour un γ fixé tel que γ = x i , les relations H i (x i , x -i ) = H i (x i , x -i ) sont vérifiées où, pour chaque j ∈ I \ {i} :

x j = x i si x j = x i γ sinon et que les relations H i (x i , χ -i ) = H i (x i , χ -i
) sont également vérifiées où, pour chaque j ∈ I \{i} :

χ j = x i si χ j = x i γ sinon On remarque que, pour chaque h ∈ F , n h (x i , x -i ) = n h (x i , χ -i ). Donc l'hypothèse 3 im- plique : H i (x i , x -i ) = H i (x i , χ -i ). Par conséquent, H i (x i , x -i ) = H i (x i , x -i ) = H i (x i , χ -i ) = H i (χ i , χ -i ).
Les auteurs de [START_REF] Konishi | Equilibria in a model with partial rivalry[END_REF][START_REF] Milgrom | Putting auction theory to work[END_REF] ont démontré indépendamment le théorème suivant. Théorème 13. Tout jeu Γ = I, {X i } i∈I , {H i } i∈I satisfaisant les hypothèses 1, 2, 3 et 4 possède un équilibre de Nash pur. D'après les définitions précédentes, une situation x de Γ est un équilibre au sens fort si, pour tout K ⊆ I et tout choix χ K ∈ X K , il existe au moins un joueur i ∈ K tel que H i (χ K , X -K ) H i (X). On note SE(Γ) l'ensemble des équilibres au sens fort du jeu Γ. En général, l'existence d'un équilibre fort n'est pas garantie mais les auteurs [START_REF] Konishi | Equilibria in a model with partial rivalry[END_REF] démontrent le théorème suivant. Théorème 14. Pour tout jeu satisfaisant les hypothèses 1, 2, 3 et 4, l'ensemble des équilibres forts est non-vide. Les auteurs [START_REF] Quint | A model of migration[END_REF] proposent un modèle dans lequel l'hypothèse que tous les joueurs possèdent le même ensemble de ressources (établie par l'hypothèse 1) est levée. Hypothèse 6. Il existe un ensemble fini F tel que X i ⊆ F pour tout i ∈ I. En supposant que l'hypothèse 6 est vérifiée, il est toujours simple de vérifier que l'hypothèse 5 implique les hypothèses 2 et 3. Mais la réciproque n'est plus vraie comme dans le lemme 3. Exemple 2 . On choisit I = {1, 2, 3}, F = {a, b, c} et les ensembles de stratégies X 1 = {a, b}, X 2 = {a}, X 3 = {a, c}. Ce jeu satisfait l'hypothèse 6. L'hypothèse 3 n'impose aucune contrainte supplémentaire et l'hypothèse 2 impose que H 1 (b, a, a) = H 1 (b, a, c) et H 3 (a, a, c) = H 3 (b, a, c). Cela n'implique pas que H 2 (a, a, c) = H 2 (b, a, a), condition requise par l'hypothèse 5.

Théorème 15. ( [START_REF] Quint | A model of migration[END_REF]) Tout jeu satisfaisant les hypothèses 6, 5 et 4 possède un équilibre de Nash pur.

Les jeux appartenant aux classes définies jusqu'alors n'admettent pas forcément de fonction de potentiel. Considérons maintenant la condition de « symmétrie croisée » (cross symmetry) qui établit le fait que les rémunérations sur certaines ressources sont indépendantes des joueurs du moment que le nombre d'utilisateurs reste le même. Elle est exprimée par l'hypothèse suivante. Hypothèse 7. Pour tout couple de situations (x, χ) ∈ X 2 et tout couple de joueurs (i, j) ∈ I 2 : si x i = χ j = f et n f (x) = n f (χ), alors H i (x) = H j (χ). Remarquons que les hypothèses 1 et 7 impliquent l'hypothèse 5 et donc les hypothèses 2 et 3 également. De plus, les hypothèses 1 et 7 garantissent l'existence d'un potentiel exact. Théorème 16. Tout jeu satisfaisant les hypothèses 1 et 7 est un jeu de potentiel exact.

Preuve. Soit Γ = I, {X i } i∈I , {H i } i∈I satisfaisant les hypothèses 1 et 7. Pour tout f ∈ F et x, χ ∈ X tels que n f (x) = n f (χ), on a par l'hypothèse 7 que s'il existe i, j ∈ I tels que x i = χ j = f , alors H i (x) = H j (χ). Cela montre que, pour tout f ∈ F , il existe une fonction d'allocation W f : {1, . . . , n} → R telle que, pour tout x ∈ X, si x i = f , alors H i (x) = W f (n f (x)). Cela fait du jeu Γ un jeu de congestion défini comme dans la sous-section 6.1 9 . Le résultat découle maintenant de la proposition 4.

Le théorème 16 est toujours vrai si nous remplaçons l'hypothèse 1 par l'hypothèse 6. La proposition 4 nous dit aussi que la fonction d'allocation (W f ) f ∈F induit le potentiel :

P : X -→ f ∈∪ i∈I {X i } n f (x) l=1 W f (l)
Les auteurs de [START_REF] Voorneveld | Congestion games and potentials reconsidered[END_REF] définissent une classe de jeux de congestion C satisfaisant les hypothèses 1, 7 mais aussi l'hypothèse 4. Il s'agit de la classe : Mentionnons enfin que la plus grande famille pour laquelle il a été montré qu'il existe des équilibres de Nash pures est la famille des jeux de congestion. Par ailleurs, les jeux du modèle de [START_REF] Konishi | Equilibria in a model with partial rivalry[END_REF][START_REF] Milgrom | Putting auction theory to work[END_REF] possèdent au moins un équilibre de Nash pur ; par contre, aucune fonction de potentiel permettant d'établir ce résultat n'est connue.

Remarques

Le concept du jeu non-coopératif, comme il est formulé par la définition 1, est suffisamment général pour représenter une vaste famille de jeux qui, à première vue, ne rentrent pas dans cette formulation. En effet, plusieurs modèles de jeux, comme les jeux répétés, les jeux à étapes, les jeux joués par des automates ou les jeux à information incomplète, peuvent être réduits à cette forme avec des choix appropriés pour l'ensemble des joueurs, les stratégies et les préférences.

La théorie des jeux non-coopératifs a été développée pour la plupart à travers l'étude des formes spéciales des jeux ; ainsi, il existe une vaste littérature sur les jeux à deux joueurs ou les jeux répétés pour mentionner quelques exemples. Parmi elles, seules les familles des jeux pour lesquelles les avancées en recherche algorithmique sont les plus significatives ont été abordés.

  ce qui est aussi en contradiction avec la maximalité de Z. Si enfin ni x z, ni z x, alors nous étendons Q et contredisons la maximalité de Z en définissant Q(x) = (a + b)/2 où a = max{Q(z) : z ∈ Z, x z} et b = min{Q(z) ∈ Z, z x}. Donc X est représenté (et admet un potentiel ordinal généralisé Q). Corollaire 4. Soit Γ un jeu fini ayant la PAF. Supposons de plus que, pour tout i ∈ I et pour tout s

C 7 Théorème 17 .

 717 = Γ = I, {X i } i∈I , {H i } i∈I : Γ satisfait les hypothèses 1, 4 et Pour tout jeu appartenant à la classe C, SE = NE = PM 10 . En effet, pour tout jeu Γ, SE(Γ) ⊆ NE(Γ) et, pout tout jeu de potentiel exact, PM(Γ) ⊆ NE(Γ). Pour démontrer le théorème 17, il suffit de démontrer le résultat suivant. Proposition 5. Pour tout jeu Γ ∈ C, NE(Γ) ⊆ PM(Γ) et NE(Γ) ⊆ SE(Γ).

  Un tour d'horizon sur quelques classes de jeux combinatoires *

	Aristotelis Giannakos	Vangelis Th. Paschos †
	LAMSADE, CNRS UMR 7024 et Université Paris-Dauphine
	Place du Maréchal De Lattre de Tassigny, 75775 Paris Cedex 16, France
	{giannako,paschos}@lamsade.dauphine.fr
	28 juin 2006
	1 Définitions

La première analyse détaillée de ce jeu est publiée dans[START_REF] Luce | Introduction and critical survey[END_REF] ; la monographie[START_REF] Rapaport | Prisoner's dilemma. A study in conflict and cooperation[END_REF] lui est entièrement consacrée.