Search

The paper analyzes the notion of an unbeatable strategy as a game-theoretic solution concept. A general framework (games with relative preferences) suitable for the analysis of this concept is proposed. Basic properties of unbeatable strategies are presented and a number of examples and applications considered. [ABSTRACT FROM AUTHOR]

To attenuate the effect of disturbances on control performance, a multi‐step adaptive critic control (MsACC) framework is developed to solve zero‐sum games for discrete‐time nonlinear systems. The MsACC algorithm utilizes multi‐step policy evaluation to obtain the solution of the Hamilton–Jacobi–Isaac equation, which is faster than that of the one‐step policy evaluation. The convergence rate of the MsACC algorithm is adjustable by varying the step size of the policy evaluation. In addition, the stability and convergence of the MsACC algorithm are proved under certain conditions. In order to realize the MsACC algorithm, three neural networks are established to approximate the control input, the disturbance input, and the cost function, respectively. Finally, the effectiveness of the MsACC algorithm is verified by two simulation examples, including a linear system and a nonlinear plant. [ABSTRACT FROM AUTHOR]

We consider a general type of non-Markovian impulse control problems under adverse non-linear expectation or, more specifically, the zero-sum game problem where the adversary player decides the probability measure. We show that the upper and lower value functions satisfy a dynamic programming principle (DPP). We first prove the dynamic programming principle (DPP) for a truncated version of the upper value function in a straightforward manner. Relying on a uniform convergence argument then enables us to show the DPP for the general setting. Following this, we use an approximation based on a combination of truncation and discretization to show that the upper and lower value functions coincide, thus establishing that the game has a value and that the DPP holds for the lower value function as well. Finally, we show that the DPP admits a unique solution and give conditions under which a saddle point for the game exists. As an example, we consider a stochastic differential game (SDG) of impulse versus classical control of path-dependent stochastic differential equations (SDEs). [ABSTRACT FROM AUTHOR]

We study repeated zero-sum games where one of the players pays a certain cost each time he changes his action. We derive the properties of the value and optimal strategies as a function of the ratio between the switching costs and the stage payoffs. In particular, the strategies exhibit a robustness property and typically do not change with a small perturbation of this ratio. Our analysis extends partially to the case where the players are limited to simpler strategies that are history independent―namely, static strategies. In this case, we also characterize the (minimax) value and the strategies for obtaining it. Funding: The project leading to this publication has received funding from the French government under the "France 2030" investment plan managed by the French National Research Agency [Grant ANR-17-EURE-0020] and from the Excellence Initiative of Aix-Marseille University–A*MIDEX. Y. Tsodikovich was supported in part by the Israel Science Foundation [Grants 2566/20, 1626/18, and 448/22]. X. Venel acknowledges the financial support of the French National Research Agency through Project CIGNE [ANR-15-CE38-0007-01]. [ABSTRACT FROM AUTHOR]

In this paper, a novel parallel learning framework is developed to solve zero-sum games for discrete-time nonlinear systems. Briefly, the purpose of this study is to determine a tentative function according to the prior knowledge of the value iteration (VI) algorithm. The learning process of the parallel controllers can be guided by the tentative function. That is to say, the neighborhood of the optimal cost function can be compressed within a small range via two typical exploration policies. Based on the parallel learning framework, a novel dichotomy VI algorithm is established to accelerate the learning speed. It is shown that the parallel controllers will converge to the optimal policy from contrary initial policies. Finally, two typical systems are used to demonstrate the learning performance of the constructed dichotomy VI algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the optimal control strategies for model‐free zero‐sum games involving the H∞$$ {H}_{\infty } $$ control. The key contribution is the development of a Q‐learning algorithm for linear quadratic games without knowing the system dynamics. The finite‐horizon setting is more practical than the infinite‐horizon setting, but it is difficult to solve the time‐varying Riccati equation associated with the finite‐horizon setting directly. The proposed algorithm is shown to solve the time‐varying Riccati equation iteratively without the use of models, and numerical experiments on aircraft dynamics demonstrate the algorithm's efficiency. [ABSTRACT FROM AUTHOR]

