Diskrete Mathematik und Optimierung

Winfried Hochstättler, Hui Jin, Robert Nickel:

The Hungarian Method in a Mixed Matching Market

Technical Report feu-dmo004.05

Contact: {winfried.hochstaettler, robert.nickel}@fernuni-hagen.de

FernUniversität in Hagen
Lehrgebiet Mathematik
Lehrstuhl für Diskrete Mathematik und Optimierung
D – 58084 Hagen
2000 Mathematics Subject Classification: 91A12, 91B68
Keywords: Assignment Game, Core, Hungarian Method, Stable Matching
 The Hungarian Method in a Mixed Matching
Market
Winfried Hochstättler Hui Jin
Department of Mathematics Department of Mathematics
FernUniversität in Hagen BTU Cottbus
D-58084 Hagen D-03013 Cottbus
Robert Nickel
Department of Mathematics
FernUniversität in Hagen
D-58084 Hagen
November 24, 2005

Abstract
We present an algorithm that computes a stable matching in a common
generalization of the marriage and the assignment game in O(n4 ) time.

1 Introduction
Since its introduction by Gale and Shapley [11] the stable marriage problem has
become quite popular among scientists from different fields such as game theory,
economics, computer science, and combinatorial optimization. Among others
this is mirrored by three monographs: Knuth [15], Gusfield and Irving [13], Roth
and Sotomayor [21]. The problem is the following: Given two disjoint groups of
players (men-women or workers-firms etc.), where each player is endowed with
a preference list on the other group, the objective is to match the players from
one group to players from the other group such that there is no pair which is
not matched but prefers each other over their partners. Gale and Shapley [11]
showed that such a stable matching always exists. The proof is algorithmic
and the algorithm has become famous under the name “men propose – women
dispose”.
In their award winning book Roth and Sotomayor [21] observed that the
set of stable solutions from another game on bipartite matching, namely the
assignment game [22], has several structural similarities with the set of stable
matchings. They challenged the readers to find a unifying theory for the two
games. In the assignment game we are given a weighted bipartite graph. A
solution consists of a matching and an allocation of its weight to the players.

1
A solution is stable if no pair gets allocated less than the weight of its con-
necting edge. Shapley and Shubik [22] observed that this condition is identical
to the dual constraints of the linear programming model for weighted bipartite
matching, thus the dual variables in an optimal solution coincide with the stable
allocations. However, algorithms and complexity issues of game theoretic solu-
tion concepts have raised attention only recently (see e. g. [3], [6], [2]) and the
classical algorithm for weighted bipartite matching, namely what is nowadays
called the Hungarian Method ([8]), is not as prominent in game theory as it
is in combinatorial optimization. However, Demange et al. [1] claim that their
“exact” auction procedure that proves the existence of stable solutions were a
variant of Kuhn’s [16] method.
Roth and Sotomayor [20] themselves presented a first model unifying stable
matching and the assignment game and showed that its set of stable solutions, if
it is non-empty, has the desired structural properties. Eriksson and Karlander [5]
modified this model to the one presented in this paper and gave an algorithmic
proof of the existence of a stable solution. For the classical special cases, their
algorithm coincides with “men propose – women dispose”, respectively with
the “exact” auction procedure of [1]. As implemented, this algorithm is not
polynomial time but pseudopolynomial. Also it yields a proof of the existence
of stable solutions in presence of irrational data only via arguments from non-
standard analysis. A careful analysis [14] of the algorithm, though, reveals that
a proper implementation solves the problem in O(n4 ) similar to the algorithm
presented here.
Sotomayor [23] gave an alternative proof of the existence of stable solutions
of the model of Eriksson and Karlander. The purpose of the present paper is
to extract an algorithm from the key lemma of Sotomayor [23] that computes a
stable solution in O(n4 ). In the case of the assignment game this algorithm
specializes to the implementation of the Hungarian Method where a search
tree (and not a forest) is grown starting from a single unmatched vertex. For
stable marriage we derive a sort of asynchronous implementation of the original
“men propose – women dispose” that does not proceed in rounds and, hereby,
corresponds to efficient implementations of that algorithm (see e. g. Gusfield and
Irving [13]).
Fujishige and Tamura [9] presented a market model in the theory of discrete
convex analysis (see [19]) with M \ -concave utility functions that contains the
Stable Marriage Model of [11], the Assignment Game of [22], and the model
of Eriksson and Karlander [5], as well as other recently published models ([4],
[7], [10]) as special case. They present a pseudopolynomial time algorithm to
find a stable solution for the general model which becomes polynomial when
restricted to instances of the present model. A careful analysis reveals that it
can be implemented with only slightly worse complexity. In the last section we
will discuss this in more detail.
In the next section we introduce the model, discuss its special cases in Sec-
tion 3 and present and analyze our algorithm in Section 4. We assume some
familiarity with bipartite matching and combinatorial optimization. Our nota-
tion should be fairly standard.

