Cette thèse aborde des sujets liés à la théorie des automates, à la logique et à la théorie des jeux. Ces thèmes sont au cœur de l'informatique théorique depuis de nombreuses décennies. Les travaux de recherche dans ces domaines sont motivés entre autres par des questions de modélisation et de vérification de systèmes. La première partie de la thèse considère les automates finis et la logique temporelle sur des ordres linéaires arbitraires. On y donne une procédure (doublement exponentielle en espace) pour décider la satisfaisabilité d'une formule LTL, utilisant une étape de transformation d'une formule logique en un transducteur synchrone. La seconde partie s'intéresse à des jeux de longueur ordinale. On propose un modèle de jeux à deux joueurs sur des graphes finis, et on montre que la question du vainqueur pour ces jeux peut être résolue en espace polynomial. De plus, on montre qu'il existe des stratégies gagnantes à mémoire finie.

<p align="justify">Depuis 20 à 30 ans, l'aide multicritère à la décision est apparue. L'expansion de cette nouvelle discipline s'est marquée dans la littérature essentiellement par un foisonnement de nouvelles méthodes multicritères d'aide à la décision et par des applications de celles-ci à des problèmes "réels". Pour la plupart de ces méthodes, il n'y pas ou peu de fondements théoriques. Seul le bon sens a guidé les créateurs de ces méthodes.</p> <p align="justify">Depuis une dizaine d'années, le besoin de bases théoriques solides se fait de plus en plus sentir. C'est dans cette perspective que nous avons réalisé le présent travail. Ceci étant dit, nous n'allons pas vraiment nous occuper de méthodes multicritères à la décision dans ce travail, mais seulement de fragments de méthodes. En effet, les méthodes multicritères d'aide à la décision peuvent généralement être décomposées en trois parties (outre la définition de l'ensemble des alternatives et le choix des critères):</p> <p align="justify"><ol><li>Modélisation des préférences: pendant cette étape, les préférences du décideur sont modélisées le long de chaque critère. <li>Agrégation des préférences: un modèle global de préférences est construit au départ des modèles obtenus critère par critère à la fin de la phase précédente. <li>Exploitation des résultats de l'agrégation: du modèle global de préférences issu de la phase 2, on déduit un choix, un rangement, une partition, ... selon les besoins.</ol></p> <p align="justify">Jusqu'à présent, à cause de la difficulté du problème, peu de méthodes ont été axiomatisées de bout en bout; la plupart des travaux ne s'intéressent qu'à une ou deux des trois étapes que nous venons de décrire.</p> <p align="justify">Nous nous sommes intéressés à une méthode bien connue: la méthode de Borda. Elle accepte comme données de départ des relations binaires. Elle intervient donc après la phase de modélisation des préférences. Le résultat de cette méthode est un rangement. Elle effectue donc les opérations correspondant aux étapes 2 et 3. Dans la suite de ce travail nous appellerons méthode de rangement toute méthode effectuant les étapes 2 et 3 pour aboutir à un rangement. Etant donné que les méthodes de rangement, celle de Borda en particulier, sont utilisées également en choix social, nous puiserons abondamment dans le vocabulaire, les outils et les résultats du choix social. Les résultats présentés seront valides en choix social, mais nous nous sommes efforcés de les rendre aussi pertinents que possible en aide multicritère à la décision.</p> <p align="justify">Dans le chapitre II, après quelques définitions et notations, nous présentons quelques méthodes de rangement classiques, y compris la méthode de Borda, et quelques résultats majeurs de la littérature. Nous généralisons une caractérisation des méthodes de scorage due à Myerson (1995).</p> <p align="justify">Nous nous tournons ensuite vers les relations valuées. La raison en est la suivante: elles sont utilisées depuis longtemps dans plusieurs méthodes multicritères et, depuis peu, elles le sont aussi en choix social (p.ex. Banerjec 1994) car elles permettent de modéliser plus finement les préférences des décideurs confrontés à des informations incertaines, imprécises, contradictoires, lacunaires, ... Nous commençons donc le chapitre III par des notations et définitions relatives aux relations valuées.</p> <p align="justify">Ensuite, nous présentons quelques méthodes de rangement opérant au départ de relations valuées. C'est-à-dire des méthodes de rangement qui agissent non pas sur des relations nettes, mais sur des relations valuées et qui fournissent comme précédemment un rangement des alternatives. N'ayant trouvé dans la littérature aucune méthode de ce type, toutes celles que nous présentons sont neuves ou des généralisations de méthodes existantes; comme par exemple, les méthodes de scorage généralisées, que nous caractérisons en généralisant encore une fois le résultat de Myerson.</p> <p align="justify">Nous présentons enfin ce que nous appelons la méthode de Borda généralisée, qui est une des généralisations possibles de la méthode de Borda au cas valué. Nous basant sur un article de Farkas et Nitzan (1979), nous montrons que contrairement à ce qui se passait dans le cas particulier envisagé par Farkas et Nitzan (agrégation d'ordres totaux), la méthode de Borda généralisée (et sa particularisation au cas net) n'est pas toujours équivalente à la méthode proximité à l'unanimité. Cette dernière méthode classe chaque alternative en fonction de l'importance des changements qu'il faudrait faire subir à un ensemble de relations pour que l’alternative considérée gagne à l'unanimité. Nous identifions quelques cas où l'équivalence est vraie.</p> <p align="justify">Ensuite, nous reprenons un résultat de Debord (1987). Il s'agit d'une caractérisation de la méthode de Borda en tant que méthode de choix appliquée à des préordres totaux. Nous la généralisons de deux façons au cas de la méthode de Borda en tant que méthode de rangement appliquée à des relations valuées. Lorsqu'on applique la méthode de Borda, on est amené à calculer une fonction à valeurs réelles sur l'ensemble des alternatives.</p> <p align="justify">La valeur prise par cette fonction pour une alternative s'appelle le score de Borda de cette alternative. Ensuite, on range les alternatives par ordre décroissant de leur score de Borda. La tentation est grande - et beaucoup y succombent (peut-être avec raison) d'utiliser le score de Borda non seulement pour calculer le rangement mais aussi pour estimer si l'écart entre deux alternatives est important ou non (voir par exemple Brans 1994). Cette approche n'a, à notre connaissance, jamais été étudiée d'un point de vue théorique. Nous présentons deux caractérisations de la méthode de Borda utilisée à cette fin.</p> <p align="justify">Dans la dernière partie du chapitre III, nous abandonnons la démarche qui visait à caractériser une méthode par un ensemble de propriétés le plus petit possible. Nous comparons 12 méthodes sur base d'une vingtaine de propriétés. Les résultats de cette partie sont résumés dans quelques tableaux.</p> <p align="justify">Ce travail aborde donc la méthode de Borda et sa généralisation au cas valué sous différents angles. Il livre une série de résultats qui, espérons-le, devraient permettre de mieux comprendre la méthode de Borda et peut-être de l'utiliser à meilleur escient. Toutefois, quoique notre objectif ait été de présenter des résultats pertinents en aide multicritère à la décision (et nous avons fait des progrès dans ce sens), il reste du chemin à faire. Nous sommes probablement encore trop proche du choix social. Ceci constitue donc une voie de recherche intéressante, de même que l'étude d'autres méthodes de rangement et l'étude de méthodes complètes d'aide multicritère à la décision: modélisation du problème (identification du ou des décideur(s), des alternatives et des critères), modélisation des préférences, agrégation des préférences et exploitation des résultats de l'agrégation.</p>

Cette thèse a pour objet d'étude les jeux vidéo en France. Ce nouveau loisir apparu commercialement dans le milieu des années 1970 aux Etats-Unis, est devenu, en trente ans d'existence, une véritable industrie au même titre que le cinéma ou la musique.Son émergence et son développement vont de pair avec les débuts et l'essor de l'informatique de loisir et des ordinateurs grand public dont le jeu est l'un des éléments déterminant de leur succès.Nous étudierons ainsi tout ce qui a trait à cette industrie, son économie (marchés, acteurs, politiques commerciales), les différentes machines de jeu et les jeux (conception, genres, thèmes abordés). Nous analyserons les joueurs, leurs profils, leurs goûts ainsi que la presse française et les différentes manifestations (salons, concours, compétitions) liées à ce media.Nous parlerons également des influences et des inspirations du jeu vidéo, de ses rapports avec les arts et les autres loisirs. D'autre part, nous mentionnerons les obstacles rencontrés et les accusations portées envers les jeux vidéo (violence, maladie, isolement) ainsi que leur dimension politique et la vision et l'action des politiques et des gouvernements sur cette industrie.En somme, le but d'un tel sujet est de comprendre et d'expliquer ce nouveau type de loisir mais aussi de réfléchir sur le sens que possède son développement et en quoi il est représentatif des évolutions de la société française depuis une trentaine d'années.

La thèse est consacrée à l'étude de jeux dynamiques dans le domaine climatique. Pour lutter contre l'accumulation de gaz à effet de serre dans l'atmosphère, la mise en place d'une taxe carbone est une solution possible. Toutefois on suppose ici que cette taxe carbone a pour les pays consommateurs d'énergie fossile des motivations qui ne se limitent pas à l'internalisation du dommage environnemental : il s'agit par un comportement stratégique d'essayer de capturer une partie de la rente des producteurs. On aboutit à la possibilité d'une taxe carbone à finalité Pigouvienne mais aussi stratégique. Des jeux dynamiques non coopératifs entre pays producteurs supposés cartellisés et pays consommateurs supposés également cartellisés peuvent être alors être envisagés dans ce contexte. Une littérature de jeux différentiels non coopératifs s'est d'ailleurs développée depuis une vingtaine d'années autour de cette idée d'une taxe carbone à visée stratégique. Dans l'introduction on rappelle le cadre économique de ces jeux, leur cadre analytique (jeux différentiels) et la littérature théorique afférente. On présente trois jeux qui forment le corps de la thèse. Chacun des trois chapitres suivants est consacré à un jeu différentiel original. Le premier jeu est un jeu non coopératif entre un bloc de consommateurs et un bloc de producteurs avec un plafond de pollution comme contrainte environnementale principale. L'existence de ce plafond modifie les conclusions classiques de ce type de jeu. Dans le deuxième jeu il y a également un jeu non coopératif entre un bloc de consommateurs (pays riches) et un bloc de producteurs mais il y a en plus un second bloc de consommateurs (pays pauvres et émergents), qui ne joue pas dans le jeu mais met en place la taxe carbone résultant à chaque instant du jeu en contrepartie d'un transfert de la part du premier bloc de consommateurs. Il apparaît que sous certaines conditions le second bloc a intérêt à ce schéma " taxe carbone contre transfert ". Dans le troisième jeu il y a aussi deux zones de consommation mais elles jouent maintenant un jeu non coopératif entre elles, les producteurs étant passifs. Il y a une taxe carbone par bloc et pas mondiale et pourtant le jeu fait apparaître sous certaines conditions une situation meil1eure pour les blocs de consommation qu'une situation de passivité face aux producteurs. La conclusion d'ensemble de ces trois jeux est que sous certaines conditions les pays consommateurs peuvent avoir intérêt à un comportement stratégique et pas seulement Pigouvien en matière de taxe carbone.

On trouve dans la littérature de nombreux exemples de jeux où les stratégies souhaitées sont soumises à des contraintes ''transversales'' portant sur des ensembles de parties, reliées entre elles par quelque relation sémantique. L'exemple le plus fameux est celui des stratégies dans les jeux à information imparfaite, et les jeux où la condition de gain a un aspect épistémique en sont d'autres. Cependant, aucune étude approfondie n'a à notre connaissance été menée sur ce type de contraintes dans leur généralité. C'est ce que nous nous proposons de commencer dans cette thèse. Nous définissons donc une notion générale de stratégies uniformes. Les propriétés d'uniformité des stratégies sont exprimées dans un langage logique qui étend CTL∗ avec deux quantificateurs originaux. Ces quantificateurs sont très proches des opérateurs de connaissance classiques en logique épistémique, et font intervenir des ensembles de parties reliées entre elles par des relations binaires. Nous montrons comment cette notion de stratégies uniformes capture les exemples connus de la littérature, puis nous étudions en profondeur le problème de la synthèse de stratégies uniformes, en considérant que les relations binaires entre les parties sont reconnaissables par des automates finis (relations rationnelles). Nous établissons plusieurs résultats de décidabilité et de complexité, reposant largement sur des techniques d'automates : nous introduisons notamment comme outils les automates d'arbres bondissants et les automates d'ensembles d'informations. Par ailleurs, nos résultats permettent d'améliorer des résultats existants et d'en établir de nouveaux, dans les domaines du model-checking des logiques temporelles et épistémiques, ainsi que de la planification épistémique.

L’intelligence artificielle est un domaine de l’informatique étudiant la conception d’agents intelligents. Un agent est une entité acquérant de l’information sur son environnement par ses capteurs et agissant sur son environnement à travers ses actionneurs. Certains agents existent seulement dans le domaine logiciel, comme par exemple un agent intelligent pour un jeu vidéo, alors que d’autres existent dans le monde physique, tels les robots mobiles. Les domaines des jeux vidéo et de la robotique partagent certaines caractéristiques, dont la nécessité de prendre des décisions en temps réel dans un environnement dynamique ainsi qu’une vue incomplète sur cet environnement. Ce mémoire est divisé en deux chapitres. Le premier chapitre traite d’une approche de planification de trajectoires exploitant la géométrie d’une classe particulière de robots omnidirectionnels non-holonomes afin de calculer des chemins adéquats leur permettant d’atteindre une destination désirée. Les résultats obtenus avec cette approche tendent à démontrer qu’elle est plus efficace que les algorithmes traditionnels de planification de trajectoires grâce à l’information additionnelle prise en compte lors du calcul. Le second chapitre décrit l’architecture décisionnelle de l’agent intelligent SPAR qui est en mesure de jouer de façon autonome des parties de StarCraft : Brood War, un jeu de stratégie en temps réel. L’architecture de SPAR inclut entre autres des algorithmes de planification de trajectoires similaires à ceux du premier chapitre. Elle permet de faire face plus facilement et de façon plus rigoureuse, en comparaison avec les architectures existantes, aux nombreuses difficultés propres à ce type de jeu. Ces difficultés incluent un degré élevé de concurrence dans les actions et une multitude d’unités à contrôler dans un contexte temps réel. L’agent SPAR a participé aux volets 2011 et 2012 de la compétition AIIDE de StarCraft et à l’édition 2012 de la compétition SSCAI où il a obtenu à chaque fois des résultats honorables.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal. / Pour respecter les droits d'auteur, la version électronique de cette thèse ou ce mémoire a été dépouillée, le cas échéant, de ses documents visuels et audio-visuels. La version intégrale de la thèse ou du mémoire a été déposée au Service de la gestion des documents et des archives de l'Université de Montréal.

Les univers fictionnels qui accueillent les connexions à distance de plusieurs joueurs comptent parmi les premières expériences de communication et de coopération à distance, médiatisées par les techniques informatiques. Longtemps réservés à un public d'initiés, ils connaissent un essor important au milieu des années 2000. Les jeux en ligne multijoueurs à univers persistant (Massive Multiplayer Online Games : MMOG) apparaissent conjointement à la connexion des technologies informatiques ainsi qu'à celle de diverses cultures et pratiques ludiques populaires. En débordant des cadres conceptuels jusqu'alors réservés au jeu électronique, ils incitent les chercheurs à renouveler les réflexions portées sur ces objets, tout comme les perceptions classiques de l'activité de jeu.L'analyse exposée dans ce mémoire de thèse a été réalisée à partir d'observations participantes menées entre 2006 et 2008 au sein du studio de développement d'un MMOG, ainsi qu'entre 2008 et 2010 dans le jeu World of Warcraft (Blizzard Entertainment). Nous abordons ici les univers ludiques en ligne comme les occurrences singulières de la construction et du partage d'un monde d'objets, de représentations et de pratiques. Les principales questions qui découlent de cette perspective sont articulées autour des thèmes dominants que sont la conception et la pratique. Elles interrogent la distribution de l'autorité sur la définition des mondes de l'activité de jeu que sont les univers ludiques en ligne, et portent pour ce faire une attention particulière à la place que les technologies de l'information et de la communication occupent dans le processus de redéfinition continue des univers ludiques partagés en ligne. / Inexistant

Pas de résumé disponible. / Pas de résumé disponible.

La th´eorie de la complexit´e permet de classifier les probl`emes en fonction de leur difficult´e. Le cadre classique dans lequel elle s’applique est celui d’un algorithme centralis´e qui dispose de toutes les informations. Avec l’essor des r´eseaux et des architectures d´ecentralis´ees, l’algo- rithmique distribu´ee a ´et´e ´etudi´ee. Dans un grand nombre de probl`emes, en optimisation et en ´economie, les d´ecisions et les calculs sont effectu´es par des agents ind´ependants qui suivent des objectifs diff´erents dont la r´ealisation d´epend des d´ecisions des autres agents. La th´eorie des jeux est un cadre naturel pour analyser les solutions de tels probl`emes. Elle propose des concepts de stabilit´e, le plus classique ´etant l’´equilibre de Nash.Une mani`ere naturelle de calculer de telles solutions est de “ faire r´eagir “ les agents ; si un agent voit quelles sont les d´ecisions des autres joueurs ou plus g´en´eralement un “ ´etat du jeu “, il peut d´ecider de changer sa d´ecision pour atteindre son objectif faisant ainsi ´evoluer l’´etat du jeu. On dit que ces algorithmes sont des “ dynamiques “.On sait que certaines dynamiques convergent vers un concept de solution. On s’int´eresse `a la vitesse de convergence des dynamiques. Certains concepts de solutions sont mˆeme complets pour certaines classes de complexit´e ce qui rend peu vraisemblable l’existence de dynamiques simples qui convergent rapidement vers ces solutions. On a utilis´e alors trois approches pour obtenir une convergence rapide : am´eliorer la dynamique (en utilisant par exemple des bits al´eatoires), restreindre la structure du probl`eme, et rechercher une solution approch´ee.Sur les jeux de congestion, on a ´etendu les r´esultats de convergence rapide vers un ´equilibre de Nash approch´e aux jeux n´egatifs. Cependant, on a montr´e que sur les jeux sans contrainte de signe, calculer un ´equilibre de Nash approch´e est PLS-complet. Sur les jeux d ’appariement, on a ´etudi´e la vitesse de dynamiques concurrentes lorsque les joueurs ont une information partielle param´etr´ee par un r´eseau social. En particulier, on a am´elior´e des dynamiques naturelles afin qu’elles atteignent un ´equilibre enO(log(n)) tours (avec n le nombre de joueurs). / Complexity theory allows to classify problems by their algorithmic hardness. The classical framework in which it applies is the one of a centralized algorithm that knows every informa- tion. With the development of networks and decentralized architectures, distributed dynamics was studied. In many problems, in optimization or economy, actions and computations are made by independant agents that don’t share the same objective whose realization depends on the actions of other agents. Game theory is a natural framework to study solutions of this kind of problem. It provides solution concepts such as the Nash equilibrium.A natural way to compute these solutions is to make the agents “react” ; if an agent sees the actions of the other player, or more generally the state of the game, he can decide to change his decision to reach his objective and updates the state of the game. We call �dynamics� this kind of algorithms.We know some dynamics converges to a stable solution. We are interested by the speed of convergence of these dynamics. Some solution concepts are even complete for some complexity classes which make unrealistic the existence of fast converging dynamics. We used three ways to obtain a fast convergence : improving dynamics (using random bits), finding simple subcases, and finding an approximate solution.We extent fast convergence results to an approximate Nash equilibria in negative congestion games. However, we proved that finding an approximate Nash equilibrium in a congestion games without sign restriction is PLS-complete. On matching game, we studied the speed of concurrent dynamics when players have partial information that depends on a social network. Especially, we improved natural dynamics for them to reach an equilibrium inO(log(n)) rounds (with n is the number of players).