Equilibrium and Pareto-optimality in noisy discrete duels with an arbitrary number of actions

We study a nonzero-sum game of two players that is a generalization of the antagonistic noisy duel of discrete type. The game is considered from the point of view of various criteria of optimality. We prove the existence of ε-equilibrium situations and show that the ε-equilibrium strategies that we found are ε-maxmin. Conditions under which the equilibrium plays are Pareto-optimal are given. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 2, pp. 147–155, 2007.     

Finding all pure strategy Nash equilibria in a planar location game

In this paper, we deal with a planar location-price game where firms first select their locations and then set delivered prices in order to maximize their profits. If firms set the equilibrium prices in the second stage, the game is reduced to a location game for which pure strategy Nash equilibria are studied assuming that the marginal delivered cost is proportional to the distance between the customer and the facility from which it is served. We present characterizations of local and global Nash equilibria. Then an algorithm is shown in order to find all possible Nash equilibrium pairs of locations. The minimization of the social cost leads to a Nash equilibrium. An example shows that there may exist multiple Nash equilibria which are not minimizers of the social cost.     

Finding location equilibria for competing firms under delivered pricing

We address the problem of finding location equilibria of a location-price game where firms first select their locations and then set delivered prices in order to maximize their profits. Assuming that firms set the equilibrium prices in the second stage, the game is reduced to a location game for which a global minimizer of the social cost is a location equilibrium if demand is completely inelastic and marginal production cost is constant. The problem of social cost minimization is studied for both a network and a discrete location space. A node optimality property when the location space is a network is shown and an Integer Linear Programming (ILP) formulation is obtained to minimize the social cost. It is also shown that multiple location equilibria can be found if marginal delivered costs are equal for all competitors. Two ILP formulations are given to select one of such equilibria that take into account the aggregated profit and an equity criterion, respectively. An illustrative example with real data is solved and some conclusions are presented.     

N-Person stochastic games with upper semi-continuous payoffs

Every n-person stochastic game with a countable state space, finite action sets for the players and bounded, upper semi-continuous payoffs has an ε-equilibrium for every ε>0.     

Hotelling's duopoly on a tree

This paper considers Hotelling's duopoly model on a tree. It is shown that if both competitors have price and location as decision variables, no equilibrium exists. If prices are fixed in advance by the competitors, equilibria may exist. Conditions for this case are developed. Then the related sequential location problem is investigated. It is shown that it is usually beneficial for a facility not to locate first but to react to its competitor's location choice.     

Value and perfection in stochastic games

A stochastic game isvalued if for every playerk there is a functionr ^k:S→R from the state spaceS to the real numbers such that for every ε>0 there is an ε equilibrium such that with probability at least 1−ε no states is reached where the future expected payoff for any playerk differs fromr ^k(s) by more than ε. We call a stochastic gamenormal if the state space is at most countable, there are finitely many players, at every state every player has only finitely many actions, and the payoffs are uniformly bounded and Borel measurable as functions on the histories of play. We demonstrate an example of a recursive two-person non-zero-sum normal stochastic game with only three non-absorbing states and limit average payoffs that is not valued (but does have ε equilibria for every positive ε). In this respect two-person non-zero-sum stochastic games are very different from their zero-sum varieties. N. Vieille proved that all such non-zero-sum games with finitely many states have an ε equilibrium for every positive ε, and our example shows that any proof of this result must be qualitatively different from the existence proofs for zero-sum games. To show that our example is not valued we need that the existence of ε equilibria for all positive ε implies a “perfection” property. Should there exist a normal stochastic game without an ε equilibrium for some ε>0, this perfection property may be useful for demonstrating this fact. Furthermore, our example sews some doubt concerning the existence of ε equilibria for two-person non-zero-sum recursive normal stochastic games with countably many states. This research was supported financially by the German Science Foundation (Deutsche Forschungsgemeinschaft) and the Center for High Performance Computing (Technical University, Dresden). The author thanks Ulrich Krengel and Heinrich Hering for their support of his habilitation at the University of Goettingen, of which this paper is a part.     

Generalized Nash equilibrium

For accep/reject games and coalitionless games, the classical Roos-Nash equilibrium is generalized to a so-called strongly dependent equilibrium, which exists for a wider class of games than the classical equilibrium. The following hierarchical chain of progressively stronger equilibria is established: symmetrical activeA-equilibrium, strongly dependent equilibrium, symmetricalB-equilibrium, Roos-Nash classical dependent equilibrium. The first three of these have been proposed by the author as weaker versions of the classical coalitionless equilibrium. Translated from Nelineinaya Dinamika i Upravlenie, pp. 217–227, 1999.     

