Information patterns and Nash equilibria in extensive games: 1

In this paper we explore the relation between information patterns and Nash Equilibria in extensive games. By information we mean what players know about moves made by others, as well as by chance. For the most part we confine ourselves to pure strategies. But in Section 2 behavioral strategies are also examined. It turns out that they can be modeled as pure strategies of an appropriately enlarged game. Our results, applied to the enlarged game, can then be reinterpreted in terms of the behavioral strategies of the original game.     

Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic

We investigate the definability in monadic ∑₁¹ and monadic Π₁¹ of the problems REG_k, of whether there is a regular subgraph of degree k in some given graph, and XREG_k, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REG_k^k and XREG_k^k, respectively, for k ≥ 2 (all our graphs are undirected). Our motivation partly stems from the fact (which we prove here) that REG_k^k and XREG_k^k are logspace equivalent to CONN and REACH, respectively, for k ≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first - order reductions, monadic ∑₁¹ games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑₁¹ and monadic Π₁¹, and we compare the definability of these problems (in monadic ∑₁¹ and monadic Π₁¹ with their computational complexity (which varies from solvable using logspace to NP - complete).     

The Study of Minimax Inequalities, Abstract Economics and Applications to Variational Inequalities and Nash Equilibria

In this survey, a new minimax inequality and one equivalent geometricform are proved. Next, a theorem concerning the existence of maximalelements for an LC-majorized correspondence is obtained.By the maximal element theorem, existence theorems of equilibrium point fora noncompact one-person game and for a noncompact qualitative game withLC-majorized correspondences are given. Using the lastresult and employing 'approximation approach', we prove theexistence of equilibria for abstract economies in which the constraintcorrespondence is lower (upper) semicontinuous instead of having lower(upper) open sections or open graphs in infinite-dimensional topologicalspaces. Then, as the applications, the existence theorems of solutions forthe quasi-variational inequalities and generalized quasi-variationalinequalities for noncompact cases are also proven. Finally, with theapplications of quasi-variational inequalities, the existence theorems ofNash equilibrium of constrained games with noncompact are given. Our resultsinclude many results in the literature as special cases.     

A note on the nucleolus and the kernel of the assignment game

There exist coalitional games with transferable utility which have the same core but different nucleoli. We show that this cannot happen in the case of assignment games. Whenever two assignment games have the same core, their nucleoli also coincide. To show this, we prove that the nucleolus of an assignment game coincides with that of its buyer–seller exact representative.I am grateful to C. Rafels and to the referees for their comments. Institutional support from research grants BEC 2002-00642 and SGR2001–0029 is also acknowledged.     

On Fraenkel’s <Emphasis Type="Italic">N</Emphasis>-Heap Wythoff’s Conjectures

The N-heap Wythoffs game is a two-player impartial game with N piles of tokens of sizes Players take turns removing any number of tokens from a single pile, or removing (a₁,..., a_N) from all piles - a_i tokens from the i-th pile, providing that where is the nim addition. The first player that cannot make a move loses. Denote all the P-positions (i.e., losing positions) by Two conjectures were proposed on the game by Fraenkel [7]. When are fixed, i) there exists an integer N₁ such that when . ii) there exist integers N₂ and _2 such that when , the golden section.In this paper, we provide a sufficient condition for the conjectures to hold, and subsequently prove them for the three-heap Wythoffs game with the first piles having up to 10 tokens.AMS Subject Classification: 91A46, 68R05.     

The $-game

We propose a payoff function extending Minority Games (MG) that captures the competition between agents to make money. In contrast with previous MG, the best strategies are not always targeting the minority but are shifting opportunistically between the minority and the majority. The emergent properties of the price dynamics and of the wealth of agents are strikingly different from those found in MG. As the memory of agents is increased, we find a phase transition between a self-sustained speculative phase in which a “stubborn majority” of agents effectively collaborate to arbitrage a market-maker for their mutual benefit and a phase where the market-maker always arbitrages the agents. A subset of agents exhibit a sustained non-equilibrium risk-return profile. Received 5 June 2002 / Received in final form 21 November 2002 Published online 27 January 2003 RID="a" ID="a"e-mail: sornette@unice.fr RID="b" ID="b"CNRS UMR7536 RID="c" ID="c"CNRS UMR6622     

Shapley value for constant-sum games

It is proved that Youngs [4] axiomatization for the Shapley value by marginalism, efficiency, and symmetry is still valid for the Shapley value defined on the class of nonnegative constant-sum games with nonzero worth of grand coalition and on the entire class of constant-sum games as well.The research was supported by NWO (The Netherlands Organization for Scientific Research) grant NL-RF 047-008-010.I am thankful to Theo Driessen, Natalia Naumova and Elena Yanovskaya for interesting discussions and comments. The useful remarks of two anonymous referees are also appreciated.     

Additive stable solutions on perfect cones of cooperative games

Closed kernel systems of the coalition matrix turn out to correspond to cones of games on which the core correspondence is additive and on which the related barycentric solution is additive, stable and continuous. Different perfect cones corresponding to closed kernel systems are described. Received: December 2001/Revised: July 2002 RID="*" ID="*"  This note contains the new results, which were presented by the first author in an invited lecture at the XIV Italian Meeting on Game Theory and Applications in Ischia, July 2001. The lecture was dedicated to Irinel Dragan on the occasion of his seventieth birthday.     

On existence of undominated pure strategy Nash equilibria in anonymous nonatomic games: a generalization

In this paper, we generalize the exitence result for pure strategy Nash equilibria in anonymous nonatomic games. By working directly on integrals of pure strategies, we also generalize, for the same class of games, the existence result for undominated pure strategy Nash equilibria even though, in general, the set of pure strategy Nash equilibria may fail to be weakly compact. Received August 2001