Single-payoff farsighted stable sets in strategic games with dominant punishment strategies

We investigate farsighted stable sets in a class of strategic games with dominant punishment strategies. In this class of games, each player has a strategy that uniformly minimizes the other players’ payoffs for any given strategies chosen by these other players. We particularly investigate a special class of farsighted stable sets, each of which consists of strategy profiles yielding a single payoff vector. We call such a farsighted stable set as a single-payoff farsighted stable set. We propose a concept called an inclusive set that completely characterizes single-payoff farsighted stable sets in strategic games with dominant punishment strategies. We also show that the set of payoff vectors yielded by single-payoff farsighted stable sets is closely related to the strict \(\alpha \)-core in a strategic game. Furthermore, we apply the results to strategic games where each player has two strategies and strategic games associated with some market models.     

分销供应链中竞争零售商联盟的稳定性

针对由单一供应商和三个相互竞争零售商组成的两层分销供应链系统,在三种不同的博弈框架下,采用合作博弈论中短视的Nash稳定性概念与远视的最大一致集(LCS)概念研究了供应商与不同零售商联盟间的定价博弈,分别讨论了不同类型零售商联盟的稳定性。发现不论是在供应商处于领导地位,还是在零售商处于领导地位的市场中,当竞争强度较弱时,大联盟不是短视零售商联盟的稳定结构,却有可能是远视零售商联盟的稳定结构;当竞争强度较强时,则无论是短视零售商还是远视零售商都以大联盟为稳定结构,但是,在供应商处于领导地位的市场中,远视零售商形成大联盟的阈值较高;在供应商和零售商地位相同的市场中,大联盟则是远视零售商和短视零售商共同的稳定结构。     

Noncooperative farsighted stable set in an <Emphasis Type="Italic">n</Emphasis>-player prisoners’ dilemma

We examine an n-player prisoners’ dilemma game in which only individual deviations are allowed, while coalitional deviations (even non-binding ones) are not, and every player is assumed to be sufficiently farsighted to understand not only the direct outcome of his own deviation but also the ultimate outcome resulting from a chain of subsequent deviations by other players. We show that there exists a unique, noncooperative farsighted stable set (NFSS) and that it supports at least one (partially and/or fully) cooperative outcome, which is individually rational and Pareto-efficient. We provide a sufficient condition for full cooperation. Further, we discuss the relationship between NFSS and other “stable set” concepts such as the (myopic) von Neumann–Morgenstern stable set, Harsanyi (1974)’s strictly stable set, Chwe (1994)’s largest consistent set, and the cooperative farsighted stable set examined by Suzuki and Muto (2005). The author is very grateful to Professor Eiichi Miyagawa, the editor and the associate editor of this journal for their insightful comments and suggestions. He also acknowledges the financial support of Japan Society for the Promotion of Science [Grant-in-Aid for Scientific Research (C), No. 18530175].     

Optimal cost sharing for capacitated facility location games

We consider cost sharing for a class of facility location games, where the strategy space of each player consists of the bases of a player-specific matroid defined on the set of resources. We assume that resources have nondecreasing load-dependent costs and player-specific delays. Our model includes the important special case of capacitated facility location problems, where players have to jointly pay for opened facilities. The goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate two classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium and separable protocols additionally require that the resulting cost shares only depend on the set of players on a resource. We find optimal basic and separable protocols that guarantee the price of stability/price of anarchy to grow logarithmically/linearly in the number of players. These results extend our previous results (cf. von Falkenhausen & Harks, 2013), where optimal basic and separable protocols were given for the case of symmetric matroid games without delays.     

The Shapley value for cooperative games under precedence constraints

Cooperative games are considered where only those coalitions of players are feasible that respect a given precedence structure on the set of players. Strengthening the classical symmetry axiom, we obtain three axioms that give rise to a unique Shapley value in this model. The Shapley value is seen to reflect the expected marginal contribution of a player to a feasible random coalition, which allows us to evaluate the Shapley value nondeterministically. We show that every exact algorithm for the Shapley value requires an exponential number of operations already in the classical case and that even restriction to simple games is #P-hard in general. Furthermore, we outline how the multi-choice cooperative games of Hsiao and Raghavan can be treated in our context, which leads to a Shapley value that does not depend on pre-assigned weights. Finally, the relationship between the Shapley value and the permission value of Gilles, Owen and van den Brink is discussed. Both refer to formally similar models of cooperative games but reflect complementary interpretations of the precedence constraints and thus give rise to fundamentally different solution concepts.     

