On a generalization of Kaplansky's game

In this paper, games of the following general kind are studied: Two players move alternately by selecting unselected integer coordinate points in the plane. On each move, the first player selects exactly r points and the second player selects exactly one point. The first player wins if he can select p points on a line having none of his opponent's points before his opponent selects q points on a line having none of his own. If this latter eventuality occurs first, the second player wins. It is shown that if p ? c(r)q, then the second player can always win.     

Two-noisy-versus-one-silent duel with equal accuracy functions

This paper deals with the two-noisy-versus-one-silent duel which is still open, as pointed out by Styszyński (Ref. 1). Player I has a noisy gun with two bullets, and player II has a silent gun with one bullet. Each player fires his bullets aiming at his opponent at any time in [0, 1]. The accuracy function (the probability that one player hits his opponent if he fires at timet) isp(t)=t for each player. If player I hits player II, without being hit himself before, the payoff of the duel is +1; if player I is hit by player II, without hitting player II before, the payoff is taken to be ?1. In this paper, we determine the optimal strategies and the value of the game. The strategy for player II depends explicitly on the firing moment of player I's first shot.     

Single-suit two-person card play

We consider a two-person constant sum perfect information game, which we call theEnd Play Game, which arises from an abstraction of simple end play positions in card games of the whist family, including bridge. This game was described in 1929 by Emanuel Lasker, the mathematician and world chess champion, who called itwhistette. The game uses a deck of cards that consists of a single totally ordered suit of 2n cards. To begin play the deck is divided into two handsA andB ofn cards each, held by players Left and Right, and one player is designated as having thelead. The player on lead chooses one of his cards, and the other player after seeing this card selects one of his own to play. The player with the higher card wins a “trick” and obtains the lead. The cards in the trick are removed from each hand, and play then continues until all cards are exhausted. Each player strives to maximize his trick total, and thevalue of the game to each player is the number of tricks he takes. Despite its simple appearance, this game is quite complicated, and finding an optimal strategy seems difficult. This paper derives basic properties of the game, gives some criteria under which one hand is guaranteed to be better than another, and determines the optimal strategies and value functions for the game in several special cases.     

Suboptimality of M-step back strategies in Bayesian games

We consider the Bayes optimal strategy for repeated two player games where moves are made simultaneously. In these games we look at models where one player assumes that the other player is employing a strategy depending only on the previousm-move pairs (as discussed in Wilson, 1986). We show that, under very unrestrictive conditions, such an assumption is not consistent with the assumption of rationality of one's opponent. Indeed, we show that by employing such a model a player is implicitly assuming that his opponent is not playing rationally,with probability one. We argue that, in the context of experimental games, thesem-step back models must be inferior to models which are consistent with the assumption that an opponent can be rational.     

Topological games and continuity of group operations

We consider a topological game GΠ involving two players α and β and show that, for a paratopological group, the absence of a winning strategy for player β implies the group is a topological one. We provide a large class of topological spaces X for which the absence of a winning strategy for player β is equivalent to the requirement that X is a Baire space. This allows to extend the class of paratopological or semitopological groups for which one can prove that they are, actually, topological groups.Conditions of the type “existence of a winning strategy for the player α” or “absence of a winning strategy for the player β” are frequently used in mathematics. Though convenient and satisfactory for theoretical considerations, such conditions do not reveal much about the internal structure of the topological space where they hold. We show that the existence of a winning strategy for any of the players in all games of Banach-Mazur type can be expressed in terms of “saturated sieves” of open sets.     

The complexity of node blocking for dags

We consider the following modification of annihilation games called node blocking. Given a directed graph, each vertex can be occupied by at most one token. There are two types of tokens, each player can move only tokens of his type. The players alternate their moves and the current player i selects one token of type i and moves the token along a directed edge to an unoccupied vertex. If a player cannot make a move then he loses. We consider the problem of determining the complexity of the game: given an arbitrary configuration of tokens in a planar directed acyclic graph (dag), does the current player have a winning strategy? We prove that the problem is PSPACE-complete.     

How to stay in a set or König’s lemma for random paths

Starting at statex?X, a player selects the next statex ₁ from the collection Τ(x) of those available and then selectsx ₂ from Τ(x ₁) and so on. Suppose the object is to control the pathx ₁,x ₂, … so that everyx _i will lie in a subsetA ofX. A famous lemma of König is equivalent to the statement that if every Τ(x) is finite and if, for everyn, the player can obtain a path inA of lengthn, then the player can obtain an infinite path inA. Here paths are not necessarily deterministic and, for eachx, Τ(x) is the collection of possible probability distributions for the next state. Under mild measurability conditions, it is shown that if, for everyn, there is a random path of lengthn which lies inA with probability larger than α, then there is an infinite random path with the same property. Furthermore, the measurability and finiteness assumptions can be dropped if, in the hypothesis, the positive integersn are replaced by stop rulest. An analogous result holds when the object is to visitA infinitely many times.     

