LogoLogo

Trabelsi, Mariem. Games with incomplete information: a framework based on possibility theory

Trabelsi, Mariem (2020). Games with incomplete information: a framework based on possibility theory.

[img]PDF - nécessite un logiciel de visualisation PDF comme GSview, Xpdf or Adobe Acrobat Reader
8Mb

Résumé en francais

Les jeux probabilistes à information incomplète, appelés jeux Bayesiens, offrent un cadre adapté au traitement de jeux à utilités cardinales sous incertitude. Ce type d'approche ne peut pas être utilisé dans des jeux ordinaux, où l'utilité capture un ordre de préférence, ni dans des situations de décision sous incertitude qualitative. Dans la première partie de cette thèse, nous proposons un modèle de jeux à information incomplète basé sur la théorie de l'utilité qualitative possibiliste: les jeux possibiliste à information incomplète, nommés PI-games. Ces jeux constituent un cadre approprié pour la représentation des jeux ordinaux sous connaissance incomplète. Nous étendons les notions fondamentales de stratégie de sécurité et d'équilibres de Nash (pur et mixte). De plus, nous montrons que tout jeu possibiliste à information incomplète peut être transformé en un jeu à information complète sous la forme normale équivalent au jeu initial, dont les stratégies de sécurité, les équilibres de Nash purs et mixtes sont en bijection dans les deux jeux. Ce résultat de représentation est une contrepartie qualitative de celui de Harsanyi sur la représentation des jeux Bayésiens par des jeux sous forme normale à information complète. Cela est plus un résultat de représentation qu'un outil de résolution. Nous montrons que décider si un équilibre de Nash pur existe dans un PI-game est un problème NP-complet et proposons un codage de programmation linéaire mixte en nombres entiers (PLNE) du problème. Nous proposons également un algorithme en temps polynomial pour trouver une stratégie de sécurité dans un PI-game et montrons qu'un équilibre mixte possibiliste peut être également calculé en temps polynomial (en fonction de la taille du jeu). Pour confirmer la faisabilité de la formulation de programmation linéaire en nombres entiers mixtes et des algorithmes en temps polynomial, nous introduisons aussi un nouveau générateur pour les PI-games basé sur le générateur de jeux sous la forme normale: GAMUT. Représenter un PI-game sous forme normale standard nécessite une expression extensive des fonctions d'utilité et de la distribution des possibilités, à savoir sur les espaces produits des actions et des types. La deuxième partie de cette thèse propose une vue moins coûteuse des PI-games, à savoir la polymatrix PI-games basée sur min, qui permet de spécifier de manière concise les PI-games avec des interactions locales, en d'autre termes, lorsque les interactions entre les joueurs sont par paires et l'utilité d'un joueur dépend de son voisinage et non de tous les autres joueurs du PI-game. Ce cadre permet, par exemple, la représentation compacte des jeux de coordination sous incertitude où la satisfaction d'un joueur est élevée si et seulement si sa stratégie est cohérente avec celles de l'ensemble de ses voisins. Dans cette thèse, nous montrons que n'importe quel PI-game à 2 joueurs peut être transformé en un jeu polymatriciel équivalent basé sur le min. Ce résultat est la contrepartie qualitative du théorème de Howson et Rosenthal reliant les jeux Bayésiens aux jeux polymatriciels. De plus, dès qu'une simple condition de cohérence des connaissances des joueurs sur le monde est satisfaite, tout polymatrix PI-game peut être transformé en temps polynomial en un jeu polymatriciel, basé sur le min, à information complète équivalent. Nous montrons que l'existence d'un équilibre de Nash pur dans un polymatrix PI-game est un problème NP-complet mais pas plus difficile que de décider si un équilibre de Nash pur existe dans un PI-game. Enfin, nous montrons que cette dernière famille de jeux peut être résolue grâce à une formulation de programmation linéaire en nombres entiers mixtes. Nous introduisons un nouveau générateur pour les polymatrix PI-games basés sur le générateur de PI-game. Les expérimentations confirment la faisabilité de cette approche.

Sous la direction du :
Directeur de thèse
Ben Amor, Nahla
Fargier, Hélène
Ecole doctorale:Mathématiques, informatique, télécommunications de Toulouse (MITT)
laboratoire/Unité de recherche :Institut de Recherche en Informatique de Toulouse (IRIT), UMR 5505
Mots-clés libres :Théorie des jeux - Jeux à information incomplète - Jeux ordinaux - Théorie des possibilités - Équilibre de Nash pur - Équilibre de Nash mixte - Stratégie de sécurité - Jeux polymatriciels - Jeux sous incertitude qualitative
Sujets :Informatique
Déposé le :18 Mar 2021 16:33