LogoLogo

Azzabi, Arij. Concisely-expressed ordinal games

Azzabi, Arij (2021). Concisely-expressed ordinal games.

[img]PDF (Accès restreint. S'adresser à l'accueil de la BU Sciences de Toulouse) - Accès intranet - nécessite un logiciel de visualisation PDF comme GSview, Xpdf or Adobe Acrobat Reader
2787Kb

Résumé en francais

Le cadre des jeux hypergraphiques, généralisant jeux graphiques et polymatriciels, fournit des représentations concises des jeux non coopératifs impliquant de nombreux agents. Dans ces jeux hypergraphiques, les agents interagissent dans des sous-jeux locaux simultanés avec leurs agents voisins dans un graphe. Par ailleurs, récemment, un nouveau cadre a été proposé pour des jeux où les utilités des agents sont ordinales. Dans ce nouveau modèle, le concept d'équilibre probabiliste mixte de Nash n'est pas pertinent car les degrés d'utilité ordinaux ne peuvent pas être moyennés. De ce fait, la notion d'équilibres mixte possibiliste a été proposée comme concept de solution pour ces jeux. Comme dans le cas classique, ila été montré qu'un jeu ordinal en forme normale admet toujours un équilibre mixte possibiliste. Contrairement au cas classique, cependant, celui-ci peut être calculé en temps polynomial. Notre contribution, dans cette thèse, est d'étendre le cadre des jeux ordinaux en forme normale en proposant des représentations compactes et des algorithmes de calculs d'équilibres, purs ou mixtes. Ces contributions sont divisées en deux parties : la première partie est consacrée à présenter notre définition des jeux Jeux Hypergraphiques Ordinaux (OHG) et les Jeux Polymatriciels Ordinaux (OPG). Nous montrons que, comme pour les jeux classiques basés sur des graphes, déterminer s'il existe un équilibre de Nash pur est un problème NP-difficile. Ensuite, nous proposons un modèle CSP original pour décider de leur existence et les calculer. Nous proposons ensuite un algorithme qui calcule un équilibre mixte possibiliste en temps polynomial pour les jeux basés sur des graphes. Cela signifie que trouver un équilibre pur ou mixte dans un jeu graphique ordinal n'est pas plus complexe que le trouver dans un jeu ordinal "plat" et plus facile que dans les jeux cardinaux, en ce qui concerne les équilibres mixtes. Une étude expérimentale est consacrée à tester et valider cette contribution. Lors de l'analyse des jeux ordinaux "compacts", on peut être intéressé à trouver tous les équilibres (les moins spécifiques) ou à les compter. La deuxième partie de notre contribution est dédiée à la description d'algorithmes permettant de calculer tous les équilibres mixtes possibilistes les moins spécifiques d'un jeu hypergraphique ordinal. Le premier algorithme, appelé Tree-Nash possibiliste (PI-Tree-Nash) se concentre sur les jeux hypergraphiques ordinaux ayant une structure arborescente. Cet algorithme est une contrepartie possibiliste de l'algorithme Tree-Nash proposé par Kearns pour les jeux graphiques arborescent cardinaux. Ensuite, nous proposons l'algorithme Search All Equilibria (SAE), calculant tous les équilibres mixtes les moins spécifiques d'un jeu hypergraphique ordinal de structure arbitraire. Enfin, nous évaluons la complexité et nous fournissons une étude expérimentale de ces deux algorithmes.

Sous la direction du :
Directeur de thèse
Ben Amor, Nahla
Sabbadin, Régis
Ecole doctorale:Mathématiques, informatique, télécommunications de Toulouse (MITT)
laboratoire/Unité de recherche :Unité de Mathématiques et Informatique Appliquées de Toulouse (MIAT), INRA UR875
Mots-clés libres :Théorie des jeux - Jeux ordinaux - Théorie des possibilités - Equilibre de Nash pur - Equilibre de Nash mixte - Jeux graphiques - Jeux hypergraphiques - jeux polymatriciels
Sujets :Informatique
Déposé le :14 Oct 2021 10:30