Representation of finite games as network congestion games

Weighted network congestion games are a natural model for interactions involving finitely many non-identical users of network resources, such as road segments or communication links. However, in spite of their special form, these games are not fundamentally special: every finite game can be represented as a weighted network congestion game. The same is true for the class of (unweighted) network congestion games with player-specific costs, in which the players differ in their cost functions rather than their weights. The intersection of the two classes consists of the unweighted network congestion games. These games are special: a finite game can be represented in this form if and only if it is an exact potential game.     

A link between sequential semi-anonymous nonatomic games and their large finite counterparts

We show that obtainable equilibria of a multi-period nonatomic game can be used by players in its large finite counterparts to achieve near-equilibrium payoffs. Such equilibria in the form of random state-to-action rules are parsimonious in form and easy to execute, as they are both oblivious of past history and blind to other players’ present states. Our transient results can be extended to a stationary case, where the finite multi-period games are special discounted stochastic games. In both nonatomic and finite games, players’ states influence their payoffs along with actions they take; also, the random evolution of one particular player’s state is driven by all players’ states as well as actions. The finite games can model diverse situations such as dynamic price competition. But they are notoriously difficult to analyze. Our results thus suggest ways to tackle these problems approximately.     

On equilibria in finite games

We are concerned with Nash equilibrium points forn-person games. It is proved that, given any real algebraic numberα, there exists a 3-person game with rational data which has a unique equilibrium point andα is the equilibrium payoff for some player. We also present a method which allows us to reduce an arbitraryn-person game to a 3-person one, so that a number of questions about generaln-person games can be reduced to consideration of the special 3-person case. Finally, a completely mixed game, where the equilibrium set is a manifold of dimension one, is constructed.     

Infinite games on finite sets

We study a family of infinite games with imperfect information introduced by B. Model for two players that alternately remove and add points to a finite set. We investigate the existence of imperfect information strategies for the remover for different ambient cardinalities. We also study a variant of a game of D. Gale introduced by Scheepers and Weiss. Work supported by the Ben-Gurion University Center for Advanced Studies in Mathematics.     

Stable cores of large games

We give general conditions, based on the largeness of the core, under which cores of exact TU games are their unique von Neumann-Morgenstern stable sets. We show that this condition is satisfied by convex games and by nonatomic exact market games. In this way, we extend and unify earlier results existing in literature. Under some additional conditions we also prove the equivalence between the core and the Mas-Colell bargaining set.We thank Jean-Francois Mertens, Enrico Minelli, William Thomson, and two anonymous referees for helpful comments. We also thank seminar audiences at CORE, Cornell, Pescara, and Rochester. We gratefully acknowledge the financial support of the Ministero dell’Istruzione, dell’Universitá e della Ricerca.     

Tightness games with bounded finite selections

For a topological space X and a point x ∈ X, consider the following game—related to the property of X being countably tight at x. In each inning n ∈ ω, the first player chooses a set A _n that clusters at x, and then the second player picks a point a _n ∈ A _n ; the second player is the winner if and only if \(x \in \overline {\left\{ {{a_n}:n \in \omega } \right\}} \).In this work, we study variations of this game in which the second player is allowed to choose finitely many points per inning rather than one, but in which the number of points they are allowed to choose in each inning has been fixed in advance. Surprisingly, if the number of points allowed per inning is the same throughout the play, then all of the games obtained in this fashion are distinct. We also show that a new game is obtained if the number of points the second player is allowed to pick increases at each inning.     

Two-person repeated games with finite automata

We study two-person repeated games in which a player with a restricted set of strategies plays against an unrestricted player. An exogenously given bound on the complexity of strategies, which is measured by the size of the smallest automata that implement them, gives rise to a restriction on strategies available to a player.  We examine the asymptotic behavior of the set of equilibrium payoffs as the bound on the strategic complexity of the restricted player tends to infinity, but sufficiently slowly. Results from the study of zero sum case provide the individually rational payoff levels. Received February 1997/revised version March 2000     

A symmetrization for finite two-person games

The symmetrization method of Gale, Kuhn and Tucker for matrix games is extended for bimatrix games. It is shown that the equilibria of a bimatrix game and its symmetrization correspond two by two. A similar result is found with respect to quasi-strong, regular and perfect equilibria.     

Independent mistakes in large games

