Perturbation theory for games in normal form and stochastic games

In this paper, the effect on values and optimal strategies of perturbations of game parameters (payoff function, transition probability function, and discount factor) is studied for the class of zero-sum games in normal form and for the class of stationary, discounted, two-person, zero-sum stochastic games.A main result is that, under certain conditions, the value depends on these parameters in a pointwise Lipschitz continuous way and that the sets of -optimal strategies for both players are upper semicontinuous multifunctions of the game parameters.Extensions to general-sum games and nonstationary stochastic games are also indicated.     

Preferred coalitions in cooperative differential games

There are many interesting situations which can be described by anN-person general-sum differential game. Such games are characterized by the fact that the strategy of each player depends upon reasonable assumptions about the strategies of the remaining players; and, thus, these games cannot be considered asN uncoupled optimal control problems. In such cases, we say that the game is not strictly competitive, but involves a mutual interest which makes it possible for all of the players to reduce their costs by cooperating with one another, provided the resulting agreement can be enforced. When cooperation is allowed and there are more than two players, there is always the question of whether all possible subcoalitions will be formed with equal ease. This work considers the situation in which a particular subcoalition is preferred. A theory of general-sum games with preferred coalitions is presented, together with constructive examples of alternative approaches which are unsatisfactory.     

Onn-person noncooperative multicriteria games described in strategic form

This paper undertakes the problem of multicriteria decision support in conflict situations described as a noncooperative game. Construction of such a decision support requires the development of the noncooperative game theory to be generalized for the multicriteria case. New theoretical results in this case are presented. Features of the multicriteria noncooperative games are shown with use of a duopoly model in case of two goods and two criteria of each player. Concepts of the decision support are discussed.     

Convex semi-infinite games

This paper introduces a generalization of semi-infinite games. The pure strategies for player I involve choosing one function from an infinite family of convex functions, while the set of mixed strategies for player II is a closed convex setC inR ⁿ. The minimax theorem applies under a condition which limits the directions of recession ofC. Player II always has optimal strategies. These are shown to exist for player I also if a certain infinite system verifies the property of Farkas-Minkowski. The paper also studies certain conditions that guarantee the finiteness of the value of the game and the existence of optimal pure strategies for player I.Many thanks are due to the referees for their detailed comments.     

Learning algorithms for repeated bimatrix Nash games with incomplete information

The purpose of this paper is to study a particular recursive scheme for updating the actions of two players involved in a Nash game, who do not know the parameters of the game, so that the resulting costs and strategies converge to (or approach a neighborhood of) those that could be calculated in the known parameter case. We study this problem in the context of a matrix Nash game, where the elements of the matrices are unknown to both players. The essence of the contribution of this paper is twofold. On the one hand, it shows that learning algorithms which are known to work for zero-sum games or team problems can also perform well for Nash games. On the other hand, it shows that, if two players act without even knowing that they are involved in a game, but merely thinking that they try to maximize their output using the learning algorithm proposed, they end up being in Nash equilibrium.This research was supported in part by NSF Grant No. ECS-87-14777.     

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.     

Computing the cores of strategic games with punishment–dominance relations

In this paper, we discuss the computational complexity of the strategic cores of a class of n-person games defined by Masuzawa (Int J Game Theory 32:479–483, 2003), which includes economic situations with monotone externality. We propose an algorithm for finding an α-core strategy of any game in this class which, counting the evaluation of a payoff for a strategy profile as one step, terminates after O(n ³· M) operations, where M is the maximum size of a strategy set of any of the n players. The idea underlying this method is based on the property of reduced games. This paper is based on a part of the doctoral dissertation of the author. The author thanks Mikio Nakayama, Masashi Umezawa, William Thomson, an associate editor, and the anonymous referee for their helpful comments, suggestions, and advice. Thanks are also due to Yukihiko Funaki for a comment that led the author to this subject. The author is responsible for errors and inadvertencies.     

Effective learning in the presence of adaptive counterparts

Adaptive learning algorithms (ALAs) is an important class of agents that learn the utilities of their strategies jointly with the maintenance of the beliefs about their counterparts' future actions. In this paper, we propose an approach of learning in the presence of adaptive counterparts. Our Q-learning based algorithm, called Adaptive Dynamics Learner (ADL), assigns Q-values to the fixed-length interaction histories. This makes it capable of exploiting the strategy update dynamics of the adaptive learners. By so doing, ADL usually obtains higher utilities than those of equilibrium solutions. We tested our algorithm on a substantial representative set of the most known and demonstrative matrix games. We observed that ADL is highly effective in the presence of such ALAs as Adaptive Play Q-learning, Infinitesimal Gradient Ascent, Policy Hill-Climbing and Fictitious Play Q-learning. Further, in self-play ADL usually converges to a Pareto efficient average utility.     

Almost global convergence to p-dominant equilibrium

