Informational structure for differential games

A positional approach for the definition of information structure in differential games is considered. A generalization ofKuhn's theorem [1953] concerning pure strategy equivalence for finite positional games is proved.     

On the existence of uncountably many matroidal families

A matroidal family is a set $\text{F}$ ≠ ? of connected finite graphs such that for every finite graph G the edge-sets of those subgraphs of G which are isomorphic to some element of $\text{F}$ are the circuits of a matroid on the edge-set of G. Simões-Pereira [5] shows the existence of four matroidal families and Andreae [1] shows the existence of a countably infinite series of matroidal families. In this paper we show that there exist uncountably many matroidal families. This is done by using an extension of Andreae's theorem, a construction theorem, and certain properties of regular graphs. Moreover we observe that all matroidal families so far known can be obtained in a unified way.     

A new index of power for simplen-person games

Measures of (a priori) power play a useful role in assessing the character of interpersonal interaction found in collective decision making bodies. We propose and axiomatically characterize an alternative power index to the familiarShapley/Shubik andBanzhaf indices which can be used for such purposes. The index presented is shown to be unique for the class of simplen-person games. By subsequent generalization of the index and its axioms to the class ofn-person games in characteristic function form we obtain an analog to theShapley value.     

Generalizedk-quota solutions for (N,k) games

A generalization of quota solutions presented byShapley [1953] andKalisch [1959] is investigated for some classes ofn-person games. A new type of solution is obtained for symmetric games as a consequence.     

ψ-Stability of a cooperative game without side payments

In the present paper we defineψ-stability for theAumann-Peleg theory of cooperative games without side payments, and we prove some theorems which are analogous to the core theorem byAumann andBurger. These theorems provide foundations of the theory ofψ-stability for cooperative games without side payments in addition to being of interest for their own sake. We also consider the composition of two admissible functionsψ ₁ andψ ₂.     

Multigraded shifts of matroidal ideals

In this paper, we show that if I is a matroidal ideal, then the ideal generated by the i-th multigraded shifts is also a matroidal ideal for every \(i=0,\ldots ,{\text {proj dim}}(I)\).     

Heights of simple games

We consider simple games which are constructed as iterated weighted majority games. It turns out that every proper simple game can be obtained in this way. The minimal number of iterations necessary to obtain a given game is called the height of this game. We investigate the behaviour ofh (n), the maximal height of a simple game withn players.     

Applications of game theory to threshold logic

Recently,Owen demonstrated an isomorphism between characteristic function games and pseudo-Boolean functions. When a game is interpreted as a function on a lattice, then properties of pseudo-Boolean inequalities can be related to partitions of the lattice. The isomorphism also has important implications for threshold logic. In particular, by using a special reflection map, unate switching functions can be studied via monotone simple games. We can show that every unate switching function can be written as the join threshold functions. Also, using the ideas ofCharnes, Kortanek andKeene, we can give several ways to calculate approximate threshold inequalities for unate switching functions.     

Simple games and weighted games: A theoretical and computational viewpoint

It is a well-known result in the theory of simple games that a game is weighted if and only if it is trade robust. In this paper we propose a variant of trade robustness, that we call invariant-trade robustness, which is enough to determine whether a simple game is weighted. To test whether a simple game is invariant-trade robust we do not need to consider all winning coalitions; a reduced subset of minimal winning coalitions is enough.We make a comparison between the two methods (trade robustness and invariant-trade robustness) to check whether a simple game is weighted. We also provide by means of algorithms a full classification using both methods, for simple games with less than 8 voters according to the maximum level of (invariant-)trade robustness they achieve.     

On the uniqueness of the Shapley value

L.S. Shapley [1953] showed that there is a unique value defined on the classD of all superadditive cooperative games in characteristic function form (over a finite player setN) which satisfies certain intuitively plausible axioms. Moreover, he raised the question whether an axiomatic foundation could be obtained for a value (not necessarily theShapley value) in the context of the subclassC (respectivelyC′, C″) of simple (respectively simple monotonic, simple superadditive) gamesalone. This paper shows that it is possible to do this. Theorem I gives a new simple proof ofShapley's theorem for the classG ofall games (not necessarily superadditive) overN. The proof contains a procedure for showing that the axioms also uniquely specify theShapley value when they are restricted to certain subclasses ofG, e.g.,C. In addition it provides insight intoShapley's theorem forD itself. Restricted toC′ orC″, Shapley's axioms donot specify a unique value. However it is shown in theorem II that, with a reasonable variant of one of his axioms, a unique value is obtained and, fortunately, it is just theShapley value again.     

