The effect of variety seeking behaviour on optimal product positioning

In this paper we develop a stochastic (first order Markovian) consumer choice model that represents variety seeking behaviour and we investigate the practical implications of this model for optimal product positioning relative to a zero order model that does not incorporate variety seeking. We show that the optimal positioning implications of a variety seeking process is indeed different than those of a (no-variety-seeking) zero order process. Based on intuition, one might expect increased variety seeking to imply that firms should increase the distance between their products in an attribute space. In fact, we show that this effect does occur for relatively low share brands. But just the opposite effect holds for relatively high share brands. That is, variety seeking behaviour generates a desire to more differentiation among low share brands, and a desire for less differentiation among high share brands.     

Closedness under Hart-Mas Colell reduction

We will find 3 maximal subclasses with respect to essential, superadditive and convex games, respectively such that a game is in one subclass, so are its reduced games.     

Approximate solutions for expanding search games on general networks

We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic “expanding search” paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs \(a_i\) such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper’s main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown.

     

Loss of skills in coordination games

This paper deals with 2-player coordination games with vanishing actions, which are repeated games where all diagonal payoffs are strictly positive and all non-diagonal payoffs are zero with the following additional property: At any stage beyond r, if a player has not played a certain action for the last r stages, then he unlearns this action and it disappears from his action set. Such a game is called an r-restricted game. To evaluate the stream of payoffs we use the average reward. For r = 1 the game strategically reduces to a one-shot game and for r ≥ 3 in Schoenmakers (Int Game Theory Rev 4:119–126, 2002) it is shown that all payoffs in the convex hull of the diagonal payoffs are equilibrium rewards. In this paper for the case r = 2 we provide a characterization of the set of equilibrium rewards for 2 × 2 games of this type and a technique to find the equilibrium rewards in m × m games. We also discuss subgame perfection.     

A Problem in Permutations: the Game of 'Mousetrap'

The game of 'Mousetrap, a problem in permutations, first introduced by Arthur Cayley in 1857 and independently addressed by Cayley and Adolph Steen in 1878, has been largely unexamined since. The game involves permutations of n cards numbered consecutively from 1 to n. The cards are laid out face up in some order and the game is played by counting on the cards, beginning the count with 1. If at any time the number of the count matches the number on the card, this is called a hit and the card is thrown out. The counting begins again with 1 on the next card and returns to the first card when the nth card is reached. Each time a card is hit, that card is removed and the counting starts over at 1. The game continues until all the cards have been hit and thrown out (the player wins) or until the counting reaches n with no cards having been hit (the cards win). The game is re-introduced here and a summary of both Cayley's and Steen's work is presented. Computer programs, written to generate the types of permutations dealt with by Steen, uncovered discrepancies in his work. Further examination of these discrepancies lead to the discovery of a combinatorial pattern of coefficients which Steen was unable to recognize because of his computational errors. Corrected versions of Steen's erroneous formulas are presented.     

Proper belief revision and rationalizability in dynamic games

In this paper we develop an epistemic model for dynamic games in which players may revise their beliefs about the opponents’ utility functions as the game proceeds. Within this framework, we propose a rationalizability concept that is based upon the following three principles: (1) at every instance of the game, a player should believe that his opponents are carrying out optimal strategies, (2) a player, at information set h, should not change his belief about an opponent’s relative ranking of two strategies s and s′ if both s and s′ could have led to h, and (3) the players’ initial beliefs about the opponents’ utility functions should agree on a given profile u of utility functions. Common belief in these events leads to the concept of persistent rationalizability for the profile u of utility functions. It is shown that for a given game tree with observable deviators and a given profile u of utility functions, every properly point-rationalizable strategy is a persistently rationalizable strategy for u. This result implies that persistently rationalizable strategies always exist for all game trees with observable deviators and all profiles of utility functions. We provide an algorithm that can be used to compute the set of persistently rationalizable strategies for a given profile u of utility functions. For generic games with perfect information, persistent rationalizability uniquely selects the backward induction strategy for every player.     

Isaacs' princess and monster game on the circle

The solution is given of a multistage pursuit-evasion game in which ablind pursuer searches for ablind evader within a finite set of locations arranged in a circle. The players traverse this set by transfering their positions, at each of a succession of instants, from the points which they occupy to ones which are adjacent to them. Some standard results of measure theory are used to construct the players' optimal strategies when the payoff to the evader is the time taken for the pursuer to find him or, more generally, an increasing function of this time.This work was carried out with the support of a CSIRO postgraduate studentship.     

On the existence of a minimum integer representation for?weighted voting systems

