Search

We study two-player games on finite graphs. Turn-based games have many nice properties, but concurrent games are harder to tame: e.g. turn-based stochastic parity games have positional optimal strategies, whereas even basic concurrent reachability games may fail to have optimal strategies. We study concurrent stochastic parity games, and identify a local structural condition that, when satisfied at each state, guarantees existence of positional optimal strategies for both players.

This article presents a multiscale, non-linear and directional statistical characterization of images based on the estimation of the skewness, flatness, entropy and distance from Gaussianity of the spatial increments. These increments are characterized by their magnitude and direction; they allow us to characterize the multiscale properties directionally and to explore anisotropy. To describe the evolution of the probability density function of the increments with their magnitude and direction, we use the skewness to probe the symmetry, the entropy to measure the complexity, and both the flatness and distance from Gaussianity to describe the shape. These four quantities allow us to explore the anisotropy of the linear correlations and non-linear dependencies of the field across scales. First, we validate the methodology on two-dimensional synthetic scale-invariant fields with different multiscale properties and anisotropic characteristics. Then, we apply it on two synthetic turbulent velocity fields: a perfectly isotropic and homogeneous one, and a channel flow where boundaries induce inhomogeneity and anisotropy. Our characterization unambiguously detects the anisotropy in the second case, where our quantities report scaling properties that depend on the direction of analysis. Furthermore, we show in both cases that turbulent velocity fluctuations are always isotropic, when the mean velocity profile is adequately removed.

We investigate concurrent two-player win/lose stochastic games on finite graphs with prefix-independent objectives. We characterize subgame optimal strategies and use this characterization to show various memory transfer results: 1) For a given (prefix-independent) objective, if every game that has a subgame almost-surely winning strategy also has a positional one, then every game that has a subgame optimal strategy also has a positional one; 2) Assume that the (prefix-independent) objective has a neutral color. If every turn-based game that has a subgame almost-surely winning strategy also has a positional one, then every game that has a finite-choice (notion to be defined) subgame optimal strategy also has a positional one. We collect or design examples to show that our results are tight in several ways. We also apply our results to B\"uchi, co-B\"uchi, parity, mean-payoff objectives, thus yielding simpler statements.

We study two-player concurrent stochastic games on finite graphs, with B\"uchi and co-B\"uchi objectives. The goal of the first player is to maximize the probability of satisfying the given objective. Following Martin's determinacy theorem for Blackwell games, we know that such games have a value. Natural questions are then: does there exist an optimal strategy, that is, a strategy achieving the value of the game? what is the memory required for playing (almost-)optimally? The situation is rather simple to describe for turn-based games, where positional pure strategies suffice to play optimally in games with parity objectives. Concurrency makes the situation intricate and heterogeneous. For most {\omega}-regular objectives, there do indeed not exist optimal strategies in general. For some objectives (that we will mention), infinite memory might also be required for playing optimally or almost-optimally. We also provide characterizations of local interactions of the players to ensure positionality of (almost-)optimal strategies for B\"uchi and co-B\"uchi objectives. This characterization relies on properties of game forms underpinning the formalism for defining local interactions of the two players. These well-behaved game forms are like elementary bricks which, when they behave well in isolation, can be assembled in graph games and ensure the good property for the whole game.

We study the shape of convective rolls in the Marine Atmospheric Boundary Layer from Synthetic Aperture Radar images of the ocean. We propose a multiscale analysis with structure functions which allow an easy generalization to analyse high-order statistics and so to finely describe the shape of the rolls. The two main results are : 1) second order structure function characterizes the size and direction of rolls just like correlation or power spectrum do, 2) high order statistics can be studied with skewness and Flatness which characterize the asymmetry and intermittency of rolls respectively. From the best of our knowledge, this is the first time that the asymmetry and intermittency of rolls is shown from radar images of the ocean surface.

