Path cooperative games

Cooperative games provide an appropriate framework for fair and stable profit distribution in multiagent systems. In this paper, we study the algorithmic issues on path cooperative games that arise from the situations where some commodity flows through a network. In these games, a coalition of edges or vertices is successful if they establish a path from the source to the sink in the network, and lose otherwise. Based on dual theory of linear programming and the relationship with flow games, we provide the characterizations on the core, CS-core, least-core and nucleolus of path cooperative games, which implies all of these solution concepts are polynomial-time solvable for path cooperative games.     

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.     

On the Global Convergence of Stochastic Fictitious Play

We establish global convergence results for stochastic fictitious play for four classes of games: games with an interior ESS, zero sum games, potential games, and supermodular games. We do so by appealing to techniques from stochastic approximation theory, which relate the limit behavior of a stochastic process to the limit behavior of a differential equation defined by the expected motion of the process. The key result in our analysis of supermodular games is that the relevant differential equation defines a strongly monotone dynamical system. Our analyses of the other cases combine Lyapunov function arguments with a discrete choice theory result: that the choice probabilities generated by any additive random utility model can be derived from a deterministic model based on payoff perturbations that depend nonlinearly on the vector of choice probabilities.     

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.     

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.     

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.     

Single Crossing Properties and the Existence of Pure Strategy Equilibria in Games of Incomplete Information

This paper analyzes a class of games of incomplete information where each agent has private information about her own type, and the types are drawn from an atomless joint probability distribution. The main result establishes existence of pure strategy Nash equilibria (PSNE) under a condition we call the single crossing condition (SCC), roughly described as follows: whenever each opponent uses a nondecreasing strategy (in the sense that higher types choose higher actions), a player's best response strategy is also nondecreasing. When the SCC holds, a PSNE exists in every finite‐action game. Further, for games with continuous payoffs and a continuum of actions, there exists a sequence of PSNE to finite‐action games that converges to a PSNE of the continuum‐action game. These convergence and existence results also extend to some classes of games with discontinuous payoffs, such as first‐price auctions, where bidders may be heterogeneous and reserve prices are permitted. Finally, the paper characterizes the SCC based on properties of utility functions and probability distributions over types. Applications include first‐price, multi‐unit, and all‐pay auctions; pricing games with incomplete information about costs; and noisy signaling games.     

基于Choquet延拓n人模糊对策的Shapley值

由于n人对策任意联盟可由它的特征向量来等价地表示,利用Choquet积分,将n人对策从集合{0,1}n延拓到[0,1]n上,通过建立公理化体系,对具有Choquet延拓形式n人模糊对策的Shapley值进行深入研究,证明了这类n人模糊对策Shapley值存在性与惟一性,并给出了此模糊对策Shapley值的解释表达式.最后将此模糊对策的Shapley值作为收益分配方案应用到供应链协作企业收益分配的实例中.     

Die Kultur der Macht. Die Macht der Kultur

Acting in organizations is characterized by strategies of “Bemächtigung” (repression) just as “Ermächtigung” (empowerment): Everyone tries to push through its individual interests, legitimate or not. Thereby in every organization specific rules of game and stiles of play are developed. Altogether these rules constitute the specific organizational culture. In unfair games, strategies of repression are dominant. In fair games, all players try to realize over and over again a just balance of legitimate interests of all stakeholders. Supervision aims to strengthen “Spielmächtigkeit” (ability of play and game) so that its addressees are able to change unfair games into fair games. The know-how for this is here called “technology of empowerment”.     

广义不确定性下广义博弈中NS均衡的存在性

把不确定性引入广义博弈的研究之中,在此博弈中,局中人策略之间存在相互影响,局中人的策略可以改变不确定参数的变化范围,而且局中人的支付函数和策略可行反应映射都受到不确定参数的作用,此类型博弈定义为广义不确定性下的广义博弈问题。进一步定义出此类型博弈中的NS均衡,并且凭借Fan-Glicksberg不动点定理,证明此均衡点的存在性。最后给出算例验证其可行性。     

Truthful Equilibria in Dynamic Bayesian Games

This paper characterizes an equilibrium payoff subset for dynamic Bayesian games as discounting vanishes. Monitoring is imperfect, transitions may depend on actions, types may be correlated, and values may be interdependent. The focus is on equilibria in which players report truthfully. The characterization generalizes that for repeated games, reducing the analysis to static Bayesian games with transfers. With independent private values, the restriction to truthful equilibria is without loss, except for the punishment level: if players withhold their information during punishment‐like phases, a folk theorem obtains.     

