Pure Nash equilibria in finite two-person non-zero-sum games

In this paper we study bimatrix games. The payoff matrices have properties closely related to concavity of functions. For such games we find sufficient conditions for the existence of pure Nash equilibria.     

Feedback strategies with finite memory in differential games

It is shown that, in differential games, strategies can be defined for the players in such a way that their controls depend, for each timet, on a finite section of the past of the trajectoryx(t). In particular,s-delay,r-memory strategies can be defined as in the Varaiya-Lin approach. It is shown that, for deterministic differential games with terminal payoff, the upper and lower values of the game so defined, are independent of the lengthr of the memory. Lettingr 0, a feedback strategy is obtained which depends only on the present (and infinitesimal past) of the trajectoryx(t).     

Block band Toeplitz preconditioners derived from generating function approximations: analysis and applications

We are concerned with the study and the design of optimal preconditioners for ill-conditioned Toeplitz systems that arise from a priori known real-valued nonnegative generating functions f(x,y) having roots of even multiplicities. Our preconditioned matrix is constructed by using a trigonometric polynomial θ(x,y) obtained from Fourier/kernel approximations or from the use of a proper interpolation scheme. Both of the above techniques produce a trigonometric polynomial θ(x,y) which approximates the generating function f(x,y), and hence the preconditioned matrix is forced to have clustered spectrum. As θ(x,y) is chosen to be a trigonometric polynomial, the preconditioner is a block band Toeplitz matrix with Toeplitz blocks, and therefore its inversion does not increase the total complexity of the PCG method. Preconditioning by block Toeplitz matrices has been treated in the literature in several papers. We compare our method with their results and we show the efficiency of our proposal through various numerical experiments.This research was co-funded by the European Union in the framework of the program “Pythagoras I” of the “Operational Program for Education and Initial Vocational Training” of the 3rd Community Support Framework of the Hellenic Ministry of Education, funded by national sources (25%) and by the European Social Fund - ESF (75%). The work of the second and of the third author was partially supported by MIUR (Italian Ministry of University and Research), grant number 2004015437.     

Gauss legendre quadrature formulas over a tetrahedron

In this article we consider the Gauss Legendre Quadrature method for numerical integration over the standard tetrahedron: {(x, y, z)|0 ≤ x, y, z ≤ 1, x + y + z ≤ 1} in the Cartesian three‐dimensional (x, y, z) space. The mathematical transformation from the (x, y, z) space to (ξ, η, ζ) space is described to map the standard tetrahedron in (x, y, z) space to a standard 2‐cube: {(ξ, η, ζ)| ? 1 ≤ ζ, η, ζ ≤ 1} in the (ξ, η, ζ) space. This overcomes the difficulties associated with the derivation of new weight coefficients and sampling points. The effectiveness of the formulas is demonstrated by applying them to the integration of three nonpolynomial, three polynomial functions and to the evaluation of integrals for element stiffness matrices in linear three‐dimensional elasticity. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Hadamard well-posedness in discontinuous non-cooperative games

We consider some recent classes of discontinuous games with Nash equilibria and we prove that such classes have the Hadamard well-posedness property. This means that given a game y, a net (y^α)_α of games converging to y and a net (x^α)_α such that x^α is a Nash equilibrium of any y^α, then at least a cluster point of (x^α)_α is a Nash equilibrium of y. In order to obtain this property, we prove that the map of Nash equilibria is upper semicontinuous. Using the pseudocontinuity, a generalization of the continuity, we improve previous results obtained with continuous functions.     

A New Method for Constructing Williamson Matrices

For every prime power q 1 (mod 4) we prove the existence of (q; x, y)-partitions of GF(q) with q=x²+4y² for some x, y, which are very useful for constructing SDS, DS and Hadamard matrices. We discuss the transformations of (q; x,y)-partitions and, by using the partitions, construct generalized cyclotomic classes which have properties similar to those of classical cyclotomic classes. Thus we provide a new construction for Williamson matrices of order q².The research supported by NSF of China (No. 10071029).     

Zero product determined classical Lie algebras

We show that the Lie algebra ? of skew-symmetric matrices with respect to either transpose or symplectic involution is zero product determined. This means that every bilinear map {·,·} from ? × ? into a vector space X is of the form {x, y} = T ([x, y]) for some linear map T provided that the following condition is fulfilled: [x, y] = 0 implies {x, y} = 0.     

