Multiple voting location problems

The facility voting location problems arise from the application of criteria derived from the voting processes concerning the location of facilities. The multiple location problems are those location problems in which the alternative solutions are sets of points. This paper extends previous results and notions on single voting location problems to the location of a set of facility points. The application of linear programming techniques to solve multiple facility voting location problems is analyzed. We propose an algorithm to solve Simpson multiple location problems from which the solution procedures for other problems are derived.     

Two-player simultaneous location game: Preferential rights and overbidding

Competitive location problems can be characterized by the fact that the decisions made by others will affect our own payoffs. In this paper, we address a discrete competitive location game in which two decision-makers have to decide simultaneously where to locate their services without knowing the decisions of one another. This problem arises in a franchising environment in which the decision-makers are the franchisees and the franchiser defines the potential sites for locating services and the rules of the game. At most one service can be located at each site, and one of the franchisees has preferential rights over the other. This means that if both franchisees are interested in opening the service in the same site, only the one that has preferential rights will open it. We consider that both franchisees have budget constraints, but the franchisee without preferential rights is allowed to show interest in more sites than the ones she can afford. We are interested in studying the influence of the existence of preferential rights and overbidding on the outcomes for both franchisees and franchiser. A model is presented and an algorithmic approach is developed for the calculation of Nash equilibria. Several computational experiments are defined and their results are analysed, showing that preferential rights give its holder a relative advantage over the other competitor. The possibility of overbidding seems to be advantageous for the franchiser, as well as the inclusion of some level of asymmetry between the two decision-makers.     

Sequential competitive location on networks

We present a survey of recent developments in the field of sequential competitive location problems, including the closely related class of voting location problems, i.e. problems of locating resources as the result of a collective election. Our focus is on models where possible locations are not a priori restricted to a finite set of points. Furthermore, we restrict our attention to problems defined on networks. Since a line, i.e. an interval of one-dimensional real space, may be interpreted as a special type of network and because models defined on lines might contain ideas worth adopting in more general network models, we include these models as well, yet without describing them in detail for the sake of brevity.     

The k-level facility location game

We propose a cost-sharing scheme for the k-level facility location game that is cross-monotonic, competitive, and 6-approximate cost recovery. This extends the recent result for the 1-level facility location game of Pál and Tardos.     

Soft-capacitated facility location game

We study the soft-capacitated facility location game which is an extension of the facility location game of Pa1 and Tardos. We propose a 6-approximate cross-monotonic cost-sharing method. Numerical tests indicate that the method is effective.     

A competitive hub location and pricing problem

We formulate and solve a new hub location and pricing problem, describing a situation in which an existing transportation company operates a hub and spoke network, and a new company wants to enter into the same market, using an incomplete hub and spoke network. The entrant maximizes its profit by choosing the best hub locations and network topology and applying optimal pricing, considering that the existing company applies mill pricing. Customers’ behavior is modeled using a logit discrete choice model. We solve instances derived from the CAB dataset using a genetic algorithm and a closed expression for the optimal pricing. Our model confirms that, in competitive settings, seeking the largest market share is dominated by profit maximization. We also describe some conditions under which it is not convenient for the entrant to enter the market.     

A note on “Location of hubs in a competitive environment”

This note suggests modifications to two models for locating hubs in a competitive environment introduced by Marianov et al. [European Journal of Operational Research 114 (1999) 363–371]. They make it possible to provide optimal solutions much faster. It is also shown that the implementation of the heuristic proposed by Marianov et al. contains a flaw. Yet the heuristic itself is correct.     

A two-player competitive discrete location model with simultaneous decisions

In this paper we will describe and study a competitive discrete location problem in which two decision-makers (players) will have to decide where to locate their own facilities, and customers will be assigned to the closest open facilities. We will consider the situation in which the players must decide simultaneously, unsure about the decisions of one another, and we will present the problem in a franchising environment. Most problems described in the literature consider sequential rather than simultaneous decisions. In a competitive environment, most problems consider that there is a set of known and already located facilities, and new facilities will have to be located, competing with the existing ones. In the presence of more than one decision-maker, most problems found in the literature belong to the class of Stackelberg location problems, where one decision-maker, the leader, locates first and then the other decision-maker, the follower, locates second, knowing the decisions made by the first. These types of problems are sequential and differ significantly from the problem tackled in this paper, where we explicitly consider simultaneous, non-cooperative discrete location decisions. We describe the problem and its context, propose some mathematical formulations and present an algorithmic approach that was developed to find Nash equilibria. Some computational tests were performed that allowed us to better understand some of the features of the problem and the associated Nash equilibria. Among other results, we conclude that worsening the situation of a player tends to benefit the other player, and that the inefficiency of Nash equilibria tends to increase with the level of competition.     

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.     

