Search

Your search keyword '"Hugo Gimbert"' showing total 25 results
Start Over Author "Hugo Gimbert" Topic 01 natural sciences
25 results on '"Hugo Gimbert"'

1. Two-Sided Matching Markets with Strongly Correlated Preferences

Author

Hugo Gimbert, Claire Mathieu, Simon Mauras, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), and Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)

Subjects
Matching (statistics), Empirical research, 010201 computation theory & mathematics, Computer science, 010102 general mathematics, Subject (documents), [INFO]Computer Science [cs], 0102 computer and information sciences, 0101 mathematics, 01 natural sciences, Mathematical economics, ComputingMilieux_MISCELLANEOUS
Abstract

Stable matching in a community consisting of men and women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley, who designed the celebrated “deferred acceptance” algorithm for the problem.

Published
2021
Full Text
View/download PDF

2. Qualitative Determinacy and Decidability of Stochastic Games with Signals

Author

Hugo Gimbert, Nathalie Bertrand, Blaise Genest, SUpervision of large MOdular and distributed systems (SUMO), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-13-BS02-0011,Stoch-MC,Modèles stochastiques: passage à l'échelle pour le Model Checking(2013), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Gimbert, Hugo, Programme 'Sécurité et Informatique' - Systèmes distribués, ouverts et temporisés - - DOTS2006 - ANR-06-SETI-0003 - SETI - VALID, Verification models and techniques applied to testing and control of reactive systems (VERTECS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Distributed and Iterative Algorithms for the Management of Telecommunications Systems (DISTRIBCOM), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-06-SETI-0003,DOTS,Systèmes distribués, ouverts et temporisés(2006), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique

Subjects
Mathematical optimization, 0209 industrial biotechnology, Matching (statistics), Determinacy, Computer Science::Computer Science and Game Theory, Theoretical computer science, EXPTIME, 0102 computer and information sciences, 02 engineering and technology, Markov Processes, Outcome (game theory), 01 natural sciences, parity games, 020901 industrial engineering & automation, Security and privacy → Logic and verification, Computing methodologies → Multi-agent systems, Artificial Intelligence, Reachability, Software/Program Verification—Model checking, partial observation, Almost surely, 0101 mathematics, Mathematics, Standard model (cryptography), Discrete mathematics, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Imperfect information, 010102 general mathematics, Perfect information, ComputingMilieux_PERSONALCOMPUTING, Controller Synthesis, algorithmic game theory, Additional Key Words and Phrases: Controller synthesis, Applied computing → Economics, Decidability, Range (mathematics), Design Aids, Hardware and Architecture, Control and Systems Engineering, 010201 computation theory & mathematics, [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], Algorithmic game theory, determinacy, Mathematical economics, Stochastic games, Software, Mathematics of computing → Markov processes, Information Systems
Abstract

We consider two-person zero-sum stochastic games with signals, a standard model of stochastic games with imperfect information. The only source of information for the players consists of the signals they receive; they cannot directly observe the state of the game, nor the actions played by their opponent, nor their own actions. We are interested in the existence of almost-surely winning or positively winning strategies, under reachability, safety, Büchi, or co-Büchi winning objectives, and the computation of these strategies when the game has finitely many states and actions. We prove two qualitative determinacy results. First, in a reachability game, either player 1 can achieve almost surely the reachability objective, or player 2 can achieve surely the dual safety objective, or both players have positively winning strategies. Second, in a Büchi game, if player 1 cannot achieve almost surely the Büchi objective, then player 2 can ensure positively the dual co-Büchi objective. We prove that players only need strategies with finite memory . The number of memory states needed to win with finite-memory strategies ranges from one (corresponding to memoryless strategies) to doubly exponential, with matching upper and lower bounds. Together with the qualitative determinacy results, we also provide fix-point algorithms for deciding which player has an almost-surely winning or a positively winning strategy and for computing an associated finite-memory strategy. Complexity ranges from EXPTIME to 2EXPTIME, with matching lower bounds. Our fix-point algorithms also enjoy a better complexity in the cases where one of the players is better informed than their opponent. Our results hold even when players do not necessarily observe their own actions. The adequate class of strategies, in this case, is mixed or general strategies (they are equivalent). Behavioral strategies are too restrictive to guarantee determinacy: it may happen that one of the players has a winning general strategy but none of them has a winning behavioral strategy. On the other hand, if a player can observe their actions, then general, mixed, and behavioral strategies are equivalent. Finite-memory strategies are sufficient for determinacy to hold, provided that randomized memory updates are allowed.

Published
2017
Full Text
View/download PDF

3. Deciding Maxmin Reachability in Half-Blind Stochastic Games

Author

Hugo Gimbert and Edon Kelmendi

