• POPULAIRE
• les fenêtres
• antivirus
• antivirus
• Arts graphiques

jeu antagoniste. Résolution de jeux antagonistes matriciels Principes de résolution de jeux antagonistes matriciels

La théorie des jeux est une théorie des modèles mathématiques de prise de décision dans des conditions de conflit ou d'incertitude. On suppose que les actions des parties dans le jeu sont caractérisées par certaines stratégies - des ensembles de règles d'action. Si le gain d'un côté entraîne inévitablement la perte de l'autre, alors on parle de jeux antagonistes. Si l'ensemble de stratégies est limité, alors le jeu s'appelle un jeu matriciel et la solution peut être obtenue très simplement. Les solutions obtenues à l'aide de la théorie des jeux sont utiles pour élaborer des plans face à une éventuelle opposition des concurrents ou à l'incertitude de l'environnement extérieur.

Si le jeu bimatrice est antagoniste, alors la matrice des gains du joueur 2 est entièrement déterminée par la matrice des gains du joueur 1 (les éléments correspondants de ces deux matrices ne diffèrent que par des signes). Par conséquent, un jeu antagoniste bimatrice est complètement décrit par une seule matrice (la matrice des gains du joueur 1) et, par conséquent, est appelé un jeu matriciel.

Ce jeu est antagoniste. Dans celui-ci j \u003d x2 - O, P et R (O, O] \u003d H (P, P) \u003d -I et R (O, P) \u003d R (P, O) \u003d 1, ou sous forme matricielle o p

Soit une classe de jeux Г "miroir fermé", c'est-à-dire chacun de ses jeux contient un jeu isomorphe miroir (puisque tous les jeux qui sont isomorphes miroir à un donné sont isomorphes entre eux, on peut, conformément à ce qui vient d'être dit, parler d'un jeu isomorphe miroir). Une telle classe est, par exemple, la classe de tous les jeux antagonistes ou la classe de tous les jeux matriciels.

En rappelant la définition des situations acceptables dans le jeu antagoniste, on obtient que la situation (X, Y) dans l'extension mixte du jeu matriciel est acceptable pour le joueur 1 si et seulement si pour tout x G x l'inégalité

Le processus de conversion des jeux en jeux symétriques est appelé symétrisation. Nous décrivons ici une méthode de symétrisation. Une autre version fondamentalement différente de la symétrisation sera donnée dans la section 26.7. Ces deux variantes de symétrisation sont en fait applicables à des jeux antagonistes arbitraires, mais ne seront formulées et prouvées que pour des jeux matriciels.

Ainsi, les termes et désignations initiaux de la théorie des jeux antagonistes généraux coïncident avec les termes et désignations correspondants de la théorie des jeux matriciels.

Pour les jeux finis antagonistes (matrices), l'existence de ces extrema a été prouvée par nous au chapitre 10. 1, et tout l'enjeu était d'établir leur égalité, ou du moins de trouver des moyens de surmonter leur inégalité.