ɛ-Consistent equilibrium in repeated games

We introduce the concept of ɛ-consistent equilibrium where each player plays a ɛ-best response after every history reached with positive probability. In particular, an ɛ-consistent equilibrium induces an ɛ-equilibrium in any subgame reached along the play path. The existence of ɛ-consistent equilibrium is examined in various repeated games. The main result is the existence in stochastic games with absorbing states. Received January 1995/Revised version October 1996/Final version September 1997     

Coordination games on graphs

We introduce natural strategic games on graphs, which capture the idea of coordination in a local setting. We study the existence of equilibria that are resilient to coalitional deviations of unbounded and bounded size (i.e., strong equilibria and k-equilibria respectively). We show that pure Nash equilibria and 2-equilibria exist, and give an example in which no 3-equilibrium exists. Moreover, we prove that strong equilibria exist for various special cases. We also study the price of anarchy (PoA) and price of stability (PoS) for these solution concepts. We show that the PoS for strong equilibria is 1 in almost all of the special cases for which we have proven strong equilibria to exist. The PoA for pure Nash equilbria turns out to be unbounded, even when we fix the graph on which the coordination game is to be played. For the PoA for k-equilibria, we show that the price of anarchy is between \(2(n-1)/(k-1) - 1\) and \(2(n-1)/(k-1)\). The latter upper bound is tight for \(k=n\) (i.e., strong equilibria). Finally, we consider the problems of computing strong equilibria and of determining whether a joint strategy is a k-equilibrium or strong equilibrium. We prove that, given a coordination game, a joint strategy s, and a number k as input, it is co-NP complete to determine whether s is a k-equilibrium. On the positive side, we give polynomial time algorithms to compute strong equilibria for various special cases.     

Brand positioning under lexicographic choice rules

This paper discusses a brand positioning model in which two brands of a product are to be positioned in a price-quality space under a new behavioral assumption. This assumption asserts that customers determine the highest-quality product within their reservation price and purchase it, provided its quality does not fall short of a minimum standard. The model also includes producers' costs that are incurred for delivering a certain quality. We first delineate reaction functions for the optimal location of one brand, give a location of its competitor. We then show that Nash equilibria do not exist as long as price and quality are both variable. Finally, we consider a two phase model: in the first phase, the duopolists sequentially choose their quality levels under the assumption that both competitors know that in the second phase, a Nash equilibrium in prices follows. Single-variable mathematical programming formulations are presented to solve the problem. A numerical example is also given to illustrate the working of the model.     

Vector equilibrium problems with elastic demands and capacity constraints

In this paper, a (weak) vector equilibrium principle for vector network problems with capacity constraints and elastic demands is introduced. A sufficient condition for a (weak) vector equilibrium flow to be a solution for a system of (weak) vector quasi-variational inequalities is obtained. By virtue of Gerstewitz’s nonconvex separation functional ξ, a (weak) ξ-equilibrium flow is introduced. Relations between a weak vector equilibrium flow and a (weak) ξ-equilibrium flow is investigated. Relations between weak vector equilibrium flows and two classes of variational inequalities are also studied.     

A discrete long-term location–price problem under the assumption of discriminatory pricing: Formulations and parametric analysis

We consider a competitive location problem in which a new firm has to make decisions on the locations of several new facilities as well as on its price setting in order to maximise profit. Under the assumption of discriminatory prices, competing firms set a specific price for each market area. The customers buy one unit of a single homogeneous price-inelastic product from the facility that offers the lowest price in the area the consumers belong to. Three customer choice rules are considered in order to break ties in the offered prices. We prove that, considering long-term competition on price, this problem can be reduced to a problem with decisions on location only. For each one of the choice rules the location problem is formulated as an integer programming model and a parametric analysis of these models is given. To conclude, an application with real data is presented.     

Generalized Nash equilibrium problems for lower semi-continuous strategy maps

We consider a class of generalized Ky Fan inequalities (quasi-variational inequalities) in which the involved multi-valued mapping is lower semi-continuous. We present a relaxed version of the generalized Nash equilibrium problem involving strategy maps, which are only lower semi-continuous. This relaxed version may have no exact Nash equilibrium, but we prove that it has an ε-Nash equilibrium for every ε > 0. Easy examples of such problems show no existence of exact solutions, but existence of ε-solutions for every ε > 0. We give positive answers to two questions (in the compact case) raised in a recent paper of Cubiotti and Yao.     

