Modelling ‘contracts’ between a terrorist group and a government in a sequential game

In this paper, we apply a sequential game to study the possibility of ‘contracts’ (or at least mutually beneficial arrangements) between a government and a terrorist group. We find equilibrium solutions for complete and incomplete information models, where the government defends and/or provides positive rent, and the terrorist group attacks. We also study the sensitivities of equilibria as a function of both players’ target valuations and preferences for rent. The contract option, if successful, may achieve (partial) attack deterrence, and significantly increase the payoffs not only for the government, but also for some types of terrorist groups. Our work thus provides some novel insights in combating terrorism.     

Generalized correlated equilibrium for two-person games in extensive form with perfect information

A correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is applied for two-person finite games in extensive form with perfect information. Randomization by an umpire takes place over the leaves of the game tree. At every decision point players have the choice either to follow the recommendation of the umpire blindly or freely choose any other action except the one suggested. This scheme can lead to Pareto-improved outcomes of other correlated equilibria. Computational issues of maximizing a linear function over the set of soft correlated equilibria are considered and a linear-time algorithm in terms of the number of edges in the game tree is given for a special procedure called “subgame perfect optimization”.     

Bounded rationality and correlated equilibria

We study an interactive framework that explicitly allows for nonrational behavior. We do not place any restrictions on how players’ behavior deviates from rationality, but rather, on players’ higher-order beliefs about the frequency of such deviations. We assume that there exists a probability p such that all players believe, with at least probability p, that their opponents play rationally. This, together with the assumption of a common prior, leads to what we call the set of p-rational outcomes, which we define and characterize for arbitrary probability p. We then show that this set varies continuously in p and converges to the set of correlated equilibria as p approaches 1, thus establishing robustness of the correlated equilibrium concept to relaxing rationality and common knowledge of rationality. The p-rational outcomes are easy to compute, also for games of incomplete information. Importantly, they can be applied to observed frequencies of play for arbitrary normal-form games to derive a measure of rationality \(\overline{p}\) that bounds from below the probability with which any given player chooses actions consistent with payoff maximization and common knowledge of payoff maximization.     

A generalization of correlated equilibrium: A new protocol

A new correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is introduced for finite games. After randomization over the outcome space, players have the choice either to follow the recommendation of an umpire blindly or freely choose some other action except the one suggested. This scheme can lead to Pareto-better outcomes than the simple extension introduced by [Moulin, H., Vial, J.-P., 1978. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory 7, 201–221]. The informational and interpretational aspects of soft correlated equilibria are also discussed in detail. The power of the generalization is illustrated in the prisoners’s dilemma and a congestion game.     

Comparative statics of a signaling game: An experimental study

In this paper a simple and basic signaling game is studied in an experimental environment. First, we check whether we can replicate some of the findings in the literature concerning equilibrium selection and the use and impact of costly signals. Second, and foremost, the comparative statics implications of the game are studied. The experimental results are related to the predictions of two competing behavioral models: a game model, in which subjects are assumed to behave in line with (refined) sequential equilibrium theory, and a decision model, in which subjects are assumed to behave as non-strategic decision makers. The experimental outcomes replicate the finding in the literature that costly messages are sent more frequently by ‘higher’ sender types (whose information is such that persuasion is also profitable to the responder), and that such messages have an impact on the behavior of the responder. These results are consistent with (versions of) both the game model and the decision model. The comparative statics results, however, clearly point in the direction of the decision model. Play is most strongly affected by ‘own’ payoff parameters, as predicted by the decision model, and less so by opponent's payoff parameters, as predicted by the mixed strategies of the refined sequential equilibrium. Particularly, a decision model in which players are assumed to adapt beliefs about opponents' choice probabilities in response to experience in previous play, appears to succeed best in organizing the data.     

On the solution of affine generalized Nash equilibrium problems with shared constraints by Lemke’s method

Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players’ variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e., common to, the players. Specifically, we present several avenues for computing structurally different GNE based on varying consistency requirements on the Lagrange multipliers associated with the shared constraints. Traditionally, variational equilibria (VE) have been amongst the more well-studied GNE and are characterized by a requirement that the shared constraint multipliers be identical across players. We present and analyze a modification to Lemke’s method that allows us to compute GNE that are not necessarily VE. If successful, the modified method computes a partial variational equilibrium characterized by the property that some shared constraints are imposed to have common multipliers across the players while other are not so imposed. Trajectories arising from regularizing the LCP formulations of AGNEPs are shown to converge to a particular type of GNE more general than Rosen’s normalized equilibrium that in turn includes a variational equilibrium as a special case. A third avenue for constructing alternate GNE arises from employing a novel constraint reformulation and parameterization technique. The associated parametric solution method is capable of identifying continuous manifolds of equilibria. Numerical results suggest that the modified Lemke’s method is more robust than the standard version of the method and entails only a modest increase in computational effort on the problems tested. Finally, we show that the conditions for applying the modified Lemke’s scheme are readily satisfied in a breadth of application problems drawn from communication networks, environmental pollution games, and power markets.     

