Characterizing the Nash equilibria of a three-player Bayesian quantum game

Quantum games with incomplete information can be studied within a Bayesian framework. We consider a version of prisoner’s dilemma (PD) in this framework with three players and characterize the Nash equilibria. A variation of the standard PD game is set up with two types of the second prisoner and the first prisoner plays with them with probability p and \(1-p\), respectively. The Bayesian nature of the game manifests in the uncertainty that the first prisoner faces about his opponent’s type which is encoded either in a classical probability or in the amplitudes of a wave function. Here, we consider scenarios with asymmetric payoffs between the first and second prisoner for different values of the probability, p, and the entanglement. Our results indicate a class of Nash equilibria (NE) with rich structures, characterized by a phase relationship on the strategies of the players. The rich structure can be exploited by the referee to set up rules of the game to push the players toward a specific class of NE. These results provide a deeper insight into the quantum advantages of Bayesian games over their classical counterpart.     

Modular strategies for recursive game graphs

Many problems in formal verification and program analysis can be formalized as computing winning strategies for two-player games on graphs. In this paper, we focus on solving games in recursive game graphs which can model the control flow in sequential programs with recursive procedure calls. While such games can be viewed as the pushdown games studied in the literature, the natural notion of winning in our framework requires the strategies to be modular with only local memory; that is, resolution of choices within a module does not depend on the context in which the module is invoked, but only on the history within the current invocation of the module. While reachability in (global) pushdown games is known to be EXPTIME-complete, we show reachability in modular games to be NP-complete. We present a fixed-point computation algorithm for solving modular games such that in the worst case the number of iterations is exponential in the total number of returned values from the modules. If the strategy within a module does not depend on the global history, but can remember the history of the past invocations of this module, that is, if memory is local but persistent, we show that reachability becomes undecidable.     

Open-loop Stackelberg strategies in a linear-quadratic differential game with time delay

The open-loop Stackelberg strategies in a linear-quadratic differential game with time delay are constructed in the form of necessary and sufficient conditions. The evolution of a game with time delay is described by coupled differential equations composed of lumped and distributed parameter subsystems. Calculation of solutions is facilitated by transforming two-point boundary-value problems to terminal boundary-value ones by the introduction of Riccati-type differential equations.     

知识驱动的游戏攻略自动标注算法

为了帮助用户快速检索感兴趣的游戏攻略,提出了知识驱动的游戏攻略自动标注算法。首先,对每款游戏的多个资讯网站进行融合,自动构建游戏领域知识库;然后,再通过游戏领域词汇发现算法和决策树分类模型,抽取游戏攻略中的游戏术语;由于游戏术语在攻略中大多以简称的形式存在,故最后将攻略中游戏术语和知识库进行链接得到该术语所对应的全称即语义标签对攻略进行标注。在多款游戏上的实验结果表明,所提出的游戏攻略标注方法的准确率高达90%。同时,游戏领域词汇发现算法与其他术语抽取方法n-gram语言模型相比取得了更好的效果。     

Evolution of iterated prisoner's dilemma game strategies in structured demes under random pairing in game playing

We discuss the evolution of strategies in a spatial iterated prisoner's dilemma (IPD) game in which each player is located in a cell of a two-dimensional grid-world. Following the concept of structured demes, two neighborhood structures are used. One is for the interaction among players through the IPD game. A player in each cell plays against its neighbors defined by this neighborhood structure. The other is for mating strategies by genetic operations. A new strategy for a player is generated by genetic operations from a pair of parent strings, which are selected from its neighboring cells defined by the second neighborhood structure. After examining the effect of the two neighborhood structures on the evolution of cooperative behavior with standard pairing in game-playing, we introduce a random pairing scheme in which each player plays against a different randomly chosen neighbor at every round (i.e., every iteration) of the game. Through computer simulations, we demonstrate that small neighborhood structures facilitate the evolution of cooperative behavior under random pairing in game-playing.     

一种基于博弈策略的群智能属性约简算法

建立了粒子群算法与博弈论之间的联系,在此基础上,引入一种基于博弈策略的群智能搜索机制,并应用于粗糙集最小属性约简问题的求解。由此构建的属性约简算法,可以设置不同的参与团体及其博弈策略,构建相应的支付效用矩阵,并能通过博弈过程构建策略的最优组合。多个UCI数据集的实验计算表明提出的基于博弈策略的新算法求解质量优于粒子群优化算法、禁忌搜索、遗传变异和变异粒子群优化算法,并具有较小的计算开销。     

Classical rules and quantum strategies in penny flip game

We study the quantum single penny flip game under various classical rules of the game. For every rule of the game, there exist unitary transformations which ensure the winning for quantum player. With the aim to understand the role of entangling gate for a sequential zero sum game, we extend the single penny problem to two penny problem. While entangling gates are found to be not useful, local gates are necessary and sufficient to win the game. Further, importance of one qubit operations is indicated. Various rules of two penny game is also indicated.     