A population of players repeatedly plays an n strategy symmetric game. Players update their strategies by sampling the behavior of k opponents and playing a best response to the distribution of strategies in the sample. Suppose the game possesses a -dominant strategy which is initially played by a positive fraction of the population. Then if the population size is large enough, play converges to the -dominant equilibrium with arbitrarily high probability. Received December 1999/Revised version November 2000     

Nash equilibria in random games

We consider Nash equilibria in 2‐player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; on m × n payoff matrices, it runs in time O(m²nloglog n + n²mloglog m) with high probability. Our result follows from showing that a 2‐player random game has a Nash equilibrium with supports of size two with high probability, at least 1 − O(1/log n). Our main tool is a polytope formulation of equilibria. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Existence of minmax points in discontinuous strategic games

In this note we prove the existence of minmax points for strategic form games where the sets of strategies are topological spaces and the payoff functions satisfy conditions weaker than continuity. The employed tools are the class of transfer weakly upper continuous functions and the class of weakly lower pseudocontinuous functions. An example shows that our result is of minimal character.     

Deposit games with reinvestment

In a deposit game coalitions are formed by players combining their capital. The proceeds of their investments then have to be divided among those players. The current model extends earlier work on capital deposits by allowing reinvestment of returns. Two specific subclasses of deposit games are introduced. These subclasses provide insight in two extreme cases. It is seen that each term dependent deposit game possesses a core element. Capital dependent deposit games are also shown to have a core element and even a population monotonic allocation scheme if the revenue function exhibits increasing returns to scale. Furthermore, it is shown that all superadditive games are deposit games if one allows for debt.     

A solution for noncooperative games

In this paper, we study solutions of strict noncooperative games that are played just once. The players are not allowed to communicate with each other. The main ingredient of our theory is the concept of rationalizing a set of strategies for each player of a game. We state an axiom based on this concept that every solution of a noncooperative game is required to satisfy. Strong Nash solvability is shown to be a sufficient condition for the rationalizing set to exist, but it is not necessary. Also, Nash solvability is neither necessary nor sufficient for the existence of the rationalizing set of a game. For a game with no solution (in our sense), a player is assumed to recourse to a standard of behavior. Some standards of behavior are examined and discussed.This work was sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and by the National Science Foundation under Grant No. MCS-75-17385-A01. The author is grateful to J. C. Harsanyi for his comments and to S. M. Robinson for suggesting the problem.     

A reinforcement learning process in extensive form games

The CPR (“cumulative proportional reinforcement”) learning rule stipulates that an agent chooses a move with a probability proportional to the cumulative payoff she obtained in the past with that move. Previously considered for strategies in normal form games (Laslier, Topol and Walliser, Games and Econ. Behav., 2001), the CPR rule is here adapted for actions in perfect information extensive form games. The paper shows that the action-based CPR process converges with probability one to the (unique) subgame perfect equilibrium.Received: October 2004     

Stay-in-a-set games

There exists a Nash equilibrium (ε-Nash equilibrium) for every n-person stochastic game with a finite (countable) state space and finite action sets for the players if the payoff to each player i is one when the process of states remains in a given set of states G _i and is zero otherwise. Received: December 2000     

Recall in extensive form games

This paper considers characterizations of perfect recall in extensive form games. It is shown that perfect recall can be expressed in terms of choices without any reference to infomation sets. When information sets are taken into account, it is decomposable into an ordering of information sets and that players do not forget what they knew nor what they did. Thus, if information sets are partially ordered, then perfect recall is implied by the player's inability to refine her information from the memory. Received: August 1997/final version: September 1998     

再制造市场OEM与UOEM的博弈与学习研究

在再制造利益的驱动下,一些非原始设备制造商(UOEM)欲进入再制造市场。为探究UOEM参与再制造的进入博弈,应用演化博弈理论构建了原始设备制造商(OEM)和UOEM策略选择的复制动态。研究表明:博弈双方的回收价格、UOEM排除障碍的成本会影响UOEM的策略选择;OEM选择默许而潜在的UOEM进入再制造品市场是二维动态系统唯一的演化稳定策略。进一步考虑了参与人的学习行为,将噪声项引入复制动态方程中,得到了一个非子博弈完美均衡,即当带着噪声项的OEM采取竞争策略时,进入者的最优策略是置身于市场之外。     

The principal-agent problem with evolutionary learning

We extend agency theory to incorporate bounded rationality of both principals and agents. In this study we define a simple version of the principal-agent game and examine it using object-oriented computer simulation. Player learning is simulated with a genetic algorithm model. Our results show that players of incentive games in highly uncertain environments may take on defensive strategies. These defensive strategies lead to equilibria which are inferior to Nash equilibria. If agents are risk averse, the principal may not be able to provide enough monetary compensation to encourage them to take risks. But principals may be able to improve system performance by identifying good performers and facilitating information exchange among agents.The authors would like to thank the anonymous referees for their helpful suggestions.