Games with randomly disturbed payoffs: A new rationale for mixed-strategy equilibrium points

Equilibrium points in mixed strategies seem to be unstable, because any player can deviate without penalty from his equilibrium strategy even if he expects all other players to stick to theirs. This paper proposes a model under which most mixed-strategy equilibrium points have full stability. It is argued that for any gameΓ the players' uncertainty about the other players' exact payoffs can be modeled as a disturbed gameΓ ^*, i.e., as a game with small random fluctuations in the payoffs. Any equilibrium point inΓ, whether it is in pure or in mixed strategies, can “almost always” be obtained as a limit of a pure-strategy equilibrium point in the corresponding disturbed gameΓ ^* when all disturbances go to zero. Accordingly, mixed-strategy equilibrium points are stable — even though the players may make no deliberate effort to use their pure strategies with the probability weights prescribed by their mixed equilibrium strategies — because the random fluctuations in their payoffs willmake them use their pure strategies approximately with the prescribed probabilities.     

Timing of messages and the Aumann conjecture: a multiple-selves approach

The Aumann (In: Gabszewicz JJ, Richard JF, Wolsey L (eds) Economic decision making: games, econometrics and optimisation, 1990) conjecture states that cheap-talk messages do not necessarily help to coordinate on efficient Nash equilibria. In an experimental test of Aumann’s conjecture, Charness (Games Econ Behav 33(2):177–194, 2000) found that cheap-talk messages facilitate coordination when they precede the action, but not when they follow the action. Standard game-theoretical modeling abstracts from this timing effect, and therefore cannot account for it. To allow for a formal analysis of the timing effect, I study the sequential equilibria of the signaling game in which the sender is modeled as comprising two selves: an acting self and a signaling self. I interpret Aumann’s argument in this context to imply that all of the equilibria in this game are ‘babbling’ equilibria, in which the message conveys no information and does not affect the behavior of the receiver. Using this framework, I show that a fully communicative equilibrium exists—only if the message precedes the action but not when the message follows the action. In the latter case, no information is transmitted in any equilibrium. This result provides a game-theoretical explanation for the puzzling experimental results obtained by Charness (2000). I discuss other explanations for this timing-of-message effect and their relationship to the current analysis.     

n人可信策略博弈

本文研究模糊支付n人策略博弈,由于支付信息的不完全性,模糊支付可视为模糊变量。基于可信性理论,在不同的决策环境中引入模糊排序方法表征支付者行为。因此,本文定义四种可信均衡,等价于纳什均衡。其次证明了可信均衡存在性定理。除此之外,在现实策略博弈中用算例说明四种可信均衡的现实意义。最后讨论四种可信均衡之间可能存在的关系。     

A link between sequential semi-anonymous nonatomic games and their large finite counterparts

We show that obtainable equilibria of a multi-period nonatomic game can be used by players in its large finite counterparts to achieve near-equilibrium payoffs. Such equilibria in the form of random state-to-action rules are parsimonious in form and easy to execute, as they are both oblivious of past history and blind to other players’ present states. Our transient results can be extended to a stationary case, where the finite multi-period games are special discounted stochastic games. In both nonatomic and finite games, players’ states influence their payoffs along with actions they take; also, the random evolution of one particular player’s state is driven by all players’ states as well as actions. The finite games can model diverse situations such as dynamic price competition. But they are notoriously difficult to analyze. Our results thus suggest ways to tackle these problems approximately.     

Redefinition of Belief Distorted Nash Equilibria for the Environment of Dynamic Games with Probabilistic Beliefs

In this paper, a new concept of equilibrium in dynamic games with incomplete or distorted information is introduced. In the games considered, players have incomplete information about crucial aspects of the game and formulate beliefs about the probabilities of various future scenarios. The concept of belief distorted Nash equilibrium combines optimization based on given beliefs and self-verification of those beliefs. Existence and equivalence theorems are proven, and this concept is compared to existing ones. Theoretical results are illustrated using several examples: extracting a common renewable resource, a large minority game, and a repeated Prisoner’s Dilemma.     

On Intrinsic Complexity of Nash Equilibrium Problems and Bilevel Optimization

