Search

Parrondo's games are essentially Markov games. They belong to the same class as Snakes and Ladders. The important distinguishing feature of Parrondo's games is that the transition probabilities may vary in time. It is as though "snakes," "ladders" and "dice" were being added and removed while the game was still in progress. Parrondo's games are not homogeneous in time and do not necessarily settle down to an equilibrium. They model non-equilibrium processes in physics. We formulate Parrondo's games as an inhomogeneous sequence of Markov transition operators, with rewards. Parrondo's "paradox" is shown to be equivalent to saying that the expected value of the reward, from the whole process, is not a linear function of the Markov operators. When we say that a game is "winning" or "losing" then we must be careful to include the whole process in our definition of the word "game." Specifically, we must include the time varying probability vector in our calculations.We give practical rules for calculating the expected value of the return from sequences of Parrondo's games. We include a worked example and a comparison between the theory and a simulation. We apply visualization techniques, from physics and engineering, to an inhomogeneous Markov process and show that the limiting set or "attractor" of this process has fractal geometry. This is in contrast to the relevant theory for homogeneous Markov processes where the stable, equilibrium limiting set is a single point in the state space.We show histograms of simulations and describe methods for calculating the capacity dimension and the moments of the fractal attractors. We indicate how to construct optimal forms of Parrondo's games and describe a symmetrical family of games which includes the optimal form, as a limiting case.We investigate the fractal geometry of the attractors for this symmetrical family of games. The resulting geometry is very interesting, even beautiful. [ABSTRACT FROM AUTHOR]

Queueing phenomena, along with many related decision problems, are well known to all of us from daily situations. We often need to answer questions concerning whether to queue or not, where to queue, how long to queue etc. In networking applications, both in road traffic as well as in telecommunication networks, individuals or some central controllers are frequently faced with similar questions. These decisions have often to be taken in a randomly changing environment, in a decentralized way, and with partial information. This gives rise to many challenging problems in dynamic games. We shall describe in this overview some generic queueing problems (both static and dynamic) that require game theoretic models and solutions. [ABSTRACT FROM AUTHOR]

A version of John Conway's game of Life is presented where the normal binary values of the cells are replaced by oscillators which can represent a superposition of states. The original game of Life is reproduced in the classical limit, but in general additional properties not seen in the original game are present that display some of the effects of a quantum mechanical Life. In particular, interference effects are seen. [ABSTRACT FROM AUTHOR]

It has been shown that it is possible to construct two games that when played individually lose, but alternating randomly or deterministically between them can win. This apparent paradox has been dubbed "Parrondo's paradox." The original games are capital-dependent, which means that the winning and losing probabilities depend on how much capital the player currently has. Recently, new games have been devised, that are not capital-dependent, but historydependent. We present some analytical results using discrete-time Markovchain theory, which is accompanied by computer simulations of the games. [ABSTRACT FROM AUTHOR]

In this paper, we provide an introduction to quantum game theory through discussion of ways of converting classical games into the quantum regime. We illustrate how a quantum-based approach can simulate all possible classical game histories in parallel, for the example of Parrondo's games. [ABSTRACT FROM AUTHOR]

In the original version of Parrondo's paradox, two losing sequences of games of chance are combined to form a winning sequence. The games in the first sequence depend on a single parameter p, while those in the second depend on two parameters p1 and p2. The paradox is said to occur because there exist choices of p, p1 and p2 such that the individual sequences of games are losing but a sequence constructed by choosing randomly between the games at each step is winning. At first sight, such behavior seems surprising. However, we contend in this paper that it should not be seen as surprising. On the contrary, we showthat such behaviour is typical in situations in which we randomly create a sequence from games whose winning regions can be defined on the same parameter space. Before we discuss this issue, we investigate in some detail the issue of when sequences of games, such as those proposed by Parrondo, should be considered to be winning, losing or fair. [ABSTRACT FROM AUTHOR]

