On finding curb sets in extensive games

We characterize strategy sets that are closed under rational behavior (curb) in extensive games of perfect information and finite horizon. It is shown that any such game possesses only one minimal curb set, which necessarily includes all its subgame perfect Nash equilibria. Applications of this result are twofold. First, it lessens computational burden while computing minimal curb sets. Second, it implies that the profile of subgame perfect equilibrium strategies is always stochastically stable in a certain class of games.I am grateful to J. Kamphorst, G. van der Laan and X. Tieman, who commented on the earlier versions of the paper. I also thank an anonymous referee and an associate editor for their helpful remarks. The usual disclaimer applies.     

On extensive games and almost complete information

Our main result for finite games in extensive form is that strict determinacy for a playeri in a completely inflated game structure implies almost complete information for playeri, even if we allow for certain type of overlapping for information sets.     

On Pareto equilibria in vector-valued extensive form games

In this paper we investigate the existence of Pareto equilibria in vector-valued extensive form games. In particular we show that every vector-valued extensive form game with perfect information has at least one subgame perfect Pareto equilibrium in pure strategies. If one tries to prove this and develop a vector-valued backward induction procedure in analogy to the real-valued one, one sees that different effects may occur which thus have to be taken into account: First, suppose the deciding player at a nonterminal node makes a choice such that the equilibrium payoff vector of the subgame he would enter is undominated under the equilibrium payoff vectors of the other subgames he might enter. Then this choice need not to lead to a Pareto equilibrium. Second, suppose at a nonterminal node a chance move may arise. The combination of the Pareto equilibria of the subgames to give a strategy combination of the entire game need not be a Pareto equilibrium of the entire game.     

Complexity of games and bounded rationality

An attempt is made to propose a concept of limited rationality for choice junctions based on computability theory in computer science.

Starting with the observation that it is possible to construct a machine simulating strategies of each individual in society, one machine for each individual's preference structure, we identify internal states of this machine with strategies or strategic preferences. Inputs are possible actions of other agents in society thus society is effectively operating as a game generated by machines. The main result states that effective realization of game strategies bound by the “complexity of computing machines'.     

On the non-existence of barker sequences

It is an old conjecture that there are no unknown Barker sequences. Here, a sufficient condition for the non-existence of Barker sequences of even length 4m ² is given, which allows us to show that there are no unknown sequences withm less than 105, exceptm=63, which remains still undecided.     

Simplification of games in extensive form

Thevon Neumann-Morgenstern normal form of a game is conceptually and theoretically useful, but in practice leads to enormous matrix games. We discuss new methods of simplifying games in extensive form that should be useful for solving actual games. The first method is that of partially normalizing the game at an information set and, if dominations are found, making local “negative” decisions not to choose certain alternatives at the information set. Coupled with this idea is the reduction operation which eliminates parts of the game tree. These methods are shown to be powerful enough to eliminate all dominations in the strategy matrix, where we consider domination in three senses.     

The logical representation of extensive games

Given an extensive formG, we associate with every choice an atomic sentence and with every information set a set of well-formed formulas (wffs) of prepositional calculus. The set of such wffs is denoted by Γ(G). Using the so-called topological semantics for propositional calculus (which differs from the standard one based on truth tables), we show that the extensive form yields a topological model of Γ(G), that is, every wff in Γ(G), is “true in G”. We also show that, within the standard truth-table semantics for propositional calculus, there is a one-to-one and onto correspondence between the set of plays ofG and the set of valuations that satisfy all the wffs in Γ(G).     

The nucleolus for cooperative games with arbitrary bounds of individual rationality

We consider cooperative games with a given bound for individual rationality. We introduce the nucleolus with respect to the set of preimputations satisfying the newly defined bounds of rationality. An axiomatization of this nucleolus is given.     

Hospital management games: a taxonomy and extensive review

Hospital management games have gained importance in better planning for scarce resources in times of growing health care demand and increasing technology costs. We classify and investigate the main characteristics of these games from an Operations Research (OR) perspective. Hospital management games model the complex decision making process of internal resource, process, and financial management all influenced by the external hospital environment (e.g., purchasing markets, job markets, legal/political conditions, competition) and simulate situations of the real world. We also highlight the potential of these games for teaching OR in the classroom. Experiencing the advantages of OR may reduce the reservations policy makers have and could make them increasingly open to promoting OR applications in practice. We also disclose potential for new applications.     

On the non-existence of homoclinic orbits for a class of infinite dimensional Hamiltonian systems

We prove that for a class of infinite dimensional Hamiltonian systems certain homoclinic connections to the origin cease to exist when the non-linearities have `super-critical' growth. The proof is based on a variational principle and a Poho\v{z}aev type identity.

     

On non-existence of certain error formulas for ideal interpolation

We answer a question raised by Carl de Boor regarding the existence of certain “good” error formulas for ideal interpolation. We will show that, for a specific form of ideal interpolation by linear polynomials in two variables, such formulas do not exist.     

On a criterion of rationality for a series in orthogonal polynomials

We present a criterion of rationality for a function determined by its expansion in a series in orthogonal polynomials. This criterion can be regarded as an analog of the well-known Kronecker criterion of rationality for functions given by power series.     

On the non-existence of a class of symmetric group divisible partial designs

Many non-existence theorems are known for symmetric group divisible partial designs. In the case that these partial designs are auto-dual with ₁=0, an ideal incidence structure can be defined whose elements are the equivalence-classes of non-collinear points and parallel blocks. Except for some trivial cases this incidence structure turns out to be a symmetric design, and by studying its existence we can prove much more powerful non-existence theorems.     

On the saddle-point stability for a class of dynamic games

In this paper, we study the stability properties of the class of capital accumulation games introduced by Fershtman and Muller (Ref. 1). Both discrete and continuous time versions are discussed. It is shown that the open-loop Nash equilibrium solutions for both games are characterized by a general saddle-point property, a result best known from the turnpike literature in optimal growth theory. In the case of zero discount rates, an even stronger result can be derived: As long as the Hessian matrix of the instantaneous profit functions has a quasidominant diagonal, no pure imaginary roots are possible.The authors thank J. Boyd III, G. Feichtinger, S. Jørgensen, and G. Schwann for helpful comments. The first author acknowledges financial support from the Natural Science and Engineering Research Council of Canada, Grant No. OGP-0037342.