A novel policy gradient (PG) adaptive dynamic programming method is developed to deal with nonlinear discrete-time zero-sum games with unknown dynamics. To facilitate the implementation, a policy iteration algorithm is established to approximate the iterative Q-function, as well as the control and disturbance policies via three neural network (NN) approximators, respectively. Then, the iterative Q-function is exploited to update the control and disturbance policies via PG method. To stabilize the training process and improve the data usage efficiency, the experience replay technique is applied to train the weight vectors of the three NNs by using mini-batch empirical data from replay memory. Furthermore, the convergence in terms of the iterative Q-function is proved. Simulation results of two numerical examples are provided to show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we present a Q-learning framework for solving finite-horizon zero-sum game problems involving the H ∞ control of linear system without knowing the dynamics. Research in the past mainly focused on solving problems in infinite horizon with completely measurable state. However, in the practical engineering, the system state is not always directly accessible, and it is difficult to solve the time-varying Riccati equation associated with the finite-horizon setting directly either. The main contribution of the proposed model-free algorithm is to determine the optimal output feedback policies without measurement state in finite-horizon setting. To achieve this goal, we first describe the Q-function caused by finite-horizon problems in the context of state feedback, then we parameterize the Q-functions as input–output vectors functions. Finally, the numerical examples on aircraft dynamics demonstrate the algorithm's efficiency. [ABSTRACT FROM AUTHOR]

In this paper, we deal with two-person zero-sum games with fuzzy goals. We investigated the cases where the membership functions of the players are nonlinear. We examined how the solutions should be if the membership functions of players were exponential functions. In case players' membership functions are exponential, we developed a new method for the maximin solution according to a degree of attainment of the fuzzy goals. An application was made to show the effectiveness of the method. [ABSTRACT FROM AUTHOR]

In this paper, a synergetic learning structure-based neuro-optimal fault tolerant control (SLSNOFTC) method is proposed for unknown nonlinear continuous-time systems with actuator failures. Under the framework of the synergetic learning structure (SLS), the optimal control input and the actuator failure are viewed as two subsystems. Then, the fault tolerant control (FTC) problem can be regarded as a two-player zero-sum differential game according to the game theory. A radial basis function neural network-based identifier, which uses the measured input/output data, is constructed to identify the completely unknown system dynamics. To develop the SLSNOFTC method, the Hamilton–Jacobi–Isaacs equation is solved by an asymptotically stable critic neural network (ASCNN) which is composed of cooperative adaptive tuning laws. Besides, with the help of the Lyapunov stability analysis, the identification error, the weight error of ASCNN, and all signals of closed-loop system are guaranteed to be converged to zero asymptotically, rather than uniformly ultimately bounded. Numerical simulation examples further verify the effectiveness and reliability of the proposed method. [ABSTRACT FROM AUTHOR]

Continuous Patrolling Sometimes it is necessary to have a Patroller (on foot, in a car, or maybe a drone) move around a network so as to prevent an intruder (the Attacker) from infiltrating or otherwise ruining the network operation. The "attack" could be, for example, removing a painting from the Louvre, crossing a border, or planting a bomb. The first possibility could take place at only a discrete set of points on the network, say, nodes. However, the last two types of attack could take place anywhere. The latter continuous problem has been modelled as a game by Steve Alpern, Thuy Bui, Thomas Lidbetter, and Katerina Papadaki in the article "Continuous Patrolling Games." The Attacker decides when and where to attack (the duration of the attack is specified by the problem), whereas the Patroller chooses a unit speed path, possibly periodic. If the Patroller passes the attacked point while the attack is going on, he wins the game, as the attack is thwarted. Otherwise the attack is successful, and the Attacker wins the game. The authors determine optimal strategies for both players for many classes of networks and find good strategies that work on any network. These ideas could be adapted to real-life patrolling problems on networks. We study a patrolling game played on a network Q, considered as a metric space. The Attacker chooses a point of Q (not necessarily a node) to attack during a chosen time interval of fixed duration. The Patroller chooses a unit speed path on Q and intercepts the attack (and wins) if she visits the attacked point during the attack-time interval. This zero-sum game models the problem of protecting roads or pipelines from an adversarial attack. The payoff to the maximizing Patroller is the probability that the attack is intercepted. Our results include the following: (i) a solution to the game for any network Q, as long as the time required to carry out the attack is sufficiently short; (ii) a solution to the game for all tree networks that satisfy a certain condition on their extremities; and (iii) a solution to the game for any attack duration for stars with one long arc and the remaining arcs equal in length. We present a conjecture on the solution of the game for arbitrary trees and establish it in certain cases. Funding: Financial support from the National Science Foundation [Grant CMMI-1935826] is gratefully acknowledged. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2346. [ABSTRACT FROM AUTHOR]