Subjects
Discrete mathematics, Computer Science::Computer Science and Game Theory, Class (set theory), Existential quantification, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Decidability, Undecidable problem, Combinatorics, 010201 computation theory & mathematics, Ask price, Reachability, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Set (psychology), Value (mathematics), Mathematics
Abstract

Two-player, turn-based, stochastic games with reachability conditions are considered, where the maximizer has no information (he is blind) and is restricted to deterministic strategies whereas the minimizer is perfectly informed. We ask the question of whether the game has maxmin value of 1 in other words we ask whether for all \(\epsilon >0\) there exists a deterministic strategy for the (blind) maximizer such that against all the strategies of the minimizer, it is possible to reach the set of final states with probability larger than \(1-\epsilon \). This problem is undecidable in general, but we define a class of games, called leaktight half-blind games where the problem becomes decidable. We also show that mixed strategies in general are stronger for both players and that optimal strategies for the minimizer might require infinite-memory.

Published
2016
Full Text
View/download PDF

4. On the values of repeated games with signals

Author

Wiesław Zielonka, Sylvain Sorin, Hugo Gimbert, Jérôme Renault, Xavier Venel, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, Groupe de recherche en économie mathématique et quantitative (GREMAQ), Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de la Recherche Agronomique (INRA)-Université Toulouse 1 Capitole (UT1), Institut de Mathématiques de Jussieu (IMJ), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centre d'économie de la Sorbonne (CES), Université Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS), Paris School of Economics (PSE), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7), ANR-10-BLAN-0112,JEUDY,Comportement en temps long pour les jeux dynamiques à temps continu et discret(2010), European Project, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National de la Recherche Agronomique (INRA)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS), École des Ponts ParisTech (ENPC)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National de la Recherche Agronomique (INRA)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), Université Paris 1 Panthéon-Sorbonne (UP1)-École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)

Subjects
Statistics and Probability, FOS: Computer and information sciences, Computer Science::Computer Science and Game Theory, Structure (category theory), Repeated Games with signals, 91A15, 01 natural sciences, repeated games with symmetric information, 010104 statistics & probability, Computer Science - Computer Science and Game Theory, 91A20, FOS: Mathematics, uniform value, 0101 mathematics, Payoff function, Multistage game, Mathematics - Optimization and Control, B- ECONOMIE ET FINANCE, Mathematics, Borel evaluation, 010102 general mathematics, limsup value, ComputingMilieux_PERSONALCOMPUTING, State (functional analysis), [SHS.ECO]Humanities and Social Sciences/Economics and Finance, Borelian evaluation, 91A05, Optimization and Control (math.OC), Repeated game, 60G35, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Statistics, Probability and Uncertainty, Mathematical economics, Value (mathematics), Computer Science and Game Theory (cs.GT)
Abstract

We study the existence of different notions of value in two-person zero-sum repeated games where the state evolves and players receive signals. We provide some examples showing that the limsup value (and the uniform value) may not exist in general. Then we show the existence of the value for any Borel payoff function if the players observe a public signal including the actions played. We also prove two other positive results without assumptions on the signaling structure: the existence of the $\sup$ value in any game and the existence of the uniform value in recursive games with nonnegative payoffs., Comment: Published at http://dx.doi.org/10.1214/14-AAP1095 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Published
2016
Full Text
View/download PDF

5. Discounting Infinite Games But How and Why?

Author

Hugo Gimbert, Wiesław Zielonka, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and L. de Alfaro

Subjects
0209 industrial biotechnology, Discounting, General Computer Science, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Stochastic game, Mean payoff, Context (language use), 0102 computer and information sciences, 02 engineering and technology, Computer society, 01 natural sciences, Theoretical Computer Science, parity games, discounting games, 020901 industrial engineering & automation, Limit (category theory), Systems theory, 010201 computation theory & mathematics, Reachability, Mathematical economics, ComputingMilieux_MISCELLANEOUS, Mathematics, Computer Science(all)
Abstract