This paper models adaptive learning behavior in a simple coordination game that Van Huyck, Cook and Battalio (1994) have investigated in a controlled laboratory setting with human subjects. We consider how populations of arti- ficially intelligent players behave when playing the same game. We use the genetic programming paradigm, as developed by Koza (1992, 1994), to model how a population of players might learn over time. In genetic programming one seeks to breed and evolve highly fit computer programs that are capable of solving a given problem. In our application, each computer program in the population can be viewed as an individual agent's forecast rule. The various forecast rules (programs) then repeatedly take part in the coordination game evolving and adapting over time according to principles of natural selection and population genetics.We argue that the genetic programming paradigm that we use has certain advantages over other models of adaptive learning behavior in the context of the coordination game that we consider. We find that the pattern of behavior generated by our population of artificially intelligent players is remarkably similar to that followed by the human subjects who played the same game. In particular, we find that a steady state that is theoretically unstable under a myopic, best-response learning dynamic turns out to be stable under our genetic-programming-based learning system, in accordance with Van Huyck et al.'s (1994) finding using human subjects. We conclude that genetic programming techniques may serve as a plausible mechanism for modeling human behavior, and may also serve as a useful selection criterion in environments with multiple equilibria. [ABSTRACT FROM AUTHOR]

In a recent paper, Pan and Başar [19] have studied the H∞ control of large scale Jump Linear systems in which the transitions of the jump Markov chain can be separated into sets having strong and weak interactions. They obtained an approximating reduced-order aggregated problem which is the limit as the rate of transitions of the faster time scale (which is a multiple of some parameter 1/∈) goes to infinity. In this paper we further investigate the solution of that problem as a function of the parameter ϵ. We show that the related optimal feedback policy and the value admit a Taylor series in terms of ϵ, and we compute its coefficients. [ABSTRACT FROM AUTHOR]

In this paper, we study the linear quadratic Nash games for infinite horizon singularly perturbed systems (SPS). In order to solve the generalized algebraic Lyapunov equation (GALE) corresponding to the generalized Lyapunov iterations, we propose a new algorithm which is based on the fixed point iterations. Furthermore, we also propose a new algorithm which is based on the Kleinman algorithm for solving the generalized cross-coupled algebraic Riccati equations (GCARE). It is shown that the resulting algorithm guarantees the quadratic convergence. [ABSTRACT FROM AUTHOR]

We develop a mathematical model within a game theoretical framework to capture the flow control problem for variable rate traffic at a bottleneck node. In this context, we also address various issues such as pricing and allocation of a single resource among a given number of users. We obtain a distributed, end-to-end flow control using cost functions defined as the difference between particular pricing and utility functions. We prove the existence and uniqueness of a Nash equilibrium for two different utility functions. The paper also discusses three distributed update algorithms, parallel, random and gradient update, which are shown to be globally stable under explicitly derived conditions. The convergence properties and robustness of each algorithm are studied through extensive simulations. [ABSTRACT FROM AUTHOR]

In this paper we develop two new parallel algorithms for differential games based on the principle of "data replication". This technique is efficient on distributed memory architectures such as IBM/PS2 or Digital Alpha and is coupled with a domain decomposition techniques to construct an approximation scheme for the Isaacs equation in ℝn. The algorithms are presented for a 2-domain decomposition and some hints are given for the case of d subdomains having crossing points. The above parallel algorithms have the same fixed point as the serial algorithm so that convergence to the viscosity solution of the Isaacs equation is guaranteed by previous results. The efficiency of the above algorithms is discussed analyzing some numerical tests which include the homicidal chauffeur game. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to compare two ways of modelling exploitation of common renewable resource by a large group of players. [ABSTRACT FROM AUTHOR]

This paper exposes in voluntarily simple terms the concept of S-adapted equilibrium introduced to represent and compute economic equilibria on stochastic markets. A model of the European gas market, that has been at the origin of the introduction of the concept, is recalled in this paper and the results obtained in 1987, when the contingent equilibrium has been computed for a time horizon extending until 2020, are compared with the observed trend in these markets over the last two decades. The information structure subsumed by this concept of S-adapted strategies is then analyzed, using different paradigms of dynamic games. The paper terminates with some open and intriguing questions related to the time consistency and subgame perfectness of the dynamic equilibrium thus introduced. [ABSTRACT FROM AUTHOR]

