Show simple item record

dc.contributor.advisorGimbert, Hugo
dc.contributor.advisorDufour, François
dc.contributor.authorKELMENDI, Edon
dc.contributor.otherBruyère, Véronique
dc.date2016-12-02
dc.identifier.urihttp://www.theses.fr/2016BORD0238/abes
dc.identifier.urihttps://tel.archives-ouvertes.fr/tel-01426223
dc.identifier.nnt2016BORD0238
dc.description.abstractOn considère des jeux stochastiques joués sur un graphe fini. La première partie s’intéresse aux jeux stochastiques à deux joueurs et information parfaite. Dans de tels jeux, les joueurs choisissent des actions dans ensemble fini, tour à tour, pour une durée infinie, produisant une histoire infinie. Le but du jeu est donné par une fonction d’utilité qui associe un réel à chaque histoire, la fonction est bornée et Borel-mesurable. Le premier joueur veut maximiser l’utilité espérée, et le deuxième joueur veut la minimiser. On démontre que si la fonction d’utilité est à la fois shift-invariant et submixing alors le jeu est semi-positionnel. C’est-à-dire le premier joueur a une stratégie optimale qui est déterministe et sans mémoire. Les deux joueurs ont information parfaite: ils choisissent leurs actions en ayant une connaissance parfaite de toute l’histoire. Dans la deuxième partie, on étudie des jeux de durée fini où le joueur protagoniste a zéro information. C’est-à-dire qu’il ne reçoit aucune information sur le déroulement du jeu, par conséquent sa stratégie est un mot fini sur l’ensemble des actions. Un automates probabiliste peut être considéré comme un tel jeu qui a un seul joueur. Tout d’abord, on compare deux classes d’automates probabilistes pour lesquelles le problème de valeur 1 est décidable: les automates leaktight et les automates simples. On prouve que la classe des automates simples est un sous-ensemble strict de la classe des automates leaktight. Puis, on considère des jeux semi-aveugles, qui sont des jeux à deux joueurs où le maximiseur a zéro information, et le minimiseur est parfaitement informé. On définit la classe des jeux semi-aveugles leaktight et on montre que le problème d’accessibilité maxmin est décidable sur cette classe.
dc.description.abstractEnWe consider stochastic games that are played on finite graphs. The subject of the first part are two-player stochastic games with perfect information. In such games the two players take turns choosing actions from a finite set, for an infinite duration, resulting in an infinite play. The objective of the game is given by a Borel-measurable and bounded payoff function that maps infinite plays to real numbers. The first player wants to maximize the expected payoff, and the second player has the opposite objective, that of minimizing the expected payoff. We prove that if the payoff function is both shift-invariant and submixing then the game is half-positional. This means that the first player has an optimal strategy that is at the same time pure and memoryless. Both players have perfect information, so the actions are chosen based on the whole history. In the second part we study finite-duration games where the protagonist player has zero information. That is, he gets no feedback from the game and consequently his strategy is a finite word over the set of actions. Probabilistic finite automata can be seen as an example of such a game that has only a single player. First we compare two classes of probabilistic automata: leaktight automata and simple automata, for which the value 1 problem is known to be decidable. We prove that simple automata are a strict subset of leaktight automata. Then we consider half-blind games, which are two player games where the maximizer has zero information and the minimizer is perfectly informed. We define the class of leaktight half-blind games and prove that it has a decidable maxmin reachability problem.
dc.language.isoen
dc.subjectJeux stochastiques
dc.subjectAccessibilité maxmin
dc.subjectJeux demiaveugles
dc.subjectAutomates simples
dc.subjectAutomates leaktight
dc.subjectAutomates probabilistes
dc.subjectSubmixing
dc.subjectShift-invariant
dc.subjectDemi-positionnel
dc.subject.enStochastic games
dc.subject.enMaxmin reachability
dc.subject.enHalf-blind games
dc.subject.enSimple automata
dc.subject.enLeaktight automata
dc.subject.enProbabilistic automata
dc.subject.enSubmixing
dc.subject.enShift-invariant
dc.subject.enHalf-positional
dc.titleJeux Stochastiques à Deux Joueurs à Information Parfaite et Zéro
dc.title.enTwo-Player Stochastic Games with Perfect and Zero Information
dc.typeThèses de doctorat
dc.contributor.jurypresidentZeitoun, Marc
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.type.institutionBordeaux
bordeaux.thesis.disciplineInformatique
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique (Talence, Gironde)
star.origin.linkhttps://www.theses.fr/2016BORD0238
dc.contributor.rapporteurDoyen, Laurent
dc.contributor.rapporteurViswanathan, Mahesh
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Jeux%20Stochastiques%20%C3%A0%20Deux%20Joueurs%20%C3%A0%20Information%20Parfaite%20et%20Z%C3%A9ro&rft.atitle=Jeux%20Stochastiques%20%C3%A0%20Deux%20Joueurs%20%C3%A0%20Information%20Parfaite%20et%20Z%C3%A9ro&rft.au=KELMENDI,%20Edon&rft.genre=unknown


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record