Uniqueness of equilibria in atomic splittable polymatroid congestion games

We study uniqueness of Nash equilibria in atomic splittable congestion games and derive a uniqueness result based on polymatroid theory: when the strategy space of every player is a bidirectional flow polymatroid, then equilibria are unique. Bidirectional flow polymatroids are introduced as a subclass of polymatroids possessing certain exchange properties. We show that important cases such as base orderable matroids can be recovered as a special case of bidirectional flow polymatroids. On the other hand we show that matroidal set systems are in some sense necessary to guarantee uniqueness of equilibria: for every atomic splittable congestion game with at least three players and non-matroidal set systems per player, there is an isomorphic game having multiple equilibria. Our results leave a gap between base orderable matroids and general matroids for which we do not know whether equilibria are unique.     

On the performance of mildly greedy players in cut games

We continue the study of the performance of mildly greedy players in cut games initiated by Christodoulou et al. (Theoret Comput Sci 438:13–27, 2012), where a mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than \(1+\epsilon \), for some given \(\epsilon \ge 0\). Hence, in presence of mildly greedy players, the classical concepts of pure Nash equilibria and best-responses generalize to those of \((1+\epsilon )\)-approximate pure Nash equilibria and \((1+\epsilon )\)-approximate best-responses, respectively. We first show that the \(\epsilon \)-approximate price of anarchy, that is the price of anarchy of \((1+\epsilon )\)-approximate pure Nash equilibria, is at least \(\frac{1}{2+\epsilon }\) and that this bound is tight for any \(\epsilon \ge 0\). Then, we evaluate the approximation ratio of the solutions achieved after a \((1+\epsilon )\)-approximate one-round walk starting from any initial strategy profile, where a \((1+\epsilon )\)-approximate one-round walk is a sequence of \((1+\epsilon )\)-approximate best-responses, one for each player. We improve the currently known lower bound on this ratio from \(\min \left\{ \frac{1}{4+2\epsilon },\frac{\epsilon }{4+2\epsilon }\right\} \) up to \(\min \left\{ \frac{1}{2+\epsilon },\frac{2\epsilon }{(1+\epsilon )(2+\epsilon )}\right\} \) and show that this is again tight for any \(\epsilon \ge 0\). An interesting and quite surprising consequence of our results is that the worst-case performance guarantee of the very simple solutions generated after a \((1+\epsilon )\)-approximate one-round walk is the same as that of \((1+\epsilon )\)-approximate pure Nash equilibria when \(\epsilon \ge 1\) and of that of subgame perfect equilibria (i.e., Nash equilibria for greedy players with farsighted, rather than myopic, rationality) when \(\epsilon =1\).     

On the Existence of Pure and Mixed Strategy Nash Equilibria in Discontinuous Games

A game is better-reply secure if for every nonequilibrium strategy x^* and every payoff vector limit u^* resulting from strategies approaching x^*, some player i has a strategy yielding a payoff strictly above u_i^* even if the others deviate slightly from x^*. If strategy spaces are compact and convex, payoffs are quasiconcave in the owner's strategy, and the game is better-reply secure, then a pure strategy Nash equilibrium exists. Better-reply security holds in many economic games. It also permits new results on the existence of symmetric and mixed strategy Nash equilibria.     

On the cores of games arising from integer edge covering functions of graphs

In this paper, we study cooperative games arising from integer edge covering problems on graphs. We introduce two games, a rigid k-edge covering game and its relaxed game, as generalizations of a rigid edge covering game and its relaxed game studied by Liu and Fang (2007). Then we give a characterization of the cores of both games, find relationships between them, and give necessary and sufficient conditions for the balancedness of a rigid k-edge covering game and its relaxed game.     

道德约束环境下的Nash实施

探讨了代理人发送信号的成本对社会选择规则可实施性的影响,证明了在存在道德约束的实施环境中,单调性不再是一个社会选择规则可Nash实施的必要条件。当代理人数量大于2时,满足一致性条件的社会选择规则都是可Nash实施的。当代理人数量等于2,满足交叉性条件和一致性条件的社会选择规则是可Nash实施的。结论表明:在实际的实施问题中,社会选择规则可实施的范围可能远远大于预期,在存在道德约束的实施环境中,一些不满足单调性但却满足一致性条件的社会选择规则,如Pareto规则都是可Nash实施的。     

Population monotonicity in matching games

The matching game is a cooperative profit game defined on an edge-weighted graph, where the players are the vertices and the profit of a coalition is the maximum weight of matchings in the subgraph induced by the coalition. A population monotonic allocation scheme is a collection of rules defining how to share the profit among players in each coalition such that every player is better off when the coalition expands. In this paper, we study matching games and provide a necessary and sufficient characterization for the existence of population monotonic allocation schemes. Our characterization implies that whether a matching game admits population monotonic allocation schemes can be determined efficiently.

     

先后次序的施塔贝格竞争均衡与纳什均衡的比较

具有产品差异的两企业,在仅进行一轮的产品定价策略博弈中,先后次序的施塔贝格竞争均衡与纳什均衡的结果是企业双方都具有较高的均衡价格和正的均衡利润.在伯川德-施塔贝格市场竞争均衡下,追随企业具有后发制人的优势,能获得比领先企业更高的利润,并且两企业的利润都高于伯川德-纳什均衡利润.但在多轮博弈的模型中伯川德-施塔贝格均衡点并不稳定,最终会趋向于伯川德-纳什均衡点.     

