A consistent value for games with n players and r alternatives

In Bolger [1993], an efficient value was obtained for a class of games called games with n players and r alternatives. In these games, each of the n players must choose one and only one of the r alternatives. This value can be used to determine a player’s “a priori” value in such a game. In this paper, we show that the value has a consistency property similar to the “consistency” for TU games in Hart/Mas-Colell [1989] and we present a set of axioms (including consistency) which characterizes this value.  The games considered in this paper differ from the multi-choice games considered by Hsiao and Raghavan [1993]. They consider games in which the actions of the players are ordered in the sense that, if i >j, then action i carries more “weight” than action j.  These games also differ from partition function games in that the worth of a coalition depends not only on the partitioning of the players but also on the action chosen by each subset of the partition. Received: April 1994/final version: June 1999     

Conditional Viability for Impulse Differential Games

We introduce in this paper the concept of “impulse evolutionary game”. Examples of evolutionary games are usual differential games, differentiable games with history (path-dependent differential games), mutational differential games, etc. Impulse evolutionary systems and games cover in particular “hybrid systems” as well as “qualitative systems”. The conditional viability kernel of a constrained set (with a target) is the set of initial states such that for all strategies (regarded as continuous feedbacks) played by the second player, there exists a strategy of the first player such that the associated run starting from this initial state satisfies the constraints until it hits the target. This paper characterizes the concept of conditional viability kernel for “qualitative games” and of conditional valuation function for “qualitative games” maximinimizing an intertemporal criterion. The theorems obtained so far about viability/capturability issues for evolutionary systems, conditional viability for differential games and about impulse and hybrid systems are used to provide characterizations of conditional viability under impulse evolutionary games.     

Game theoretical optimization inspired by information theory

Inspired by previous work on information theoretical optimization problems, the basics of an axiomatic theory of certain special two-person zero-sum games is developed. One of the players, “Observer”, is imagined to have a “mind”, the other, “Nature”, not. These ideas lead to un-symmetric modeling as the two players are treated quite differently. Basic concavity- and convexity results as well as a general minimax theorem are derived from the axioms.     

Probabilistic interpretation for systems of Isaacs equations with two reflecting barriers

In this paper we investigate zero-sum two-player stochastic differential games whose cost functionals are given by doubly controlled reflected backward stochastic differential equations (RBSDEs) with two barriers. For admissible controls which can depend on the whole past and so include, in particular, information occurring before the beginning of the game, the games are interpreted as games of the type “admissible strategy” against “admissible control”, and the associated lower and upper value functions are studied. A priori random, they are shown to be deterministic, and it is proved that they are the unique viscosity solutions of the associated upper and the lower Bellman–Isaacs equations with two barriers, respectively. For the proofs we make full use of the penalization method for RBSDEs with one barrier and RBSDEs with two barriers. For this end we also prove new estimates for RBSDEs with two barriers, which are sharper than those in Hamadène, Hassani (Probab Theory Relat Fields 132:237–264, 2005). Furthermore, we show that the viscosity solution of the Isaacs equation with two reflecting barriers not only can be approximated by the viscosity solutions of penalized Isaacs equations with one barrier, but also directly by the viscosity solutions of penalized Isaacs equations without barrier. Partially supported by the NSF of P.R.China (No. 10701050; 10671112), Shandong Province (No. Q2007A04), and National Basic Research Program of China (973 Program) (No. 2007CB814904).     

The unit-level-core for multi-choice games: the replicated core for TU games

This note extends the solution concept of the core for traditional transferable-utility (TU) games to multi-choice TU games, which we name the unit-level-core. It turns out that the unit-level-core of a multi-choice TU game is a “replicated subset” of the core of a corresponding “replicated” TU game. We propose an extension of the theorem of Bondareva (Probl Kybern 10:119–139, 1963) and Shapley (Nav Res Logist Q 14:453–460, 1967) to multi-choice games. Also, we introduce the reduced games for multi-choice TU games and provide an axiomatization of the unit-level-core on multi-choice TU games by means of consistency and its converse.     

Hamilton cycles in highly connected and expanding graphs

In this paper we prove a sufficient condition for the existence of a Hamilton cycle, which is applicable to a wide variety of graphs, including relatively sparse graphs. In contrast to previous criteria, ours is based on two properties only: one requiring expansion of “small” sets, the other ensuring the existence of an edge between any two disjoint “large” sets. We also discuss applications in positional games, random graphs and extremal graph theory.     

More examples of invariance under twisting

The so-called “invariance under twisting” for twisted tensor products of algebras is a result stating that, if we start with a twisted tensor product, under certain circumstances we can “deform” the twisting map and we obtain a new twisted tensor product, isomorphic to the given one. It was proved before that a number of independent and previously unrelated results from Hopf algebra theory are particular cases of this theorem. In this article we show that some more results from literature are particular cases of invariance under twisting, for instance a result of Beattie-Chen-Zhang that implies the Blattner-Montgomery duality theorem.     

Phenomena in Inverse Stackelberg Games,Part 2: Dynamic 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.     

On the existence of a minimum integer representation for?weighted voting systems