In this work, we consider systems whose components suffer from clock offsets and quantization and study the effect of those on a reinforcement learning (RL) algorithm. Specifically, we consider an off-policy iterative RL algorithm for continuous-time systems, which uses input and state data to approximate the Nash-equilibrium of a zero-sum game. However, the data used by this algorithm are not consistent with one another, in that each of them originates from a slightly different time instant of the past, hence putting the convergence of the algorithm in question. We prove that, given that these timing inconsistencies remain below a certain threshold, the iterative off-policy RL algorithm will still converge epsilon-closely to the desired Nash policy. However, this result is conditional to a certain Lipschitz continuity and differentiability condition on the input-state data collected, which is indispensable in the presence of clock offsets. A similar result is also derived when quantization of the measured state is considered. Finally, unlike prior work, we provide a sufficiently rich data condition for the execution of the iterative RL algorithm, which can be verified a priori across all iteration indices. Simulations are performed, which verify and clarify theoretical findings. [ABSTRACT FROM AUTHOR]

This paper proposes a novel way to compare classes of strategic games based on their sets of pure Nash equilibria. This approach is then used to relate the classes of zero-sum games, polymatrix, and k-polymatrix games. This paper concludes with a conjecture that k-polymatrix games form an increasing chain of classes. [ABSTRACT FROM AUTHOR]

This paper investigates the robust social optimum problem for linear quadratic mean field control systems by the direct approach, where model uncertainty appears in both drift and diffusion terms of each agent. We take a zero-sum game approach by considering local disturbance as the control of an adversarial player. Under centralized information structure, we first obtain the necessary and sufficient condition for the existence of open-loop and closed-loop saddle points, which are characterized by the solvability of forward-backward stochastic differential equations (FBSDEs) and two coupled Riccati equations, respectively. By considering the infinite system, we next design a set of decentralized open-loop strategies based on mean field FBSDEs and obtain closed-loop strategies in terms of two uncoupled Riccati equations. Finally, the performance of the proposed decentralized strategies is analyzed and the efficiency is verified by numerical simulation. [ABSTRACT FROM AUTHOR]

This paper designs a novel event-based adaptive learning method for solving zero-sum games (ZSGs) of nonlinear systems with incomplete known dynamics. Firstly, a discounted cost is introduced for the system with nonzero equilibrium point to obtain the near-optimal strategy pair. Then, the employment of integral reinforcement learning (IRL) makes it unnecessary to acquire the model of the drift dynamics. To approximate the solution of the Hamilton-Jacobi-Isaacs equations (HJIEs), single-critic network is constructed with the modified tuning law utilizing preprocessed data. For purpose of increasing algorithm efficiency, the event-triggered mechanism (ETM) is introduced which could obviate Zeno behavior. Furthermore, the state and critic weight vector error are proved to be uniform ultimate bounded (UUB) through Lyapunov approach. Finally, the effectiveness of the proposed method is validated by conducting a simulation experiment. [ABSTRACT FROM AUTHOR]

In this paper, an adjustable Q-learning scheme is developed to solve the discrete-time nonlinear zero-sum game problem, which can accelerate the convergence rate of the iterative Q-function sequence. First, the monotonicity and convergence of the iterative Q-function sequence are analyzed under some conditions. Moreover, by employing neural networks, the model-free tracking control problem can be overcome for zero-sum games. Second, two practical algorithms are designed to guarantee the convergence with accelerated learning. In one algorithm, an adjustable acceleration phase is added to the iteration process of Q-learning, which can be adaptively terminated with convergence guarantee. In another algorithm, a novel acceleration function is developed, which can adjust the relaxation factor to ensure the convergence. Finally, through a simulation example with the practical physical background, the fantastic performance of the developed algorithm is demonstrated with neural networks. [ABSTRACT FROM AUTHOR]

The infinite-horizon zero-sum game of a linear system can be resorted to solve a Game algebraic Riccati equation (GARE) with indefinite quadratic term. Double-loop policy iteration algorithm is often used to find the solution of such GARE, but its calculation is usually time-consuming. In this work, we propose a novel model-based single-loop policy iteration algorithm to solve GARE and the convergence of the algorithm is guaranteed by the boundness of the iterative sequence and the comparison result. Furthermore, we devise a data-driven single-loop policy iteration algorithm for solving linear zero-sum games, without requiring the knowledge of system dynamics. Compared to the existing Newton's single-loop methods, the initialization of our algorithms is significantly relaxed and easier to implement. Two numerical examples are included to illustrate the proposed algorithms. [ABSTRACT FROM AUTHOR]

We set up a game theoretical model to analyze the optimal attacking intensity of sports teams during a game. We suppose that two teams can dynamically choose among more or less offensive actions and that the scoring probability of each team depends on both teams' actions. We assume a zero sum setting and characterize a Nash equilibrium in terms of the unique solution of an Isaacs equation. We present results from numerical experiments showing that a change in the score has a strong impact on strategies, but not necessarily on scoring intensities. We give examples where strategies strongly depend on the score, the scoring intensities not at all. [ABSTRACT FROM AUTHOR]