We introduce an index based on information theory to quantify the stationarity of a stochastic process.The index compares on the one hand the information contained in the increment at the time scale $\tau$ of the process at time $t$ with, on the other hand, the extra information in the variable at time $t$ that is not present at time $t-\tau$. By varying the scale $\tau$, the index can explore a full range of scales. We thus obtain a multi-scale quantity that is not restricted to the first two moments of the density distribution, nor to the covariance, but that probes the complete dependences in the process. This index indeed provides a measure of the regularity of the process at a given scale.Not only is this index able to indicate whether a realization of the process is stationary, but its evolution across scales also indicates how rough and non-stationary it is.We show how the index behaves for various synthetic processes proposed to model fluid turbulence, as well as on experimental fluid turbulence measurements., Comment: Entropy, MDPI, 2021

We study two-player reachability games on finite graphs. At each state the interaction between the players is concurrent and there is a stochastic Nature. Players also play stochastically. The literature tells us that 1) Player B, who wants to avoid the target state, has a positional strategy that maximizes the probability to win (uniformly from every state) and 2) from every state, for every {\epsilon} > 0, Player A has a strategy that maximizes up to {\epsilon} the probability to win. Our work is two-fold. First, we present a double-fixed-point procedure that says from which state Player A has a strategy that maximizes (exactly) the probability to win. This is computable if Nature's probability distributions are rational. We call these states maximizable. Moreover, we show that for every {\epsilon} > 0, Player A has a positional strategy that maximizes the probability to win, exactly from maximizable states and up to {\epsilon} from sub-maximizable states. Second, we consider three-state games with one main state, one target, and one bin. We characterize the local interactions at the main state that guarantee the existence of an optimal Player A strategy. In this case there is a positional one. It turns out that in many-state games, these local interactions also guarantee the existence of a uniform optimal Player A strategy. In a way, these games are well-behaved by design of their elementary bricks, the local interactions. It is decidable whether a local interaction has this desirable property.

