Branch-and-Cut for Mixed-Integer Nash Equilibrium Problems

This paper introduces a branch-and-cut algorithm that reformulates mixed-integer Nash equilibrium problems as bilevel optimization tasks to either compute a pure Nash equilibrium or prove its non-existence, with specific adaptations and finite termination guarantees for both standard and generalized settings.

The Gist

Imagine a group of friends trying to decide where to go for dinner. Each person has their own strict rules: "I only eat Italian," "I can't spend more than $20," and "I hate crowded places." They all want to pick a restaurant that makes them happiest, but their happiness depends on what the others choose. If Alice picks a fancy Italian place, Bob might have to switch to a cheap pizza spot because he can't afford the fancy one anymore.

This is a Nash Equilibrium Problem: finding a state where no one wants to change their choice because, given what everyone else is doing, they are already doing the best they can.

Now, imagine adding a twist: some of these rules are "all-or-nothing" (like choosing a whole pizza vs. half a pizza) rather than smooth and continuous (like choosing 1.5 slices). This makes the math incredibly messy and hard to solve. This paper presents a new, powerful tool to solve these tricky "mixed-integer" games.

Here is the breakdown of their solution using simple analogies:

1. The Problem: A Maze with Dead Ends

The authors are dealing with games where players have integer constraints (whole numbers only). Think of it like a maze where you can only step on specific tiles (1, 2, 3) and not the spaces in between.

• Standard Games (NEP): Everyone has their own private maze, but the walls move slightly depending on where others are standing.
• Generalized Games (GNEP): The mazes themselves are shared. If Alice moves, she might block a path for Bob, changing his entire set of options.

The big question is: Does a stable solution exist where everyone is happy? And if it does, how do we find it without checking every single possible combination (which would take forever)?

2. The Solution: A Smart Detective with a "Cutting" Knife

The authors built a Branch-and-Cut (B&C) algorithm. Think of this as a super-smart detective trying to find a hidden treasure (the equilibrium) in a massive, dark warehouse.

Step A: The "Branching" (Splitting the Search)

Imagine the detective enters the warehouse and sees a huge pile of boxes. Instead of opening them one by one, they split the pile in half.

• "Okay, let's look at all the boxes where Player A chose 'Option 1'."
• "Now let's look at the pile where Player A chose 'Option 2'."
  This is Branching. They keep splitting the problem into smaller and smaller pieces until the pieces are small enough to solve easily.

Step B: The "Cutting" (Throwing Away the Garbage)

This is the paper's secret sauce. Sometimes, the detective finds a box that looks promising (it has a solution inside), but it's actually a trap. It's a solution that seems valid but isn't a true equilibrium because someone could still improve their situation.

Instead of just throwing that box away and moving on, the detective uses a Cut.

• The Metaphor: Imagine the warehouse is a room full of furniture. The detective realizes, "Wait, the treasure can't be behind this specific sofa." So, they take a laser cutter and slice the room in half, removing the sofa and everything behind it.
• The Math: They draw a mathematical line (a "cut") that says, "Any solution that looks like this specific bad guess is impossible." This line is called a Non-NE Cut.
  • For Standard Games, they use "Best-Response Cuts." It's like saying, "If you chose X, you would have chosen Y instead. So, X is impossible."
  • For Generalized Games, they use "Intersection Cuts." This is a more complex geometric trick that slices off a chunk of the impossible space, ensuring the real treasure is still inside the remaining room.

3. The Guarantee: "We Will Finish"

A major fear in these algorithms is getting stuck in an infinite loop, slicing the room forever without ever finding the treasure.
The authors proved that under certain realistic conditions (like when costs are "concave" or when players only care about integer choices), the algorithm must finish.

• The Analogy: They proved that every time they make a cut, they are permanently removing a chunk of the "bad guesses" that can never be reused. Since there are only a finite number of "bad guesses" to remove, the detective will eventually run out of bad guesses and either find the treasure or prove it doesn't exist.

4. The Results: It Actually Works

The team tested their method on four types of games:

1. Knapsack Games: Like packing a backpack where items have fixed weights.
2. Generalized Knapsack Games: Where the backpacks share a limited supply of items.
3. Traffic/Flow Games: Like routing data packets through a network where you can't split a packet in half.
4. Quadratic Games: Games with curved, complex cost functions.

The Verdict:

• Their method was faster and more reliable than previous methods for many of these problems.
• It successfully found solutions (or proved none existed) for games that were previously too hard to solve.
• It works like a "proof of concept," showing that this "detective with a laser cutter" approach is a viable way to solve complex real-world problems like energy markets, traffic routing, and supply chains.

Summary

In short, this paper introduces a new way to solve complex games where players have "all-or-nothing" choices. Instead of blindly guessing, the algorithm intelligently splits the problem and uses mathematical "laser cuts" to slice away impossible scenarios, guaranteeing that it will eventually find the perfect balance (equilibrium) or prove that no such balance exists.

Technical Summary

Here is a detailed technical summary of the paper "Branch-and-Cut for Mixed-Integer Nash Equilibrium Problems" by Duguet, Harks, Schmidt, and Schwarz.

1. Problem Statement

The paper addresses Mixed-Integer Nash Equilibrium Problems (NEPs) and Generalized Nash Equilibrium Problems (GNEPs).

• Context: In these games, $N$ players compete non-cooperatively. Each player $i$ solves a mixed-integer optimization problem parameterized by the strategies of rivals ($x_{-i}$).
• Variables: Strategies $x_i$ consist of integer components ($x_i^{int} \in \mathbb{Z}^{k_i}$) and continuous components ($x_i^{con} \in \mathbb{R}^{l_i}$).
• Distinction:
  • Standard NEPs: The strategy set $X_i$ is fixed and independent of rivals' strategies; only the cost function $\pi_i$ depends on $x_{-i}$.
  • Generalized NEPs (GNEPs): The strategy set $X_i(x_{-i})$ depends on rivals' strategies (e.g., via shared coupling constraints).
• Challenge: Due to integer constraints, strategy spaces are non-convex. Pure Nash Equilibria (NE) are not guaranteed to exist, and computing them is NP-hard. Existing methods often rely on convexification (which is computationally expensive) or are limited to pure integer settings.

2. Methodology

The authors propose a Branch-and-Cut (B&C) framework that reformulates the equilibrium search as a bilevel optimization problem.

2.1. Reformulation via Nikaido–Isoda Function

The search for an NE is transformed into finding a global minimizer of the Nikaido–Isoda (NI) function, $\hat{V}(x)$.

• $\hat{V}(x) = \max_{y \in X(x)} \sum_{i \in N} [\pi_i(x) - \pi_i(y_i, x_{-i})]$.
• Property: $\hat{V}(x) = 0$ if and only if $x$ is a Nash Equilibrium.
• Bilevel Formulation: The problem is modeled as minimizing $\hat{V}(x)$ subject to $x \in W$. This is reformulated as a single-level problem using an epigraph variable $\eta$ representing the best-response values:
  $$\min_{x, \eta} \sum \pi_i(x) - \eta_i \quad \text{s.t.} \quad \eta \leq \Phi(x)$$
  where $\Phi(x)$ is the vector of optimal values of the lower-level (best-response) problems.

2.2. The Branch-and-Cut Framework

The algorithm operates on a search tree where nodes represent relaxed subproblems:

1. Relaxation: The algorithm solves a Continuous High-Point Relaxation (C-HPR) at each node. This involves relaxing integrality constraints and dropping the lower-level constraints (replacing $\Phi(x)$ with a valid upper bound $\eta^+$).
2. Pruning: If the node is infeasible or the optimal objective value is strictly positive ($>0$), no NE exists in that node, and it is pruned.
3. Branching: If the solution has fractional integer variables, the algorithm branches on them.
4. Cutting (The Core Innovation): If an integer-feasible solution $(x^*, \eta^*)$ is found but is not an NE (i.e., $\hat{V}(x^*) > 0$), the algorithm generates a non-NE-cut to exclude this specific non-equilibrium point without removing any potential equilibria.

2.3. Cut Generation Strategies

The paper derives two distinct types of cuts based on the problem class:

• For Standard NEPs: Best-Response Cuts

  • Mechanism: Based on the observation that if $x^*$ is not an NE, there exists a player $i$ whose current cost $\pi_i(x^*)$ is strictly greater than their best response $\Phi_i(x^*_{-i})$.
  • Cut: $\eta_i \leq \pi_i(y^*_i, x_{-i})$, where $y^*_i$ is the best response.
  • Validity: These cuts are globally valid (valid for all nodes) and do not require additional assumptions on convexity.

• For GNEPs: Intersection Cuts (ICs)

  • Mechanism: Inspired by mixed-integer bilevel optimization (Fischetti et al., 2018). The algorithm constructs a cone $K$ pointing at the non-equilibrium solution and an NE-free convex set $S$ containing the solution but no equilibria.
  • Requirements:
    • Cost and constraint functions must be convex in rivals' strategies.
    • Constraints must be linear (or integer-valued).
    • Social cost functions (sum of all players' costs) must be concave (often linear) to ensure the optimal solution lies at a vertex of the polytope.
  • Result: An intersection cut is derived that separates the current non-NE solution from the feasible region containing equilibria.

3. Key Contributions

1. First B&C Framework for Mixed-Integer Games: This is the first algorithm capable of computing pure NE or proving non-existence for general mixed-integer games (both NEPs and GNEPs) within a single-tree framework.
2. Theoretical Guarantees of Finite Termination:
   • For NEPs: Proves finite termination if the set of best-response sets is finite. This holds for:
     • Games with concave cost functions in continuous variables.
     • Games where costs depend only on own strategy and rivals' integer components.
   • For GNEPs: Establishes sufficient conditions (linear constraints, convexity in rivals' strategies) for the existence of intersection cuts.
3. Correctness Proof: Theorem 3.3 proves that if the algorithm terminates, it either outputs a valid NE or a certificate of non-existence.
4. Comparison with Existing Methods:
   • Unlike Branch-and-Prune (Schwarze & Stein, 2023), which relies on strict monotonicity and dominance pruning, this method uses cuts to tighten relaxations.
   • Unlike Cut-and-Play (Carvalho et al., 2021), which targets mixed NE via convexification, this method targets pure NE directly without constructing a convexified game.

4. Numerical Results

The authors implemented the algorithm in C++ (using Gurobi for subproblems) and tested it on four game classes:

1. Knapsack Games (NEP):

   • Solved instances with up to 80 items and 4 players.
   • Mixed-integer instances were solved faster than pure-integer ones in terms of node count, though continuous variables slowed down node resolution.
   • Outperformed the pure cutting-plane method of Dragotto and Scatamacchia (2023) on larger, harder instances where the latter failed.

2. Generalized Knapsack Games (GNEP):

   • Used intersection cuts.
   • Generated significantly more cuts than NEPs (locally valid cuts), but the node problems were easier (LPs vs. non-convex QPs).

3. Implementation Games (TCP Congestion Control):

   • Modeled as a GNEP with a central authority.
   • High success rate (41% solved within 1 hour); 22% solved at the root node due to total unimodularity of flow constraints.

4. Quadratic Integer NEPs:

   • Comparison: Compared against the Branch-and-Prune (B&P) method of Schwarze and Stein (2023).
   • Performance: The B&C method solved 50 out of 56 instances, while B&P solved only 21.
   • Speed: B&C was on average 6.3 times faster than B&P.
   • Robustness: B&P failed on some instances due to wrong pruning (pruning a valid NE) or numerical errors, whereas B&C remained robust.

5. Significance and Conclusion

• Bridging the Gap: The paper successfully bridges the gap between mixed-integer bilevel optimization and game theory, adapting powerful techniques like intersection cuts to the Nash equilibrium setting.
• Practical Impact: It provides a computationally tractable method for finding pure equilibria in non-convex games, which are prevalent in energy markets, transport, and telecommunications but were previously difficult to solve exactly.
• Future Work: The authors suggest extending intersection cuts to general convex (non-linear) constraints and developing game-specific branching rules to further improve performance.

In summary, this work establishes a rigorous, theoretically grounded, and empirically superior algorithm for solving mixed-integer Nash equilibrium problems, outperforming existing state-of-the-art methods in both speed and reliability.