La considération des jeux matriciels montre déjà qu'il existe des jeux antagonistes sans situations d'équilibre (et même sans situations d'e-équilibre pour e > 0 suffisamment petit) dans les stratégies initialement données des joueurs.

Mais chaque jeu fini (matrice) peut être étendu à un jeu infini, par exemple, en fournissant à chaque joueur un nombre quelconque de stratégies dominées (voir 22 Ch. 1). De toute évidence, une telle expansion de l'ensemble de stratégies du joueur ne signifiera pas vraiment une expansion de ses possibilités, et son comportement réel dans le jeu étendu ne devrait pas différer de son comportement dans le jeu original. Ainsi, nous avons immédiatement obtenu un nombre suffisant d'exemples de jeux antagonistes infinis qui n'ont pas de points de selle. Il existe aussi des exemples de ce genre.

Ainsi, pour mettre en œuvre le principe du maximin dans un jeu antagoniste infini, il est nécessaire, comme dans le cas d'un jeu fini (matrice), une certaine expansion des capacités stratégiques des joueurs. Pour 96

Comme dans le cas des jeux matriciels (voir chap. 1, 17), pour les jeux antagonistes généraux, un rôle important est joué par le concept de spectre de stratégies mixtes, qui doit cependant recevoir ici une définition plus générale.

Enfin, notez que l'ensemble de toutes les stratégies mixtes du joueur 1 dans un jeu antagoniste arbitraire est, comme dans la matrice

Même un examen des jeux antagonistes montre qu'un grand nombre de ces jeux, y compris les jeux finis, les jeux matriciels ont des situations d'équilibre non pas dans les stratégies pures originales, mais seulement dans les stratégies mixtes généralisées. Par conséquent, pour les jeux généraux, non antagonistes et non coopératifs, il est naturel de rechercher des situations d'équilibre précisément dans les stratégies mixtes.

Ainsi, par exemple (voir Fig. 3.1), nous avons déjà noté que le "Contractant" n'a presque jamais à faire face à l'incertitude comportementale. Mais si l'on prend le niveau conceptuel du type "Administrateur", alors tout est tout le contraire. En règle générale, le principal type d'incertitude auquel "notre décideur" doit faire face est le "conflit". Nous pouvons maintenant préciser qu'il s'agit généralement d'une rivalité non stricte. Un peu moins souvent, "l'Administrateur" prend des décisions dans des conditions "d'incertitude naturelle", et encore plus rarement rencontre-t-il un conflit strict et antagoniste. De plus, le conflit d'intérêts lors de la prise de décisions par "l'Administrateur" se produit, pour ainsi dire, "une fois", c'est-à-dire que dans notre classification, il ne joue souvent qu'un seul (parfois un très petit nombre) de parties du jeu. Les échelles d'évaluation des conséquences sont plus souvent qualitatives que quantitatives. L'indépendance stratégique de l'"Administrateur" est assez limitée. Compte tenu de ce qui précède, on peut affirmer que les situations problématiques de cette ampleur doivent le plus souvent être analysées à l'aide de jeux bi-matrices non coopératifs non antagonistes, qui plus est, en stratégies pures.

Principes de résolution de jeux antagonistes matriciels

En conséquence, il est raisonnable de s'attendre à ce que dans le jeu décrit ci-dessus, les adversaires adhèrent aux stratégies qu'ils ont choisies. Jeu antagoniste matriciel pour lequel max min fiv = min max Aiy>

Cependant, tous les jeux antagonistes matriciels ne sont pas bien définis, et dans le cas général

Ainsi, dans le cas général, pour résoudre un jeu matriciel antagoniste de dimension /uxl, il faut résoudre un couple de problèmes de programmation linéaire duale , aboutissant à un ensemble de stratégies optimales , / et au coût du jeu v.

Comment se définit le jeu antagoniste matriciel de deux personnes ?

Quelles sont les méthodes pour simplifier et résoudre les jeux antagonistes matriciels

Dans le cas d'un jeu de deux personnes, il est naturel de considérer leurs intérêts comme directement opposés - le jeu est antagoniste. Ainsi, le gain d'un joueur est égal à la perte de l'autre (la somme des gains des deux joueurs est nulle, d'où le nom, le jeu à somme nulle). Nous considérerons des jeux dans lesquels chaque joueur dispose d'un nombre fini d'alternatives. La fonction de gain pour un tel jeu à deux personnes à somme nulle peut être donnée sous forme matricielle (sous la forme d'une matrice de gain).

Comme déjà noté, le jeu antagoniste final est appelé matrice.

MATRIX GAMES - une classe de jeux antagonistes dans lesquels deux joueurs participent, et chaque joueur a un nombre fini de stratégies. Si un joueur a m stratégies et l'autre joueur a n stratégies, alors on peut construire une matrice de jeu de dimension txn. Mi. peut ou non avoir un point de selle. Dans le dernier cas

Institut d'ingénierie électrique de Moscou

(Université technique)

Rapport de laboratoire

en théorie des jeux

"Un programme de recherche de stratégies optimales pour un jeu antagoniste apparié donné sous forme matricielle"

Complété par les étudiants

groupe A5-01

Achrapov Daler

Achrapova Olga

Concepts de base de la théorie des jeux

La théorie des jeux conçue pour résoudre situations conflictuelles , c'est à dire. situations dans lesquelles les intérêts de deux ou plusieurs parties poursuivant des objectifs différents entrent en conflit.

Si les objectifs des parties sont directement opposés, alors ils parlent de conflit antagoniste .

Jeu appelé un modèle formalisé simplifié d'une situation de conflit.

Jouer une partie une fois du début à la fin s'appelle faire la fête . Le résultat de la fête est Paiement (ou gagner ).

Le parti est composé de se déplace , c'est à dire. choisir des joueurs parmi un ensemble d'alternatives possibles.

Les mouvements peuvent être personnel et Aléatoire.déménagement personnel , Contrairement à Aléatoire , implique un choix conscient par le joueur d'une option.

Les jeux dans lesquels il y a au moins un coup personnel sont appelés stratégique .

Les jeux dans lesquels tous les mouvements sont aléatoires sont appelés jeux d'argent .

Lorsqu'ils font un geste personnel, ils parlent aussi de stratégies joueur, c'est-à-dire sur la règle ou l'ensemble de règles qui déterminent le choix du joueur. Dans le même temps, la stratégie doit être globale, c'est-à-dire le choix doit être déterminé pour toute situation possible au cours du jeu.

Défi de la théorie des jeux– trouver les stratégies optimales des joueurs, c'est-à-dire stratégies qui leur procurent le maximum de gain ou le minimum de perte.

Classification des modèles de la théorie des jeux

Jeu n les personnes sont généralement appelées, où
est l'ensemble des stratégies du i-ème joueur,
- paiement du jeu.

Conformément à cette désignation, la classification suivante des modèles de la théorie des jeux peut être proposée :

Discret (ensembles de stratégies discret)

Final

Sans fin

Continu (ensembles de stratégies continu)

Sans fin

n personnes (
)

Coalition (coopérative)

Non coopératif (non coopératif)

2 personnes (jumelées)

Antagonistes (jeux à somme nulle)

(les intérêts des parties sont opposés, c'est-à-dire que la perte d'un joueur est égale au gain de l'autre)

Non antagoniste

Avec une information complète (si le joueur effectuant un coup personnel connaît tout l'historique du jeu, c'est-à-dire tous les coups de l'adversaire)

Avec des informations incomplètes

Avec un montant nul (le paiement total est nul)

Avec une somme non nulle

Aller simple (loteries)

multi-voies

Représentation matricielle d'un jeu antagoniste apparié

Dans ce tutoriel, nous considérerons jeux antagonistes de deux personnes donnée sous forme matricielle. Cela signifie que nous connaissons l'ensemble des stratégies du premier joueur (joueur UN){ UN je }, je = 1,…, m et l'ensemble des stratégies du second joueur (joueur B){ B j }, j = 1,..., n, et la matrice UN = || un ij || les gains du premier joueur. Puisqu'on parle d'un jeu antagoniste, on suppose que le gain du premier joueur est égal à la perte du second. On considère que l'élément de matrice un ij est le gain du premier joueur lorsqu'il choisit une stratégie UN je et la réponse du deuxième joueur avec la stratégie B j. Nous appellerons un tel jeu
, où m - nombre de stratégies de joueurs MAIS,n - nombre de stratégies de joueurs À. De manière générale, il peut être représenté par le tableau suivant :

Exemple 1

Comme exemple simple, considérons un jeu dans lequel le jeu se compose de deux coups.

1er coup: Joueur MAIS choisit l'un des nombres (1 ou 2) sans informer l'adversaire de son choix.

2e coup: Joueur À sélectionne l'un des nombres (3 ou 4).

Résultat: Sélection du joueur MAIS et À additionner. Si la somme est paire, alors À paie sa valeur au joueur MAIS, si impair - vice versa, MAIS paie le joueur À.

Ce jeu peut être représenté comme
de la manière suivante :

Il est facile de voir que ce jeu est antagoniste, en plus, c'est un jeu avec des informations incomplètes, puisque joueur À, faisant un coup personnel, on ne sait pas quel choix le joueur a fait MAIS.

Comme indiqué ci-dessus, la tâche de la théorie des jeux est de trouver les stratégies optimales des joueurs, c'est-à-dire stratégies qui leur procurent le maximum de gain ou le minimum de perte. Ce processus est appelé décision de jeu .

Lors de la résolution d'un jeu sous forme matricielle, il faut vérifier le jeu pour la présence point de selle . Pour cela, deux valeurs sont introduites :

est la borne inférieure du prix du jeu, et

est l'estimation supérieure du prix du jeu.

Le premier joueur choisira très probablement la stratégie dans laquelle il obtiendra le gain maximum parmi toutes les réponses possibles du second joueur, et le second, au contraire, choisira celle qui minimise sa propre perte, c'est-à-dire possible victoire du premier.

On peut prouver que α ≤ V ≤ β , où V–prix du jeu , c'est-à-dire le gain probable du premier joueur.

Si la relation α = β = V, alors ils disent que le jeu a un point de selle
, et résolu en stratégies pures . En d'autres termes, il existe plusieurs stratégies
, donnant au joueur MAISV.

Exemple 2

Revenons au jeu que nous avons considéré dans l'exemple 1 et vérifions la présence d'un point de selle.

Pour ce jeu
= -5,
= 4,
, par conséquent, il n'a pas de point de selle.

Encore une fois, notez que ce jeu est un jeu d'information incomplet. Dans ce cas, vous ne pouvez que conseiller le joueur MAIS choisir une stratégie , car dans ce cas, il peut cependant obtenir le plus gros gain, à condition que le joueur choisisse À stratégies .

Exemple 3

Apportons quelques modifications aux règles du jeu de l'exemple 1. Donnons au joueur À informations sur la sélection des joueurs MAIS. Alors À Il existe deux stratégies supplémentaires :

- une stratégie bénéfique pour MAIS. Si choix A-1, alors À choisit 3 si choix A-2, alors À choisit 4 ;

- une stratégie qui n'est pas bénéfique pour MAIS. Si choix A-1, alors À choisit 4 si choix A-2, alors À choisit 3.

Ce jeu regorge d'informations.

Dans ce cas
= -5,
= -5,
, donc le jeu a un point de selle
. Ce point selle correspond à deux paires de stratégies optimales :
et
. Prix ​​du jeu V= -5. Il est évident que pour MAIS ce jeu ne sert à rien.

Les exemples 2 et 3 illustrent bien le théorème suivant, prouvé en théorie des jeux :

Théorème 1

Chaque jeu antagoniste apparié avec des informations parfaites est résolu en stratégies pures.

Ce. Le théorème 1 dit que tout jeu à deux avec des informations parfaites a un point de selle et qu'il existe une paire de stratégies pures
, donnant au joueur MAIS gain durable égal au prix du jeu V.

En cas d'absence de point de selle, le soi-disant stratégies mixtes :, où p je etq j sont les probabilités de choisir des stratégies UN je et B j les premier et deuxième joueurs, respectivement. La solution du jeu dans ce cas est une paire de stratégies mixtes
maximiser l'espérance mathématique du prix du jeu.

Une généralisation du théorème 1 au cas d'un jeu avec des informations incomplètes est le théorème suivant :

Théorème 2

Tout jeu antagoniste apparié a au moins une solution optimale, c'est-à-dire une paire de stratégies mixtes dans le cas général
, donnant au joueur MAIS gain durable égal au prix du jeu V, en outre α ≤ V ≤ β .

Dans un cas particulier, pour un jeu avec un point de selle, la solution dans les stratégies mixtes ressemble à une paire de vecteurs dans lesquels un élément est égal à un et les autres sont égaux à zéro.

Le cas le plus simple, élaboré en détail dans la théorie des jeux, est un jeu de paires finies à somme nulle (un jeu antagoniste de deux personnes ou de deux coalitions). Considérez ce jeu g, dans lequel deux joueurs MAIS et À, ayant des intérêts opposés : le gain de l'un est égal à la perte de l'autre. Depuis le gain du joueur MAIS est égal au gain du joueur Avec de signe contraire, on ne peut s'intéresser qu'au gain un joueur MAIS. Naturellement, MAIS veut maximiser et À - minimiser un. Pour simplifier, identifions-nous mentalement à l'un des joueurs (que ce soit MAIS) et nous l'appellerons "nous", et le joueur À -« adversaire » (bien sûr, pas d'avantages réels pour MAIS n'en découle pas). Ayons t stratégies possibles MAIS 1 , UN 2 , ..., MAIS m, et l'ennemi n stratégies possibles À 1 , À 2 , ..; À n(un tel jeu s'appelle un jeu t × n). Dénoter un ij notre gain si nous utilisons la stratégie UN je , et l'ennemi est une stratégie B j .

Tableau 26.1

Supposons que pour chaque couple de stratégies A<, À, gain (ou gain moyen) un, j nous savons. Ensuite, en principe, il est possible de constituer un tableau rectangulaire (matrice), qui liste les stratégies des joueurs et les gains correspondants (voir tableau 26.1).

Si un tel tableau est compilé, alors on dit que le jeu g réduit à une forme matricielle (en soi, amener le jeu à une telle forme peut déjà être une tâche difficile, et parfois presque impossible, en raison du grand nombre de stratégies). Notez que si le jeu est réduit à une forme matricielle, alors le jeu à plusieurs coups est en fait réduit à un jeu à un coup - le joueur n'est tenu de faire qu'un seul coup : choisir une stratégie. On notera brièvement la matrice du jeu ( un ij).

Prenons un exemple de jeu g(4×5) sous forme matricielle. A notre disposition (au choix) quatre stratégies, l'ennemi a cinq stratégies. La matrice de jeu est donnée dans le tableau 26.2

Réfléchissons à quelle stratégie nous (le joueur MAIS) tirer profit? La matrice 26.2 a le gain alléchant "10" ; nous sommes amenés à choisir une stratégie MAIS 3 , à laquelle nous aurons cette "friandise". Mais attendez, l'ennemi n'est pas stupide non plus ! Si nous choisissons une stratégie MAIS 3 , lui, pour nous contrarier, choisira une stratégie À 3 , et nous obtenons un gain misérable "1". Non, choisissez une stratégie MAIS 3 c'est interdit! Comment être? Évidemment, selon le principe de prudence (et c'est le grand principe de la théorie des jeux), il faut choisir

Tableau 26.2

la stratégie qui notre gain minimum est maximum. C'est ce qu'on appelle le "principe minimax": agissez de manière à ce que, avec le pire comportement de l'ennemi pour vous, vous obteniez le gain maximum.

Nous réécrivons le tableau 26.2 et dans la colonne supplémentaire de droite nous inscrivons la valeur minimale du gain dans chaque ligne, (ligne minimum) ; désignons-le pour je-ième ligne α je(voir tableau 26.3).

Tableau 26.3

De toutes les valeurs α je(colonne de droite) la plus grande (3) est mise en surbrillance. Cela correspond à la stratégie UN quatre. Ayant choisi cette stratégie, nous pouvons en tout cas être sûrs que (pour tout comportement de l'ennemi) nous ne gagnerons pas moins de 3. Cette valeur est notre gain garanti ; en faisant attention, on ne peut pas avoir moins que ça (j'en aurai peut-être plus). Ce gain est appelé le prix le plus bas du jeu (ou "maximin" - le maximum des gains minimum). Nous le noterons un. Dans notre cas α = 3.

Prenons maintenant le point de vue de l'ennemi et plaidons pour lui. Ce n'est pas une sorte de pion, mais aussi raisonnable ! En choisissant une stratégie, il aimerait donner moins, mais il doit compter sur notre comportement, qui est le pire pour lui. S'il choisit une stratégie À 1 , nous lui répondrons MAIS 3 , et il donnera 10; s'il choisit B 2 - nous lui répondrons MAIS 2 , et il donnera 8, etc. Nous ajoutons une ligne inférieure supplémentaire au tableau 26.3 et y écrivons les maximums des colonnes β j. Évidemment, un adversaire prudent devrait choisir la stratégie qui minimise cette valeur (la valeur correspondante de 5 est mise en évidence dans le tableau 26.3). Cette valeur de β est la valeur du gain, plus qu'un adversaire raisonnable ne nous donnera certainement pas. C'est ce qu'on appelle le prix supérieur du jeu (ou "minimax" - le minimum des gains maximum). Dans notre exemple, β = 5 et est atteint avec la stratégie de l'adversaire B 3 .

Alors, sur la base du principe de prudence (la règle de la réassurance « toujours compter sur le pire ! »), il faut choisir une stratégie MAIS 4 , et l'ennemi - stratégie À 3 . De telles stratégies sont appelées "minimax" (suivant le principe minimax). Tant que les deux parties dans notre exemple s'en tiennent à leurs stratégies minimax, le gain sera un 43 = 3.

Imaginons maintenant un instant que nous ayons appris que l'ennemi poursuit une stratégie À 3 . Allez, punissons-le pour ça et choisissons une stratégie MAIS 1 - nous en aurons 5, ce qui n'est pas si mal. Mais après tout, l'ennemi n'est pas non plus un raté; faites-lui savoir que notre stratégie MAIS 1 ; il est aussi rapide à choisir À 4 , réduire notre gain à 2, etc. (les partenaires « se sont précipités sur les stratégies »). En un mot, les stratégies minimax dans notre exemple instable par rapport àà des informations sur le comportement de l'autre partie ; ces stratégies n'ont pas la propriété d'équilibre.

Est ce toujours comme ça? Non pas toujours. Prenons un exemple avec la matrice donnée dans le tableau 26.4.

Dans cet exemple, le prix le plus bas du jeu est égal au prix le plus élevé : α = β = 6. Qu'en résulte-t-il ? Stratégies du joueur Minimax MAIS et À sera durable. Tant que les deux joueurs s'y tiennent, le gain est de 6. Voyons ce qui se passe si nous (MAIS) sachez que l'ennemi (À)

Tableau 26.4

s'en tient à la stratégie B 2 ? Et exactement rien ne changera. Parce que tout écart par rapport à la stratégie MAIS 2 ne peut qu'empirer notre situation. De même, les informations reçues par l'ennemi ne le feront pas reculer de sa stratégie. À 2 . Paire de stratégies MAIS 2 , B 2 possède la propriété d'équilibre (une paire de stratégies équilibrée), et le gain (dans notre cas, 6) obtenu avec cette paire de stratégies est appelé le « point de selle de la matrice » 1). Un signe de la présence d'un point de selle et d'une paire équilibrée de stratégies est l'égalité des prix inférieurs et supérieurs du jeu ; la valeur commune de α et β est appelée le prix du jeu. Nous allons l'étiqueter v:

α = β = v

Stratégies UN je , B j(dans ce cas MAIS 2 , À 2 ), pour lesquelles ce gain est atteint sont appelées stratégies pures optimales, et leur totalité est appelée solution du jeu. Dans ce cas, on dit que le jeu lui-même est résolu en stratégies pures. Des deux côtés MAIS et À on peut indiquer leurs stratégies optimales sous lesquelles leur position est la meilleure possible. Qu'est-ce qu'un joueur MAIS dans ce cas, 6 victoires, et le joueur À - perd 6, - eh bien, ce sont les conditions du jeu : elles sont bénéfiques pour MAIS et désavantageux pour À

1) Le terme "point de selle" est tiré de la géométrie - c'est le nom du point sur la surface, où le minimum le long d'une coordonnée et le maximum le long de l'autre sont atteints simultanément.

Le lecteur peut se poser une question : pourquoi les stratégies optimales sont-elles dites « pures » ? En regardant un peu plus loin, répondons à cette question : il existe des stratégies "mixtes", qui consistent dans le fait que le joueur utilise non pas une stratégie, mais plusieurs, en les alternant au hasard. Donc, si nous autorisons, en plus des stratégies pures, également des stratégies mixtes, tout fin du jeu a une solution - un point d'équilibre. Mais nous parlons toujours de l'atome.