In this article we study generalized Nash equilibrium problems (GNEP) and bilevel optimization side by side. This perspective comes from the crucial fact that both problems heavily depend on parametric issues. Observing the intrinsic complexity of GNEP and bilevel optimization, we emphasize that it originates from unavoidable degeneracies occurring in parametric optimization. Under intrinsic complexity, we understand the involved geometrical complexity of Nash equilibria and bilevel feasible sets, such as the appearance of kinks and boundary points, non-closedness, discontinuity and bifurcation effects. The main goal is to illustrate the complexity of those problems originating from parametric optimization and singularity theory. By taking the study of singularities in parametric optimization into account, the structural analysis of Nash equilibria and bilevel feasible sets is performed. For GNEPs, the number of players’ common constraints becomes crucial. In fact, for GNEPs without common constraints and for classical NEPs we show that—generically—all Nash equilibria are jointly nondegenerate Karush–Kuhn–Tucker points. Consequently, they are isolated. However, in presence of common constraints Nash equilibria will constitute a higher dimensional set. In bilevel optimization, we describe the global structure of the bilevel feasible set in case of a one-dimensional leader’s variable. We point out that the typical discontinuities of the leader’s objective function will be caused by follower’s singularities. The latter phenomenon occurs independently of the viewpoint of the optimistic or pessimistic approach. In case of higher dimensions, optimistic and pessimistic approaches are discussed with respect to possible bifurcation of the follower’s solutions.     

Non‐explanatory equilibria: An extremely simple game with (mostly) unattainable fixed points

Equilibrium analysis pervades mathematical social science. This paper calls into question the explanatory significance of equilibrium by offering an extremely simple game, most of whose equilibria are unattainable in principle from any of its initial conditions. Moreover, the number of computation steps required to reach those (few) equilibria that are attainable is shown to grow exponentially with the number of players—making long‐run equilibrium a poor predictor of the game's observed state. The paper also poses a number of combinatorially challenging problems raised by the game. © 2002 Wiley Periodicals, Inc.     

On participation games with complete information

We analyze a class of two-candidate voter participation games under complete information that encompasses as special cases certain public good provision games. We characterize the Nash equilibria of these games as stationary points of a non-linear programming problem, the objective function of which is a Morse function (onethat does not admit degenerate critical points) for almost all costs of participation. We use this fact to establish that, outside a closed set of measure zero of participation costs, all equilibria of these games are regular (an alternative to the result of De Sinopoli and Iannantuoni in Econ Theory 25(2):477–486, 2005). One consequence of regularity is that the equilibria of these games are robust to the introduction of (mild) incomplete information. Finally, we establish the existence of monotone Nash equilibria, such that players with higher participation cost abstain with (weakly) higher probability.      

Correlated equilibria in repeated games with lack of information on one side: A model with verifiable types

Games with lack of information on one side are considered where the uncertainty of the uniformed player concerns the (verifiable) identity of his opponent. Two solution concepts are compared: the correlated equilibrium and the noisy channel equilibrium. The analysis shows in particular that correlated equilibria behave differently in the model with verifiable types and in the one with unverifiable types.     

Terrorists’ Eradication Versus Perpetual Terror War

We study an infinite-horizon sequential dynamic game where the players are a government and an international terrorist organization. We provide conditions for the existence of equilibria in which the terrorists’ resources are totally destroyed by a government’s strike. Specifically, we study strong eradication equilibria in which the government’s strike annihilates the terrorists’ resources, preventing the terrorists from acting. We also pay attention to weak eradication equilibria in which the terrorists’ resources are destroyed but in which the initial value of the terrorists’ strike is nevertheless positive. We also show the existence of an equilibrium in which war is perpetual between the government and the terrorists. Perpetual war can only coexist with weak eradication equilibria. For these cases, we provide conditions under which the government would be better off in a weak eradication equilibrium.     

Limiting distributions of the number of pure strategy Nash equilibria in n-person games

We study the number of pure strategy Nash equilibria in a “random” n-person non-cooperative game in which all players have a countable number of strategies. We consider both the cases where all players have strictly and weakly ordinal preferences over their outcomes. For both cases, we show that the distribution of the number of pure strategy Nash equilibria approaches the Poisson distribution with mean 1 as the numbers of strategies of two or more players go to infinity. We also find, for each case, the distribution of the number of pure strategy Nash equilibria when the number of strategies of one player goes to infinity, while those of the other players remain finite.     

COMPETITION AND COOPERATION IN A DYNAMICAL MODEL OF NATURAL RESOURCES

Abstract In this paper, we propose a model describing the commercial exploitation of a common renewable resource by a population of strategically interacting agents. Players can cooperate or compete; cooperators maximize the payoff of their group while defectors maximize their own profit. The partition of the players into two groups, defectors and cooperators, results from the players' choices, so it is not predetermined. This partition is decided as a Nash equilibrium of a static game. It is shown that different types of players can exist in an equilibrium; more precisely, depending on the parameter values such as resource stock, cost, and so on, there might be equilibria only with defectors, cooperators, or with a combination of cooperators and defectors. In any case the total harvest depends on the renewable resource stock, so it influences agents' positions. It is assumed that at each time period the agents harvest according to Nash equilibrium, which can be combined with a dynamic model describing the evolution of fish population. A complete analysis of the equilibria is presented and their stability is analysed. The effect of the different Nash equilibria on the stability of the fish stock, showing that full cooperation is the most stable case, is examined.     

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium. Dedicated to the memory of Professor K G Ramanathan