2
2 Notation
The following model, originally introduced by Eriksson and Karlander [5], dis-
plays a two-sided market, where we have two types of players, P and Q which
we call firms and workers. Moreover, both sets are again subdivided into flexible
(F ) and rigid players (R) so that P ∪Q ˙ = F ∪R.
˙ If a firm i ∈ P is matched to
a worker j ∈ Q they get a certain benefit aij + bij from that relationship. If
both players are flexible, they can negotiate on how to split up this amount. If
at least one player is rigid i receives aij and j receives bij .
Thus, mathematically we have the following. Let G = (P ∪ Q, E, a, b) be a
complete bipartite graph with two non-negative weight functions a, b : E → R+
˙ = F ∪R
and P ∪Q ˙ another partition of the vertices.
A set M ⊆ E is called a matching if each vertex of G is contained in at most
one edge of M and we denote by VM ⊆ V the set of matched vertices of G. A
pair of functions u : P → R and v : Q → R is called a payoff. An outcome of
the game is a triple (u, v; M ) consisting of a payoff and a matching. Such an
outcome (u, v; M ) is called feasible if

(i) ui ≥ 0 and vj ≥ 0 for all (i, j) ∈ P × Q and ui = 0 (resp. vj = 0) if i

(resp. j) is unmatched.

(ii) ui + vj = aij + bij for (i, j) ∈ M and {i, j} ⊆ F .

(iii) ui = aij and vj = bij for (i, j) ∈ M and {i, j} ∩ R 6= ∅.

Accordingly, we call an edge (i, j) flexible if {i, j} ⊆ F , rigid otherwise, and

denote by F ∗ resp. R∗ the set of flexible resp. rigid edges.
Now, we can define our notion of stability:

Definition 2.1. A payoff (u, v) is called stable if for all (i, j) ∈ P × Q we

have that

(i) ui + vj ≥ aij + bij if (i, j) ∈ F ∗ and

(ii) ui ≥ aij or vj ≥ bij if (i, j) ∈ R∗ .

An outcome (u, v; M ) is called stable if it is feasible and (u, v) is a stable payoff.

Note that this notion of stability coincides with Eriksson and Karlander [5]
and [23] only for outcomes. A pair (i, j) ∈ P × Q that violates one of (i) and (ii)
of Definition 2.1 is called a blocking pair. For any blocking pair (i, j) we define

if (i, j) ∈ F ∗

aij + bij − vj
uji :=
aij if (i, j) ∈ R∗ .

A blocking partner j that maximizes uji is called i’s favorite blocking partner.

3
3 Special Cases
If one of F or R is empty the model from the last section reduces to the well-
known stable marriage resp. assignment game. In this section we will discuss
these models and recall an algorithm for each of them that we will merge into
a single algorithm for the mixed model in Section 4.

3.1 Stable Marriage

If F = ∅ the numbers aij (for the firms) and the numbers bij (for the workers)
induce a preference list for each firm resp. worker. A matching M is stable if no
non-matching edge (i, j) 6∈ M has the property that i prefers j to its matching
partner as well as j prefers i to its matching partner, i. e. ui < aij and vi < bij .
The famous algorithm to find a stable matching is due to Gale and Shapley [11].
We need a slightly modified version (see Algorithm 1) which differs from the
original “men propose – women dispose” algorithm in a way that proposals are
not made in rounds but asynchronously.

Algorithm 1 Asynchronous “men propose – women dispose”

while ∃ an unmatched firm i do
i asks favorite j to join
if j prefers i over its current partner i0 then
j deletes i0 from preference list
Unmatch(j)
Match(i,j)
else
i deletes j from preference list
end if
end while

3.2 Assignment Game

If R = ∅ the problem reduces to the assignment game or weighted bipartite
matching and its dual linear program. The payoffs are the dual variables (i. e. a
weighted vertex cover), the stability condition reduces to their feasibility, and
a maximum matching together with a minimum weighted vertex cover yield a
stable outcome by linear programming duality.
A famous algorithm to find a maximum weighted matching and a minimum
weighted vertex cover in O(n3 ) is Kuhn’s Hungarian Method (see Algorithm 2
or e. g. Frank [8] for a transparent presentation). It starts with a weighted
vertex cover (resp. a dually feasible i. e. stable payoff). For a given bipartite
graph G = (P ∪Q,˙ E), a matching M , and a payoff (u, v) the digraph of tight
edges G(u,v;M ) is defined as the bipartite digraph with all vertices of G, forward
edges (i, j) 6∈ M that satisfy ui + vj = aij + bij , and backward edges (j, i)
for (i, j) ∈ M . An augmenting path in G(u,v;M ) is a directed path that starts

4
Algorithm 2 Modified Hungarian Method
1: procedure WeightedBipartiteMatching
2: for all i ∈ P do
3: ui ← max({aij + bij | j ∈ Q})
4: end for
5: while (u, v; M ) is not stable do
6: if ∃ augmenting path P in G(u,v;M ) then
7: alternate(P)
8: else
9: i ← unmatched firm
10: HungarianUpdate(i)
11: end if
12: end while
13: end procedure