A basic problem in the theory of simple games and other fields is to study whether a simple game (Boolean function) is weighted (linearly separable). A second related problem consists in studying whether a weighted game has a minimum integer realization. In this paper we simultaneously analyze both problems by using linear programming. For less than 9 voters, we find that there are 154 weighted games without minimum integer realization, but all of them have minimum normalized realization. Isbell in 1958 was the first to find a weighted game without a minimum normalized realization, he needed to consider 12 voters to construct a game with such a property. The main result of this work proves the existence of weighted games with this property with less than 12 voters. This research was partially supported by Grant MTM 2006-06064 of “Ministerio de Ciencia y Tecnología y el Fondo Europeo de Desarrollo Regional” and SGRC 2005-00651 of “Generalitat de Catalunya”, and by the Spanish “Ministerio de Ciencia y Tecnología” programmes ALINEX (TIN2005-05446 and TIN2006-11345).     

Approximate common knowledge revisited

Suppose we replace “knowledge” by “belief with probability p” in standard definitions of common knowledge. Very different notions arise depending on the exact definition of common knowledge used in the substitution. This paper demonstrates those differences and identifies which notion is relevant in each of three contexts: equilibrium analysis in incomplete information games, best response dynamics in incomplete information games, and agreeing to disagree/no trade results.     

On equilibrium in pure strategies in games with many players

We demonstrate that, if there are sufficiently many players, any Bayesian equilibrium of an incomplete information game can be “ε-purified” . That is, close to any Bayesian equilibrium there is an approximate Bayesian equilibrium in pure strategies. Our main contribution is obtaining this result for games with a countable set of pure strategies. In order to do so we derive a mathematical result, in the spirit of the Shapley–Folkman Theorem, permitting countable strategy sets. Our main assumption is a “large game property,” dictating that the actions of relatively small subsets of players cannot have large affects on the payoffs of other players. E. Cartwright and M. Wooders are indebted to Phillip Reny, Frank Page and two anonymous referees for helpful comments.     

Credible deviations from signaling equilibria

In games with costly signaling, some equilibria are vulnerable to deviations which could be “unambiguously” interpreted as coming from a unique set of Sender-types. This occurs when these types are precisely the ones who gain from deviating for any beliefs the Receiver could form over that set. We show that this idea characterizes a unique equilibrium outcome in two classes of games. First, in monotonic signaling games, only the Riley outcome is immune to this sort of deviation. Our result therefore provides a plausible story behind the selection made by Cho and Kreps’s (Q J Econ 102:179–221, 1987) D1 criterion on this class of games. Second, we examine a version of Crawford and Sobel (Econometrica 50:1431–1451, 1982) model with costly signaling, where standard refinements have no effect. We show that only a Riley-like separating equilibrium is immune to these deviations.     

Central elements in pseudoeffect algebras

We introduce the definition of pseudoorthoalgebras and discuss some relationships between orthomodular lattices and pseudoorthoalgebras. Then we study the conditions that a pseudoeffect algebra is isomorphic to an “internal direct product” of ideals generated by orthogonal principal elements. At last, we give some characterizations of central elements in pseudoeffect algebras.     

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     

An alternative characterization of the weighted Banzhaf value

We provide a new characterization of the weighted Banzhaf value derived from some postulates in a recent paper by Radzik, Nowak and Driessen [7]. Our approach owes much to the work by Lehrer [4] on the classical Banzhaf value based on the idea of amalgamation of pairs of players and an induction construction of the value. Compared with the approach in [7] we consider two new postulates: a weighted version of Lehrer’s “2-efficiency axiom” [4] and a generalized “null player out” property studied in terms of symmetric games by Derks and Haller [2]. Received: December 1997/final version: October 1999     

On duality gap in linear conic problems

In their paper “Duality of linear conic problems” Shapiro and Nemirovski considered two possible properties (A) and (B) for dual linear conic problems (P) and (D). The property (A) is “If either (P) or (D) is feasible, then there is no duality gap between (P) and (D)”, while property (B) is “If both (P) and (D) are feasible, then there is no duality gap between (P) and (D) and the optimal values val(P) and val(D) are finite”. They showed that (A) holds if and only if the cone K is polyhedral, and gave some partial results related to (B). Later Shapiro conjectured that (B) holds if and only if all the nontrivial faces of the cone K are polyhedral. In this note we mainly prove that both the “if” and “only if” parts of this conjecture are not true by providing examples of closed convex cone in \mathbbR⁴{\mathbb{R}^{4}} for which the corresponding implications are not valid. Moreover, we give alternative proofs for the results related to (B) established by Shapiro and Nemirovski.     

Isomorphism of random walks

We show that any two aperiodic, recurrent random walks on the integers whose jump distributions have finite seventh moment, are isomorphic as infinite measure preserving transformations. The method of proof involved uses a notion of equivalence of renewal sequences, and the “relative” isomorphism of Bernoulli shifts respecting a common state lumping with the same conditional entropy. We also prove an analogous result for random walks on the two dimensional integer lattice.     

Saturated models in institutions

Saturated models constitute one of the powerful methods of conventional model theory, with many applications. Here we develop a categorical abstract model theoretic approach to saturated models within the theory of institutions. The most important consequence is that the method of saturated models becomes thus available to a multitude of logical systems from logic or from computing science. In this paper we define the concept of saturated model at an abstract institution-independent level and develop the fundamental existence and uniqueness theorems. As an application we prove a general institution-independent version of the Keisler–Shelah isomorphism theorem “any two elementarily equivalent models have isomorphic ultrapowers” (assuming Generalized Continuum Hypothesis).