Interactive decisions and potential games

The aim of this contribution is an overview on Potential Games. This class of games is special, in fact we can investigate their properties by a unique function: the potential function. We consider several types of potential games: exact, ordinal, bayesian and hierarchical. Some results are generalized to multicriteria decisions.      

On ordinal equivalence of the Shapley and Banzhaf values for cooperative games

In this paper I consider the ordinal equivalence of the Shapley and Banzhaf values for TU cooperative games, i.e., cooperative games for which the preorderings on the set of players induced by these two values coincide. To this end I consider several solution concepts within semivalues and introduce three subclasses of games which are called, respectively, weakly complete, semicoherent and coherent cooperative games. A characterization theorem in terms of the ordinal equivalence of some semivalues is given for each of these three classes of cooperative games. In particular, the Shapley and Banzhaf values as well as the segment of semivalues they limit are ordinally equivalent for weakly complete, semicoherent and coherent cooperative games.     

Probabilities of Pure Nash Equilibria in Matrix Games when the Payoff Entries of One Player Are Randomly Selected

The Nash equilibrium in pure strategies represents an important solution concept in nonzero sum matrix games. Existence of Nash equilibria in games with known and with randomly selected payoff entries have been studied extensively. In many real games, however, a player may know his own payoff entries but not the payoff entries of the other player. In this paper, we consider nonzero sum matrix games where the payoff entries of one player are known, but the payoff entries of the other player are assumed to be randomly selected. We are interested in determining the probabilities of existence of pure Nash equilibria in such games. We characterize these probabilities by first determining the finite space of ordinal matrix games that corresponds to the infinite space of matrix games with random entries for only one player. We then partition this space into mutually exclusive spaces that correspond to games with no Nash equilibria and with r Nash equilibria. In order to effectively compute the sizes of these spaces, we introduce the concept of top-rated preferences minimal ordinal games. We then present a theorem which provides a mechanism for computing the number of games in each of these mutually exclusive spaces, which then can be used to determine the probabilities. Finally, we summarize the results by deriving the probabilities of existence of unique, nonunique, and no Nash equilibria, and we present an illustrative example.     

A proof that the core of an ordinal convex game is a von Neumann-Morgenstern solution

It is proved that the core of an ordinal convex game is a von Neumann-Morgenstern solution. The proof makes a strong use of reduced games of cooperative games without side payments.     

An ordinal well-posedness property for Nash equilibria

The aim of this article is to give, for Nash equilibria, a well-posedness criterion in the form of an ordinal property. This property is important for games because it captures the case when players' decisions depend on preferences and not on a special choice of a utility function. The ordinal characteristics of this well-posedness criterion comes from considering value-bounded approximate equilibria.     

On the ordinal equivalence of the Johnston, Banzhaf and Shapley power indices

In this paper, we characterize the games in which Johnston, Shapley-Shubik and Penrose-Banzhaf-Coleman indices are ordinally equivalent, meaning that they rank players in the same way. We prove that these three indices are ordinally equivalent in semicomplete simple games, which is a newly defined class that contains complete games and includes most of the real-world examples of binary voting systems. This result constitutes a twofold extension of Diffo Lambo and Moulen’s result (Diffo Lambo and Moulen, 2002) in the sense that ordinal equivalence emerges for three power indices (not just for the Shapley-Shubik and Penrose-Banzhaf-Coleman indices), and it holds for a class of games strictly larger than the class of complete games.     

A cardinal bargaining set for games without side payments

A bargaining set for games without side payments, based on cardinal considerations is introduced. It is proved that it is never empty for a fairly general class of games without side payments, that it coincides with the classical bargaining set if the game has side payments and that it is a subset of an ordinal bargaining set described inAsscher [1975a].     

A note on NTU convexity

For cooperative games with transferable utility, convexity has turned out to be an important and widely applicable concept. Convexity can be defined in a number of ways, each having its own specific attractions. Basically, these definitions fall into two categories, namely those based on a supermodular interpretation and those based on a marginalistic interpretation. For games with nontransferable utility, however, the literature mainly focuses on two kinds of convexity, ordinal and cardinal convexity, which both extend the supermodular interpretation. In this paper, we analyse three types of convexity for NTU games that generalise the marginalistic interpretation of convexity. Received: December 2000     

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.     

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.     

Classification of two-person ordinal bimatrix games