Multiple voting location and single voting location on trees

We examine voting location problems in which the goal is to place, based on an election amongst the users, a given number of facilities in a graph. The user preference is modeled by shortest path distances in the graph. A Condorcet solution is a set of facilities to which there does not exist an alternative set preferred by a majority of the users. Recent works generalize the model to additive indifference and replaced user majority by γ-proportion.     

A cross-monotonic cost sharing method for the facility location game with service installation costs

In this paper,we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the installation cost depends only on the service type.     

Competitive facility location model with concave demand

We consider a spatial interaction model for locating a set of new facilities that compete for customer demand with each other, as well as with some pre-existing facilities to capture the “market expansion” and the “market cannibalization” effects. Customer demand is assumed to be a concave non-decreasing function of the total utility derived by each customer from the service offered by the facilities. The problem is formulated as a non-linear Knapsack problem, for which we develop a novel solution approach based on constructing an efficient piecewise linear approximation scheme for the objective function. This allows us to develop exact and α-optimal solution approaches capable of dealing with relatively large-scale instances of the model. We also develop a fast Heuristic Algorithm for which a tight worst-case error bound is established.     

Finding the optimal solution to the Huff based competitive location model

In this paper we solve the gravity (Huff) model for the competitive facility location problem. We show that the generalized Weiszfeld procedure converges to a local maximum or a saddle point. We also devise a global optimization procedure that finds the optimal solution within a given accuracy. This procedure is very efficient and finds the optimal solution for 10,000 demand points in less than six minutes of computer time. We also experimented with the generalized Weiszfeld algorithm on the same set of randomly generated problems. We repeated the algorithm from 1,000 different starting solutions and the optimum was obtained at least 17 times for all problems.     

Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique

This paper deals with the uncapacitated multiple allocation hub location problem. The dual problem of a four-indexed formulation is considered and a heuristic method, based on a dual-ascent technique, is designed. This heuristic, which is reinforced with several specifical subroutines and does not require any external linear problem solver, is the core tool embedded in an exact branch-and-bound framework. Besides, the heuristic provides the branch-and-bound algorithm with good lower bounds for the nodes of the branching tree. The results of the computational experience (with the classical CAB and AP data sets) are included, showing the great effectiveness of this approach: instances with up to 120 nodes are solved.     

Facility location problems in the plane based on reverse nearest neighbor queries

For a finite set of points S, the (monochromatic) reverse nearest neighbor (RNN) rule associates with any query point q the subset of points in S that have q as its nearest neighbor. In the bichromatic reverse nearest neighbor (BRNN) rule, sets of red and blue points are given and any blue query is associated with the subset of red points that have it as its nearest blue neighbor. In this paper we introduce and study new optimization problems in the plane based on the bichromatic reverse nearest neighbor (BRNN) rule. We provide efficient algorithms to compute a new blue point under criteria such as: (1) the number of associated red points is maximum (MAXCOV criterion); (2) the maximum distance to the associated red points is minimum (MINMAX criterion); (3) the minimum distance to the associated red points is maximum (MAXMIN criterion). These problems arise in the competitive location area where competing facilities are established. Our solutions use techniques from computational geometry, such as the concept of depth of an arrangement of disks or upper envelope of surface patches in three dimensions.     

A stopping game in a stochastic and fuzzy environment

A zero-sum stopping game for a sequence of fuzzy-valued random variables is discussed. The fuzzy random variables are estimated by probabilistic expectation and fuzzy expectation. A saddle point is given for the stopping game.     

Recent insights in Huff-like competitive facility location and design

Recently, several articles appeared on the location–design problem that firms face when entering a competing market. All use a Huff-like attraction model. We discuss the formulation of the base model, the different settings studied in the papers and summarise their findings.     

An intersection theorem in TU cooperative game theory

We prove a theorem on the intersection of the Weber sets (Weber, 1988) of two ordered cooperative games. From this theorem several consequences are derived, the inclusion of the core in the Weber set (Weber, 1988), the fact that every convex game has a large core (Sharkey, 1982), and a discrete separation theorem (Frank, 1982). We introduce a definition of general largeness, proving that the Weber set is large for any cooperative game.Institutional support from research grants SGR2001-0029 and BEC 2002-00642 is gratefully acknowledged.     

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.