# Maximum weight matching with surreal weights

Is there an efficient algorithm for finding a maximum weight matching in a graph where the weight of each edge is a surreal number?

On one hand, I think that algorithms (like Edmonds's) should work for surreal numbers as well--this might follow from standard methods in nonstandard analysis.
On the other, this would solve finding maximum weight maximum cardinality matchings, which is claimed to be open in this paper. Added: Seems like this should not be open, see the comment by Neal.

• (1) Are you asking whether there is an efficient algorithm for the problem, or just whether such a max-weight matching always exists? If the former, how is the input encoded? (2) I'm confused by the assertion that it is not known how to find (presumably in poly time) a matching of maximum weight among matchings of maximum cardinality. Surely this can be done by asking for a max-weight matching in the graph with an appropriate encoding of the edge weights (e.g. give edge $e$ weight $1+\epsilon w_e$ for positive $\epsilon \ll 1/\sum_e w_e$)? What am I missing? Commented Jan 17, 2023 at 2:02
• (1) Yes, and I hope I won't have to define the encoding. I assume addition/subtraction, comparison are allowed, like on a real RAM machine. (2) I was also confused by the very same thing, my essentially same construction was adding $\sum w_i$ to the weight of each edge. Then I assume this problem is not so open, though there are several references to it online: google.com/… Commented Jan 17, 2023 at 5:34
• @Emil Yes, I also think so, thank you for confirming it. Do you maybe have a reference for this? Commented Jan 17, 2023 at 7:59
• @Emil: Would you put together these comments into an answer that I can accept and cite? Commented Jan 17, 2023 at 15:57

Fix any algorithm that works for integer edge weights, and treats the weights as black boxes that can be copied, added, subtracted, and compared, but cannot be accessed in any other way. Furthermore, assume that the algorithm terminates in time bounded by a function $$t(n)$$ of the number of vertices of the graph, independent of the weights. We may assume the input graph is the complete graph, with missing edges represented by $$0$$ weights.

I claim that such an algorithm also works for weights valued in arbitrary (totally) ordered abelian groups. This follows from the following two observations.

Lemma 1: For any $$n$$, the soundness of the algorithm on graphs of order $$n$$ can be expressed by a universal first-order sentence in the language of ordered groups.

Proof: For fixed $$n$$, the computation of the algorithm can be described by a tree that branches whenever two black boxes are compared; at each node of the tree, the content of each black box is given by a linear function of the input weights $$\{x_{i,j}:i,j\in[n]\}$$ with integer coefficients. If $$\{\ell_t:t\in[m]\}$$ is an enumeration of leaves of the tree, let $$\theta_t(\vec x)$$ denote the conjunction of the linear inequalities or their negations that determine the path leading to $$\ell_t$$, and let $$M_t$$ denote (the set of edges of) the matching that’s output at $$\ell_t$$. Then $$\bigvee_{t\in[m]}\theta_t(\vec x)$$ is a tautology, and the soundness of the algorithm is expressed by the universal sentence $$\forall\vec x\:\bigwedge_{t\in[m]}\bigwedge_M\Bigl(\theta_t(\vec x)\to\sum_{\{i,j\}\in M_t}x_{i,j}\ge\sum_{\{i,j\}\in M}x_{i,j}\Bigr),$$ where $$M$$ runs over all (finitely many) matchings on $$[n]$$.

Lemma 2: Every universal sentence true in $$(\mathbb Z,+,\le)$$ holds in all ordered abelian groups.

Proof: An ordered abelian group $$(G,+,\le)$$ embeds in its divisible hull $$G\otimes_\mathbb Z\mathbb Q$$ (which carries a unique order $$\le'$$ extending $$\le$$ that makes it an ordered group, namely $$x\le'y\iff nx\le ny$$ for some/all $$n\in\mathbb N_{>0}$$ such that $$nx,ny\in G$$). This in turn embeds in $$(G\otimes_\mathbb Z\mathbb Q)\oplus\mathbb Z$$, ordered lexicographically so that $$\mathbb Z$$ is a convex subgroup. Being an extension of a divisible ordered abelian group by $$\mathbb Z$$, this is a $$\mathbb Z$$-group, thus it is elementarily equivalent to $$\mathbb Z$$. It follows that any universal sentence true in $$\mathbb Z$$ is true in $$(G\otimes_\mathbb Z\mathbb Q)\oplus\mathbb Z$$, and therefore in $$G$$.

Alternatively, every nontrivial finitely generated subgroup of $$\mathbb Q$$ is isomorphic to $$\mathbb Z$$, thus a universal sentence true in $$(\mathbb Z,+,\le)$$ is also true in $$(\mathbb Q,+,\le)$$. It follows that it is true in all divisible ordered abelian groups such as $$G\otimes_\mathbb Z\mathbb Q$$, and consequently in $$G$$.

(The first argument relies on completeness of the theory of $$\mathbb Z$$-groups, aka Presburger arithmetic; the second argument on completeness of the theory of nontrivial divisible ordered abelian groups.)

A final note: the statements above apply to ordered abelian groups that are sets, whereas the question asks for surreal numbers, which form a proper class. But this is of no consequence: we can just look at the subgroup of the surreals generated by the (finitely many) weights of the given graph, which is a countable set.