Endogenous Movement and Equilibrium Selection in Spatial Coordination Games

We study the effects of agent movement on equilibrium selection in network based spatial coordination games with Pareto dominant and risk dominant Nash equilibria. Our primary interest is in understanding how endogenous partner selection on networks influences equilibrium selection in games with multiple equilibria. We use agent based models and best response behaviors of agents to study our questions of interest. In general, we find that allowing agents to move and choose new game play partners greatly increases the probability of attaining the Pareto dominant Nash equilibrium in coordination games. We also find that agent diversity increases the ability of agents to attain larger payoffs on average.     

Multi-agent graphical games with input constraints: an online learning solution

This paper studies an online iterative algorithm for solving discrete-time multi-agent dynamic graphical games with input constraints. In order to obtain the optimal strategy of each agent, it is necessary to solve a set of coupled Hamilton-Jacobi-Bellman (HJB) equations. It is very difficult to solve HJB equations by the traditional method. The relevant game problem will become more complex if the control input of each agent in the dynamic graphical game is constrained. In this paper, an online iterative algorithm is proposed to find the online solution to dynamic graphical game without the need for drift dynamics of agents. Actually, this algorithm is to find the optimal solution of Bellman equations online. This solution employs a distributed policy iteration process, using only the local information available to each agent. It can be proved that under certain conditions, when each agent updates its own strategy simultaneously, the whole multi-agent system will reach Nash equilibrium. In the process of algorithm implementation, for each agent, two layers of neural networks are used to fit the value function and control strategy, respectively. Finally, a simulation example is given to show the effectiveness of our method.     

Graphical Congestion Games

We consider congestion games with linear latency functions in which each player is aware only of a subset of all the other players. This is modeled by means of a social knowledge graph G in which nodes represent players and there is an edge from i to j if i knows j. Under the assumption that the payoff of each player is affected only by the strategies of the adjacent ones, we first give a complete characterization of the games possessing pure Nash equilibria. Namely, if the social graph G is undirected, the game is an exact potential game and thus isomorphic to a classical congestion game. As a consequence, it always converges and possesses Nash equilibria. On the other hand, if G is directed an equilibrium is not guaranteed to exist, but the game is always convergent and an equilibrium can be found in polynomial time if G is acyclic, even if finding the best equilibrium remains an intractable problem.     

Properties of Nash solutions of a two-stage nonzero-sum game

This paper contains exact expressions for the complete class of uncountably many globally optimal affine Nasb equilibrium strategies for a two-stage two-person nonzero-sum game problem with quadratic objective functionals and with dynamic information for beth players. Existence conditions for each of these Nash equilibrium solutions are derived and it is shown that a recursive Nash solution is not necessarily globally optimal. Cost-uniqueness property of the derived Nash strategies is investigated and it is proven that the game problem under consideration admits a unique Nash cost pair if and only if it can be made equivalent to either a team problem or a zero-sum game. It is also shown that existence conditions of a globally optimal Nash solution will be independent of the parameters characterizing the nonuniques of the Nash strategies only if the game problem can be made equivalent to a team problem.     

Matrix games with missing,interval, and ambiguous lottery payoffs of pure strategy profiles and compound strategy profiles

In a matrix game, the interactions among players are based on the assumption that each player has accurate information about the payoffs of their interactions and the other players are rationally self‐interested. As a result, the players should definitely take Nash equilibrium strategies. However, in real‐life, when choosing their optimal strategies, sometimes the players have to face missing, imprecise (i.e., interval), ambiguous lottery payoffs of pure strategy profiles and even compound strategy profile, which means that it is hard to determine a Nash equilibrium. To address this issue, in this paper we introduce a new solution concept, called ambiguous Nash equilibrium, which extends the concept of Nash equilibrium to the one that can handle these types of ambiguous payoff. Moreover, we will reveal some properties of matrix games of this kind. In particular, we show that a Nash equilibrium is a special case of ambiguous Nash equilibrium if the players have accurate information of each player's payoff sets. Finally, we give an example to illustrate how our approach deals with real‐life game theory problems.     

