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.     

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.

     

Atomic congestion games with random players: network equilibrium and the price of anarchy

Journal of Combinatorial Optimization - In this paper, we present a new model of congestion games with finite and random number of players, and an analytical method to compute the random path and...     

价格和成本波动对CoPS合约方不合作行为影响的演化分析

在合同执行过程中因环境不确定性引发的违约行为，是导致复杂产品系统项目失败的重要原因。论文研究了环境波动（具体到市场价格波动和研制成本波动）对复杂产品系统合约方不合作行为的影响。首先研究了价格下降情况下买卖双方的收益函数、论证了收益函数中各变量与价格下降之间的逻辑关系，构建了复制动态方程、分析了用户不合作行为的演化路径和阈值与价格下降的关系；之后以同样的逻辑研究了价格上升情况下集成商的不合作行为；最后用数值仿真演示了初始条件改变和决策参数的不同取值对演化结果的影响。研究发现：（1）博弈双方收益函数中的各变量在价格下降时均是价格下降程度的函数，在价格上升时均是成本上涨程度的函数；（2）用户行为与价格下降的关系：当价格下降幅度小于用户合作阈值时合作是演化的结果，当价格下降幅度超过用户不合作阈值时不合作是演化的结果，当价格下降幅度界于合作阈值和不合作阈值之间时演化结果取决于对方的行为；（3）集成商行为与成本上升的关系：当成本上升幅度小于集成商合作阈值时合作是演化的结果，当成本上升幅度超过集成商不合作阈值时不合作是演化的结果，当成本上升幅度界于合作阈值和不合作阈值之间时演化结果取决于对方的行为。研究揭示了不合作行为与价格下降及成本上升的突变非线性关系，找出了合作和不合作的阈值。研究是环境不确定情境下合约治理理论在复杂产品系统及相关项目管理领域的深入，研究结果可为管理实践的合约治理提供决策支持，提高复杂产品系统项目的成功率。     

碳交易机制下零售商合作的费用分配研究

在一个由单供应商和多个零售商组成的二阶供应链中，研究碳交易机制下多零售商合作的订货决策问题。对完全信息下零售商合作的费用分配问题，应用合作博弈理论建立了费用分配的博弈模型，证明了博弈为子模博弈且设计了属于核心的费用分配方案，该方案不仅可通过总体单调分配机制实现而且可使大联盟长远稳定。对不完全信息下零售商合作的费用分配问题，证明了纯策略纳什均衡的存在性。研究结果表明，零售商的合作不仅能降低总费用，而且能降低碳排放量；各零售商在不完全信息下分担的费用大于完全信息下分担的费用。     

Duality Approaches to Economic Lot‐Sizing Games

Sharing common production, resources, and services to reduce cost are important for not for profit operations due to limited and mission‐oriented budget and effective cost allocation mechanisms are essential for encouraging effective collaborations. In this study, we illustrate how rigorous methodologies can be developed to derive effective cost allocations to facilitate sustainable collaborations in not for profit operations by modeling the cost allocation problem arising from an economic lot‐sizing (ELS) setting as a cooperative game. Specifically, we consider the economic lot‐sizing (ELS) game with general concave ordering cost. In this cooperative game, multiple retailers form a coalition by placing joint orders to a single supplier in order to reduce ordering cost. When both the inventory holding cost and backlogging cost are linear functions, it can be shown that the core of this game is non‐empty. The main contribution of this study is to show that a core allocation can be computed in polynomial time under the assumption that all retailers have the same cost parameters. Our approach is based on linear programming (LP) duality. More specifically, we study an integer programming formulation for the ELS problem and show that its LP relaxation admits zero integrality gap, which makes it possible to analyze the ELS game by using LP duality. We show that there exists an optimal dual solution that defines an allocation in the core. An interesting feature of our approach is that it is not necessarily true that every optimal dual solution defines a core allocation. This is in contrast to the duality approach for other known cooperative games in the literature.     

Who's Who in Networks. Wanted: The Key Player