A basic problem in the theory of simple games and other fields is to study whether a simple game (Boolean function) is weighted (linearly separable). A second related problem consists in studying whether a weighted game has a minimum integer realization. In this paper we simultaneously analyze both problems by using linear programming. For less than 9 voters, we find that there are 154 weighted games without minimum integer realization, but all of them have minimum normalized realization. Isbell in 1958 was the first to find a weighted game without a minimum normalized realization, he needed to consider 12 voters to construct a game with such a property. The main result of this work proves the existence of weighted games with this property with less than 12 voters. This research was partially supported by Grant MTM 2006-06064 of “Ministerio de Ciencia y Tecnología y el Fondo Europeo de Desarrollo Regional” and SGRC 2005-00651 of “Generalitat de Catalunya”, and by the Spanish “Ministerio de Ciencia y Tecnología” programmes ALINEX (TIN2005-05446 and TIN2006-11345).     

Analyzing n-player impartial games

Combinatorial game theory is the study of two player perfect information games. While work has been done in the past on expanding this field to include n-player games we present a unique method which guarantees a single winner. Specifically our goal is to derive a function which, given an n-player game, is able to determine the winning player (assuming all n players play optimally). Once this is accomplished we use this function in analyzing a certain family of three player subtraction games along with a complete analysis of three player, three row Chomp. Furthermore we make use of our new function in producing alternative proofs to various well known two player Chomp games. Finally the paper presents a possible method of analyzing a two player game where one of the players plays a completely random game. As it turns out this slight twist to the rules of combinatorial game theory produces rather interesting results and is certainly worth the time to study further.     

The Sprague–Grundy function of the real game Euclid

The game Euclid, introduced and named by Cole and Davie, is played with a pair of nonnegative integers. The two players move alternately, each subtracting a positive integer multiple of one of the integers from the other integer without making the result negative. The player who reduces one of the integers to zero wins. Unfortunately, the name Euclid has also been used for a subtle variation of this game due to Grossman in which the game stops when the two entries are equal. For that game, Straffin showed that the losing positions (a,b) with a<b are precisely the same as those for Cole and Davie’s game. Nevertheless, the Sprague–Grundy functions are not the same for the two games. We give an explicit formula for the Sprague–Grundy function for the original game of Euclid and we explain how the Sprague–Grundy functions of the two games are related.     

Effort Games and the Price of Myopia

We consider Effort Games, a game‐theoretic model of cooperation in open environments, which is a variant of the principal‐agent problem from economic theory. In our multiagent domain, a common project depends on various tasks; carrying out certain subsets of the tasks completes the project successfully, while carrying out other subsets does not. The probability of carrying out a task is higher when the agent in charge of it exerts effort, at a certain cost for that agent. A central authority, called the principal, attempts to incentivize agents to exert effort, but can only reward agents based on the success of the entire project. We model this domain as a normal form game, where the payoffs for each strategy profile are defined based on the different probabilities of carrying out each task and on the boolean function that defines which task subsets complete the project, and which do not. We view this boolean function as a simple coalitional game, and call this game the underlying coalitional game. We suggest the Price of Myopia (PoM) as a measure of the influence the model of rationality has on the minimal payments the principal has to make in order to motivate the agents in such a domain to exert effort. We consider the computational complexity of testing whether exerting effort is a dominant strategy for an agent, and of finding a reward strategy for this domain, using either a dominant strategy equilibrium or using iterated elimination of dominated strategies. We show these problems are generally #P‐hard, and that they are at least as computationally hard as calculating the Banzhaf power index in the underlying coalitional game. We also show that in a certain restricted domain, where the underlying coalitional game is a weighted voting game with certain properties, it is possible to solve all of the above problems in polynomial time. We give bounds on PoM in weighted voting effort games, and provide simulation results regarding PoM in another restricted class of effort games, namely effort games played over Series‐Parallel Graphs (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Deterministic Time-inconsistent Optimal Control Problems - an Essentially Cooperative Approach

A general deterministic time-inconsistent optimal control problem is formulated for ordinary differential equations. To find a time-consistent equilibrium value function and the corresponding time-consistent equilibrium control, a non-cooperative N-person differential game (but essentially cooperative in some sense) is introduced. Under certain conditions, it is proved that the open-loop Nash equilibrium value function of the N -person differential game converges to a time-consistent equilibrium value function of the original problem, which is the value function of a time-consistent optimal control problem. Moreover, it is proved that any optimal control of the time-consistent limit problem is a time-consistent equilibrium control of the original problem.     

Finitely repeated prisoners’ dilemma experiments without a commonly known end

