纯策略纳什均衡的博弈强化学习

将博弈理论与多智能体强化学习结合形成博弈强化学习逐渐受到关注，但是也存在算法的计算复杂度高和无法保证纯策略纳什均衡的问题。Meta equilibrium Q-learning算法通过反应函数将原始博弈转换为元博弈，而元博弈推导出的元均衡是纯策略纳什均衡。该算法在保证纯策略纳什均衡的前提下能够使得每个智能体的回报不低于某特定阈值。同时，基于分形的均衡程度评估模型能够通过计算任意状态的分形维数来判断其稳态，并评估任意状态与均衡状态之间的距离，该模型可以检验元均衡的科学性与合理性，上述算法和模型的相关结论在福利博弈和夺控战中都得到具体验证。     

竞争环境下任务分配方法的研究

以博弈论和纳什均衡理论为基础,介绍了一种基于博弈论的竞争环境下的任务分配方法,提出了竞争环境下任务的分配模型框架,引入了Agent能力的概念,并给出了竞争环境下详细的任务竞争算法和资源竞买算法,最后通过实例获得了满意的结果,同时该实例也表明了本模型的合理性和算法的有效性.     

利用退火回归神经网络极值搜索算法求纳什均衡解

针对如何解算n人非合作的动态博弈对策中的纳什均衡解问题,提出一种利用退火回归神经网络极值搜索算法解算纳什均衡解的方法．在动态博弈对策问题中,将每个竞争者视为一个代价函数,利用此算法可以使每个代价函数均收敛于其最小值,从而获得此对策的纳什均衡解．此算法不限制代价函数的具体形式,同时由于摒弃了正弦激励信号,解决了一般极值搜索算法中存在的输出量“颤动”现象和控制量来回切换问题,改善了系统的动态性能．     

基于纳什竞价的空间众包任务定价算法

任务定价是众包平台解决利润驱动的任务分配、最大化利润的重要步骤。然而关于工人期望的任务定价研究相对较少，现有大多数研究并不考虑工人与任务的动态需求。此外，出于工人隐私和传感器限制，获取完整的工人信息是困难的。为解决上述难题，提出了基于纳什竞价的空间众包任务定价算法。首先通过机器学习算法获取任务的价格范围，然后在价格区间上进行纳什竞价。为了解决动态供需造成的价格大幅波动问题，设计调整机制来稳定任务均价。最后为模拟纳什均衡点，采用了两种不同的梯度递减函数，来搜索匹配数最大的任务定价。分别在gMission数据集和合成数据集进行了实验，结果表明所提算法的匹配数量和任务均价分别是MCMF算法的60%和1.57倍，时间花费是MCMF算法的9.6%,验证了所提算法的有效性。     

面向智能工厂原料供应环节的多机器人任务分配方法

智能工厂下的动态定制生产带来了原料供应的动态变化，需要更加灵活的供应解决方案，在此，我们考虑任务需求和运行距离等因素，建立一个以最大化供应问题收益为目标的智能工厂供应任务优化模型，将原料供应转化为一个多机器人任务分配问题的变体，提出一种多机器人协作的原料供应解决方案，基于贪婪选择策略，产生满足当前各任务要求的供应机器人划分；运用博弈论的纳什平衡概念为任务划分寻求平衡解，进一步提升分配质量.实验表明，所提出算法能够面对不同规模的供应任务，在保证分配质量的同时在极短的时间内给出供应分配方案.     

资源获胜率保证的网格任务调度算法

为保证多资源竞争下单个资源的获胜率,建立一个资源富裕型的网格计算环境模型,基于此模型提出了一个基于博弈论的资源竞争获胜率保证算法（GVP）。GVP算法通过对已知信息分析,预测对手在下一次博弈中的行动,并在此基础上确定自己的行动,使资源累计的获胜率维持在一个可接受的范围。通过实验比较了使用不同竞争策略资源的获胜率。对实验结果进行了深入分析,讨论了两资源博弈的纳什均衡解。     

非光滑聚合博弈纳什均衡的分布式连续时间算法

本文研究多智能体聚合博弈的分布式算法设计.其中,个体的成本函数具有非光滑性.提出一个连续时间分布式算法,使得每个个体仅利用本地数据及局部的信息交互就能达到纳什均衡.利用李雅普诺夫方法,证明了算法的收敛性.在此基础上,进一步研究了带有耦合不等式约束博弈的广义纳什均衡求解.仿真结果验证了方法的有效性.     