14: procedure HungarianUpdate(i)

15: P̄ ∪˙ Q̄ ←BFS(G(u,v;M ) ,i)
16: ∆ ← min{ui + vj − aij − bij | i ∈ P̄ , j 6∈ Q̄} > 0
17: for all i ∈ P̄ do
18: ui ← ui − ∆
19: end for
20: for all j ∈ Q̄ do
21: vj ← vj + ∆
22: end for
23: end procedure

with an unmatched firm and ends with an unmatched worker. Alternate(P)

interchanges matching and non-matching edges on the alternating path P. For
a vertex k ∈ P × Q the function BFS(k) returns all vertices P̄ ∪˙ Q̄ from P ∪ Q
that are connected to k by a directed path in the digraph of tight edges.

4 An Algorithm to Find a Stable Outcome

P
Sotomayor [23] has shown that an outcome maximizing j∈Q vj under cer-
tain constraints exists and yields a stable outcome. In her proof she derives a
contradiction by constructing an augmentation under the assumption that the
outcome is not stable. Using this augmentation step and ideas from matching
theory such as the update of the dual variables in the Hungarian Method we
derive an algorithm that finds a stable outcome.
By eventually introducing dummy firms or workers we may assume that
|P | = |Q| =: n. Such a dummy k satisfies akj = 0 for all workers resp. bik = 0
for all firms.
For a given outcome (u, v; M ) we define an augmentation digraph G(u,v;M )

5
as a directed subgraph of G with edge set
E(u,v;M ) := {(j, i) | (i, j) ∈ M } ∪ {(i, j) | j ∈ Di (u, v; M )},
where
Di (u,v; M ) := {i’s favorite blocking partners}
∪ {j ∈ Q | (i, j) ∈ F ∗ \ M and ui + vj = aij + bij }
∪ {j ∈ Q | (i, j) ∈ R∗ \ M and ui = aij and vj < bij }.
The following path augmentation argument is a slight modification of So-
tomayor [23, Lemma 1].
Lemma 4.1. Let (u, v; M ) be a feasible outcome such that no matched firm is
contained in a blocking pair. If there is an unmatched firm i1 with a blocking
partner then there exists a feasible outcome (ũ, ṽ; M ) and an oriented path P in
G(ũ,ṽ;M ) starting from i1 that reaches a player of R, an unmatched worker or a
firm with payoff zero.
Proof. Let P̄ ⊆ P and Q̄ ⊆ Q be the firms and workers reachable from i1
in G(u,v;M ) (let i1 be included in P̄ ). If i1 ∈ R we can set P = {i1 } and
(ũ, ṽ; M ) = (u, v; M ). Now let i1 ∈ F and assume there is no such path. Then
(P̄ ∪ Q̄) ∩ R = ∅, VM ∩ Q̄ = Q̄ and ui > 0 ∀i ∈ P̄ \ {i1 }. If i ∈ P̄ \ {i1 } then i
is matched and by assumption is not contained in any blocking pair, i. e. for all
j ∈ Q ui ≥ aij + bij − vj and if j ∈ R then either ui ≥ aij or vj ≥ bij . For each
edge (i, j) ∈ (P̄ \ {i1 }) × (Q \ Q̄) it, thus, follows from the definition of G(u,v;M )
that ui > aij + bij − vj and if j ∈ R and vj < bij then ui > aij . Now let

F̃ := (P̄ × (Q \ Q̄)) ∩ F ∗ and

R̃ := {(i, j) ∈ P̄ × ((Q \ Q̄) ∩ R) | ui > aij and vj < bij }.
We modify the outcome such that it remains feasible until we either get a new
edge in G(u,v;M ) or a firm with payoff zero, i. e. let
∆ := max{δ |ui − δ ≥ 0 ∀i ∈ P̄ \ {i1 } (1)
ui − δ ≥ aij ∀(i, j) ∈ R̃ (2)
ui − δ ≥ aij + bij − vj ∀(i, j) ∈ F̃ }. (3)
By the above then ∆ > 0. We construct a new outcome (ũ, ṽ; M ) by decreasing
ui and increasing vj by ∆ for all (i, j) ∈ (P̄ \ {i1 }) × Q̄. By construction, this
outcome is still feasible. ∆ has been chosen such that equality holds in one
of (1-3) for at least one edge (i, j). If (1) holds with equality then there is a
firm with payoff zero in P̄ and if (2) holds with equality we reach a worker in
R. Otherwise, we reach another flexible worker from Q \ Q̄ and enlarge Q̄. If
the assumption of the lemma is still satisfied, i.e. there is still no such path,
we iterate the process. The latter can happen at most |Q| times. Thus the
process is finite and eventually ends with a path since there must be at least
one unmatched worker as |P | = |Q|.

