Robust equilibria in location games

In the framework of spatial competition, two or more players strategically choose a location in order to attract consumers. It is assumed standardly that consumers with the same favorite location fully agree on the ranking of all possible locations. To investigate the necessity of this questionable and restrictive assumption, we model heterogeneity in consumers’ distance perceptions by individual edge lengths of a given graph. A profile of location choices is called a “robust equilibrium” if it is a Nash equilibrium in several games which differ only by the consumers’ perceptions of distances. For a finite number of players and any distribution of consumers, we provide a complete characterization of robust equilibria and derive structural conditions for their existence. Furthermore, we discuss whether the classical observations of minimal differentiation and inefficiency are robust phenomena. Thereby, we find strong support for an old conjecture that in equilibrium firms form local clusters.     

Location choices under quality uncertainty

We examine a linear city duopoly where firms choose their locations to maximize expected profits, uncertain about how consumers will assess the relative quality of their products. Equilibrium locations depend on the ratio of the expected quality superiority and the strength of horizontal differentiation. When this ratio is small, firms locate at opposite endpoints. As it becomes larger, agglomeration also emerges as an equilibrium with both firms choosing the same location within an interval around the center. Eventually, when the ratio is large enough, agglomeration becomes the only equilibrium and can occur at any point of the linear city.     

On bargaining partner selection when communication is restricted

This paper analyzes the optimal selection of a bargaining partner when communication among players is restricted by an exogenously given graph. If players are equally patient, bargaining agreements are immune to players' locations, and the selection of a bargaining partner is not an issue. In contrast, when players differ in their discount factors, both location and impatience matter for bilateral agreements and partner selection becomes an issue. We show that selecting the most impatient neighbor is an equilibrium strategy whenever two players having a common neighbor share their most impatient neighbor. This condition is always satisfied by stratified graphs with no more than three strata. In the absence of this condition, cyclically-stratified graphs with no more than three strata also admit this equilibrium selection rule. Received: November 2000/Final version: January 2002     

A note on the m-center problem with rectilinear distances

Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.     

On a game in manufacturing

We analyse a non-zero sum two-person game introduced by Teraoka and Yamada to model the strategic aspects of production development in manufacturing. In particular we investigate how sensitive their solution concept (Nash equilibrium) is to small variations in their assumptions. It is proved that a Nash equilibrium is unique if it exists and that a Nash equilibrium exists when the capital costs of the players are zero or when the players are equal in every respect. However, when the capital costs differ, in general a Nash equilibrium exists only when the players' capital costs are high compared to their profit rates.     

Competition-reachability of a graph

The reachability r(D) of a directed graph D is the number of ordered pairs of distinct vertices (x,y) with a directed path from x to y. Consider a game associated with a graph G=(V,E) involving two players (maximizer and minimizer) who alternately select edges and orient them. The maximizer attempts to maximize the reachability, while the minimizer attempts to minimize the reachability, of the resulting digraph. If both players play optimally, then the reachability is fixed. Parameters that assign a value to each graph in this manner are called competitive parameters. We determine the competitive-reachability for special classes of graphs and discuss which graphs achieve the minimum and maximum possible values of competitive-reachability.     

Microeconomics-based resource allocation in overlay networks by using non-strategic behavior modeling

Behavior modeling has recently been investigated for designing self-organizing mechanisms in the context of communication networks in order to exploit the natural selfishness of the users with the goal of maximizing the overall utility. In strategic behavior modeling, the users of the network are assumed to be game players who seek to maximize their utility with taking into account the decisions that the other players might make. The essential difference between the aforementioned researches and this work is that it incorporates the non-strategic decisions in order to design the mechanism for the overlay network. In this solution concept, the decisions that a peer might make does not affect the actions of the other peers at all. The theory of consumer-firm developed in microeconomics is a model of the non-strategic behavior that we have adopted in our research. Based on it, we have presented distributed algorithms for peers’ “joining” and “leaving” operations. We have modeled the overlay network as a competitive economy in which the content provided by an origin server can be viewed as commodity and the origin server and the peers who multicast the content to their downside are considered as the firms. On the other hand, due to the dual role of the peers in the overlay network, they can be considered as the consumers as well. On joining to the overlay economy, each peer is provided with an income and tries to get hold of the service regardless to the behavior of the other peers. We have designed the scalable algorithms in such a way that the existence of equilibrium price (known as Walrasian equilibrium price) is guaranteed.     

Discrimination in festival games with limited observability and accessibility

This paper provides an analysis of discrimination and prejudices from the perspective of inductive game theory. We extend the festival game, originally given by Kaneko-Matsui, to include new constraints on the observability of ethnic identities and on accessible locations for players. We characterize the Nash equilibrium set, which reveals a different variety of segregation patterns and discriminatory behavior. In order to facilitate the analysis of discrimination and prejudices, we introduce a measure of discrimination, which chooses a representative equilibrium with the smallest degree of discrimination. Using this measure, we discuss various new phenomena, such as discrimination in an ethnic hierarchy; similar ethnicities as discriminated and as discriminating; and mutual discrimination. The introduction of limited observability and accessibility enables us to obtain those results.     

