Jeux booléens statiques et représentation compacte de préférences

Notations et rappels de logique propositionnelle

Soit V = {a,b,…} un ensemble fini de variables propositionnelles et LV le langage propositionnel construit à partir de V, des connecteurs habituels et des constantes booléennes ⊤ (vrai) et ⊥ (faux). Les formules de LV seront notées ϕ,ψ etc. Un littéral est, soit une variable de V, soit sa négation. Une conjonction finie de littéraux est appelée terme. On note Lit(α) l’ensemble des littéraux formant le terme α. Une formule ϕ est en DNF si c’est une disjonction de termes. 2 V est l’ensemble des interprétations pour V avec la convention suivante : soit M une interprétation pour V et pour tout x ∈ V, M donne la valeur vrai à x si x ∈ M et faux sinon. Soit M une interprétation pour V et ψ ∈ LV , la conséquence logique M |= ψ est définie de la manière usuelle. Soit X ⊆ V. 2X est l’ensemble des X-interprétations. Une interprétation partielle de LV est une X-interprétation pour X ⊆V. Les interprétations partielles sont représentées par une liste de variables de X, le symbole représentant la négation d’une variable. Par exemple, si X = {a,b,d}, la X-interprétation M = {a,d} sera notée abd. Si {V1,…,Vp} est une partition de V et si {M1,…,Mp} sont des interprétations partielles, avec Mi ∈ 2 Vi , (M1,…,Mp) représente alors l’interprétation M1 ∪…∪ Mp. Rappellons que, quelle que soit la formule ϕ, une interprétation qui rend ϕ vrai est un modèle de ϕ. L’interprétation partielle d’une formule ϕ sera notée par une X-interprétation MX : (ϕ)MX = ϕv∈MX←⊤,v∈X\MX←⊥ Nous aurons également besoin dans ce rapport de plusieurs notions d’impliquants premiers. Les définitions suivantes sont reprises du rapport de synthèse [Mar00]. Intuitivement, un impliquant premier d’une formule propositionnelle ψ est un des plus petits termes dont tous les modèles sont des modèles de ψ. Définition 1 (Impliquant, impliquant premier) Soit ψ une formule propositionnelle. – Un terme α est un impliquant de ψ ssi α |= ψ. – Un terme α est un impliquant premier de ψ ssi – α est un impliquant de ψ, et – pour chaque impliquant α ′ de ψ, si α |= α ′ , alors α ′ |= α. On notera PI(ψ) l’ensemble des impliquants premiers de ψ. Un L-impliquant premier est un impliquant premier dont tous les littéraux appartiennent à l’ensemble L. Définition 2 (L-impliquant, L-impliquant premier) Soit L ⊆ V et soit ψ une formule propositionnelle de LV . – Un terme α est un L-impliquant de ψ ssi α |= ψ et Lit(α) ⊆ L. – Un terme α est un L-impliquant premier de ψ ssi – α est un L-impliquant de ψ, et – pour chaque L-impliquant α ′ de ψ, si α |= α ′ , alors α ′ |= α. On notera PIL(ψ) l’ensemble des L-impliquants premiers de ψ. La notion de projection d’une formule sur un ensemble de variables correspond à l’utilisation de l’opérateur forget, qui a été étudié par [LLM02, LLM03]. On dit que l’on “oublie complètement” la variable x dans une formule ϕ si et seulement si on s’intéresse à la formule (notée ∀x : ϕ) : ϕx←⊤ ∧ϕx←⊥. On peut aussi “oublier partiellement” x dans ϕ en s’intéressant à la formule (notée ∃x : ϕ) : ϕx←⊤ ∨ϕx←⊥. On note que l’on a : ∀i : ϕ ≡ ¬∃i : ¬ϕ 

Introduction aux jeux booléens

