On the core of network synthesis games

We use polynomial formulations to show that several rational and discrete network synthesis games, including the minimum cost spanning tree game, satisfy the assumptions of Owen's linear production game model. We also discuss computational issues related to finding and recognizing core points for these classes of games.     

On the isochronous and stroboscopic capture in differential games

In Ref. 1, Hájek formulated the conjecture that isochronous capture is necessarily stroboscopic in linear differential games. Here, it is shown that this conjecture is not valid.     

A class of stochastic games with ordered field property

It is shown that discounted general-sum stochastic games with two players, two states, and one player controlling the rewards have the ordered field property. For the zero-sum case, this result implies that, when starting with rational data, also the value is rational and that the extreme optimal stationary strategies are composed of rational components.     

Ordered field property for stochastic games when the player who controls transitions changes from state to state

In this paper, we consider a zero-sum stochastic game with finitely many states restricted by the assumption that the probability transitions from a given state are functions of the actions of only one of the players. However, the player who thus controls the transitions in the given state will not be the same in every state. Further, we assume that all payoffs and all transition probabilities specifying the law of motion are rational numbers. We then show that the values of both a -discounted game, for rational , and of a Cesaro-average game are in the field of rational numbers. In addition, both games possess optimal stationary strategies which have only rational components. Our results and their proofs form an extension of the results and techniques which were recently developed by Parthasarathy and Raghavan (Ref. 1).The author wishes to thank Professor T. E. S. Raghavan for introducing him to this problem and for discussing stochastic games with him on many occasions. This research was supported in part by AFOSR Grant No. 78–3495B.     

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.     

The complexity of recursion theoretic games

We show that some natural games introduced by Lachlan in 1970 as a model of recursion theoretic constructions are undecidable, contrary to what was previously conjectured. Several consequences are pointed out; for instance, the set of all -sentences that are uniformly valid in the lattice of recursively enumerable sets is undecidable. Furthermore we show that these games are equivalent to natural subclasses of effectively presented Borel games.

     

Bargaining sets and the core in partitioning games

Partitioning games are useful on two counts: first, in modeling situations with restricted cooperative possibilities between the agents; second, as a general framework for many unrestricted cooperative games generated by combinatorial optimization problems.We show that the family of partitioning games defined on a fixed basic collection is closed under the strategic equivalence of games, and also for taking the monotonic cover of games. Based on these properties we establish the coincidence of the Mas-Colell, the classical, the semireactive, and the reactive bargaining setswith the core for interesting balanced subclasses of partitioning games, including assignment games, tree-restricted superadditive games, and simple network games. Prepared during the author’s Bolyai János Research Fellowship. Also supported by OTKA grant T46194.     

Limit Consistent Solutions in Noncooperative Games

Strong and limit consistency in finite noncooperative games are studied. A solution is called strongly consistent if it is both consistent and conversely consistent (Ref. 1). We provide sufficient conditions on one-person behavior such that a strongly consistent solution is nonempty. We introduce limit consistency for normal form games and extensive form games. Roughly, this means that the solution can be approximated by strongly consistent solutions. We then show that the perfect and proper equilibrium correspondences in normal form games, as well as the weakly perfect and sequential equilibrium correspondences for extensive form games, are limit consistent.     

Some new results on least square values for TU games

In this paper we present some new results concerning the least square family of values for TU games. We first examine the stability of these values from a dynamic point of view and propose a reinteropretation of them from the standpoint of the propernsity to disrupt approach. In the second part the family of individually rational least square (IRLS) values is introduced and an alternative kernel-like formulation of them is provided. Finally we describe a natural and simple algorithm for calculating any IRLS value of a game. We gratefully acknowledge financial support from the Basque Government (Project PI95/101) and from the D.G.E.S. of the Ministerio de Educatión y Cultura (Project PB96-0247).     

凸对策核仁的非空性及合成凸对策核仁的单调性

本文给出了核仁与核及最小核心之间的关系 ,且证明了凸对策核仁的存在性和唯一性 ,证明了凸对策的合成对策仍是凸对策 .最后 ,我们讨论了合成凸对策的核仁不满足单调性 .     

Periodic stopping games

