Variational inequality formulation for the games with random payoffs

We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case where the continuous strategy set of each player does not depend on the strategies of other players. If a random vector defining the payoffs of each player follows a multivariate elliptically symmetric distribution, we show that there exists a Nash equilibrium. We characterize the set of Nash equilibria using the solution set of a variational inequality (VI) problem. Next, we consider the case where the continuous strategy set of each player is defined by a shared constraint set. In this case, we show that there exists a generalized Nash equilibrium for elliptically symmetric distributed payoffs. Under certain conditions, we characterize the set of a generalized Nash equilibria using the solution set of a VI problem. As an application, the random payoff games arising from electricity market are studied under chance-constrained game framework.     

Player splitting in extensive form games

By a player splitting we mean a mechanism that distributes the information sets of a player among so-called agents. A player splitting is called independent if each path in the game tree contains at most one agent of every player. Following Mertens (1989), a solution is said to have the player splitting property if, roughly speaking, the solution of an extensive form game does not change by applying independent player splittings. We show that Nash equilibria, perfect equilibria, Kohlberg-Mertens stable sets and Mertens stable sets have the player splitting property. An example is given to show that the proper equilibrium concept does not satisfy the player splitting property. Next, we give a definition of invariance under (general) player splittings which is an extension of the player splitting property to the situation where we also allow for dependent player splittings. We come to the conclusion that, for any given dependent player splitting, each of the above solutions is not invariant under this player splitting. The results are used to give several characterizations of the class of independent player splittings and the class of single appearance structures by means of invariance of solution concepts under player splittings. Received: December 1996/Revised Version: January 2000     

General sum games with joint chance constraints

We consider an $n$-player non-cooperative game with continuous strategy sets. The strategy set of each player contains a set of stochastic linear constraints. We model the stochastic linear constraints of each player as a joint chance constraint. We assume that the row vectors of a matrix defining the stochastic constraints of each player are independent and each row vector follows a multivariate normal distribution. Under certain conditions, we show the existence of a Nash equilibrium for this game.     

Equilibrium with strategy-dependent trembles

Trembling-hand arguments, introduced by Selten, where players make errors in implementing a strategy, are a successful and intuitively plausible approach to eliminating some equilibria. Typically, these errors are independent of the strategy the player aims to implement. In many contexts, however, when a player aims at one strategy, some errors are more likely than if a different strategy is the target. We introduce the notion of strategy-dependent trembles where each strategy intended by a player implies a different probability vector of errors over other strategies. This seemingly minor but plausible change makes a major difference. The focus becomes a player's own errors rather than the errors of others. A weakly dominated strategy is not necessarily eliminated if less costly errors arise when aiming at it than at the dominating strategy. Almost every Nash equilibrium in pure strategies is a strategy-dependent trembling-hand perfect equilibrium. We thank the associate editor, two referees, James Friedman, and audiences at the Public Choice Society Meetings and Southeastern Economic Theory Meetings for comments and the Public Utility Research Center and the College of Business Administration at the University of Florida for financial support.     

Dynamique des groupes paraboliques d'automorphismes polynomiaux de ℂ2

Résumé  Nous étudions la dynamique de certains groupes abéliens d'automorphismes polynomiaux de ², que nous appelons groupes paraboliques. Nous montrons que ces groupes sont toujours formellement linéarisables, et que la linéarisante peut être strictement formelle ou au contraire convergente. Nous montrons ensuite que sous une hypothèse d'uniformité un groupe parabolique admet un (1,1) courant positif fermé invariant. Enfin nous donnons un exemple de groupe parabolique non uniforme n'admettant aucun (1,1) courant positif fermé invariant.

---

We study the dynamics of a class of abelian groups of polynomial automorphisms of ², that we call parabolic groups. We show that these groups are always formally linearizable, and the linearizing map could be strictly formal or convergent. Further we show that under an uniformity hypothesis a parabolic group has a invariant (1, 1) positive closed current. Lastly we give an example of parabolic group that does not admit any invariant (1,1) positive closed current.

     

Evolutionary games and matching rules