The set of possible outcomes of a strongly ordinal bimatrix games is studied by imbedding each pair of possible payoffs as a point on the standard two-dimensional integral lattice. In particular, we count the number of different Pareto-optimal sets of each cardinality; we establish asymptotic bounds for the number of different convex hulls of the point sets, for the average shape of the set of points dominated by the Pareto-optimal set, and for the average shape of the convex hull of the point set. We also indicate the effect of individual rationality considerations on our results. As most of our results are asymptotic, the appendix includes a careful examination of the important case of 2×2 games.Supported by the Program in Discrete Mathematics and its Applications at Yale and NSF Grant CCR-8901484.     

An application of optimization theory to the study of equilibria for games: a survey

This contribution is a survey about potential games and their applications. In a potential game the information that is sufficient to determine Nash equilibria can be summarized in a single function on the strategy space: the potential function. We show that the potential function enable the application of optimization theory to the study of equilibria. Potential games and their generalizations are presented. Two special classes of games, namely team games and separable games, turn out to be potential games. Several properties satisfied by potential games are discussed and examples from concrete situations as congestion games, global emission games and facility location games are illustrated.     

Ordinal Operations on Surreal Numbers

An open problem posed by John H. Conway in [2] was whether onecould, on his system of numbers and games, ‘... defineoperations of addition and multiplication which will restricton the ordinals to give their usual operations’. Sucha definition for addition was later given in [4], and this paperwill show that a definition also exists for multiplication.An ordinal exponentiation operation is also considered.     

The planning of marketing strategies in consumer credit: an approach based on graphical chain models for ordinal variables

This paper explores the potential of graphical chain models in defining marketing strategies in the consumer credit field. When ordinal variables are involved, the potential can be increased by exploiting the ordinal scale of variables. In the presented research, the effectiveness of ordinal methods is analysed in three important activities for building a score-card: (1) in coarse classifying of variables, (2) in model selection and (3) in measuring the prediction accuracy of the model.     

The structure of utility functions ensuring the existence of an exact potential in a strategic game

Strategic games in which the profit of each participant is the sum of local profits gained by means certain “objects” and shared by all players using these objects are considered. If each object satisfies a regularity condition, then the game has an exact potential. Both universal classes of potential games considered previously in the literature, overflow games and games with structured utility functions, are contained in the class under consideration and satisfy the regularity condition.     

A Shapley value representation of network potentials

We consider network formation games by Jackson and Wolinsky (J Econ Theory 71:44–74, 1996) and characterize the class of games that have a network potential. We show that there exists a network potential if and only if each player’s payoff function can be represented as the Shapley value of a special class of cooperative games indexed by the networks. We also show that a network potential coincides with a potential of the same class of cooperative games.     

When is tit-for-tat unbeatable?

We characterize the class of symmetric two-player games in which tit-for-tat cannot be beaten even by very sophisticated opponents in a repeated game. It turns out to be the class of exact potential games. More generally, there is a class of simple imitation rules that includes tit-for-tat but also imitate-the-best and imitate-if-better. Every decision rule in this class is essentially unbeatable in exact potential games. Our results apply to many interesting games including all symmetric 2 $\times $ 2 games, and standard examples of Cournot duopoly, price competition, public goods games, common pool resource games, and minimum effort coordination games.     

A survey of static and dynamic potential games

Potential games are noncooperative games for which there exist auxiliary functions, called potentials, such that the maximizers of the potential are also Nash equilibria of the corresponding game. Some properties of Nash equilibria, such as existence or stability, can be derived from the potential, whenever it exists. We survey different classes of potential games in the static and dynamic cases, with a finite number of players, as well as in population games where a continuum of players is allowed. Likewise, theoretical concepts and applications are discussed by means of illustrative examples.     

An Approach to Fuzzy Noncooperative Nash Games

Systems that involve more than one decision maker are often optimized using the theory of games. In the traditional game theory, it is assumed that each player has a well-defined quantitative utility function over a set of the player decision space. Each player attempts to maximize/minimize his/her own expected utility and each is assumed to know the extensive game in full. At present, it cannot be claimed that the first assumption has been shown to be true in a wide variety of situations involving complex problems in economics, engineering, social and political sciences due to the difficulty inherent in defining an adequate utility function for each player in these types of problems. On the other hand, in many of such complex problems, each player has a heuristic knowledge of the desires of the other players and a heuristic knowledge of the control choices that they will make in order to meet their ends.In this paper, we utilize fuzzy set theory in order to incorporate the players' heuristic knowledge of decision making into the framework of conventional game theory or ordinal game theory. We define a new approach to N-person static fuzzy noncooperative games and develop a solution concept such as Nash for these types of games. We show that this general formulation of fuzzy noncooperative games can be applied to solve multidecision-making problems where no objective function is specified. The computational procedure is illustrated via application to a multiagent optimization problem dealing with the design and operation of future military operations.