Oriented Euler complexes and signed perfect matchings

László A. Végh, Bernhard von Stengel

Abstract

This paper establishes a unified framework for oriented pivoting systems, proving that the endpoints of complementary pivoting paths possess opposite signs. By introducing the concept of "oriented oiks" (Euler complexes), the authors provide a simplified proof for the parity of solutions in mathematical optimization and game theory. Furthermore, they present a near-linear time algorithm for finding a second perfect matching of opposite sign in Euler digraphs, significantly improving upon the exponential complexity of traditional pivoting approaches.

Introduction

In mathematical optimization and game theory, finding solutions such as Nash equilibria often relies on "complementary pivoting" algorithms, most notably the Lemke–Howson algorithm. These methods traverse a path through a high-dimensional state space. While it has long been known that these paths eventually terminate at a solution, two fundamental challenges remained: the "Sign Problem"—proving that start and end points have opposite indices—and the "Speed Problem"—the fact that these paths can be exponentially long.

To address these, the authors generalize the geometry of these problems into "Euler complexes," or oiks. This framework allows for a unified treatment of the orientation and parity of solutions across various problem classes.

Oriented Pivoting Systems and Oiks

The paper's primary theoretical contribution is the definition of oriented pivoting systems. By tracking "direction" through permutations and orientations, the authors provide a simplified proof that the two ends of a pivoting path must have opposite signs.

They extend this to oriented oiks, which are collections of "rooms" (sets of nodes) where every "wall" (a subset of nodes) is shared by an even number of rooms. This structure generalizes manifolds and graphs, providing a robust geometric language for pivoting problems. The authors show that the sign of a solution is not merely a label but a fundamental property of the complex's orientation; pivoting essentially flips a determinant's sign or a permutation's parity at each step.

The Sign-Switching Algorithm

For the specific case of two-dimensional oiks—which correspond to Euler digraphs—the authors move beyond simple pivoting. They introduce a "Sign-Switching" algorithm that utilizes graph-theoretic reductions, such as node shrinking and the identification of sign-switching cycles.

Figure 1: A representation of a cycle in an Euler digraph, illustrating the structural components used in sign-switching algorithms.

This approach leverages the connection between the sign of perfect matchings and the theory of Pfaffian orientations. Since an Eulerian orientation is never Pfaffian, matchings will necessarily have different signs. The algorithm exploits this property to find a second solution quickly by identifying specific cycles in the graph rather than walking an entire exponential path.

Key Results and Complexity

The paper delivers two major results:

  1. Unified Parity Theorem: Theorem 3 proves that for any oriented pivoting system, the number of "completely labeled" states with a positive sign equals the number with a negative sign.
  2. Algorithmic Speedup: Theorem 12 introduces an algorithm to find a second perfect matching of opposite sign in an Euler digraph in $O(|E| \alpha(|V|))$ time, where $\alpha$ is the inverse Ackermann function.

This near-linear complexity represents a massive improvement over traditional complementary pivoting, which is known to be exponential in the worst case for this class of problems.

Limitations and Future Outlook

While the 2D case (graphs) is now solvable in near-linear time, higher-dimensional oiks remain a challenge. The authors leave the complexity of finding a second room partition in a 3-dimensional oik as an open question, noting it may be PPAD-complete. Additionally, while the framework covers Nash equilibria and Linear Complementarity Problems (LCPs), the direct application of the fast algorithm to general bimatrix games requires further research, as these games do not always reduce to simple 2D Euler graphs.

Summary updated

Abstract

This paper presents “oriented pivoting systems” as an abstract framework for complementary pivoting. It gives a unified simple proof that the endpoints of complementary pivoting paths have opposite sign. A special case are the Nash equilibria of a bimatrix game at the ends of Lemke–Howson paths, which have opposite index. For Euler complexes or “oiks”, an orientation is defined which extends the known concept of oriented abstract simplicial manifolds. Ordered “room partitions” for a family of oriented oiks come in pairs of opposite sign. For an oriented oik of even dimension, this sign property holds also for unordered room partitions. In the case of a two-dimensional oik, these are perfect matchings of an Euler graph, with the sign as defined for Pfaffian orientations of graphs. A near-linear time algorithm is given for the following problem: given a graph with an Eulerian orientation with a perfect matching, find another perfect matching of opposite sign. In contrast, the complementary pivoting algorithm for this problem may be exponential.
BibTeX
@article{vegh2015oriented,
  author = {László A. Végh and Bernhard von Stengel},
  title = {{Oriented Euler complexes and signed perfect matchings}},
  journal = {Math. Program.},
  year = {2015},
  doi = {10.1007/s10107-014-0770-4},
}

Loading related content...

Figure