6
 The modification of the payoffs in the above proof is similar to the update
of the dual variables in HungarianUpdate. A major difference is that the
Hungarian Method always ensures dually feasible variables, namely ui + vj ≥
aij + bij ∀(i, j) ∈ P × Q. In our terms this corresponds to a stable payoff.
We adapt this idea and introduce virtual payoffs denoted by ūi for all firms
such that no edge (i, j) ever forms a blocking pair in the (infeasible) outcome
(ū, v; M ) during the algorithm. Thus ui is the allocation that we can afford
from the current matching and ūi is an upper bound on the highest possible
benefit of firm i from the current market situation. Our approach thus becomes
similar to complementarity algorithms known from combinatorial optimization:
We have a (primal) feasible matching M and a stable (dual feasible) payoff
(ū, v). Optimality is reached when ūi > 0 implies that i is matched for all i.
The algorithm then can be outlined as follows: We start with an empty
matching, payoff zero for all workers, and the maximum possible individual vir-
tual payoff for each firm. Throughout the algorithm we ensure that no firm
that has a matching partner belongs to a blocking pair. As long as there are
blocking pairs, we consider the connected component of the corresponding un-
matched firm i formed by Di and construct a path as in Lemma 4.1. For that
purpose we, eventually, modify the outcomes. Once such a path is found we
either increment the matching, check off a firm, or check off an edge from R∗ .
We first adjust HungarianUpdate choosing ∆ as in (1-3). Furthermore we
modify ū for all vertices in P̄ and u for all vertices in P̄ \ {i1 } (see Algorithm 3).

Algorithm 3 Modified Hungarian Method

1: procedure HungarianUpdate(i)
2: P̄ ∪˙ Q̄ ←BFS(G(u,v;M ) ,i)
∆ ← max{δ | ui − δ ≥ 0 ∀i ∈ P̄ \ {i1 }
3: ui − δ ≥ aij ∀(i, j) ∈ R̃
ui − δ ≥ aij + bij − vj ∀(i, j) ∈ F̃ }.
4: for all i ∈ P̄ \ {i1 } do
5: ui ← ui − ∆
6: ūi ← ūi − ∆
7: end for
8: ūi1 ← ūi1 − ∆
9: for all j ∈ Q̄ do
10: vj ← vj + ∆
11: end for
12: end procedure

The main procedure (see Algorithm 4) starts with a feasible outcome

(u, v; M ) ← (0, 0; ∅) and a stable payoff (ū, v):

ūi ← max ({aij + bij | (i, j) ∈ F ∗ } ∪ {aij | (i, j) ∈ R∗ }) i ∈ P.

In the next section we will discuss how we implement the update of the

7
Algorithm 4 Construction of a Stable Outcome
1: (u, v; M ) ← (0, 0; ∅)
2: for all i ∈ P do
3: ūi ← max ({aij + bij | (i, j) ∈ F ∗ } ∪ {aij | (i, j) ∈ R∗ })
4: end for
5: while blocking pair (i1 , j) exists do
6: while there is no path P as in Lemma 4.1 do
7: HungarianUpdate(i1 )
8: end while
9: PathUpdate(P)
10: end while

outcome according to P.

4.1 The Augmentation Step

The details of the path update procedure are worked out in Algorithm 5 where
we make use of the following sub-procedures.

Alternate gets an alternating path (resp. an alternating cycle in CASE 3.3)

P = (i1 , j1 , i2 , j2 , . . .) as argument, i. e. every second edge is a matching
edge. Matching and non-matching edges are exchanged along the path
(resp. cycle) such that former matching edges become non-matching edges
and vice versa. Hence, the number of matching edges does not change in
case P starts in an unmatched firm and ends in a firm or if P is a cycle and
increases by 1 if it starts in an unmatched firm and ends in an unmatched
worker. Other cases will not occur. If P = (i1 , j1 , i2 , j2 , . . .) is the path
as in Lemma 4.1 then P[i1 ,js−1 ] denotes the subpath from i1 to js−1 and
if ik ∈ R is matched to jk = js with 1 ≤ k < s then P[jk ,js ] denotes
the alternating cycle composed of the subpath of P from jk to is and the
matching edge (jk , ik ).

Update(i, j) sets ūi ← ui ← aij + bij − vj in case (i, j) ∈ F ∗ and ūi ← ui ←

aij , vj ← bij if (i, j) ∈ R∗ .
Unmatch(j) : if there is an edge (i, j) ∈ M, remove it from M and set ui ← 0.

CheckOff(i) sets ūi ← ui ← 0. Such a firm will never ever form a blocking
pair.

