A robust von Neumann minimax theorem for zero-sum games under bounded payoff uncertainty

The celebrated von Neumann minimax theorem is a fundamental theorem in two-person zero-sum games. In this paper, we present a generalization of the von Neumann minimax theorem, called robust von Neumann minimax theorem, in the face of data uncertainty in the payoff matrix via robust optimization approach. We establish that the robust von Neumann minimax theorem is guaranteed for various classes of bounded uncertainties, including the matrix 1-norm uncertainty, the rank-1 uncertainty and the columnwise affine parameter uncertainty.     

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.     

Cooperative games under bubbly uncertainty

The allocation problem of rewards/costs is a basic question for players, namely, individuals and companies that are planning cooperation under uncertainty. The involvement of uncertainty in cooperative game theory is motivated by the real world in which noise in observation and experimental design, incomplete information and vagueness in preference structures and decision-making play an important role. In this study, a new class of cooperative games, namely, the cooperative bubbly games, where the worth of each coalition is a bubble instead of a real number, is presented. Furthermore, a new solution concept, the bubbly core, is defined. Finally, the properties and the conditions for the non-emptiness of the bubbly core are given. The paper ends with a conclusion and an outlook to related and future studies.     

Identifying key missing data for inference under uncertainty

In many applications of knowledge-based systems, initial facts are insufficient to lead to any conclusion, and the systems need to ask users to provide more information. A question-asking strategy decides the questions to ask and their sequence. We present a question-asking strategy for Horn clause knowledge bases under uncertainties. The strategy selects questions quickly by considering both conclusion certainties and costs of reaching conclusions. The experiments on randomly generated knowledge bases show that the proposed strategy is significantly better than the contingent strategies being used with forward-chaining or backward-chaining procedures.     

Robust strategies for facility location under uncertainty

This paper considers a stochastic facility location problem in which multiple capacitated facilities serve customers with a single product, and a stockout probabilistic requirement is stated as a chance constraint. Customer demand is assumed to be uncertain and to follow either a normal or an ambiguous distribution. We study robust approximations to the problem in order to incorporate information about the random demand distribution in the best possible, computationally tractable way. We also discuss how a decision maker’s risk preferences can be incorporated in the problem through robust optimization. Finally, we present numerical experiments that illustrate the performance of the different robust formulations. Robust optimization strategies for facility location appear to have better worst-case performance than nonrobust strategies. They also outperform nonrobust strategies in terms of realized average total cost when the actual demand distributions have higher expected values than the expected values used as input to the optimization models.     

不确定条件下n人非合作博弈均衡点集的通有稳定性

基于经典博弈模型的Nash均衡点集的通有稳定性和具有不确定参数的n人非合作博弈均衡点的概念,探讨了具有不确定参数博弈的均衡点集的通有稳定性.参照Nash均衡点集稳定性的统一模式,构造了不确定博弈的问题空间和解空间,并证明了问题空间是一个完备度量空间,解映射是上半连续的,且解集是紧集（即usco（upper semicontinuous and compact-valued）映射）,得到不确定参数博弈模型的解集通有稳定性的相关结论.     

A relation between perfect equilibria in extensive form games and proper equilibria in normal form games

The concept of quasi-perfect equilibria for games in extensive form is introduced. It is shown that a proper equilibrium of a normal form game induces a quasi-perfect equilibrium in every extensive form game having this normal form.     

Mollifiers for games in normal form and the Harsanyi-Selten valuation function

The concepts of disruption and mollifiers ofCharnes/Rousseau/Seiford [1978] for games in characteristic function form are here extended to games in normal form. We show for a large class of games that theHarsanyi-Selten [1959] modification ofvon Neumann /Morgenstern's [1953] construction of a characteristic function for games in normal form, to take better account of “disruption” or “threat” possibilities, yields a constant mollifier. In general, it can be non-superadditive when the von Neumann-Morgenstern function is superadditive, and it also fails to take account of coalitional sizes. Our extended “homomollifier” concept does, and always yields a superadditive constant sum characteristic function.     

Finding mixed strategies with small supports in extensive form games

The complexity of algorithms that compute strategies or operate on them typically depends on the representation length of the strategies involved. One measure for thesize of a mixed strategy is the number of strategies in itssupport — the set of pure strategies to which it gives positive probability. This paper investigates the existence of “small” mixed strategies in extensive form games, and how such strategies can be used to create more efficient algorithms. The basic idea is that, in an extensive form game, a mixed strategy induces a small set ofrealization weights that completely describe its observable behavior. This fact can be used to show that for any mixed strategy μ, there exists a realization-equivalent mixed strategy µ′ whose size is at most the size of the game tree. For a player with imperfect recall, the problem of finding such a strategy µ′ (given the realization weights) is NP-hard. On the other hand, if μ is a behavior strategy, µ′ can be constructed from μ in time polynomial in the size of the game tree. In either case, we can use the fact that mixed strategies need never be too large for constructing efficient algorithms that search for equilibria. In particular, we construct the first exponential-time algorithm for finding all equilibria of an arbitrary two-person game in extensive form.     

The theory of normal form games from the differentiable viewpoint

An alternative definition of regular equilibria is introduced and shown to have the same properties as those definitions already known from the literature. The system of equations used to define regular equilibria induces a globally differentiable structure on the space of mixed strategies. Interpreting this structure as a vector field, called the Nash field, allows for a reproduction of a number of classical results from a differentiable viewpoint. Moreover, approximations of the Nash field can be used to suitably define indices of connected components of equilibria and to identify equilibrium components which are robust against small payoff perturbations.     