In a recent paper de Alfaro, Henzinger and Majumdar [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] observed that discounting successive payments, the procedure that is employed in the classical stochastic game theory since the seminal paper of Shapley [L.S. Shapley. Stochastic games. Proceedings Nat. Acad. of Science USA, 39:1095–1100, 1953], is also pertinent in the context of much more recent theory of stochastic parity games [L. de Alfaro and R. Majumdar. Quantitative solution to omega-regular games. In STOC'01, pages 675–683. ACM Press, 2001. final version to appear in Journal of Computer and System Sciences, L. de Alfaro, T.A. Henzinger, and O. Kupferman. Concurrent reachability games. In FOCS'98, pages 564–575. IEEE Computer Society Press, 1998, L. de Alfaro and T.A. Henzinger. Concurrent ω-regular games. In LICS'00, pages 142–154. IEEE Computer Society Press, 2000] which were proposed as a tool for verification of probabilistic systems. We show that, surprisingly perhaps, the particular discounting used in [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] is in fact very close to the original ideas of Shapley. This observation allows to realize that the specific discounting of [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] suffers in fact from some needless restrictions. We advocate that dropping the constraints imposed in [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] leads to a more general and elegant theory that includes parity and mean payoff games as particular limit cases.

Published
2005
Full Text
View/download PDF

6. Perfect-Information Stochastic Mean-Payoff Parity Games

Author

Krishnendu Chatterjee, Hugo Gimbert, Laurent Doyen, Youssouf Oualhadj, Institute of Science and Technology [Austria] (IST Austria), Laboratoire Spécification et Vérification [Cachan] (LSV), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Institut de Mathématiques [Mons], and Université de Mons (UMons)

Subjects
Computer Science::Computer Science and Game Theory, 005 Computer programming, programs & data, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Stochastic process, Stochastic game, Perfect information, ComputingMilieux_PERSONALCOMPUTING, Mean payoff, Functional requirement, 0102 computer and information sciences, 02 engineering and technology, 000 Computer science, knowledge & systems, 01 natural sciences, Combinatorics, 510 Mathematics, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Markov decision process, Special case, 000 Computer science, knowledge general works, Reactive system, Mathematics
Abstract

International audience; The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2-1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2-1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running in time O(d * n^{2d}*MeanGame) to compute the set of almost-sure winning states from which the objective can be ensured with probability 1, where n is the number of states of the game, d the number of priorities of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states in 2-1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective).

Published
2014
Full Text
View/download PDF

7. Deciding the Value 1 Problem for sharp-acyclic Partially Observable Markov Decision Processes

Author

Hugo Gimbert, Youssouf Oualhadj, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Institut de Mathématiques [Mons], and Université de Mons (UMons)

Subjects
Discrete mathematics, Computer Science::Computer Science and Game Theory, Markov kernel, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Stochastic game, Partially observable Markov decision process, 0102 computer and information sciences, 02 engineering and technology, Decision rule, Markov model, 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, Reachability, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Markov decision process, Algorithmic game theory, Mathematics
Abstract

The value 1 problem is a natural decision problem in algorithmic game theory. For partially observable Markov decision processes with reachability objective, this problem is defined as follows: are there observational strategies that achieve the reachability objective with probability arbitrarily close to 1? This problem was shown undecidable recently. Our contribution is to introduce a class of partially observable Markov decision processes, namely \(\sharp-acyclic\) partially observable Markov decision processes, for which the value 1 problem is decidable. Our algorithm is based on the construction of a two-player perfect information game, called the knowledge game, abstracting the behaviour of a \(\sharp\)-acyclic partially observable Markov decision process \({\mathcal M}\) such that the first player has a winning strategy in the knowledge game if and only if the value of \({\mathcal M}\) is 1.

Published
2014
Full Text
View/download PDF

8. Two Recursively Inseparable Problems for Probabilistic Automata

Author

Florian Horn, Nathanaël Fijalkow, Hugo Gimbert, and Youssouf Oualhadj

Subjects
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Failure probability, Stochastic game, Timed automaton, 0102 computer and information sciences, 02 engineering and technology, Decision problem, Nonlinear Sciences::Cellular Automata and Lattice Gases, 01 natural sciences, Mobile automaton, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Deterministic automaton, Fair coin, Probabilistic automaton, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Algorithm, Computer Science::Formal Languages and Automata Theory, Mathematics
Abstract

This paper introduces and investigates decision problems for numberless probabilistic automata, i.e. probabilistic automata where the support of each probabilistic transitions is specified, but the exact values of the probabilities are not. A numberless probabilistic automaton can be instantiated into a probabilistic automaton by specifying the exact values of the non-zero probabilistic transitions.

Published
2014
Full Text
View/download PDF

9. Asynchronous Games over Tree Architectures

Author

Hugo Gimbert, Anca Muscholl, Igor Walukiewicz, Blaise Genest, SUpervision of large MOdular and distributed systems (SUMO), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Fomin, Fedor V. and Freivalds, Rūsiņš and Kwiatkowska, Marta and Peleg, David, LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, Distributed and Iterative Algorithms for the Management of Telecommunications Systems (DISTRIBCOM), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)

