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.     

Consensus in Noncooperative Dynamic Games: A Multiretailer Inventory Application

We focus on Nash equilibria and Pareto optimal Nash equilibria for a finite horizon noncooperative dynamic game with a special structure of the stage cost. We study the existence of these solutions by proving that the game is a potential game. For the single-stage version of the game, we characterize the aforementioned solutions and derive a consensus protocol that makes the players converge to the unique Pareto optimal Nash equilibrium. Such an equilibrium guarantees the interests of the players and is also social optimal in the set of Nash equilibria. For the multistage version of the game, we present an algorithm that converges to Nash equilibria, unfortunately, not necessarily Pareto optimal. The algorithm returns a sequence of joint decisions, each one obtained from the previous one by an unilateral improvement on the part of a single player. We also specialize the game to a multiretailer inventory system.     

Game Optimization of Gas Market Development

A two-person noncooperative game is studied with special payoff functions for which standard existence theorems and algorithms for computing the Nash equilibrium solutions are not applicable. The problem is motivated by the questions related to the determination of the commencement of construction and timing of new gas pipelines.     

有多个不合作随从的诱导策略

本文讨论上级宣布策略后随从进行Nash不合作对策时的诱导问题.由于Nash不合作平衡点的不唯一性,本文提出了拟诱导策略,弱诱导策略和强诱导策略的概念。当随从目标函数是凸函数时,得到了仿射型拟诱导策略和仿射型弱诱导策略的存在条件与设计方法,当随从目标函数是正定二次函数时,得到了仿射型强诱导策略的存在条件与设计方法,并有示例说明本文的结论。     

Convergence Analysis for Symmetric Arbitration Games FOA and DOA

Up to now, results on the existence of Nash equilibrium have required either continuity of payoff functions or compactness of strategy sets. However, in the arbitration games FOA and DOA, neither condition is satisfied. This paper first gives a new existence result for a general game. The result is then applied to the symmetric arbitration games FOA and DOA. The conclusions of this paper generalize the main result of Zeng, Nakamura and Ibaraki (1996), that DOA leads to a convergence of offers but FOA does not.     

Noisy relativistic quantum games in noninertial frames

The influence of noise and of Unruh effect on quantum Prisoners’ dilemma is investigated both for entangled and unentangled initial states. The noise is incorporated through amplitude damping channel. For unentangled initial state, the decoherence compensates for the adverse effect of acceleration of the frame and the effect of acceleration becomes irrelevant provided the game is fully decohered. It is shown that the inertial player always out scores the noninertial player by choosing defection. For maximally entangled initially state, we show that for fully decohered case every strategy profile results in either of the two possible equilibrium outcomes. Two of the four possible strategy profiles become Pareto optimal and Nash equilibrium and no dilemma is leftover. It is shown that other equilibrium points emerge for different region of values of decoherence parameter that are either Pareto optimal or Pareto inefficient in the quantum strategic spaces. It is shown that the Eisert et al. (Phys Rev Lett 83:3077, 1999) miracle move is a special move that leads always to distinguishable results compare to other moves. We show that the dilemma like situation is resolved in favor of one player or the other.     

Analysis of game-theoretic models of an oligopoly market under constrains on the capacity and competitiveness of agents

We develop an oligopoly model for nonlinear cost functions of the agents under constraints on the competitiveness and capacity of the agents and formulate Nash equilibrium conditions for this model. We develop a game-theoretic model for choosing the strategies for competitive and unbounded in capacity agents and define a Pareto optimal solution for this model under complete information.     

On relaxation algorithms in computation of noncooperativeequilibria