La présence d'un point sellier dans le jeu est loin d'être la règle, c'est plutôt l'exception. La plupart des jeux n'ont pas de point de selle. Cependant, il existe une variété de jeux qui ont toujours un point de selle et, par conséquent, sont résolus en stratégies pures. Ce sont les soi-disant "jeux avec des informations complètes". Un jeu avec une étagère d'informations est un jeu dans lequel chaque joueur connaît l'historique complet de son développement, c'est-à-dire les résultats de tous les coups précédents, personnels et aléatoires, à chaque coup personnel. Des exemples de jeux avec des informations complètes sont les dames, les échecs, le tic-tac-toe, etc.

En théorie des jeux, il est prouvé que chaque jeu avec des informations complètes a un point de selle, et peut donc être résolu en stratégies pures. Dans chaque jeu avec une information parfaite, il existe une paire de stratégies optimales qui donne un gain stable égal à la chaîne du jeu v. Si un tel jeu se compose uniquement de mouvements personnels, alors lorsque chaque joueur applique sa propre stratégie optimale, il doit se terminer de manière bien définie - avec un gain égal au prix du jeu. Ainsi, si la solution du jeu est connue, le jeu lui-même perd son sens !

Prenons un exemple élémentaire d'un jeu avec des informations complètes : deux joueurs placent alternativement des nickels sur une table ronde, en choisissant arbitrairement la position du centre de la pièce (le chevauchement mutuel des pièces n'est pas autorisé). Le gagnant est celui qui met le dernier centime (quand il n'y a pas de place pour les autres). Il est facile de voir que le résultat de ce jeu est essentiellement couru d'avance. Il existe une certaine stratégie qui garantit que le joueur qui met la pièce en premier gagne. A savoir, il doit d'abord placer un nickel au centre de la table, puis répondre à chaque coup de l'adversaire par un coup symétrique. De toute évidence, quel que soit le comportement de l'adversaire, il ne peut éviter de perdre. La situation est exactement la même avec les échecs et les jeux avec des informations complètes en général : chacun d'eux, écrit sous forme de matrice, a un point de selle, et donc la solution est en stratégies pures, et, par conséquent, n'a de sens que tant que cela solution non trouvée. Disons qu'une partie d'échecs est soit toujours se termine par la victoire des Blancs, ou toujours - les noirs gagnent, ou toujours - un match nul, seulement par quoi exactement - nous ne savons pas encore (heureusement pour les amateurs d'échecs). Ajoutons encore une chose : nous ne le saurons guère dans un avenir prévisible, car le nombre de stratégies est si énorme qu'il est extrêmement difficile (voire impossible) de réduire le jeu à une forme matricielle et d'y trouver un point de selle.