Subjects
FOS: Computer and information sciences, 0209 industrial biotechnology, Theoretical computer science, Matching (graph theory), Formal Languages and Automata Theory (cs.FL), [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Computer Science - Formal Languages and Automata Theory, Systems and Control (eess.SY), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Turing machine, symbols.namesake, 020901 industrial engineering & automation, Complete information, FOS: Electrical engineering, electronic engineering, information engineering, Mathematics, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Tree (graph theory), Decidability, Undecidable problem, Automaton, 010201 computation theory & mathematics, Asynchronous communication, symbols, Computer Science - Systems and Control, Computer Science::Formal Languages and Automata Theory
Abstract

We consider the task of controlling in a distributed way a Zielonka asynchronous automaton. Every process of a controller has access to its causal past to determine the next set of actions it proposes to play. An action can be played only if every process controlling this action proposes to play it. We consider reachability objectives: every process should reach its set of final states. We show that this control problem is decidable for tree architectures, where every process can communicate with its parent, its children, and with the environment. The complexity of our algorithm is l-fold exponential with l being the height of the tree representing the architecture. We show that this is unavoidable by showing that even for three processes the problem is EXPTIME-complete, and that it is non-elementary in general.

Published
2013
Full Text
View/download PDF

10. On (Subgame Perfect) Secure Equilibrium in Quantitative Reachability Games

Author

Hugo Gimbert, Julie De Pril, Thomas Brihaye, and Véronique Bruyère

Subjects
FOS: Computer and information sciences, TheoryofComputation_MISCELLANEOUS, Computer Science - Logic in Computer Science, Computer Science::Computer Science and Game Theory, General Computer Science, Computer science, Open problem, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Subgame perfect equilibrium, symbols.namesake, Computer Science - Computer Science and Game Theory, Reachability, 0202 electrical engineering, electronic engineering, information engineering, D.2.4, ComputingMilieux_PERSONALCOMPUTING, TheoryofComputation_GENERAL, Logic in Computer Science (cs.LO), 010201 computation theory & mathematics, Nash equilibrium, symbols, 020201 artificial intelligence & image processing, Mathematical economics, Computer Science and Game Theory (cs.GT)
Abstract

We study turn-based quantitative multiplayer non zero-sum games played on finite graphs with reachability objectives. In such games, each player aims at reaching his own goal set of states as soon as possible. A previous work on this model showed that Nash equilibria (resp. secure equilibria) are guaranteed to exist in the multiplayer (resp. two-player) case. The existence of secure equilibria in the multiplayer case remained and is still an open problem. In this paper, we focus our study on the concept of subgame perfect equilibrium, a refinement of Nash equilibrium well-suited in the framework of games played on graphs. We also introduce the new concept of subgame perfect secure equilibrium. We prove the existence of subgame perfect equilibria (resp. subgame perfect secure equilibria) in multiplayer (resp. two-player) quantitative reachability games. Moreover, we provide an algorithm deciding the existence of secure equilibria in the multiplayer case., Comment: 32 pages. Full version of the FoSSaCS 2012 proceedings paper

Published
2013
Full Text
View/download PDF

11. Deciding the Value 1 Problem for Probabilistic Leaktight Automata

Author

Nathanaël Fijalkow, Youssouf Oualhadj, Hugo Gimbert, École normale supérieure - Cachan (ENS Cachan), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)

Subjects
FOS: Computer and information sciences, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Nested word, Formal Languages and Automata Theory (cs.FL), Timed automaton, Computer Science - Formal Languages and Automata Theory, Decidability, 0102 computer and information sciences, 02 engineering and technology, ω-automaton, 01 natural sciences, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Computer Science - Computer Science and Game Theory, Continuous spatial automaton, 0202 electrical engineering, electronic engineering, information engineering, Probabilistic automata, F.1.1 Models of Computation, B.6.3 Design Aids, Quantum finite automata, Mathematics, Discrete mathematics, Value 1 problem, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Nonlinear Sciences::Cellular Automata and Lattice Gases, 16. Peace & justice, Mobile automaton, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Probabilistic automaton, Automata theory, 020201 artificial intelligence & image processing, Computer Science::Formal Languages and Automata Theory, Computer Science and Game Theory (cs.GT)
Abstract

The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton A, are there words accepted by A with probability arbitrarily close to 1? This problem was proved undecidable recently. We sharpen this result, showing that the undecidability result holds even if the probabilistic automata have only one probabilistic transition. Our main contribution is to introduce a new class of probabilistic automata, called leaktight automata, for which the value 1 problem is shown decidable (and PSPACE-complete). We construct an algorithm based on the computation of a monoid abstracting the behaviours of the automaton, and rely on algebraic techniques developed by Simon for the correctness proof. The class of leaktight automata is decidable in PSPACE, subsumes all subclasses of probabilistic automata whose value 1 problem is known to be decidable (in particular deterministic automata), and is closed under two natural composition operators., Comment: arXiv admin note: significant text overlap with arXiv:1104.3054

Published
2012
Full Text
View/download PDF

12. Blackwell Optimal Strategies in Priority Mean-Payoff Games

Author

Hugo Gimbert, Wieslaw Zielonka, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), and Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Mathematical optimization, Computer Science::Computer Science and Game Theory, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], 010102 general mathematics, Perfect information, Combinatorial game theory, ComputingMilieux_PERSONALCOMPUTING, Mean payoff, TheoryofComputation_GENERAL, 02 engineering and technology, 01 natural sciences, 0202 electrical engineering, electronic engineering, information engineering, Computer Science (miscellaneous), 020201 artificial intelligence & image processing, 0101 mathematics, Parity (mathematics), Mathematical economics, Mathematics
Abstract

