基于多跟随者Stackelberg博弈的流速控制算法

由于现实网络中,端系统的角色往往并不平等,存在某些端系统制定整个网络的流速控制策略,其他端系统只能跟随这些策略,不能简单地使用非合作博弈理论研究Internet中非合作端系统的贪婪行为。该文在讨论了一次博弈模型和流速控制博弈均衡的解析解的基础上,对多跟随者Stackelberg博弈模型的流速与拥塞控制行为进行了深入研究。提出了多跟随者Stackelberg博弈流速控制模型,论证了Stackelberg均衡的存在性,并推导出在Stackelberg均衡点上领导者和多跟随者流速率的解析解。最后,文章设计了一种基于多跟随者Stackelberg博弈的流速控制算法(FCSM),并讨论了FCSM算法执行的过程。     

802.11网络中基于博弈理论的可变带宽信道分配研究

802.11网络中节点的理性和自私性导致可变带宽信道分配的低公平性、低负载均衡性及低社会效率问题.基于非合作博弈理论将可变带宽信道分配问题建模成策略型博弈模型.首先,给出问题的纳什均衡分配策略,证明了纳什均衡点的存在;然后,针对纳什均衡策略社会效率低的问题,提出一种基于支付的激励机制,使可变带宽信道分配过程收敛到占优决策均衡状态,从而系统整体吞吐量性能达到全局最优;并分析了上述两种策略的公平性和负载均衡问题;最后,给出达到纳什均衡和全局最优状态的可变带宽信道分配算法.仿真结果表明,纳什均衡策略能够获得好的公平性,而全局最优策略的负载均衡和社会效率性能要优于纳什均衡策略.     

考虑非线性奖惩机制的多主体主从博弈模型

本文针对以往电价机制仅由供方主导而缺乏电能供需双向调节功能的缺点问题,构建了一个考虑双边非线性奖惩机制的电力市场多主体主从博弈模型,以实现市场多主体的利益均衡.首先,在零售端提出了一种由供需双方共同参与且具有动态奖惩激励的电价机制.其次,在此基础上构建了一个以零售商为领导者、用户为跟随者的主从博弈模型,同时利用演化博弈描述用户的动态选择过程.然后,证明了该主从博弈模型纳什均衡解的存在性,并设计了分布式算法进行求解.最后,通过算例分析证明了本文所提博弈模型的合理性,并验证了电价机制在引导用户合理用电、保证供需平衡以及实现成本节约等方面的有效性;同时仿真结果表明给出的分布式求解算法具有较快的收敛速度和良好的稳定性能.     

MAS动态协作任务求解模型与算法

针对网格环境的自治性、动态性、分布性和异构性等特征.提出基于多智能体系统(mutil agent system, MAS) 博弈协作的资源动态分配和任务调度模型,建立了能够反映供求关系的网格资源调度动态任务求解算法,证明了资源分配博弈中Nash均衡点的存在性、惟一性和Nash均衡解.该方法能够利用消费者Agent的学习和协商能力,引入消费者的心理行为,使消费者的资源申请和任务调度具有较高的合理性和有效性.实验结果表明,该方法在响应时间的平滑性、吞吐率及任务求解效率方面比传统算法要好,从而使得整个资源供需合理、满足用户QoS要求.     

异构无线网络用户网络关联优化:一种基于群体博弈的方法

针对异构无线网络(Heterogeneous Wireless Networks,HWNs)负载平衡问题,提出了一种基于群体博弈的用户网络关联方案.首先将HWNs系统用户网络关联问题抽象成一个群体博弈模型,根据用户在网络中得到的收益函数,证明该群体博弈满足势博弈的条件.利用复制动态作为演化动态工具,证明演化的结果最终会收敛到纳什均衡,这个特性确保了每个用户关联到一个效用最优的网络.然后证明纳什均衡点能最大化整个HWNs系统的吞吐量,保证了纳什均衡的有效性.最后,基于复制动态原理提出了用户网络关联算法.仿真实验模拟了用户网络选择过程,得到了均衡点,验证了理论分析的结果.     

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

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

