Differential game of optimal approach of two inertial pursuers to a noninertial evader

In this paper, the game of the optimal approach of two identical inertial pursuers to a noninertial evader is investigated. The duration of the game is fixed. The payoff functional is the distance between the evader and the closest pursuer when the game terminates. The value function is constructed for all possible positions of the game. The regions where the pursuit is one-to-one and the regions where it is essentially collective are described algorithmically. Some analogies between this game and the linear differential game with elliptical vectograms are indicated. It is noted that the focal surface and the dispersal surface are in proximity of one another.     

Differential games with a given value function

The set of solutions of a differential game with a terminal payoff functional is investigated. A method is obtained that allows us to establish whether a given function is a value of some differential game with a terminal payoff functional. The condition obtained is in fact the condition for the given function to be a minimax (viscosity) solution of some Hamilton-Jacobi equation with Hamiltonian homogeneous in the third variable. We also obtain a sufficient condition for a function to belong to the set of values of differential games with a terminal payoff function.     

On repeated games with incomplete information played by non-Bayesian players

Unlike in the traditional theory of games of incomplete information, the players here arenot Bayesian, i.e. a player does not necessarily have any prior probability distribution as to what game is being played. The game is infinitely repeated. A player may be absolutely uninformed, i.e. he may know only how many strategies he has. However, after each play the player is informed about his payoff and, moreover, he has perfect recall. A strategy is described, that with probability unity guarantees (in the sense of the liminf of the average payoff) in any game, whatever the player could guarantee if he had complete knowledge of the game.     

Crowding games are sequentially solvable

A sequential-move version of a given normal-form game Γ is an extensive-form game of perfect information in which each player chooses his action after observing the actions of all players who precede him and the payoffs are determined according to the payoff functions in Γ. A normal-form game Γ is sequentially solvable if each of its sequential-move versions has a subgame-perfect equilibrium in pure strategies such that the players' actions on the equilibrium path constitute an equilibrium of Γ.  A crowding game is a normal-form game in which the players share a common set of actions and the payoff a particular player receives for choosing a particular action is a nonincreasing function of the total number of players choosing that action. It is shown that every crowding game is sequentially solvable. However, not every pure-strategy equilibrium of a crowding game can be obtained in the manner described above. A sufficient, but not necessary, condition for the existence of a sequential-move version of the game that yields a given equilibrium is that there is no other equilibrium that Pareto dominates it. Received July 1997/Final version May 1998     

Potential theory for mean payoff games

The paper presents an O(mn2ⁿ log Z) deterministic algorithm for solving the mean payoff game problem, m and n being the numbers of arcs and vertices, respectively, in the game graph, and Z being the maximum weight (the weights are assumed to be integers). The theoretical basis for the algorithm is the potential theory for mean payoff games. This theory allows one to restate the problem in terms of solving systems of algebraic equations with minima and maxima. Also, in order to solve the mean payoff game problem, the arc reweighting technique is used. To this end, simple modifications, which do not change the set of winning strategies, are applied to the game graph; in the end, a trivial instance of the problem is obtained. It is shown that any game graph can be simplified by n reweightings. Bibliography: 16 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 340, 2006, pp. 61–75.     

Analytical solutions of N‐person games

The possibility of analytical solutions of N‐person games is presented. A simple formula provides valuable information about the outcomes of such games with linear payoff functions and Pavlovian agents. Experiments performed with our simulation tool for the multiagent stag hunt dilemma game are presented. For the case of Pavlovian agents the game has nontrivial but remarkably regular solutions. If both payoff functions are linear and the real solutions of Eq. (2) are both positive, then the analytical solutions are remarkably accurate. © 2012 Wiley Periodicals, Inc. Complexity, 2012     

Robust game theory

We present a distribution-free model of incomplete-information games, both with and without private information, in which the players use a robust optimization approach to contend with payoff uncertainty. Our ``robust game' model relaxes the assumptions of Harsanyi's Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call ``robust-optimization equilibrium,' to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an incomplete-information game subsume the ex post equilibria of the game and are, unlike the latter, guaranteed to exist when the game is finite and has bounded payoff uncertainty set. For arbitrary robust finite games with bounded polyhedral payoff uncertainty sets, we show that we can compute a robust-optimization equilibrium by methods analogous to those for identifying a Nash equilibrium of a finite game with complete information. In addition, we present computational results. The research of the author was partially supported by a National Science Foundation Graduate Research Fellowship and by the Singapore-MIT Alliance. The research of the author was partially supported by the Singapore-MIT Alliance.     

Optimal strategic reasoning with McNaughton functions

The aim of the paper is to explore strategic reasoning in strategic games of two players with an uncountably infinite space of strategies the payoff of which is given by McNaughton functions—functions on the unit interval which are piecewise linear with integer coefficients. McNaughton functions are of a special interest for approximate reasoning as they correspond to formulas of infinitely valued Lukasiewicz logic. The paper is focused on existence and structure of Nash equilibria and algorithms for their computation. Although the existence of mixed strategy equilibria follows from a general theorem (Glicksberg, 1952) [5], nothing is known about their structure neither the theorem provides any method for computing them. The central problem of the article is to characterize the class of strategic games with McNaughton payoffs which have a finitely supported Nash equilibrium. We give a sufficient condition for finite equilibria and we propose an algorithm for recovering the corresponding equilibrium strategies. Our result easily generalizes to n-player strategic games which don't need to be strictly competitive with a payoff functions represented by piecewise linear functions with real coefficients. Our conjecture is that every game with McNaughton payoff allows for finitely supported equilibrium strategies, however we leave proving/disproving of this conjecture for future investigations.     

Risk and quality control in a supply chain: competitive and collaborative approaches