INFLUENCE OF ENVIRONMENTAL CHANGES ON COOPERATIVE BEHAVIOR IN THE PRISONER'S DILEMMA GAME ON AN ARTIFICIAL SOCIAL MODEL

In this paper, by simulations on an artificial social model, we analyze cooperative behavior of agents playing the prisoner's dilemma game, in which each of the agents has the two strategies: cooperate and defect. Because defect yields a better payoff whichever strategy an opponent chooses, it is rational for an agent to choose defect in a single game or a finite number of games. However, it is known that a pair of cooperates can also be a Nash equilibrium pair if the players do not know when the game is over or the game is infinitely repeated. To investigate such cooperative behavior, we employ an artificial social model called the Sugarscape and carry out simulations on the model. Arranging three kinds of environments in the Sugarscape, we examine cooperative behavior of agents who are essentially selfish, in a sense that they maximize their payoffs, and investigate influence of environmental changes on the cooperative behavior.     

A Pure Nash Equilibrium-Based Game Theoretical Method for Data Replication across Multiple Servers

This paper proposes a non-cooperative game based technique to replicate data objects across a distributed system of multiple servers in order to reduce user perceived Web access delays. In the proposed technique computational agents represent servers and compete with each other to optimize the performance of their servers. The optimality of a non-cooperative game is typically described by Nash equilibrium, which is based on spontaneous and non-deterministic strategies. However, Nash equilibrium may or may not guarantee system-wide performance. Furthermore, there can be multiple Nash equilibria, making it difficult to decide which one is the best. In contrast, the proposed technique uses the notion of pure Nash equilibrium, which if achieved, guarantees stable optimal performance. In the proposed technique, agents use deterministic strategies that work in conjunction with their self-interested nature but ensure system-wide performance enhancement. In general, the existence of a pure Nash equilibrium is hard to achieve, but we prove the existence of such equilibrium in the proposed technique. The proposed technique is also experimentally compared against some well-known conventional replica allocation methods, such as branch and bound, greedy, and genetic algorithms.     

Solution of multiobjective optimization problems: coevolutionary algorithm based on evolutionary game theory

When attempting to solve multiobjective optimization problems (MOPs) using evolutionary algorithms, the Pareto genetic algorithm (GA) has now become a standard of sorts. After its introduction, this approach was further developed and led to many applications. All of these approaches are based on Pareto ranking and use the fitness sharing function to keep diversity. On the other hand, the scheme for solving MOPs presented by Nash introduced the notion of Nash equilibrium and aimed at solving MOPs that originated from evolutionary game theory and economics. Since the concept of Nash Equilibrium was introduced, game theorists have attempted to formalize aspects of the evolutionary equilibrium. Nash genetic algorithm (Nash GA) is the idea to bring together genetic algorithms and Nash strategy. The aim of this algorithm is to find the Nash equilibrium through the genetic process. Another central achievement of evolutionary game theory is the introduction of a method by which agents can play optimal strategies in the absence of rationality. Through the process of Darwinian selection, a population of agents can evolve to an evolutionary stable strategy (ESS). In this article, we find the ESS as a solution of MOPs using a coevolutionary algorithm based on evolutionary game theory. By applying newly designed coevolutionary algorithms to several MOPs, we can confirm that evolutionary game theory can be embodied by the coevolutionary algorithm and this coevolutionary algorithm can find optimal equilibrium points as solutions for an MOP. We also show the optimization performance of the co-evolutionary algorithm based on evolutionary game theory by applying this model to several MOPs and comparing the solutions with those of previous evolutionary optimization models. This work was presented, in part, at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24#x2013;26, 2003.     

Convergence analysis for pure stationary strategies in repeated potential games: Nash,Lyapunov and correlated equilibria