基于MAS市场机制的动态计算资源调度模型研究

针对动态计算网格资源调度问题,结合多Agent系统(multi agent syste,MAS)协同技术和市场竞价博弈机制,对计算网格资源分配技术进行了深入研究,提出了能够反映供求关系的基于市场经济的网格资源调度模型,该模型一方面能够充分利用消费者Agent的协商能力,另一方面能够充分考虑消费者的行为,使得消费者的资源申请和分配具有较高的合理性和有效性.同时,设计了消费者的效用函数,论证了资源分配博弈中Nash均衡点的存在性和惟一性以及Nash均衡解.基于所提资源调度模型,设计了一种网格资源调度算法.仿真实验表明,资源调度算法能够为消费者的资源数量提供参考,规范消费者竞价,从而使得整个资源的分配趋于合理.     

基于演化博弈论的移动Ad Hoc网络中继协作机制

从演化博弈论的角度,提出一种能有效激励无线Ad Hoc网络节点参与数据分组中继协作的纳什均衡策略:G-TFT(Generous Tit for Tat).以节点中继的分组数与所需的能量开销为均衡点,建立了中继协作过程的单阶段博弈模型G,验证了节点的自私性动机,将G扩展为基于时闻序列、策略可转换的演化博弈R,并根据R的纳什均衡提出了协作激励策略G-TFT.仿真结果表明.通过调整宽容因子g,G-TFT能有效地激励节点参与中继协作.     

一种基于马尔可夫博弈的能量均衡路由算法

针对无线传感器网络中耗能不均问题,引入马尔可夫博弈理论,构建了无线传感器网络的马尔可夫博弈模型.在能量均衡路由分析的基础上,给出了一种基于马尔可夫博弈的能量均衡路由算法,该算法从无线传感器网络整体耗能出发,兼顾节点之间的合作.定义了能量和信誉值的二元收益函数,给出了节点转发的状态转移概率,根据收益函数进行能量调节,求解出能量和收益之间的均衡系数——纳什均衡,实现了节点能量的均衡消耗,延长了网络的生命周期.使用PRISM概率仿真工具进行仿真,验证了该博弈模型存在纳什均衡点,同时表明该模型能促进节点之间合作,最大化无线传感器网络的生命周期.     

一种基于合作博弈的均衡路由方法

网络资源公平性分配是网络可存性研究中的关键问题，路由选择算法是影响网络资源分配的公平性和均衡性的关键因素。本文研究路由器路径选择中的均衡性问题，提出了基于博弈论思想的解决方案，即将IPv6协议中的任意播路由问题看作是合作参与者间的博弈；针对该博弈问题，建立了路由算法的合作博弈模型，求得了该博弈均衡点，并在此基础上，提出了一种基于合作博弈的均衡路由方法；最后通过实验仿真了算法结果。     

Discrete time dynamic multi-leader-follower games with feedback perfect information

Both Stackelberg games and Nash games play extremely important roles in such fields as economics, management, politics and behavioral sciences. Stackelberg game can be modelled as a bilevel optimization problem. Static multi-leader-follower optimization problems are initially proposed by Pang and Fukushima. In this article, a discrete time dynamic version of multi-leader-follower games with feedback information is given and analyzed. There are two major contributions in this article. On one hand, based on the multi-leader-follower games, discrete time dynamic multi-leader-follower games are proposed. On the other hand, dynamic programming algorithms are presented to attack discrete time dynamic multi-leader-follower games with multi-players under feedback information structure for dependent followers.     

Nash equilibria: Complexity,symmetries, and approximation

