A consistent value for games with n players and r alternatives

In Bolger [1993], an efficient value was obtained for a class of games called games with n players and r alternatives. In these games, each of the n players must choose one and only one of the r alternatives. This value can be used to determine a player’s “a priori” value in such a game. In this paper, we show that the value has a consistency property similar to the “consistency” for TU games in Hart/Mas-Colell [1989] and we present a set of axioms (including consistency) which characterizes this value.  The games considered in this paper differ from the multi-choice games considered by Hsiao and Raghavan [1993]. They consider games in which the actions of the players are ordered in the sense that, if i >j, then action i carries more “weight” than action j.  These games also differ from partition function games in that the worth of a coalition depends not only on the partitioning of the players but also on the action chosen by each subset of the partition. Received: April 1994/final version: June 1999     

Buyer-seller exactness in the assignment game

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the core of the game. These games will be called buyer-seller exact games and satisfy the condition that each mixed-pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyer-seller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer-seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed-pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a “45^o-lattice” by means of the core of an assignment game can now be answered. Received: March 2002/Revised version: January 2003 RID="*" ID="*"  Institutional support from research grants BEC 2002-00642 and SGR2001-0029 is gratefully acknowledged RID="**" ID="**"  The authors thank the referees for their comments     

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.     

An application of coding theory to a problem in graphical enumeration

This note was written while the first author was visiting the Department of Combinatorics and Optimization of the University of Waterloo as an Adjunct Professor. He would like to thank his colleagues there for their hospitality. The second author acknowledges the support of the National Science and Engineering Research Council of Canada given under grant #0GP0009258.     

Stochastic games without perfect monitoring

A two-person zero-sum stochastic game with finitely many states and actions is considered. The classical assumption of perfect monitoring is relaxed. Instead of being informed of the previous action of his opponent, each player receives a random signal, the law of which depending on both previous actions and on the previous state. We prove the existence of the max-min and dually of the min-max, thus extending both the result of Mertens-Neyman about the existence of the value in case of perfect monitoring and a theorem obtained by the author on a subclass of stochastic games: the absorbing games. It is a pleasure to thank J. Filar and V. Gaitsgory for their friendly hospitality at the School of Mathematics, University of South-Australia, where this work was initiated. There, the author was supported by a grant from the Australian Research Council no. A69703141. I would like also to thank S. Sorin for his keen interest and finally an anonymous referee for his careful reading of the proof.     

Quitting games – An example

Quitting games are multi-player sequential games in which, at every stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; each player i then receives a payoff r _S ⁱ, which depends on the set S of players that did choose to quit. If the game never ends, the payoff to each player is zero.? We exhibit a four-player quitting game, where the “simplest” equilibrium is periodic with period two. We argue that this implies that all known methods to prove existence of an equilibrium payoff in multi-player stochastic games are therefore bound to fail in general, and provide some geometric intuition for this phenomenon. Received: October 2001     

On non-transferable utility games with coalition structure

We introduce a solution function for Non-transferable Utility (NTU) games when prior coalition structure is given. This solution function generalizes both the Harsanyi solution function forNTU games and the Owen solution forTU games with coalition structure.I would like to thank Sergiu Hart, Bezalel Peleg and Shmuel Zamir for some conversations and constructive remarks on an earlier version of this paper. Part of this research was supported by the Sonderforschungsbereich 303 in the university of Bonn.     

The Compromise Value for Cooperative Games with Random Payoffs

This paper introduces and studies the compromise value for cooperative games with random payoffs, that is, for cooperative games where the payoff to a coalition of players is a random variable. This value is a compromise between utopia payoffs and minimal rights and its definition is based on the compromise value for NTU games and the τ-value for TU games. It is shown that the nonempty core of a cooperative game with random payoffs is bounded by the utopia payoffs and the minimal rights. Consequently, for such games the compromise value exists. Further, we show that the compromise value of a cooperative game with random payoffs coincides with the τ-value of a related TU game if the players have a certain type of preferences. Finally, the compromise value and the marginal value, which is defined as the average of the marginal vectors, coincide on the class of two-person games. This results in a characterization of the compromise value for two-person games.I thank Peter Borm, Ruud Hendrickx and two anonymous referees for their valuable comments.     

Uniform Group Divisible Designs with Block Sizes Three and <Emphasis Type="Italic">n</Emphasis>

 The existence of group divisible designs of type g ^t with block sizes three and n, 4≤ n≤10, is completely settled for all values of g and t. Received: July 21, 1999 Final version received: September 10, 2001 RID="*" ID="*" This work was done in 1995 while the authors were graduate students at the University of Waterloo, Waterloo, Ontario N2L 3G1, Canada Acknowledgments. The authors would like to thank the referee for his careful reading and for pointing out some errors in an earlier draft of the paper.     

Power indices and the veil of ignorance

