Congestion games with failures

We introduce a new class of games, congestion games with failures (CGFs), which allows for resource failures in congestion games. In a CGF, players share a common set of resources (service providers), where each service provider (SP) may fail with some known probability (that may be constant or depend on the congestion on the resource). For reliability reasons, a player may choose a subset of the SPs in order to try and perform his task. The cost of a player for utilizing any SP is a function of the total number of players using this SP. A main feature of this setting is that the cost for a player for successful completion of his task is the minimum of the costs of his successful attempts. We show that although CGFs do not, in general, admit a (generalized ordinal) potential function and the finite improvement property (and thus are not isomorphic to congestion games), they always possess a pure strategy Nash equilibrium. Moreover, every best reply dynamics converges to an equilibrium in any given CGF, and the SPs’ congestion experienced in different equilibria is (almost) unique. Furthermore, we provide an efficient procedure for computing a pure strategy equilibrium in CGFs and show that every best equilibrium (one minimizing the sum of the players’ disutilities) is semi-strong. Finally, for the subclass of symmetric CGFs we give a constructive characterization of best and worst equilibria.     

Nondominated Nash points: application of biobjective mixed integer programming

We study the connection between biobjective mixed integer linear programming and normal form games with two players. We first investigate computing Nash equilibria of normal form games with two players using single-objective mixed integer linear programming. Then, we define the concept of efficient (Pareto optimal) Nash equilibria. This concept is precisely equivalent to the concept of efficient solutions in multi-objective optimization, where the solutions are Nash equilibria. We prove that the set of all points in the payoff (or objective) space of a normal form game with two players corresponding to the utilities of players in an efficient Nash equilibrium, the so-called nondominated Nash points, is finite. We demonstrate that biobjective mixed integer linear programming, where the utility of each player is an objective function, can be used to compute the set of nondominated Nash points. Finally, we illustrate how the nondominated Nash points can be used to determine the disagreement point of a bargaining problem.     

Selection of a correlated equilibrium in Markov stopping games

This paper deals with an extension of the concept of correlated strategies to Markov stopping games. The Nash equilibrium approach to solving nonzero-sum stopping games may give multiple solutions. An arbitrator can suggest to each player the decision to be applied at each stage based on a joint distribution over the players’ decisions according to some optimality criterion. This is a form of equilibrium selection. Examples of correlated equilibria in nonzero-sum games related to the best choice problem are given. Several concepts of criteria for selecting a correlated equilibrium are used.     

A Strong Anti-Folk Theorem

We study the properties of finitely complex, symmetric, globally stable, and semi-perfect equilibria. We show that: (1) If a strategy satisfies these properties then players play a Nash equilibrium of the stage game in every period; (2) The set of finitely complex, symmetric, globally stable, semi-perfect equilibrium payoffs in the repeated game equals the set of Nash equilibria payoffs in the stage game; and (3) A strategy vector satisfies these properties in a Pareto optimal way if and only if players play some Pareto optimal Nash equilibrium of the stage game in every stage. Our second main result is a strong anti-Folk Theorem, since, in contrast to what is described by the Folk Theorem, the set of equilibrium payoffs does not expand when the game is repeated.This paper is a revised version of Chapter 3 of my Ph.D. thesis, which has circulated under the title “An Interpretation of Nash Equilibrium Based on the Notion of Social Institutions”.     

Game theoretic approach for fertilizer application: looking for the propensity to cooperate