In game theory the interaction among players obligates each player to develop a belief about the possible strategies of the other players, to choose a best-reply given those beliefs, and to look for an adjustment of the best-reply and the beliefs using a learning mechanism until they reach an equilibrium point. Usually, the behavior of an individual cost-function, when such best-reply strategies are applied, turns out to be non-monotonic and concluding that such strategies lead to some equilibrium point is a non-trivial task. Even in repeated games the convergence to a stationary equilibrium is not always guaranteed. The best-reply strategies analyzed in this paper represent the most frequent type of behavior applied in practice in problems of bounded rationality of agents considered within the Artificial Intelligence research area. They are naturally related with the, so-called, fixed-local-optimal actions or, in other words, with one step-ahead optimization algorithms widely used in the modern Intelligent Systems theory.This paper shows that for an ergodic class of finite controllable Markov games the best-reply strategies lead necessarily to a Lyapunov/Nash equilibrium point. One of the most interesting properties of this approach is that an expedient (or absolutely expedient) behavior of an ergodic system (repeated game) can be represented by a Lyapunov-like function non-decreasing in time. We present a method for constructing a Lyapunov-like function: the Lyapunov-like function replaces the recursive mechanism with the elements of the ergodic system that model how players are likely to behave in one-shot games. To show our statement, we first propose a non-converging state-value function that fluctuates (increases and decreases) between states of the Markov game. Then, we prove that it is possible to represent that function in a recursive format using a one-step-ahead fixed-local-optimal strategy. As a result, we prove that a Lyapunov-like function can be built using the previous recursive expression for the Markov game, i.e., the resulting Lyapunov-like function is a monotonic function which can only decrease (or remain the same) over time, whatever the initial distribution of probabilities. As a result, a new concept called Lyapunov games is suggested for a class of repeated games. Lyapunov games allow to conclude during the game whether the applied strategy provides the convergence to an equilibrium point (or not). The time for constructing a Potential (Lyapunov-like) function is exponential. Our algorithm tractably computes the Nash, Lyapunov and the correlated equilibria: a Lyapunov equilibrium is a Nash equilibrium, as well it is also a correlated equilibrium. Validity of the proposed method is successfully demonstrated both theoretically and practically by a simulated experiment related to the Duel game.     

基于博弈论的隐私保护分布式数据挖掘

隐私保护的分布式数据挖掘问题是数据挖掘领域的一个研究热点,而基于经济视角,利用博弈论的方法对隐私保护分布式数据挖掘进行研究只是处于初始阶段。基于收益最大化,研究了完全信息静态博弈下分布式数据挖掘中参与者(两方或多方)的策略决策问题,得出了如下结论:数据挖掘在满足一定的条件下,参与者(两方或多方)的准诚信攻击策略是一个帕累托最优的纳什均衡策略;在准诚信攻击的假设下,参与者(多方)的非共谋策略并不是一个纳什均衡策略。同时给出了该博弈的混合战略纳什均衡,它对隐私保护分布式数据挖掘中参与者的决策具有一定的理论和指导意义。     

Concurrent imitation dynamics in congestion games

Imitating successful behavior is a natural and frequently applied approach when facing complex decision problems. In this paper, we design protocols for distributed latency minimization in atomic congestion games based on imitation. We propose to study concurrent dynamics that emerge when each agent samples another agent and possibly imitates this agent’s strategy if the anticipated latency gain is sufficiently large. Our focus is on convergence properties. We show convergence in a monotonic fashion to stable states, in which none of the agents can improve their latency by imitating others. As our main result, we show rapid convergence to approximate equilibria, in which only a small fraction of agents sustains a latency significantly above or below average. Imitation dynamics behave like an FPTAS, and the convergence time depends only logarithmically on the number of agents. Imitation processes cannot discover unused strategies, and strategies may become extinct with non-zero probability. For singleton games we show that the probability of this event occurring is negligible. Additionally, we prove that the social cost of a stable state reached by our dynamics is not much worse than an optimal state in singleton games with linear latency functions. We concentrate on the case of symmetric network congestion games, but our results do not use the network structure and continue to hold accordingly for general symmetric games. They even apply to asymmetric games when agents sample within the set of agents with the same strategy space. Finally, we discuss how the protocol can be extended such that, in the long run, dynamics converge to a pure Nash equilibrium.     

