192 results
Search Results
2. Olimpiadi della Matematica: il punto di vista di un docente/responsabile.
- Author
-
Fiorini, Paolo
- Abstract
The Mathematical Olympiad, or Mathematical Championships, is a major event for the Italian schools. The present paper aims to give the reader an overview of how they work, focusing on describing the main organization structure and analyzing them from the point of view of a teacher which is both a District Coordinator and a School representative. Finally, some thoughts on the impact of the project on the students and the whole school system will be set forth. [ABSTRACT FROM AUTHOR]
- Published
- 2024
3. HOW TO DESIGN Fun Math Games for Kids, Teens, Seniors, and In-Betweeners.
- Author
-
Shapiro, Phil
- Subjects
- *
ART , *COMPUTER peripherals , *GAMES , *MATHEMATICS , *SOFTWARE architecture , *EDUCATIONAL technology , *ELECTRONIC spreadsheets , *PUBLIC libraries , *WORLD Wide Web , *VIDEO recording - Abstract
The article reports on the author's initiative to design and share fun, paper-based math games for diverse age groups, utilizing tools like LibreOffice Calc, and details the evolution of the Pairs Math Game, its varied versions, and potential uses in educational and community settings. The author also emphasizes promoting playful conversations about numbers and fostering a sense of agency in students to invent their math questions.
- Published
- 2024
4. Seeking strategy design for distributed nonsmooth games and its application.
- Author
-
Deng, Zhenhua and Luo, Jin
- Subjects
- *
DIFFERENTIAL inclusions , *CONVEX sets , *ELECTRICITY markets , *NASH equilibrium , *GAMES , *DISTRIBUTED algorithms - Abstract
This paper investigates the nonsmooth noncooperative games (NGs) over unbalanced digraphs, where each player has a nondifferentiable payoff function. Meanwhile, these players are subject to local nonsmooth inequality constraints, local convex set constraints and coupled equality constraints. Due to the coexistence of nonsmooth payoff functions, unbalanced digraphs and constraints, existing generalized Nash equilibrium (GNE) seeking strategies are fail to address our problem. Based on subgradient descents, differential inclusions, projection and primal-dual methods, we develop a distributed seeking strategy. Besides, the convergence of the strategy is proved. Finally, the proposed method is applied to electricity market games (EMGs) of smart grids. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. Distributed Nash Equilibrium Seeking for Aggregative Games With Directed Communication Graphs.
- Author
-
Fang, Xiao, Wen, Guanghui, Zhou, Jialing, Lu, Jinhu, and Chen, Guanrong
- Subjects
- *
NASH equilibrium , *PLUG-in hybrid electric vehicles , *DIRECTED graphs , *DISTRIBUTED algorithms , *UNDIRECTED graphs , *COST functions - Abstract
One key factor affecting the distributed Nash equilibrium (NE) seeking in aggregative games is the unbalanced communication structure for multiple players. Although some results on seeking NE over undirected or weight-balanced graphs were established, how to address the distributed NE seeking problem over general directed communication graphs is still an outstanding challenge. This paper addresses the NE seeking problem for a class of aggregative games with general directed communication graphs. To achieve this objective, two new kinds of distributed discrete-time NE seeking algorithms are developed for aggregative games over fixed digraphs and time-varying digraphs, respectively. In particular, motivated by the heavy-ball method in optimization studies, a momentum term is introduced to the update law of the players’ actions and it is numerically verified that this momentum term accelerates the convergence of the proposed algorithms. For both strongly connected fixed graph and $B$ -strongly connected time-varying graph, it is theoretically proved that the actions of players will converge to the NE of aggregative games for the case of decreasing step-size implemented by the proposed NE seeking algorithms if the cost functions and the aggregation of players satisfy some certain conditions. Finally, the developed NE seeking algorithms are applied to the energy consumption control of plug-in hybrid electric vehicles (PHEVs), which demonstrates the effectiveness of the theoretical results. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
6. An interval noncooperative-cooperative biform game model based on weighted equal contribution division values.
- Author
-
Liang, Kai-Rong, Li, Deng-Feng, Li, Kevin W., and Liu, Jia-Cai
- Subjects
- *
GROUP decision making , *CHARACTERISTIC functions , *NASH equilibrium , *GAMES , *COALITIONS - Abstract
• Propose an interval biform game model to handle both strategy choice and coalition formation. • Develop an interval weighted equal contribution division method to solve cooperative games. • Identify existence and necessary conditions of pure strategy Nash equilibriums. • Numerical examples are presented to illustrate the proposed method. This paper develops an interval noncooperative-cooperative biform game (referred to as the interval biform game in short hereafter) model that accounts for both strategy choice and coalition formation while also addressing profit allocation with interval coalition characteristic values. This interval biform game consists of four elements: a finite set of players, their strategy choices, coalitions, and interval coalition characteristic functions, and contains both noncooperative and cooperative parts. The payoffs of different strategies are not directly given a priori in the noncooperative part but obtained by solving interval cooperative games in the cooperative part. To solve the interval cooperative game, we extend a real-valued weighted equal contribution division (WECD) approach to an interval-valued version. Subsequently, an interval acceptability degree comparison method is introduced to compare the interval payoff values. We then establish existence and necessary conditions of pure strategy Nash equilibriums and derive a condition for a Nash equilibrium to be efficient in an interval biform game. Finally, numerical examples are furnished to illustrate the validity and applicability of the proposed framework. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
7. Games of incomplete information: A framework based on belief functions.
- Author
-
Pomeret-Coquot, Pierre, Fargier, Helene, and Martin-Dorel, Érik
- Subjects
- *
TELEVISION game programs , *GAMES - Abstract
This paper proposes a model for incomplete-information games where the knowledge of the players is represented by a Dempster-Shafer belief function. Beyond an extension of the classical definitions, it shows such a game can be transformed into an equivalent hypergraphical complete-information game (without uncertainty), thus generalizing Howson and Rosenthal's theorem to the framework of belief functions and to any number of players. The complexity of this transformation is finally studied and shown to be polynomial in the degree of k -additivity of the mass function. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
8. Rock-paper-scissors may explain evolutionary 'games' in nature.
- Author
-
Cesare, Chris
- Subjects
- *
ROCK-paper-scissors (Game) , *GAMES & psychology , *GAMES , *AGGRESSION (Psychology) , *DECEPTION , *COOPERATION - Abstract
The article discusses the lessons to be learned by scientists from the rock-paper-scissors game. Topics covered include the competing strategies used to derive the game such as aggression, deception and cooperation. Also mentioned is the long-term implications of the game for the behavior of players.
- Published
- 2015
9. Optimal encryption strategy for cyber-physical systems against stealthy attacks with energy constraints: A Stackelberg game approach.
- Author
-
Liu, Xuan and Yang, Guang-Hong
- Subjects
- *
CYBER physical systems , *TRANSPORTATION terminal design & construction , *WATERMARKS , *GAMES , *ATTEMPTED suicide - Abstract
• Compared with the existing results, both the attacker and the defender are considered under a game-theoretic framework. Besides, the energy constraints are introduced to limit the attack times and encryption rank, respectively. • Different from the related works, the worst-case attack schedules and parameters are designed collaboratively to maximize the impact of the stealthy attacks. • The proposed optimal encryption strategies increase the difficulty of launching stealthy attacks and diminish the impact of attacks simultaneously. This paper investigates the problem of encryption strategy for cyber-physical systems based on the Stackelberg game theoretic model with a stealthy attacker and a defender. In order to defend against the attacker who can inject false data without being detected by the detector, an encryption mechanism is proposed. Different from the existing results, the energy constraints are introduced to limit the attack times of attacker and encryption rank of defender, respectively. Under the framework of Stackelberg game, the optimal encryption strategies against worst-case stealthy attacks are designed for accumulative and terminal estimation performance, which increase the difficulty of launching stealthy attacks and diminish the impact of attacks on system performance simultaneously. Finally, simulation examples are provided to demonstrate effectiveness of the proposed strategy. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
10. Informational Cascades With Nonmyopic Agents.
- Author
-
Bistritz, Ilai, Heydaribeni, Nasimeh, and Anastasopoulos, Achilleas
- Subjects
- *
INFORMATION storage & retrieval systems , *PRODUCT quality , *EQUILIBRIUM - Abstract
We consider an environmentwhere players need to decide whether to buy a certain product (or adopt a technology) or not. The product is either good or bad, but its true value is unknown to the players. Instead, each player has her own private information on its quality. Each player can observe the previous actions of other players and estimate the quality of the product. A classic result in the literature shows that in similar settings, informational cascades occur, where learning stops for the whole network and players repeat the actions of their predecessors. In contrast to this literature, in this paper, players get more than one opportunity to act. In each turn, a player is chosen uniformly at random from all the players and can decide to buy the product and leave the market or wait. Her utility is the total expected discounted reward, and thus, myopic strategies may not constitute equilibria. We provide a characterization of perfect Bayesian equilibria (PBEs) with forward-looking strategies through a fixed-point equation of dimensionality that grows only quadratically with the number of players. Using this tractable fixed-point equation, we show the existence of a PBE and characterize PBEs with threshold strategies. Based on this characterization, we study informational cascades in two regimes. First, we show that for a discount factor $\delta$ strictly smaller than 1, informational cascades happen with high probability as the number of players $N$ increases. Furthermore, only a small portion of the total information in the system is revealed before a cascade occurs. Second, and more surprisingly, we show that for a fixed $N$ , and for a sufficiently large $\delta < 1$ , when the product is bad, there exists an equilibrium where an informational cascade can happen only after at least half of the players revealed their private information, and consequently, the probability for a “bad cascade” where all the players buy the product vanishes exponentially with $N$. Finally, when $\delta =1$ and the product is bad, there exists an equilibrium where informational cascades do not happen at all. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
11. Optimal encryption strategy for cyber-physical systems against stealthy attacks with energy constraints: A Stackelberg game approach.
- Author
-
Liu, Xuan and Yang, Guang-Hong
- Subjects
- *
CYBER physical systems , *TRANSPORTATION terminal design & construction , *WATERMARKS , *GAMES , *ATTEMPTED suicide - Abstract
• Compared with the existing results, both the attacker and the defender are considered under a game-theoretic framework. Besides, the energy constraints are introduced to limit the attack times and encryption rank, respectively. • Different from the related works, the worst-case attack schedules and parameters are designed collaboratively to maximize the impact of the stealthy attacks. • The proposed optimal encryption strategies increase the difficulty of launching stealthy attacks and diminish the impact of attacks simultaneously. This paper investigates the problem of encryption strategy for cyber-physical systems based on the Stackelberg game theoretic model with a stealthy attacker and a defender. In order to defend against the attacker who can inject false data without being detected by the detector, an encryption mechanism is proposed. Different from the existing results, the energy constraints are introduced to limit the attack times of attacker and encryption rank of defender, respectively. Under the framework of Stackelberg game, the optimal encryption strategies against worst-case stealthy attacks are designed for accumulative and terminal estimation performance, which increase the difficulty of launching stealthy attacks and diminish the impact of attacks on system performance simultaneously. Finally, simulation examples are provided to demonstrate effectiveness of the proposed strategy. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
12. Minimum cost control of weighted networked evolutionary games with switched topologies and threshold.
- Author
-
Wu, Yue, Li, Lulu, and Alofi, A.S.
- Subjects
- *
COST control , *TOPOLOGY , *GAMES - Abstract
Networked evolutionary games (NEGs) are a class of models that capture the interactions and evolution of strategies among rational agents in a network. In this paper, we study the problem of minimum cost control of NEGs with switched topologies and threshold, where the network structure can change over time and the agents have a minimum payoff requirement to survive. Using the semi-tensor product (STP) of matrices, we express the weighted networked evolutionary game in an algebraic form. Then, we propose an efficient algorithm to design the minimum cost control that ensures the survival of the agents. Finally, we demonstrate the validity of our theoretical results with an example and simulations. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
13. Robust hierarchical games of linear discrete-time systems based on off-policy model-free reinforcement learning.
- Author
-
Ma, Xiao and Yuan, Yuan
- Subjects
- *
REINFORCEMENT learning , *DISCRETE-time systems , *LINEAR systems , *GAMES - Abstract
An off-policy model-free reinforcement learning (RL) algorithm is proposed for a robust hierarchical game while considering incomplete information and input constraints. The robust hierarchical game exhibits characteristics of a Stackelberg–Nash (SN) game, where equilibrium points are designated as Stackelberg–Nash–Saddle equilibrium (SNE) points. An off-policy method is employed for the RL algorithm, addressing input constraints by using excitation input instead of real-time update polices as control inputs. Moreover, a model-free method is implemented for the off-policy RL algorithm, accounting for the challenge posed by incomplete information. The goal of this paper is to develop an off-policy model-free RL algorithm to obtain approximate SNE polices of the robust hierarchical game with incomplete information and input constraints. Furthermore, the convergence and effectiveness of the off-policy model-free RL algorithm are guaranteed by proving the equivalence of Bellman equation between nominal SNE policies and approximate SNE policies. Finally, a simulation is provided to verify the advantage of the developed algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
14. Random games under normal mean–variance mixture distributed independent linear joint chance constraints.
- Author
-
Nguyen, Hoang Nam, Lisser, Abdel, and Singh, Vikas Vikram
- Subjects
- *
NASH equilibrium , *RANDOM variables , *GAMES , *FINANCIAL markets - Abstract
In this paper, we study an n player game where the payoffs as well as the strategy sets are defined using random variables. The payoff function of each player is defined using expected value function and his/her strategy set is defined using a linear joint chance constraint. The random constraint vectors defining the joint chance constraint are independent and follow normal mean–variance mixture distributions. For each player, we reformulate the joint chance constraint in order to prove the existence of a Nash equilibrium using the Kakutani fixed-point theorem under mild assumptions. We illustrate our theoretical results by considering a game between two competing firms in financial market. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
15. Social disruption games in signed networks.
- Author
-
Molinero, Xavier, Riquelme, Fabián, and Serna, Maria
- Subjects
- *
COMPUTATIONAL complexity , *GAMES , *GAME theory , *GRAPH algorithms - Abstract
Signed networks describe many real-world relations among users. Positive connections between two users or vertices generally mean good feelings between them, but negative connections mean bad feelings. A disruptor cycle in a graph is a cycle containing only one negative edge. A signed graph is known to be clusterable if and only if it does not contain a disruptor cycle. In this paper, we study the clusterability of a signed graph from the point of view of game theory introducing social disruption games on signed graphs. In these games, a coalition wins if the subgraph induced by the coalition is non-clusterable, i.e., it contains a disruptor cycle. Moreover, we study parameters and properties of players and compare them to other subclasses of simple games. In addition, we give some complexity results. In particular, we show that, unlike other subclasses of simple games, given a social disruption game, computing its length, deciding whether it is proper, or deciding whether it has a dummy player can be done in polynomial time. However, other problems, such as deciding whether the game is strong, or computing known power indices, remain computationally hard. • We introduce social disruption games on signed graphs to study clusterability. • A coalition wins if the subgraph induced by the coalition is non-clusterable. • We study parameters and properties of players and compare them to other simple games. • We provide different computational complexity results. • For this games, some problems become polynomial, while some others remain hard. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
16. Evaluation and learning in two-player symmetric games via best and better responses.
- Author
-
Yan, Rui, Zhang, Weixian, Deng, Ruiliang, Duan, Xiaoming, Shi, Zongying, and Zhong, Yisheng
- Subjects
- *
MACHINE learning , *LEARNING strategies , *REINFORCEMENT learning , *GAMES - Abstract
This paper focuses on filling the gap between strategy evaluation and strategy learning in two-player symmetric games, as a learning algorithm may converge to the strategies not preferred by an evaluation metric. When a player determines its strategies, it needs to first evaluate candidate strategies without knowing the opponents' decisions. Then, based on the result of the evaluation, a preferred strategy is selected. On the contrary, many multi-agent reinforcement learning algorithms are constructed provided that the strategies of other players are known in each training episode. In this paper, we first introduce two graph-based metrics grounded on sink equilibrium to characterize the preferred strategies of the players in strategy evaluation. These metrics can be regarded as generalized solution concepts in games. Then, we propose two variants of the classical self-play algorithm, named strictly best-response and weakly better-response self-plays , to learn the strategies for the players. By modeling the learning processes as walks over joint-strategy response digraphs, we prove that under some conditions, the learned strategies by two variants are the preferred strategies under two metrics, respectively, which thus fills the evaluation–learning gap, and ensures that the preferred strategies are learned. We also investigate the relationship between the two metrics. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
17. A concept of nucleolus for uncertain coalitional game with application to profit allocation.
- Author
-
Yang, Xiangfeng, Gao, Jinwu, Luo, Sha, and Loia, Vincenzo
- Subjects
- *
NUCLEOLUS , *GAMES - Abstract
Uncertain coalitional game is a type of coalitional games where the transferable payoffs are assumed to be uncertain variables. As solutions of uncertain coalitional game, uncertain core, uncertain Shapley value, and uncertain stable set have been offered. This article further presents a new thought of uncertain nucleolus as another solution to the uncertain coalitional game. Meantime, this paper proves that uncertain nucleolus is nonempty and singleton and proves that uncertain nucleolus is a subset of the uncertain core if the uncertain core is nonempty. Finally, an uncertain nucleolus is applied to resolve a profit allocation problem. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
18. A concept of nucleolus for uncertain coalitional game with application to profit allocation.
- Author
-
Yang, Xiangfeng, Gao, Jinwu, Luo, Sha, and Loia, Vincenzo
- Subjects
- *
NUCLEOLUS , *GAMES - Abstract
Uncertain coalitional game is a type of coalitional games where the transferable payoffs are assumed to be uncertain variables. As solutions of uncertain coalitional game, uncertain core, uncertain Shapley value, and uncertain stable set have been offered. This article further presents a new thought of uncertain nucleolus as another solution to the uncertain coalitional game. Meantime, this paper proves that uncertain nucleolus is nonempty and singleton and proves that uncertain nucleolus is a subset of the uncertain core if the uncertain core is nonempty. Finally, an uncertain nucleolus is applied to resolve a profit allocation problem. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
19. Matrix approach to verification of finite multi-potential games.
- Author
-
Liu, Aixin and Li, Haitao
- Subjects
- *
POTENTIAL functions , *FINITE, The , *MATRIX multiplications , *GAMES , *MATRICES (Mathematics) - Abstract
This paper studies the verification of multi-potential games with a given partition, and proposes a kind of multi-potential equation based on semi-tensor product of matrices. Firstly, the basis of each player's potential function is constructed, based on which, a new formula is established for the calculation of each player's potential function. Secondly, a new potential equation is proposed for the verification of potential games via each player's potential function. Using the new potential equation, a kind of multi-potential equation is constructed for the verification of multi-potential games with a given partition. It is proved that a finite game is a multi-potential game with a given partition if and only if the multi-potential equation has solution. In addition, all possible potential functions are obtained for each group of the partition. An illustrative example is worked out to show the effectiveness of the obtained new results. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
20. Novel fairness-aware co-scheduling for shared cache contention game on chip multiprocessors.
- Author
-
Xiao, Zheng, Chen, Liwen, Wang, Bangyong, Du, Jiayi, and Li, Keqin
- Subjects
- *
MULTIPROCESSORS , *NASH equilibrium , *GAMES , *SHARED workspaces - Abstract
• Propose a novel fairness-aware thread co-scheduling model using non-cooperative game. • Algorithm IA is proposed to solve the Nash equilibrium of non-cooperative game model. • It is theoretically proved that IA has a potential game process and it can converge to Nash equilibrium. • IA is further enhanced by cache partition, reducing the number of misses under the shared cache. Threads running on different cores of chip multiprocessors (CMP) can cause thread performance degradation due to contention for shared resources such as shared L2 cache. Some studies have shown that thread co-scheduling can effectively reduce contention for shared resources. However, in a multi-core system with shared caches, mutual interference between threads is unpredictable. As the number of cores increases, we are unlikely to exhaust all possible co-scheduling schemes. In this paper, a novel fairness-aware thread co-scheduling algorithm base on non-cooperative game is proposed to reduce L2 cache misses. We tried to improve the overall performance of the system by scheduling threads fairly. The originality of this work is to model thread scheduling using a non-cooperative game. The execution time of a thread varies depending on which threads are running on other cores of the same chip, because different thread combinations result in different levels of cache contention. Given the interdependence and competition between threads on the CMP architecture, non-cooperative game is used to solve the problem of thread co-scheduling where each thread is considered as a participant in the game. An iterative algorithm (IA) is proposed to solve the Nash equilibrium of the non-cooperative game in this paper. Subsequently, it is theoretically proved that IA has a potential game process and finally proves that IA can converge to Nash equilibrium in N iterations, where N is the number of threads. The co-scheduling scheme of all threads is obtained by solving the Nash equilibrium of the IA. Finally, the convergence and effectiveness of IA proposed in this paper is verified by experiments. In addition, we use the cache partition to improve the performance of IA. Experimental results show that the number of total cache misses of IA is less than that of the default scheduling algorithm, IA combined with cache partitioning can further reduce the total cache misses. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
21. Stochastic Stability of Perturbed Learning Automata in Positive-Utility Games.
- Author
-
Chasparis, Georgios C.
- Subjects
- *
MACHINE theory , *PROBABILITY measures , *INVARIANT measures , *STOCHASTIC approximation , *MARKOV processes , *STOCHASTIC analysis , *AUTONOMOUS robots - Abstract
This paper considers a class of reinforcement-based learning (namely, perturbed learning automata) and provides a stochastic-stability analysis in repeatedly played, positive-utility, finite strategic-form games. Prior work in this class of learning dynamics primarily analyzes asymptotic convergence through stochastic approximations, where convergence can be associated with the limit points of an ordinary-differential equation (ODE). However, analyzing global convergence through an ODE-approximation requires the existence of a Lyapunov or a potential function, which naturally restricts the analysis to a fine class of games. To overcome these limitations, this paper introduces an alternative framework for analyzing asymptotic convergence that is based upon an explicit characterization of the invariant probability measure of the induced Markov chain. We further provide a methodology for computing the invariant probability measure in positive-utility games, together with an illustration in the context of coordination games. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
22. Public resources allocation using an uncertain cooperative game among vulnerable groups.
- Author
-
Liang, Pei, Hu, Junhua, Liu, Yongmei, and Chen, Xiaohong
- Subjects
- *
RESOURCE allocation , *NONCOOPERATIVE games (Mathematics) , *GAME theory , *GAMES , *PROBLEM solving , *CELL phone systems - Abstract
Purpose: This paper aims to solve the problem of public resource allocation among vulnerable groups by proposing a new method called uncertain α-coordination value based on uncertain cooperative game. Design/methodology/approach: First, explicit forms of uncertain Shapley value with Chouqet integral form and uncertain centre-of-gravity of imputation-set (CIS) value are defined separately on the basis of uncertainty theory and cooperative game. Then, a convex combination of the two values above called the uncertain α-coordination value is used as the best solution. This study proves that the proposed methods meet the basic properties of cooperative game. Findings: The uncertain α-coordination value is used to solve a public medical resource allocation problem in fuzzy coalitions and uncertain payoffs. Compared with other methods, the α-coordination value can solve such problem effectively because it balances the worries of vulnerable group's further development and group fairness. Originality/value: In this paper, an extension of classical cooperative game called uncertain cooperative game is proposed, in which players choose any level of participation in a game and relate uncertainty with the value of the game. A new function called uncertain α-Coordination value is proposed to allocate public resources amongst vulnerable groups in an uncertain environment, a topic that has not been explored yet. The definitions of uncertain Shapley value with Choquet integral form and uncertain CIS value are proposed separately to establish uncertain α-Coordination value. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
23. An LP Approach for Solving Two-Player Zero-Sum Repeated Bayesian Games.
- Author
-
Li, Lichun, Langbort, Cedric, and Shamma, Jeff
- Subjects
- *
TECHNOLOGY convergence , *GAMES , *TREE size , *LINEAR programming , *NASH equilibrium - Abstract
This paper studies two-player zero-sum repeated Bayesian games in which every player has a private type that is unknown to the other player, and the initial probability of the type of every player is publicly known. The types of players are independently chosen according to the initial probabilities, and are kept the same all through the game. At every stage, players simultaneously choose actions, and announce their actions publicly. For finite horizon cases, an explicit linear program is provided to compute players’ security strategies. Moreover, this paper shows that a player's sufficient statistics, which is independent of the strategy of the other player, consists of the belief over the player's own type, the regret over the other player's type, and the stage. Explicit linear programs, whose size is linear in the size of the game tree, are provided to compute the initial regrets, and the security strategies that only depends on the sufficient statistics. For discounted cases, following the same idea in the finite horizon, this paper shows that a player's sufficient statistics consists of the belief of the player's own type and the antidiscounted regret with respect to the other player's type. Besides, an approximated security strategy depending on the sufficient statistics is provided, and an explicit linear program to compute the approximated security strategy is given. This paper also obtains a bound on the performance difference between the approximated security strategy and the security strategy, and shows that the bound converges to 0 exponentially fast. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
24. The Importance of System-Level Information in Multiagent Systems Design: Cardinality and Covering Problems.
- Author
-
Paccagnan, Dario and Marden, Jason R.
- Subjects
- *
SYSTEMS design , *INFORMATION storage & retrieval systems , *MULTIAGENT systems , *DISTRIBUTED algorithms , *COLLECTIVE behavior , *RESOURCE allocation - Abstract
A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behavior. The information available to the agents, gathered either through communication or sensing, naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information is valuable and can be exploited to design control laws with enhanced performance guarantees. This paper studies the case when such information is uncertain or inaccessible for a class of submodular resource allocation problems termed covering problems. In the first part of this paper, we pinpoint a fundamental risk-reward tradeoff faced by the system operator when conditioning the control design on a valuable but uncertain piece of information, which we refer to as the cardinality, that represents the maximum number of agents that can simultaneously select any given resource. Building on this analysis, we propose a distributed algorithm that allows agents to learn the cardinality while adjusting their behavior over time. This algorithm is proved to perform on par or better to the optimal design obtained when the exact cardinality is known a priori. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
25. Recurrent Neural Network Model: A New Strategy to Solve Fuzzy Matrix Games.
- Author
-
Mansoori, Amin, Eshaghnezhad, Mohammad, and Effati, Sohrab
- Subjects
- *
RECURRENT neural networks , *ARTIFICIAL neural networks , *LYAPUNOV stability , *GAMES - Abstract
This paper aims to investigate the fuzzy constrained matrix game (MG) problems using the concepts of recurrent neural networks (RNNs). To the best of our knowledge, this paper is the first in attempting to find a solution for fuzzy game problems using RNN models. For this purpose, a fuzzy game problem is reformulated into a weighting problem. Then, the Karush–Kuhn–Tucker (KKT) optimality conditions are provided for the weighting problem. The KKT conditions are used to propose the RNN model. Moreover, the Lyapunov stability and the global convergence of the RNN model are also confirmed. Finally, three illustrative examples are presented to demonstrate the effectiveness of this approach. The obtained results are compared with the results obtained by the previous approaches for solving fuzzy constrained MG. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
26. Nonzero-sum games using actor-critic neural networks: A dynamic event-triggered adaptive dynamic programming.
- Author
-
Shen, Hao, Li, Ziwei, Wang, Jing, and Cao, Jinde
- Subjects
- *
DYNAMIC programming , *NASH equilibrium , *LYAPUNOV functions , *NONLINEAR systems , *GAMES - Abstract
This paper mainly investigates the nonzero-sum games of nonlinear systems with unmatched uncertainty by using actor-critic neural networks. To handle the unmatched components, an auxiliary system with a modified value function is constructed, which transforms the robust stabilization issue into the optimal control issue. Then, a novel dynamic event-triggering condition is designed to further save bandwidth via introducing a dynamic variable. In addition, the actor-critic algorithm is employed in adaptive dynamic programming to achieve Nash equilibrium, which is tuned together with the control policy. By constructing appropriate Lyapunov functions, a criterion is established to ensure that the considered system is uniformly ultimately bounded. Finally, the effectiveness of the developed strategy is demonstrated by an example. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
27. Evolutionary dynamics of [formula omitted]-person snowdrift game with two thresholds in well-mixed and structured populations.
- Author
-
Pi, Jinxiu, Wang, Chun, Zhou, Die, Tang, Wei, and Yang, Guanghui
- Subjects
- *
MARKOV processes , *GAMES - Abstract
In this paper, to state the necessary and the critical number of cooperators for completing the snow shoveling, we investigate the evolutionary dynamics of an N -person snowdrift game with two thresholds in well-mixed populations and structured populations. Firstly, we discuss the effects of these thresholds on equilibria in infinite well-mixed populations by applying the replicator equation, and observe that there exist three types of equilibria with the variations of parameters. Secondly, we study the game in finite well-mixed populations by means of the Markov process, and find that the evolutionary results converge to those in infinite population as the finite population size increases. Finally, we explore such a game in structured populations by using the pair approximation approach, and derive the dynamical equation under weak selection, which is ignored in the previous work. Results present that structured populations can create more complicated behaviors of the cooperative dynamics, and to some extent facilitate cooperation compared with well-mixed populations. Our work helpfully provides a theoretical approximation for the N -person snowdrift game in more complicated scenarios. • Some concise critical conditions of equilibria are obtained in infinite and well-mixed populations. • The relationship between equilibria in finite and infinite well-mixed populations is discussed. • The dynamical equation of the double threshold game in structured populations is derived. • Structure populations to some extent facilitate cooperation compared with well-mixed populations. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
28. Dynamics and convergence of hyper-networked evolutionary games with time delay in strategies☆.
- Author
-
Zhang, Jing, Lou, Jungang, Qiu, Jianlong, and Lu, Jianquan
- Subjects
- *
NASH equilibrium , *GAME theory , *GAMES , *COMMON good , *EVOLUTIONARY theories - Abstract
Networked evolutionary game theory is an important tool to study the emergence and maintenance of cooperation in natural, social, and economical systems. In this paper, we investigate the dynamics and convergence of a generalized networked evolutionary game, i.e., delayed hyper-networked evolutionary game (HNEG), which considers the multi-players in fundamental network game and time delay in strategies simultaneously. Based on the tool of semi-tensor product (STP) of matrices, the definition of delayed potential HNEG and representation of potential function are given. Moreover, we conclude the steps to analyze the dynamics and convergence of delayed potential HNEGs. Considering the efficiency in updating process, we define a new strategy updating rule based on the myopic best response adjustment rule (MBRAR), which is called delayed group-based sequential MBRAR. Furthermore, we prove that delayed potential HNEG converges to one of the pure Nash equilibrium trajectories under this rule. Finally, public good game is provided to illustrate the realistic application of our results. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
29. An adaptive replacement of the rule update triggers the cooperative evolution in the Hawk–Dove game.
- Author
-
Sakiyama, Tomoko and Arizono, Ikuo
- Subjects
- *
POPULATION , *GAME theory , *GAMES , *BIOLOGICAL evolution , *RULES - Abstract
Highlights • In this paper, we developed a novel spatial HD model replacing the best takes over update rule with different one. • We investigated the effect of modifying update rules on the problem of cooperators extinction in the space HD games. • We found that our model generated characteristic population patterns and represented the survival of cooperators compared with the classical spatial HD model in which the updated rule was fixed. Abstract Since Maynard Smith and Price proposed the earliest version of Hawk–Dove (HD) game, it attracted researchers' attention as one of models of conflict for two players in game theory. In conflict game, the players' benefit depends on the strategy of opponent for each other. In the classical spatial HD games, if one player adopts defector strategy, it tends to get high payoffs, and therefore increases population of the same strategy, which resulting in an extinction of cooperators. Several studies tried to solve the problem of an extinction of cooperator in spatial HD game. In this paper, we developed a novel spatial HD model replacing the best takes over update rule with different one, and investigated the effect of modifying update rules on the problem of collaborators extinction in space HD games. We found that our model generated characteristic population patterns and represented the survival of cooperators compared with the classical spatial HD model in which the updated rule was fixed. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
30. Design and Analysis of State-Feedback Optimal Strategies for the Differential Game of Active Defense.
- Author
-
Garcia, Eloy, Casbeer, David W., and Pachter, Meir
- Subjects
- *
MATHEMATICAL optimization , *MILITARY airplanes , *HAMILTON'S equations , *ATTACK planes , *NAVIGATION - Abstract
This paper is concerned with a scenario of active target defense modeled as a zero-sum differential game. The differential game theory as developed by Isaacs provides the correct framework for the analysis of pursuit-evasion conflicts and the design of optimal strategies for the players involved in the game. This paper considers an Attacker missile pursuing a Target aircraft protected by a Defender missile which aims at intercepting the Attacker before the latter reaches the Target aircraft. A differential game is formulated where the two opposing players/teams try to minimize/maximize the distance between the Target and the Attacker at the time of interception of the Attacker by the Defender and such time indicates the termination of the game. The Attacker aims to minimize the terminal distance between itself and the Target at the moment of its interception by the Defender. The opposing player/team consists of two cooperating agents: The Target and the Defender. These two agents cooperate in order to accomplish the two objectives: Guarantee interception of the Attacker by the Defender and maximize the terminal Target-Attacker separation. In this paper, we provide a complete, closed form solution of the active target defense differential game; we synthesize closed-loop state feedback optimal strategies for the agents and obtain the Value function of the game. We characterize the Target's escape set and show that the Value function is continuous and continuously differentiable over the Target's escape set, and that it satisfies the Hamilton–Jacobi–Isaacs equation everywhere in this set. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
31. Hierarchical Decision and Control for Continuous Multitarget Problem: Policy Evaluation With Action Delay.
- Author
-
Zhu, Jiangcheng, Zhu, Jun, Wang, Zhepei, Guo, Shan, and Xu, Chao
- Subjects
- *
ANALYTIC hierarchy process , *REINFORCEMENT learning , *MOBILE robots - Abstract
This paper proposes a hierarchical decision-making and control algorithm for the shepherd game, the seventh mission in the International Aerial Robotics Competition (IARC). In this game, the agent (a multirotor aerial robot) is required to contact targets (ground vehicles) sequentially and drive them to a certain boundary to earn score. During the game of 10 min, the agent should be fully autonomous without any human interference. Regarding the lower-level controller and dynamics of the agent, each action takes a duration of time to accomplish. Denoted as an action delay, in this paper, this action duration is nonconstant and is related to the final reward. Therefore, the challenging point is making the agent “aware of time” when applying a certain action. We solve this problem by two approaches: deep Q-networks and lookup table. The action delay predictor in the decision-level is fitted by a lower-level controller. Through simulations by the example of the shepherd game, the effectiveness and efficiency of this approach are validated. This paper helps our team winning the first prize in IARC 2017, and keeps the best record of this mission since it was released in 2013. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
32. Distributed Inertial Best-Response Dynamics.
- Author
-
Swenson, Brian, Eksin, Ceyhun, Kar, Soummya, and Ribeiro, Alejandro
- Subjects
- *
NASH equilibrium , *DISTRIBUTED algorithms , *COMPUTER simulation , *SYSTEMS engineering , *HEURISTIC algorithms - Abstract
The note considers the problem of computing pure Nash equilibrium (NE) strategies in distributed (i.e., network-based) settings. The paper studies a class of inertial best-response dynamics based on the fictitious play (FP) algorithm. It is shown that inertial best-response dynamics are robust to informational limitations common in distributed settings. Fully distributed variants of FP with inertia and joint strategy FP (JSFP) with inertia are developed and convergence is proven to the set of pure NE. The distributed algorithms developed in the paper rely on consensus methods. Results are validated using numerical simulations. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
33. Linear criterion for testing the extremity of an exact game based on its finest min-representation.
- Author
-
Studený, Milan and Kratochvíl, Václav
- Subjects
- *
CRITERION (Theory of knowledge) , *LINEAR equations , *GAMES , *KNOWLEDGE representation (Information theory) , *INFORMATION theory - Abstract
A game-theoretical concept of an exact (cooperative) game corresponds to the notion of a discrete coherent lower probability, used in the context of imprecise probabilities. The collection of (suitably standardized) exact games forms a pointed polyhedral cone and the paper is devoted to the recognition of extreme rays of that cone, whose generators are called extreme exact games . We give a necessary and sufficient condition for an exact game to be extreme. Our criterion leads to solving a simple linear equation system determined by a certain min-representation of the game. It has been implemented on a computer and a web-based platform for testing the extremity of an exact game is available, which works with a modest number of variables. The paper also deals with different min-representations of a fixed exact game μ , which can be compared with the help of the concept of a tightness structure (of a min-representation) introduced in the paper. The collection of tightness structures (of min-representations of μ ) is shown to be a finite lattice with respect to a refinement relation. We give a method to obtain a min-representation with the finest tightness structure, which construction comes from the coarsest standard min-representation of μ given by the (complete) list of vertices of the core (polytope) of μ . The newly introduced criterion for exact extremity is based on the finest tightness structure. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
34. Changing behaviour under unfairness: An evolutionary model of the Ultimatum Game.
- Author
-
Arioli, Gianni, Lucchetti, Roberto, and Valente, Giovanni
- Subjects
- *
EVOLUTIONARY models , *GAMES , *DEMOGRAPHIC change - Abstract
Experimental results on the Ultimatum Game indicate that receivers may reject non-zero offers, even though that seems irrational. The explanation is that, when players are treated unfairly, they can act against strict rationality. This paper discusses an evolutionary model of the Ultimatum Game describing how populations of players change their behaviour in time. We prove an analytical result that establishes under what conditions receivers tend to reject unfair offers. The response to unfair offers is also shown to be sensitive to different degrees of unfairness. We then introduce a Bayesian game to translate our result from populations to individual players. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
35. Sampled-data state feedback control design for evolutionary threshold public goods games on coupled networks.
- Author
-
Li, Ling, Fu, Shihua, Wang, Jianjun, Feng, Jun-e, and Zhao, Jianli
- Subjects
- *
STATE feedback (Feedback control systems) , *PUBLIC goods , *GROUP decision making , *MULTIPLE criteria decision making , *GAMES - Abstract
This paper investigates the design problem of the sampled-data state feedback control (SDSFC) for evolutionary threshold public goods games (PGGs) with two enhancement factors on coupled networks. Firstly, using the semi-tensor product (STP) of matrices, an algebraic form for the dynamics of the controlled coupled PGGs is established. Secondly, based on the algebraic expression, the conditions to make the accumulated contribution of all players in each game reach its own threshold under SDSFCs are provided, and the SDSFCs are derived. Finally, an illustrative example is given to show the effectiveness of the obtained results. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
36. Model-free optimal tracking policies for Markov jump systems by solving non-zero-sum games.
- Author
-
Zhou, Peixin, Xue, Huiwen, Wen, Jiwei, Shi, Peng, and Luan, Xaoli
- Subjects
- *
MARKOVIAN jump linear systems , *ECONOMIC models , *NASH equilibrium , *GAMES - Abstract
This paper develops model-free optimal tracking policies for Markov jump systems by solving non-zero-sum games (NZSGs). First, coupled action and mode-dependent value functions (CAMDVFs) are built for solving a two-player NZSG and getting Nash equilibrium solutions. Second, we propose a value iteration (VI) algorithm to parallelly update policies under each mode by collecting data on different operation modes within each iterative window. Moreover, the iterative increasing convergence of the CAMDVFs is proved by introducing auxiliary functions between two adjacent iterations. It is worth pointing out that an influence function is introduced to remove abnormal data to improve the learning capability of the VI algorithm effectively. Finally, the tracking policies' validity, self-adaptability and application potential are verified by a numerical example and a generalized economic model. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
37. Two-level games on the trans-boundary river Indus: obstacles to cooperation.
- Author
-
Rigi, Hanifeh and Warner, Jeroen F.
- Subjects
- *
WATERSHEDS , *COOPERATION , *GAMES , *RIVERS - Abstract
This synthesis paper explores the reasons hindering water cooperation between India and Pakistan on the Indus River Basin. It argues that both domestic and international-level elements narrow the size of the 'win-sets' which make water cooperation between the two states highly challenging. Not only state actors but also the domestic actors in both India and Pakistan have repeatedly played 'water games'. Further, due to long-standing geopolitical and territorial conflicts between India and Pakistan, the strategies pursued so far by these states including 'securitization', 'issue-linkage' and 'alliance strategies' as leverage mechanisms, have also contributed to the lack of cooperation in their water realm. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
38. Special Issue on Deep Reinforcement Learning and Adaptive Dynamic Programming.
- Author
-
Zhao, Dongbin, Liu, Derong, Lewis, F. L., Principe, Jose C., and Squartini, Stefano
- Subjects
- *
REINFORCEMENT learning , *ARTIFICIAL neural networks - Abstract
In the first issue of Nature 2015, Google DeepMind published a paper “Human-level control through deep reinforcement learning.” Furthermore, in the first issue of Nature 2016, it published a cover paper “Mastering the game of Go with deep neural networks and tree search” and proposed the computer Go program, AlphaGo. In March 2016, AlphaGo beat the world’s top Go player Lee Sedol by 4:1. This becomes a new milestone in artificial intelligence history, the core of which is the algorithm of deep reinforcement learning (RL). [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
39. Single Sample Fictitious Play.
- Author
-
Swenson, Brian, Kar, Soummya, and Xavier, Joao
- Subjects
- *
MULTIAGENT systems , *LARGE scale systems , *NASH equilibrium , *MONTE Carlo method , *GAMES - Abstract
This paper is concerned with distributed learning and optimization in large-scale settings. The well-known fictitious play (FP) algorithm has been shown to achieve Nash equilibrium learning in certain classes of multiagent games. However, FP can be computationally difficult to implement when the number of players is large. Sampled FP (SFP) is a variant of FP that mitigates the computational difficulties arising in FP by using a Monte Carlo (i.e., sampling based) approach. Despite its computational advantages, a shortcoming of SFP is that the number of samples that must be drawn at each iteration grows without bound as the algorithm progresses. In this paper, we propose single sample FP (SSFP)—A variant of SFP in which only one sample needs to be drawn in each round of the algorithm. Convergence of SSFP to the set of Nash equilibria is proven. Simulation results show the performance of SSFP is comparable to that of SFP, despite drawing far fewer samples. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
40. Distributed Nash Equilibrium Seeking by a Consensus Based Approach.
- Author
-
Ye, Maojiao and Hu, Guoqiang
- Subjects
- *
NASH equilibrium , *NONCOOPERATIVE games (Mathematics) , *LYAPUNOV stability , *HEURISTIC algorithms , *STOCHASTIC convergence - Abstract
In this paper, Nash equilibrium seeking among a network of players is considered. Different from many existing works on Nash equilibrium seeking in noncooperative games, the players considered in this paper cannot directly observe the actions of the players who are not their neighbors. Instead, the players are supposed to be capable of communicating with each other via an undirected and connected communication graph. By a synthesis of a leader-following consensus protocol and the gradient play, a distributed Nash equilibrium seeking strategy is proposed for the noncooperative games. Analytical analysis on the convergence of the players’ actions to the Nash equilibrium is conducted via Lyapunov stability analysis. For games with nonquadratic payoffs, where multiple isolated Nash equilibria may coexist in the game, a local convergence result is derived under certain conditions. Then, a stronger condition is provided to derive a nonlocal convergence result for the nonquadratic games. For quadratic games, it is shown that the proposed seeking strategy enables the players’ actions to converge to the Nash equilibrium globally under the given conditions. Numerical examples are provided to verify the effectiveness of the proposed seeking strategy. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
41. Berge equilibrium in linear-quadratic mean-field-type games.
- Author
-
Toumi, Noureddine, Barreiro-Gomez, Julian, Duncan, Tyrone E., and Tembine, Hamidou
- Subjects
- *
EQUILIBRIUM , *CONDITIONAL expectations , *GAMES , *MEAN field theory , *PROBLEM solving , *QUADRATIC equations - Abstract
In this paper, we study Berge equilibria in linear-quadratic mean-field-type game problems under a jump-diffusion-regime switching state dynamics that incorporate mean-field terms in both the states and cost functional. In the cost functional, we consider conditional variance of the states and control actions, conditional mean of states and control actions, and conditional covariance terms. The underlying Berge problem is solved in a semi-explicit way by using the direct method and an illustrative numerical example is presented. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
42. Efficient Strategy Computation in Zero-Sum Asymmetric Information Repeated Games.
- Author
-
Li, Lichun and Shamma, Jeff S.
- Subjects
- *
INFORMATION asymmetry , *SYSTEM administrators , *GAMES , *INFORMATION modeling - Abstract
Zero-sum asymmetric information games model decision-making scenarios involving two competing players who have different information about the game being played. A particular case is that of nested information, where one (informed) player has superior information over the other (uninformed) player. This paper considers the case of nested information in repeated zero-sum games and studies the computation of strategies for both the informed and uninformed players for finite-horizon and discounted infinite-horizon nested information games. For finite-horizon settings, we exploit that for both players, the security strategy, and also the opponent's corresponding best response, depend only on the informed player's history of actions. Using this property, we formulate an linear program (LP) computation of player strategies that is linear in the size of the uninformed player's action set. For the infinite-horizon discounted game, we construct LP formulations to compute the approximated security strategies for both players, and show that the worst-case performance difference between the approximated security strategies and the security strategies converges to zero exponentially. Finally, we illustrate the results on a network interdiction game between an informed system administrator and an uniformed intruder. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
43. A pursuit–evasion game between two identical differential drive robots.
- Author
-
Bravo, Luis, Ruiz, Ubaldo, and Murrieta-Cid, Rafael
- Subjects
- *
SIMULATION games , *STATISTICAL decision making , *TELEVISION game programs , *GAMES , *MOTION - Abstract
This paper addresses a pursuit-evasion problem between two identical Differential Drive Robots (DDRs). The pursuer wants to capture the evader in minimal time, while the evader wants to delay capture as much as possible. The game takes place in a Euclidean plane without obstacles. In this work, the motion primitives and time-optimal motion strategies for both players are presented. Based on the initial positions of the players, it is possible to solve the decision problem of determining the winner of the game. Simulations of the pursuit-evasion game showing the time-optimal motion primitives of the players are provided for both cases, when the pursuer wins and when the evader escapes. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
44. Optimal Secure Control With Linear Temporal Logic Constraints.
- Author
-
Niu, Luyao and Clark, Andrew
- Subjects
- *
LINEAR dynamical systems , *OPTIMAL control theory , *LOGIC , *STOCHASTIC control theory , *CYBER physical systems , *DISCRETE-time systems , *ECOLOGICAL disturbances - Abstract
Prior work on automatic control synthesis for cyber-physical systems under logical constraints has primarily focused on environmental disturbances or modeling uncertainties, however, the impact of deliberate and malicious attacks has been less studied. In this paper, we consider a discrete-time dynamical system with a linear temporal logic (LTL) constraint in the presence of an adversary, which is modeled as a stochastic game. We assume that the adversary observes the control policy before choosing an attack strategy. We investigate two problems. In the first problem, we synthesize a robust control policy for the stochastic game that maximizes the probability of satisfying the LTL constraint. A value iteration based algorithm is proposed to compute the optimal control policy. In the second problem, we focus on a subclass of LTL constraints, which consist of an arbitrary LTL formula and an invariant constraint. We then investigate the problem of computing a control policy that minimizes the expected number of invariant constraint violations while maximizing the probability of satisfying the arbitrary LTL constraint. We characterize the optimality condition for the desired control policy. A policy iteration based algorithm is proposed to compute the control policy. We illustrate the proposed approaches using two numerical case studies. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
45. Graphical Nash Equilibria and Replicator Dynamics on Complex Networks.
- Author
-
Tan, Shaolin and Wang, Yaonan
- Subjects
- *
NASH equilibrium , *MULTIAGENT systems , *NETWORK effect , *MEASUREMENT of runoff - Abstract
Pairwise-interaction graphical games have been widely used in the study and design of strategic interaction in multiagent systems. With regard to this issue, one entitative problem is actually to understand how the interaction structure of agents affects the strategy configuration of Nash equilibria. This paper intends to study the effect of interaction networks on Nash equilibria in pairwise-interaction graphical games. We first show that interaction networks may induce new strategy equilibria in pairwise-interaction graphical games and then provide graphical conditions for the existence of these network-induced equilibria. Furthermore, to determine Nash equilibria of pairwise-interaction graphical games, a graphical replicator dynamics model is formulated, and its connection with graphical games is established. In detail, it is shown that every Nash equilibrium of the graphical games corresponds to a fixed point of the graphical replicator dynamics and that every asymptotically stable fixed point of the graphical replicator dynamics corresponds to a strict pure Nash equilibrium of the graphical games. The obtained results are applied in understanding coordination in complex networks and determination of structural conflicts in signed graphs. This work may provide new insights into understanding and designing strategy equilibria and dynamics in games on networks. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
46. Robust Optimal Filtering Over Lossy Networks.
- Author
-
Feng, Yu, Nie, Xuanhe, and Chen, Xiang
- Subjects
- *
DATA packeting , *RANDOM noise theory , *NASH equilibrium , *RICCATI equation , *ALGEBRAIC equations , *WHITE noise - Abstract
This paper addresses the robust optimal filtering design over unreliable networks, where the data packet dropouts occur during the signal transmission from the sensor side to the filter. The designed filter is expected, under communication data loss, to provide a guaranteed robustness against disturbance/model uncertainty while achieving the minimized variance of the estimation error under Gaussian white noises and the worst case of the disturbance. The Nash game approach is adopted to deal with such a multiobjective filtering problem. Based on the concept of the mean-square stability, Nash equilibrium strategies are analytically applied in terms of two cross-coupled modified algebraic Riccati equations. The presented design method provides a systematic way to achieve a tradeoff of the estimation performance in the $\mathcal {H}_2$ and $\mathcal {H}_\infty$ senses in the presence of data loss. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
47. Solutions for Multiagent Pursuit-Evasion Games on Communication Graphs: Finite-Time Capture and Asymptotic Behaviors.
- Author
-
Lopez, Victor G., Lewis, Frank L., Wan, Yan, Sanchez, Edgar N., and Fan, Lingling
- Subjects
- *
NONCOOPERATIVE games (Mathematics) , *NASH equilibrium , *GAMES , *MULTIAGENT systems , *DIFFERENTIAL games - Abstract
In this paper, the multiagent pursuit-evasion (MPE) games are solved in order to obtain optimal strategic policies for all players. In these games, multiple pursuers attempt to intercept multiple evaders who try to avoid capture. A graph-theoretic approach is employed to study the interactions of the agents with limited sensing capabilities, such that distributed control policies are obtained for every agent. Furthermore, the minimization of performance indices associated with the goals of the agents is guaranteed. Nash equilibrium among the players is obtained by means of optimal policies that use the solutions of the Hamilton–Jacobi–Isaacs (HJI) equations of the game. Minmax strategies are also proposed to guarantee a security-level performance when the solutions of the HJI equations for Nash equilibrium do not exist. Scenarios for finite-time capture and for asymptotic rendezvous are analyzed, and emergent behaviors are obtained by means of modifications of the proposed general-case performance indices. The containment control results are shown to be special cases of the solutions of the MPE games. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
48. Distributed GNE Seeking Under Partial-Decision Information Over Networks via a Doubly-Augmented Operator Splitting Approach.
- Author
-
Pavel, Lacra
- Subjects
- *
INFORMATION networks , *MONOTONE operators , *NASH equilibrium , *ALGORITHMS , *UNDIRECTED graphs , *PEER-to-peer architecture (Computer networks) - Abstract
We consider distributed computation of generalized Nash equilibrium (GNE) over networks, in games with shared coupling constraints. Existing methods require that each player has full access to opponents’ decisions. In this paper, we assume that players have only partial-decision information, and can communicate with their neighbors over an arbitrary undirected graph. We recast the problem as that of finding a zero of a sum of monotone operators through primal-dual analysis. To distribute the problem, we doubly augment variables, so that each player has local decision estimates and local copies of Lagrangian multipliers. We introduce a single-layer algorithm, fully distributed with respect to both primal and dual variables. We show its convergence to a variational GNE with fixed step sizes, by reformulating it as a forward–backward iteration for a pair of doubly-augmented monotone operators. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
49. Linear Quadratic Mean Field Games: Asymptotic Solvability and Relation to the Fixed Point Approach.
- Author
-
Huang, Minyi and Zhou, Mengjie
- Subjects
- *
QUADRATIC fields , *MEAN field theory , *ORDINARY differential equations , *QUADRATIC equations , *UNIQUENESS (Mathematics) , *GAMES - Abstract
Mean field game theory has been developed largely following two routes. One of them, called the direct approach, starts by solving a large-scale game and next derives a set of limiting equations as the population size tends to infinity. The second route is to apply mean field approximations and formalize a fixed point problem by analyzing the best response of a representative player. This paper addresses the connection and difference of the two approaches in a linear quadratic (LQ) setting. We first introduce an asymptotic solvability notion for the direct approach, which means for all sufficiently large population sizes, the corresponding game has a set of feedback Nash strategies in addition to a mild regularity requirement. We provide a necessary and sufficient condition for asymptotic solvability and show that in this case the solution converges to a mean field limit. This is accomplished by developing a re-scaling method to derive a low-dimensional ordinary differential equation (ODE) system, where a non-symmetric Riccati ODE has a central role. We next compare with the fixed point approach which determines a two-point boundary value (TPBV) problem, and show that asymptotic solvability implies feasibility of the fixed point approach, but the converse is not true. We further address non-uniqueness in the fixed point approach and examine the long time behavior of the non-symmetric Riccati ODE in the asymptotic solvability problem. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
50. On the Existence of the Stabilizing Solution of a Class of Periodic Stochastic Riccati Equations.
- Author
-
Aberkane, Samir and Dragan, Vasile
- Subjects
- *
RICCATI equation , *DIFFERENCE equations , *DISCRETE-time systems , *DYNAMICAL systems , *CLASS differences - Abstract
This paper is devoted to the characterization of existence and uniqueness conditions for the stabilizing solution of a large class of Riccati equations arising in stochastic dynamic games. As an application of the obtained results, we consider in a second step the problem of a zero-sum two players linear quadratic difference game for a stochastic discrete-time dynamical system subject to both random switching of its coefficients and multiplicative noise. We show that in the solution of such a control problem, a crucial role is played by the stabilizing solution of the considered class of Riccati difference equations. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.