A Dynamic Reinterpretation of Nash Bargaining With Endogenous Threats

This paper concerns the two‐stage game introduced in Nash (1953). It formalizes a suggestion made (but not pursued) by Nash regarding equilibrium selection in that game, and hence offers an arguably more solid foundation for the “Nash bargaining with endogenous threats” solution. Analogous reasoning is then applied to an infinite horizon game to provide equilibrium selection in two‐person repeated games with contracts. In this setting, issues about enforcement of threats are much less problematic than in Nash's static setting. The analysis can be extended to stochastic games with contracts.     

同类异质产品市场博弈Nash均衡最优策略模型

本文按照Nash均衡解的要求,建立同类异质产品市场用户需求分布及效用结构模型,导出不同定位的企业所实施竞争策略的若干最优条件,通过计算不同策略设计下产品相应的临界功能效用值,参与竞争的企业可找到适合于市场需求的最优决策。     

带预算约束的广告主均衡报价研究——基于纳什均衡角度

从广告主角度出发，研究基于纳什均衡概念的带有预算约束的关键词拍卖问题。首先推导出纳什均衡下各个广告主报价的上界和下界。其次给出广告主报价向上偏离无利可图的充要条件，并进行了数值分析。此外，通过数值实例分析了广告主报价向下偏离时对其收益的影响。利用各个广告主报价的上下界和预算刻画了带有预算约束的纳什均衡。最后，利用广告主报价在纳什均衡下的上界给出报价向量是带预算约束的纳什均衡的充要条件。对于广告主制定预算策略具有参考作用。     

Nash 讨价还价公平参考下的供应链优化决策

基于 Nash 讨价还价博弈思想建立公平参考框架,构建公平关切效用体系,以此为基础对报童模型展开行为研究,探讨零售商的公平关切行为倾向对供应链的影响． 通过数值分析说明了模型的应用,并通过比较静态分析进一步分别讨论了零售商的最优决策和供应链系统最优决策的性质．     

基于Nash均衡约束的竞争性评估方法研究

基于多指标决策模型(MCDM),研究了在Nash均衡约束的基础上,如何根据各决策单元(DMU)本身的特点来获取不同DMU的优势权重从而达到最终决策时自身的优势最大化.从新的角度,引入Nash均衡约束,提出了基于Nash均衡约束的多指标决策竞争性评估模型.在主体自身优势最大化的基础上,增加Nash均衡约束,通过约束参数的不断迭代,达到各决策单元的优势均衡,给出了一种新的基于优势均衡的客观确定权重的方法.     

基于秩依期望效用理论的鹰鸽博弈均衡解分析

运用秩依期望效用理论研究鹰鸽博弈模型,在考虑局中人带有情绪因素的条件下研究博弈均衡解的存在性条件以及局中人情绪因素对均衡解的影响规律.研究发现:局中人情绪因素虽然不影响纯战略意义下的博弈均衡解,但对混合战略纳什均衡解存在非常大的影响.如果博弈双方争夺的利益大于双方同时采取"鹰"策略时的总成本,则无论局中人情绪如何,博弈不存在混合战略均衡;如果博弈双方争夺的利益小于双方同时采取"鹰"策略时的总成本,则当局中人同为悲观情绪且情绪指数的倒数之和小于等于1时,博弈不存在混合战略均衡解;否则,混合战略均衡解存在.特别地,如果博弈双方争夺的利益等于双方同时采取"鹰"策略时的总成本,则无论局中人情绪如何,存在且有无数个混合战略均衡.此外,在混合战略均衡存在的条件下,各自的混合均衡战略是分别关于自身或对方情绪指数的单调函数.     

The Expected Number of Nash Equilibria of a Normal Form Game

Fix finite pure strategy sets _S1,…,_Sn , and let S=_S1×⋯×_Sn . In our model of a random game the agents' payoffs are statistically independent, with each agent's payoff uniformly distributed on the unit sphere in ℝ^S. For given nonempty _T1⊂_S1,…,_Tn⊂_Sn we give a computationally implementable formula for the mean number of Nash equilibria in which each agent i's mixed strategy has support T_i. The formula is the product of two expressions. The first is the expected number of totally mixed equilibria for the truncated game obtained by eliminating pure strategies outside the sets T_i. The second may be construed as the “probability” that such an equilibrium remains an equilibrium when the strategies in the sets _Si∖_Ti become available.     

多属性采购拍卖与多属性不对称纳什谈判的比较研究

拍卖与谈判作为采购中有效选择交易对象的常见方式,从最大化采购方收益的角度看,现有理论对这2种方式各有支持。通过运用经典的多属性拍卖模型和多属性不对称纳什谈判模型,将拍卖的期望收益和谈判的收益进行比较,发现2种机制的分界与谈判力量和投标人数这2个指标有关,通过划分谈判力量和投标人数取值的不同区间,找到了拍卖或谈判这2种方式的边界条件以及它们各自的适宜范围。     

Computing equilibrium in network utility-sharing and discrete election games

Journal of Combinatorial Optimization - This paper studies the computation of pure Nash equilibrium (PNE) in network utility-sharing and discretized Hotelling–Downs games, and the interplay...