Multi-agent discrete-time graphical games and reinforcement learning solutions

This paper introduces a new class of multi-agent discrete-time dynamic games, known in the literature as dynamic graphical games. For that reason a local performance index is defined for each agent that depends only on the local information available to each agent. Nash equilibrium policies and best-response policies are given in terms of the solutions to the discrete-time coupled Hamilton–Jacobi equations. Since in these games the interactions between the agents are prescribed by a communication graph structure we have to introduce a new notion of Nash equilibrium. It is proved that this notion holds if all agents are in Nash equilibrium and the graph is strongly connected. A novel reinforcement learning value iteration algorithm is given to solve the dynamic graphical games in an online manner along with its proof of convergence. The policies of the agents form a Nash equilibrium when all the agents in the neighborhood update their policies, and a best response outcome when the agents in the neighborhood are kept constant. The paper brings together discrete Hamiltonian mechanics, distributed multi-agent control, optimal control theory, and game theory to formulate and solve these multi-agent dynamic graphical games. A simulation example shows the effectiveness of the proposed approach in a leader-synchronization case along with optimality guarantees.     

基于Agent的电子市场结伴购买算法

以电子商务市场中买方Agent的结伴购买为背景，研究了自利主体的动态结盟问题。基于博弈论，考虑协商花费为常数情况，若所有Agent都采用“底线”策略，存在唯一的纳什平衡解。最后给出了计算底线值的方法及算法。     

Effective short-term opponent exploitation in simplified poker

Uncertainty in poker stems from two key sources, the shuffled deck and an adversary whose strategy is unknown. One approach to playing poker is to find a pessimistic game-theoretic solution (i.e., a Nash equilibrium), but human players have idiosyncratic weaknesses that can be exploited if some model or counter-strategy can be learned by observing their play. However, games against humans last for at most a few hundred hands, so learning must be very fast to be useful. We explore two approaches to opponent modelling in the context of Kuhn poker, a small game for which game-theoretic solutions are known. Parameter estimation and expert algorithms are both studied. Experiments demonstrate that, even in this small game, convergence to maximally exploitive solutions in a small number of hands is impractical, but that good (e.g., better than Nash) performance can be achieved in as few as 50 hands. Finally, we show that amongst a set of strategies with equal game-theoretic value, in particular the set of Nash equilibrium strategies, some are preferable because they speed learning of the opponent’s strategy by exploring it more effectively. Electronic Supplementary Material  The online version of this article () contains supplementary material, which is available to authorized users.     

非合作博弈均衡在确定性Ad hoc网络中的应用

首先介绍了非合作博弈均衡(纳什均衡),并将纳什均衡的基本原理应用到Ad hoc网络中节点间的数据传输中,对采用纳什均衡的几种常用的策略也做了介绍,并着重对其中的TFT策略进行了讨论.并用"Small World"这一概念替代传统的"最短路径"概念,同时对Small-World做了介绍.随后针对Ad hoc网络的某些拓扑结构,将"纳什均衡"策略和目前其他一些激励机制进行了比较和讨论.认为在目前的Ad hoc网络中,非合作博弈均衡(纳什均衡)是比较理想,比较简单的一种分组传输策略.     

ε-Equilibrium in LQ differential games with bounded uncertain disturbances: robustness of standard strategies and new strategies with adaptation