一种改进的多agent分布式联盟形成算法

仅采用任务性价比作为多智能体任务分配过程中的任务选择标准,会产生时间消耗大、资源利用低等问题.为此,综合任务性价比和智能体资源的特点,提出了多任务准备度的概念.根据多智能体任务分配过程的收敛性和时效性,采用Learning Automata算法动态调整任务准备度各项的权重;进而利用该方法模拟解决了低、中、高3种任务需求下多智能体任务分配问题.仿真实验结果验证了所提出方法的有效性,资源冗余可至少减少20%.     

无线传感器网络中基于协作的包转发研究

运用博弈论的观点和方法来解决传感器网络中的包转发问题．为传感器网络建立了包转发模型，分析了节点参与包转发会话所获得的帕累托最优效用．提出了基于帕累托最优效用的包转发算法POUPF，并证明了该算法能够建立纳什均衡以保证每个节点都获得帕累托最优效用．仿真结果表明：POUPF能够有效促进节点自发合作，确保了每个节点获得帕累托最优效用；任何偏离POUPF节点的包转发行为都会导致所有节点效用的下降．     

基于博弈论的自组网数据链资源调度分析

随着无线自组网技术的发展,必须解决在该网络结构下的动态资源分配问题。本文引入经济学博弈理论中的纳什议价解函数,证明了基于启发式的自组网数据链资源的调度算法存在纳什均衡,且分配结果与支付函数成比例公平。该结论为设计自组网数据链终端间的资源竞争和调度策略,实现资源的按需动态分配提供了理论依据。     

WLAN中非合作博弈的信道分配研究

为解决基于802.11无线局域网中固定信道结构导致的因客户需求不均衡而产生的信道频谱分配不公平和系统效用率低的问题,提出了基于认知无线电技术的可变带宽信道分配方法,建立了无线局域网中频谱分配的非合作博弈模型.在该多接入点无线网络博弈模型中,重点考虑非重叠频谱的单碰撞域方案,在证明存在公平的且是系统最优的纯纳什均衡的基础上,给出单阶段的公平的信道分配算法.仿真实验结果表明,该分配方案无论在信道使用公平性还是系统效用上都优于固定信道和非纳什均衡的分配方式.     

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

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

基于对策论的团队计算机生成角色任务分配方法

针对带有时间约束的、可以动态加入到环境中的复杂任务,建立了一种基于对策论的任务分配模型,并给出了一种任务分配方法。该方法中计算机生成角色(CGA)根据自身掌握的局部信息进行行为选择,并使用虚拟行动方法确保CGA快速学习到一个严格纯策略Nash平衡。仿真实验结果表明该方法是合理的,能够有效地解决动态任务的分配问题。     

基于博弈论的多服务器多用户视频分析任务卸载算法

在过去的近10年中,人工智能相关的服务和应用大规模出现,它们要求高算力、高带宽和低时延.边缘计算目前被认为是这些应用最适合的计算模式,尤其是视频分析相关应用.研究多服务器多用户异构视频分析任务卸载问题,其中用户选择合适的边缘服务器,并将他们的原始视频数据上传至服务器进行视频分析.为了有效处理众多用户对有限网络资源的竞争和共享,并且能够获得稳定的网络资源分配局面,即每个用户不会单方面地改变自己的任务卸载决策,该多服务器多用户异构视频分析任务卸载问题被建模为一个多玩家的博弈问题.基于最小化整体时延的优化目标,先后研究非分布式视频分析场景和分布式视频分析场景两种情形,分别提出基于博弈论的潜在最优服务器选择算法和视频单元分配算法.通过严格的数学证明,两种情形下提出的算法均可以达到纳什均衡,同时保证较低的整体时延.最后,基于真实数据集的大量实验表明,所提方法比其他现有算法降低了平均26.3%的整体时延.     

一种基于理性Agent的任务求解联盟形成策略