This paper continues the research implemented in previous work of (Schreider et al. in Environ. Model. Assess. 15(4):223–238, 2010) where a game theoretic model for optimal fertilizer application in the Hopkins River catchment was formulated, implemented and solved for its optimal strategies. In that work, the authors considered farmers from this catchment as individual players whose objective is to maximize their objective functions which are constituted from two components: economic gain associated with the application of fertilizers which contain phosphorus to the soil and environmental harms associated with this application. The environmental losses are associated with the blue-green algae blooming of the coastal waterways due to phosphorus exported from upstream areas of the catchment. In the previous paper, all agents are considered as rational players and two types of equilibria were considered: fully non-cooperative Nash equilibrium and cooperative Pareto optimum solutions. Among the plethora of Pareto optima, the solution corresponding to the equally weighted individual objective functions were selected. In this paper, the cooperative game approach involving the formation of coalitions and modeling of characteristic value function will be applied and Shapley values for the players obtained. A significant contribution of this approach is the construction of a characteristic function which incorporates both the Nash and Pareto equilibria, showing that it is superadditive. It will be shown that this approach will allow each players to obtain payoffs which strictly dominate their payoffs obtained from their Nash equilibria.     

Pure strategy Nash equilibria and the probabilistic prospects of Stackelberg players

We consider the set of all m×n bimatrix games with ordinal payoffs. We show that on the subset E of such games possessing at least one pure strategy Nash equilibrium, both players prefer the role of leader to that of follower in the corresponding Stackelberg games. This preference is in the sense of first-degree stochastic dominance by leader payoffs of follower payoffs. It follows easily that on the complement of E, the follower’s role is preferred in the same sense. Thus we see a tendency for leadership preference to obtain in the presence of multiple pure strategy Nash equilibria in the underlying game.     

Non-additive anonymous games

This paper introduces a class of non-additive anonymous games where agents are assumed to be uncertain (in the sense of Knight) about opponents’ strategies and about the initial distribution over players’ characteristics in the game. We model uncertainty by non-additive measures or capacities and prove the Cournot–Nash equilibrium existence theorem for this class of games. Equilibrium distribution can be symmetrized under milder conditions than in the case of additive games. In particular, it is not required for the space characteristics to be atomless under capacities. The set-valued map of the Cournot–Nash equilibria is upper-semicontinuous as a function of initial beliefs of the players for non-additive anonymous games.     

Competition Among Conventions

A convention can be seen as a way of resolving a coordination problem. If different conventions exist in various geographical, social or other entities (called &;201C;groups&;201D;) and if there is some mobility between these groups, which conventions, if any, will emerge as the successful ones? A simple evolutionary process is suggested and it is shown that the process converges to a Nash equilibrium for all games satisfying weak acyclity. Further, if the process converges, it converges to an efficient convention for all games in which the Pareto optimal symmetric equilibria are strict. Hence, the paper presents an explanation for the endogenous evolution of efficiency. In contrast to most recent studies in evolutionary game theory, the conclusions do not rely on random &;201C;mutations&;201D;. Instead, the driving force is the tendency of players to have increased interaction with member of their own group (viscosity).     

Optimal strategic reasoning with McNaughton functions

The aim of the paper is to explore strategic reasoning in strategic games of two players with an uncountably infinite space of strategies the payoff of which is given by McNaughton functions—functions on the unit interval which are piecewise linear with integer coefficients. McNaughton functions are of a special interest for approximate reasoning as they correspond to formulas of infinitely valued Lukasiewicz logic. The paper is focused on existence and structure of Nash equilibria and algorithms for their computation. Although the existence of mixed strategy equilibria follows from a general theorem (Glicksberg, 1952) [5], nothing is known about their structure neither the theorem provides any method for computing them. The central problem of the article is to characterize the class of strategic games with McNaughton payoffs which have a finitely supported Nash equilibrium. We give a sufficient condition for finite equilibria and we propose an algorithm for recovering the corresponding equilibrium strategies. Our result easily generalizes to n-player strategic games which don't need to be strictly competitive with a payoff functions represented by piecewise linear functions with real coefficients. Our conjecture is that every game with McNaughton payoff allows for finitely supported equilibrium strategies, however we leave proving/disproving of this conjecture for future investigations.     

Internal correlation in repeated games