Un jeu booléen sur V [HvdHMW01, Har04a] est un jeu à deux joueurs 1 et 2, à somme nulle, ayant les spécificités suivantes : – les actions que peuvent entreprendre les deux joueurs consistent à donner une valeur de vérité à des variables de V ; – les fonctions d’utilité des deux joueurs sont représentées au moyen d’une formule propositionnelle ϕ formée sur les variables V, appelée forme booléenne du jeu. ϕ représente le but du joueur 1 : l’utilité de celui-ci est +1 lorsque ϕ est satisfaite 1 (et alors le joueur 1 gagne), et −1 sinon (et c’est alors le joueur 2 qui gagne). Le jeu étant à somme nulle, c’est-à-dire u2 = −u1, le but du joueur 2 n’est autre que ¬ϕ. Le jeu n’a donc que deux issues possibles : le gain de 1 ou celui de 2. Pour construire ces jeux booléens, [HvdHMW01, Har04a] commencent par définir deux jeux booléens atomiques, dénotés par 1 et 0. Le premier est gagné par 1 sans qu’aucun des joueurs n’ait à prendre la moindre décision, tandis que le second est gagné par 2. Des jeux booléens plus complexes sont ensuite construits récursivement à partir de ces jeux atomiques et d’un ensemble de variables propositionnelles que l’on appellera variables de décision binaires. Pour tous jeux booléens g0 et g1, et pour toute variable de décision a, il existe un autre jeu booléen dénoté a(g0,g1). Chaque variable de décision est contrôlée de manière exclusive par l’un des deux joueurs. Exemple 1 Soit V = {a,b,c} un ensemble de variables propositionnelles. Soit 1, 2 deux joueurs ayant pour buts : ϕ1 = (a ↔ b)∨(¬a∧b∧ ¬c), ϕ2 = ¬ϕ1 = (¬a∧b∧c)∨(a∧ ¬b). Le joueur 1 contrôle les variables a et c, tandis que 2 contrôle la variable b. La représentation proposée par Harrenstein dans [Har04a] de ce jeu booléen est donnée figure 3.1. Sur cette figure, la flèche gauche partant du nœud x représente la mise à faux de x, tandis que la flèche droite représente la mise à vrai de x. Comme l’ont constaté Dunne et Van der Hoek [DvdH04], cette construction basée sur un modèle dynamique n’est pas nécessaire. En effet, l’hypothèse disant que les stratégies des agents sont choisies en parallèle (c’est-à-dire sans que l’un observe la décision de l’autre) est implicite. Cette forme extensive, sous forme d’arbre, est donc inutile. Il est possible ici d’utiliser une représentation plus simple, correspondant à un jeu statique. Cette représentation utilise la forme normale du jeu : c’est un tableau à deux dimensions, chacune d’entre elles correspondant à un des deux joueurs. On associe à chaque joueur l’ensemble des choix qu’il peut faire pour chacune des variables qu’il contrôle. On associe à chaque état du tableau un couple, dont la première composante représente l’utilité du joueur 1 et la seconde l’utilité du joueur 2. Stricto sensu, les jeux obtenus ne sont pas à somme nulle, mais à somme constante (égale à 1) – ce qui, en pratique, n’a aucune importance – on utilisera donc, par abus de langage, la terminologie “à somme nulle”. Ainsi, si l’on reprend l’exemple 1 page précédente on aura la représentation suivante : Exemple 1 – suite Soit V = {a,b,c} un ensemble de variables propositionnelles. Soit 1, 2 deux joueurs ayant pour buts : ϕ1 = (a ↔ b)∨(¬a∧b∧ ¬c), ϕ2 = ¬ϕ1 = (¬a∧b∧c)∨(a∧ ¬b). Le joueur 1 contrôle les variables a et c, tandis que 2 contrôle la variable b. 

Jeux booléens à n joueurs

 Avant de revenir plus en détail aux jeux booléens tels qu’ils ont été définis dans [HvdHMW01, Har04a], nous allons d’abord les généraliser en nous intéressant à des jeux à n joueurs et à somme non nulle. Nous verrons ensuite que le cadre étudié par [HvdHMW01, Har04a] est un cas particulier de ce cadre plus général.

 Formalisation des jeux booléens 

Commençons par formaliser la notion de jeu booléen. Définition 3 (Jeu booléen) Soit : – un ensemble V de variables propositionnelles (appelées désormais variables de décision), – un ensemble de joueurs A = {1,2,…,n}, – un ensemble de contraintes intra-agent C, – une fonction d’assignement de contrôle π : A → V , et – Φ = hϕ1,…,ϕni les formules représentant les buts des joueurs, où chaque ϕi est une formule de LV . Le jeu booléen correspondant est alors représenté par le quintuplet (A,V,C,π,Φ). π représentant la fonction d’assignement de contrôle qui associe à chaque joueur les variables qu’il contrôle, on note πi l’ensemble des variables contrôlées par le joueur i. Ainsi, {π1,…,πn} forme une partition de V. C représente l’ensemble des contraintes intra-agent, c’est-à-dire l’ensemble des contraintes que chaque agent doit satisfaire. On suppose dans tout le document que l’ensemble C est un ensemble consistant, et que le but de chaque joueur est consistant avec l’ensemble des contraintes : ∀i ∈ {1,…,n} C∧ϕi 6|= ⊥ L’utilisation des jeux booléens permet d’avoir une représentation compacte du problème. Pour illustrer ce propos, nous allons utiliser une variante de l’exemple du dilemme des prisonniers : nous considérons ici n prisonniers qui ne peuvent bénéficier que d’un seul type de remise de peine afin de simplifier le problème. Exemple 2 Dans le jeu du prisonnier à n joueurs, n détenus (notés pi , i = 1,…,n) sont emprisonnés dans des cellules séparées. La police fait à chacun d’eux le même marché : « Tu as le choix entre trahir tes complices en les dénonçant (noté Ti , i = 1,…,n) ou les couvrir (noté Ci , i = 1,…,n). Si tu les dénonces, tu auras une remise de peine et tes partenaires purgeront le maximum (sauf si l’un d’eux t’a dénoncé aussi, auquel cas il bénéficiera comme toi d’une remise de peine). Mais si vous vous couvrez mutuellement, vous aurez tous une remise de peine. »