This paper considers a special class of numerical algorithms, the so-called relaxation algorithm, for Nash equilibrium points in noncooperative games. The relaxation algorithms have been studied by various authors for the deterministic case. Convergence conditions of this algorithm are based on fixed point theorems. For example, Basar (1987) and Li and Basar (1987) have proved its convergence for a two-player game via the contraction mapping theorem. For the quadratic case these conditions can be easily checked. For other nonlinear payoff functions it is sometimes difficult to check these convergence conditions. In this paper, the authors propose an alternative approach using the residual terms of the Nikaido-Isoda function. The convergence theorem is proved for nonsmooth weakly convex-concave Nikaido-Isoda functions. The family of weakly convex-concave functions is broad enough for applications, since if includes the family of smooth functions. When the payoff functions are twice continuously differentiable, the condition for the residual terms is reduced to strict positiveness of a matrix representing the difference of the Hessians of the Nikaido-Isoda function with respect to the first and second groups of variables. An analogous condition was used by Uryas'ev (1988) to prove convergence of the gradient-type algorithm for the Nash equilibrium problem. In this paper the authors discuss only the deterministic case; nevertheless this approach can be generalized for the stochastic Nash equilibrium problems with uncertainties in parameters     

Equilibrium Trajectories in Dynamical Bimatrix Games with Average Integral Payoff Functionals

This paper considers models of evolutionary non-zero-sum games on the infinite time interval. Methods of differential game theory are used for the analysis of game interactions between two groups of participants. We assume that participants in these groups are controlled by signals for the behavior change. The payoffs of coalitions are defined as average integral functionals on the infinite horizon. We pose the design problem of a dynamical Nash equilibrium for the evolutionary game under consideration. The ideas and approaches of non-zero-sum differential games are employed for the determination of the Nash equilibrium solutions. The results derived in this paper involve the dynamic constructions and methods of evolutionary games. Much attention is focused on the formation of the dynamical Nash equilibrium with players strategies that maximize the corresponding payoff functions and have the guaranteed properties according to the minimax approach. An application of the minimax approach for constructing optimal control strategies generates dynamical Nash equilibrium trajectories yielding better results in comparison to static solutions and evolutionary models with the replicator dynamics. Finally, we make a comparison of the dynamical Nash equilibrium trajectories for evolutionary games with the average integral payoff functionals and the trajectories for evolutionary games with the global terminal payoff functionals on the infinite horizon.     

Learning through reinforcement for N-person repeated constrained games

The design and analysis of an adaptive strategy for N-person averaged constrained stochastic repeated game are addressed. Each player is modeled by a stochastic variable-structure learning automaton. Some constraints are imposed on some functions of the probabilities governing the selection of the player's actions. After each stage, the payoff to each player as well as the constraints are random variables. No information concerning the parameters of the game is a priori available. The "diagonal concavity" conditions are assumed to be fulfilled to guarantee the existence and uniqueness of the Nash equilibrium. The suggested adaptive strategy which uses only the current realizations (outcomes and constraints) of the game is based on the Bush-Mosteller reinforcement scheme in connection with a normalization procedure. The Lagrange multipliers approach with a regularization is used. The asymptotic properties of this algorithm are analyzed. Simulation results illustrate the feasibility and the performance of this adaptive strategy.     

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.     

带Poisson跳的线性二次随机微分博弈及其在鲁棒控制中的应用

研究了一类带Poisson跳扩散过程的线性二次随机微分博弈,包括非零和博弈的Nash均衡策略与零和博弈的鞍点均衡策略问题．利用微分博弈的最大值原理,得到Nash均衡策略的存在条件等价于两个交叉耦合的矩阵Riccati方程存在解,鞍点均衡策略的存在条件等价于一个矩阵Riccati方程存在解的结论,并给出了均衡策略的显式表达及最优性能泛函值．最后,将所得结果应用于现代鲁棒控制中的随机H₂/H_∞控制与随机H_∞控制问题,得到了鲁棒控制策略的存在条件及显式表达,并验证所得结果在金融市场投资组合优化问题中的应用．     

不确定性下非合作博弈强Nash均衡的存在性