We survey recent joint work with Christos Papadimitriou and Paul Goldberg on the computational complexity of Nash equilibria. We show that finding a Nash equilibrium in normal form games is computationally intractable, but in an unusual way. It does belong to the class NP; but Nash’s theorem, showing that a Nash equilibrium always exists, makes the possibility that it is also NP-complete rather unlikely. We show instead that the problem is as hard computationally as finding Brouwer fixed points, in a precise technical sense, giving rise to a new complexity class called PPAD. The existence of the Nash equilibrium was established via Brouwer’s fixed-point theorem; hence, we provide a computational converse to Nash’s theorem.To alleviate the negative implications of this result for the predictive power of the Nash equilibrium, it seems natural to study the complexity of approximate equilibria: an efficient approximation scheme would imply that players could in principle come arbitrarily close to a Nash equilibrium given enough time. We review recent work on computing approximate equilibria and conclude by studying how symmetries may affect the structure and approximation of Nash equilibria. Nash showed that every symmetric game has a symmetric equilibrium. We complement this theorem with a rich set of structural results for a broader, and more interesting class of games with symmetries, called anonymous games.     

Existence of solutions in zero-sum differential games

The existence of a weak solution — an active zero-sum equilibrium — is proved for programmed zero-sum differential games with two-point boundary conditions. A constructive existence theorem of a dependent saddle point is established for a special subclass of such games.Translated from Kibernetika, No. 3, pp. 96–99, 104, May–June 1990.     

Existence of perfect equilibria in a class of multigenerational stochastic games of capital accumulation

In this paper we introduce a model of multigenerational stochastic games of capital accumulation where each generation consists of m different players. The main objective is to prove the existence of a perfect stationary equilibrium in an infinite horizon game. A suitable change in the terminology used in this paper provides (in the case of perfect altruism between generations) a new Nash equilibrium theorem for standard stochastic games with uncountable state space.     

Probability and possibility models of matrix games of two subjects

Probability models and their possibility counterparts of one-matrix and bimatrix games of two subjects (A and B) were defined and analyzed. For the one-matrix game possibility model, a theorem was proven saying that maximin and minimax fuzzy strategies exist and that possibilities of A winning or losing (B) in relation to these strategies are equal. The concepts of fuzzy and randomized game strategies were defined and analyzed. The problem of statistic modeling of A and B fuzzy strategies was resolved. For possible models of bimatrix games, the existence of equilibrium points was examined. For the problem of maximization of the winning A and B possibility, it was proven that equilibrium points exist. For the problem of minimizing the possibility of losses, it was shown that if equilibrium points exist, some of them are related to clear strategies, A and B.     

N人合作博弈的Nash及演化均衡稳定策略分析

在有限理性的基础上,对N人合作博弈的对称Nash均衡进行了分析,并引入演化博弈理论分析了参与人的演化均衡稳定策略,得到了不同策略选择下的均衡点。进而应用生物复制动态理论对离散时间及连续时间下的复制动态稳定集进行了研究。最后通过实例说明了该方法在博弈均衡选择上的有效性。     

A Matrix Approach to the Modeling and Analysis of Networked Evolutionary Games With Time Delays

Using the semi-tensor product method, this paper investigates the modeling and analysis of networked evolutionary games (NEGs) with finite memories, and presents a number of new results. Firstly, a kind of algebraic expression is formulated for the networked evolutionary games with finite memories, based on which the behavior of the corresponding evolutionary game is analyzed. Secondly, under a proper assumption, the existence of Nash equilibrium of the given networked evolutionary games is proved and a free-type strategy sequence is designed for the convergence to the Nash equilibrium. Finally, an illustrative example is worked out to support the obtained new results.      

Saddle points and active zero-sum equilibrium in games with multivalued functionals

We consider existence and properties of saddle points of multivalued payoff functions on metric spaces and existence of active zero-sum equilibria which generalize the notion of saddle-point equilibrium. The results are applied to programmed zero-sum differential games.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 70–75, July–August, 1991.     

Constrained multiobjective games in general topological space

In this paper, we introduce and study a new class of constrained multiobjective games in general noncompact topological space. By employing an existence theorem of quasi-equilibrium problems due to this author, several existence theorems of weighted Nash equilibria and Pareto equilibria for the constrained multiobjective games are established in noncompact topological spaces. These theorems improve, unify, and generalize the corresponding results of the multiobjective games in recent literature.