Finite population noncooperative games with linear‐quadratic utilities, where each player decides how much action she exerts, can be interpreted as a network game with local payoff complementarities, together with a globally uniform payoff substitutability component and an own‐concavity effect. For these games, the Nash equilibrium action of each player is proportional to her Bonacich centrality in the network of local complementarities, thus establishing a bridge with the sociology literature on social networks. This Bonacich–Nash linkage implies that aggregate equilibrium increases with network size and density. We then analyze a policy that consists of targeting the key player, that is, the player who, once removed, leads to the optimal change in aggregate activity. We provide a geometric characterization of the key player identified with an intercentrality measure, which takes into account both a player's centrality and her contribution to the centrality of the others.     

Distributed Decisions in Networks: Laboratory Study of Routing Splittable Flow

We study network games in which users choose routes in computerized networks susceptible to congestion. In the “unsplittable” condition, route choices are completely unregulated, players are symmetric, each player controls a single unit of flow and chooses a single origin–destination (O–D) path. In the “splittable” condition, which is the main focus of this study, route choices are partly regulated, players are asymmetric, each player controls multiple units of flow and chooses multiple O–D paths to distribute her fleet. In each condition, users choose routes in two types of network: a basic network with three parallel routes and an augmented network with five routes sharing joint links. We construct and subsequently test equilibrium solutions for each combination of condition and network type, and then propose a Markov revision protocol to account for the dynamics of play. In both conditions, route choice behavior approaches equilibrium and the Braess Paradox is clearly manifested.     

Two efficient values of cooperative games with graph structure based on $$\tau $$-values

The paper is devoted to value concepts for cooperative games with a communication structure represented by a graph. Under assumptions that the players partition themselves into ‘components’ before realizing cooperation and the worth of the grand coalition not less than the sum of the worths of all components, the fair distribution of surplus solution and the two-step \(\tau \)-value are introduced as two efficient values for such games, each of which is an extension of the graph \(\tau \)-value. For the two efficient values, we discuss their special properties and we provide their axiomatic characterizations in views of those properties. By analysing an example applied to the two values, we conclude that the fair distribution of surplus solution allocates more surplus to the bigger coalitions and favors the powerful players, while the two-step \(\tau \)-value benefits the vulnerable groups and inspires to form small coalitions.     

Congestion games with mixed objectives

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the (non-)existence of pure Nash equilibria (PNE), the convergence of improvement dynamics, the quality of equilibria and show the complexity of the decision problem. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.     

具有联盟优先关系的模糊合作博弈的目标规划求解模型

用合作博弈研究实际管理问题中的分配方案时，常常存在一些不重要联盟或无效联盟，这些联盟影响公平合理的分配方案。因此，联盟的重要程度成为求解合作博弈必不可少的因素。本文考虑了联盟的重要性和局中人参与联盟的不确定性，研究了具有优先关系的模糊联盟合作博弈(简称为模糊合作博弈)。首先，借助于目标规划模型的优先因子可以表征联盟重要程度的思想，通过构建多优先级目标规划模型，得到模糊合作博弈新的解。其次，证明了构建的多优先级目标规划模型的解和模糊合作博弈的核心之间具有重要对应关系。最后，通过数值实例和比较分析，说明本文提出的多优先级目标规划模型求解模糊合作博弈问题的合理性和有效性。研究表明：(1)本文提出的多优先级目标规划模型考虑不同联盟重要程度，得到的解符合“多劳多得”原则，能够更公平合理解决实际管理中的分配问题。(2)本文的目标规划模型同时适用于求解存在联盟特征函数值缺失的合作博弈。与已有合作博弈的解进行比较分析，该模型无需估算无效联盟的特征函数缺失数据得到的分配值更为准确。从而，说明本文给出的目标规划求解模糊合作博弈解的模型，更符合许多管理学问题的实际情况。(3)通过多优先级目标规划模型最优解是否存在可判断模糊合作博弈的核心存在情况，若核心存在则该模型通过目标规划软件包可得到核心内的一个解，这样也得到了一个判断合作博弈核心是否存在的标准。(4)目标规划模型可弥补已有合作博弈解的一些不足，如核心可能为空集，Shapley值和最小二乘预核仁可能不满足个体合理性等。本文构建的多优先级目标规划模型不仅能求解联盟具有优先关系的模糊合作博弈，而且能够求解一般合作博弈的解，该目标规划模型作为合作博弈一种新的求解方法，能更有效地解决实际管理中的分配问题，具有更加广泛的应用价值。     