Demandons-nous maintenant que faire si le jeu n'a pas de point selle : α ≠ β ? Eh bien, si chaque joueur est obligé d'en choisir une - la seule stratégie pure, alors il n'y a rien à faire: il faut être guidé par le principe du minimax. Une autre chose est s'il est possible de "mélanger" un ensemble de stratégies, alterner au hasard avec certaines probabilités. L'utilisation de stratégies mixtes est conçue de cette manière : le jeu est répété plusieurs fois ; avant chaque partie du jeu, lorsque le joueur reçoit un coup personnel, il "confie" son choix au hasard, "lance au sort", et reprend la stratégie qui est tombée (on sait déjà organiser le lot du chapitre précédent ).

Les stratégies mixtes dans la théorie des jeux sont un modèle de tactique variable et flexible, lorsqu'aucun des joueurs ne sait comment l'adversaire se comportera dans un jeu donné. Cette tactique (bien que généralement sans aucune justification mathématique) est souvent utilisée dans les jeux de cartes. Notons en même temps que le meilleur moyen de cacher votre comportement à l'ennemi est de lui donner un caractère aléatoire et, donc, de ne pas savoir à l'avance ce que vous ferez.

Parlons donc des stratégies mixtes. On notera les stratégies mixtes des joueurs MAIS et À respectivement S A = ( p 1 , R 2 , ..., p m), S B = (q 1 , q 2 , …, q n), où p 1 , p 2 , …, p m(formant un total de un) - les probabilités que le joueur utilise MAIS stratégies MAIS 1 , UN 2 ,… , UN m ; q 1 , q 2 , …, q n- probabilités d'utilisation par le joueur À stratégies À 1 , À 2 , ..., À n . Dans un cas particulier, lorsque toutes les probabilités, sauf une, sont égales à zéro, et que celle-ci est égale à un, la stratégie mixte se transforme en stratégie pure.