8
Algorithm 5 Augmentation along the path P
procedure PathUpdate(P)
F
z }| {
if P = (i1 , j1 , . . . , is , js ) and js unmatched then . CASE 1
Alternate(P)
Update(i1 , j1 )
Update(is , js )
F
z }| {
else if P = (i1 , j1 , . . . , is−1 , js−1 , is ), uis = 0 then . CASE 2
Alternate(P)
Update(i1 , j1 )
CheckOff(is )

else
if P = (. . . , is ) and Dis (u, v; M ) 6= ∅ then
P ← Pjs for some js ∈ Dis (u, v; M )
end if
R∗
if P = (i1 , j1 ) then . CASE 3.1
Unmatch(j1 )
Alternate((i1 , j1 ))
Update(i1 , j1 )
F
z }| { R∗
else if P = (i1 , j1 , . . . , is−1 , js−1 , is , js ) then . CASE 3.2
Unmatch(js )
Alternate(P)
Update(i1 , j1 )
Update(is , js )
F
z }| { R F
else if P = (i1 , j1 , . . . , ik , jk = js , . . ., is , js ) then . CASE 3.3
Alternate(P[jk ,js ] )
Update(is , js )
F
z }| { R
else if P = (i1 , j1 , . . ., is ) and Dis (u, v; M ) = ∅ then . CASE 3.4
Unmatch(js−1 )
Alternate(P[i1 ,js−1 ] )
Update(i1 , j1 )
if is has blocking partner then . CASE 3.4a
js ← favorite blocking partner of is
PathUpdate((is , js ))
else . CASE 3.4b
CheckOff(is )
end if
end if
end if
end procedure
9
4.2 Correctness and Complexity
We are now going to prove that Algorithm 4 is correct and show at first that
Algorithm 5 covers all cases. If P is a path that lies completely in F, then, by
construction, P either ends in an unmatched worker (CASE 1) or a firm with
payoff zero (CASE 2). Now let the end vertex k of P be in R. If k ∈ Q then
CASE 3.1 or CASE 3.2 applies. Now let is ∈ P ∩ R be the end vertex of P.
If Dis (u, v; M ) = ∅ then CASE 3.4 applies. Otherwise, PathUpdate chooses
some js ∈ Dis (u, v; M ). If js is already contained in P we add js to the end
of P and are in CASE 3.3. Otherwise, we add js to the end of P and are in
CASE 3.1 or 3.2. The correctness of the main procedure now directly follows
from some invariants of the algorithm.

Lemma 4.2. After each call of HungarianUpdate or PathUpdate the fol-

lowing holds:

a) (u, v; M ) is feasible.

b) (i, j) blocks (u, v; M ) ⇒ i is unmatched.

c) ui = ūi ⇐⇒ i is matched or ui = ūi = 0.

d) (ū, v) is stable.

e) For all i ∈ P ūi did not increase.

f ) For all j ∈ Q vj did not decrease .

g) |M | did not decrease.

h) Once a firm has been checked off it will never be matched again.

Proof. In the first step of the algorithm all conditions hold as we start with a
sufficiently large virtual payoff ū and an outcome (0, 0; ∅). Now assume condi-
tions a) to h) are true for the current step of the algorithm. We show that this
is still true after the next call of the procedures considered.

f) We start with v = 0 and v is altered only in HungarianUpdate, when

the matching is augmented (CASE 1), or when an edge in R∗ is matched
(CASES 3.1, 3.2 and 3.3). HungarianUpdate only increases some vj and
an unmatched worker had a payoff of zero before. An edge in (i, j) ∈ R∗
can be matched only if either (i, j) forms a blocking pair or ui = aij and
vj < bij . In both cases vj < bij holds and Update(i, j) increases vj .

g) The matching is altered in PathUpdate only. In CASE 1 it is increased

and in CASE 3.1 the matching increases when j1 is not matched. In
all other cases we either alternate on an even path or an even cycle or
unmatch a vertex and immediately augment the matching again. Thus in
all cases other the size of the matching is not changed.

10
 h) A firm i is checked off in CASE 2, if it was matched, and thus had no
blocking partner by b), with ui = ūi = 0 and has become unmatched. Or
it has become unmatched, enforcing ui = 0 and has no blocking partner in
CASE 3.4. In that case we can set ūi = 0 and remain dually feasible. By
f) and as aij and bij are non-negative i will never have a blocking partner
again. After the algorithm has terminated we may match such a firm to
some unmatched vj , necessarily satisfying aij = 0.

c) When an unmatched firm is matched, it is matched to its favorite blocking

partner, updated and ui = ūi holds. When a firm becomes unmatched its
payoff is set to zero.

d),e) We consider situations where an outcome is updated. In HungarianUp-

date the definition of ∆ ensures that d) is not violated. Furthermore,
ūi only decreases for some firms. In PathUpdate ū is altered when
Update(i, j) or CheckOff(is ) is called. The latter case has been dis-
cussed before and does not cause blocking pairs. When Update(i, j) is
invoked, then (i, j) ∈ Di (u, v; M ), in particular (i, j) 6∈ M and we have
the following cases:

i was already matched (CASES 1, 3.2, 3.3, 3.4) and