Daily pandemic surveillance, often achieved through the estimation of the reproduction number, constitutes a critical challenge for national health authorities to design countermeasures. In an earlier work, we proposed to formulate the estimation of the reproduction number as an optimization problem, combining data-model fidelity and space-time regularity constraints, solved by nonsmooth convex proximal minimizations. Though promising, that first formulation significantly lacks robustness against the Covid-19 data low quality (irrelevant or missing counts, pseudo-seasonalities,.. .) stemming from the emergency and crisis context, which significantly impairs accurate pandemic evolution assessments. The present work aims to overcome these limitations by carefully crafting a functional permitting to estimate jointly, in a single step, the reproduction number and outliers defined to model low quality data. This functional also enforces epidemiology-driven regularity properties for the reproduction number estimates, while preserving convexity, thus permitting the design of efficient minimization algorithms, based on proximity operators that are derived analytically. The explicit convergence of the proposed algorithm is proven theoretically. Its relevance is quantified on real Covid-19 data, consisting of daily new infection counts for 200+ countries and for the 96 metropolitan France counties, publicly available at Johns Hopkins University and Sant{\'e}-Publique-France. The procedure permits automated daily updates of these estimates, reported via animated and interactive maps. Open-source estimation procedures will be made publicly available.

We study infinite two-player win/lose games $(A,B,W)$ where $A,B$ are finite and $W \subseteq (A \times B)^\omega$. At each round Player 1 and Player 2 concurrently choose one action in $A$ and $B$, respectively. Player 1 wins iff the generated sequence is in $W$. Each history $h \in (A \times B)^*$ induces a game $(A,B,W_h)$ with $W_h := \{\rho \in (A \times B)^\omega \mid h \rho \in W\}$. We show the following: if $W$ is in $\Delta^0_2$ (for the usual topology), if the inclusion relation induces a well partial order on the $W_h$'s, and if Player 1 has a winning strategy, then she has a finite-memory winning strategy. Our proof relies on inductive descriptions of set complexity, such as the Hausdorff difference hierarchy of the open sets. Examples in $\Sigma^0_2$ and $\Pi^0_2$ show some tightness of our result. Our result can be translated to games on finite graphs: e.g. finite-memory determinacy of multi-energy games is a direct corollary, whereas it does not follow from recent general results on finite memory strategies., Comment: 15 pages (+ appendix), submitted to CSL 2022

In general, finite concurrent two-player reachability games are only determined in a weak sense: the supremum probability to win can be approached via stochastic strategies, but cannot be realized. We introduce a class of concurrent games that are determined in a much stronger sense, and in a way, it is the larger class with this property. To this end, we introduce the notion of \emph{local interaction} at a state of a graph game: it is a \emph{game form} whose outcomes (i.e. a table whose entries) are the next states, which depend on the concurrent actions of the players. By definition, a game form is \emph{determined} iff it always yields games that are determined via deterministic strategies when used as a local interaction in a Nature-free, one-shot reachability game. We show that if all the local interactions of a graph game with Borel objective are determined game forms, the game itself is determined: if Nature does not play, one player has a winning strategy; if Nature plays, both players have deterministic strategies that maximize the probability to win. This constitutes a clear-cut separation: either a game form behaves poorly already when used alone with basic objectives, or it behaves well even when used together with other well-behaved game forms and complex objectives. Existing results for positional and finite-memory determinacy in turn-based games are extended this way to concurrent games with determined local interactions (CG-DLI).

We compare the macroscopic and the local plastic behavior of a model amorphous solid based on two radically different numerical descriptions. On the one hand, we simulate glass samples by atomistic simulations. On the other, we implement a mesoscale elasto-plastic model based on a solid-mechanics description. The latter is extended to consider the anisotropy of the yield surface via statistically distributed local and discrete weak planes on which shear transformations can be activated. To make the comparison as quantitative as possible, we consider the simple case of a quasistatically driven two-dimensional system in the stationary flow state and compare mechanical observables measured on both models over the same length scales. We show that the macroscale response, including its fluctuations, can be quantitatively recovered for a range of elasto-plastic mesoscale parameters. Using a newly developed method that makes it possible to probe the local yield stresses in atomistic simulations, we calibrate the local mechanical response of the elasto-plastic model at different coarse-graining scales. In this case, the calibration shows a qualitative agreement only for an optimized subset of mesoscale parameters and for sufficiently coarse probing length scales. This calibration allows us to establish a length scale for the mesoscopic elements that corresponds to an upper bound of the shear transformation size, a key physical parameter in elasto-plastic models. We find that certain properties naturally emerge from the elasto-plastic model. In particular, we show that the elasto-plastic model reproduces the Bauschinger effect, namely the plasticity-induced anisotropy in the stress-strain response. We discuss the successes and failures of our approach, the impact of different model ingredients and propose future research directions for quantitative multi-scale models of amorphous plasticity.

The overarching goal of the present work is to contribute to the understanding of the relations between fetal heart rate (FHR) temporal dynamics and the well-being of the fetus, notably in terms of predicting cardiovascular decompensation (CVD). It makes uses of an established animal model of human labor, where fourteen near-term ovine fetuses subjected to umbilical cord occlusions (UCO) were instrumented to permit regular intermittent measurements of metabolites, pH, and continuous recording of electrocardiogram (ECG) and systemic arterial blood pressure (to identify CVD) during UCO. ECG-derived FHR was digitized at the sampling rate of 1000 Hz and resampled to 4Hz, as used in clinical routine. We focused on four FHR variability features which are tunable to temporal scales of FHR dynamics, robustly computable from FHR sampled at $4$Hz and within short-time sliding windows, hence permitting a time-dependent, or local, analysis of FHR which helps dealing with signal noise. Results show the sensitivity of the proposed features for early detection of CVD, correlation to metabolites and pH, useful for early acidosis detection and the importance of coarse time scales (2.5 to 8 seconds) which are not disturbed by the low FHR sampling rate. Further, we introduce the performance of an individualized self-referencing metric of the distance to healthy state, based on a combination of the four features. We demonstrate that this novel metric, applied to clinically available FHR temporal dynamics alone, accurately predicts the time occurrence of CVD which heralds a clinically significant degradation of the fetal health reserve to tolerate the trial of labor., Comment: 34 pages (preprint version) 10 figures

The Ornstein-Uhlenbeck process can be seen as a paradigm of a finite-variance and statistically stationary rough random walk. Furthermore, it is defined as the unique solution of a Markovian stochastic dynamics and shares the same local regularity as the one of the Brownian motion. A natural generalization of this process able to reproduce the local regularity of a fractional Brownian motion of parameter H is provided by the fractional Ornstein-Uhlenbeck process. Based on previous works, we propose to include some Multifractal corrections to this picture using a Gaussian Multiplicative Chaos. The aforementioned process, called a Multifractal fractional Ornstein-Uhlenbeck process, is a statistically stationary finite-variance process. Its underlying dynamics is non-Markovian, although non-anticipating and causal. The numerical scheme and theoretical approach are based on a regularization procedure, that gives a meaning to this dynamical evolution, which unique solution converges towards a well-behaved stochastic process., Comment: 21 pages, 3 figures, a reference added

For decades, two-player (antagonistic) games on graphs have been a framework of choice for many important problems in theoretical computer science. A notorious one is controller synthesis, which can be rephrased through the game-theoretic metaphor as the quest for a winning strategy of the system in a game against its antagonistic environment. Depending on the specification, optimal strategies might be simple or quite complex, for example having to use (possibly infinite) memory. Hence, research strives to understand which settings allow for simple strategies. In 2005, Gimbert and Zielonka provided a complete characterization of preference relations (a formal framework to model specifications and game objectives) that admit memoryless optimal strategies for both players. In the last fifteen years however, practical applications have driven the community toward games with complex or multiple objectives, where memory -- finite or infinite -- is almost always required. Despite much effort, the exact frontiers of the class of preference relations that admit finite-memory optimal strategies still elude us. In this work, we establish a complete characterization of preference relations that admit optimal strategies using arena-independent finite memory, generalizing the work of Gimbert and Zielonka to the finite-memory case. We also prove an equivalent to their celebrated corollary of great practical interest: if both players have optimal (arena-independent-)finite-memory strategies in all one-player games, then it is also the case in all two-player games. Finally, we pinpoint the boundaries of our results with regard to the literature: our work completely covers the case of arena-independent memory (e.g., multiple parity objectives, lower- and upper-bounded energy objectives), and paves the way to the arena-dependent case (e.g., multiple lower-bounded energy objectives).

We describe how to analyze the wide class of non stationary processes with stationary centered increments using Shannon information theory. To do so, we use a practical viewpoint and define ersatz quantities from time-averaged probability distributions. These ersatz versions of entropy, mutual information and entropy rate can be estimated when only a single realization of the process is available. We abundantly illustrate our approach by analyzing Gaussian and non-Gaussian self-similar signals, as well as multi-fractal signals. Using Gaussian signals allow us to check that our approach is robust in the sense that all quantities behave as expected from analytical derivations. Using the stationarity (independence on the integration time) of the ersatz entropy rate, we show that this quantity is not only able to fine probe the self-similarity of the process but also offers a new way to quantify the multi-fractality.

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., Comment: 23 pages

A recently developed Projection-based Digital Image Correlation (P-DVC) method is here extended to 4D (space and time) displacement field measurement and mechanical identification based on a single radiograph per loading step instead of volumes as in standard DVC methods. Two levels of data reductions are exploited, namely, reduction of the data acquisition (and time) by a factor of 1000 and reduction of the solution space by exploiting model reduction techniques. The analysis of a complete tensile elastoplastic test composed of 127 loading steps performed in 6 minutes is presented. The 4D displacement field as well as the elastoplastic constitutive law are identified. Keywords: Image-based identification, Model reduction, Fast 4D identification, In-situ tomography measurements. INTRODUCTION Identification and validation of increasingly complex mechanical models is a major concern in experimental solid mechanics. The recent developments of computed tomography coupled with in-situ tests provide extremely rich and non-destructive analyses [1]. In the latter cases, the sample was imaged inside a tomograph, either with interrupted mechanical load or with a continuously evolving loading and on-the-fly acquisitions (as ultra-fast X-ray synchrotron tomography, namely, 20 Hz full scan acquisition for the study of crack propagation [2]). Visualization of fast transformations, crack openings, or unsteady behavior become accessible. Combined with full-field measurements, in-situ tests offer a quantitative basis for identifying a broad range of mechanical behavior., Comment: SEM 2019, Jun 2019, Reno, United States

Sophisticated mass attacks, especially when exploiting zero-day vulnerabilities, have the potential to cause destructive damage to organizations and critical infrastructure. To timely detect and contain such attacks, collaboration among the defenders is critical. By correlating real-time detection information (alerts) from multiple sources (collaborative intrusion detection), defenders can detect attacks and take the appropriate defensive measures in time. However, although the technical tools to facilitate collaboration exist, real-world adoption of such collaborative security mechanisms is still underwhelming. This is largely due to a lack of trust and participation incentives for companies and organizations. This paper proposes TRIDEnT, a novel collaborative platform that aims to enable and incentivize parties to exchange network alert data, thus increasing their overall detection capabilities. TRIDEnT allows parties that may be in a competitive relationship, to selectively advertise, sell and acquire security alerts in the form of (near) real-time peer-to-peer streams. To validate the basic principles behind TRIDEnT, we present an intuitive game-theoretic model of alert sharing, that is of independent interest, and show that collaboration is bound to take place infinitely often. Furthermore, to demonstrate the feasibility of our approach, we instantiate our design in a decentralized manner using Ethereum smart contracts and provide a fully functional prototype., Comment: 28 pages

We study finite-memory (FM) determinacy in games on finite graphs, a central question for applications in controller synthesis, as FM strategies correspond to implementable controllers. We establish general conditions under which FM strategies suffice to play optimally, even in a broad multi-objective setting. We show that our framework encompasses important classes of games from the literature, and permits to go further, using a unified approach. While such an approach cannot match ad-hoc proofs with regard to tightness of memory bounds, it has two advantages: first, it gives a widely-applicable criterion for FM determinacy; second, it helps to understand the cornerstones of FM determinacy, which are often hidden but common in proofs for specific (combinations of) winning conditions., Comment: Conference version appeared in FSTTCS 2018

Consider concurrent, infinite duration, two-player win/lose games played on graphs. If the winning condition satisfies some simple requirement, the existence of Player 1 winning (finite-memory) strategies is equivalent to the existence of winning (finite-memory) strategies in finitely many derived one-player games. Several classical winning conditions satisfy this simple requirement. Under an additional requirement on the winning condition, the non-existence of Player 1 winning strategies from all vertices is equivalent to the existence of Player 2 stochastic strategies winning almost surely from all vertices. Only few classical winning conditions satisfy this additional requirement, but a fairness variant of o, Comment: 29 pages, 2 figures

In 1998 Zielonka simplified the proofs of memoryless determinacy of infinite parity games. In 2018 Haddad simplified some proofs of memoryless determinacy of finite parity games. This article adapts Haddad's technique for infinite parity games. Two proofs are given, a shorter one and a more constructive one. None of them uses Zielonka's traps and attractors., Comment: 10 pages, 6 figures

Intrapartum fetal heart rate (FHR) monitoring constitutes a reference tool in clinical practice to assess the baby health status and to detect fetal acidosis. It is usually analyzed by visual inspection grounded on FIGO criteria. Characterization of Intrapartum fetal heart rate temporal dynamics remains a challenging task and continuously receives academic research efforts. Complexity measures, often implemented with tools referred to as \emph{Approximate Entropy} (ApEn) or \emph{Sample Entropy} (SampEn), have regularly been reported as significant features for intrapartum FHR analysis. We explore how Information Theory, and especially {\em auto mutual information} (AMI), is connected to ApEn and SampEn and can be used to probe FHR dynamics. Applied to a large (1404 subjects) and documented database of FHR data, collected in a French academic hospital, it is shown that i) auto mutual information outperforms ApEn and SampEn for acidosis detection in the first stage of labor and continues to yield the best performance in the second stage; ii) Shannon entropy increases as labor progresses, and is always much larger in the second stage;iii) babies suffering from fetal acidosis additionally show more structured temporal dynamics than healthy ones and that this progressive structuration can be used for early acidosis detection.