A note on a generalization of the nucleolus to games without sidepayments

We present a generalization of the nucleolus to games without sidepayments. By allowing the interpersonal utility comparison such that payoffs are determined proportionally to given weights, we define an excess of a coalition as a number depending on this vector of weights. The existence and the inclusion in nonempty cores are proved, but the uniqueness is not preserved. It is also remarked that the excess defined here is not the same as that ofKalai [1975]     

Economical tight examples for the biased Erd?s-Selfridge theorem

A positional game is essentially a generalization of tic-tac-toe played on a hypergraph (V,F). A pivotal result in the study of positional games is the Erd?s-Selfridge theorem, which gives simple criteria for the existence of a Breaker's winning strategy on a hypergraph F. It has been shown that the Erd?s-Selfridge theorem can be tight and that numerous extremal systems exist for that theorem. We focus on a generalization of the Erd?s-Selfridge theorem proven by Beck for biased (p:q) games, which we call the (p:q)-Erd?s-Selfridge theorem. We show that for pn-uniform hypergraphs there is a unique extremal system for the (p:q)-Erd?s-Selfridge theorem (q?2) when Maker must win in exactly n turns (i.e., as quickly as possible).     

k-convexn-person games and their cores

For any natural numbersk andn, the subclass ofk-convexn-person games is introduced. In casek=n, the subclass consists of the convexn-person games. Ak-convexn-person game is characterized in several ways in terms of the core and certain marginal worth vectors. The marginal worth vectors of a game are described in terms of an upper bound for the core and the corresponding gap function. It is shown that thek-convexity of ann-person gamev is equivalent to

1. all marginal worth vectors ofv belong to the core ofv; or
2. the core ofv is the convex hull of the set consisting of all marginal worth vectors ofv; or
3. the extreme points of the core ofv are exactly the marginal worth vectors ofv.

Examples ofk-convexn-person games are also treated.     

Solution concepts ofk-convexn-person games

For any positive integersk andn, the subclass ofk-convexn-person games is considered. In casek=n, we are dealing with convexn-person games. Three characterizations ofk-convexn-person games, formulated in terms of the core and certain adapted marginal worth vectors, are given. Further it is shown that fork-convexn-person games the intersection of the (pre)kernel with the core consists of a unique point (namely the nucleolus), but that the (pre)kernel may contain points outside the core. For certain 1-convex and 2-convexn-person games the part of the bargaining set outside the core is even disconnected with the core. The Shapley value of ank-convexn-person game can be expressed in terms of the extreme points of the core and a correction-vector whenever the game satisfies a certain symmetric condition. Finally, theτ-value of ank-convexn-person game is given.     

A formal theory of generalized intermediate syllogisms

In this paper, we continue developing the formal theory of intermediate quantifiers (expressions such as most, few, almost all, a lot of, many, a great deal of, a large part of, a small part of). The theory is a fuzzy-logic formalization of the concept introduced by Peterson in his book. We will syntactically prove that 105 generalized Aristotle's syllogisms introduced in this book are valid in our theory. At the same time, we will also prove that syllogisms listed there as invalid are invalid also in our theory. Therefore, we believe that our theory provides a reasonable mathematical model of the generalized syllogistics.     

A note on polymatrix games

This work is concerned with the class ofn-person games called polymatrix games (Yanovskaya (1968)). The structure of the set of Nash equilibrium points in a polymatrix game is studied and characterizations of these games are given.     

Generalized solution concepts in games with possibly unaware players

Most work in game theory assumes that players are perfect reasoners and have common knowledge of all significant aspects of the game. In earlier work (Halpern and Rêgo 2006, arxiv.org/abs/0704.2014), we proposed a framework for representing and analyzing games with possibly unaware players, and suggested a generalization of Nash equilibrium appropriate for games with unaware players that we called generalized Nash equilibrium. Here, we use this framework to analyze other solution concepts that have been considered in the game-theory literature, with a focus on sequential equilibrium.     

Non-existence of super-additive solutions for 3-person games

The super-additive solution for 2-person Nash bargaining games (with constant threat) was defined axiomatically inPerles/Maschler [1981]. That paper contains also a study of its basic properties. In this paper we show that the axioms are incompatible even for 3-person unanimity games. This raises the problem of finding a satisfactory generalization of this solution concept to multi-person games.     

Modelling of Ring Geometry from von Neumann’s Point of View

The idea to consider different unions of points, lines, planes, etc., is rather old. Many important configurations of such kinds are geometric (or matroidal) lattices. In this work, we study Desargues, Pappus, and Pasch configurations in D-semimodular lattices.