We adopt the robust control, or game theoretic, approach of [5] to option pricing. In this approach, uncertainty is described by a restricted set of possible price trajectories, without endowing this set with any probability measure. We seek a hedge against every possible price trajectory. In the absence of transaction costs, the continuous trading theory leads to a very simple differential game, but to an uninteresting financial result, as the hedging strategy obtained lacks robustness to the unmodeled transaction costs. (A feature avoided by the classical Black and Scholes theory through the use of unbounded variation cost trajectories. See [5].) We therefore introduce transaction costs into the model. We examine first the continuous time model. Its mathematical complexity makes it beyond a complete solution at this time, but the partial results obtained do point to a robust strategy, and as a matter of fact justify the second part of the paper. In that second part, we examine the discrete time theory, deemed closer to a realistic trading strategy. We introduce transaction costs into the model from the outset and derive a pricing equation, which can be seen as a discretization of the quasi variational inequality of the continuous time theory. The discrete time theory is well suited to a numerical solution. We give some numerical results. In the particular case where the transaction costs are null, we recover our theory of [5], and in particular the Cox, Ross and Rubinstein formula when the contingent claim is a convex function of the terminal price of the underlying security. [ABSTRACT FROM AUTHOR]

The existence of Nash equilibria is investigated for one-stage and two-stage rent-seeking games with endogenous rent which depends on the aggregate expenditure by all rent-seeking agents such as individuals, firms or countries. Under reasonable assumptions on lottery production functions and rent function, both games turn out to have a unique equilibrium. The conditions for the equilibrium aggregate expenditure by all agents to increase in the first stage and for the total rent over two stages to dissipate are derived for the two-stage rent-seeking games. [ABSTRACT FROM AUTHOR]

An evolutionary game with three players — trade unions, financial investors and firms — is presented where each player has a short-term and a long-term maximizing strategy at hand. The short-term strategy maximizes current payoffs without taking into account benefits from future cooperation while long-term strategies depend on the cooperative behavior of the other players. We first determine equilibria arising in the static game and determine under which conditions long-term cooperation may emerge. We then endogenize the stochastic environment, making it subject to the strategies selected and show how additional equilibria and strategy cycles arise in an evolutionary set-up. [ABSTRACT FROM AUTHOR]

A mathematical model of competitive selection of the applicants for a post is considered. There are N applicants with similar qualifications on an interview list. The applicants come in random order and their salary demands are distinct. Two managers, I and II, interview them one at a time. The aim of the manager is to obtain the applicant who demands minimal salary. When both managers want to accept the same candidate, then some rule of assignment to one of the managers is applied. Any candidate hired by a manager will accept the offer with some given probability. A candidate can be hired only at the moment of his appearance and can be accepted at that moment. At each moment n one candidate is presented. The considered problem is a generalization of the best choice problem with uncertain employment and its game version with priority or random priority. The general stopping game model is constructed. The algorithms of construction of the game value and the equilibrium strategies are given. An example is solved. [ABSTRACT FROM AUTHOR]

A bargaining problem with two players, Labor (player L) and Management (player M) is considered. The players must decide the monthly wage paid to L by M. At the beginning players L and M submit their offers x and y. If x ≤ y there is an agreement at (x + y)/2. If not, the arbiter is called in and he chooses the offer which is nearest to his solution α. The arbiter imposes a solution α which is concentrated in two points with probabilities p = 1/2. The equilibrium in the arbitration game among pure and mixed strategies is derived. [ABSTRACT FROM AUTHOR]