(i, j) ∈ F ∗ ⇒Update(i, j) has no effect as vj has not been changed
(i, j) ∈ R∗ ⇒ by definition of Di ūi = ui does not change while vj
increases
j is i’s favorite blocking partner (CASES 1, 2, 3.1, 3.2, 3.4) and
(i, j) ∈ F ∗ ⇒ ūi ← max{aij + bij − vj | (i, j) forms a blocking pair}
(i, j) ∈ R∗ ⇒ ūi ← max{aij | (i, j) forms a blocking pair}

Hence, d) holds as in any case ūi + vj ≥ aij + bij holds for all edges in F ∗
and ūi ≥ aij for all edges in R∗ . As ūi changes at most if i was unmatched,
e) follows from the fact that ūi was dually feasible before the procedure
call and is now changed to the minimal value guaranteeing dual feasibility.

Finally we discuss a) and b):

HungarianUpdate: The procedure modifies outcomes only in P̄ ∪ Q̄. Note

that any firm in P̄ \ {i1 } is matched and therefore ui = ūi ∀i ∈ P̄ \ {i1 }.
Since for a matching edge (i, j) ∈ M ui and vj are modified in opposite
direction the edge (i, j) remains tight. Furthermore, u is decreased at
most only until the first i satisfies ui = 0, thus (u, v; M ) remains feasible.
In P̄ ∪ Q̄ ui + vj is not altered for any edge and thus we do not have
any blocking pair. By partially increasing v workers in Q̄ become less
attractive for firms outside P̄ . It follows that no new blocking pairs occur
and b) holds.

CASES 1 and 2 : All edges along P are tight except for the first edge which is
made tight by Update. Hence, all newly matched edges are tight. Before

11
 (i, j) is updated we have

0 = ui1 < ai1 j1 + bi1 j1 − vj1 ≤ ūi1

and therefore ui1 > 0 after the update and the outcome is feasible. There
are no new blocking pairs since v is not changed, i1 is matched to its
favorite blocking partner and there is no other newly matched firm. In
CASE 2 a firm is checked off but actually this step does nothing as has
been discussed before.
CASE 3.1: The feasibility is obvious and there are no newly matched firms
instead of i1 which is matched to its favorite blocking partner.

CASE 3.2: Again, the new outcome is still feasible. i1 has no blocking partner
after it is matched to its favorite. Since (is , js ) ∈ R∗ we have uis = ais js
and vjs < bis js . Hence, an update does not change the outcome of is and
makes js less attractive to other firms.

CASE 3.3: Only the outcome of js is modified in a direction that makes js

less attractive. No new blocking pairs are formed and feasibility is not
violated.

CASE 3.4: If is does not have any new blocking partner then vj ≥ ais j + bis j
for all j ∈ Q and we can set ūis ← 0 without violating d). Therefore a)
and b) are obviously still true. Otherwise, is is matched to its favorite
blocking partner.

In each of the CASES 3.1 – 3.4a an edge from R∗ is made tight. By

Lemma 4.2 and definition of Di such an edge will never appear as non-matching
edge in any search tree again. Therefore, we may say it is checked off. Cor-
rectness and a complexity result now follow from the immediate observation
that:

Proposition 4.3. After every call of PathUpdate one of the following state-
ments holds:

1. |M | has been increased.

2. A firm has been checked off.

3. An edge from R∗ has been checked off.

Proof. We summarize the progress made by PathUpdate in Table 1. Here, •

(resp. ◦ or –) in row p and column c mean that property p of Proposition 4.3
holds definitely (resp. probably or definitely not) after CASE c was applied:

12
 CASE: 1 2 3.1 3.2 3.3 3.4a 3.4b
|M | increases • – ◦ ◦ – ◦ –
firm checked off – • – – – – •
rigid edge checked off – – • • • • –

Table 1: Progress made by PathUpdate

Any column in Table 1 contains a bullet, hence at least one statement holds.

Theorem 4.4. Algorithm 4 computes a stable outcome and can be implemented

to run in O(n4 ).

Proof. From Lemma 4.1 we conclude that as long as there is some blocking pair
there also must be a path P in line 9 of Algorithm 4. The matching can be
augmented at most |Q| times, there are only |P | firms to check off, and at most
|P | · |Q| edges to be checked off in R∗ . The correctness thus follows from Lemma
4.2 and Proposition 4.3.
There is not much work left to derive an implementation that runs in O(n4 ).
By Proposition 4.3 all that is left to show is that we can implement the while-
loop in line 6 of Algorithm 4 to be passed in O(n2 ). For that purpose we use a
standard implementation of the Hungarian Method see e. g. Galil [12].
For any fixed j ∈ Q we store a value ∆j corresponding to ∆ in (1)-(3) being
the gap between j and P̄ ∪ Q̄, i. e.

∆j := max{δ |ui − δ ≥ 0 ∀i ∈ P̄ \ {i1 } (4)

ui − δ ≥ aij ∀(i, j) ∈ R̃ (5)
ui − δ ≥ aij + bij − vj ∀(i, j) ∈ F̃ }. (6)