This study considers evolutionary games with non-uniformly random matching when interaction occurs in groups of \(n\ge 2\) individuals using pure strategies from a finite strategy set. In such models, groups with different compositions of individuals generally co-exist and the reproductive success (fitness) of a specific strategy varies with the frequencies of different group types. These frequencies crucially depend on the matching process. For arbitrary matching processes (called matching rules), we study Nash equilibrium and ESS in the associated population game and show that several results that are known to hold for population games under uniform random matching carry through to our setting. In our most novel contribution, we derive results on the efficiency of the Nash equilibria of population games and show that for any (fixed) payoff structure, there always exists some matching rule leading to average fitness maximization. Finally, we provide a series of applications to commonly studied normal-form games.     

Computation of equilibria and the price of anarchy in bottleneck congestion games

We study Nash and strong equilibria in weighted and unweighted bottleneck games. In such a game every (weighted) player chooses a subset of a given set of resources as her strategy. The cost of a resource depends on the total weight of players choosing it and the personal cost every player tries to minimize is the cost of the most expensive resource in her strategy, the bottleneck value. To derive efficient algorithms for finding equilibria in unweighted games, we generalize a transformation of a bottleneck game into a congestion game with exponential cost functions introduced by Caragiannis et al. (2005). For weighted routing games we show that Greedy methods give Nash equilibria in extension-parallel and series-parallel graphs. Furthermore, we show that the strong Price of Anarchy can be arbitrarily high for special cases and give tight bounds depending on the topology of the graph, the number and weights of the users and the degree of the polynomial latency functions. Additionally we investigate the existence of equilibria in generalized bottleneck games, where players aim to minimize not only the bottleneck value, but also the second most expensive resource in their strategy and so on.     

Distributionally robust chance-constrained games: existence and characterization of Nash equilibrium

We consider an n-player finite strategic game. The payoff vector of each player is a random vector whose distribution is not completely known. We assume that the distribution of a random payoff vector of each player belongs to a distributional uncertainty set. We define a distributionally robust chance-constrained game using worst-case chance constraint. We consider two types of distributional uncertainty sets. We show the existence of a mixed strategy Nash equilibrium of a distributionally robust chance-constrained game corresponding to both types of distributional uncertainty sets. For each case, we show a one-to-one correspondence between a Nash equilibrium of a game and a global maximum of a certain mathematical program.     

Baryzentrische Formeln zur trigonometrischen Interpolation (II) Stabilität und Anwendung auf die Fourieranalyse bei ungleichabständigen Stützstellen

Summary In Part I we have presented barycentric formulas for trigonometric interpolation. Here we show that these formulas make it possible to calculate Fourier coefficients easily and efficiently. The only inconvenience is their instability when the number of interpolating points becomes large; this instability can be avoided in a special case. The formulas can be used to approximate the inverse of a periodic function, for instance of the boundary correspondence function in numerical conformal mapping.

---

Résumé Dans la première partie, nous avons présenté des formules barycentriques pour l'interpolation trigonométrique. Ici, nous montrons que ces formules permettent une analyse de Fourier particuliérement simple et efficiente; leur seul inconvénient réside dans leur instabilité lorsque le nombre de noeuds croît, instabilité qui peut être évitée dans un cas particulier. Elles sont applicables à l'approximation de l'inverse d'une fonction périodique, par exemple de la fonction de correspondance des frontières en application conforme numérique.

     

Utilitarian resource assignment

This paper studies a resource allocation problem introduced by Koutsoupias and Papadimitriou. The scenario is modelled as a multiple-player game in which each player selects one of a finite number of known resources. The cost to the player is the total weight of all players who choose that resource, multiplied by the “delay” of that resource. Recent papers have studied the Nash equilibria and social optima of this game in terms of the L_∞ cost metric, in which the social cost is taken to be the maximum cost to any player. We study the L₁ variant of this game, in which the social cost is taken to be the sum of the costs to the individual players, rather than the maximum of these costs. We give bounds on the size of the coordination ratio, which is the ratio between the social cost incurred by selfish behavior and the optimal social cost; we also study the algorithmic problem of finding optimal (lowest-cost) assignments and Nash Equilibria. Additionally, we obtain bounds on the ratio between alternative Nash equilibria for some special cases of the problem.     