In zero-sum asynchronous revision games, players revise their actions only at exogenous random times. Players' revision times follow Poisson processes, independent across players. Payoffs are obtained only at the deadline by implementing the last prepared actions in the “component game”. We characterize the value of this game as the unique solution of an ordinary differential equation and show it is continuous in all parameters. As the duration of the game increases, the limit revision value does not depend on the initial position and is included between the min-max and max-min of the component game. We characterize the equilibrium for 2 × 2 games. When the component game min-max and max-min differ, the revision game equilibrium have a wait-and-wrestle structure: far form the deadline, players stay put at sur-place action profile, close to the deadline, they take best responses to the action of the opponent. [ABSTRACT FROM AUTHOR]

We study the asymptotics of a class of two-player, zero-sum stochastic game with incomplete information on one side when the time span between two consecutive stages vanishes. The informed player observes the realization of a Markov chain on which the payoffs depend, whereas the noninformed player only observes his opponent's actions. We show the existence of a limit value; this value is characterized through an auxiliary optimization problem and as the solution of a Hamilton-Jacobi equation. [ABSTRACT FROM AUTHOR]

In this paper, stochastic optimal strategy for unknown linear discrete-time system quadratic zero-sum games in input-output form with communication imperfections such as network-induced delays and packet losses, otherwise referred to as networked control system (NCS) zero-sum games, relating to the H8 optimal control problem is solved in a forward-in-time manner. First, the linear discrete-time zero sum state space representation is transformed into a linear NCS in the state space form after incorporating random delays and packet losses and then into the input-output form. Subsequently, the stochastic optimal approach, referred to as adaptive dynamic programming (ADP), is introduced which estimates the cost or value function to solve the infinite horizon optimal regulation of unknown linear NCS quadratic zero-sum games in the presence of communication imperfections. The optimal control and worst case disturbance inputs are derived based on the estimated value function in the absence of state measurements. An update law for tuning the unknown parameters of the value function estimator is derived and Lyapunov theory is used to show that all signals are asymptotically stable (AS) and that the estimated control and disturbance signals converge to optimal control and worst case disturbances, respectively. Simulation results are included to verify the theoretical claims. [ABSTRACT FROM AUTHOR]

We analyze the complexity of equilibria problems for a class of strategic zero-sum games, called angel-daemon games. Those games were introduced to asses the performance of the execution of a web orchestration on a moderate faulty or under stress environment. Angel-daemon games are a natural example of zero-sum games whose representation is naturally succinct. We show that the problems of deciding the existence of a pure Nash equilibrium or of a dominant strategy for a given player are ${\Sigma}^{p}_{2}$-complete. Furthermore, computing the value of an angel-daemon game is EXP-complete. Thus, our results match the already known classification of the corresponding problems for the generic families of succinctly represented games with exponential number of actions. [ABSTRACT FROM AUTHOR]

Abstract: This paper addresses the solution of large zero-sum matrix games using randomized methods. We formalize a procedure, termed as the sampled security policy (SSP) algorithm, by which a player can compute policies that, with a high confidence, are security policies against an adversary using randomized methods to explore the possible outcomes of the game. The SSP algorithm essentially consists of solving a stochastically sampled subgame that is much smaller than the original game. We also propose a randomized algorithm, termed as the sampled security value (SSV) algorithm, which computes a high-confidence security-level (i.e., worst-case outcome) for a given policy, which may or may not have been obtained using the SSP algorithm. For both the SSP and the SSV algorithms we provide results to determine how many samples are needed to guarantee a desired level of confidence. We start by providing results when the two players sample policies with the same distribution and subsequently extend these results to the case of mismatched distributions. We demonstrate the usefulness of these results in a hide-and-seek game that exhibits exponential complexity. [Copyright &y& Elsevier]

In 1951, Dantzig showed the equivalence of linear programming problems and two-person zero-sum games. However, in the description of his reduction from linear programs to zero-sum games, he noted that there was one case in which the reduction does not work. This also led to incomplete proofs of the relationship between the Minimax Theorem of game theory and the Strong Duality Theorem of linear programming. In this note, we fill these gaps. [ABSTRACT FROM AUTHOR]

We observe that a symmetric two-player zero-sum game has a pure strategy equilibrium if and only if it is not a generalized rock-paper-scissors matrix. Moreover, we show that every finite symmetric quasiconcave two-player zero-sum game has a pure equilibrium. Further sufficient conditions for existence are provided. Our findings extend to general two-player zero-sum games using the symmetrization of zero-sum games due to von Neumann. We point out that the class of symmetric two-player zero-sum games coincides with the class of relative payoff games associated with symmetric two-player games. This allows us to derive results on the existence of finite population evolutionary stable strategies. [ABSTRACT FROM AUTHOR]