Il existe un théorème de base de la théorie des jeux : tout jeu fini à somme nulle pour deux personnes a au moins une solution - paire de stratégies optimales, généralement mixtes
et prix correspondant v.

Paire de stratégies optimales
formant la solution du jeu a la propriété suivante : si l'un des joueurs s'en tient à sa stratégie optimale, alors il ne peut être avantageux pour l'autre de s'écarter de la sienne. Ce couple de stratégies forme une sorte d'équilibre dans le jeu : l'un veut tourner le gain au maximum, l'autre au minimum, chacun tire dans son sens, et, avec un comportement raisonnable des deux, un équilibre et une stabilité. gain sont établis. v. Si un v > 0, alors le jeu nous est profitable si v< 0 - pour l'ennemi; à v= 0 le jeu est « équitable », également bénéfique pour les deux participants.

Considérons un exemple de jeu sans point de selle et donnons (sans preuve) sa solution. Le jeu est le suivant : deux joueurs MAIS et À en même temps et sans dire un mot montrer un, deux ou trois doigts. Le gain est décidé par le nombre total de doigts : s'il est pair, gagne MAIS et reçoit de À un montant égal à ce nombre ; si impair, alors vice versa MAIS paie À un montant égal à ce nombre. Que doivent faire les joueurs ?

Créons une matrice de jeu. Dans un jeu, chaque joueur dispose de trois stratégies : montrer un, deux ou trois doigts. La matrice 3×3 est donnée dans le tableau 26.5 ; la colonne supplémentaire de droite montre les minima de ligne et la ligne supplémentaire du bas montre les maxima de colonne.

Le prix inférieur du jeu α = - 3 et correspond à la stratégie UN 1 . Cela signifie qu'avec un comportement raisonnable et prudent, nous garantissons que nous ne perdrons pas plus de 3. Petite consolation, mais toujours meilleure que, disons, une victoire de 5, qui se produit dans certaines cellules de la matrice. Mauvais pour nous, le joueur MAIS... Mais consolons-nous :

la position de l'adversaire semble encore pire : le coût le plus bas du jeu est β = 4, c'est-à-dire qu'avec un comportement raisonnable, il nous en donnera au moins 4. En général, la position n'est pas très bonne - ni pour un ni pour le autre côté. Mais voyons si cela peut être amélioré ? Il s'avère que vous pouvez. Si chaque camp utilise non pas une stratégie pure, mais une stratégie mixte, dans laquelle

Tableau 26.5

le premier et le troisième entrent avec probabilité 1/4, et le second - avec probabilité 1/2, c'est-à-dire

alors le gain moyen sera régulièrement égal à zéro (ce qui signifie que le jeu est "équitable" et également bénéfique pour les deux parties). Stratégies
forment une solution au jeu, et son prix v= 0. Comment avons-nous trouvé cette solution ? C'est une question différente. Dans la section suivante, nous montrons comment les jeux finis sont généralement résolus.

Considérons un jeu de paires finies à somme nulle. Dénoter par un gain du joueur UN, et à travers b- victoire du joueur B. Car un = –b, alors lors de l'analyse d'un tel jeu, il n'est pas nécessaire de considérer ces deux nombres - il suffit de considérer le gain de l'un des joueurs. Que ce soit, par exemple, UN. Dans ce qui suit, pour des raisons de commodité de présentation, le côté UN nous nommerons conditionnellement " nous« et le côté B – "ennemi".

Ayons m stratégies possibles UN 1 , UN 2 , …, Suis, et l'ennemi n stratégies possibles B 1 , B 2 , …, B n(un tel jeu s'appelle un jeu m×n). Supposons que chaque camp ait choisi une certaine stratégie : nous avons choisi ai, adversaire B j. Si le jeu ne consiste qu'en mouvements personnels, alors le choix des stratégies ai et B j détermine de manière unique le résultat du jeu - notre gain (positif ou négatif). Notons ce gain comme aij(gagner quand on choisit la stratégie ai, et l'ennemi - stratégies B j).

Si le jeu contient, en plus de mouvements aléatoires personnels, alors le gain pour une paire de stratégies ai, B j est une variable aléatoire qui dépend des résultats de tous les mouvements aléatoires. Dans ce cas, l'estimation naturelle du gain espéré est espérance mathématique d'une victoire aléatoire. Par commodité, nous désignerons par aijà la fois le gain lui-même (dans un jeu sans mouvements aléatoires) et son espérance mathématique (dans un jeu avec des mouvements aléatoires).

Supposons que nous connaissions les valeurs aij pour chaque paire de stratégies. Ces valeurs peuvent être écrites sous la forme d'une matrice dont les lignes correspondent à nos stratégies ( ai), et les colonnes montrent les stratégies de l'adversaire ( B j):

Une telle matrice est appelée matrice des gains du jeu ou simplement matrice de jeu.

Notez que la construction d'une matrice de gains pour les jeux avec un grand nombre de stratégies peut être une tâche difficile. Par exemple, pour jeu d'échecs le nombre de stratégies possibles est si grand que la construction de la matrice des gains est pratiquement impossible. Cependant, en principe, tout jeu fini peut être réduit à une forme matricielle.

