Nash $\epsilon $-equilibria for stochastic games with total reward functions: an approach through Markov decision processes

Francisco J. González-Padilla; Raúl Montes-de-Oca

Displaying similar documents to “Nash $ϵ$ -equilibria for stochastic games with total reward functions: an approach through Markov decision processes”

Empirical approximation in Markov games under unbounded payoff: discounted and average criteria

Fernando Luque-Vásquez, J. Adolfo Minjárez-Sosa (2017)

Kybernetika

Similarity:

This work deals with a class of discrete-time zero-sum Markov games whose state process $\{x_{t}\}$ evolves according to the equation $x_{t + 1} = F (x_{t}, a_{t}, b_{t}, ξ_{t}),$ where $a_{t}$ and $b_{t}$ represent the actions of player 1 and 2, respectively, and $\{ξ_{t}\}$ is a sequence of independent and identically distributed random variables with unknown distribution $θ$ . Assuming possibly unbounded payoff, and using the empirical distribution to estimate $θ$ , we introduce approximation schemes for the value of the game as well as for optimal strategies considering...

An optimal strong equilibrium solution for cooperative multi-leader-follower Stackelberg Markov chains games

Kristal K. Trejo, Julio B. Clempner, Alexander S. Poznyak (2016)

Kybernetika

Similarity:

This paper presents a novel approach for computing the strong Stackelberg/Nash equilibrium for Markov chains games. For solving the cooperative $n$ -leaders and $m$ -followers Markov game we consider the minimization of the $L_{p} -$ norm that reduces the distance to the utopian point in the Euclidian space. Then, we reduce the optimization problem to find a Pareto optimal solution. We employ a bi-level programming method implemented by the extraproximal optimization approach for computing the strong...

Infinite $G_{δ}$ -games with imperfect information

D. Blackwell (1969)

Applicationes Mathematicae

Similarity:

Applications of limited information strategies in Menger's game

Steven Clontz (2017)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

As shown by Telgársky and Scheepers, winning strategies in the Menger game characterize $σ$ -compactness amongst metrizable spaces. This is improved by showing that winning Markov strategies in the Menger game characterize $σ$ -compactness amongst regular spaces, and that winning strategies may be improved to winning Markov strategies in second-countable spaces. An investigation of 2-Markov strategies introduces a new topological property between $σ$ -compact and Menger spaces.

On the Variational Inequality and Tykhonov Well-Posedness in Game Theory

C. A. Pensavalle, G. Pieri (2010)

Bollettino dell'Unione Matematica Italiana

Similarity:

Consider a M-player game in strategic form $G=(X_{1},\cdots,X_{M},g_{1},\cdots,g_{M})$ where the set $X_{i}$ is a closed interval of real numbers and the payoff function $g_{i}$ is concave and differentiable with respect to the variable $x_{i}\in X_{i}$ , for any $i=1,\cdots,M$ . The aim of this paper is to find appropriate conditions on the payoff functions under the well-posedness with respect to the related variational inequality is equivalent to the formulation of the Tykhonov well-posedness in a game context. The idea of the proof is to appeal to a third equivalence,...

Systems of Bellman Equations to Stochastic Differential Games with Discount Control

Alain Bensoussan, Jens Frehse (2008)

Bollettino dell'Unione Matematica Italiana

Similarity:

We consider two dimensional diagonal elliptic systems $\Delta u+au=H(x,u,\nabla u)$ which arise from stochastic differential games with discount control. The Hamiltonians $H$ have quadratic growth in $\nabla u$ and a special structure which has notyet been covered by regularity theory. Without smallness condition on $H$ , the existence of a regular solution is established.

Some applications of the point-open subbase game

D. Guerrero Sánchez, Vladimir Vladimirovich Tkachuk (2017)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Given a subbase $𝒮$ of a space $X$ , the game $P O (𝒮, X)$ is defined for two players $P$ and $O$ who respectively pick, at the $n$ -th move, a point $x_{n} \in X$ and a set $U_{n} \in 𝒮$ such that $x_{n} \in U_{n}$ . The game stops after the moves ${x_{n}, U_{n} : n \in ø}$ have been made and the player $P$ wins if $⋃_{n \in ø} U_{n} = X$ ; otherwise $O$ is the winner. Since $P O (𝒮, X)$ is an evident modification of the well-known point-open game $P O (X)$ , the primary line of research is to describe the relationship between $P O (X)$ and $P O (𝒮, X)$ for a given subbase $𝒮$ . It turns out that, for any subbase $𝒮$ , the player $P$ has a winning...

Chocolate games that satisfy the inequality $y \leq ⌊ \frac{z}{k} ⌋$ for $k = 1, 2$ and Grundy numbers

Shunsuke Nakamura, Ryo Hanafusa, Wataru Ogasa, Takeru Kitagawa, Ryohei Miyadera (2013)

Visual Mathematics

Similarity:

Metastability in reversible diffusion processes I: Sharp asymptotics for capacities and exit times

Anton Bovier, Michael Eckhoff, Véronique Gayrard, Markus Klein (2004)

Journal of the European Mathematical Society

Similarity:

We develop a potential theoretic approach to the problem of metastability for reversible diffusion processes with generators of the form $- ϵ Δ + \nabla F (\cdot) \nabla$ on $ℝ^{d}$ or subsets of $ℝ^{d}$ , where $F$ is a smooth function with finitely many local minima. In analogy to previous work on discrete Markov chains, we show that metastable exit times from the attractive domains of the minima of $F$ can be related, up to multiplicative errors that tend to one as $ϵ ↓ 0$ , to the capacities of suitably constructed sets. We show that...

Covariance structure of wide-sense Markov processes of order k ≥ 1

Arkadiusz Kasprzyk, Władysław Szczotka (2006)