Certifiable Pre‐Play Communication: Full Disclosure

This article asks when communication with certifiable information leads to complete information revelation. We consider Bayesian games augmented by a pre‐play communication phase in which announcements are made publicly. We first characterize the augmented games in which there exists a fully revealing sequential equilibrium with extremal beliefs (i.e., any deviation is attributed to a single type of the deviator). Next, we define a class of games for which existence of a fully revealing equilibrium is equivalent to a richness property of the evidence structure. This characterization enables us to provide different sets of sufficient conditions for full information disclosure that encompass and extend all known results in the literature, and are easily applicable. We use these conditions to obtain new insights in games with strategic complementarities, voting with deliberation, and persuasion games with multidimensional types.     

Finding disjoint paths with related path costs

We consider routing in survivable networks that provide protection against node or link failures. In these networks resilience against failures is provided by routing connections on pairs of disjoint paths called primary and backup paths. The primary path of a connection carries its traffic under normal circumstances and in the eventuality of a network failure effecting the primary path the connection traffic (all or some portion of it) is rerouted over its backup path. In an online setting as connection requests arrive a pair of disjoint primary and backup paths of least total cost (under some link cost metric) are selected to route the connections. In many situations the cost metric used for the primary path differs from the cost metric used for the backup path. Also in many realistic settings these two cost metrics are related to each other. In this paper we study the problem of finding a pair of edge or node disjoint paths of least total cost where the cost of the primary path is the total cost of its links while the cost for the backup path is α times the sum of the cost of its links, for some given α < 1. We show that the problem is hard to approximate to within a factor for any positive . In addition we show that the problem is complete for a set of hard to approximate problems. On the positive side we show that a simple algorithm achieves an approximation ratio of for the problem.     

Improvement of path analysis algorithm in social networks based on HBase

When social network has reached hundreds of million users, the analysis of data in social network services becomes very important. Understanding how nodes interconnect in large graphs is an essential problem in many fields. In order to find connecting nodes between two nodes or two groups of source nodes in huge graphs, we propose a parallelized data-mining algorithm to get the shortest path between nodes in a social network based on HBase distributed key/value store. Our algorithm can achieve the shortest path among different nodes in network under the parallel environment. We analyze the social network model by this algorithm first, and then optimize the output from cloud platform by using the intermediary degrees and degree central algorithm. Finally, with a simulated social network, we validate the efficiency of the proposed algorithm. The experiment results indicate that our algorithm can improve the efficiency of parallel breath-first search (BSF).     

Harsanyi power solution for games with restricted cooperation

This paper discusses the Harsanyi power solution for cooperative games in which cooperation among players is based on an arbitrary collection of feasible coalitions. We define the Harsanyi power solution as a value which distributes the Harsanyi dividends such that the dividend shares of players in each feasible coalition are proportional to the corresponding players’ participation index, (i.e., a power measure for players in the cooperation restrictions). When all coalitions can be formed in a game, the Harsanyi power solution coincides with the Shapley value. We provide two axiomatic characterizations for the Harsanyi power solution: one uses component efficiency and participation fairness, and the other uses efficiency and participation balanced contributions. Meanwhile, we show that the axioms of each axiomatization are logically independent. The study also shows that the Harsanyi power solution satisfies several other properties such as additivity and inessential player out. In addition, the Harsanyi power solution is the unique value that admits the \(\lambda \)-potential.     

不同渠道权力结构和信息结构下供应链定价和销售努力决策

