Game Theoretic Approaches to Competitive Location Choice: A Mathematical Perspective

Tags: #Game Theory

In this post, I present an in‐depth analysis of a project that investigates optimal location choices for competing firms using concepts from graph theory and game theory. The project models a set of cities as nodes in a graph and employs two primary methods: the iterated elimination of strictly dominated strategies and local search dynamics. I provide a detailed exposition of the mathematical foundations, algorithms, and extensions implemented to reflect more realistic scenarios. This is my answer to a university assignement.

1. Project Overview

The project is set in a region with $( n )$ cities, where each city $( i )$ is characterized by its population $( \text{pop}(i) )$ and geographical coordinates $((\lambda_i, \phi_i))$. Firms choose locations from among these cities in order to maximize the number of products sold. Every inhabitant is assumed to purchase exactly one unit of the product, and they patronize the firm located in the nearest city. In the event that two firms choose the same city, they share the market equally.

The problem is approached in several stages:

  • Problem 1: Construction of a graph (via an adjacency matrix) where cities are connected if the Euclidean distance (or a more precise geographical distance calculation) is below a specified threshold.
  • Problem 2: Use of iterated elimination to remove strictly dominated strategies from the decision set.
  • Problem 3: Application of local search dynamics to find equilibrium locations.
  • Problem 4: Investigation of parameter sensitivity and the introduction of real-life extensions such as variable pricing and distinct sets for cities and potential locations.

Assignment details can be found here.

2. Modeling the Region: Graphs and Data Structures

2.1. City Graph Construction

The first step involves representing the geographical region as a graph:

  • Vertices: Each city is a vertex $( v_i \in V )$.
  • Edges: An edge $( e = {v_i, v_j} )$ exists if the computed distance between cities $( i )$ and $( j )$ is less than a threshold $( d_{\text{th}} )$ (e.g., 40 km).

The distance between two cities is computed from their latitude and longitude. While the project uses a method embedded in an object-oriented design (with a method such as distanceTo), mathematically one might employ the Haversine formula or Euclidean approximations for short distances.

An adjacency matrix $( A )$ is then defined as: $$ A_{ij} = \begin{cases} \text{round}(\text{dist}(i, j)), & \text{if } \text{dist}(i,j) < d_{\text{th}}, \ 0, & \text{otherwise.} \end{cases} $$ This matrix provides a concise representation of which cities are “neighbors” and is crucial for subsequent computations.

3. Iterated Elimination of Strictly Dominated Strategies

3.1. Theoretical Background

In game theory, consider a two-player (bimatrix) game where each firm chooses a strategy (i.e., a city) from a set $( S )$. For firm $( i )$, a strategy $( s_i \in S )$ is strictly dominated by another strategy $( s_i’ )$ if: $$ \forall s_{-i} \in S_{-i} : u_i(s_i’, s_{-i}) > u_i(s_i, s_{-i}), $$ where $( u_i )$ is the utility function (in this case, the utility is derived from the number of inhabitants served).

Iterated elimination of strictly dominated strategies is based on the theorem that, in finite games, repeatedly removing strictly dominated strategies does not eliminate any Nash equilibria. In many cases, this process can lead to a unique surviving strategy, thus greatly simplifying the decision problem.

3.2. Recursive Algorithm

The implementation employs a recursive algorithm that progressively reduces the utility matrix. Let:

  • $( U )$ be the utility matrix for firm A,
  • $( I )$ be the corresponding index matrix mapping matrix entries to city indices.

The pseudocode for the elimination procedure is as follows:

function eliminateDominated(U, I):
    if (U has only one row/column):
        return (U[0][0], I[0][0])
    for each row i in U:
        for each row j in U:
            dominated = true
            for each column k:
                if (U[i][k] >= U[j][k]):
                    dominated = false
                    break
            if (dominated):
                U_new = deleteRowAndColumn(U, j)
                I_new = deleteRowAndColumn(I, j)
                return eliminateDominated(U_new, I_new)
    return failureIndicator

This algorithm systematically checks for a row (and the corresponding column, due to symmetry) that is strictly dominated, eliminates it, and recurses on the reduced matrix. The mathematical beauty here lies in the fact that if the game is dominance solvable, the iterative process converges to a unique outcome that represents the optimal location for a firm.

For example, the algorithm yielded Utrecht as the surviving city with a utility of approximately 3,467,050, indicating that despite not being the largest by population, its strategic location makes it resilient against domination by any other city.

4. Local Search Dynamics

4.1. Best Response Dynamics

Local search provides an alternative approach based on best response dynamics. In this method, firms start from an initial guess (or a user-specified starting city) and then iteratively consider whether moving to a neighboring city can improve their payoff. Formally, a firm’s current strategy $( s_i^* )$ is a best response if:

