The desirability relation of simple games

We prove some properties of simple games with a complete desirability relation, and investigate the relationships between the desirability of a simple game G and that of some simple games that are derived from G. We also provide an example of a proper simple game that has a complete and acyclic desirability relation but is not a weighted majority game.     

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.     

Weighted and roughly weighted simple games

In this paper we give necessary and sufficient conditions for a simple game to have rough weights. We define two functions f(n) and g(n) that measure the deviation of a simple game from a weighted majority game and roughly weighted majority game, respectively. We formulate known results in terms of lower and upper bounds for these functions and improve those bounds. We also investigate rough weightedness of simple games with a small number of players.     

Atomic weights and the combinatorial game of bipass

We define an all-small ruleset, bipass, within the framework of normal play combinatorial games. A game is played on finite strips of black and white stones. Stones of different colors are swapped provided they do not bypass one of their own kind. We find a simple surjective function from the strips to integer atomic weights (Berlekamp, Conway and Guy 1982) that measures the number of units in all-small games. This result provides explicit winning strategies for many games, and in cases where it does not, it gives narrow bounds for the canonical form game values. We find game values for some parametrized families of games, including an infinite number of strips of value ?, and we prove that the game value ?2 does not appear as a disjunctive sum of bipass. Lastly, we define the notion of atomic weight tameness, and prove that optimal misére play bipass resembles optimal normal play.     

A solitaire game played on 2-colored graphs

We introduce a solitaire game played on a graph. Initially one disk is placed at each vertex, one face green and the other red, oriented with either color facing up. Each move of the game consists of selecting a vertex whose disk shows green, flipping over the disks at neighboring vertices, and deleting the selected vertex. The game is won if all vertices are eliminated. We derive a simple parity-based necessary condition for winnability of a given game instance. By studying graph operations that construct new graphs from old ones, we obtain broad classes of graphs where this condition also suffices, thus characterizing the winnable games on such graphs. Concerning two familiar (but narrow) classes of graphs, we show that for trees a game is winnable if and only if the number of green vertices is odd, and for n-cubes a game is winnable if and only if the number of green vertices is even and not all vertices have the same color. We provide a linear-time algorithm for deciding winnability for games on maximal outerplanar graphs. We reduce the decision problem for winnability of a game on an arbitrary graph G to winnability of games on its blocks, and to winnability on homeomorphic images of G obtained by contracting edges at 2-valent vertices.     

Forms of representation for simple games: Sizes,conversions and equivalences

Simple games are cooperative games in which the benefit that a coalition may have is always binary, i.e., a coalition may either win or loose. This paper surveys different forms of representation of simple games, and those for some of their subfamilies like regular games and weighted games. We analyze the forms of representations that have been proposed in the literature based on different data structures for sets of sets. We provide bounds on the computational resources needed to transform a game from one form of representation to another one. This includes the study of the problem of enumerating the fundamental families of coalitions of a simple game. In particular we prove that several changes of representation that require exponential time can be solved with polynomial-delay and highlight some open problems.     

Binary games in constitutional form and collective choice

In this paper, we define the notion of binary game in constitutional form. For this game, we define a core and give a necessary and sufficient condition for a game to be stable.We define a representation of a collective choice rule by a binary game in constitutional form and characterize those collective choice rules which are representable.We finally introduce the notion of c-social decision function and characterize, as an application of our theorem on stability of binary constitutional games, the collective choice rules which are c-social decision functions.Our representation of a collective choice rule by a binary game in constitutional form is an obvious improvement of the classical representation by a simple game.     

Dimension of complete simple games with minimum

Weighted majority games have the property that players are totally ordered by the desirability relation (introduced by Isbell in [J.R. Isbell, A class of majority games, Quarterly Journal of Mathematics, 7 (1956) 183–187]) because weights induce it. Games for which this relation is total are called complete simple games. Taylor and Zwicker proved in [A.D. Taylor, W.S. Zwicker, Weighted voting, multicameral representation, and power, Games and Economic Behavior 5 (1993) 170–181] that every simple game (or monotonic finite hypergraph) can be represented by an intersection of weighted majority games and consider the dimension of a game as the needed minimum number of them to get it. They provide the existence of non-complete simple games of every dimension and left open the problem for complete simple games.     

Cycle games and cycle cut games

Two players play a game on a connected graphG. Each player in his turn occupies an edge ofG. The player who occupies a set of edges that contains a cycle, before the other does it, wins. This game may end in a draw. We call this game the normal cycle game. We define furthermore three similar games, which are called the misère cycle game, the normal cycle cut game and the misère cycle cut game. We characterize the above four games.     

Matroidal games

The theory ofmatriods consists of generalization of basic notions oflinear algebra likedependence, basis andspan. In this paper we point out that every non-trivial matroid represents a simple game though the converse need not be true. The class of simple games which possess the matroidal structure is designated asmatroidal games. In matroidal games, we have a generalization of the concept of complete exchangeability of players observed in purely size dependent games. Invoking the well developed theory of matroids, we study the combinatorial structure of matroidal games.     

How to play the one-lie Rényi-Ulam game

The one-lie Rényi-Ulam liar game is a two-player perfect information zero-sum game, lasting q rounds, on the set [n]?{1,…,n}. In each round Paul chooses a subset A⊆[n] and Carole either assigns one lie to each element of A or to each element of [n]?A. Paul wins the original (resp. pathological) game if after q rounds there is at most one (resp. at least one) element with one or fewer lies. We exhibit a simple, unified, optimal strategy for Paul to follow in both games, and use this to determine which player can win for all q,n and for both games.     