We study the never-worse relation (NWR) for Markov decision processes with an infinite-horizon reachability objective. A state q is never worse than a state p if the maximal probability of reaching the target set of states from p is at most the same value from q, regard- less of the probabilities labelling the transitions. Extremal-probability states, end components, and essential states are all special cases of the equivalence relation induced by the NWR. Using the NWR, states in the same equivalence class can be collapsed. Then, actions leading to sub- optimal states can be removed. We show the natural decision problem associated to computing the NWR is coNP-complete. Finally, we ex- tend a previously known incomplete polynomial-time iterative algorithm to under-approximate the NWR.

We consider N-player non-zero sum games played on finite trees (i.e., sequential games), in which the players have the right to repeatedly update their respective strategies (for instance, to improve the outcome wrt to the current strategy profile). This generates a dynamics in the game which may eventually stabilise to a Nash Equilibrium (as with Kukushkin's lazy improvement), and we argue that it is interesting to study the conditions that guarantee such a dynamics to terminate. We build on the works of Le Roux and Pauly who have studied extensively one such dynamics, namely the Lazy Improvement Dynamics. We extend these works by first defining a turn-based dynamics, proving that it terminates on subgame perfect equilibria, and showing that several variants do not terminate. Second, we define a variant of Kukushkin's lazy improvement where the players may now form coalitions to change strategies. We show how properties of the players' preferences on the outcomes affect the termination of this dynamics, and we thereby characterise classes of games where it always terminates (in particular two-player games)., Comment: In Proceedings GandALF 2017, arXiv:1709.01761

Nash equilibrium (NE) is a central concept in game theory. Here we prove formally a published theorem on existence of an NE in two proof assistants, Coq and Isabelle: starting from a game with finitely many outcomes, one may derive a game by rewriting each of these outcomes with either of two basic outcomes, namely that Player 1 wins or that Player 2 wins. If all ways of deriving such a win/lose game lead to a game where one player has a winning strategy, the original game also has a Nash equilibrium. This article makes three other contributions: first, while the original proof invoked linear extension of strict partial orders, here we avoid it by generalizing the relevant definition. Second, we notice that the theorem also implies the existence of a secure equilibrium, a stronger version of NE that was introduced for model checking. Third, we also notice that the constructive proof of the theorem computes secure equilibria for non-zero-sum priority games (generalizing parity games) in quasi-polynomial time., Comment: In Proceedings GandALF 2017, arXiv:1709.01761

For generic systems exhibiting power law behaviors, and hence multiscale dependencies, we propose a new, and yet simple, tool to analyze multifractality and intermittency, after noticing that these concepts are directly related to the deformation of a probability density function from Gaussian at large scales to non-Gaussian at smaller scales. Our framework is based on information theory, and uses Shannon entropy and Kullback-Leibler divergence. We propose an extensive application to three-dimensional fully developed turbulence, seen here as a paradigmatic complex system where intermittency was historically defined. Moreover, the concepts of scale invariance and multifractality were extensively studied in this field and, most importantly, benchmarked. We compute our measure on experimental Eulerian velocity measurements, as well as on synthetic processes and a phenomenological model of fluid turbulence.Our approach is very general and does not require any underlying model of the system, although it can probe the relevance of such a model.

We study multi-player turn-based games played on (potentially infinite) directed graphs. An outcome is assigned to every play of the game. Each player has a preference relation on the set of outcomes which allows him to compare plays. We focus on the recently introduced notion of weak subgame perfect equilibrium (weak SPE). This is a variant of the classical notion of SPE, where players who deviate can only use strategies deviating from their initial strategy in a finite number of histories. Having an SPE in a game implies having a weak SPE but the contrary is generally false. We propose general conditions on the structure of the game graph and on the preference relations of the players that guarantee the existence of a weak SPE, that additionally is finite-memory. From this general result, we derive two large classes of games for which there always exists a weak SPE: (i) the games with a finite-range outcome function, and (ii) the games with a finite underlying graph and a prefix-independent outcome function. For the second class, we identify conditions on the preference relations that guarantee memoryless strategies for the weak SPE., Comment: 28 pages