Using a symmetric two-player prisoners’ dilemma as base game, each player receives a signal for the number of rounds to be played with the same partner. One of these signals is the true number of rounds R while the other is R − 5. Thus both players know that the game has a finite end. They both know that the opponent knows this, but the finite end is not commonly known. As a consequence, both mutual defection and mutual cooperation until the second last round are subgame perfect equilibrium outcomes. We find experimental evidence that many players do in fact cooperate beyond their individual signal round.     

Embracing the giant component

Consider a game in which edges of a graph are provided a pair at a time, and the player selects one edge from each pair, attempting to construct a graph with a component as large as possible. This game is in the spirit of recent papers on avoiding a giant component, but here we embrace it. We analyze this game in the offline and online setting, for arbitrary and random instances, which provides for interesting comparisons. For arbitrary instances, we find that the competitive ratio (the best possible solution value divided by best possible online solution value) is large. For “sparse” random instances the competitive ratio is also large, with high probability (whp); If the instance has ¼(1 + ε)n random edge pairs, with 0 < ε ≤ 0.003, then any online algorithm generates a component of size O((log n)^3/2) whp , while the optimal offline solution contains a component of size Ω(n) whp . For “dense” random instances, the average‐case competitive ratio is much smaller. If the instance has ½(1 ? ε)n random edge pairs, with 0 < ε ≤ 0.015, we give an online algorithm which finds a component of size Ω(n) whp . © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Endogenous timing in duopoly: experimental evidence

In this paper we experimentally investigate Cournot duopolies with an extended timing game. The timing game has observable delay, that is, firms announce a production period (one out of two periods) and then they produce in the announced sequence. Theory predicts simultaneous production in the first period. With random matching we find that, given the actual experimental behavior in the subgames, subjects play a timing game more akin to a coordination game with two symmetric equilibria rather than the predicted game with a dominant strategy to produce early. As a result, a substantial proportion of subjects choose the second period.     

Values and potential of games with cooperation structure

Games with cooperation structure are cooperative games with a family offeasible coalitions, that describes which coalitions can negotiate in the game. We study a model ofcooperation structure and the corresponding restricted game, in which the feasible coalitions are those belonging to apartition system. First, we study a recursive procedure for computing the Hart and Mas-Colell potential of these games and we develop the relation between the dividends of Harsanyi in the restricted game and the worths in the original game. The properties ofpartition convex geometries are used to obtain formulas for theShapley andBanzhaf values of the players in the restricted game in terms of the original gamev. Finally, we consider the Owen multilinear extension for the restricted game.The author is grateful to Paul Edelman, Ulrich Faigle and the referees for their comments and suggestions. The proof of Theorem 1 was proposed by the associate editor's referee.     

On finding the nucleolus of an n-person cooperative game

Kohlberg (1972) has shown how the nucleolus for ann-person game with side-payments may be found by solving a single minimization LP in case the imputation space is a polytope. However the coefficients in the LP have a very wide range even for problems with 3 or 4 players. Therefore the method is computationally viable only for small problems on machines with finite precision. Maschler et al. (1979) find the nucleolus by solving a sequence of minimization LPs with constraint coefficients of either –1, 0 or 1. However the number of LPs to be solved is o(4 ⁿ ). In this paper, we show how to find the nucleolus by solving a sequence of o(2 ⁿ ) LPs whose constraint coefficients are –1, 0 or 1.     

On computational complexity of membership test in flow games and linear production games

Let Γ≡(N,v) be a cooperative game with the player set N and characteristic function v: 2^N→R. An imputation of the game is in the core if no subset of players could gain advantage by splitting from the grand coalition of all players. It is well known that, for the flow game (and equivalently, for the linear production game), the core is always non-empty and a solution in the core can be found in polynomial time. In this paper, we show that, given an imputation x, it is NP-complete to decide x is not a member of the core, for the flow game. And because of the specific reduction we constructed, the result also holds for the linear production game. Received: October 2000/Final version: March 2002     

The Rényi–Ulam pathological liar game with a fixed number of lies

The q-round Rényi–Ulam pathological liar game with k lies on the set [n]{1,…,n} is a 2-player perfect information zero sum game. In each round Paul chooses a subset A[n] and Carole either assigns 1 lie to each element of A or to each element of [n]A. Paul wins if after q rounds there is at least one element with k or fewer lies. The game is dual to the original Rényi–Ulam liar game for which the winning condition is that at most one element has k or fewer lies. Define to be the minimum n such that Paul can win the q-round pathological liar game with k lies and initial set [n]. For fixed k we prove that is within an absolute constant (depending only on k) of the sphere bound, ; this is already known to hold for the original Rényi–Ulam liar game due to a result of J. Spencer.