This paper provides a quantitative and comparative economic and risk approach to strategic quality control in a supply chain, consisting of one supplier and one producer, using a random payoff game. Such a game is first solved in a risk-neutral framework by assuming that both parties are competing with each other. We show in this case that there may be an interior solution to the inspection game. A similar analysis under a collaborative framework is shown to be trivial and not practical, with a solution to the inspection game being an ‘all or nothing’ solution to one or both the parties involved. For these reasons, the sampling random payoff game is transformed into a Neyman–Pearson risk constraints game, where the parties minimize the expected costs subject to a set of Neyman–Pearson risk (type I and type II) constraints. In this case, the number of potential equilibria can be large. A number of such solutions are developed and a practical (convex) approach is suggested by providing an interior (partial sampling) solution for the collaborative case. Numerical examples are developed to demonstrate the procedure used. Thus, unlike theoretical approaches to the solution of strategic quality control random payoff games, the approach we construct is both practical and consistent with the statistical risk Neyman–Pearson approach.     

Optimal non-proportional reinsurance control and stochastic differential games

We study stochastic differential games between two insurance companies who employ reinsurance to reduce risk exposure. We consider competition between two companies and construct a single payoff function of two companies’ surplus processes. One company chooses a dynamic reinsurance strategy in order to maximize the payoff function while its opponent is simultaneously choosing a dynamic reinsurance strategy so as to minimize the same quantity. We describe the Nash equilibrium of the game and prove a verification theorem for a general payoff function. For the payoff function being the probability that the difference between two surplus reaches an upper bound before it reaches a lower bound, the game is solved explicitly.     

两人进化博弈策略的决定机制与应用研究

通过建立一般情况下的两人进化博弈模型,给出了系统均衡点对应的矩阵行列式和迹表达式的经济含义,分析了16种典型情形下的进化稳定策略,详细讨论了均衡点稳定性分析结果所对应的博弈双方决策过程,从策略权衡的视角揭示了策略选择的内在机制。研究结果表明:不同策略前提下的相对净支付决定了系统的进化稳定策略,对方的策略选择以及自身可选策略的支付比较是影响博弈主体策略选择的两个基本要素,博弈主体会趋向于选择在对方策略既定下能够带来更大支付的策略。最后以环境治理中地方政府与企业以及地方政府之间的博弈关系为例,从对称博弈和非对称博弈两方面阐明了本文所构建模型在政策设计中的应用价值:针对不同案例,只要明确了两人博弈的支付矩阵,就可以通过计算相对净支付确定博弈双方的行为演化规律和稳定策略,从而简化计算过程,更加直接和更为便捷地为政策设计提供理论参考。     

On a game of optimal pursuit of an object by two others

A game problem of the simple pursuit of one object by two others, the former having a speed advantage, is analyzed. The duration of the game is fixed. The payoff functional is the distance between the object being pursued and the pursuer closest to it when the game terminates. Similar problems were examined in /1–7/.     

Convergence conditions for the Brown-Robinson iterative method for bimatrix games

The article considers the convergence of the Brown-Robinson iterative method to find a mixed-strategy equilibrium in a bimatrix game. The known result on convergence to an equilibrium for a zero-sum game is generalized to a wider class of games that are reducible to zero-sum games by a composition of various transformations: addition of a constant to any column of the first-player payoff matrix; addition of a constant to any row in the second-player payoff matrix; multiplication of the payoff matrix by a positive constant α>0. Translated from Prikladnaya Matematika i Informatika, No. 2, pp. 69–83, 1999.     

集群搜索-规避对抗对策的概念和性质

讨论了集群搜索-规避对抗对策的概念，明确了对策双方的策略与最优策略的定义，给出了对策的支付函数及对策的解，讨论了最优策略及对策值的存在性。     

A game of optimal pursuit of one object by several

A differential game in which m dynamical objects pursue a single one is investigated. All the players perform simple motions. The termination time of the game is fixed. The controls of the first k (k ⩽ m) pursuers are subject to integral constraints and the controls of the other pursuers and the evader are subject to geometric constraints. The payoff of the game is the distance between the evader and the closest pursuer at the instant the game is over. Optimal strategies for the players are constructed and the value of the game is found.     

Cooperative games with large cores

A payoff vector in ann-person cooperative game is said to be acceptable if no coalition can improve upon it. The core of a game consists of all acceptable vectors which are feasible for the grand coalition. The core is said to be large if for every acceptable vectory there is a vectorx in the core withx?y. This paper examines the class of games with large cores.     

The Folk theorem for dominance solutions

The known variants of the Folk theorem characterize the sets of equilibria for repeated games. The present paper considers dominance solutions of finitely repeated games and discounted supergames with perturbed payoff functions. The paper shows that for a normal form game the set of dominance solution payoff vectors of the T-fold repetitions converges to the set of feasible and individually rational payoffs as T tends to infinity and the perturbation value tends to 0. A similar theorem is proved for supergames as the discount factor tends to 1. Received: May 1994/final version: September 1997     

The gold-mine game

The paper considers the following two-person zero-sum game. The minimizing player chooses to hide his gold and a mine in two distinct boxes from an infinite number of boxes labelled 1, 2, 3,.... The maximizing player now chooses to open the boxes in some order, and if he finds the gold before the mine the payoff to him is 1; otherwise, the payoff is zero. The game is solved in the sense of Kindler.     

Quitting games – An example

Quitting games are multi-player sequential games in which, at every stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; each player i then receives a payoff r _S ⁱ, which depends on the set S of players that did choose to quit. If the game never ends, the payoff to each player is zero.? We exhibit a four-player quitting game, where the “simplest” equilibrium is periodic with period two. We argue that this implies that all known methods to prove existence of an equilibrium payoff in multi-player stochastic games are therefore bound to fail in general, and provide some geometric intuition for this phenomenon. Received: October 2001