本文针对零售商销售努力和销售价格影响需求情况下的制造商-零售商两级供应链,研究不同渠道权力结构和信息结构下供应链的分散决策。基于博弈理论和建模方法,对几种权力结构和信息结构情景建立相应模型,通过理论与数值分析对不同博弈均衡进行比较。研究表明,随着零售商势力逐步增强制造商利润会逐步恶化;但零售商势力增强能否带来更多利润,取决于需求对价格和销售努力的敏感度、销售努力成本以及信息结构。占优一方可以通过获取对方更多信息来改善自己处境。若占优零售商不得不依赖于对制造商成本先验分布进行决策,当估计的均值大于真实成本时,适度的方差对零售商更有利。最后,讨论了销售努力成本分担的合作机制,针对非合作博弈给出了帕累托改进的合约区间和 Nash讨价还价均衡。     

What Happens in the Field Stays in the Field: Exploring Whether Professionals Play Minimax in Laboratory Experiments

The minimax argument represents game theory in its most elegant form: simple but with stark predictions. Although some of these predictions have been met with reasonable success in the field, experimental data have generally not provided results close to the theoretical predictions. In a striking study, Palacios‐Huerta and Volij ( 2008 ) presented evidence that potentially resolves this puzzle: both amateur and professional soccer players play nearly exact minimax strategies in laboratory experiments. In this paper, we establish important bounds on these results by examining the behavior of four distinct subject pools: college students, bridge professionals, world‐class poker players, who have vast experience with high‐stakes randomization in card games, and American professional soccer players. In contrast to Palacios‐Huerta and Volij's results, we find little evidence that real‐world experience transfers to the lab in these games—indeed, similar to previous experimental results, all four subject pools provide choices that are generally not close to minimax predictions. We use two additional pieces of evidence to explore why professionals do not perform well in the lab: (i) complementary experimental treatments that pit professionals against preprogrammed computers and (ii) post‐experiment questionnaires. The most likely explanation is that these professionals are unable to transfer their skills at randomization from the familiar context of the field to the unfamiliar context of the lab.     

Clocks and Trees: Isomorphic Dutch Auctions and Centipede Games

We report an experiment on effects of varying institutional format and dynamic structure of centipede games and Dutch auctions. Centipede games with a clock format unravel, as predicted by theory but not reported in previous literature on two‐player tree‐format centipede games. Dutch auctions with a tree format produce bids close to risk neutral Nash equilibrium bids, unlike previous literature on clock‐format Dutch auctions. Our data provide a new, expanded set of stylized facts which may provide a foundation for unified modeling of play in a class of games that includes centipede games and Dutch auctions.     

Finding nucleolus of flow game

We study the algorithmic issues of finding the nucleolus of a flow game. The flow game is a cooperative game defined on a network D=(V,E;ω). The player set is E and the value of a coalition S⊆E is defined as the value of a maximum flow from source to sink in the subnetwork induced by S. We show that the nucleolus of the flow game defined on a simple network (ω(e)=1 for each e∈E) can be computed in polynomial time by a linear program duality approach, settling a twenty-three years old conjecture by Kalai and Zemel. In contrast, we prove that both the computation and the recognition of the nucleolus are -hard for flow games with general capacity. Supported by NCET, NSFC (10771200), a CERG grant (CityU 1136/04E) of Hong Kong RGC, an SRG grant (7001838) of City University of Hong Kong.     

Stochastic Learning Dynamics and Speed of Convergence in Population Games

We study how long it takes for large populations of interacting agents to come close to Nash equilibrium when they adapt their behavior using a stochastic better reply dynamic. Prior work considers this question mainly for 2 × 2 games and potential games; here we characterize convergence times for general weakly acyclic games, including coordination games, dominance solvable games, games with strategic complementarities, potential games, and many others with applications in economics, biology, and distributed control. If players' better replies are governed by idiosyncratic shocks, the convergence time can grow exponentially in the population size; moreover, this is true even in games with very simple payoff structures. However, if their responses are sufficiently correlated due to aggregate shocks, the convergence time is greatly accelerated; in fact, it is bounded for all sufficiently large populations. We provide explicit bounds on the speed of convergence as a function of key structural parameters including the number of strategies, the length of the better reply paths, the extent to which players can influence the payoffs of others, and the desired degree of approximation to Nash equilibrium.