Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal Strategies in Perfect-Information Stochastic Games with Tail Winning Conditions
277
0
0.0
(
0
)
Added by
Hugo Gimbert
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Hugo Gimbert
Ask ChatGPT about the research
No Arabic abstract
We prove that optimal strategies exist in every perfect-information stochastic game with finitely many states and actions and a tail winning condition.
rate research
Read More
We examine the problem of the existence of optimal deterministic stationary strategiesintwo-players antagonistic (zero-sum) perfect information stochastic games with finitely many states and actions.We show that the existenceof such strategies follows from the existence of optimal deterministic stationarystrategies for some derived one-player games.Thus we reducethe problem from two-player to one-player games (Markov decisionproblems), where usually it is much easier to tackle.The reduction is very general, it holds not only for all possible payoff mappings but alsoin more a general situations whereplayers preferences are not expressed by payoffs.
We consider extensive games with perfect information with well-founded game trees and study the problems of existence and of characterization of the sets of subgame perfect equilibria in these games. We also provide such characterizations for two classes of these games in which subgame perfect equilibria exist: two-player zero-sum games with, respectively, two and three outcomes.
This paper studies a planar multiplayer Homicidal Chauffeur reach-avoid differential game, where each pursuer is a Dubins car and each evader has simple motion. The pursuers aim to protect a goal region cooperatively from the evaders. Due to the high-dimensional strategy space among pursuers, we decompose the whole game into multiple one-pursuer-one-evader subgames, each of which is solved in an analytical approach instead of solving Hamilton-Jacobi-Isaacs equations. For each subgame, an evasion region (ER) is introduced, based on which a pursuit strategy guaranteeing the winning of a simple-motion pursuer under specific conditions is proposed. Motivated by the simple-motion pursuer, a strategy for a Dubins-car pursuer is proposed when the pursuer-evader configuration satisfies separation condition (SC) and interception orientation (IO). The necessary and sufficient condition on capture radius, minimum turning radius and speed ratio to guarantee the pursuit winning is derived. When the IO is not satisfied (Non-IO), a heading adjustment pursuit strategy is proposed, and the condition to achieve IO within a finite time, is given. Then, a two-step pursuit strategy is proposed for the SC and Non-IO case. A non-convex optimization problem is introduced to give a condition guaranteeing the winning of the pursuer. A polynomial equation gives a lower bound of the non-convex problem, providing a sufficient and efficient pursuit winning condition. Finally, these pairwise outcomes are collected for the pursuer-evader matching. Simulations are provided to illustrate the theoretical results.
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.
Evolutionarily stable strategy (ESS) is a key concept in evolutionary game theory. ESS provides an evolutionary stability criterion for biological, social and economical behaviors. In this paper, we develop a new approach to evaluate ESS in symmetric two player games with fuzzy payoffs. Particularly, every strategy is assigned a fuzzy membership that describes to what degree it is an ESS in presence of uncertainty. The fuzzy set of ESS characterize the nature of ESS. The proposed approach avoids loss of any information that happens by the defuzzification method in games and handles uncertainty of payoffs through all steps of finding an ESS. We use the satisfaction function to compare fuzzy payoffs, and adopts the fuzzy decision rule to obtain the membership function of the fuzzy set of ESS. The theorem shows the relation between fuzzy ESS and fuzzy Nash quilibrium. The numerical results illustrate the proposed method is an appropriate generalization of ESS to fuzzy payoff games.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