联盟形成是多 agent 系统中的一个关键问题, 主要着眼于如何在联盟内 agent 间划分联盟的效用. 但已有策略无法摆脱搭便车问题, 尤其是额外效用的分配没有确切反映出各 agent 对于联盟贡献的差异性, 导致联盟潜在的不稳定. 本文给出了一种新的联盟形成的行为策略, 在公平分配原则和无妒忌原则的基础上, 提高了对额外效用分配的合理性, 在具有超加性的面向任务的领域中可以形成全局最优联盟, 并具有 Nash 均衡意义下的稳定性.     

A Nash equilibrium solution in an oligopoly market: The search for Nash equilibrium solutions with replicator equations derived from the gradient dynamics of a simplex algorithm

The present analysis applies continuous time replicator dynamics to the analysis of oligopoly markets. In the present paper, we discuss continuous game problems in which decision-making variables for each player are bounded on a simplex by equalities and non-negative constraints. Several types of problems are considered under conditions of normalized constraints and non-negative constraints. These problems can be classified into two types based on their constraints. For one type, the simplex constraint applies to the variables for each player independently, such as in a product allocation problem. For the other type, the simplex constraint applies to interference among all players, creating a market share problem. In the present paper, we consider a game problem under the constraints of allocation of product and market share simultaneously. We assume that a Nash equilibrium solution can be applied and derive the gradient system dynamics that attain the Nash equilibrium solution without violating the simplex constraints. Models assume that three or more firms exist in a market. Firms behave to maximize their profits, as defined by the difference between their sales and cost functions with conjectural variations. The effectiveness of the derived dynamics is demonstrated using simple data. The present approach facilitates understanding the process of attaining equilibrium in an oligopoly market.     

The robustness of a Nash equilibrium simulation model: Game-theoretic approach using variable metric projection method

This paper proposes a Nash equilibrium model that applies continuous time replicator dynamics to the analysis of oligopoly markets. The robustness of the proposed simple Nash equilibrium model under the simultaneous constraints of allocation of product and market share using a simulation method to derive an optimal solution for production decisions by rival firms in oligopoly markets is tested by changing profit and cost function parameters, as well as the initial production values and market shares of the firms examined in this study. The effects of differences in conjectural variation and initial allocation of market share on the convergent values are considered, particularly in the case of corner solutions. This approach facilitates the understanding of the robustness of attaining equilibrium in an oligopoly market.     

一种优化的任务分配方法研究

在计算机领域中,由于数据量和待处理任务的复杂度迅速增加,多台计算机共同协作完成任务已是未来发展的趋势,而合理的任务分配方法是高效地执行任务的前提。目前,借助多Agent系统去研究任务分配的方法是目前研究的一个热点。本文基于多Agent系统提出一种基于执行代价和传输代价的任务分配的优化方法,建立相应的任务分配模型,推导出评价任务分配优化效果的目标函数,并通过实例说明了该分配机制对多Agent系统处理问题性能的影响。结果表明,该种优化方法能有效地分析多Agent系统处理问题时的性能。     

Existence and uniqueness of the Nash equilibrium in the non-cooperative QoS routing

Researchers dealing with game theoretic issues are well aware that the definition of a model capturing some physical behaviours such as the routing, the pricing, the flow and congestion control, the admission control just to mention some examples in the telecommunication field, is a difficult task, but it is only half of the overall effort. As a matter of fact, a key aspect is the analysis of the equilibrium (or equilibria) towards which the game will (hopefully) converge. The existence, the uniqueness, the efficiency and the structure of the equilibrium are some of the typical properties which are investigated. In this article, we propose a game theoretic model for quality of service (QoS) routing in networks implementing a Differentiated Service model for the QoS support. In particular, we focus on a parallel link network model and we consider a non-cooperative joint problem of QoS routing and dynamic capacity allocation. For this model, we demonstrate that the Nash equilibrium exists, so overcoming a typical problem in the existence proofs appeared in many papers in the area of routing game since 1990s, and we explicitly obtain a suitable set of relations characterising its structure. Moreover, we prove that Nash equilibrium uniqueness cannot be guaranteed in general.     

一类拥塞问题研究综述

说明了E1 Farol酒吧拥塞问题是多种实际拥塞问题的一个简化模型，这类问题的关键是如何协调各参与者的行为，综述了从Nash均衡、学习算法和预测规则等不同角度研究此类拥塞问题的主要进展，指出了存在的问题和进一步的研究方向．