Network formation when players seek confirmation of information

We study network formation in a situation where the network allows players to obtain information (signals) about other players. This information is important for making a payoff relevant decision. However, not all information is reliable and so players may have an incentive to check it. By obtaining multiple messages about the same player through the network, a player learns whether his information is reliable for making the payoff relevant decision. We study the existence and architecture of strict Nash networks. We find that players who are involved in at least three links sponsor all links they are involved in. These players are similar to the central players in center sponsored stars. We show that strict Nash networks can be over-connected as well as under-connected as compared to efficient networks. Finally, we extend the basic model to study heterogeneous populations. In the first scenario, we allow for the co-existence of players who only value checked information and players who also value information with unknown reliability. In the second scenario, players who do not care about checking their information co-exist with players who do. Our results are robust to both types of heterogeneity, with one exception: the presence of a single player who cares only about checked information is enough to ensure that center sponsored stars are no longer stable.     

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.     

Dynamic resource allocation in fuzzy coalitions: a game theoretic model

We introduce an efficient and dynamic resource allocation mechanism within the framework of a cooperative game with fuzzy coalitions (cooperative fuzzy game). A fuzzy coalition in a resource allocation problem can be so defined that membership grades of the players in it are proportional to the fractions of their total resources. We call any distribution of the resources possessed by the players, among a prescribed number of coalitions, a fuzzy coalition structure and every membership grade (equivalently fraction of the total resources), a resource investment. It is shown that this resource investment is influenced by the satisfaction of the players in regard to better performance under a cooperative setup. Our model is based on the real life situations, where possibly one or more players compromise on their resource investments in order to help forming coalitions.     

On Cournot-Nash-Walras Equilibria and Their Computation

This paper concerns a model of Cournot-Nash-Walras (CNW) equilibrium where the Cournot-Nash concept is used to capture equilibrium of an oligopolistic market with non-cooperative players/firms who share a certain amount of a so-called rare resource needed for their production, and the Walras equilibrium determines the price of that rare resource. We prove the existence of CNW equilibria under reasonable conditions and examine their local stability with respect to small perturbations of problem data. In this way we show the uniqueness of CNW equilibria under mild additional requirements. Finally, we suggest some efficient numerical approaches and compute several instances of an illustrative test example.     

Nash Equilibrium Seeking in Quadratic Noncooperative Games Under Two Delayed Information-Sharing Schemes

In this paper, we propose non-model-based strategies for locally stable convergence to Nash equilibrium in quadratic noncooperative games where acquisition of information (of two different types) incurs delays. Two sets of results are introduced: (a) one, which we call cooperative scenario, where each player employs the knowledge of the functional form of his payoff and knowledge of other players’ actions, but with delays; and (b) the second one, which we term the noncooperative scenario, where the players have access only to their own payoff values, again with delay. Both approaches are based on the extremum seeking perspective, which has previously been reported for real-time optimization problems by exploring sinusoidal excitation signals to estimate the Gradient (first derivative) and Hessian (second derivative) of unknown quadratic functions. In order to compensate distinct delays in the inputs of the players, we have employed predictor feedback. We apply a small-gain analysis as well as averaging theory in infinite dimensions, due to the infinite-dimensional state of the time delays, in order to obtain local convergence results for the unknown quadratic payoffs to a small neighborhood of the Nash equilibrium. We quantify the size of these residual sets and corroborate the theoretical results numerically on an example of a two-player game with delays.

     

Analysis and design of selection committees: a game theoretic secretary problem

Firms often delegate important decisions to committees which are set up specifically for that purpose; for example selection committees. We analyze the equilibrium behavior of a game in which committee members (the players) interview candidates sequentially, either hiring or going on to the next one. The players have differing evaluations of candidates (e.g. one cares about typing skills; the other about IT skills), which become their utilities if the candidate is hired. We then consider the optimal design (rules of the game) of such a committee, from the point of view of the firm. That is, which rules hire candidates which maximize the firm’s utility. Our committee game has a first round in which the members sequentially, by order of player number, say ‘yea’ or ‘nea’ to the candidate. If there are sufficient ‘yeas’ then she is tentatively hired; otherwise she is rejected. In the former case, members who said nea can veto the candidate in the second round. Thus the candidate is either hired, rejected, or vetoed. In the last case, the member casting a veto has one less to use on later candidates. We analyze equilibria where a player may say ‘yea’ to a candidate he would prefer not to hire, in order to force the other player to use up a valuable veto. We show that for the uniform candidate distribution there is a unique equilibrium and better candidates for the firm are hired when there are more vetoes. However we exhibit a candidate distribution where increasing the numbers of vetoes results in hiring worse candidates.     