We study optimal static routing problems in open multiclass networks with state-independent arrival and service rates. Our goal is to study the uniqueness of optimal routing under different scenarios. We consider first the overall optimal policy, that is the routing policy whereby the overall mean cost of a job is minimized. We then consider an individually optimal policy whereby jobs are routed so that each job may feel that its own expected cost is minimized if it knows the mean cost for each path. This is related to the Wardrop equilibrium concept in a multiclass framework. We finally study the case of class optimization, in which each of several classes of jobs tries to minimize the averaged cost per job within that class; this is related to the Nash equilibrium concept. For all three settings, we show that the routing decisions at optimum need not be unique, but that the utilizations in some large class of links are uniquely determined. [ABSTRACT FROM AUTHOR]

A non-zero-sum n-stage game version of a full-information best-choice problem under expected net value (ENV) maximization is analyzed and the solutions are obtained in some special cases of 2-person and 3-person games. The essential feature contained in this multistage game is the fact that the players have their own weights by which at each stage one player's desired decision is preferred to the opponent's one by drawing a lottery. [ABSTRACT FROM AUTHOR]

A zero-sum game version of the full-information best choice problem is considered. Two players observe sequentially a stream of iid random variables (objects) from a known continuous distribution appearing according to some renewal process with the object of choosing the largest one. The horizon of observation is a positive random variable independent of objects. The observation of the random variables is imperfect and the players are informed only whether the object is greater than or less than some levels specified by both of them. Each player can choose at most one object. If both want to accept the same object, a random assignment mechanism is used. If some Player accepts an object, the other Player can change his level and continues the game alone. A similar game with discrete time and random number of objects is considered as a dual problem. The normal form of the game is derived. For the Poisson stream and the exponential horizon the value of the game and the form of the equilibrium strategy are obtained. In discrete-time case a game with geometric number of objects is completely solved. [ABSTRACT FROM AUTHOR]

We survey recent results on the existence of the value in zero-sum stopping games with discrete and continuous time, and on the existence of ɛ-equilibria in nonzero-sum games with discrete time. [ABSTRACT FROM AUTHOR]

We consider stopping games for Markov chains in the formulation introduced by Dynkin [6]. Two players observe a Markov sequence and may stop it at any stage. When the chain is stopped the game terminates and Player 1 receives from Player 2 a sum depending on the player who stopped the chain and on its current state. If the game continues infinitely, then Player 1 gets "the payoff at infinity" depending on the "limiting" behavior of the chain trajectory. We describe the structure of solutions for a class of stopping games with a countable state space and nonnegative payoffs. The payoff is equal to zero if Player 1 stops the chain but not Player 2. These solutions require using of randomized stopping rules. We study an extent of dependence of the value for these games on the "the payoff at infinity". It turns out that this extent is determined with the "limiting" behavior of payoffs and with the transition structure of the chain. [ABSTRACT FROM AUTHOR]

The many-player game of selling an asset, introduced by Sakaguchi and extended to monotone voting procedures by Yasuda, Nakagami and Kurano, is reviewed. Conditions for a unique equilibrium among stationary threshold strategies are given. [ABSTRACT FROM AUTHOR]

Astopping game problem is formulated by cooperating with fuzzy stopping time in a decision environment. The dynamic fuzzy system is a fuzzification version of a deterministic dynamic system and the move of the game is a fuzzy relation connecting between two fuzzy states.We define a fuzzy stopping time using several degrees of levels and instances under a monotonicity property, then an "expectation" of the terminal fuzzy state via the stopping time. By inducing a scalarization function (a linear ranking function) as a payoff for the game problem we will evaluate the expectation of the terminal fuzzy state. In particular, a two-person zero-sum game is considered in case its state space is a fuzzy set and a payoff is ordered in a sense of the fuzzy max order. For both players, our aim is to find the equilibrium point of a payoff function. The approach depends on the interval analysis, that is, manipulating a class of sets arising from α-cut of fuzzy sets. We construct an equilibrium fuzzy stopping time under some conditions. [ABSTRACT FROM AUTHOR]