∆j must be updated for each j in O(n) whenever we add a vertex to P̄ ∪ Q̄

(which happens O(n) times). Computing ∆ = min{∆j > 0} is easily done
in O(n). After an update of the payoffs we can set ∆j := ∆j − ∆. Now,
HungarianUpdate can be implemented to simply continue the breadth-first
search of its previous call with modified payoffs. Hence, the accumulated time
spent in one iteration of the outer while-loop of Algorithm 4 for updating the
payoffs is O(n2 ). Adding the time needed for a breadth-first search (also O(n2 ))
yields the upper bound of O(n2 ). After we leave the inner while-loop we reach
an unmatched worker, a player in R, or a firm with payoff zero which can happen
at most O(n2 ) times. The overall complexity of O(n4 ) follows.

The complexity argument in the proof of Theorem 4.4 is straight-forward.

Further investigations might lead to slight improvements, though. Similar to
the Hungarian Method one could keep the set P̄ ∪ Q̄ of vertices reachable from
unmatched firms in a tree-structure until the matching is augmented. This tree
changes when a rigid edge is matched. Then the “hungarian” tree rooted by an

13
unmatched firm becomes a tree which is rooted by a matched player. We had
no idea of a data structure that could help to efficiently recycle the data.
The advantage of the implementation discussed in the proof of Theorem 4.4
is that in any stage of the hungarian update one keeps track of the “distance” of
unmatched and rigid players from the current component P̄ ∪ Q̄. Those values
can be updated in linear time when the payoffs in P̄ ∪ Q̄ are altered by ∆. In the
situation described in the above paragraph it seems to be difficult to update this
data in linear time. Such a linear time update would lead to an O(n3 )-algorithm
having the same complexity as the Hungarian Method.

Remark 1. As we mentioned above, Sotomayor [23, Lemma 1] picked a special

outcome (i. e. with maximized worker profit) and proved it to be stable. Although
we extracted the major techniques of our algorithm
P from that lemma, we point
out that we do not necessarily maximize j∈Q vj among all stable outcomes
(u, v; M ) as the following example demonstrates:

Example 1. Let P = {1, 2}, Q = {3, 4}, F = {1, 3, 4}, R = {2}, and
       
a13 a14 10 5 b13 b14 0 0
:= and := .
a23 a24 6 2 b23 b24 6 2

For this example Algorithm 4 gives the stable outcome (u, v; M ) with

u1 = 5, u2 = 6, v3 = 6, v4 = 0, and M = {(1, 4), (2, 3)}

while a stable outcome with maximum worker profit is

u1 = 3, u2 = 2, v3 = 7, v4 = 2, and M = {(1, 4), (2, 3)}.

5 Comparison With Existing Algorithms

5.1 The Algorithm in [14] for the Same Model
In [14] a polynomial time algorithm is derived from an auction algorithm of
Eriksson and Karlander [5] which, in their implementation, is pseudopolynomial.
This algorithm differs from the algorithm presented here in various ways. In
[14] (especially rigid) proposals are made in rounds and not asynchronously
as in the present implementation. When restricted to instances of the Stable
Marriage or Assignment Model our implementation coincides with standard
implementations of existing algorithms (see the efficient implementation of “men
propose – women dispose” discussed in [13, Section 1.2.3] and the Hungarian
Method as introduced in Kuhn [17, Variant 2]) while the algorithm presented
in [14] is a direct extension of the original “men propose – women dispose”
algorithm of Gale and Shapley [11]. Also the concepts of augmenting paths
differ here as we augment the cardinality of a matching while in [14] the image
of a map is augmented until it becomes bijective.

14
5.2 The Algorithm of Fujishige and Tamura [9] for a More
General Model
Fujishige and Tamura [9] introduce a more general market model that contains
the models of [11, 22, 5, 7, 4, 10] as special cases and constructively prove
the existence of a pairwise stable outcome by presenting an algorithm that is
pseudopolynomial with respect to the volume of the domain of an M \ -concave
function. This algorithm becomes polynomial if restricted to instances of the
model of Eriksson and Karlander [5] and furthermore, in some aspects reminds
of the algorithm in [14]. It also consists of two main stages where the first
stage ensures that any firm gets at most one rigid proposal ([9, Case 1]) and
the second stage either finds an augmenting path or adjusts payoffs until such a
path exists ([9, Case 2]). However, the concepts of augmenting paths differ and
the augmentation graph used in [9] is different since vertices are identified with
edges of the original graph. Since the augmentation graph is sparse, a careful
analysis of the algorithm in [9] yields a complexity of O(n2 (n2 + g(n2 , n2 , C) +
h(n2 , n2 , C))), where g(n, m, C) is the complexity of a procedure that computes
the shortest distances from a fixed set of sources S to all other vertices, and
h(n, m, C) is the complexity to compute one shortest path from S to T using
a minimum number of arcs, both in a digraph with n vertices, m arcs, and
positive arc weights bounded by C = max(i,j)∈P ×Q {aij + bij }.
For further details of the algorithm which go beyond the scope of this paper
we refer the reader to Fujishige and Tamura [9] and Moriguchi and Murota [18].