Stopping games (without simultaneous stopping) are sequential games in which at every stage one of the players is chosen, who decides whether to continue the interaction or stop it, whereby a terminal payoff vector is obtained. Periodic stopping games are stopping games in which both of the processes that define it, the payoff process as well as the process by which players are chosen, are periodic and do not depend on the past choices. We prove that every periodic stopping game without simultaneous stopping, has either periodic subgame perfect ϵ-equilibrium or a subgame perfect 0-equilibrium in pure strategies. This work is part of the master thesis of the author done under the supervision of Prof. Eilon Solan. I am thankful to Prof. Solan for his inspiring guidance. I also thank two anonymous referees of the International Journal of Game Theory for their comments.     

Values for strategic games in which players cooperate

In this paper we propose a new method to associate a coalitional game with each strategic game. The method is based on the lower value of finite two-player zero-sum games. We axiomatically characterize this new method, as well as the method that was described in Von Neumann and Morgenstern (1944). As an intermediate step, we provide axiomatic characterizations of the value and the lower value of matrix games and finite two-player zero-sum games, respectively.The authors acknowledge the financial support of Ministerio de Ciencia y Tecnologia, FEDER andXunta de Galicia through projects BEC2002-04102-C02-02 and PGIDIT03PXIC20701PN.We wish to thank Professor William Thomson as well as an anonymous referee for useful comments.     

On the core of cooperative queueing games

We consider a class of cooperative games for managing several canonical queueing systems. When cooperating parties invest optimally in common capacity or choose the optimal amount of demand to serve, cooperation leads to “single-attribute” games whose characteristic function is embedded in a one-dimensional function. We show that when and only when the latter function is elastic will all embedded games have a non-empty core, and the core contains a population monotonic allocation. We present sufficient conditions for this property to be satisfied. Our analysis reveals that in most Erlang B and Erlang C queueing systems, the games under our consideration have a non-empty core, but there are exceptions, which we illustrate through a counterexample.     

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.     

Totally monotonic games and flow games

Equivalences between totally balanced games and flow games, and between monotonic games and pseudoflow games are well-known. This paper shows that for every totally monotonic game there exists an equivalent flow game and that for every monotonic game, there exists an equivalent flow-based secondary market game.     

Online Ramsey games for more than two colors

Consider the following one‐player game played on an initially empty graph with n vertices. At each stage a randomly selected new edge is added and the player must immediately color the edge with one of r available colors. Her objective is to color as many edges as possible without creating a monochromatic copy of a fixed graph F. We use container and sparse regularity techniques to prove a tight upper bound on the typical duration of this game with an arbitrary, but fixed, number of colors for a family of 2‐balanced graphs. The bound confirms a conjecture of Marciniszyn, Spöhel and Steger and yields the first tight result for online graph avoidance games with more than two colors. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 464–492, 2017     

Weighted search games

In this paper we shall deal with search games in which the strategic situation is developed on a lattice. The main characteristic of these games is that the points in each column of the lattice have a specific associated weight which directly affects the payoff function. Thus, the points in different columns represent points of different strategic value. We solve three different types of games. The first involves search, ambush and mixed situations, the second is a search and inspection game and the last is related to the accumulative games.     

Notes on the Roots of Ehrhart Polynomials

We determine lattice polytopes of smallest volume with a given number of interior lattice points. We show that the Ehrhart polynomials of those with one interior lattice point have largest roots with norm of order n², where n is the dimension. This improves on the previously best known bound n and complements a recent result of Braun where it is shown that the norm of a root of a Ehrhart polynomial is at most of order n². For the class of 0-symmetric lattice polytopes we present a conjecture on the smallest volume for a given number of interior lattice points and prove the conjecture for crosspolytopes. We further give a characterisation of the roots of Ehrhart polyomials in the three-dimensional case and we classify for n ≤ 4 all lattice polytopes whose roots of their Ehrhart polynomials have all real part -1/2. These polytopes belong to the class of reflexive polytopes.     

双准均衡合作对策τ值的公理化

介绍了能准确刻画现实生活中每个参与者有三种选择的双合作对策,在此基础上研究了双合作对策的τ值,并对双准均衡合作对策的τ值进行了公理化,其中双合作对策的上向量、间隙函数、让步向量的构造是刻画其τ值的基础．