Game theory with translucent players

A traditional assumption in game theory is that players are opaque to one another—if a player changes strategies, then this change in strategies does not affect the choice of other players’ strategies. In many situations this is an unrealistic assumption. We develop a framework for reasoning about games where the players may be translucent to one another; in particular, a player may believe that if she were to change strategies, then the other player would also change strategies. Translucent players may achieve significantly more efficient outcomes than opaque ones. Our main result is a characterization of strategies consistent with appropriate analogues of common belief of rationality. Common Counterfactual Belief of Rationality (CCBR) holds if (1) everyone is rational, (2) everyone counterfactually believes that everyone else is rational (i.e., all players i believe that everyone else would still be rational even if i were to switch strategies), (3) everyone counterfactually believes that everyone else is rational, and counterfactually believes that everyone else is rational, and so on. CCBR characterizes the set of strategies surviving iterated removal of minimax-dominated strategies, where a strategy \(\sigma \) for player i is minimax dominated by \(\sigma '\) if the worst-case payoff for i using \(\sigma '\) is better than the best possible payoff using \(\sigma \).     

Domain representability and the Choquet game in Moore and BCO-spaces

In this paper we investigate the role of domain representability and Scott-domain representability in the class of Moore spaces and the larger class of spaces with a base of countable order. We show, for example, that in a Moore space, the following are equivalent: domain representability; subcompactness; the existence of a winning strategy for player α (= the nonempty player) in the strong Choquet game Ch(X); the existence of a stationary winning strategy for player α in Ch(X); and Rudin completeness. We note that a metacompact ?ech-complete Moore space described by Tall is not Scott-domain representable and also give an example of ?ech-complete separable Moore space that is not co-compact and hence not Scott-domain representable. We conclude with a list of open questions.     

On expectations and the monetary stakes in ultimatum games

In an ultimatum game, player 1 makes an offer of $X from a total of $M to player 2. If player 2 accepts the offer, then player 1 is paid $(M-X) and player 2 receives $X; if player 2 rejects the offer, each gets zero. In the ultimatum game experiments reported in the literature,M is typically not more than $10 (see Forsythe, Horowitz, Savin and Sefton, 1994, hereafter FHSS; Hoffman, McCabe, Shachat and Smith, 1994, hereafter HMSS, and the literature cited therein). We report new results for 50 bargaining pairs in whichM=$100, and compare them with previous outcomes from 48 pairs withM=$10. The need for an examination of the effect of increased stakes on ultimatum bargaining is suggested by a literature survey of the effect of varying the stakes in a wide variety of decision making and market experiments over the last 33 years (Smith and Walker, 1993b). Many cases were found in which the predictions of theory were improved when the monetary rewards were increased. There were also cases in which the level of monetary rewards had no effect on the results. Consequently, it is necessary to examine the stakes question on a case by case basis. The previously reported effect of instructional changes, which define different institutional contexts, on ultimatum game outcomes, and the effect of stakes reported here, suggest a game formulation that explains changes in the behavior of both players as a result of changes in the instructional treatments. We formulate such a model and indicate how it might be further tested.     

Share functions for cooperative games with levels structure of cooperation

In a standard TU-game it is assumed that every subset of the player set N can form a coalition and earn its worth. One of the first models where restrictions in cooperation are considered is the one of games with coalition structure of Aumann and Drèze (1974). They assumed that the player set is partitioned into unions and that players can only cooperate within their own union. Owen (1977) introduced a value for games with coalition structure under the assumption that also the unions can cooperate among them. Winter (1989) extended this value to games with levels structure of cooperation, which consists of a game and a finite sequence of partitions defined on the player set, each of them being coarser than the previous one.     

Strategic disclosure of random variables

We consider a game G_n played by two players. There are n independent random variables Z₁, … , Z_n, each of which is uniformly distributed on [0,1]. Both players know n, the independence and the distribution of these random variables, but only player 1 knows the vector of realizations z ? (z₁, … , z_n) of them. Player 1 begins by choosing an order _zk1,…,_zkn$z_{k_1}\text{,}\dots \text{,}{z}_{k_n}$ of the realizations. Player 2, who does not know the realizations, faces a stopping problem. At period 1, player 2 learns _zk1$z_{k_1}$. If player 2 accepts, then player 1 pays _zk1$z_{k_1}$ euros to player 2 and play ends. Otherwise, if player 2 rejects, play continues similarly at period 2 with player 1 offering _zk2$z_{k_2}$ euros to player 2. Play continues until player 2 accepts an offer. If player 2 has rejected n − 1 times, player 2 has to accept the last offer at period n. This model extends Moser’s (1956) problem, which assumes a non-strategic player 1.     

Some remarks on a game of Telgársky