在已知不确定参数变化范围的假设下,研究了非合作博弈强Nash均衡的存在性问题.基于经典非合作博弈的强Berge均衡及帕雷托均衡的概念,结合非合作博弈NS均衡,定义了不确定性下非合作博弈的帕雷托强Berge和强Nash均衡的概念,并借助Ky Fan不等式证明其存在性.最后利用算例验证了其可行性和有效性.     

Comparing the notions of optimality in CP-nets,strategic games and soft constraints

The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of three formalisms used for different purposes in reasoning about multi-agent systems: strategic games, CP-nets, and soft constraints. To relate the notions of optimality in these formalisms we introduce a natural qualitative modification of the notion of a strategic game. We show then that the optimal outcomes of a CP-net are exactly the Nash equilibria of such games. This allows us to use the techniques of game theory to search for optimal outcomes of CP-nets and vice-versa, to use techniques developed for CP-nets to search for Nash equilibria of the considered games. Then, we relate the notion of optimality used in the area of soft constraints to that used in a generalization of strategic games, called graphical games. In particular we prove that for a natural class of soft constraints that includes weighted constraints every optimal solution is both a Nash equilibrium and Pareto efficient joint strategy. For a natural mapping in the other direction we show that Pareto efficient joint strategies coincide with the optimal solutions of soft constraints.      

广义Nash平衡点和切换控制在对策论中的应用

通过把平衡点和决策者的动机耦合的方法,提出了广义纳什平衡点这一新概念.决策者的动机通常有两类：一是最大化自己的利益,另一则是最大化对手的利益.如果每一个决策者的动机都是第一类,一个理性的群体就会形成,整个系统最终会达到第一类平衡点（也就是经典的纳什平衡点）.如果每一个决策者的动机都是第二类,一个有智慧的群体就会形成,整个系统最终会达到第二类平衡点.同时,切换控制被用来帮助决策者确定他们的动机.     

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.     

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

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

博弈论框架下P2P实时流的合作模型研究

针对P2P实时流环境中出现的“搭便车”和“公共悲剧”问题,提出一种博弈论框架下的激励合作模型。分析该模型达到Nash均衡和Pareto最优状态下对应的比例公平策略优化。并考虑存在欺骗行为的情况,研究对应的节点行为策略。理论分析表明,该模型能够刺激节点合作,并且对节点的欺骗行为具有抑制作用。     

一种新的多目标优化策略机制及其应用

在博弈问题中很多学习机制只能使Agent收敛到Nash均衡解,不能很好地满足实际需要。将博弈问题转化为多目标优化问题,提出了一种新的多目标优化策略机制——保留受控策略机制,并将其应用到囚徒困境问题中得到比Nash均衡更有意义的Pareto最优解,在自博弈实验中取得了较高的满意度。实验结果表明,该策略机制求解Pareto最优解的有效性。     

On the interaction of multiple overlay routing

In the past few years, overlay networks have received much attention but there has been little study on the “interaction” of multiple, co-existing overlays on top of a physical network. In addition to previously introduced concept of overlay routing strategy such as selfish routing, we introduce a new strategy called “overlay optimal routing”. Under this routing policy, the overlay seeks to minimize its weighted average delay by splitting its traffic onto multiple paths. We establish that (i) the overlay optimal routing can achieve better delay compared to selfish routing and (ii) there exists a Nash equilibrium when multiple overlays adopt this strategy. Although an equilibrium point exists for overlay optimal routing and possibly for selfish routing, we show that the interaction of multiple overlay routing may not be Pareto optimal and that some fairness anomalies of resource allocation may occur. This is worthy of attention since overlay may not know the existence of other overlays and they will continue to operate at this sub-optimal point. We explore two pricing schemes to resolve the above issues. We show that by incorporating a proper pricing scheme, the overlay routing game can be led to the desired equilibrium and avoid the problems mentioned above. Extensive fluid-based simulations are performed to support the theoretical claims.