International audience; We examine perfect information stochastic mean-payoff games - a class of games containing as special sub-classes the usual mean-payoff games and parity games. We show that deterministic memoryless strategies that are optimal for discounted games with state-dependent discount factors close to 1 are optimal for priority mean-payoff games establishing a strong link between these two classes.

Published
2012
Full Text
View/download PDF

13. Subgame Perfection for Equilibria in Quantitative Reachability Games

Author

Julie De Pril, Hugo Gimbert, Thomas Brihaye, Véronique Bruyère, Institut de Mathématiques [Mons], Université de Mons (UMons), Institute of Computer Science [Mons], University of Mons [Belgium] (UMONS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Gimbert, Hugo

Subjects
TheoryofComputation_MISCELLANEOUS, Computer Science::Computer Science and Game Theory, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], media_common.quotation_subject, Open problem, Perfection, ComputingMilieux_PERSONALCOMPUTING, TheoryofComputation_GENERAL, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Subgame perfect equilibrium, symbols.namesake, Markov perfect equilibrium, Subgame, 010201 computation theory & mathematics, Nash equilibrium, Reachability, 0202 electrical engineering, electronic engineering, information engineering, symbols, [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], 020201 artificial intelligence & image processing, Mathematical economics, Mathematics, media_common
Abstract

International audience; We study turn-based quantitative multiplayer non zero-sum games played on finite graphs with reachability objectives. In such games, each player aims at reaching his own goal set of states as soon as possible. A previous work on this model showed that Nash equilibria (resp. secure equilibria) are guaranteed to exist in the multiplayer (resp. two-player) case. The existence of secure equilibria in the multiplayer case remained, and is still an open problem. In this paper, we focus our study on the concept of subgame perfect equilibrium, a refinement of Nash equilibrium well-suited in the framework of games played on graphs. We also introduce the new concept of subgame perfect secure equilibrium. We prove the existence of subgame perfect equilibria (resp. subgame perfect secure equilibria) in multiplayer (resp. two-player) quantitative reachability games. Moreover, we provide an algorithm deciding the existence of secure equilibria in the multiplayer case.

Published
2012

14. Probabilistic Automata on Finite words: Decidable and Undecidable Problems

Author

Youssouf Oualhadj, Hugo Gimbert, Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)

Subjects
Discrete mathematics, 0209 industrial biotechnology, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, probabilistic automata, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Existential quantification, 0102 computer and information sciences, 02 engineering and technology, Decision problem, 01 natural sciences, Undecidable problem, Decidability, Combinatorics, value 1 problem, Post correspondence problem, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 020901 industrial engineering & automation, 010201 computation theory & mathematics, Probabilistic automaton, Quantum finite automata, Word problem (mathematics), Computer Science::Formal Languages and Automata Theory, Mathematics
Abstract

International audience; This paper tackles three algorithmic problems for probabilis- tic automata on finite words: the Emptiness Problem, the Isolation Prob- lem and the Value 1 Problem. The Emptiness Problem asks, given some probability 0 ≤ λ ≤ 1, whether there exists a word accepted with prob- ability greater than λ, and the Isolation Problem asks whether there exist words whose acceptance probability is arbitrarily close to λ. Both these problems are known to be undecidable [8, 2, 3]. About the Empti- ness problem, we provide a new simple undecidability proof and prove that it is decidable for automata with one probabilistic transition and undecidable for automata with as few as two probabilistic transitions. The Value 1 Problem is the special case of the Isolation Problem when λ = 1 or λ = 0. The decidability of the Value 1 Problem was an open question. We show that the Value 1 Problem is undecidable. Moreover, we introduce a new class of probabilistic automata, ♯-acyclic automata, for which the Value 1 Problem is decidable.

Published
2010
Full Text
View/download PDF

15. Randomness for Free

Author

Hugo Gimbert, Thomas A. Henzinger, Krishnendu Chatterjee, Laurent Doyen, Institute of Science and Technology [Austria] (IST Austria), Laboratoire Spécification et Vérification [Cachan] (LSV), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Petr Hliněný and Antonín Kučera