A normal form and schemes of quadratic forms

We present a solution of the problem of construction of a normal diagonal form for quadratic forms over a local principal ideal ring R = 2R with a QF-scheme of order 2. We give a combinatorial representation for the number of classes of projective congruence quadrics of the projective space over R with nilpotent maximal ideal. For the projective planes, the enumeration of quadrics up to projective equivalence is given; we also consider the projective planes over rings with nonprincipal maximal ideal. We consider the normal form of quadratic forms over the field of p-adic numbers. The corresponding QF-schemes have order 4 or 8. Some open problems for QF-schemes are mentioned. The distinguished finite QF-schemes of local and elementary types (of arbitrarily large order) are realized as the QF-schemes of a field. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 1, pp. 161–178, 2007.     

On some geometry and equivalence classes of normal form games

Equivalence classes of normal form games are defined using the discontinuities of correspondences of standard equilibrium concepts like correlated, Nash, and robust equilibrium, or risk dominance and rationalizability. Resulting equivalence classes are fully characterized and compared across different equilibrium concepts for 2 ×  2 games; larger games are also studied. It is argued that the procedure leads to broad and game-theoretically meaningful distinctions of games as well as to alternative ways of representing, comparing and testing equilibrium concepts.     

Distributionally robust scheduling on parallel machines under moment uncertainty

This paper investigates a distributionally robust scheduling problem on identical parallel machines, where job processing times are stochastic without any exact distributional form. Based on a distributional set specified by the support and estimated moments information, we present a min-max distributionally robust model, which minimizes the worst-case expected total flow time out of all probability distributions in this set. Our model doesn’t require exact probability distributions which are the basis for many stochastic programming models, and utilizes more information compared to the interval-based robust optimization models. Although this problem originates from the manufacturing environment, it can be applied to many other fields when the machines and jobs are endowed with different meanings. By optimizing the inner maximization subproblem, the min-max formulation is reduced to an integer second-order cone program. We propose an exact algorithm to solve this problem via exploring all the solutions that satisfy the necessary optimality conditions. Computational experiments demonstrate the high efficiency of this algorithm since problem instances with 100 jobs are optimized in a few seconds. In addition, simulation results convincingly show that the proposed distributionally robust model can hedge against the bias of estimated moments and enhance the robustness of production systems.     

Semi-cooperative strategies for differential games

The paper is concerned with a non-cooperative differential game for two players. We first consider Nash equilibrium solutions in feedback form. In this case, we show that the Cauchy problem for the value functions is generically ill-posed. Looking at vanishing viscosity approximations, one can construct special solutions in the form of chattering controls, but these also appear to be unstable. In the second part of the paper we propose an alternative semi-cooperative pair of strategies for the two players, seeking a Pareto optimum instead of a Nash equilibrium. In this case, we prove that the corresponding Hamiltonian system for the value functions is always weakly hyperbolic.Revised: May 2004     

A robust optimization model for multi-product two-stage capacitated production planning under uncertainty

Production planning (PP) is one of the most important issues carried out in manufacturing environments which seeks efficient planning, scheduling and coordination of all production activities that optimizes the company’s objectives. In this paper, we studied a two-stage real world capacitated production system with lead time and setup decisions in which some parameters such as production costs and customer demand are uncertain. A robust optimization model is developed to formulate the problem in which minimization of the total costs including the setup costs, production costs, labor costs, inventory costs, and workforce changing costs is considered as performance measure. The robust approach is used to reduce the effects of fluctuations of the uncertain parameters with regards to all the possible future scenarios. A mixed-integer programming (MIP) model is developed to formulate the related robust production planning problem. In fact the robust proposed model is presented to generate an initial robust schedule. The performance of this schedule could be improved against of any possible occurrences of uncertain parameters. A case from an Iran refrigerator factory is studied and the characteristics of factory and its products are discussed. The computational results display the robustness and effectiveness of the model and highlight the importance of using robust optimization approach in generating more robust production plans in the uncertain environments. The tradeoff between solution robustness and model robustness is also analyzed.     

On the approximability of adjustable robust convex optimization under uncertainty

In this paper, we consider adjustable robust versions of convex optimization problems with uncertain constraints and objectives and show that under fairly general assumptions, a static robust solution provides a good approximation for these adjustable robust problems. An adjustable robust optimization problem is usually intractable since it requires to compute a solution for all possible realizations of uncertain parameters, while an optimal static solution can be computed efficiently in most cases if the corresponding deterministic problem is tractable. The performance of the optimal static robust solution is related to a fundamental geometric property, namely, the symmetry of the uncertainty set. Our work allows for the constraint and objective function coefficients to be uncertain and for the constraints and objective functions to be convex, thereby providing significant extensions of the results in Bertsimas and Goyal (Math Oper Res 35:284–305, 2010) and Bertsimas et al. (Math Oper Res 36: 24–54, 2011b) where only linear objective and linear constraints were considered. The models in this paper encompass a wide variety of problems in revenue management, resource allocation under uncertainty, scheduling problems with uncertain processing times, semidefinite optimization among many others. To the best of our knowledge, these are the first approximation bounds for adjustable robust convex optimization problems in such generality.     

A new proof of existence of equilibria in infinite normal form games

In this note, we prove the existence of Nash equilibria in infinite normal form games with compact sets of strategies and continuous payoffs by constructing Nash mappings.