Cooperative games of choosing partners and forming coalitions in the marketplace

Two games of interacting between a coalition of players in a marketplace and the residual players acting there are discussed, along with two approaches to fair imputation of gains of coalitions in cooperative games that are based on the concepts of the Shapley vector and core of a cooperative game. In the first game, which is an antagonistic one, the residual players try to minimize the coalition's gain, whereas in the second game, which is a noncooperative one, they try to maximize their own gain as a coalition. A meaningful interpretation of possible relations between gains and Nash equilibrium strategies in both games considered as those played between a coalition of firms and its surrounding in a particular marketplace in the framework of two classes of n-person games is presented. A particular class of games of choosing partners and forming coalitions in which models of firms operating in the marketplace are those with linear constraints and utility functions being sums of linear and bilinear functions of two corresponding vector arguments is analyzed, and a set of maximin problems on polyhedral sets of connected strategies which the problem of choosing a coalition for a particular firm is reducible to are formulated based on the firm models of the considered kind.     

Stabilizing network bargaining games by blocking players

Cooperative matching games (Shapley and Shubik) and Network bargaining games (Kleinberg and Tardos) are games described by an undirected graph, where the vertices represent players. An important role in such games is played by stable graphs, that are graphs whose set of inessential vertices (those that are exposed by at least one maximum matching) are pairwise non adjacent. In fact, stable graphs characterize instances of such games that admit the existence of stable outcomes. In this paper, we focus on stabilizing instances of the above games by blocking as few players as possible. Formally, given a graph G we want to find a minimum cardinality set of vertices such that its removal from G yields a stable graph. We give a combinatorial polynomial-time algorithm for this problem, and develop approximation algorithms for some NP-hard weighted variants, where each vertex has an associated non-negative weight. Our approximation algorithms are LP-based, and we show that our analysis are almost tight by giving suitable lower bounds on the integrality gap of the used LP relaxations.     

Stability of the core mapping in games with a countable set of players

Greenberg (1990) and Ray (1989) showed that in coalitional games with a finite set of players the core consists of those and only those payoffs that cannot be dominated using payoffs in the core of a subgame. We extend the definition of the dominance relation to coalitional games with an infinite set of players and show that this result may not hold in games with a countable set of players (even in convex games). But if a coalitional game with a countable set of players satisfies a mild continuity property, its core consists of those and only those payoff vectors which cannot be dominated using payoffs in the core of a subgame.     

Common pool resources with support

We examine the role of support for coalition stability in common pool resource games such as fisheries games. Some players may not want to join a coalition that jointly manages a resource. Still, because they benefit from spillovers, they may want to support the coalition with a transfer payment to set incentives for others to join. We find that the impact of support on equilibria of this game is limited to games with three or five players. Recommendations for Resource Managers

• Coalitions may be able to effectively manage common pool resources such as fisheries but such coalitions are often not stable due to free-rider incentives.
• We explore the impact of a transfer scheme that can improve this coalition stability which would lead to larger and more effective coalitions.
• Our results show that this new transfer scheme works only for cases where the number of players is small.

     

Take-and-guess games

This paper studies two classes of two-person zero-sum games in which the strategies of both players are of a special type. Each strategy can be split into two parts, a taking and a guessing part. In these games two types of asymmetry between the players can occur. In the first place, the number of objects available for taking does not need to be the same for both players. In the second place, the players can be guessing sequentially instead of simultaneously; the result is asymmetric information. The paper studies the value and equilibria of these games, for all possible numbers of objects available to the players, for the case with simultaneous guessing as well as for the variant with sequential guessing.      

A test of the core solution in finite strategy non-sidepayment games

This paper reports a test of the core solution in cooperative non-sidepayment games where players have finite strategy sets. Two laboratory experiments were conducted with three-person and four-person games; in both experiments, the core solution was tested competitively against the von Neumann-Morgenstern stable set and the imputation set. Predictions from these solution concepts were computed under parameters of α-effectiveness and strict preference. Results show that the frequency of outcomes falling in core is substantially higher than that observed in previous experiments (most of which involve sidepayment games). In addition, goodness-of-fit tests show that the core solution predicts the observed outcomes more accurately than do the stable set or the imputation set.     

Common resources, optimality and taxes in dynamic games with increasing number of players