Subjects
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computer Science::Computer Science and Game Theory, Theoretical computer science, Computer science, 004 Data processing & computer science, 0102 computer and information sciences, Characterization (mathematics), 01 natural sciences, Theoretical Computer Science, Computer Science - Computer Science and Game Theory, 0101 mathematics, Randomness, Mathematics, Discrete mathematics, Basis (linear algebra), [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Transition function, Transition (fiction), Stochastic game, 010102 general mathematics, Mode (statistics), Probabilistic logic, ComputingMilieux_PERSONALCOMPUTING, Randomized algorithms as zero-sum games, Computer Science Applications, Logic in Computer Science (cs.LO), Computational Theory and Mathematics, 010201 computation theory & mathematics, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Information Systems, Computer Science and Game Theory (cs.GT)
Abstract

International audience; We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (both players interact simultaneously); and (b) turn-based (both players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. In this work we present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games.

Published
2010
Full Text
View/download PDF

16. Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata

Author

Anca Muscholl, Hugo Gimbert, Igor Walukiewicz, Blaise Genest, Image & Pervasive Access Lab (IPAL), National University of Singapore (NUS)-MATHEMATIQUES, SCIENCES ET TECHNOLOGIES DE L'INFORMATION ET DE LA COMMUNICATION (UJF)-Agency for science, technology and research [Singapore] (A*STAR)-Centre National de la Recherche Scientifique (CNRS)-Institute for Infocomm Research - I²R [Singapore], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, Distributed and Iterative Algorithms for the Management of Telecommunications Systems (DISTRIBCOM), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Genest, Blaise, Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, and Walukiewicz, Igor

Subjects
Discrete mathematics, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Timed automaton, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 0102 computer and information sciences, 02 engineering and technology, Nonlinear Sciences::Cellular Automata and Lattice Gases, 01 natural sciences, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, DFA minimization, 010201 computation theory & mathematics, Deterministic automaton, 0202 electrical engineering, electronic engineering, information engineering, Quantum finite automata, Automata theory, 020201 artificial intelligence & image processing, Two-way deterministic finite automaton, Nondeterministic finite automaton, Asynchronous cellular automaton, Computer Science::Formal Languages and Automata Theory, Mathematics
Abstract

International audience; Asynchronous automata are parallel compositions of finite- state processes synchronizing over shared variables. A deep theorem due to Zielonka says that every regular trace language can be represented by a deterministic asynchronous automaton. In this paper we improve the construction, in that the size of the obtained asynchronous automaton is polynomial in the size of a given DFA and simply exponential in the number of processes. We show that our construction is optimal within the class of automata produced by Zielonka-type constructions. In particular, we provide the first non trivial lower bound on the size of asynchronous automata.

Published
2010

17. Solving Simple Stochastic Games with Few Random Vertices

Author

Hugo Gimbert, Florian Horn, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centrum voor Wiskunde en Informatica (CWI), Centrum Wiskunde & Informatica (CWI)-Netherlands Organisation for Scientific Research, ERTN GAMES, French project ANR DOTS, ANR-06-SETI-0003,DOTS,Systèmes distribués, ouverts et temporisés(2006), and Networks and Optimization

Subjects
FOS: Computer and information sciences, Class (set theory), Computer Science::Computer Science and Game Theory, General Computer Science, Linear programming, Computer science, G.3, Brute-force search, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Permutation, Simple (abstract algebra), Reachability, Computer Science - Computer Science and Game Theory, 0202 electrical engineering, electronic engineering, information engineering, simple stochastic games, Time complexity, I.2.1, Discrete mathematics, algorithm, Mathematics::Combinatorics, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Perfect information, algorithmic game theory, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Computer Science and Game Theory (cs.GT)
Abstract

Simple stochastic games are two-player zero-sum stochastic games with turn-based moves, perfect information, and reachability winning conditions. We present two new algorithms computing the values of simple stochastic games. Both of them rely on the existence of optimal permutation strategies, a class of positional strategies derived from permutations of the random vertices. The "permutation-enumeration" algorithm performs an exhaustive search among these strategies, while the "permutation-improvement" algorithm is based on successive improvements, \`a la Hoffman-Karp. Our algorithms improve previously known algorithms in several aspects. First they run in polynomial time when the number of random vertices is fixed, so the problem of solving simple stochastic games is fixed-parameter tractable when the parameter is the number of random vertices. Furthermore, our algorithms do not require the input game to be transformed into a stopping game. Finally, the permutation-enumeration algorithm does not use linear programming, while the permutation-improvement algorithm may run in polynomial time.

Published
2009
Full Text
View/download PDF

18. Simple Stochastic Games with Few Random Vertices are Easy to Solve

Author

Florian Horn, Hugo Gimbert, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), ANR DOTS, and ANR-06-SETI-0003,DOTS,Systèmes distribués, ouverts et temporisés(2006)

Subjects
Discrete mathematics, Computer Science::Computer Science and Game Theory, Markov chain, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Stochastic game, Brute-force search, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Running time, Combinatorics, 010201 computation theory & mathematics, Simple (abstract algebra), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Quadratic programming, Mathematics
Abstract

We present a new algorithm for solving Simple Stochastic Games (SSGs). This algorithm is based on an exhaustive search of a special kind of positional optimal strategies, the f-strategies. The running time is O( |VR|! ċ (|V ||E| + |p|) ), where |V |, |VR|, |E| and |p| are respectively the number of vertices, random vertices and edges, and the maximum bit-length of a transition probability. Our algorithm improves existing algorithms for solving SSGs in three aspects. First, our algorithm performs well on SSGs with few random vertices, second it does not rely on linear or quadratic programming, third it applies to all SSGs, not only stopping SSGs.

Published
2009
Full Text
View/download PDF

19. Solving Simple Stochastic Games

Author

Florian Horn, Hugo Gimbert, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Arnold Beckmann, Costas Dimitracopoulos, Benedikt Löwe, and ANR-06-SETI-0003,DOTS,Systèmes distribués, ouverts et temporisés(2006)

Subjects
Discrete mathematics, Computer Science::Computer Science and Game Theory, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Stochastic game, Brute-force search, 010103 numerical & computational mathematics, 0102 computer and information sciences, 01 natural sciences, Running time, 010201 computation theory & mathematics, Simple (abstract algebra), Markov decision process, Quadratic programming, 0101 mathematics, Mathematics
Abstract

International audience; We present a new algorithm for solving Simple Stochastic Games (SSGs), which is fixed parameter tractable when parametrized with the number of random vertices. This algorithm is based on an exhaustive search of a special kind of positional optimal strategies, the f-strategies. The running time is , where and are respectively the number of vertices, random vertices and edges, and the maximum bit-length of a transition probability. Our algorithm improves existing algorithms for solving SSGs in three aspects. First, our algorithm performs well on SSGs with few random vertices, second it does not rely on linear or quadratic programming, third it applies to all SSGs, not only stopping SSGs.

Published
2008
Full Text
View/download PDF

20. Limits of Multi-Discounted Markov Decision Processes

Author

Wiesław Zielonka, Hugo Gimbert, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and French ANR-SETI project AVERISS

Subjects
Discounting, Mathematical optimization, Computer Science::Computer Science and Game Theory, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Stochastic process, Stochastic game, Markov process, TheoryofComputation_GENERAL, 0102 computer and information sciences, 02 engineering and technology, Optimal control, 01 natural sciences, ComputingMethodologies_ARTIFICIALINTELLIGENCE, symbols.namesake, 010201 computation theory & mathematics, Control system, 0202 electrical engineering, electronic engineering, information engineering, symbols, 020201 artificial intelligence & image processing, Markov decision process, Parity (mathematics), Mathematics
Abstract

International audience; Markov decision processes (MDPs) are controllable discrete event systems with stochastic transitions. The payoff received by the controller can be evaluated in different ways, depending on the payoff function the MDP is equipped with. For example a \emph{mean--payoff} function evaluates average performance, whereas a \emph{discounted} payoff function gives more weights to earlier performance by means of a discount factor. Another well--known example is the \emph{parity} payoff function which is used to encode logical specifications~\cite{dagstuhl}. Surprisingly, parity and mean--payoff MDPs share two non--trivial properties: they both have pure stationary optimal strategies~\cite{CourYan:1990,neyman} and they both are approximable by discounted MDPs with multiple discount factors (multi--discounted MDPs)~\cite{dealf:2003,neyman}. In this paper we unify and generalize these results. We introduce a new class of payoff functions called the priority weighted payoff functions, which are generalization of both parity and mean--payoff functions. We prove that priority weighted MDPs admit optimal strategies that are pure and stationary, and that the priority weighted value of an MDP is the limit of the multi--discounted value when discount factors tend to $0$ simultaneously at various speeds.

Published
2007
Full Text
View/download PDF

21. Pure Stationary Optimal Strategies in Markov Decision Processes

Author

Hugo Gimbert, Matematyki, Informatyki i Mechaniki Uniwersytetu Warzawskiego (MIMUW), Uniwersytet Warszawski, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), EURTN GAMES, and Wolfgang Thomas and Pascal Weil

Subjects
game theory, Mathematical optimization, Computer Science::Computer Science and Game Theory, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Existential quantification, stationary strategies, Stochastic game, TheoryofComputation_GENERAL, markov decision process, 0102 computer and information sciences, 02 engineering and technology, Function (mathematics), Mathematical proof, 01 natural sciences, ComputingMethodologies_ARTIFICIALINTELLIGENCE, 010201 computation theory & mathematics, Control theory, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Markov decision process, Game theory, Mathematics, Event (probability theory)
Abstract

International audience; Markov decision processes (MDPs) are controllable discrete event systems with stochastic transitions. Performances of an MDP are evaluated by a payoff function. The controller of the MDP seeks to optimize those performances, using optimal strategies. There exists various ways of measuring performances, i.e. various classes of payoff functions. For example, average performances can be evaluated by a mean-payoff function, peak performances by a limsup payoff function, and the parity payoff function can be used to encode logical specifications. Surprisingly, all the MDPs equipped with mean, limsup or parity payoff functions share a common non-trivial property: they admit pure stationary optimal strategies. In this paper, we introduce the class of prefix-independent and submixing payoff functions, and we prove that any MDP equipped with such a payoff function admits pure stationary optimal strategies. This result unifies and simplifies several existing proofs. Moreover, it is a key tool for generating new examples of MDPs with pure stationary optimal strategies.

Published
2007
Full Text
View/download PDF

22. Perfect Information Stochastic Priority Games

Author

Wiesław Zielonka, Hugo Gimbert, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), French ANR-SETI project AVERISS, and ANR-06-SETI-0001,AVERISS,Vérification automatisée de systèmes logiciels(2006)

Subjects
Computer Science::Computer Science and Game Theory, Discounting, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], media_common.quotation_subject, Stochastic game, ComputingMilieux_PERSONALCOMPUTING, Perfect information, Combinatorial game theory, TheoryofComputation_GENERAL, 0102 computer and information sciences, 02 engineering and technology, Infinity, 01 natural sciences, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Markov decision process, Limit (mathematics), Mathematical economics, Finite set, media_common, Mathematics
Abstract

International audience; We introduce stochastic priority games - a new class of perfect information stochastic games. These games can take two different, but equivalent, forms. In stopping priority games a play can be stopped by the environment after a finite number of stages, however, infinite plays are also possible. In discounted priority games only infinite plays are possible and the payoff is a linear combination of the classical discount payoff and of a limit payoff evaluating the performance at infinity. Shapley games and parity games are special extreme cases of priority games.

Published
2007
Full Text
View/download PDF

23. Deterministic priority mean-payoff games as limits of discounted games

Author

Wiesław Zielonka, Hugo Gimbert, Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego (MIMUW), Uniwersytet Warszawski, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), EURTN GAMES, MIMUW - Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego, University of Warsaw (UW), M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener

Subjects
Discounting, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Stochastic game, ComputingMilieux_PERSONALCOMPUTING, Mean payoff, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, parity games, 010201 computation theory & mathematics, multi-disounted games, ComputerApplications_GENERAL, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Markov decision process, Parity (mathematics), Majumdar, Mathematical economics, Game theory, Mathematics
Abstract

International audience; Inspired by the paper of de Alfaro, Henzinger and Majumdar about discounted $\mu$-calculus we show new surprising links between parity games and different classes of discounted games.

Published
2006
Full Text
View/download PDF

24. Games where you can play optimally without any memory

Author

Wiesław Zielonka, Hugo Gimbert, Gimbert, Hugo, M. Abadi and L. de Alfaro, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), and Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Computer Science::Computer Science and Game Theory, Property (philosophy), [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], Computer science, Stochastic game, ComputingMilieux_PERSONALCOMPUTING, TheoryofComputation_GENERAL, Context (language use), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Positional infinite games, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], 020201 artificial intelligence & image processing, Preference relation, Game theory, Mathematical economics
Abstract

International audience; Reactive systems are often modelled as two person antagonistic games where one player represents the system while his adversary represents the environment. Undoubtedly, the most popular games in this context are parity games and their cousins (Rabin, Streett and Muller games). Recently however also games with other types of payments, like discounted or mean-payoff , previously used only in economic context, entered into the area of system modelling and verification. The most outstanding property of parity, mean-payoff and discounted games is the existence of optimal positional (memoryless) strategies for both players. This observation raises two questions: (1) can we characterise the family of payoff mappings for which there always exist optimal positional strategies for both players and (2) are there other payoff mappings with practical or theoretical interest and admitting optimal positional strategies. This paper provides a complete answer to the first question by presenting a simple necessary and sufficient condition on payoff mapping guaranteeing the existence of optimal positional strategies. As a corollary to this result we show the following remarkable property of payoff mappings: if both players have optimal positional strategies when playing solitary one-player games then also they have optimal positional strategies for two-player games.

Published
2005

25. Parity and Exploration Games on Infinite Graphs

Author

Hugo Gimbert, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), EURTN GAMES, and Jerzy Marcinkowski and Andrzej Tarlecki

Subjects
Infinite game, Computer Science::Computer Science and Game Theory, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], ComputingMilieux_PERSONALCOMPUTING, Pushdown automaton, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Countable set, 020201 artificial intelligence & image processing, Boolean combination, Tree automaton, Parity (mathematics), Game theory, Mathematics
Abstract

International audience; This paper examines two players' turn-based perfect-information games played on infinite graphs. Our attention is focused on the classes of games where winning conditions are boolean combinations of the following two conditions: (1) the first one states that an infinite play is won by player $0$ if during the play infinitely many different vertices were visited, (2) the second one is the well known parity condition generalized to a countable number of priorities. We show that, in most cases, both players have positional winning strategies and we characterize their respective winning sets. In the special case of pushdown graphs, we use these results to show that the sets of winning positions are regular and we show how to compute them as well as positional winning strategies in exponential time.

Published
2004
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results