Two-step values for games with two-level communication structure

TU games with two-level communication structure, in which a two-level communication structure relates fundamentally to the given coalition structure and consists of a communication graph on the collection of the a priori unions in the coalition structure, as well as a collection of communication graphs within each union, are considered. For such games we introduce two families of two-step values inspired by the two-step procedures staying behind the Owen value (Owen, in: Henn, Moeschlin (eds) Essays in mathematical economics and game theory, Springer, Berlin, pp 76–88, 1977) and the two-step Shapley value (Kamijo in Int Game Theory Rev 11:207–214, 2009) for games with coalition structure. Our approach is based on the unified treatment of several component efficient values for games with communication structure and it generates two-stage solution concepts that apply component efficient values for games with communication structure on both distribution levels. Comparable axiomatic characterizations are provided.     

Weakly Belief‐Free Equilibria in Repeated Games With Private Monitoring

Repeated games with imperfect private monitoring have a wide range of applications, but a complete characterization of all equilibria in this class of games has yet to be obtained. The existing literature has identified a relatively tractable subset of equilibria. The present paper introduces the notion of weakly belief‐free equilibria for repeated games with imperfect private monitoring. This is a tractable class which subsumes, as a special case, a major part of the existing literature (the belief‐free equilibria). It is shown that this class can outperform the equilibria identified by the previous work.     

利益相关者参与公司管理的进化博弈分析

利用进化博弈的复制动态方法,建立企业管理决策的进化博弈模型,研究利益相关者参与公司管理可能演化的管理模式.研究结果表明,企业最终进化成哪一种管理模式取决于初始时选择某一种管理模式的管理者比例,而这种比例与选择这种模式带给博弈方的收益大小有关系.     

NORMS MAKE PREFERENCES SOCIAL

We explore the idea that prosocial behavior in experimental games is driven by social norms imported into the laboratory. Under this view, differences in behavior across subjects is driven by heterogeneity in sensitivity to social norms. We introduce an incentivized method of eliciting individual norm‐sensitivity, and we show how it relates to play in public goods, trust, dictator, and ultimatum games. We show how our observations can be rationalized in a stylized model of norm‐dependent preferences under reasonable assumptions about the nature of social norms. Then we directly elicit norms in these games to test the robustness of our interpretation.     

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.     

Genericity and Markovian Behavior in Stochastic Games

This paper examines Markov perfect equilibria of general, finite state stochastic games. Our main result is that the number of such equilibria is finite for a set of stochastic game payoffs with full Lebesgue measure. We further discuss extensions to lower dimensional stochastic games like the alternating move game.     

有限战略式博弈纯战略均衡求解的新算法

针对现有寻找有限战略式博弈纯战略均衡方法的缺陷,本文证明了一个战略组合是纯战略蚋什均衡的充分必要条件,并根据该条件提出的求解此类博弈模型的纯战略均衡一个算法,最后用一个算例验证了该算法的有效性.     

EXPLAINING GIFT‐EXCHANGE—THE LIMITS OF GOOD INTENTIONS

This paper explores the limitations of intention‐based social preferences as an explanation of gift‐exchange between a firm and a worker. In a framework with one self‐interested and one reciprocal player, gift‐giving never arises in equilibrium. Instead, any equilibrium in a large class of multistage games must involve mutually unkind behavior of both players. Besides gift‐exchange, this class of games also includes moral hazard models and the rotten kid framework. Even though equilibrium behavior may appear positively reciprocal in some of these games, the self‐interested player never benefits from reciprocity. We discuss the relation of these results to the theoretical and empirical literature on gift‐exchange in employment relations.     

Hard‐to‐Solve Bimatrix Games

The Lemke–Howson algorithm is the classical method for finding one Nash equilibrium of a bimatrix game. This paper presents a class of square bimatrix games for which this algorithm takes, even in the best case, an exponential number of steps in the dimension d of the game. Using polytope theory, the games are constructed using pairs of dual cyclic polytopes with 2d suitably labeled facets in d‐space. The construction is extended to nonsquare games where, in addition to exponentially long Lemke–Howson computations, finding an equilibrium by support enumeration takes on average exponential time.