Hypercontractivité pour des systèmes de spins de portée infinie

Résumé Nous considérons un système de spins sur ^d . Nous prouvons l'équivalence entre premièrement une condition faible de mélange deuxièmement le contrôle du trou dans le spectre et troisièmement celui de la constante de Sobolev logarithmique pour des potentiels de Gibbs de portée non nécessairement finie. Nous en tirons des conséquences sur la vitesse de convergence des semi-groupes dansL ² et sur la décroissance des corrélations: il n'y a pas de régime intermédiaire entre un taux algébrique ent ^–2d (resp. |j-k|^–2d) et un taux exponentiel. Les résultats généraux sont montrés pour des spins à valeur dans une variété riemannienne compacte ou dans un espace fini.

---

Summary We consider a spin system on ^d . We prove the equivalence between first a weak mixing condition, secondly the controle of spectral gap and thirdly the controle of logarithmic Sobolev constants for non necessarily finite range Gibbs potentials. Hence we draw consequences concerning theL ² decay to equilibrium and the correlations decay: there is no transitory rate between an algebraic decay ast ^–2d (resp. |j-k|^–2d)and exponential decay. The general results are obtained for both continuous and discrete compact spins.

This article was processed by the authors using the LATEX style filepljour Im from Springer-Verlag     

Sur le comportement asymptotique des potentiels d'une chaîne de Markov sur ℝ d

Résumé Dans cet article j'étudie le comportement à l'infini des potentiels des chaînes de Markov sur ^d (d3) proches du mouvement brownien, tout spécialement le cas des marches aléatoires, ainsi que des critères de transience et de récurrence inspirés de la méthode utilisée.

---

We study the asymptotic behaviour of potentials of Markov chains on ^d (d3), closed to Brownian motion, and particularly the case of random walks. Following a similar approach, we give transience and recurrence criteria.

     

Membranes élastiquement liées inhomogènes ou sur une surface: Une nouvelle extension du théorème isopérimétrique de Rayleigh-Faber-Krahn

Résumé Soit ₁ la première valeur propre d'une membrane élastiquement liée inhomogène ou sur une surface. On caractérise ₁ comme Maximum, avec une méthode inspirée par celle des longueurs extrémales de Beurling et Ahlfors [1]. Cette caractérisation permet une nouvelle extension du théorème isopérimétrique de Rayleigh-Faber-Krahn ([10], p. 191 ou [4], p. 104).

---

Summary Let ₁ be the first eigenvalue of an elastically supported membrane, either inhomogeneous or on a surface. ₁ is caracterized as a Maximum by a method close to the extremal length of Beurling and Ahlfors [1]. This caracterization allows a new extension of Rayleigh-Faber-Krahn's isoperimetric theorem ([10], p. 191 or [4], p. 104).

---

---

Cette recherche a été soutenue par le Fonds national suisse de la recherche scientifique.     

Transplantation et isospectralité. I

Sans résumé

---

Recherche effectuée au sein de l'U.R.A. C.N.R.S. n^o 188 et qui a bénéficié de crédits du contrat CEE#SC 1-0105-C GADGET et de l'OTAN     

How to Select a Solution in Generalized Nash Equilibrium Problems

We propose a new solution concept for generalized Nash equilibrium problems. This concept leads, under suitable assumptions, to unique solutions, which are generalized Nash equilibria and the result of a mathematical procedure modeling the process of finding a compromise. We first compute the favorite strategy for each player, if he could dictate the game, and use the best response on the others’ favorite strategies as starting point. Then, we perform a tracing procedure, where we solve parametrized generalized Nash equilibrium problems, in which the players reduce the weight on the best possible and increase the weight on the current strategies of the others. Finally, we define the limiting points of this tracing procedure as solutions. Under our assumptions, the new concept selects one reasonable out of typically infinitely many generalized Nash equilibria.     

Sur un théorème de Choquet

