On stochastic games with additive reward and transition structure

In this paper, we introduce a new class of two-person stochastic games with nice properties. For games in this class, the payoffs as well as the transitions in each state consist of a part which depends only on the action of the first player and a part dependent only on the action of the second player.For the zero-sum games in this class, we prove that the orderfield property holds in the infinite-horizon case and that there exist optimal pure stationary strategies for the discounted as well as the undiscounted payoff criterion. For both criteria also, finite algorithms are given to solve the game. An example shows that, for nonzero sum games in this class, there are not necessarily pure stationary equilibria. But, if such a game possesses a stationary equilibrium point, then there also exists a stationary equilibrium point which uses in each state at most two pure actions for each player.     

A coalition formation value for games in partition function form

The coalition formation problem in an economy with externalities can be adequately modeled by using games in partition function form (PFF games), proposed by Thrall and Lucas. If we suppose that forming the grand coalition generates the largest total surplus, a central question is how to allocate the worth of the grand coalition to each player, i.e., how to find an adequate solution concept, taking into account the whole process of coalition formation. We propose in this paper the original concepts of scenario-value, process-value and coalition formation value, which represent the average contribution of players in a scenario (a particular sequence of coalitions within a given coalition formation process), in a process (a sequence of partitions of the society), and in the whole (all processes being taken into account), respectively. We give also two axiomatizations of our coalition formation value.     

New optimality conditions for average-payoff continuous-time Markov games in Polish spaces

This paper concerns two-person zero-sum games for a class of average-payoff continuous-time Markov processes in Polish spaces.The underlying processes are determined by transition rates that are allowed to be unbounded,and the payoff function may have neither upper nor lower bounds.We use two optimality inequalities to replace the so-called optimality equation in the previous literature.Under more general conditions,these optimality inequalities yield the existence of the value of the game and of a pair of ...     

A necessary and sufficient condition for Pareto-optimal security strategies in multicriteria matrix games

In this paper, a scalar game is derived from a zero-sum multicriteria matrix game, and it is proved that the solution of the new game with strictly positive scalarization is a necessary and sufficient condition for a strategy to be a Pareto-optimal security strategy (POSS) for one of the players in the original game. This is done by proving that a certain set, which is the extension of the set of security level vectors in the criterion function space, is convex and polyhedral. It is also established that only a finite number of scalarizations are necessary to obtain all the POSS for a player. An example is included to illustrate the main steps in the proof.This work was done while the author was a Research Associate in the Department of Electrical Engineering at the Indian Institute of Science and was financially supported by the Council of Scientific and Industrial Research, Delhi, India.The author wishes to express his gratefulness to Professor U. R. Prasad for helpful discussions and to two anonymous referees for suggestions which led to an improved presentation.     

Weighted shapley values for games in generalized characteristic function form

We study the family of weighted Shapley values for games in generalized characteristic function form. These values are defined and characterized.     

Methods for comparison of coalition influence on games in characteristic function form and their interrelationships

This paper extends two existent methods, called the blockability relation and the viability relation, for simple games to compare influence of coalitions, to those for games in characteristic function form, and shows that the newly defined relations satisfy transitivity and completeness. It is shown in this paper that for every game in characteristic function form the blockability relation and the viability relation have a complementary interrelationship.     

Optimal stopping and stochastic control differential games for jump diffusions

We study stochastic differential games of jump diffusions driven by Brownian motions and compensated Poisson random measures, where one of the players can choose the stochastic control and the other player can decide when to stop the system. We prove a verification theorem for such games in terms of a Hamilton–Jacobi–Bellman variational inequality. The results are applied to study some specific examples, including optimal resource extraction in a worst-case scenario, and risk minimizing optimal portfolio and stopping.     

The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands

By showing that there is an upper bound for the price of anarchyρ(Γ) for a non-atomic congestion game Γ with only separable cost maps and fixed demands, Roughgarden and Tardos show that the cost of forgoing centralized control is mild. This letter shows that there is an upper bound for ρ(Γ) in Γ for fixed demands with symmetric cost maps. It also shows that there is a weaker bound for ρ(Γ) in Γ with elastic demands.     

Relations between game parameters,value, and optimal strategy spaces in stochastic games and construction of games with given solution

Results of Bohnenblust, Karlin, and Shapley and results of Shapley and Snow, concerning solutions of matrix games, are extended to the class of discounted stochastic games. Prior to these extensions, relations between the game parameters, value, and optimal stationary strategy spaces are established. Then, the inverse problem of constructing stochastic games, given the solution, is considered.     

Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs

The problem of computing the smallest fixed point of an order-preserving map arises in the study of zero-sum positive stochastic games. It also arises in static analysis of programs by abstract interpretation. In this context, the discount rate may be negative. We characterize the minimality of a fixed point in terms of the nonlinear spectral radius of a certain semidifferential. We apply this characterization to design a policy iteration algorithm, which applies to the case of finite state and action spaces. The algorithm returns a locally minimal fixed point, which turns out to be globally minimal when the discount rate is nonnegative.     

Non zero-sum stochastic games in admission,service and routing control in queueing systems

The purpose of this paper is to investigate situations of non-cooperative dynamic control of queueing systems by two agents, having different objectives. The main part of the paper is devoted to analyzing a problem of an admission and a service (vacation) control. The admission controller has to decide whether to allow arrivals to occur. Once the queue empties, the server goes on vacation, and controls the vacations duration (according to the state and past history of the queue). The immediate costs for each controller are increasing in the number of customers, but no convexity assumptions are made. The controllers are shown to have a stationary equilibrium policy pair, for which each controller uses a stationary threshold type policy with randomization in at most one state. We then investigate a problem of a non-zero sum stochastic game between a router into several queues, and a second controller that allocates some extra service capacity to one of the queues. We establish the equilibrium of a policy pair for which the router uses the intuitive Join the shortest queue policy.     

Existence of equilibrium for generalized games in choice form and applications

This paper has two central aims: first, to provide simple conditions under which the generalized games in choice form and, consequently, the abstract economies admit equilibrium; second, to study the solvability of several types of systems of vector quasi-equilibrium problems as an application. Our work outlines that there still is much to be gained from using the results concerning the existence of equilibrium of games as tools of research for other optimization problems.     

Risk minimizing portfolios and HJBI equations for stochastic differential games

In this paper, we consider the problem to find a market portfolio that minimizes the convex risk measure of the terminal wealth in a jump diffusion market. We formulate the problem as a two player (zero-sum) stochastic differential game. To help us find a solution, we prove a theorem giving the Hamilton–Jacobi–Bellman–Isaacs (HJBI) conditions for a general zero-sum stochastic differential game in a jump diffusion setting. We then use the theorem to study particular risk minimization problems. Finally, we extend our approach to cover general stochastic differential games (not necessarily zero-sum), and we obtain similar HJBI equations for the Nash equilibria of such games.     

一种电子商务环境下耐用品的动态定价模型与策略

针对电子商务环境下消费者对价格歧视的抗拒问题,以及耐用品生命周期长、产品需求依赖于时间、价格等特点,提出了一种动态定价模型与策略。该模型通过构造转移概率矩阵,推导出在线消费者浏览到耐用品的不同价格状态下的概率,接着根据消费者多阶段效用函数分析消费者的购买决策行为,进而给出零售商利润达到最大化时的最优定价策略集合。为了验证模型与策略的有效性,通过数值模拟实验,分析模型主要参数变化对最优定价策略的影响。研究发现当效用折扣因子越高,零售商应该降低促销频率和高价格并且提高低价格,从而诱导高端消费者在高价格购买产品。折扣效用因子大小还决定了网上零售商是否要隐藏自己的促销概率。     

Uniform estimate for maximum of randomly weighted sums with applications to insurance risk theory

This paper obtains the uniform estimate for maximum of sums of independent and heavy-tailed random variables with nonnegative random weights,which can be arbi- trarily dependent of each other.Then the applications to ruin probabilities in a discrete time risk model with dependent stochastic returns are considered.     

Almost sure optimality and optimality in probability for stochastic linear-quadratic regulator with partial information

Partially observed linear-quadratic regulator is considered over an infinite time horizon. A limiting per unit time inequality is proved for the random difference between the cost corresponding to the feedback control based on Kalman filter estimates and the cost corresponding to an alternative control. Under suitable assumptions of admissibility for a control, it is shown that the feedback control mentioned above is asymptotically optimal almost surely and in probability     

A regularity result for a minimum problem in orlicz-sobolev spaces with applications in the study of the dirichlet problem for the operator of hencky-nadai theory

The existence and uniqueness of the solution to the problem of minimum for functionals generated by N- functions are obtained in Orlicz-Sobolev spaces. Applications for some functionals dealing with Hencky theory are given.