$$ \forall s_i \in S, \quad u_i(s_i^*, s_{-i}) \geq u_i(s_i, s_{-i}). $$

4.2. Algorithmic Implementation

The local search procedure works as follows:

  • Initialization:
    Set initial locations $( s_A^{(0)} )$ and $( s_B^{(0)} )$ for firms A and B.

  • Iterative Improvement:

    • For firm B, fix $( s_A )$ and evaluate all neighboring cities in the same row of the utility matrix. Firm B moves to the city that minimizes the utility for firm A (since the game is zero-sum in the sense that the total market is constant).
    • Similarly, for firm A, fix $( s_B )$ and find the neighboring city that maximizes its own utility.

  • Termination:
    The process stops when no unilateral move can further improve a firm’s payoff (i.e., when a Nash equilibrium is reached) or after a fixed number of iterations if a cycle is detected.

In our study, the local search dynamic consistently converged to Eindhoven for both firms, with the system stabilizing after approximately 5 iterations. This result underscores the fact that while local search is computationally efficient, it might settle on a locally optimal solution rather than a global optimum.

5. Sensitivity Analysis and Real-Life Extensions

5.1. Sensitivity Analysis

An extensive investigation was conducted to analyze the sensitivity of the outcomes to various factors:

  • Starting Positions:
    Iterating over all possible initial configurations revealed that, despite differing iteration counts (from 2 to 7 iterations), the elimination process always converged to the same equilibrium.

  • Edge Distance Thresholds:
    Varying the threshold for connecting cities dramatically affects the graph structure. A small threshold yields a sparse graph, while a large threshold results in a fully connected graph, altering the strategic dynamics.

These observations highlight the importance of parameter selection in algorithmic game theory and the robustness of the iterative elimination method.

5.2. Real-Life Extensions

To bring the model closer to a realistic scenario, several extensions were incorporated:

  • Distinct Sets of Cities and Locations:
    Instead of assuming that every city is a potential location, an additional set of candidate locations was introduced. This separation better reflects practical constraints.

  • Variable Pricing:
    Recognizing that larger cities can sustain higher prices, the model was extended so that cities with populations greater than 200,000 incur a 20% higher price. This modification alters the utility function $( u_i )$ such that:

    $$ u_i = \text{pop}(i) \times p(i), $$

    where $( p(i) = 1 )$ for most cities and $( p(i) = 1.2 )$ for larger cities.

  • Customer Travel Boundaries:
    The model also considers a maximum travel distance for customers, which further refines the neighborhood relationships within the graph.

These extensions not only add layers of realism but also necessitate a reexamination of the equilibrium conditions and convergence properties of the algorithms.

6. Mathematical Analysis and Game Theory Foundations

6.1. Definitions and Theorems

  • Strict Dominance:
    A strategy $( s_i )$ is strictly dominated by $( s_i’ )$ if

    $$ \forall s_{-i}, \quad u_i(s_i’, s_{-i}) > u_i(s_i, s_{-i}). $$

  • Iterated Elimination of Dominated Strategies (IEDS):
    The process of sequentially removing strictly dominated strategies. In finite games, IEDS preserves all Nash equilibria.

  • Nash Equilibrium:
    A strategy profile $( s_A^* , s_B^* )$ is a Nash equilibrium if

$$ u_A(s_{A}^{\ast}, s_{B}^{\ast}) \geq u_A(s_{A}, s_{B}^{\ast}) \quad \text{and} \quad u_B(s_{A}^{\ast}, s_{B}^{\ast}) \geq u_B(s_{A}^{\ast}, s_{B}) $$

for all $( s_A, s_B )$ in the strategy sets.

6.2. Complexity Considerations

The recursive algorithm for eliminating dominated strategies has a worst-case time complexity that depends on the number of strategies $( |S| )$. Although elimination reduces the dimensionality of the game, in the worst case (when no strategy is dominated) the algorithm may perform comparisons on the order of $( O(|S|^3) )$. The practical performance, however, is often much better due to early termination when a strictly dominated strategy is found.

7. Conclusion

This project illustrates how classical game theoretic methods can be effectively employed in computational settings to solve location choice problems. The iterated elimination of strictly dominated strategies and local search dynamics offer complementary approaches:

  • Iterated Elimination:
    Provides a mathematically rigorous method to pare down the decision space to a uniquely optimal solution (when the game is dominance solvable).

  • Local Search:
    Offers a pragmatic route to reach an equilibrium through best-response dynamics, though it may converge to a local rather than global optimum.

The incorporation of real-life factors such as variable pricing and customer travel constraints further demonstrates the model’s adaptability and potential for extension. This blend of theoretical elegance and computational implementation underscores the rich interplay between mathematics, economics, and computer science.

Feel free to provide feedback or reach out with questions regarding any of the methods or analyses discussed in this post.