The τ-value,The core and semiconvex games

Theτ-value for cooperativen-person games is central in this paper. Conditions are given which guarantee that theτ-value lies in the core of the game. A full-dimensional cone of semiconvex games is introduced. This cone contains the cones of convex and exact games and there is a simple formula for theτ-value for such games. The subclass of semiconvex games with constant gap function is characterized in several ways. It turns out to be an (n+1)-dimensional cone and for all games in this cone the Shapley value, the nucleolus and theτ-value coincide.     

A Shared-Constraint Approach to Multi-Leader Multi-Follower Games

Multi-leader multi-follower games are a class of hierarchical games in which a collection of leaders compete in a Nash game constrained by the equilibrium conditions of another Nash game amongst the followers. The resulting equilibrium problem with equilibrium constraints is complicated by nonconvex agent problems and therefore providing tractable conditions for existence of global or even local equilibria has proved challenging. Consequently, much of the extant research on this topic is either model specific or relies on weaker notions of equilibria. We consider a modified formulation in which every leader is cognizant of the equilibrium constraints of all leaders. Equilibria of this modified game contain the equilibria, if any, of the original game. The new formulation has a constraint structure called shared constraints, and our main result shows that if the leader objectives admit a potential function, the global minimizers of the potential function over this shared constraint are equilibria of the modified formulation. We provide another existence result using fixed point theory that does not require potentiality. Additionally, local minima, B-stationary, and strong-stationary points of this minimization problem are shown to be local Nash equilibria, Nash B-stationary, and Nash strong-stationary points of the corresponding multi-leader multi-follower game. We demonstrate the relationship between variational equilibria associated with this modified shared-constraint game and equilibria of the original game from the standpoint of the multiplier sets and show how equilibria of the original formulation may be recovered. We note through several examples that such potential multi-leader multi-follower games capture a breadth of application problems of interest and demonstrate our findings on a multi-leader multi-follower Cournot game.     

On multi-choice TU games arising from replica of economies

In this paper we derive a multi-choice TU game from r-replica of exchange economy with continuous, concave and monetary utility functions, and prove that the cores of the games converge to a subset of the set of Edgeworth equilibria of exchange economy as r approaches to infinity. We prove that the dominance core of each balanced multi-choice TU game, where each player has identical activity level r, coincides with the dominance core of its corresponding r-replica of exchange economy. We also give an extension of the concept of the cover of the game proposed by Shapley and Shubik (J Econ Theory 1: 9-25, 1969) to multi-choice TU games and derive some sufficient conditions for the nonemptyness of the core of multi-choice TU game by using the relationship among replica economies, multi-choice TU games and their covers.     

Homogeneous games as anti step functions

In this paper the class of homogeneousn-person games “without dummies and steps” is characterized by two algebraic axioms. Each of these games induces a natural vector of lengthn, called incidence vector of the game, and vice versa. A geometrical interpretation of incidence vectors allows to construct all of these games and to enumerate them recursively with respect to the number of persons. In addition an algorithm is defined, which maps each directed game to a minimal representation of a homogeneous game. Moreover both games coincide, if the initial game is homogeneous.     

The canonical function game

The canonical function game is a game of length ω ₁ introduced by W. Hugh Woodin which falls inside a class of games known as Neeman games. Using large cardinals, we show that it is possible to force that the game is not determined. We also discuss the relationship between this result and Σ² ₂ absoluteness, cardinality spectra and Π₂ maximality for H(ω ₂) relative to the Continuum Hypothesis.     

Single-suit two-person card play

We consider a two-person constant sum perfect information game, which we call theEnd Play Game, which arises from an abstraction of simple end play positions in card games of the whist family, including bridge. This game was described in 1929 by Emanuel Lasker, the mathematician and world chess champion, who called itwhistette. The game uses a deck of cards that consists of a single totally ordered suit of 2n cards. To begin play the deck is divided into two handsA andB ofn cards each, held by players Left and Right, and one player is designated as having thelead. The player on lead chooses one of his cards, and the other player after seeing this card selects one of his own to play. The player with the higher card wins a “trick” and obtains the lead. The cards in the trick are removed from each hand, and play then continues until all cards are exhausted. Each player strives to maximize his trick total, and thevalue of the game to each player is the number of tricks he takes. Despite its simple appearance, this game is quite complicated, and finding an optimal strategy seems difficult. This paper derives basic properties of the game, gives some criteria under which one hand is guaranteed to be better than another, and determines the optimal strategies and value functions for the game in several special cases.     

N-person Nim andn-person Moore's Games

We present one way of definingn-person perfect information games so that there is a reasonable outcome for every game. In particular, the theory of Nim and Moore's games is generalized ton-person games.     

A convex representation of totally balanced games

We analyze the least increment function, a convex function of n variables associated to an n-person cooperative game. Another convex representation of cooperative games, the indirect function, has previously been studied. At every point the least increment function is greater than or equal to the indirect function, and both functions coincide in the case of convex games, but an example shows that they do not necessarily coincide if the game is totally balanced but not convex. We prove that the least increment function of a game contains all the information of the game if and only if the game is totally balanced. We also give necessary and sufficient conditions for a function to be the least increment function of a game as well as an expression for the core of a game in terms of its least increment function.     

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.