Résumé Le but de ce travail est de caractériser les éspaces topologiques qui possèdent la propriété suivant: pour toute famille(f _t ) _{t I} de fonctions numériques définies dansX il existe une partie dénombrableI ₀ de l'ensemble d'indicesI telle que les fonctions inf _tI f _i et inf _tI0 f _i ont la meme régularisation inférieurement semi-continue.On démontre que l'espace topologiqueX possède cette propriété si et seulement si pour tout sous-ensembleA deX il existe une sous-ensemble dénombrableA ₀,A ₀ A tel queA ₀.On généralise un résultat topologique de G. Choquet.

---

     

Sur la régularité de la fonction croissance d'une variété riemannienne

Résumé On étudie la différentiabilité de la fonction croissance d'une variété riemannienne complète. En général, elle a la même régularité qu'une fonction concave: la dérivée peut avoir des sauts pour lesquels on donne une formule. Dans le cas analytique réel, la fonction croissance est de classeC ¹. Un exemple montre qu'elle n'est pas nécessairementC ². A titre d'application, nous construisons, pour toute variété ouverte paracompacteM et toute fonction croissantev de classeC ¹, une métrique continue de croissance égale àv et une métrique de classeC surM de croissance proche dev en topologieC ¹-fine.

---

Travail réalisé avec l'aide financière du MURST d'Italie.     

Quasi-variational inequalities, generalized Nash equilibria, and multi-leader-follower games

The noncooperative multi-leader-follower game can be formulated as a generalized Nash equilibrium problem where each player solves a nonconvex mathematical program with equilibrium constraints. Two major deficiencies exist with such a formulation: One is that the resulting Nash equilibrium may not exist, due to the nonconvexity in each players problem; the other is that such a nonconvex Nash game is computationally intractable. In order to obtain a viable formulation that is amenable to practical solution, we introduce a class of remedial models for the multi-leader-follower game that can be formulated as generalized Nash games with convexified strategy sets. In turn, a game of the latter kind can be formulated as a quasi-variational inequality for whose solution we develop an iterative penalty method. We establish the convergence of the method, which involves solving a sequence of penalized variational inequalities, under a set of modest assumptions. We also discuss some oligopolistic competition models in electric power markets that lead to multi-leader-follower games.Jong-Shi Pang: The work of this authors research was partially supported by the National Science Foundation under grant CCR-0098013 and ECS-0080577 and by the Office of Naval Research under grant N00014-02-1-0286.Masao Fukushima: The work of this authors research was partially supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Science, Culture and Sports of Japan.     

La conjecture de Novikov pour les feuilletages hyperboliques

Nous définissons la notion de bolicité pour les feuilletages, qui est une notion plus faible que l'hyperbolicité de Gromov, et nous démontrons la conjecture de Novikov pour les feuilletages boliques à base compacte dont le groupoï de d'holonomie est séparé en établissant l'injectivité de l'application de Baum–Connes. Ce résultat généralise celui de Kasparov et Skandalis obtenu dans le cas des groupes boliques.We define the notion of bolicity for foliations, which is a weaker notion than Gromov's hyperbolicity, and we prove the Novikov conjecture for foliations with compact base and whose holonomy groupoid is Hausdorff, by showing that the Baum–Connes map is injective. This result generalizes that of Kasparov and Skandalis in the case of bolic groups.     

Contribution à l'étude des ondes gravito-capillaires forcées d'amplitude finie

Résumé Dans ce travail, on expose une méthode de perturbation régulière permettant de calculer une solution au 3° ordre des équations de propagation des ondes gravito-capillaires forcées induites à la surface libre d'un liquide. La solution est présentée sous forme d'une série entière par rapport à un petit paramètre, dont les coefficients sont développés à leur tour en séries de fonctions propres. Une étude sommaire de quelques cas limites permet aussi d'éxaminer l'évolution de la zône d'établissement du régime d'ondes en fonction de certains paramètres fondamentaux.

---

Summary In this paper, a regular perturbation method is proposed to calculate a third order solution, for equations governing the forced propagation of gravity-capillary waves in a perfect fluid. The solution is presented as a series in a small parameter, for which the coefficients are also developed in series of eigenfunctions. The study of some limiting cases gives also an approximation of the wave's structure near the wave-maker.