In the paper we examine the problem of exploitation of a common renewable resource. We use two kinds of models of this problem: games with finitely many players and games with a continuum of players. Equilibria in both cases are calculated and the payoffs are compared with payoffs in the situation in which each player behaves as a single owner of the resource. Various concepts of optimality are considered: optimality in the sense of property, Pareto optimality, maximization of a social welfare function of specific type and environmental sustainability. Another issue is the problem of enforcement of assumed profiles by so-called “linear” tax systems. Special attention is paid to the comparison of games with finitely many players and their continuum-of-players limit game.     

The maximum and the addition of assignment games

In the framework of two-sided assignment markets, we first consider that, with several markets available, the players may choose where to trade. It is shown that the corresponding game, represented by the maximum of a finite set of assignment games, may not be balanced. Some conditions for balancedness are provided and, in that case, properties of the core are analyzed. Secondly, we consider that players may trade simultaneously in more than one market and then add up the profits. The corresponding game, represented by the sum of a finite set of assignment games, is balanced. Moreover, under some conditions, the sum of the cores of two assignment games coincides with the core of the sum game.     

Ternary choices in repeated games and border collision bifurcations

Several recent contributions formalize and analyze binary choices games with externalities as those described by Schelling. Nevertheless, in the real world choices are not always binary, and players have often to decide among more than two alternatives. These kinds of interactions are examined in game theory where, starting from the well known rock-paper-scissor game, several other kinds of strategic interactions involving more than two choices are examined. In this paper we investigate how the dynamics evolve introducing one more option in binary choice games with externalities. The dynamics we obtain are always in a stable regime, that is, the structurally stable dynamics are only attracting cycles, but of any possible positive integer as period. We show that, depending on the structure of the game, the dynamics can be quite different from those existing when considering binary choices. The bifurcation structure, due to border collisions, is explained, showing the existence of so-called big-bang bifurcation points.     

Two Game Models for Cooperation with Implicit Noncooperation

We propose two flexible game models to represent and analyze cases that cannot be modeled by current game models. One is called sharing creditability game (SCG) and the other is called bottomline game (BLG). The new models transform cooperative games into new games that incorporate auxiliary information (noncooperative in nature) usually neglected in previous theories. The new games will be solved only by traditional noncooperative game theory. When the new solutions are applied to the original games, the solutions can reflect the auxiliary information in addition to the original objectives of the decision makers or players. Generally, the new solutions are different from the cooperative and the noncooperative solutions of the original games. Existing transferable utility (TU) games and noncooperative games will coincide with special cases of the two new game models. Using SCG and BLG, the prisoner’s dilemma can be reformulated and a richer set of decisions can be considered for the players. The two new game models have potential applications in military and socioeconomic situations.This research was partly funded by the College Engineering, Ohio State University.     

拟凸对策的解

本文先引入拟凸对策的概念作为凸对策的推广,然后研究这种对策的各种解的性质。我们主要证得,当局中人数小于6或者对策的复盖严格凸时,谈判集与核心重合,核是单点集。另外,存在一个6人拟凸对策,其谈判集与核心不同。     

Farsighted Stability in an n-Person Prisoner’s Dilemma

Farsighted stability is examined in an n-person prisoner’s dilemma. It is shown that any individually rational and Pareto efficient outcome is a farsighted stable set and no other farsighted stable set exists; it is further shown that the largest consistent set consists of all individually rational outcomes.     

Structure of equilibria inN-person non-cooperative games

Here we study the structure of Nash equilibrium points forN-person games. For two-person games we observe that exchangeability and convexity of the set of equilibrium points are synonymous. This is shown to be false even for three-person games. For completely mixed games we get the necessary inequality constraints on the number of pure strategies for the players. Whereas the equilibrium point is unique for completely mixed two-person games, we show that it is not true for three-person completely mixed game without some side conditions such as convexity on the equilibrium set. It is a curious fact that for the special three-person completely mixed game with two pure strategies for each player, the equilibrium point is unique; the proof of this involves some combinatorial arguments.     

Farsighted coalitional stability in TU-games

We study farsighted coalitional stability in the context of TU-games. We show that every TU-game has a nonempty largest consistent set and that each TU-game has a von Neumann–Morgenstern farsighted stable set. We characterize the collection of von Neumann–Morgenstern farsighted stable sets. We also show that the farsighted core is either empty or equal to the set of imputations of the game. In the last section, we explore the stability of the Shapley value. The Shapley value of a superadditive game is a stable imputation: it is a core imputation or it constitutes a von Neumann–Morgenstern farsighted stable set. A necessary and sufficient condition for a superadditive game to have the Shapley value in the largest consistent set is given.