Min-Max Spaces and Complexity Reduction in Min-Max Expansions

Idempotent methods have been found to be extremely helpful in the numerical solution of certain classes of nonlinear control problems. In those methods, one uses the fact that the value function lies in the space of semiconvex functions (in the case of maximizing controllers), and approximates this value using a truncated max-plus basis expansion. In some classes, the value function is actually convex, and then one specifically approximates with suprema (i.e., max-plus sums) of affine functions. Note that the space of convex functions is a max-plus linear space, or moduloid. In extending those concepts to game problems, one finds a different function space, and different algebra, to be appropriate. Here we consider functions which may be represented using infima (i.e., min-max sums) of max-plus affine functions. It is natural to refer to the class of functions so represented as the min-max linear space (or moduloid) of max-plus hypo-convex functions. We examine this space, the associated notion of duality and min-max basis expansions. In using these methods for solution of control problems, and now games, a critical step is complexity-reduction. In particular, one needs to find reduced-complexity expansions which approximate the function as well as possible. We obtain a solution to this complexity-reduction problem in the case of min-max expansions.     

Generalising diagonal strict concavity property for uniqueness of Nash equilibrium

In this paper, we extend the notion of diagonally strictly concave functions and use it to provide a sufficient condition for uniqueness of Nash equilibrium in some concave games. We then provide an alternative proof of the existence and uniqueness of Nash equilibrium for a network resource allocation game arising from the so-called Kelly mechanism by verifying the new sufficient condition. We then establish that the equilibrium resulting from the differential pricing in the Kelly mechanism is related to a normalised Nash equilibrium of a game with coupled strategy space.     

Differential games with fixed terminal time and estimation of the instability degree of sets in these games

This paper contributes to the theory of differential games. A game problem of bringing a conflict-controlled system to a compact target set is analyzed. Sets in the position space that terminate on the target set and are not stable bridges are considered. The notion of stability defect of these sets is examined. It is demonstrated how the notion of stability defect can be used to construct sets with relatively good geometry that are at the same time convenient for the first player to play the game successfully.     

Values and semivalues on subspaces of finite games

It is proved that every value or semivalue on a linear symmetric subspace of finite games is the restriction to this subspace of a semivalue on the space of all finite games.The theorem is proved for the space of all finite games on a fixed finite set of players, and for the space of all games with a finite support on an infinite set of players (the universe of players).     

Solution concepts in two-person multicriteria games

In this paper, we propose new solution concepts for multicriteria games and compare them with existing ones. The general setting is that of two-person finite games in normal form (matrix games) with pure and mixed strategy sets for the players. The notions of efficiency (Pareto optimality), security levels, and response strategies have all been used in defining solutions ranging from equilibrium points to Pareto saddle points. Methods for obtaining strategies that yield Pareto security levels to the players or Pareto saddle points to the game, when they exist, are presented. Finally, we study games with more than two qualitative outcomes such as combat games. Using the notion of guaranteed outcomes, we obtain saddle-point solutions in mixed strategies for a number of cases. Examples illustrating the concepts, methods, and solutions are included.     

Values of games with denumerably many players

In this paper axioms for values of games with denumerably many players are introduced and, on a certain space of games, a value is defined as a limit of values of finite games. Further, some relationships between the value that the topology on the space of games of bounded variation are investigated. It is also shown and the regular weighted majority games are members of the space on which the value is defined.     

Semivalues as power indices

A restricted notion of semivalue as a power index, i.e. as a value on the lattice of simple games, is axiomatically introduced by using the symmetry, positivity and dummy player standard properties together with the transfer property. The main theorem, that parallels the existing statement for semivalues on general cooperative games, provides a combinatorial definition of each semivalue on simple games in terms of weighting coefficients, and shows the crucial role of the transfer property in this class of games. A similar characterization is also given that refers to unanimity coefficients, which describe the action of the semivalue on unanimity games. We then combine the notion of induced semivalue on lower cardinalities with regularity and obtain a series of characteristic properties of regular semivalues on simple games, that concern null and nonnull players, subgames, quotients, and weighted majority games.     

Total Reward Stochastic Games and Sensitive Average Reward Strategies

In this paper, total reward stochastic games are surveyed. Total reward games are motivated as a refinement of average reward games. The total reward is defined as the limiting average of the partial sums of the stream of payoffs. It is shown that total reward games with finite state space are strategically equivalent to a class of average reward games with an infinite countable state space. The role of stationary strategies in total reward games is investigated in detail. Further, it is outlined that, for total reward games with average reward value 0 and where additionally both players possess average reward optimal stationary strategies, it holds that the total reward value exists.     

Separable and low-rank continuous games

In this paper, we study nonzero-sum separable games, which are continuous games whose payoffs take a sum-of-products form. Included in this subclass are all finite games and polynomial games. We investigate the structure of equilibria in separable games. We show that these games admit finitely supported Nash equilibria. Motivated by the bounds on the supports of mixed equilibria in two-player finite games in terms of the ranks of the payoff matrices, we define the notion of the rank of an n-player continuous game and use this to provide bounds on the cardinality of the support of equilibrium strategies. We present a general characterization theorem that states that a continuous game has finite rank if and only if it is separable. Using our rank results, we present an efficient algorithm for computing approximate equilibria of two-player separable games with fixed strategy spaces in time polynomial in the rank of the game. This research was funded in part by National Science Foundation grants DMI-0545910 and ECCS-0621922 and AFOSR MURI subaward 2003-07688-1.     

