Silence. (Dessin)

N. Lygeros




Peu à peu, la discussion devenait plus profonde. Toujours dans le cadre de la recherche, les étudiants recherchaient les schémas mentaux. En un instant, ils lui demandèrent s’il pouvait y avoir une relation avec les hyperstructures afin de créer des liens. Il parla alors de résultats qui avaient été trouvés avec Chaunier sur les groupes cycliques et avec Mizony sur les groupes quelconques. L’idée était simple puisqu’elle utilisait un vieux théorème. Il était toujours possible de trouver un ensemble partiellement ordonné qui était isomorphe au groupe d’automorphisme d’un groupe quelconque. Mais pour que le résultat soit constructif et si possible avec le plus petit ordre , ils ont trouvé une nouvelle méthodologie. Ils prirent d’abord un groupe, tracèrent sa matrice, construisirent le tableau de Cayley et ensuite incorporèrent des chaînes à chaque sommet et ainsi, ils ne cassèrent pas la cyclicité du graphe et créèrent enfin un ensemble partialement ordonné pour lequel le groupe d’automorphisme était isomorphe au groupe initial. Σε κάποια στιγμήen un instant, Κορυφών : sommets (théorie des graphe) https://pdfs.semanticscholar.org/421d/20cdd3c55c545e3879dcca5959cb3ca483b5.pdf Birkhoff: 1946 Tout group fini peut être réalisé (que signifie réalisé?) par un groupe d’automorphisme d’un poset fini. Si |G|=n, G peut etre réalisé par le groupe d’automorphism d’un poset avec n(n+1) points. (Ce théorème est-il important car il fait un lien entre une notion algébrique et une notion d’ordre). http://www.lygeros.org/4483.pdf http://www.lygeros.org/4404.pdf http://www.lygeros.org/4236.pdf http://lygeros.org/articles.php?n=4222&l=gr http://www.lygeros.org/3560.pdf http://lygeros.org/articles.php?n=3558&l=gr http://www.lygeros.org/3559.pdf http://lygeros.org/articles.php?n=3541&l=gr http://www.lygeros.org/3553.pdf http://lygeros.org/articles.php?n=3427&l=gr http://lygeros.org/articles.php?n=1086&l=gr http://lygeros.org/articles.php?n=4403&l=gr http://lygeros.org/articles.php?n=4443&l=gr http://lygeros.org/articles.php?n=4483&l=gr http://lygeros.org/articles.php?n=5797&l=gr http://lygeros.org/articles.php?n=12673&l=gr http://www.lygeros.org/lygeros/12860.pdf http://lygeros.org/articles.php?n=12872&l=gr http://lygeros.org/articles.php?n=31708&l=gr http://arielrubinstein.tau.ac.il/papers/20.pdf Soit un entier $n$ Le groupe symétrique est $S_n=Bij(X)={1,ldot,n}$. Le groupe symétrique $S_n$ agit naturellement sur $X$. Il est de cardinal $n!$. On définit une relation d’équivalence en disant que deux éléments $x,yin X$ sont équivalents si et seulement si il existe $jinmathbb{Z}$ tels que $y=sigma^j(x)$ : $$xRyLongleftrightarrow exists jinmathbb{Z}, y=sigma^j(x)$$ Une classe d’équivalence s’appelle aussi orbite. Comme pour toute relation d’équivalence $X$ est réunion disjointes de $sigma$-orbites $O_i(sigma)$. Soit $$n_1geq n_2geq ldotsgeq n_N$ la suite ordonnée des cardinaux des orbites non réduites à un élément. Le type de $sigma$ est le $N$-uple $bar{n}=(n_1,ldots,n_N)$. On dit que $sigma$ est un cycle de longueur $d=n_1$ si $N=1$, on parle de $d$-cycle. Le support d’un cycle est son unique orbite non réduite à un élément. La longueur d’un cycle est le cardinal de son support. Un cycle de longueur 2 est une transposition. On note un cycle de longueur $d>1$ sous la forme $$sigma=(x,sigma(x), ldots, sigma^{d-1}(x))$$ où $x$ est un élément arbitraire dans l’orbite non trivial de $sigma$. Par exemple, le cycle de longueur 3 noté $(3, 7, 5)$ fixe tout élément distinct de 3,7, 5 et permute circulairement les autres éléments sur le dessin $$3rightarrow 7 rightarrow 5 rightarrow 3$$ Deux cycles commutent si et seulement si leurs supports sont disjoints. Le produit de tels cycles est donc bien défini l’ordre n’intervenant pas. Toute permutation s’écrit de façon unique comme produit de cycles à supports disjoints. Les transpositions engendrent le groupe $S_n$. Pour un cycle $(a_1,…,a_m)in S_n$ et $sigmain S_n$, on a la formule $$sigmacirc (a_1,ldots, a_m)circ sigma^{-1}=(sigma(a_1),ldots, sigma(a_m))$$ Elle assure que le conjugué d’un cycle est un cycle de même longueur et que de plus deux cycles sont conjugués si et seulement si ils ont la même longueur. \ Deux permutations sont conjuguées si et seulement si elles ont même type. Un père propose à son fils de choisir un nombre entier entre 1 et 10. Le père choisira également un tel nombre qu’il prendra soin d’écrire sou pli scellé. Si tous deux ont désigné un nombre pair, alors le père donnera deux écus à son fils, si tous deux ont choisi un nombre impair, alors il ne lui donnera qu’un écu : si enfin, l’un deux à choisi un nombre pair et l’autre un nombre impair, alors c’est le fils qui donnera un écu à son père. Le jeu peut se ramener : -Il n’existe pas de stratégie dominante dans ce jeu, mais il y a une espèce de circularité : si le père joue P, le mieux que le fils puisse faire c’est de jouer P. Dans ce cas, son père intérêt à jouer I. Auquel cas son père a de nouveau intérêt à jouer P, mais son fils devrait alors se raviser, et jouer I. Auquel cas, son père a de nouveau intérêt à jouer P. -Si on suppose que chacun des deux joueurs décide de jeter indépendamment une pièce de monnaie avant de jouer : begin{itemize} item Si la pièce du père tombe sur Face, le père joue P item Si la pièce du père tombe sur Pile, le père joue I item Si la pièce du fils tombe sur Face, le fils joue P item Si la pièce du fils tombe sur Pile, le fils joue I end{itemize} -Si la pièce est truquée de telle sorte que Pile tombe avec une probabilité de 3/5. L’espérance d’utilité de ce père est égale à -1/5. Supposons que l’un d’entre eux ait la velléité de dévier du scénario précédent : que le fils, par exemple, tente de jouer P à coup sûr. Son paiement est inchangé. Il en va de même pour son père et pour toute déviation que chacun d’eux pourrait concevoir. L’idée fondatrice de von Neumann est de considérer que cette issue du jeu est la solution. -Une autre interprétation des stratégies mixtes consiste à en faire des croyances et non plus des loteries. Admettons qu’Alice et Bill jouent au jeu précédent depuis plusieurs années et que chacun d’eux ait observé que son adversaire joue P (resp. I) avec une fréquence statistique égale 2/5 (resp 3/5). Considérons le point de vue d’Alice, qui est prudente et pessimiste, et qu’elle se dise que, quelle que soit la stratégie (mixte) qu’elle décidera de mettre en œuvre, son mari choisira systématiquement la stratégie mixte qui la pénalise le plus. Puisqu’elle est prudente, elle choisira une stratégie mixte qui maximise le plus mauvais paiement que Bill serait capable de lui infliger. Une telle stratégie se nomme une stratégie de maximum. -Dès lors qu’elle accordera des poids différents de (2/5,3/5) à ses stratégies, son adversaire sera en mesure de lui infliger un paiement espéré inférieur à -1/5. En jouant (2/5,3/5), elle peut se garantir un paiement final espéré égal à -1/5, quelle que soit la stratégie de son adversaire. -la somme des paiement des deux joueurs est nulle quelle que soit la paire de stratégies mixtes qu’ils décident de jouer. La paiement espéré d’Alice (du joueur qui joue en colonnes), lorsque les deux joueurs jouent leur stratégie mixte prudente, les deux joueurs jouent leur stratégie mixte prudente, se nomme la valeur du jeu somme nulle. -Cette solution est presque aussi robuste que celle de l’équilibre en stratégies dominantes au sens où, pour la mettre en œuvre, aucun joueur n’a réellement besoin de savoir avec exactitude ce que son adversaire projette de mettre en œuvre. section{Equilibre de Nash}index{équilibre de Nash} Le jeu suivant n’admet pas de stratégies dominantes et n’est pas à somme nulle. C’est ici qu’intervient la contribution de Nash. L’idée est la suivante : ce qui nous avait plongé dans l’embarras, dans l’analyse du jeu 1.4., c’est le caractère cyclique des anticipations des joueurs : si l’un d’eux anticipe tel comportement de la part de son adversaire, alors il a intérêt à jouer telle stratégie. Or si son adversaire à son tour anticipe ladite stratégie alors son intérêt n’est pas de se conformer à l’anticipation initiale qui avait incité le premier joueur à choisir cette stratégie. Supposons que l’on puisse construire une paire d’anticipations et de stratégies telles que, si chacun anticipe que son adversaire jouera la stratégie qui lui appartient, alors il aura intérêt à jouer la stratégie que son adversaire anticipe. Si par miracle, une telle situation existe, alors les anticipations de nos deux joueurs seraient « autoréalisatrices », au sens où aucun des deux joueurs n’aurait intérêt à ne pas se conformer à l’anticipation de son adversaire. Une telle situation est un équilibre de Nash. -L’important est que chacun anticipe correctement le comportement des autres intervenants, et maximise son paiement espéré compte tenu de ses anticipations. -Keynes (1936) : assimile les marchés financiers à un concours de beauté dont le vainqueur serait celui qui aurait prédit laquelle sera le plus souvent citée comme étant la plus belle : la vraie question n’est pas de savoir laquelle est réellement la plus belle, mais bien de savoir laquelle sera considérée comme la plus belle par les autres membres du jury. Il s’agit pour les jurés de concours de beauté de se coordonner sur un équilibre de Nash. -Exemple : L’unique équilibre de Nash (mixte) est celui où Alice joue la stratégie mixte (2/3,1/3) et Bill (1/3,2/3). Pour le trouver, il suffit de trouver l’unique stratégie mixte d’Alice telle que Bill soit indifférent entre ses deux actions. En effet, si Alice joue (2/3,1/3) le paiement espéré de Bill quand il joue G est 2/3, tout comme lorsqu’il joue D. Etant indifférent entre ses deux actions pures, il jouera lui-même une stratégie mixte qui à son tour, rendra Alice indifférente entre ses deux actions et légitimera sa propre stratégie mixte initiale. Une stratégie mixte qui maximise le paiement espéré d’un joueur étant donné son anticipation sur le comportement de ses adversaires se nomme une meilleure réponseindex{meilleure réponse}. L’unique équilibre de Nash du dilemme des prisonniers coïncide avec son unique équilibre en stratégies dominantes, tandis que l’unique équilibre de Nash du jeu à somme nulle 1.4 est la paire de stratégies prudentes qui induisent la valeur du jeu. Plus généralement, l’unique paiement d’équilibre de Nash d’un jeu somme nulle est égal à sa valeur. Le concept d’équilibre de Nash est donc bien une généralisation de celui d’équilibres en stratégies dominantes et en stratégies prudentes au cas des jeux à somme non nulle ne possédant pas d’équilibre en stratégies dominantes. -Il n’est pas difficile de créer un jeu ne possédant aucun équilibre de Nash : supposez que Bill et Alice doivent choisir un nombre entier quelconque dans Z, et que le vainqueur du jeu soit celui qui aura choisi le plus grand entier. -Un jeu pour lequel les paiements de ses équilibres de Nash sont égaux aux paiements d’équilibre de Nash de son jeu tordu associé et l’ensemble des stratégies d’équilibre de l’un a une intersection non vide avec l’ensemble des stratégies d’équilibre de Nash de l’autre est dit ‘presque strictement concurrentiel’. Pour ce type de jeu, il n’est pas difficile de voir que la logique sous-jacente au calcul des stratégies prudentes d’un jeu à somme nulle peut s’appliquer séparément pour chaque joueur, et donne l’unique équilibre de Nash du jeu. -Le dilemme des prisonniers nous a montré que l’équilibre en stratégies dominantes n’est pas nécessairement compatible avec la poursuite de l’intérêt commun. Un autre exemple montre de manière différente qu’il en va malheureusement de même pour l’équilibre de Nash. Exemple avec le jeu de la chasse du cerf et du lièvre : index{jeu du cerf et lièvre}. Si Bill et Alice encore eux, coopèrent afin de chasser le cerfs, ils auront un paiement symétrique égal à 1. Si, au contraire, un seul d’entre eux aperçoit un lièvre, et délaissent la chasse au cerf, son paiement sera 1/3, et celui de son adversaire sera nul ; si enfin, tous deux se coordonnent pour chasser le lièvre, ils obtiendront le paiement symétrique égal à 1/3. Il y a deux équilibres de Nash purs : (1,1) et (1/3,1/3). --> Un jeu stratégique peut admettre plusieurs équilibres de Nash et que la coopération n’est pas la seule issue d’équilibre envisageable. \ Le problème posé, est distinct de celui du dilemme des prisonniers puisqu’il est possible d’atteindre le paiement Pareto-optimal via un équilibre de Nashindex{ Pareto-optimal}. section{Des enchères au jeu de Bertrand}index{enchères} -Supposons que dans une enchère, le commissaire-priseur décide de ne pas faire payer à celui qui emportera le tableau le prix de sa dernière mise, mais le prix de l’avant dernière mise. Puisqu’il s’agit d’une enchère ascendante, ce prix correspond au prix le plus élevé proposé par ses adversaires de celui qui aura finalement aura le tableau. Quelle stratégie faut-il adopter ? A combien évalueront-ils l’objet à vendre ? Est-il prudent de ne pas proposer de prix supérieur à la valeur subjective que vous attribuez à ce tableau ? La réponse est simple car il existe une stratégie dominante. Elle consiste à proposer un prix exactement égal à la valeur subjective que vous accordez à ce tableau. En effet, si on fixe un prix strictement supérieur, deux choses peut-arriver : ---> ou bien vous n’emportez pas le tableau et dans ce cas vous n’avez rien gagné à surenchérir ---> ou bien vous emportez le tableau, et dans ce cas, vous payez le prix du dernier acheteur à avoir pris la parole avant vous. Ici, deux choses peuvent arriver : --->ou bien ce prix est supérieur à la valeur que vous attribuez au tableau, auquel cas vous y perdez et vous eussiez mieux fait de ne pas surenchérir --->ou bien, ce prix est inférieur, et alors vous auriez pu tout aussi bien proposer comme prix d’achat la vraie valeur que vous accordez à ce tableau : vous auriez remporté l’objet et vous auriez payé le même prix. Par conséquent, jouer honnêtement est une stratégie dominante. - Puisque nous venons de voir que jouer « honnêtement » est une stratégie dominante pour chacun des joueurs, cela implique que si l’on organise une enchère ascendante, au second prix, alors ce sera nécessairement celui qui accordait la plus grande valeur subjective à l’objet mis aux enchères qui l’emportera. Par conséquent, puisqu’un seul individu doit remporter l’objet, l’issue du jeu présentera un caractère de justice qui est assez séduisant. \ Considérons à présent deux entreprises qui se trouvent en concurrenceindex{duôpole de Bertrand} sur le même marché et pour le même produit. C’est l’entreprise qui fixera le prix de vente le plus bas qui emportera la totalité du marché. Envisageons la situation sous l’angle de la théorie des jeux : la stratégie d’un joueur consiste à fixer son prix de vente, et son paiement n’est autre que son profit. Si l’entreprise A fixe un prix $p_A$, son concurrent $B$ aura un intérêt à vendre son produit pour un prix $p_B$ inférieur d’un euro à celui de $A$. Du coup, la meilleure réponse de $A$ à cette réplique de $B$ consiste à baisser son propre pris de deux euros. Mais, l’ayant anticipé, $B$ aura déjà ajusté $p_B$ trois euros plus bas.\ Quel sera l’équilibre de Nash du jeu ? Si l’on se restreint aux stratégies pures, il n’y en a qu’un possible : celui où chacune des deux entreprises fixe un prix égal à son coût marginal de production du produit qu’elle cherche à vendre. Fixer un prix inférieur reviendrait à avoir des pertes, fixer un prix supérieur impliquerait de perdre le marché. C’est donc bien un équilibre de Nash pur. Remarquez que les stratégies d’équilibre de Nash sont faiblement dominées : la stratégie qui consiste à fixer un prix $p>p’$ domine faiblement celle qui consiste à fixer $p’$. Pis encore, toutes les stratégies de ce jeu sont faiblement dominées. Quel est l’intérêt de ce jeu ? De montrer via un modèle simple comment la solution concurrentielle peut émerger comme l’unique équilibre de Nash pur d’un jeu à deux joueurs. section{L’équilibre corrélé} -L’équilibre dit « corrélé » index{L’équilibre corrélé} quand deux joueurs en situation conflictuelle peuvent avoir tout intérêt à recourir aux services d’un médiateur extérieur qui les aide à se coordonner et obtenir un meilleur paiement. Une équilibre corrélé est la donnée d’un mécanisme de corrélation (une probabilité sur le produit des actions des joueurs) et d’un équilibre de Nash du jeu étendu par ce mécanisme. Contrairement aux apparences, l’équilibre corrélé est un équilibre rigoureusement non coopératif. -Considérons le jeu suivant, dont chacun des deux joueurs dispose de trois stratégies : -Il existe un unique équilibre de Nash : (1/3, 1/3, 1/3),(1/3,1/3,1/3). Le paiement espéré est alors de 2. -Supposons qu’Alice et Bill ait recours à un mécanisme externe qui attribue des probabilités aux stratégies apportant des paiements non nuls. Supposons qu’on ait 1/6 pour chaque stratégie : -Ensuite, le mécanisme externe choisit une paire d’actions, informe secrètement chaque joueur de l’action à jouer, mais chaque joueur n’est pas informé de l’autre action à jouer. Quelle que soit la recommandation du mécanisme, chaque époux aura donc intérêt à la suivre. Si Alice reçoit le conseil de jouer la première ligne, elle saura que son époux jouera respectivement la deuxième et la troisième colonnes avec une probabilité ½. Jouer H sera effectivement la meilleure réponse. Or le paiement espéré du jeu, grâce à l’intervention de l’avocat est 3. Cela montre que deux joueurs en situation conflictuelle peuvent avoir tout intérêt à recourir aux services d’un mécanisme externe qui les aide à se coordonner. -Les équilibres de Nash sont des cas particulier d’équilibres corrélés : ceux-là même où les joueurs n’utilisent aucun mécanisme de corrélation. Mais l’exemple précédent montre que l’inclusion est stricte en général. Par contre, le mécanisme peut-être nuisible en terme de bien-être collectif : -Dans ce jeu, l’unique paiement d’équilibre de Nash pur est (2,2) et Pareto-domineindex{Pareto-domine} au sens large tous les paiements d’équilibres corrélés. Pire, (2,2) Pareto-domine strictement l’équilibre corrélé où chaque paire d’action est sélectionnée avec probabilité 1/4. -Si l’équilibre sur lequel tout le monde se coordonne est bien un équilibre corrélé, alors les anticipations des investisseurs seront autoréalisatrices, comme elles le sont par définition, pour tout équilibre de Nash. -Dans le cas d’un jeu a somme nulle, rien n’est à craindre : on peut démontrer facilement que le seul paiement d’équilibre corrélé d’un jeu à somme nulle est égal à la valeur de ce jeu. La raison est que chaque joueur possède une stratégie qui lui garantit le paiement associé à la valeur du jeu qui que fasse son adversaire. Si son paiement espéré lié à un équilibre corrolé était inférieur à cette valeur, il lui suffirait de ne plus tenir compte des conseils de son avocat et de recourir prudemment à sa stratégie de maximumindex{stratégie de maximum} -Le jeu suivant est un exemple de jeu presque strictement compétitif dont les paiements d’équilibres corrélés contiennent strictement les paiements d’équilibre de Nash : -Pour voir qu’il s’agit d’un jeu presque complétement compétitif, il faut écrire le jeu torduindex{jeu tordu} correspondant et à constater que dans ce jeu fictif auxiliaire, les deux premières actions de chaque joueur sont strictement dominées. Dans ces conditions, on voit facilement que le seul paiement d’équilibre de Nash pur du jeu tordu est (0,0). Pour voir qu’il n’existe pas d’autre paiement d’équilibre de Nash mixte, considérons la matrice suivante, dont la première ligne contient la liste de toutes les actions susceptibles d’être jouées avec une probabilité strictement positive par une stratégie mixte quelconque d’Alice, et dont la seconde ligne contient, pour chaque colonne, la liste des meilleurs réponses de Bill correspondant à la stratégie mixte d’Alice appartenant la même colonne. Puisque le jeu est symétrique, on obtiendrait la même matrice en inversant les rôles d’Alice et de Bill. Cela implique que l’on peut éliminer les familles ${A,C},{A,D},{B,C},{B,D},{B,C,D}, {A,C,D}$ de la liste des stratégies pures candidates constituer le support d’une stratégie pures candidates à constituer le support d’une stratégie d’équilibre de Nash mixte. \ On ne tardera pas à voir que l’on peut éliminer $A$ et $B$ lesquelles ne sont jamais les meilleures reponses à une stratégie mixte restante dont le support serait ${a,b}, {a,b,c}, {a,b,d}, {a,b,c,d}$. Elles peuvent être éliminées à leur tour. Pour la même raison, nous pouvons ignorer ${A,B,C},{A,B,D},{A,B,C,D}$. D’où le résultat.







free counters


Opus