Applicationes Mathematicae

Similarity:

A notion of a wide-sense Markov process $X_{t}$ of order k ≥ 1, $X_{t} \sim W M (k)$ , is introduced as a direct generalization of Doob’s notion of wide-sense Markov process (of order k=1 in our terminology). A base for investigation of the covariance structure of $X_{t}$ is the k-dimensional process $x_{t} = (X_{t - k + 1}, . . ., X_{t})$ . The covariance structure of $X_{t} \sim W M (k)$ is considered in the general case and in the periodic case. In the general case it is shown that $X_{t} \sim W M (k)$ iff $x_{t}$ is a k-dimensional WM(1) process and iff the covariance function of $x_{t}$ has the triangular...

More on the Ehrenfeucht-Fraisse game of length ω₁

Tapani Hyttinen, Saharon Shelah, Jouko Vaananen (2002)

Fundamenta Mathematicae

Similarity:

By results of [9] there are models and for which the Ehrenfeucht-Fraïssé game of length ω₁, $E F G_{ω ₁} (,)$ , is non-determined, but it is consistent relative to the consistency of a measurable cardinal that no such models have cardinality ≤ ℵ₂. We now improve the work of [9] in two ways. Firstly, we prove that the consistency strength of the statement “CH and $E F G_{ω ₁} (,)$ is determined for all models and of cardinality ℵ₂” is that of a weakly compact cardinal. On the other hand, we show that if $2^{ℵ ₀} < 2^{ℵ ₃}$ , T is a countable...

On pathwise uniqueness for stochastic differential equations driven by stable Lévy processes

Nicolas Fournier (2013)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We study a one-dimensional stochastic differential equation driven by a stable Lévy process of order $α$ with drift and diffusion coefficients $b$ , $σ$ . When $α \in (1, 2)$ , we investigate pathwise uniqueness for this equation. When $α \in (0, 1)$ , we study another stochastic differential equation, which is equivalent in law, but for which pathwise uniqueness holds under much weaker conditions. We obtain various results, depending on whether $α \in (0, 1)$ or $α \in (1, 2)$ and on whether the driving stable process is symmetric or not. Our...

Topological games and product spaces

Salvador García-Ferreira, R. A. González-Silva, Artur Hideyuki Tomita (2002)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In this paper, we deal with the product of spaces which are either $𝒢$ -spaces or $𝒢_{p}$ -spaces, for some $p \in ω^{*}$ . These spaces are defined in terms of a two-person infinite game over a topological space. All countably compact spaces are $𝒢$ -spaces, and every $𝒢_{p}$ -space is a $𝒢$ -space, for every $p \in ω^{*}$ . We prove that if ${X_{μ} : μ < ω_{1}}$ is a set of spaces whose product $X = \prod_{μ < ω_{1}} X_{μ}$ is a $𝒢$ -space, then there is $A \in {[ω_{1}]}^{\leq ω}$ such that $X_{μ}$ is countably compact for every $μ \in ω_{1} ∖ A$ . As a consequence, $X^{ω_{1}}$ is a $𝒢$ -space iff $X^{ω_{1}}$ is countably compact, and if $X^{2^{𝔠}}$ is a $𝒢$ -space,...

Time-varying Markov decision processes with state-action-dependent discount factors and unbounded costs

Beatris A. Escobedo-Trujillo, Carmen G. Higuera-Chan (2019)

Kybernetika

Similarity:

In this paper we are concerned with a class of time-varying discounted Markov decision models $ℳ_{n}$ with unbounded costs $c_{n}$ and state-action dependent discount factors. Specifically we study controlled systems whose state process evolves according to the equation $x_{n + 1} = G_{n} (x_{n}, a_{n}, ξ_{n}), n = 0, 1, ...$ , with state-action dependent discount factors of the form $α_{n} (x_{n}, a_{n})$ , where $a_{n}$ and $ξ_{n}$ are the control and the random disturbance at time $n$ , respectively. Assuming that the sequences of functions ${α_{n}}$ , ${c_{n}}$ and ${G_{n}}$ converge, in certain sense, to $α_{\infty}$ ,...

Soft local times and decoupling of random interlacements

Serguei Popov, Augusto Teixeira (2015)

Journal of the European Mathematical Society

Similarity:

In this paper we establish a decoupling feature of the random interlacement process $ℐ^{u} \subset ℤ^{d}$ at level $u$ , $d \geq 3$ . Roughly speaking, we show that observations of $ℐ^{u}$ restricted to two disjoint subsets $A_{1}$ and $A_{2}$ of $ℤ^{d}$ are approximately independent, once we add a sprinkling to the process $ℐ^{u}$ by slightly increasing the parameter $u$ . Our results differ from previous ones in that we allow the mutual distance between the sets $A_{1}$ and $A_{2}$ to be much smaller than their diameters. We then provide an important application...

On the central limit theorem for some birth and death processes

Tymoteusz Chojecki (2011)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Suppose that ${X n : n \geq 0}$ is a stationary Markov chain and $V$ is a certain function on a phase space of the chain, called an observable. We say that the observable satisfies the central limit theorem (CLT) if $Y_{n} : = N^{- 1 / 2} \sum_{n = 0}^{N} V (X_{n})$ converge in law to a normal random variable, as $N \to + \infty$ . For a stationary Markov chain with the $L^{2}$ spectral gap the theorem holds for all $V$ such that $V (X_{0})$ is centered and square integrable, see Gordin [7]. The purpose of this article is to characterize a family of observables $V$ for which the CLT holds...

Displaying similar documents to “Nash ϵ -equilibria for stochastic games with total reward functions: an approach through Markov decision processes”

Displaying similar documents to “Nash $ϵ$ -equilibria for stochastic games with total reward functions: an approach through Markov decision processes”