Envisager Exemple 1 Jeu antagoniste 4×5. Nous avons quatre stratégies à notre disposition, l'ennemi a cinq stratégies. La matrice du jeu est la suivante :

Quelle stratégie devrions-nous (c'est-à-dire, le joueur UN) utiliser? Quelle que soit la stratégie que nous choisissons, un adversaire raisonnable y répondra avec la stratégie pour laquelle notre gain sera minime. Par exemple, si nous choisissons la stratégie UN 3 (tenté par une victoire de 10), l'adversaire choisira une stratégie en réponse B 1 , et notre gain ne sera que de 1. Évidemment, selon le principe de prudence (et c'est le grand principe de la théorie des jeux), il faut choisir la stratégie dans laquelle notre gain minimum est maximum.

Dénoter par un je valeur de gain minimum pour la stratégie ai:

et ajoutez une colonne contenant ces valeurs à la matrice du jeu :

Lors du choix d'une stratégie, il faut choisir celle dont la valeur un je maximum. Notons cette valeur maximale par α :

Évaluer α appelé prix du jeu plus bas ou maximin(gain maximum minimum). Stratégie du joueur UN correspondant au maximum α , est appelé stratégie maximale.

Dans cet exemple, le maximin α est égal à 3 (la cellule correspondante dans le tableau est surlignée en gris), et la stratégie maximin est UN quatre. Après avoir choisi cette stratégie, nous pouvons être sûrs que pour tout comportement de l'ennemi, nous gagnerons pas moins de 3 (et peut-être plus avec le comportement "déraisonnable" de l'ennemi). Cette valeur est notre minimum garanti, que nous pouvons assurer pour nous-mêmes, en adhérant à la stratégie la plus prudente ("réassurance").

Maintenant, nous allons effectuer un raisonnement similaire pour l'ennemi B B UN B 2 - nous lui répondrons UN .

Dénoter par βj UN B) pour la stratégie ai:

βj β :

7. QU'EST-CE QUE LE JEU DE VALEUR SUPÉRIEURE Maintenant, nous allons effectuer un raisonnement similaire pour l'adversaire B. Il a intérêt à minimiser notre gain, c'est-à-dire à nous donner moins, mais il doit compter sur notre comportement, qui est le pire pour lui. Par exemple, s'il choisit la stratégie B 1 , alors nous lui répondrons par une stratégie UN 3 , et il nous donnera 10. S'il choisit B 2 - nous lui répondrons UN 2 , et il donnera 8, et ainsi de suite. Évidemment, un adversaire prudent doit choisir la stratégie dans laquelle notre gain maximum sera minimum.

Dénoter par βj les valeurs maximales dans les colonnes de la matrice des gains (le gain maximum du joueur UN, ou, ce qui revient au même, la perte maximale du joueur B) pour la stratégie ai:

et ajoutez une ligne contenant ces valeurs à la matrice du jeu :

En choisissant une stratégie, l'ennemi préférera celle dont la valeur βj le minimum. Notons-le par β :

Évaluer β appelé meilleur prix du jeu ou minimax(gain minimum maximum). La stratégie de l'adversaire (du joueur) correspondant au minimax B), est appelé stratégie minimax.

Minimax est la valeur du gain, plus qu'un adversaire raisonnable ne nous donnera certainement pas (autrement dit, un adversaire raisonnable ne perdra pas plus de β ). Dans cet exemple, minimax β est égal à 5 ​​(la cellule correspondante dans le tableau est surlignée en gris) et il est réalisé avec la stratégie de l'adversaire B 3 .

Alors, selon le principe de prudence ("toujours s'attendre au pire !"), il faut choisir une stratégie UN 4 , et l'ennemi - une stratégie B 3 . Le principe de prudence est fondamental en théorie des jeux et s'appelle principe minimax.

Envisager exemple 2. Laissez les joueurs UN et À l'un des trois nombres s'écrit simultanément et indépendamment l'un de l'autre : soit « 1 », soit « 2 », soit « 3 ». Si la somme des nombres écrits est paire, alors le joueur B paie le joueur UN Cette somme. Si le montant est impair, alors le joueur paie ce montant UN joueur À.

Écrivons la matrice des gains du jeu et trouvons les prix inférieurs et supérieurs du jeu (le numéro de stratégie correspond au numéro écrit) :