A finite time multi-persons linear-quadratic differential game (LQDG) with bounded disturbances and uncertainties is considered. When players cannot measure these disturbances and uncertainties, the standard feedback Nash strategies are shown to yield to an ε-(or quasi) Nash equilibrium depending on an uncertainty upper bound that confirms the robustness property of such standard strategies. In the case of periodic disturbances, another concept, namely adaptive concept, is suggested. It is defined an “adaptation period” where all participants apply the standard feedback Nash strategies with the, so-called, “shifting signal” generated only by a known external exciting signal. Then, during the adaptation, the readjustment (or correction) of the control strategies is realized to estimate the effect of unknown periodic disturbances by the corresponding correction of the shifting vector. After that adaptation period, the complete standard strategies including the recalculated shifting signal are activated allowing the achievement of pure (ε?=?0) Nash equilibrium for the rest of the game. A numerical example dealing with a two participants game shows that the cost functional for each player achieves better values when the adaptive approach is applied.     

Distributed projection subgradient algorithm for two-network zero-sum game with random sleep scheme

In this paper, a zero-sum game Nash equilibrium computation problem with a common constraint set is investigated under two time-varying multi-agent subnetworks, where the two subnetworks have opposite payoff function. A novel distributed projection subgradient algorithm with random sleep scheme is developed to reduce the calculation amount of agents in the process of computing Nash equilibrium. In our algorithm, each agent is determined by an independent identically distributed Bernoulli decision to compute the subgradient and perform the projection operation or to keep the previous consensus estimate, it effectively reduces the amount of computation and calculation time. Moreover, the traditional assumption of stepsize adopted in the existing methods is removed, and the stepsizes in our algorithm are randomized diminishing. Besides, we prove that all agents converge to Nash equilibrium with probability 1 by our algorithm. Finally, a simulation example verifies the validity of our algorithm.     

基于纳什均衡的智能合约缺陷检测

本文研究区块链智能合约的缺陷检测问题,即检测合约中是否存在部分合约方无论选择什么动作,均无法避免损失的状态.将智能合约问题转换成合约状态迁移图上的博弈策略选择问题,提出了基于纳什均衡理论的合约缺陷自动检测方法,以及为了提高检测效率,提出了针对合约状态变迁图和博弈策略形式的一系列化简方法.最后,实现了一个智能合约建模、分...     

基于纳什均衡迁移学习的碳-能复合流自律优化

提出了一种全新的纳什均衡迁移学习算法,并应用于求解大规模电力系统分散式碳–能复合流自律优化.首次引入碳排放责任分摊机制,避免了碳排放责任的重复计算.将大规模电网分解成若干小型区域电网,每个小型区域电网被定义为一个智能体,通过纳什博弈实现分散式自律优化.智能体利用记忆矩阵对寻优知识进行存储,并通过多个个体与环境的反复交互实现记忆更新;采用状态–动作链对记忆矩阵进行降维,有效避免了"维数灾难".此外,基于相似度的迁移学习可以对历史任务知识进行高效提炼,提高了新任务寻优效率.IEEE 57和300节点系统仿真表明:所提算法非常适合求解大规模电网的碳–能复合流自律优化,在保证纳什均衡解质量的同时,明显加快寻优速度.     

多组对策系统非劣Nash策略的最优均衡解算法

多组对策系统中求解组与组之间的非劣Nash策略至关重要.如何针对一般问题解析求出非劣Nash策略还没有有效的方法.本文阐述了一种利用组与组之间的非劣反应集构造求解非劣Nash策略的迭代算法.为此首先引进多组对策系统组内部合作对策的最优均衡值和最优均衡解的概念,然后通过证明最优均衡解是组内部隐含某一权重向量的合作对策的非劣解,得到求解合作对策的单目标规划问题.进一步说明在组内部该问题的解不仅是非劣解而且对所有局中人都优于不合作时的Nash平衡策略.最后给出了验证该算法有效性的一个实际例子.