In a system of interdependent users, the security of an entity is affected not only by that user’s investment in security measures, but also by the positive externality of the security decisions of (some of) the other users. The provision of security in such system is therefore modeled as a public good provision problem, and is referred to as a security game. In this paper, we compare two well-known incentive mechanisms in this context for incentivizing optimal security investments among users, namely the Pivotal and the Externality mechanisms. The taxes in a Pivotal mechanism are designed to ensure users’ voluntary participation, while those in an Externality mechanism are devised to maintain a balanced budget. We first show the more general result that, due to the nonexcludable nature of security, no mechanism can incentivize the socially optimal investment profile, while at the same time ensuring voluntary participation and maintaining a balanced budget for all instances of security games. To further illustrate, we apply the Pivotal and Externality mechanisms to the special case of weighted total effort interdependence models, and identify some of the effects of varying interdependency between users on the budget deficit in the Pivotal mechanism, as well as on the participation incentives in the Externality mech
@cite_21 introduces a network model of public goods, and studies different features of its Nash equilibria. This model is equivalent to a total effort game with linear investment costs and a general interdependence graph. The authors show that these games always have a Nash equilibrium; i.e., one in which users are either specialists exerting full effort (equivalent to main investors in our terminology), or free-riders. They show that such equilibria correspond to maximal independent sets of the graph, and that specialized equilibira may lead to higher welfare compared to other (distributed) Nash equilibria. Similarly, @cite_22 studies the Nash equilibrium of a linear quadratic interdependence model, and relates the equilibrium effort levels to the nodes' Bonacich centrality in a suitably defined matrix of local complementarities. The work in @cite_11 generalizes these results by studying existence, uniqueness, and closed form of the Nash equilibrium in a broader class of games for which best-responses are linear in other players' actions. All the aforementioned work focuses on the Nash equilibrium in public good provision environments.
@cite_21 @cite_22 @cite_11
2170451139 2166193992 2059431191
Much of Game Theory, including the Nash equilibrium concept, is based on the assumption that players are expectation maximizers. It is known that if players are risk averse, games may no longer have Nash equilibria ([11,6]. We show that 1. Under risk aversion (convex risk valuations), and for almost all games, there are no mixed Nash equilibria, and thus either there is a pure equilibrium or there are no equilibria at all, and, 2. For a variety of important valuations other than expectation, it is NP-complete to determine if games between such players have a Nash equilibrium. We introduce two new natural decision problems, denoted as ? RATIONAL NASH and ? IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ask, given a strategic game, whether or not it admits (i) a rational Nash equilibrium where all probabilities are rational numbers, and (ii) an irrational Nash equilibrium where at least one probability is irrational, respectively. We are interested here in the complexities of ? RATIONAL NASH and ? IRRATIONAL NASH. Towards this end, we study two other decision problems, denoted as NASH-EQUIVALENCE and NASH-REDUCTION, pertinent to some mutual properties of the sets of Nash equilibria of two given strategic games with the same number of players. The problem NASH-EQUIVALENCE asks whether or not the two sets of Nash equilibria coincide; we identify a restriction of its complementary problem that witnesses ? RATIONAL NASH. The problem NASH-REDUCTION asks whether or not there is a so called Nash reduction: a suitable map between corresponding strategy sets of players that yields a Nash equilibrium of the former game from a Nash equilibrium of the latter game; we identify a restriction of NASH-REDUCTION that witnesses ? IRRATIONAL NASH. As our main result, we provide two distinct reductions to simultaneously show that (i) NASH-EQUIVALENCE is co- @math -hard and ? RATIONAL NASH is @math -hard, and (ii) NASH-REDUCTION and ? IRRATIONAL NASH are both @math -hard, respectively. The reductions significantly extend techniques previously employed by Conitzer and Sandholm (Proceedings of the 18th Joint Conference on Artificial Intelligence, pp. 765---771, 2003; Games Econ. Behav. 6 We consider a finite population simultaneous move game with heterogeneous interaction modes across different pairs of players. We allow for general interaction patterns, but restrict our analysis to games whose pure strategy Nash equilibrium conditions boil down to a set of piece-wise linear conditions, so that an equilibrium is a solution to a linear complementarity problem. We introduce a new class of games for which a suitable linear transformation of the original interaction matrix induces a game with complementarities. We provide general moderation conditions on the interaction matrix such that a game in this class has a unique Nash equilibrium, that we are able to characterize by means of a closed-form expression involving a generalized version of the Katz network measure of node centrality.