Economic models usually assume that agents play precise best responses to others' actions. It is sometimes argued that this is a good approximation when there are many agents in the game, because if their mistakes are independent, aggregate uncertainty is small. We study a class of games in which players' payoffs depend solely on their individual actions and on the aggregate of all players' actions. We investigate whether their equilibria are affected by mistakes when the number of players becomes large. Indeed, in generic games with continuous payoff functions, independent mistakes wash out in the limit. This may not be the case if payoffs are discontinuous. As a counter-example we present the n players Nash bargaining game, as well as a large class of “free-rider games.” Received: November 1997/Final version: December 1999     

Cooperative games with large cores

A payoff vector in ann-person cooperative game is said to be acceptable if no coalition can improve upon it. The core of a game consists of all acceptable vectors which are feasible for the grand coalition. The core is said to be large if for every acceptable vectory there is a vectorx in the core withx?y. This paper examines the class of games with large cores.     

Representation of characteristic function games by social choice functions

In Peleg's investigation of the representation of a simple game by a social choice function, it is shown that a special kind of proper symmetric simple game has its representation by employing the elimination procedure. In this paper, we consider a representation of a characteristic function game and explore general conditions under which the elimination procedure works effectively.     

Dominance elimination procedures on finite alternative games

A general definition of dominance elimination procedures for finite games is given which includes the multistage game representation of sophisticated voting for binary procedures. There then follows a proof that the set of outcomes resulting from the successive application of any dominance elimination procedure to any game in which each player has strict preferences over the alternatives, and in which the alternative and strategy spaces are finite, contains the set of outcomes attained by applying a procedure previously defined byFarquharson [1969].     

Minimal large sets for cooperative games

We analyze the concept of large set for a coalitional game v introduced by Martínez-de-Albéniz and Rafels (Int. J. Game Theory 33(1):107–114, 2004). We give some examples and identify some of these sets. The existence of such sets for any game is proved, and several properties of largeness are provided. We focus on the minimality of such sets and prove its existence using Zorn’s lemma. Institutional support from research grants (Generalitat de Catalunya) 2005SGR00984 and (Spanish Government and FEDER) SEJ2005-02443/ECON is gratefully acknowledged, and the support of the Barcelona Economics Program of CREA.     

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).     

Representation theory of wreath products of finite groups

This is an introduction to the representation theory of wreath products of finite groups. We also discuss in full details a couple of examples. Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 50, Functional Analysis, 2007.     

Feedback strategies with finite memory in differential games

It is shown that, in differential games, strategies can be defined for the players in such a way that their controls depend, for each timet, on a finite section of the past of the trajectoryx(t). In particular,s-delay,r-memory strategies can be defined as in the Varaiya-Lin approach. It is shown that, for deterministic differential games with terminal payoff, the upper and lower values of the game so defined, are independent of the lengthr of the memory. Lettingr 0, a feedback strategy is obtained which depends only on the present (and infinitesimal past) of the trajectoryx(t).     

Pure Nash equilibria in finite two-person non-zero-sum games

In this paper we study bimatrix games. The payoff matrices have properties closely related to concavity of functions. For such games we find sufficient conditions for the existence of pure Nash equilibria.     

On cooperative games with large monotonic core

Cooperative games with large core were introduced by Sharkey (Int. J. Game Theory 11:175–182, 1982), and the concept of Population Monotonic Allocation Scheme was defined by Sprumont (Games Econ. Behav. 2:378–394, 1990). Inspired by these two concepts, Moulin (Int. J. Game Theory 19:219–232, 1990) introduced the notion of large monotonic core giving a characterization for three-player games. In this paper we prove that all games with large monotonic core are convex. We give an effective criterion to determine whether a game has a large monotonic core and, as a consequence, we obtain a characterization for the four-player case.     

Impartial achievement and avoidance games for generating finite groups

We study two impartial games introduced by Anderson and Harary and further developed by Barnes. Both games are played by two players who alternately select previously unselected elements of a finite group. The first player who builds a generating set from the jointly selected elements wins the first game. The first player who cannot select an element without building a generating set loses the second game. After the development of some general results, we determine the nim-numbers of these games for abelian and dihedral groups. We also present some conjectures based on computer calculations. Our main computational and theoretical tool is the structure diagram of a game, which is a type of identification digraph of the game digraph that is compatible with the nim-numbers of the positions. Structure diagrams also provide simple yet intuitive visualizations of these games that capture the complexity of the positions.