Reduction of Silverman-like games to games on bounded sets

A two person zero sum game is regarded as Silverman-like if the strategy sets are sets of real numbers bounded below, the payoff function is bounded, the maximum payoff is achieved whenever the second player's numbery exceeds the first player's numberx by “too much”, and the minimum is achieved wheneverx exceedsy by “too much”. Explicit upper bounds are obtained for pure strategies to be included in an optimal mixed strategy in such games. In particular, if the strategy sets are discrete, the games may be reduced to games on specified finite sets.     

Zero product determined Jordan algebras,I

We show that the Jordan algebra 𝒮 of symmetric matrices with respect to either transpose or symplectic involution is zero product determined. This means that if a bilinear map {.,?.} from 𝒮?×?𝒮 into a vector space X satisfies {x, y}?=?0 whenever x?○?y?=?0, then there exists a linear map T : 𝒮?→?X such that {x,?y}?=?T(x?○?y) for all x, y?∈?𝒮 (here, x?○?y?=?xy?+?yx).     

Noncooperative selection of the core

For bargaining environments given by transferable utility characteristic functions that are zero-normalized and admit a nonempty core, we find a class of random-proposer bargaining games, generalized from Okada (1993), such that there is a one-to-one mapping from these games to the core, each game realizes the corresponding core allocation as its unique (ex ante) Stationary Subgame Perfect Equilibrium (SSPE) payoff profile, and every ex post SSPE payoff profile converges to the core allocation as the discount factor goes to one. The result has a natural interpretation in terms of bargaining power. Received: December 2000/Revised: August 2002     

Probabilities of Pure Nash Equilibria in Matrix Games when the Payoff Entries of One Player Are Randomly Selected

The Nash equilibrium in pure strategies represents an important solution concept in nonzero sum matrix games. Existence of Nash equilibria in games with known and with randomly selected payoff entries have been studied extensively. In many real games, however, a player may know his own payoff entries but not the payoff entries of the other player. In this paper, we consider nonzero sum matrix games where the payoff entries of one player are known, but the payoff entries of the other player are assumed to be randomly selected. We are interested in determining the probabilities of existence of pure Nash equilibria in such games. We characterize these probabilities by first determining the finite space of ordinal matrix games that corresponds to the infinite space of matrix games with random entries for only one player. We then partition this space into mutually exclusive spaces that correspond to games with no Nash equilibria and with r Nash equilibria. In order to effectively compute the sizes of these spaces, we introduce the concept of top-rated preferences minimal ordinal games. We then present a theorem which provides a mechanism for computing the number of games in each of these mutually exclusive spaces, which then can be used to determine the probabilities. Finally, we summarize the results by deriving the probabilities of existence of unique, nonunique, and no Nash equilibria, and we present an illustrative example.     

Cone Concavity and Multiple-Payoff Constrained n-Person Games

This paper investigates special cases of abstract economies, i.e., n-person games with multiple payoff functions. Dominances with certain convex cones and interactive strategies are introduced in such game settings. Gradients of payoff functions are involved to establish certain Lagrange or Kuhn–Tucker conditions which may lead to some algorithms to actually compute an equilibrium. Sufficient and necessary conditions for such multiple payoff constrained n-person games are obtained.     

Propriétés statistiques des entiers friables

Let Ψ(x,y) (resp. Ψ_m(x,y)) denote the number of integers not exceeding x that are y-friable, i.e. have no prime factor exceeding y (resp. and are coprime to m). Evaluating the ratio Ψ_m(x/d,y)/Ψ(x,y) for 1≤slantd≤slantx, m≥slant 1, x≥slant y≥slant 2, turns out to be a crucial step for estimating arithmetic sums over friable integers. Here, it is crucial to obtain formulae with a very wide range of validity. In this paper, several uniform estimates are provided for the aforementioned ratio, which supersede all previously known results. Applications are given to averages of various arithmetic functions over friable integers which in turn improve corresponding results from the literature. The technique employed rests mainly on the saddle-point method, which is an efficient and specific tool for the required design.2000 Mathematics Subject Classification: Primary—11N25; Secondary—11K65, 11N37     

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     

On a duel with time lag and equal accuracy functions