References
[1] Gabrielle Demange, David Gale, and Marilda Sotomayor. Multi-item auc-
tions. Journal of Political Economy, 94(4):863–872, 1986.
[2] Xiaotie Deng, Toshihide Ibaraki, and Hiroshi Nagamochi. Combinatorial
optimization games. In Proceedings of the 8th Annual ACM-SIAM Sympo-
sium on Discrete Algorithms, pages 720–729, New Orleans, LA, 1997.

[3] Xiaotie Deng and Christos H. Papadimitriou. On the complexity of coopar-

ative game solution concepts. Mathematics of Operations Research, 19:257–
266, 1994.

[4] Akinobu Eguchi, Satoru Fujishige, and Akihisa Tamura. A generalized

Gale-Shapley algorithm for a discrete-concave stable-marriage model. In
Algorithms and computation, volume 2906 of Lecture Notes in Computer
Science, pages 495–504. Springer, Berlin, 2003.

[5] Kimmo Eriksson and Johan Karlander. Stable matching in a common gen-
eralization of the marriage and assignment models. Discrete Mathematics,
217(1-3):135–156, 2000.

15
 [6] Ulrich Faigle, Sandor P. Fekete, Winfried Hochstättler, and Walter Kern.
On the complexity of testing membership in the core of min cost spanning
tree games. International Journal of Game Theory, 26:361–366, 1997.

[7] Tamás Fleiner. A matroid generalization of the stable matching polytope.

In Integer programming and combinatorial optimization (Utrecht,2001),
volume 2081 of Lecture Notes in Computer Science, pages 105–114.
Springer, Berlin, 2001.

[8] András Frank. On Kuhn’s Hungarian method – A tribute from Hungary.

Technical report, Egerváry Research Group on Combinatorial Optimiza-
tion, October 2004.

[9] Satoru Fujishige and Akihisa Tamura. A two-sided discrete-concave market

with bounded side payments: An approach by discrete convex analysis.
RIMS Preprint No. 1470, Kyoto University, August 2004.

[10] Satoru Fujishige and Akihisa Tamura. A general two-sided matching mar-
ket with discrete concave utility functions. Discrete Applied Mathematics,
154(6):950–970, 2006.

[11] David Gale and Lloyd S. Shapley. College admissions and the stability of
marriage. American Mathematical Monthly, 69:9–15, 1962.

[12] Zvi Galil. Efficient algorithms for finding maximum matchings in graphs.
ACM Computing Surveys, 18(1):23–38, 1986.

[13] Dan Gusfield and Robert W. Irving. The stable marriage problem: Struc-
ture and algorithms. MIT Press, Cambridge, MA, USA, 1989.

[14] Winfried Hochstättler, Hui Jin, and Robert Nickel. Note on an auction
procedure for matching games in polynomial time. In AAIM Proceedings,
pages 387–394, 2006.

[15] Donald E. Knuth. Stable marriage and its relation to other combinatorial
problems. In CRM Proceedings and Lecture Notes, volume 10. American
Mathematical Society, 1997.

[16] Harold W. Kuhn. The Hungarian method for the assignment problem.
Naval Research Logistics Quaterly, 2:83–97, 1955.

[17] Harold W. Kuhn. Variants of the Hungarian method for the assignment
problem. Naval Research Logistics Quaterly, 3:253–258, 1956.

[18] Satoko Moriguchi and Kazuo Murota. Capacity scaling algorithm for scal-
able M -convex submodular flow problems. Optimization Methods and Soft-
ware, 18(2):207–218, 2003. The Second Japanese-Sino Optimization Meet-
ing, Part I (Kyoto, 2002).

16
[19] Kazuo Murota. Discrete convex analysis. SIAM Monographs on Discrete
Mathematics and Applications. Society for Industrial and Applied Mathe-
matics (SIAM), Philadelphia, PA, 2003.

[20] Alvin E. Roth and Marilda Sotomayor. Stable outcomes in discrete and
continuous models of two-sided matching: A unified treatment. Revista
de Econometria, The Brazilian Review of Econometrics, 16(2), November
1996.

[21] Alwin E. Roth and Marilda Sotomayor. Two-sided matching: A study in

game-theoretic modeling and analysis. Cambridge University Press, Cam-
bridge, 1991.

[22] Lloyd S. Shapley and Martin Shubik. The assignment game I: The core.
International Journal of Game Theory, 1:111–130, 1972.

[23] Marilda Sotomayor. Existence of stable outcomes and the lattice property
for a unified matching market. Mathematical Social Sciences, 39:119–132,
2000.

17