Optimal cost sharing for capacitated facility location games

We consider cost sharing for a class of facility location games, where the strategy space of each player consists of the bases of a player-specific matroid defined on the set of resources. We assume that resources have nondecreasing load-dependent costs and player-specific delays. Our model includes the important special case of capacitated facility location problems, where players have to jointly pay for opened facilities. The goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate two classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium and separable protocols additionally require that the resulting cost shares only depend on the set of players on a resource. We find optimal basic and separable protocols that guarantee the price of stability/price of anarchy to grow logarithmically/linearly in the number of players. These results extend our previous results (cf. von Falkenhausen & Harks, 2013), where optimal basic and separable protocols were given for the case of symmetric matroid games without delays.     

在消费者偏好不确定下双寡头定位定价博弈

本文通过建立在企业对消费者偏好信息不确定情形下,双寡头企业动态定位、定价博弈模型,研究企业的定位策略、定价策略以及产品差异化问题。证明了该动态博弈存在唯一的子博弈精炼均衡。均衡结果表明,偏好不确定性是一种差异化力量,与消费者偏好信息确定情形相比,企业的不确定性能够提高均衡价格、增加均衡利润。最后,分析了偏好不确定性对社会最优定位和社会最优差异化的影响。     

Sequential Discrete p-Facility Models for Competitive Location Planning

Two new models for duopolistic competitive discrete location planning with sequential acting and variable delivered prices are introduced. If locations and prices are assumed to be set once and for all by the players, the resulting bilevel program is nonlinear. Under the assumption that further price adjustments are possible, i.e., that a Nash equilibrium in prices is reached, the model can be simplified to a linear discrete bilevel formulation. It is shown that in either situation players should not share any locations or markets if they strive for profit-maximization.For the situation with price adjustments, a heuristic solution procedure is suggested. In addition, the bilevel models are shown to serve as a basis from which different well-known location models – as, for example, the p-median problem, the preemptive location problem and the maximum covering problem – can be derived as special cases.     

A note on vector network equilibrium principles

An example is given to show that the necessary conditions of Theorem 4.5 [in Chen et al. Math Methods Oper Res 49:239–253, 1999] and Theorem 2.1 (i) [in Goh and Yang Eur J Oper Res 116:615–628, 1999] for (weak) vector equilibrium flows may not hold. New ξ-equilibrium and parametric equilibrium flows are introduced. As a result, necessary and sufficient conditions between a weak vector equilibrium flow and an ξ-equilibrium flow and between a vector equilibrium flow and a parametric equilibrium flow are established.     

Correlated equilibrium payoffs and public signalling in absorbing games

An absorbing game is a repeated game where some action combinations are absorbing, in the sense that whenever they are played, there is a positive probability that the game terminates, and the players receive some terminal payoff at every future stage.  We prove that every multi-player absorbing game admits a correlated equilibrium payoff. In other words, for every ε>0 there exists a probability distribution p _ε over the space of pure strategy profiles that satisfies the following. With probability at least 1−ε, if a pure strategy profile is chosen according to p _ε and each player is informed of his pure strategy, no player can profit more than ε in any sufficiently long game by deviating from the recommended strategy. Received: April 2001/Revised: June 4, 2002     

Stay-in-a-set games

There exists a Nash equilibrium (ε-Nash equilibrium) for every n-person stochastic game with a finite (countable) state space and finite action sets for the players if the payoff to each player i is one when the process of states remains in a given set of states G _i and is zero otherwise. Received: December 2000     

消费者连续统集合下一种投入产出经济的均衡和一般均衡价格

本给出了一个经济模型把跨期间的一般均衡理论和neo-Ricardian的生产价格理论联系起来，并改进了Roce-Anne Oana模型[1][2]。即把消费有限改变消费连续统，并在Rose-Anne Dana模型的基础上，加了条件C.4和C.7，得出了两个重要的结果：（1）在标准条件下，此模型有一均衡使得每一个生产的每期最大利润是相等的；（2）如考虑生产价格是稳定价格；且等于最大利润；则在适当的条件下，这样的价格系统是存在且唯一的，而所定义的均衡的非折扣的价格序列收敛于生产价格。因此均衡价格依赖于技术和消费特征，但在取极限时，有关价格仅依赖于技术。