Existence of nash equilibria for constrained stochastic games

In this paper, we consider constrained noncooperative N-person stochastic games with discounted cost criteria. The state space is assumed to be countable and the action sets are compact metric spaces. We present three main results. The first concerns the sensitivity or approximation of constrained games. The second shows the existence of Nash equilibria for constrained games with a finite state space (and compact actions space), and, finally, in the third one we extend that existence result to a class of constrained games which can be “approximated” by constrained games with finitely many states and compact action spaces. Our results are illustrated with two examples on queueing systems, which clearly show some important differences between constrained and unconstrained games.Mathematics Subject Classification (2000): Primary: 91A15. 91A10; Secondary: 90C40     

From winning strategy to Nash equilibrium

Game theory is usually considered applied mathematics, but a few game‐theoretic results, such as Borel determinacy, were developed by mathematicians for mathematics in a broad sense. These results usually state determinacy, i.e., the existence of a winning strategy in games that involve two players and two outcomes saying who wins. In a multi‐outcome setting, the notion of winning strategy is irrelevant yet usually replaced faithfully with the notion of (pure) Nash equilibrium. This article shows that every determinacy result over an arbitrary game structure, e.g., a tree, is transferable into existence of multi‐outcome (pure) Nash equilibrium over the same game structure. The equilibrium‐transfer theorem requires cardinal or order‐theoretic conditions on the strategy sets and the preferences, respectively, whereas counter‐examples show that every requirement is relevant, albeit possibly improvable. When the outcomes are finitely many, the proof provides an algorithm computing a Nash equilibrium without significant complexity loss compared to the two‐outcome case. As examples of application, this article generalises Borel determinacy, positional determinacy of parity games, and finite‐memory determinacy of Muller games.     

On the Structural Stability of Values for Cooperative Games

It is generally assumed that any set of players can form a feasible coalition for classical cooperative games. But, in fact, some players may withdraw from the current game and form a union, if this makes them better paid than proposed. Based on the principle of coalition split, this paper presents an endogenous procedure of coalition formation by levels and bargaining for payoffs simultaneously, where the unions formed in the previous step continue to negotiate with others in the next step as “individuals,” looking for maximum share of surplus by organizing themselves as a partition. The structural stability of the induced payoff configuration is discussed, using two stability criteria of core notion for cooperative games and strong equilibrium notion for noncooperative games.

     

Cooperative games with coalition structures

Many game-theoretic solution notions have been defined or can be defined not only with reference to the all-player coalition, but also with reference to an arbitrary coalition structure. In this paper, theorems are established that connect a given solution notion, defined for a coalition structure ? with the same solution notion applied to appropriately defined games on each of the coalitions in ?. This is done for the kernel, nucleolus, bargaining set, value, core, and thevon Neumann-Morgenstern solution. It turns out that there is a single function that plays the central role in five out of the six solution notions in question, though each of these five notions is entirely different. This is an unusual instance of a game theoretic phenomenon that does not depend on a particular solution notion but holds across a wide class of such notions.     

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.     

Oddness of the number of equilibrium points: A new proof

A new proof is offered for the theorem that, in “almost all” finite games, the number of equilibrium points isfinite andodd. The proof is based on constructing a one-parameter family of games with logarithmic payoff functions, and studying the topological properties of the graph of a certain algebraic function, related to the graph of the set of equilibrium points for the games belonging to this family. In the last section of the paper, it is shown that, in the space of all games of a given size, those “exceptional” games which fail to satisfy the theorem (by having an even number or an infinity of equilibrium points) is a closed set of measure zero.     

Existence of Value and Saddle Point in Infinite-Dimensional Differential Games

We study two-player zero-sum differential games of finite duration in a Hilbert space. Following the Berkovitz notion of strategies, we prove the existence of value and saddle-point equilibrium. We characterize the value as the unique viscosity solution of the associated Hamilton–Jacobi–Isaacs equation using dynamic programming inequalities.     

Size direction games over the real line. II

Variants of two basic infinite games of perfect information are studied. A notion of continuous strategy for the playerS (Size) is shown to be related to a notion of convergence norm for sequences of reals. With each such norm, a variant of each of the basic games is associated in which the size player has to see that each play obeys the norm. Restriction to choose only rational numbers is also imposed onS. Some games are completely solved, and in this caseS has a winning strategy iff his set includes a perfect subset, andD has a winning strategy iffS's set is at most denumerable. Some other games, in whichS has to choose only rationals and obey a norm, induce a hierarchy structure on the class of nowhere dense perfect sets, that is embedded cofinally in the lattice of infinite sequences of integers modulo finite differences.     

Phenomena in Inverse Stackelberg Games,Part 1: Static Problems

Games are considered in which the role of the players is a hierarchical one. Some players behave as leaders, others as followers. Such games are named after Stackelberg. In the current paper, a special type of these games is considered, known in the literature as inverse Stackelberg games. In such games, the leader (or: leaders) announces his strategy as a mapping from the follower (or: followers) decision space into his own decision space. Arguments for studying such problems are given. The routine way of analysis, leading to a study of composed functions, is not very fruitful. Other approaches are given, mainly by studying specific examples. Phenomena in problems with more than one leader and/or follower are studied within the context of the inverse Stackelberg concept. As a side issue, expressions like “two captains on a ship” and “divide and conquer” are given a mathematical foundation.