In [3] R. Telgársky (1975) asked: does the first player have a winning strategy in the game G(F,X×X) if the first player has a winning strategy in the game G(F,X)? I give a positive answer to this question and prove that this result is also true for spaces where the first player has a winning strategy in game G(K,X) where K=1, F, C, for σC if X is P-space and for DC if X is collectionwise-normal space. The last result is related to the Telgársky's (1983) conjecture discussed in [1]. These results are not true for infinite product of spaces.     

Average-discounted equilibria in stochastic games

In stochastic games with finite state and action spaces, we examine existence of equilibria where player 1 uses the limiting average reward and player 2 a discounted reward for the evaluations of the respective payoff sequences. By the nature of these rewards, the far future determines player 1's reward, while player 2 is rather interested in the near future. This gives rise to a natural cooperation between the players along the course of the play. First we show the existence of stationary ε-equilibria, for all ε>0, in these games. However, besides these stationary ε-equilibria, there also exist ε-equilibria, in terms of only slightly more complex ultimately stationary strategies, which are rather in the spirit of these games because, after a large stage when the discounted game is not interesting any longer, the players cooperate to guarantee the highest feasible reward to player 1. Moreover, we analyze an interesting example demonstrating that 0-equilibria do not necessarily exist in these games, not even in terms of history dependent strategies. Finally, we examine special classes of stochastic games with specific conditions on the transition and payoff structures. Several examples are given to clarify all these issues.     

The partition bargaining problem

Consider the problem of partitioning n items among d players where the utility of each player for bundles of items is additive; so, player r has utility for item i and the utility of that player for a bundle of items is the sum of the 's over the items i in his/her bundle. Each partition S of the items is then associated with a d-dimensional utility vector V^S whose coordinates are the utilities that the players assign to the bundles they get under S. Also, lotteries over partitions are associated with the corresponding expected utility vectors. We model the problem as a Nash bargaining game over the set of lotteries over partitions and provide methods for computing the corresponding Nash solution, to prescribed accuracy, with effort that is polynomial in n. In particular, we show that points in the pareto-optimal set of the corresponding bargaining set correspond to lotteries over partitions under which each item, with the possible exception of at most d(d-1)/2 items, is assigned in the same way.     

Layers of noncooperative games

We model and analyze classes of antagonistic stochastic games of two players. The actions of the players are formalized by marked point processes recording the cumulative damage to the players at any moment of time. The processes evolve until one of the processes crosses its fixed preassigned threshold of tolerance. Once the threshold is reached or exceeded at some point of the time (exit time), the associated player is ruined. Both stochastic processes are being “observed” by a third party point stochastic process, over which the information regarding the status of both players is obtained. We succeed in these goals by arriving at closed form joint functionals of the named elements and processes. Furthermore, we also look into the game more closely by introducing an intermediate threshold (see a layer), which a losing player is to cross prior to his ruin, in order to analyze the game more scrupulously and see what makes the player lose the game.     

On pursuit problems in controlled distributed systems

In the present paper, we study the problem of transferring a system from one state into another state in the presence of a player trying to prevent the occurrence of this transfer in the system. The system dynamics is described by partial differential equations whose right-hand sides contain the player controls in additive form. In a similar setting, the problem was solved in several papers, but it has not been considered for the case in which various constraints are imposed on the controls of the players. Here, in contrast to several other papers, we consider games in the entire scale of spaces H _r , r ≥ 0. We propose a new approach for completing the pursuit under various constraints on the player controls.     

Layers of noncooperative games

We model and analyze classes of antagonistic stochastic games of two players. The actions of the players are formalized by marked point processes recording the cumulative damage to the players at any moment of time. The processes evolve until one of the processes crosses its fixed preassigned threshold of tolerance. Once the threshold is reached or exceeded at some point of the time (exit time), the associated player is ruined. Both stochastic processes are being “observed” by a third party point stochastic process, over which the information regarding the status of both players is obtained. We succeed in these goals by arriving at closed form joint functionals of the named elements and processes. Furthermore, we also look into the game more closely by introducing an intermediate threshold (see a layer), which a losing player is to cross prior to his ruin, in order to analyze the game more scrupulously and see what makes the player lose the game.     

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.     

Partizan octal games: Partizan subtraction games

A subtraction gameS=(s ₁, ...,s _k)is a two-player game played with a pile of tokens where each player at his turn removes a number ofm of tokens providedmεS. The player first unable to move loses, his opponent wins. This impartial game becomes partizan if, instead of one setS, two finite setsS _L andS _R are given: Left removes tokens as specified byS _L, right according toS _R. We say thatS _L dominatesS _R if for all sufficiently large piles Left wins both as first and as second player. We exhibit a curious property of dominance and provide two subclasses of games in which a dominance relation prevails. We further prove that all partizan subtraction games areperiodic, and investigatepure periodicity.