This paper characterizes the set of all the Nash equilibrium payoffs in two player repeated games where the signal that the players get after each stage is either trivial (does not reveal any information) or standard (the signal is the pair of actions played). It turns out that if the information is not always trivial then the set of all the Nash equilibrium payoffs coincides with the set of the correlated equilibrium payoffs. In particular, any correlated equilibrium payoff of the one shot game is also a Nash equilibrium payoff of the repeated game.For the proof we develop a scheme by which two players can generate any correlation device, using the signaling structure of the game. We present strategies with which the players internally correlate their actions without the need of an exogenous mediator.     

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.     

On the existence of Nash equilibria in large games

We study the existence of Nash equilibria in games with an infinite number of players. We show that there exists a Nash equilibrium in mixed strategies in all normal form games such that pure strategy sets are compact metric spaces and utility functions are continuous. The player set can be any nonempty set.     

On the existence of almost-pure-strategy Nash equilibrium in <Emphasis Type="Italic">n</Emphasis>-person finite games

This paper gives wide characterization of n-person non-coalitional games with finite players’ strategy spaces and payoff functions having some concavity or convexity properties. The characterization is done in terms of the existence of two-point-strategy Nash equilibria, that is equilibria consisting only of mixed strategies with supports being one or two-point sets of players’ pure strategy spaces. The structure of such simple equilibria is discussed in different cases. The results obtained in the paper can be seen as a discrete counterpart of Glicksberg’s theorem and other known results about the existence of pure (or “almost pure”) Nash equilibria in continuous concave (convex) games with compact convex spaces of players’ pure strategies.     

Robust equilibria in location games

In the framework of spatial competition, two or more players strategically choose a location in order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A profile of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which differ only by the consumers’ perceptions of distances. For a finite number of players and any distribution of consumers, we provide a complete characterization of robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal differentiation and inefficiency are robust phenomena. Thereby, we find strong support for an old conjecture that in equilibrium firms form local clusters.     

Nash equilibrium based fairness

There are several approaches of sharing resources among users. There is a noncooperative approach wherein each user strives to maximize its own utility. The most common optimality notion is then the Nash equilibrium. Nash equilibria are generally Pareto inefficient. On the other hand, we consider a Nash equilibrium to be fair as it is defined in a context of fair competition without coalitions (such as cartels and syndicates). We show a general framework of systems wherein there exists a Pareto optimal allocation that is Pareto superior to an inefficient Nash equilibrium. We consider this Pareto optimum to be ??Nash equilibrium based fair.?? We further define a ??Nash proportionately fair?? Pareto optimum. We then provide conditions for the existence of a Pareto-optimal allocation that is, truly or most closely, proportional to a Nash equilibrium. As examples that fit in the above framework, we consider noncooperative flow-control problems in communication networks, for which we show the conditions on the existence of Nash-proportionately fair Pareto optimal allocations.     

Some remarks on the folk theorem in game theory

It is argued that although the pathological multiplicity of Nash equilibria of super games stated by the folk theorem can be removed by introducing limited observations into super games with a continuum of players, the consideration of super games in terms of the Nash equilibrium concept involves a more fundamental and conceptual difficulty.     

Algorithms and the calculation of Nash equilibria for multi-objective control of time-discrete systems and polynomial-time algorithms for dynamic c-games on networks

We consider a multi-objective control problem of time-discrete systems with given starting and final states. The dynamics of the system are controlled by p actors (players). Each of the players intends to minimize his own integral-time cost of the system’s transitions using a certain admissible trajectory. Nash Equilibria conditions are derived and algorithms for solving dynamic games in positional form are proposed in this paper. The existence theorem for Nash equilibria is related to the introduction of an auxiliary dynamic c-game. Stationary and non-stationary cases are described. The paper concludes with a complexity analysis for that decision process.     

A unifying approach to existence of nash equilibria

An approach initiated in [4] is shown to unify results about the existence of (i) Nash equilibria in games with at most countably many players, (ii) Cournot-Nash equilibrium distributions for large, anonymous games, and (iii) Nash equilibria (both mixed and pure) for continuum games. A new, central notion ofmixed externality is developed for this purpose.