The paper is concerned with two-person nonzero-sum stopping games in which pairs of randomized stopping times are game strategies. For a general form of reward functions, existence of Nash equilibrium strategies is proved under some restrictions for three types of games: quasi-finite-horizon, random-horizon and infinite-horizon games. [ABSTRACT FROM AUTHOR]

In this paper we investigate the existence and turnpike properties of overtaking Nash equilibria for an infinite horizon dynamic game in which the dynamic constraints are described by linear evolution equations in a Hilbert space. [ABSTRACT FROM AUTHOR]

In this paper the definition of cooperative game in characteristic function form is given. The notions of optimality principle and solution concepts based on it are introduced. The new concept of "imputation distribution procedure" (IDP) is defined and connected with the basic definitions of time-consistency and strong time-consistency. Sufficient conditions of the existence of time-consistent solutions are derived. For a large class of games where these conditions cannot be satisfied, the regularization procedure is developed and new c.f. constructed. The "regularized" core is defined and its strong time-consistency proved. [ABSTRACT FROM AUTHOR]

We use in this paper the viability/capturability approach for studying the problem of characterizing the dynamic core of a dynamic cooperative game defined in a characteristic function form. In order to allow coalitions to evolve, we embed them in the set of fuzzy coalitions. Hence, we define the dynamic core as a set-valued map associating with each fuzzy coalition and each time the set of allotments is such that their payoffs at that time to the fuzzy coalition are larger than or equal to the one assigned by the characteristic function of the game. We shall characterize this core through the (generalized) derivatives of a valuation function associated with the game. We shall provide its explicit formula, characterize its epigraph as a viable-capture basin of the epigraph of the characteristic function of the fuzzy dynamical cooperative game, use the tangential properties of such basins for proving that the valuation function is a solution to a Hamilton-Jacobi-Isaacs partial differential equation and use this function and its derivatives for characterizing the dynamic core. [ABSTRACT FROM AUTHOR]

We present a generalization of Amir's continuous model of nonsymmetric infinite-horizon discounted stochastic game of capital accumulation. We show that the game has a pure-strategy equilibrium in strategies that are nondecreasing and have Lipschitz property. To prove that, we use a technique based on an approximation of continuous model by the analogous discrete one. [ABSTRACT FROM AUTHOR]

We discuss the risk-sensitive Nash equilibrium concept in static non-cooperative games and two-stage stochastic games of resource extraction. Two equilibrium theorems are established for the latter class of games. Provided examples explain the meaning of risk-sensitive equilibria in games with random moves. [ABSTRACT FROM AUTHOR]

Two players hold money and bid each day for a nondurable consumer good whose worth to each player is measured by a concave utility function. The money recirculates to the players according to a rule that treats them symmetrically. When the total reward is discounted and the discount factor is small, there is a Nash equilibrium in which the players make large bids. For a discount factor close to one and also for a game with long run average reward, there is a Nash equilibrium with small bids. [ABSTRACT FROM AUTHOR]

In repeated games where the payoff is accumulated along the play, the players face a problem since they have to take into account the impact of their choices both on the current payoff and on the future of the game. [ABSTRACT FROM AUTHOR]

Zero-sum stochastic games with the expected average cost criterion and unbounded stage cost are studied. It is assumed that the transition probabilities of the Markov chains induced by stationary strategies satisfy a certain geometric drift condition. Under additional assumptions concerning especially the existence of ε-optimal strategies in corresponding one-stage games it is shown that the average optimality equation has a solution and that both players have ε-optimal stationary strategies. [ABSTRACT FROM AUTHOR]

We describe conditions for the existence of a stationary Markovian equilibrium when total production or total endowment is a random variable. Apart from regularity assumptions, there are two crucial conditions: (i) low information—agents are ignorant of both total endowment and their own endowments when they make decisions in a given period, and (ii) proportional endowments—the endowment of each agent is in proportion, possibly random, to the total endowment. When these conditions hold, there is a stationary equilibrium. When they do not hold, such an equilibrium need not exist. [ABSTRACT FROM AUTHOR]