Closed-loop strategies in continuous dynamic game with multi-level of hierarchy

The derivation is given of the closed-loop Stackelberg strategy for a class of continuous three-player non-zero-sum differential games using the idea of the team optimal Stackelberg strategy. The game systems are described by linear state dynamics and quadratic objective functions. First, a definition of the three-player hierarchical equilibrium is given, then a general theorem which was developed by Basar (1981) is examined and applied to the game under consideration to deduce some sufficient conditions for the solution of the game to exist. A simple example is given.     

Invariance and polynomial design of strategies in the linear-quadratic game

A new algorithm to solve the H ^∞ control problem in the case of full information was presented. It combines the spectral and matrix methods. The polynomial Lur’e-Riccati operator was introduced. Parametrization of all solutions of the controlled plant equation by hidden variables was presented within the framework of the J.C. Willems behavioral approach. The kernel of the polynomial Lur’e-Riccati operator was decomposed into the direct sum of subspaces that are similar to the Jordan blocks. The saddle point of the linear-quadratic game which was found by V.A. Yakubovich in 1970 was shown to provide solution to the H ^∞ control problem for a considerable class of controlled plants.     

Evasion from a group of inertial objects

Sufficient conditions of evasion from a rendezvous in a game with equal opportunities of participants are obtained. The motion law of each participant is described by third-order equations. A single evader and a group of pursuers take part.     

基于微分博弈的双渠道广告合作协调策略研究

研究在制造商开通网上和零售渠道的情形下, 供应链成员的广告合作和成本分担对双渠道协调的影响. 研究结果表明, 无论零售商的广告对品牌形象产生何种影响, 制造商分担零售商的部分广告费用均能使得双方的利润优于分散决策的情形, 但不能完全实现双渠道协调. 此外, 当零售商也分担制造商的部分广告费用时, 双方均可以实现完全的协调. 相比于零售商频繁促销产生负面影响的情形, 在不产生负面影响的情况下, 双方能够实现更多的价值.

     

A multi-agent collaborative maintenance platform applying game theory negotiation strategies

Engineering asset management (EAM) is a broad discipline with distributed functions and services. When engineering assets are capital intensive, management requires specialized expertise for diagnosis, prognosis, maintenance and repairs. The current practice of EAM relies on self maintained experiential rules with coordinated collaboration and outsourcing for maintenance and repairs. In order to enhance the life long asset value and efficiency (from the stakeholder’s viewpoint) and after sales service quality (from the asset provider’s viewpoint), this research proposes a collaborative maintenance platform that integrates real time data collection with diagnostic and prognostic expertise. The collaborative system combines and delivers services among asset operation sites (the maintenance demanders), the service center (the intermediary coordinator), the system providers, the first tier maintenance collaborators, and the second and lower tier parts suppliers. Multi-agent system technology is used to integrate different systems and databases. Agents with autonomy and authority work to assist service providers and coordinate communications, negotiations, and maintenance decision support. Finally, game theory is used to design the decision models for strategic, tactical, and operational decision making during collaborative maintenance practices.     

On-the-fly generation of multi-robot team formation strategies based on game conditions

This paper describes a new model to automatically generating dynamic formation strategies for robotic soccer applications based on game conditions, regarded to as favorable or unfavorable for a robotic team. Decisions are distributedly computed by the players of a multi-agent team. A game policy is defined and applied by a human coach who establishes the attitude of the team for defending or attacking. A simple neural net model is applied using current and previous game experience to classify the game’s parameters so that the new game conditions can be determined so that a robotic team can modify its strategy on-the-fly. Experiments and results of the proposed model for a robotic soccer team show the promise of the approach.     

Model predictive and non-cooperative dynamic game fault recovery control strategies for a network of unmanned underwater vehicles

In this paper, the problem of control and fault recovery for a team of autonomous underwater vehicles in the presence of loss of effectiveness (LOE) actuator faults is addressed. Towards this end, two different fault recovery control strategies based on the model predictive control technique as well as the dynamic game theory are proposed and developed. Given the allowable information that can be exchanged among the agents, both centralised and semi-decentralised recovery control schemes are considered and their associated corresponding fault recovery strategies are developed. The proposed active fault recovery control strategies incorporate both the online inaccurate as well as delayed actuator fault estimates to reconfigure the nominal (healthy state) controllers. The effectiveness of the proposed semi-decentralised fault recovery control schemes is quantitatively investigated through extensive simulation case studies considering various LOE actuator fault severities in one or more unmanned vehicles as well as fault detection and isolation module imperfections such as fault estimation error and time delays in detecting the faults. The simulation results demonstrate and illustrate that our proposed semi-decentralised recovery control scheme can maintain acceptable degraded tracking and formation keeping performance of both the faulty and healthy agents in the team with lower computational and communication bandwidth requirements as well as lower or fairly close control effort cost as compared to the centralised control recovery scheme.     

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

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