Joueur UN doit adhérer à la stratégie maximin UN 1 pour gagner au moins -3 (c'est-à-dire perdre au plus 3). Stratégie du joueur Minimax B aucune des stratégies B 1 et B 2 , ce qui garantit qu'il ne donnera pas plus de 4.

Nous obtiendrons le même résultat si nous écrivons la matrice des gains du point de vue du joueur À. En fait, cette matrice est obtenue en transposant la matrice construite du point de vue du joueur UN, et en changeant les signes des éléments à l'opposé (puisque le gain du joueur UN est la perte du joueur À):

Sur la base de cette matrice, il s'ensuit que le joueur B doit suivre l'une des stratégies B 1 et B 2 (et alors il ne perdra pas plus de 4), et le joueur UN- stratégies UN 1 (et alors il ne perdra pas plus de 3). Comme vous pouvez le voir, le résultat est exactement le même que celui obtenu ci-dessus, donc l'analyse n'a pas d'importance du point de vue de quel joueur nous la menons.

8 QU'EST-CE QU'UN JEU DE VALEUR.

9. EN QUOI CONSISTE LE PRINCIPE MINIMAX. 2. Prix inférieur et supérieur du jeu. Principe minimax

Considérons un jeu matriciel du type avec matrice de gains

Si le joueur MAIS choisira une stratégie Un je, alors tous ses gains possibles seront des éléments je-ème ligne de la matrice DE. Le pire pour un joueur MAIS cas où le joueur À applique une stratégie adaptée à le minimumélément de cette ligne, le gain du joueur MAIS sera égal au nombre.

Par conséquent, afin d'obtenir le gain maximum, le joueur MAIS vous devez choisir l'une des stratégies dont le nombre maximum.

Le problème d'aide à la décision, considéré dans le cadre de l'approche système, contient trois composantes principales : le système, le sous-système de contrôle et l'environnement y sont identifiés. Passons maintenant à l'étude des problèmes de prise de décision, dans lesquels le système est affecté non pas par un, mais par plusieurs sous-systèmes de contrôle, chacun ayant ses propres objectifs et possibilités d'action. Cette approche de la prise de décision est appelée théorie des jeux, et les modèles mathématiques des interactions correspondantes sont appelés Jeux. En raison de la différence d'objectifs des sous-systèmes de contrôle, ainsi que de certaines restrictions sur la possibilité d'échanger des informations entre eux, ces interactions sont de nature conflictuelle. Par conséquent, tout jeu est un modèle mathématique de conflit. Nous nous limitons au cas où il y a deux sous-systèmes de contrôle. Si les objectifs des systèmes sont opposés, le conflit est dit antagoniste, et le modèle mathématique d'un tel conflit est appelé jeu antagoniste..

Dans la terminologie de la théorie des jeux, le 1er sous-système de contrôle est appelé joueur 1, 2e sous-système de contrôle - joueur 2, ensembles

leurs actions alternatives sont appelées ensembles de stratégies ces joueurs. Laisser X- ensemble de stratégies du joueur 1, Oui- de nombreuses stratégies

joueur 2. L'état du système est uniquement déterminé par le choix des actions de contrôle par les sous-systèmes 1 et 2, c'est-à-dire le choix des stratégies

X∈X et y∈Oui. Laisser F(X,y) - estimation de l'utilité pour le joueur 1 de cet état

le système auquel il passe lorsque le joueur 1 choisit une stratégie X et

stratégie du joueur 2 à. Numéro F(X,y) est appelé gagnant joueur 1 dans la situation ( X,y), et la fonction F- fonction de gain du joueur 1. Victoire du joueur

1 est également la perte du joueur 2, c'est-à-dire la valeur que le premier joueur cherche à augmenter et la seconde à réduire. C'est ce que c'est

manifestation du caractère antagoniste du conflit : les intérêts des joueurs sont complètement opposés (ce que l'un gagne, l'autre perd).

Un jeu antagoniste est naturellement mis en place par le système G=(X, Y, F).

Notons que formellement le jeu antagoniste se pose en fait de la même manière que le problème de la prise de décision dans des conditions d'incertitude - si

identifier le sous-système de commande 2 avec l'environnement. La différence fondamentale entre le sous-système de contrôle et l'environnement est que

le comportement du premier est intentionnel. Si, lors de l'élaboration d'un modèle mathématique d'un conflit réel, nous avons une raison (ou une intention) de considérer l'environnement comme un adversaire dont le but est d'amener

nous le mal maximum, alors une telle situation peut être représentée comme un jeu antagoniste. En d'autres termes, le jeu antagoniste peut être interprété comme un cas extrême de la ZPR dans des conditions d'incertitude,

caractérisée par le fait que l'environnement est perçu comme un adversaire avec un but. En même temps, il faut limiter les types d'hypothèses sur le comportement de l'environnement.

La plus étayée ici est l'hypothèse d'une extrême prudence, lorsque, au moment de prendre une décision, nous nous appuyons sur le pire scénario possible pour agir sur l'environnement.

Définition. Si un X et Oui sont finis, alors le jeu antagoniste est appelé matrice. Dans le jeu matriciel, on peut supposer que X={1,…,n},

Oui={1,…,m) et met aj=F(je,j). Ainsi, le jeu matriciel est entièrement déterminé par la matrice A=(aij), je=1,…,n, j=1,…,m.

Exemple 3.1. Jeu avec deux doigts.

Deux personnes en même temps montrent un ou deux doigts et appellent le numéro 1 ou 2, ce qui, selon l'orateur, signifie le numéro

doigts montrés aux autres. Une fois les doigts montrés et les numéros nommés, les gains sont distribués selon les règles suivantes :

si les deux ont deviné ou les deux n'ont pas deviné combien de doigts leur adversaire a montré, le gain de chacun est égal à zéro ; si un seul a deviné correctement, alors l'adversaire paie au devineur le montant d'argent proportionnel au nombre total de montrés

Il s'agit d'un jeu matriciel antagoniste. Chaque joueur a quatre stratégies : 1- montrer 1 doigt et dire 1, 2- montrer 1 doigt et dire 2, 3-

montrez 2 doigts et dites 1, 4 - montrez 2 doigts et dites 2. Ensuite, la matrice des gains A=(aij), je= 1,…, 4, j= 1,…, 4 est défini comme suit :

a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 sinon.

Exemple 3.2. Jeu discret de type duel.

Les tâches de type duel décrivent, par exemple, la lutte de deux joueurs,

chacun d'eux souhaite effectuer une action ponctuelle (la mise sur le marché d'un lot de marchandises, une demande d'achat lors d'une vente aux enchères) et choisit un moment pour cela. Laissez les joueurs se déplacer les uns vers les autres sur n pas. Après chaque pas effectué, le joueur peut ou non tirer sur l'adversaire. Chaque personne ne peut avoir qu'un seul coup. On pense que la probabilité de toucher l'ennemi si vous avancez de k n =5 a la forme