We provide an axiomatic foundation of the expected utility preferences over lotteries on roles in simple superadditive games represented by the two main power indices, the Shapley-Shubik index and the Banzhaf index, when they are interpreted as von Neumann-Morgenstern utility functions. Our axioms admit meaningful interpretations in the setting proposed by Roth in terms of different attitudes toward risk involving roles in collective decision procedures under the veil of ignorance. In particular, an illuminating interpretation of `efficiency', up to now missing in this set up, as well as of the corresponding axiom for the Banzhaf index, is provided. November 7, 2002 RID="*" ID="*"  We want to thank M. Maschler, J. M. Zarzuelo and two referees for their comments. This research has been supported by the IVIE, and by the DGES of the Spanish Ministerio de Educación y Cultura, under project PB96-0247. The first author also acknowledges the financial support from the Ramón y Cajal Program initiated by the Spanish MCyT.     

Optimal threat strategies in collective bargaining

A model of collective bargaining in differential games, similar to one considered by Leitmann (Ref. 1), is proposed. Optimal threat strategies are then found and compared with Leitmann's solution. Nash-optimal threat strategies are also found and compared with the other two solutions.The author would like to thank Professor G. Leitmann of the University of California for bringing the author's attention to this subject.     

A generalization of the Dual Ellentuck Theorem

 We prove versions of the Dual Ramsey Theorem and the Dual Ellentuck Theorem for families of partitions which are defined in terms of games. Received: 8 July 1999 Published online: 19 December 2002 RID="*" ID="*" The author wishes to thank the Swiss National Science Foundation for supporting him. The authors thank the referee for helpful comments. Mathematics Subject Classification (2000): 03E02, 05D10, 03E35 Key words or phrases: Dual Ramsey Theorem – Dual Ellentuck Theorem – Partitions – Games     

Maximal Energy Bipartite Graphs

 Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, then

Stability of marriage with externalities

In many matching problems, it is natural to consider that agents may have preferences not only over the set of potential partners but also over what other matches occur. Once such externalities are considered, the set of stable matchings will depend on what agents believe will happen if they deviate. In this paper, we introduce endogenously generated beliefs (which depend on the preferences). We introduce a particular notion of endogenous beliefs, called sophisticated expectations, and show that with these beliefs, stable matchings always exist. I would like to thank the editor, William Thomson, two anonymous referees, Kalyan Chatterjee, Federico Echenique, Matthew Jackson, Tarık Kara, Semih Koray, and Manabu Toda for their comments and suggestions. I am very much indebted to Vijay Krishna for his guidance and support.     

A generalization of the rees theorem to a class of regular semigroups

Let S be a regular semigroup for which Green's relations J and D coincide, and which is max-principal in the sense that every element of S is contained in maximal principal right, left and two-sided ideals of S. A construction is given of a max-principal regular semigroup W with J=D, which is also principally separated in the sense that distinct maximal principal right (or left) ideals of S are disjoint, and an epimorphism ψ: W→S that preserves maximality of principal left, right, and two sided ideals, and is in a sense locally one-to-one. If S is completely simple, this construction reduces to the Rees matrix representation of S. The main result of this paper has its origin in an incorrect result contained in the author's doctoral dissertation which was written at the University of California (Berkeley) under Professor John Rhodes. This theorem was first established for finite regular semigroups in [1] (Corollary 2.3), and the present generalization of this result to infinite semigroups was suggested by Professor A. H. Clifford, who the author would like to thank for this as well as his generous encouragement and many helpful editorial suggestions. The author would also like to thank Professor Rhodes for his encouragement.     

Random marginal and random removal values

We propose two variations of the non-cooperative bargaining model for games in coalitional form, introduced by Hart and Mas-Colell (Econometrica 64:357–380, 1996a). These strategic games implement, in the limit, two new NTU-values: the random marginal and the random removal values. Their main characteristic is that they always select a unique payoff allocation in NTU-games. The random marginal value coincides with the Consistent NTU-value (Maschler and Owen in Int J Game Theory 18:389–407, 1989) for hyperplane games, and with the Shapley value for TU games (Shapley in In: Contributions to the theory of Games II. Princeton University Press, Princeton, pp 307–317, 1953). The random removal value coincides with the solidarity value (Nowak and Radzik in Int J Game Theory 23:43–48, 1994) in TU-games. In large games we show that, in the special class of market games, the random marginal value coincides with the Shapley NTU-value (Shapley in In: La Décision. Editions du CNRS, Paris, 1969), and that the random removal value coincides with the equal split value.      

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 consistent solutions for strategic games

Nash equilibria for strategic games were characterized by Peleg and Tijs (1996) as those solutions satisfying the properties of consistency, converse consistency and one-person rationality.  There are other solutions, like the ɛ-Nash equilibria, which enjoy nice properties and appear to be interesting substitutes for Nash equilibria when their existence cannot be guaranteed. They can be characterized using an appropriate substitute of one-person rationality. More generally, we introduce the class of “personalized” Nash equilibria and we prove that it contains all of the solutions characterized by consistency and converse consistency. Received January 1996/Final version December 1996     

A differential game of approach with two pursuers and one evader

A differential game of approach with one evader and two pursuers with a nonconvex payoff function is considered. The duration of the game is fixed. The payoff functional is the distance between the object being pursued and the pursuer closest to it when the game terminates. An explicit form of the game value is found for all possible game positions. The paper is closely related to Refs. 1–12.The authors would like to thank Professor A. I. Subbotin for his valuable advice and encouragement.