This paper deals with a duel with time lag that has the following structure: Each of two players I and II has a gun with one bullet and he can fire his bullet at any time in [0, 1], aiming at this opponent. The gun of player I is silent and the gun of player II is noisy with time lagt (i.e., if player II fires at timex, then player I knows it at timex+t). They both have equal accuracy functions. Furthermore, if player I hits player II without being hit himself before, the payoff is +1; if player I is hit by player II without hitting player II before, the payoff is –1; if they hit each other at the same time or both survive, the payoff is 0.This paper gives the optimal strategy for each player, the game value, and some examples.     

Unit-sphere games

This paper introduces a class of games, called unit-sphere games, in which strategies are real vectors with unit 2-norms (or, on a unit-sphere). As a result, they should no longer be interpreted as probability distributions over actions, but rather be thought of as allocations of one unit of resource to actions and the payoff effect on each action is proportional to the square root of the amount of resource allocated to that action. The new definition generates a number of interesting consequences. We first characterize the sufficient and necessary condition under which a two-player unit-sphere game has a Nash equilibrium. The characterization reduces solving a unit-sphere game to finding all eigenvalues and eigenvectors of the product matrix of individual payoff matrices. For any unit-sphere game with non-negative payoff matrices, there always exists a unique Nash equilibrium; furthermore, the unique equilibrium is efficiently reachable via Cournot adjustment. In addition, we show that any equilibrium in positive unit-sphere games corresponds to approximate equilibria in the corresponding normal-form games. Analogous but weaker results are obtained in n-player unit-sphere games.     

On the NP-completeness of finding an optimal strategy in games with common payoffs

Consider a very simple class of (finite) games: after an initial move by nature, each player makes one move. Moreover, the players have common interests: at each node, all the players get the same payoff. We show that the problem of determining whether there exists a joint strategy where each player has an expected payoff of at least r is NP-complete as a function of the number of nodes in the extensive-form representation of the game. Received January 2001/Final version May 1, 2001     

Multicriteria Goal Games

In this paper, we deal with multicriteria matrix games. Different solution concepts have been proposed to cope with these games. Recently, the concept of Pareto-optimal security strategy which assures the property of security in the individual criteria against an opponent's deviation in strategy has been introduced. However, the idea of security behind this concept is based on expected values, so that this security might be violated by mixed strategies when replications are not allowed. To avoid this inconvenience, we propose in this paper a new concept of solution for these games: the G-goal security strategy, which includes as part of the solution the probability of obtaining prespecified values in the payoff functions. Thus, attitude toward risk together with payoff values are considered jointly in the solution analysis.     

Characterizations of generalized quadrangles by generalized homologies

Let S = (P, B, I) be a generalized quadrangle of order (s, t). For x, y P, x y, let (x, y) be the group of all collineations of S fixing x and y linewise. If z {x, y}, then the set of all points incident with the line xz (resp. yz) is denoted by (resp. ). The generalized quadrangle S = (P, B, I) is said to be (x, y)-transitive, x y, if (x, y) is transitive on each set and . If S = (P, B, I) is a generalized quadrangle of order (s, t), s > 1 and t > 1, which is (x, y)-transitive for all x, y P with x y, then it is proved that we have one of the following: (i) S W(s), (ii) S Q(4, s), (iii) S H(4, s), (iv) S Q(5, s), (v) s = t² and all points are regular.     

Network search games with immobile hider,without a designated searcher starting point

In the (zero-sum) search game Γ(G, x) proposed by Isaacs, the Hider picks a point H in the network G and the Searcher picks a unit speed path S(t) in G with S(0) = x. The payoff to the maximizing Hider is the time T = T(S, H) = min{t : S(t) = H} required for the Searcher to find the Hider. An extensive theory of such games has been developed in the literature. This paper considers the related games Γ(G), where the requirement S(0) = x is dropped, and the Searcher is allowed to choose his starting point. This game has been solved by Dagan and Gal for the important case where G is a tree, and by Alpern for trees with Eulerian networks attached. Here, we extend those results to a wider class of networks, employing theory initiated by Reijnierse and Potters and completed by Gal, for the fixed-start games Γ(G, x). Our results may be more easily interpreted as determining the best worst-case method of searching a network from an arbitrary starting point.