BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Stéphane Le Roux

Stéphane Le Roux appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryLogic in Computer Sciencemath.LOFormal Languages and Automata TheoryComputational Complexitymath.GNmath.PRMultiagent Systems

Catalog footprint

What is connected

10works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2020arXiv

Time-aware uniformization of winning strategies

Two-player win/lose games of infinite duration are involved in several disciplines including computer science and logic. If such a game has deterministic winning strategies, one may ask how simple such strategies can get. The answer may help with actual implementation, or to win despite imperfect information, or to conceal sensitive information especially if the game is repeated. Given a concurrent two-player win/lose game of infinite duration, this article considers equivalence relations over histories of played actions. A classical restriction used here is that equivalent histories have equal length, hence \emph{time awareness}. A sufficient condition is given such that if a player has winning strategies, she has one that prescribes the same action at equivalent histories, hence \emph{uniformization}. The proof is fairly constructive and preserves finiteness of strategy memory, and counterexamples show relative tightness of the result. Several corollaries follow for games with states and colors.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Connected Choice and the Brouwer Fixed Point Theorem

We study the computational content of the Brouwer Fixed Point Theorem in the Weihrauch lattice. Connected choice is the operation that finds a point in a non-empty connected closed set given by negative information. One of our main results is that for any fixed dimension the Brouwer Fixed Point Theorem of that dimension is computably equivalent to connected choice of the Euclidean unit cube of the same dimension. Another main result is that connected choice is complete for dimension greater than or equal to two in the sense that it is computably equivalent to Weak Kőnig's Lemma. While we can present two independent proofs for dimension three and upwards that are either based on a simple geometric construction or a combinatorial argument, the proof for dimension two is based on a more involved inverse limit construction. The connected choice operation in dimension one is known to be equivalent to the Intermediate Value Theorem; we prove that this problem is not idempotent in contrast to the case of dimension two and upwards. We also prove that Lipschitz continuity with Lipschitz constants strictly larger than one does not simplify finding fixed points. Finally, we prove that finding a connectedness component of a closed subset of the Euclidean unit cube of any dimension greater or equal to one is equivalent to Weak Kőnig's Lemma. In order to describe these results, we introduce a representation of closed subsets of the unit cube by trees of rational complexes.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract)

We consider a dynamical approach to sequential games. By restricting the convertibility relation over strategy profiles, we obtain a semi-potential (in the sense of Kukushkin), and we show that in finite games the corresponding restriction of better-response dynamics will converge to a Nash equilibrium in quadratic time. Convergence happens on a per-player basis, and even in the presence of players with cyclic preferences, the players with acyclic preferences will stabilize. Thus, we obtain a candidate notion for rationality in the presence of irrational agents. Moreover, the restriction of convertibility can be justified by a conservative updating of beliefs about the other players strategies. For infinite sequential games we can retain convergence to a Nash equilibrium (in some sense), if the preferences are given by continuous payoff functions; or obtain a transfinite convergence if the outcome sets of the game are Delta^0_2 sets.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Equilibria in multi-player multi-outcome infinite sequential games

We investigate the existence of certain types of equilibria (Nash, $\varepsilon$-Nash, subgame perfect, $\varepsilon$-subgame perfect, Pareto-optimal) in multi-player multi-outcome infinite sequential games. We use two fundamental approaches: one requires strong topological restrictions on the games, but produces very strong existence results. The other merely requires some very basic determinacy properties to still obtain some existence results. Both results are transfer results: starting with the existence of some equilibria for a small class of games, they allow us to conclude the existence of some type of equilibria for a larger class. To make the abstract results more concrete, we investigate as a special case infinite sequential games with real-valued payoff functions. Depending on the class of payoff functions (continuous, upper semi-continuous, Borel) and whether the game is zero-sum, we obtain various existence results for equilibria. Our results hold for games with two or up to countably many players.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Extending Finite Memory Determinacy to Multiplayer Games

We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium built from finite memory strategies for the corresponding class of multi-player multi-outcome games. This generalizes a previous result by Brihaye, De Pril and Schewe. For most of our conditions we provide counterexamples showing that they cannot be dispensed with. Our proofs are generally constructive, that is, provide upper bounds for the memory required, as well as algorithms to compute the relevant winning strategies.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Extending Finite Memory Determinacy to Multiplayer Games

We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium built from finite memory strategies for the corresponding class of multi-player multi-outcome games. This generalizes a previous result by Brihaye, De Pril and Schewe. We provide a number of example that separate the various criteria we explore. Our proofs are generally constructive, that is, provide upper bounds for the memory required, as well as algorithms to compute the relevant Nash equilibria.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Minkowski games

We introduce and study Minkowski games. These are two player games, where the players take turns to chose positions in $\mathbb{R}^d$ based on some rules. Variants include boundedness games, where one player wants to keep the positions bounded, and the other wants to escape to infinity; as well as safety games, where one player wants to stay within a prescribed set, while the other wants to leave it. We provide some general characterizations of which player can win such games, and explore the computational complexity of the associated decision problems. A natural representation of boundedness games yields coNP-completeness, whereas the safety games are undecidable.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

From winning strategy to Nash equilibrium

Game theory is usually considered applied mathematics, but a few game-theoretic results, such as Borel determinacy, were developed by mathematicians for mathematics in a broad sense. These results usually state determinacy, i.e. the existence of a winning strategy in games that involve two players and two outcomes saying who wins. In a multi-outcome setting, the notion of winning strategy is irrelevant yet usually replaced faithfully with the notion of (pure) Nash equilibrium. This article shows that every determinacy result over an arbitrary game structure, e.g. a tree, is transferable into existence of multi-outcome (pure) Nash equilibrium over the same game structure. The equilibrium-transfer theorem requires cardinal or order-theoretic conditions on the strategy sets and the preferences, respectively, whereas counter-examples show that every requirement is relevant, albeit possibly improvable. When the outcomes are finitely many, the proof provides an algorithm computing a Nash equilibrium without significant complexity loss compared to the two-outcome case. As examples of application, this article generalises Borel determinacy, positional determinacy of parity games, and finite-memory determinacy of Muller games.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multi-scale metastable dynamics and the asymptotic stationary distribution of perturbed Markov chains

We consider a simple but important class of metastable discrete time Markov chains, which we call perturbed Markov chains. Basically, we assume that the transition matrices depend on a parameter $\varepsilon$, and converge as $\varepsilon$. We further assume that the chain is irreducible for $\varepsilon$ but may have several essential communicating classes when $\varepsilon$. This leads to metastable behavior, possibly on multiple time scales. For each of the relevant time scales, we derive two effective chains. The first one describes the (possibly irreversible) metastable dynamics, while the second one is reversible and describes metastable escape probabilities. Closed probabilistic expressions are given for the asymptotic transition probabilities of these chains, but we also show how to compute them in a fast and numerically stable way. As a consequence, we obtain efficient algorithms for computing the committor function and the limiting stationary distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Computable Closed Euclidean Subsets with and without Computable Points

The empty set of course contains no computable point. On the other hand, surprising results due to Zaslavskii, Tseitin, Kreisel, and Lacombe assert the existence of NON-empty co-r.e. closed sets devoid of computable points: sets which are `large' in the sense of positive Lebesgue measure. We observe that a certain size is in fact necessary: every non-empty co-r.e. closed real set without computable points has continuum cardinality. This leads us to investigate for various classes of computable real subsets whether they necessarily contain a (not necessarily effectively findable) computable point.

0 citations0 reviewsNo code linkedOpen access