Simple centrifugal incentives in spatial competition

This paper studies the effects of introducing centrifugal incentives in an otherwise standard Downsian model of electoral competition. First, we demonstrate that a symmetric equilibrium is guaranteed to exist when centrifugal incentives are induced by any kind of partial voter participation (such as abstention due to indifference, abstention due to alienation, etc.) and, then, we argue that: (a) this symmetric equilibrium is in pure strategies, and it is hence convergent, only when centrifugal incentives are sufficiently weak on both sides; (b) when centrifugal incentives are strong on both sides (when, for example, a lot of voters abstain when they are sufficiently indifferent between the two candidates) players use mixed strategies—the stronger the centrifugal incentives, the larger the probability weight that players assign to locations near the extremes; and (c) when centrifugal incentives are strong on one side only—say for example only on the right—the support of players’ mixed strategies contain all policies except from those that are sufficiently close to the left extreme.     

内生网络环境下具有异质连接费用的局部策略互动

考察内生网络环境下局中人之间的局部策略互动, 网络中的局中人只与直接邻居进行协同对策. 网络生成的过程中, 建立连接的费用是异质的~(具有两种水平), 与采取有效行动的局中人建立连接时执行高水平费用, 与采取风险占优行动的局中人建立连接时执行低水平费用. 在异质连接费用的情形下, 首次较为完整地给出了均衡网络的结构特性和局中人的行动选择, 并分析了费用参数对均衡结果的影响.     

Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia

In this work we present a multiobjective location routing problem and solve it with a multiobjective metaheuristic procedure. In this type of problem, we have to locate some plants within a set of possible locations to meet the demands of a number of clients with multiple objectives. This type of model is used to solve a problem with real data in the region of Andalusia (Spain). Thus, we study the location of two incineration plants for the disposal of solid animal waste from some preestablished locations in Andalusia, and design the routes to serve the different slaughterhouses in this region. This must be done while taking into account certain economic objectives (start-up, maintenance, and transport costs) and social objectives (social rejection by towns on the truck routes, maximum risk as an equity criterion, and the negative implications for towns close to the plant).     

On equilibrium in pure strategies in games with many players

We demonstrate that, if there are sufficiently many players, any Bayesian equilibrium of an incomplete information game can be “ε-purified” . That is, close to any Bayesian equilibrium there is an approximate Bayesian equilibrium in pure strategies. Our main contribution is obtaining this result for games with a countable set of pure strategies. In order to do so we derive a mathematical result, in the spirit of the Shapley–Folkman Theorem, permitting countable strategy sets. Our main assumption is a “large game property,” dictating that the actions of relatively small subsets of players cannot have large affects on the payoffs of other players. E. Cartwright and M. Wooders are indebted to Phillip Reny, Frank Page and two anonymous referees for helpful comments.     

Implementability of correlated and communication equilibrium outcomes in incomplete information games

In a correlated equilibrium, the players’ choice of actions is directed by correlated random messages received from an outside source, or mechanism. These messages allow for more equilibrium outcomes than without any messages (pure-strategy equilibrium) or with statistically independent ones (mixed-strategy equilibrium). In an incomplete information game, the messages may also reflect the types of the players, either because they are affected by extraneous factors that also affect the types (correlated equilibrium) or because the players themselves report their types to the mechanism (communication equilibrium). Mechanisms may be further differentiated by the connections between the messages that the players receive and their own and the other players’ types, by whether the messages are statistically dependent or independent, and by whether they are random or deterministic. Consequently, whereas for complete information games there are only three classes of equilibrium outcomes, with incomplete information the corresponding number is 14 or 15 for correlated equilibria and even larger—15, 16 or 17—for communication equilibria. For both solution concepts, the implication relations between the different kinds of equilibria form a two-dimensional lattice, which is considerably more intricate than the single-dimensional one of the complete information case.     

Location game on disjoint line segments

Two players are endowed with resources for setting up N locations on K line segments of identical length, with N > K ≥ 1. The players alternately choose these locations (possibly in batches of more than one in each round) in order to secure the area closer to their locations than that of their rival’s. The player with the highest secured area wins the game and otherwise the game ends in a tie. Earlier research has shown that, if an analogous game is played on disjoint circles, the second mover advantage is in place only if K = 1, while for K > 1 both players have a tying strategy. It was also shown that these results hold for line segments of identical length when rules of the game additionally require players to take exactly one location in the first round. In this paper we show that the second mover advantage is still in place for K ≥ 1 and 2K − 1 ≤ N, even if the additional restriction is dropped, while K ≤ N < 2K − 1 results in the first mover advantage. Our results allow us to draw conclusions about a natural variant of the game, where the resource mobility constraint is more stringent so that in each round each player chooses a single location and we show that the second mover advantage re-appears for K ≤ N < 2K − 1 if K is an even number. In all the cases the losing player has a strategy guaranteeing him arbitrarily small loss.