Plaintext
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33
www.theoryofcomputing.org
S PECIAL ISSUE : APPROX-RANDOM 2019
Max-Min Greedy Matching
Alon Eden* Uriel Feige† Michal Feldman‡
Received March 2, 2020; Revised February 17, 2021; Published April 13, 2022
Abstract. A bipartite graph G(U,V ; E) that admits a perfect matching is given. One player
imposes a linear order π over V , the other player imposes a linear order σ over U. In the
greedy matching algorithm, vertices of U arrive in order σ and each vertex is matched to
the highest (under π) yet unmatched neighbor in V (or is left unmatched, if all its neighbors
are already matched). The matching obtained is maximal, thus matches at least half of the
vertices. The max-min greedy matching problem asks: Suppose the first (max) player reveals
π, and the second (min) player responds with the worst possible σ for π. Does there exist a
linear order π ensuring to match strictly more than half of the vertices? Can such a linear
order be computed in polynomial time?
The main result of this paper is an affirmative answer for these questions: we show that
there exists a polynomial-time algorithm to compute π for which for every σ at least ρ > 0.51
fraction of the vertices of V are matched. We provide additional lower and upper bounds for
A conference version of this paper appeared in the Proceedings of the 22nd International Conference on Approximation
Algorithms for Combinatorial Optimization Problems, 2019 (APPROX’19) [6].
* Partially supported by the European Research Council under the European Union’s Seventh Framework Programme
(FP7/2007-2013) / ERC grant agreement number 337122, the Israel Science Foundation (grant number 317/17), and the
Blavatnik family foundation.
† Partially supported by the Israel Science Foundation (grant No. 1388/16).
‡ Partially supported by the European Research Council under the European Union’s Seventh Framework Programme
(FP7/2007-2013) / ERC grant agreement number 337122, the Israel Science Foundation (grant number 317/17), and the
Blavatnik family foundation.
ACM Classification: G.2.2
AMS Classification: 68W25,68R10,91B26,05C70
Key words and phrases: Online matching, pricing mechanism, markets
© 2022 Alon Eden, Uriel Feige, and Michal Feldman
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018a006
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
special families of graphs, including regular and Hamiltonian graphs. Our solution solves an
open problem regarding the welfare guarantees attainable by pricing in sequential markets
with binary unit-demand valuations.
1 Introduction
Given a bipartite graph G(U,V ; E), where U and V are the sets of vertices and E ⊂ U ×V is the set of
edges, a matching M ⊂ E is a set of edges such that every vertex is incident with at most one edge of
M. For simplicity of notation, for every n we shall only consider the following class of bipartite graphs,
that we shall refer to as Gn . For every G(U,V ; E) ∈ Gn it holds that |U| = |V | = n and that E contains
a matching of size n (and hence G has a perfect matching). All results that we will state for Gn hold
without change for all bipartite graphs that have a matching of size n (and arbitrarily many vertices).
Karp, Vazirani and Vazirani [13] introduced the online bipartite matching problem. In this problem,
a bipartite graph G(U,V ; E) is revealed in an online manner, where side V is known in advance, and
vertices in U are revealed one after another, along with their edges to V . When a vertex u ∈ U is revealed
together with its set of neighbors N(u) ⊂ V , the algorithm must decide, immediately and irrevocably,
which of the yet unmatched vertices in N(u) to match to u (if any). The goal of the algorithm is to
maximize the size of the matching achieved.
This setting can be viewed as a game between two players: a maximizing player who wishes the
resulting matching to be as large as possible, and a minimizing player who wishes the matching to be as
small as possible. First, the minimizing player chooses G(U,V ; E) in private (without the maximizing
player seeing E), subject to G ∈ Gn . Thereafter, the structure of G is revealed to the maximizing player in
n steps, where at step j (for 1 ≤ j ≤ n) the set N(u j ) ⊂ V of vertices adjacent to u j is revealed. At every
step j, upon seeing N(u j ) (and based on all edges previously seen and all previous matching decisions
made), the maximizing player needs to irrevocably either match u j to a currently unmatched vertex in
N(u j ), or leave u j unmatched.
There has been much recent interest in the online bipartite matching problem and variations and
generalizations of it, as such models have applications to allocation problems in certain economic settings,
in which buyers (vertices of U) arrive online and are interested in purchasing various items (vertices of
V ). A prominent example of such an application is online advertising; for more details, see for example
the survey by Mehta [17]. The new problems are both theoretically elegant and practically relevant.
Max-min greedy matching We study a setting related to online bipartite matching, that we call max-
min greedy matching. Our setting is also a game between a maximizing player and a minimizing player.
The bipartite graph G(U,V ; E) ∈ Gn is given upfront. Upon seeing G the maximizing player chooses a
linear order π over V . Upon seeing G and π, the minimizing player chooses a linear order σ over U. The
combination of G, π and σ defines a unique matching MG [σ , π] that we refer to as the greedy matching.
It is the matching produced by the greedy matching algorithm in which vertices of U arrive in order σ
and each vertex u ∈ U is matched to the highest (under π) yet unmatched v ∈ N(u) (or left unmatched, if
all of N(u) has already been matched).
The matching MG [σ , π] has several additional equivalent definitions. For example, MG [σ , π] is the
matching produced by the greedy matching algorithm in which vertices of V arrive in order π and each
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 2
M AX -M IN G REEDY M ATCHING
vertex v ∈ V is matched to the highest (earliest in arrival order under σ ) yet unmatched u ∈ N(v) (or left
unmatched, if all of N(v) has already been matched). Also, MG [σ , π] is the unique stable matching in G
(in the sense of [10]), if the preference order of every vertex u ∈ U over its neighbors is consistent with π,
and the preference order of every vertex v ∈ V over its neighbors is consistent with σ . More details are
given in Section 8.
Let
1
ρ[G] = max min[|MG [σ , π]|],
n π σ
and let
ρ = min [ρ[G]].
G∈Gn
It is easy to see that ρ ≥ 1/2. In fact, to ensure a matching of size n/2, the max player need not work
hard. Since every greedy matching is a maximal matching, for every linear order π the obtained matching
is of size at least n/2. The question we study here is whether the max player can ensure a matching of
size strictly greater than n/2; that is, whether ρ is bounded away from 1/2.
For an upper bound on ρ, it was observed by Cohen-Addad et al. [4] that ρ ≤ 2/3. To show this,
they observe that in the 6-cycle graph, depicted in Figure 1, no linear order π can guarantee to match
more than two vertices in the worst case. Indeed, suppose (without loss of generality) that π = (v3 , v2 , v1 ).
For σ = (u1 , u3 , u2 ), u1 is matched to v2 , u3 is matched to v3 , and u2 is left unmatched, resulting in a
matching of size 2.
𝜎(2) 𝑢3 𝑣3
𝜎(3) 𝑢2 𝑣2 𝜋
𝜎(1) 𝑢1 𝑣1
𝐺
Figure 1: For every linear order π there exists a linear order σ that matches only 2 of the 3 vertices. Thick
edges are in the matching; gray vertices are unmatched.
1.1 Our results
Our main result resolves the open problem in the affirmative.
Main result [Theorem 2.1]: For all graphs, ρ ≥ 1/2 + 1/86 > 0.51. Moreover, there is a polynomial-
time algorithm that given G(U,V ; E) produces a linear order π over V satisfying the above bound.
The significance of this result is that 1/2 is not the optimal answer. We believe that further improve-
ments are possible. In fact, for Hamiltonian graphs we show that ρ ≥ 5/9 (see Section 6).
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 3
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
The proof method is quite involved; it is natural to ask whether simpler approaches may work. In
what follows we specify three natural attempts that all fail.
Failed attempt 1: random linear order. A first attempt would be to check whether a random linear
order π obtains the desired result (in expectation)1 . The performance of a random linear order is interesting
for an additional reason: it is the performance in scenarios where the graph structure is unknown to the
designer. Unfortunately, there exists a bipartite graph G, even one where all vertices have high degree, for
which a random linear order matches no more than a 1/2 + o(1) fraction of the vertices (see Section 4).
In contrast, we show that in the case of Hamiltonian graphs a random linear order guarantees a
competitive ratio strictly greater than 1/2 (Section 4). A similar proof approach applies to regular graphs
as well.
Results for a random linear order [Theorem 6.2]: There is some constant ρ0H > 1/2 such that for every
Hamiltonian graph G ∈ Gn , regardless of n, a random linear order π results in ρ ≥ ρ0H . Similarly, there
is some constant ρ0R > 1/2 such that for every d-regular graph G, regardless of d, n, a random linear
order π results in ρ ≥ ρ0R .
Failed attempt 2: iterative upgrading. A second attempt would be to iteratively “upgrade” unmatched
vertices, with the hope that the iterative process will reach a state where many vertices will be matched.
That is, in every iteration consider the worst order σ for the current linear order π and move all unmatched
vertices (in the matching produced by (π, σ )) to be ranked higher in π. This algorithm is similar to
the k-pass Category Advice algorithm of [1], but with the difference that in [1] σ remains unchanged
throughout the k iterations.
√ In [1] it was shown that in their setting, the fraction of matched vertices
approaches 2/(1 + 5) ' 0.619 as k grows. In contrast, in Section 7 we show that in our setting this
process can go on for log n iterations before reaching a linear order that matches more than a half of the
vertices. This fact gives some indication that establishing a proof using this operator might be difficult.
Failed attempt 3: degree-based ranking. A third attempt would be to give preference to vertices with
lower degrees, as they would have fewer opportunities to be matched to incoming vertices of U. Consider
a graph with multiple copies of the subgraph (u1 , v1 ), (u2 , v2 ), (u1 , v2 ) along with two additional vertices
ua , ub (and their partners va , vb ). If we connect all vertices of type v1 to ua and ub , we get that their degree
is 3, while the degree of vertices of type v2 is 2. If π is chosen according to the degree, vertices of type v2
will be ranked higher than vertices of type v1 . In this case, if σ orders the vertices of type u1 first, they
will be matched to vertices of type v2 , leaving the vertices of type v1 unmatched. The resulting matching
will therefore be of size (1/2 + o(1))n.
Why is this model interesting mathematically? The setting of max-min greedy matching is easy to
state. The deceptively simple problem of getting a ratio bounded away from one half turns out to be quite
difficult.
1 Unless stated otherwise, whenever way say “random linear order,” we refer to choosing a linear order uniformly at random.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 4
M AX -M IN G REEDY M ATCHING
As discussed above, several natural approaches fail to achieve this. The problem remained open for
quite some time, despite attempts to solve it. Indeed, the solution that we find is not simple; it involves
taking the best of four algorithms. However, these algorithms are not unrelated. They all share a unifying
theme that involves a clean combinatorial property, referred to as a maximal path cover (see Section 2).
This theme enabled us to break the barrier of half, but interesting problems remain open, such as whether
the bound of 2/3 can be achieved. We hope that the progress made in this paper will motivate and enable
further improvement in this interesting problem.
1.2 Additional results
We further establish lower and upper bounds for regular graphs.
Results for√regular graphs [Corollary 3.3 and Theorem 3.5]: For d-regulars bipartite graphs, ρ ≥
5/9 − O(1/ d). On the other hand, for every integer d ≥ 1, there is a regular graph Gd of even degree
2d such that ρ(Gd ) ≤ 8/9.
An additional natural problem is to find the best linear order π, given a graph G. We suspect that
this is a difficult computational problem. However, the special case of determining whether there is a
perfect π (a linear order on V that for every linear order σ leads to a perfect matching) does have a
polynomial-time algorithm. (The proof appears in Section 5.)
Theorem 1.1. There is a polynomial-time algorithm that given a graph G ∈ Gn determines whether G
has a perfect π, and if so, computes a perfect π.
1.3 Application to resource allocation and pricing
Various problems related to online bipartite matching are closely related to problems that attract attention
in the algorithms community. Gaining better understanding of the max-min greedy matching problem
sheds light on more general problems, some of which are still open. In what follows we elaborate on an
application to a pricing problem.
Feldman et al. [9] study the design of pricing mechanisms for allocation of items in markets. The
basic setting is a matching market, where vi j is the value agent i obtains from getting item j, and every
agent can receive at most a single item. The seller assigns prices to items, and agents arrive in an
adversarial order (after observing the prices), each purchasing an (arbitrary) item that maximizes their
utility (defined as value minus price). It is shown that, given a weighted bipartite graph (with agents on
one side, items of the other side, and weight vi j for the edge between agent i and item j), one can set
item prices that guarantee at least half of the optimal welfare for any arrival order. The last result holds
in much more general settings, namely settings where buyers have submodular valuations over bundles
of items 2 , and even in a Bayesain settings, where the seller knows only the (product) distribution from
which agent valuations are drawn, but not their realizations.
In the Bayesian setting no item prices can guarantee better than half of the optimal welfare in the
worst case. A natural question is whether this ratio can be improved in scenarios where the designer
2 A valuation is said to be submodular if for every two sets S, T , v(S) + v(T ) ≥ v(S ∪ T ) + v(S ∩ T ),.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 5
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
knows the realized values of the buyers from the outset 3 . Concretely, do there exist item prices that
guarantee strictly more than half the optimal welfare, for any arrival order σ ? Not only has this question
been open for general combinatorial auctions with submodular valuations, it has been open even for
unit-demand buyers, and even if all individual values are in {0, 1} (henceforth referred to as binary
unit demand valuations). In the latter setting, pricing is equivalent to imposing a linear order over the
items, hence the max-min greedy matching is a precise formulation for the pricing problem in binary
unit-demand settings.
An equivalent scenario is one where in each step the “items player” offers an item, and the “buyers
player,” upon seeing the item, allocates the item to one of the buyers who want the item (if there are
any), and that buyer leaves. The items player is non-adaptive (plays blindfolded, without seeing which
buyers remain4 ). The size of the matching that can be guaranteed by the items player is equivalent to the
max-min greedy matching problem.
Yet an additional equivalent formulation of the problem is one where the linear order π is imposed
over the buyers rather than over the items. The buyers then arrive in the order of π, each taking an
arbitrary item they want. One can verify that the size of the matching that can be guaranteed by an
ordering over the buyers is equivalent to the max-min greedy matching problem.
1.4 Relation to prior work
Relation to online bipartite matching The max-min greedy Matching problem is a nonstandard
version of online problems. In the standard online matching problem [13], the algorithm designer has
control over the matching algorithm, but has no control over the arrival order of clients (vertices). Our
setting can model a situation in which the designer (the maximizing player) has full control over the
arrival order of clients (it knows which “items” in U each “client” in V wants, and it chooses π based on
this knowledge), but no control over the matching algorithm (the minimizing player can choose the worst
possible match in every step, effectively resulting in a linear order σ ).
Karp et al. [13] introduced the Ranking algorithm which has a 1 − 1/e competitive ratio in the online
bipartite matching setting [13, 11]. Translating this algorithm to our max-min greedy setting, it amounts
to simply selecting π at random, and then the minimizing player selects σ after seeing π. We show that
there are bipartite graphs G ∈ Gn for which with high probability over the random choice of π, there is a
choice of σ resulting in MG [σ , π] ≤ 1/2 + o(1). Karp et al. [13] also showed that no algorithm for online
bipartite matching has a competitive ratio better than 1 − 1/e + o(1). This was shown by exhibiting a
distribution over “difficult” graphs. Each graph in the support of this distribution has a unique perfect
matching, and consequently (see Proposition 2.2), there is a linear order π in the max-min greedy setting
that ensures that all vertices are matched (regardless of σ ). Hence neither the lower bounds nor the upper
bounds known for the online matching model give useful bounds in the max-min greedy model.
There are additional known results for online bipartite matching. For √ d-regular graphs, Cohen and
√
Wajc [3] present a randomized algorithm that obtains 1 − O( log d/ d) in expectation, and a lower
3 The full information assumption is sensible in repeated markets or in markets where the stakes are high and the designer
may invest in learning the demand in the market before setting prices.
4 We note that when the items player is adaptive (chooses the next item based on what happened in the past), the items player
can ensure a perfect matching. This is done as follows: in each step, find a minimal tight set of items, and offer an arbitrary item
from that set. Here, a set of items is tight if the number of buyers that want items in the set is equal to the size of the set.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 6
M AX -M IN G REEDY M ATCHING
√
bound of 1 − O(1/ d). This is in contrast to our Theorem 3.5 that shows that ρ is bounded away from 1
even when d is arbitrarily large. For general bipartite graphs, under random (rather than adversarial)
arrival order, the deterministic greedy algorithm gives 1 − 1/e and no deterministic algorithm can obtain
more than 3/4 [11]. Ranking (which is a randomized algorithm) obtains at least 0.696 of the optimal
matching [15] and at most 0.727 [12]. No randomized algorithm can obtain more than 0.823 [16].
Relation to pricing mechanisms Our work is also related to the recent body of literature on pricing
mechanisms. Motivated by the fact that in real-life situations one is often willing to trade optimality for
simplicity, the study of simple mechanisms has gained a lot of interest in the literature on algorithmic
mechanism design. One of the simplest forms of mechanisms is that of posted price mechanisms, where
prices are associated with items and agents buy their most preferred bundles as they arrive. Pricing
mechanisms have many advantages: they are simple, straightforward, and allow for asynchronous arrival
and departure of buyers. Various forms of posted price mechanisms for welfare maximization have been
proposed for various combinatorial settings [9, 5, 14, 7]. These mechanisms are divided along several
axes, such as item vs. bundle pricing, static vs. dynamic pricing, and anonymous vs. personalized
pricing. For any market with submodular valuations, one can obtain 1/2 of the optimal welfare by static,
anonymous item prices [9]. Until the present paper, no results better than 1/2 were known even for
markets with unit-demand valuations with {0, 1} individual values. For a market with m identical items,
there exists a pricing scheme that obtains at least 5/7 − 1/m of the optimal welfare for submodular
valuations [7].
2 Proof of main result
The graph G(U,V ; E) with |U| = |V | = n has a perfect matching M in which ui ∈ U is matched with
vi ∈ V for every 1 ≤ i ≤ n. For a given i, we refer to ui and vi as partners of each other. Given a set S ⊂ V ,
the set of neighbors of S is denoted as N(S) (where necessarily N(S) ⊂ U). In this section we prove our
main result.
Theorem 2.1. Given a bipartite graph G(U,V ; E) with a perfect matching {(ui , vi )}, there exists a linear
order π that guarantees that the greedy matching will be of size at least 22
43 n, regardless of σ . Moreover,
there is a polynomial-time algorithm that chooses π with such a guarantee.
Our proof approach is as follows. We shall first associate with G an auxiliary directed graph that
we refer to as the spoiling graph H(V, D). This notion by itself is not new—similar notions appear in
previous related work. The new aspect related to the spoiling graph and the key to our approach is
a notion of a maximal path cover. Given a maximal path cover of the spoiling graph (which, as we
show in Proposition 2.3, can be found in polynomial time), we partition the set V of vertices into four
classes, depending on their roles in the maximal path cover. The classes are V1 (singleton vertices), S
(start vertices of paths), T (end vertices of paths), and I (intermediate vertices of paths). By considering
several carefully chosen orders among the classes of vertices, and also of vertices within the classes, we
obtain four possible candidate linear orders for π, denoted π1 , π2 , π3 , π4 . We show that for every bipartite
graph with a perfect matching, at least one of these linear orders, if used as π, guarantees that the greedy
matching will be of size at least 22
43 n, for every σ . Put in other words, if for each of {π1 , π2 , π3 , π4 } there
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 7
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
is a linear order over U for which the greedy matching is smaller than 22 43 n, this would imply (using
properties listed in Lemma 2.4) that the path cover giving rise to these linear orders was not maximal.
Our lemma statements provide tools to identify the correct π in polynomial time using properties of the
classes V1 , S, T, and I described above.
𝑈 𝑉 𝑉
𝑢1 𝑣1 𝑣1
𝑢2 𝑣2 𝑣2
𝑢3 𝑣3 𝑣3
𝑢4 𝑣4 𝑣4
𝑎 𝐺(𝑈, 𝑉; 𝐸) 𝑏 𝐻(𝑉; 𝐷)
Figure 2: (a) A graph G(U,V ; E); (b) The corresponding spoiling graph of G, H(V, D).
We now proceed to define the spoiling graph. Given G(U,V ; E), consider a directed graph H(V, D)
whose vertices are the set V , and whose set D of directed edges (arcs) is defined as follows: (vi , v j ) ∈ D iff
(u j , vi ) ∈ E (see Figure 2 for an illustration). We refer to H(V, D) as the spoiling graph for G, because arc
(vi , v j ) ∈ D allows for the possibility that edge (u j , vi ) ∈ E is chosen into a matching M 0 in G, spoiling for
v j the possibility (offered by M) of being matched to u j . Note that this spoiling effect may materialize in
a (σ , π) matching only if vi is ranked higher than v j in π. Hence the spoiling graph conveys information
that may be relevant to the choice of π.
As an example of the information that can be derived from the spoiling graph, consider the following
proposition (whose proof can be also obtained as a special case of a result given in [4] and [19] for the
more general case of Gross Substitutes valuations).
Proposition 2.2. If G has a unique perfect matching, then ρ(G) = 1.
Proof. Let ui ∈ U and vi ∈ V be partners in the unique perfect matching M of G. We claim that the spoiling
graph H of G is a directed acyclic graph (DAG). Suppose toward a contradiction that H contains a simple
directed cycle vi1 , vi2 , . . . , vi` , vi1 . This directed cycle corresponds to the cycle ui1 , vi1 , ui2 , vi2 , . . . , ui` , vi` , ui1
in G. But removing the edges (ui j , vi j ), 1 ≤ j ≤ ` from M and adding the edges (ui j , vi j+1 ) to M (where
` + 1 = 1) yields a different perfect matching, contradicting the uniqueness of M.
Since H is a DAG, we can topologically sort its vertices and choose a linear order π such that earlier
vertices in the topological order have a lower rank in π. This ensures that for every directed edge (v, w) in
H, the partner of vertex v will never prefer w over v. Thus, every vertex chooses its partner in M upon
arrival.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 8
M AX -M IN G REEDY M ATCHING
We now proceed to define the notion of a maximal path cover. A directed path P (whose length
is denoted by |P|) in H is a sequence of |P| vertices (say, v1 , . . . , v|P| ) such that (vi , vi+1 ) ∈ D for all
1 ≤ i ≤ |P| − 1. A single vertex is a path of length 1. A path cover of H is a collection of vertex-disjoint
directed paths that covers all vertices in V . We consider the following operations that can transform a
given path cover to a different one (see Figure 3 for an illustration):
1. Path merging: Two paths can be merged into one longer path if H(V, D) has an arc from the end of
one path to the start of the other path.
2. Path unbalancing: Consider any two paths P and P0 with 1 < |P| ≤ |P0 |, let vs and vt denote the
first and last vertices of P, and let v0s and vt0 denote the first and last vertices of P0 . If (vs , v0s ) ∈ D
we may remove vs from P and append it at the beginning of P0 . Likewise, if (vt0 , vt ) ∈ D we may
remove vt from P and append it at the end of P0 .
3. Rotation: if there is a path P (say, vs , . . . , vt ) such that (vt , vs ) ∈ D, we may add the arc (vt , vs ) to P
(obtaining a cycle), and then remove any other single arc from the resulting cycle to get a path P0 .
Observe that P0 and P have the same vertex set, but they differ in their starting vertex along the
cycle vs , . . . , vt , vs .
A path cover is maximal if no path merging operation and no path unbalancing can be applied to it,
and furthermore, this continues to hold even after performing any single rotation operation.
Proposition 2.3. Given a bipartite graph G(U,V ; E) with a perfect matching {(ui , vi )}, a maximal path
cover in the associated spoiling graph H(V, D) can be found in O(n3 ) time.
Proof. Start with the trivial path cover in which each vertex of V forms a path of length 1, and perform
arbitrary path merging and path unbalancing operations (some of which are preceded by a single rotation
operation) until no longer possible. The process must end within O(n2 ) operations, because each path
merging and each path unbalancing operation increases the sum of squares of the lengths of the paths,
and the sum of squares of the lengths is at most n2 . Each of these operations can be performed in O(n)
time.
Given a maximal path cover of H (where p denotes the number of paths in the path cover), sort the
paths in order of increasing lengths, breaking ties arbitrarily. Hence 1 ≤ |P1 | ≤ |P2 | ≤ . . . ≤ |Pp |. We
consider the following classes of vertices of V :
1. Singleton vertices V1 . These are the vertices that belong to paths of length 1 in the given maximal
path cover. Let k = |V1 | denote the number of singleton vertices. Observe that |Pk | = 1 and
|Pk+1 | > 1.
2. Other vertices V2 = V \V1 . We partition V2 into three subclasses of vertices:
(a) Start vertices S. These are the starting vertices of those paths that have length larger than 1.
The start vertex of path j, for k < j ≤ p, is denoted by s j .
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 9
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
𝑣1 𝑣2 𝑣3 𝑣4 𝑣5 𝑣6 𝑣7 𝑣8
𝑎 Spoiling graph
𝑃1 𝑣4 𝑃1 𝑣4 𝑃1 𝑣4
𝑃2 𝑣2 𝑣1 𝑃2 𝑣3 𝑣6 𝑣7 𝑃2 𝑣3 𝑣6
𝑃3 𝑣8 𝑣5 𝑃3 𝑣2 𝑣1 𝑣8 𝑣5 𝑃3 𝑣2 𝑣1 𝑣8 𝑣5 𝑣7
𝑃4 𝑣3 𝑣6 𝑣7
𝑏 Path cover 1 𝑐 Path cover 2 𝑑 Path cover 3
Figure 3: (a) A spoiling graph H; (b) Path cover 1 — a path cover of H; (c) Path cover 2, obtained
from Path cover 1 by merging paths P2 , P3 ; (d) Path cover 3, obtained from Path cover 2 by unbalancing
paths P2 , P3 . One can verify that Path cover 3 is maximal. In Path cover 3, V1 = {v4 }, S = {v3 , v2 },
T = {v6 , v7 }, I = {v1 , v8 , v5 }. To illustrate the notion of rotation, suppose H had contained two additional
edges (v7 , v2 ), (v1 , v3 ), then Path cover 3 would not have been maximal, as one could rotate P3 to get
P30 = v8 , v5 , v7 , v2 , v1 , then merge it with P2 .
(b) End vertices T . These are the end vertices of those paths that have length larger than 1. The
end vertex of path j, for k < j ≤ p, is denoted by t j .
(c) Intermediate vertices I = V2 \ (S ∪ T ).
Lemma 2.4. The classes of vertices listed above have the following properties.
1. There are no arcs in H between vertices of V1 . Hence no vertex of V1 can be a spoiler vertex for
another vertex in V1 .
2. There are no arcs in H from vertices of V1 to vertices in S. Hence no vertex of V1 can be a spoiler
vertex for a vertex in S.
3. There are no arcs in H from vertices of T to vertices in V1 . Hence no vertex of T can be a spoiler
vertex for a vertex in V1 .
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 10
M AX -M IN G REEDY M ATCHING
4. For i 6= j, there are no arcs in H from any vertex ti ∈ T to any vertex s j ∈ S. Hence no vertex of
T can be a spoiler vertex for a vertex in S, unless they both belong to the same path in the given
maximal path cover.
5. (si , s j ) 6∈ D for any si , s j ∈ S with i < j. Hence si cannot be a spoiler vertex for s j if i < j.
6. (t j ,ti ) 6∈ D for any ti ,t j ∈ S with i < j. Hence t j cannot be a spoiler vertex for ti if i < j.
7. If for some s j ∈ S and t j ∈ T (where s j and t j are start and end vertices of the same path Pj ) we
have (t j , s j ) ∈ D, then there are no arcs from (T \ {t j }) ∪V1 to any of the vertices of Pj , and likewise,
no arcs from sk+1 , . . . , s j−1 to any of the vertices of Pj .
Proof. All properties follow from the maximality of the path cover. Properties 1,2,3 and 4 hold because
otherwise one could perform a path merging operation. Properties 5 and 6 hold because otherwise one
could perform a path unbalancing operation. Property 7 holds because otherwise one could perform
a rotation operation for path Pj , followed either by a path merging operation (if there is an arc from
(T \ {t j }) ∪ V1 to any of the vertices of Pj ) or a path unbalancing operation (if there is an arc from
sk+1 , . . . , s j−1 to any of the vertices of Pj ).
We now introduce additional notation. Considering only the arcs in D leading from V2 to V1 , we let
M21 denote the maximum matching among these arcs. In our analysis we shall consider three parameters:
1. ε1 : its value is such that k = (1/2 − ε1 ) n (recall that k = |V1 | is the number of singleton paths in
the maximal path cover). Observe that ε1 might be negative.
2. ε2 : its value is such that p = k + ε2 n = (1/2 − ε1 + ε2 ) n (recall that p is the total number of paths
in the maximal path cover). Necessarily, ε2 ≥ 0.
3. ε3 : its value is such that |M21 | = (1/2 − ε3 ) n. Necessarily, ε3 ≥ 0.
Given the above classes of vertices, we consider four possible candidate linear orders for π (denoted
π1 , π2 , π3 , π4 , see below for details). Given some linear order π, we shall use the notation ρ(π) to denote
the fraction of vertices guaranteed to be matched under π. This fraction will be expressed as a function
of the parameters ε1 , ε2 and ε3 , and we will show that regardless of the value of these parameters, there
must be some π with ρ(π) ≥ 22/43.
The following four lemmas present the four candidate linear orders for π along with their correspond-
ing guarantees. Whenever unspecified, the order within a set of vertices can be arbitrary; e. g., for two
sets of vertices X,Y , π = X,Y means that the set X precedes Y and the order within X, as well as the
order within Y , is arbitrary.
Lemma 2.5. For G and π1 = V2 ,V1 ,
1 |V2 | |M21 | 1 ε1 ε3
ρ(π1 ) ≥ |V1 | + − = − + .
n 2 2 2 2 2
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 11
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
Proof. Let σ be an arbitrary linear order over U. Let m denote the number of vertices in V2 that are
matched to vertices in U1 , where U1 is the set of partners of V1 . Then m ≤ |M21 |. Of the |V2 | − m vertices
of V2 not matched to vertices in U1 , at least half are matched (because for every unmatched vertex from
this set, its partner must be matched to a different vertex from this set). In addition, all those vertices of
V1 whose partner is not matched to V2 are matched, because of property 1 of Lemma 2.4. Hence the total
number of vertices matched is at least
|V2 | − m |V2 | |M21 |
m+ + |V1 | − m ≥ |V1 | + − , (2.1)
2 2 2
as desired.
Lemma 2.6. For G and π2 = V1 ,V2 ,
2 1
ρ(π2 ) ≥ − (ε1 + ε3 ).
3 3
Proof. Let σ be an arbitrary linear order over U. All vertices in V1 are matched because of property 1 of
Lemma 2.4. As to the vertices in V2 , observe that |N(V2 )| ≥ |V2 | + |M21 |, as the set N(V2 ) includes the
|V2 | partners of V2 , plus at least |M21 | additional neighbors in U1 (due to the matching M21 ). Moreover, if
x vertices are removed from V2 , the number of remaining neighbors is at least |V2 | + |M21 | − 2x, because
each vertex of V2 contributed at most two neighbors to the lower bound that we provided on the number
of neighbors.
Let x denote the number of vertices in V2 matched under (π2 , σ ). Then the size of the matching
is |V1 | + x, the number of unmatched vertices in V2 is |V2 | − x, and they have at least |V2 | + |M21 | − 2x
neighbors which have to be matched. Since the number of matched vertices on each side is the same, we
have that |V1 | + x ≥ |V2 | + |M21 | − 2x.
We get that
1 1 1
3x ≥ |V2 | + |M21 | − |V1 | = n + ε1 + n − ε3 − n − ε1 (2.2)
2 2 2
1
= + 2ε1 − ε3 n. (2.3)
2
Therefore, the size of the matching is at least
1 1 2ε1 ε3 2 1
|V1 | + x ≥ − ε1 n + + − n= − (ε1 + ε3 ) n. (2.4)
2 6 3 3 3 3
Lemma 2.7. For G and π3 = t p , . . . ,tk+1 ,V1 , sk+1 , . . . , s p , I,
2p − k 1
ρ(π3 ) ≥ = − ε1 + 2ε2 .
n 2
Proof. In π3 , we refer to the vertices of T ∪V1 ∪ S as the prefix of π3 , and to the vertices of I as the suffix.
Lemma 2.4 implies that within the prefix, the only arcs of H that go from an earlier vertex to a later vertex
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 12
M AX -M IN G REEDY M ATCHING
are of the form (t j , s j ) (for a path Pj that can undergo a rotation). We claim that regardless of σ , all the
prefix will be matched. As the length of this prefix is 2p − k, this will prove the lemma.
It remains to prove the claim. Suppose first that in the above prefix there are no arcs of H that go
from an earlier vertex to a later vertex. Then earlier vertices in this prefix cannot be spoiling vertices for
later vertices. Hence indeed, regardless of σ , all the prefix will be matched.
Suppose now that in the prefix of π3 there are arcs of H that go from an earlier vertex to a later vertex.
As noted above, such an arc would be of the form (t j , s j ). We need to show that even if t j acts as a spoiling
vertex for s j under π3 and σ , the vertex s j will still be matched. Consider the path Pj , and let us rename
its vertices as x1 , . . . , x` (where previously we used s j = x1 and t j = x` ). We wish to show the x1 would be
matched even if x` is matched to the partner of x1 . The path Pj implies that the partner of x2 is a neighbor
of x1 in G. Hence x1 will be matched if no vertex preceding x1 = s j in π3 is matched to the partner of x2 .
By property 7 of Lemma 2.4, there is no arc in H from any of the vertices T ∪V1 ∩ {sk+1 , . . . , s j−1 } \ {t j }
to x2 , and consequently none of them can be matched to the partner of x2 . As to t j = x` , it might be a
neighbor of the partner of x2 (in fact, it could be that ` = 2), but we already assumed that t j is matched to
the partner of x1 , and hence it is not matched to the partner of x2 . Hence no vertex preceding x1 = s j in
π3 is matched to the partner of x2 , and hence s j will be matched.
Let Ve (Vo , respectively) denote those vertices of S ∪ I that are at even (odd, respectively) distance
from the beginning of their respective path. Observe that S ⊂ Ve .
Lemma 2.8. For G and π4 = t p , . . . ,tk+1 ,V1 ,Vo ,Ve ,
5 p 1 ε1 ε2
ρ(π4 ) ≥ − = + − .
9 9n 2 9 9
Proof. Observe that |Ve | ≥ |Vo |, because in every path (of length above 1) the vertices alternate in entering
Ve and Vo , and start with Ve . Observe also that every vertex v ∈ Ve contributes two distinct neighbors to
N(Ve ): the partner of v, and the partner of the vertex that follows v on its path (note that the vertex that
follows v is not in Ve ). Likewise, every vertex v ∈ Vo contributes two distinct neighbors to N(Vo ).
Regardless of σ , all p vertices of T and V1 are matched, as in Lemma 2.7. For a given σ , let no be the
number of vertices matched in Vo and let ne be the number of vertices matched in Ve . Then, |Vo | − no ,
the number of unmatched vertices in Vo , satisfies 2(|Vo | − no ) ≤ p + no , because the neighbors of the
unmatched vertices in Vo need to be matched to earlier vertices in T ∪V1 ∪Vo . Likewise, |Ve | − ne , the
number of unmatched vertices in Ve , satisfies 2(|Ve | − ne ) ≤ p + no + ne . Adding two times the first
inequality and three times the second we get that 4|Vo | + 6|Ve | − 4no − 6ne ≤ 5p + 5no + 3ne . Using
|Vo |+|Ve | = n− p and |Ve | ≥ |Vo |, we can replace 4|Vo |+6|Ve | by 5(n− p), implying that 9(p+no +ne ) ≥
5n − p, as desired.
We can now prove Theorem 2.1.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 13
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
Proof. Observe that ρ(G) ≥ maxi∈[1,4] [ρ(πi )].
1 ε1 ε3
By Lemma 2.5 we have: ρ(π1 ) ≥ − + . (2.5)
2 2 2
2 1
By Lemma 2.6 we have: ρ(π2 ) ≥ − (ε1 + ε3 ). (2.6)
3 3
1
By Lemma 2.7 we have: ρ(π3 ) ≥ − ε1 + 2ε2 . (2.7)
2
1 ε1 ε2
By Lemma 2.8 we have: ρ(π4 ) ≥ + − . (2.8)
2 9 9
Taking a weighted average of the lower bounds provided by the four lemmas, with weights
2 3 2 36
, , , ,
43 43 43 43
respectively, results in a weighted average of 22/43. Hence regardless, of the values of ε1 , ε2 and ε3 , at
least one of the lemmas gives ρ(G) ≥ 22/43. For
19 10 21
ε1 = , ε2 = , ε3 = ,
86 86 86
none of the lemmas implies a bound better than
1 1 22
+ = .
2 86 43
The above analysis leads to a polynomial-time algorithm for finding π that ensures ρ(G) ≥ 22/43. A
maximal path cover of H(V, D) can be found in polynomial time by Proposition 2.3. Thereafter, the sets
V1 , S, T , Ve and Vo can easily be determined, and likewise, the values of ε1 and ε2 can be easily computed.
A maximum matching M21 (from V2 to V1 in H) can be computed in polynomial time using any standard
algorithm for maximum bipartite matching. Thereafter, ε3 can be easily computed. Given the values
ε1 , ε2 and ε3 , one can determine which of π1 , π2 , π3 or π4 provides a higher lower bound on ρ, and use
that linear order as π.
3 Regular graphs
In this section we consider the case where G(U,V ; E) is a d-regular bipartite graph with 2n vertices.
Given that such graphs have d edge-disjoint perfect matchings, one can hope to achieve higher values for
ρ for these graphs.
3.1 Positive result
The following known fact (see for example [18]) establishes a lower bound on ρ, as a function of d. A
proof is provided for completeness.
Proposition 3.1. For every d-regular graph G ∈ Gn , the inequality ρ[G] ≥ d/(2d − 1) holds.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 14
M AX -M IN G REEDY M ATCHING
Proof. Since the greedy algorithm produces a maximal matching, it suffices to show that every maximal
d
matching in a d-regular graph has size at least 2d−1 n. To see this, let S ⊂ U and T ⊂ V be the sets of
unmatched nodes in an arbitrary maximal matching, and suppose |S| = |T | = (1 − α)n. The nodes in S, T
must form an independent set. Consider the size of the edge set connecting S and V \ T . On the one hand,
this size equals (1 − α)nd (since all edges from S go to V \ T ); on the other hand, this size is at most
αn(d − 1) (since at least one edge from each node in V \ T goes to U \ S). Thus, (1 − α)nd ≤ αn(d − 1),
d
implying that α ≥ d/(2d − 1). Hence we have that |MG [σ , π]| ≥ 2d−1 n, for every π.
Remark 3.2. For every d there exists a d-regular graph with a perfect matching that admits a maximal
d
matching of size 2d−1 n. Suppose that n = 2d − 1, and consider a d-regular graph where |S| = |T | = d − 1
for some S ⊂ U, T ⊂ V , every node in U \ S is connected to a single, different node in V \ T , and to all
d − 1 nodes in T , and every node in V \ T is connected to a single, different node in U \ S, and to all d − 1
d
nodes in S. The perfect matching between U \ S and V \ T is a maximal matching of size 2d−1 n.
The lower bound of Proposition 3.1 approaches 1/2 from above as d grows. The following theorem
shows that there exists a linear order π that ensures that the fraction of matched vertices approaches 5/9.
This is a direct corollary from Lemma 2.8 and a theorem in [8].
Corollary 3.3. For d-regulars bipartite graphs,
5 1
ρ≥ −O √ .
9 d
Proof. Theorem 3 in [8] shows√ that every n-vertex d-regular graph has a path cover (referred to √ as a
linear forest) with p = O(n/ d) paths. This means that there exists a maximal path cover with O(n/ d)
paths, as the operations used to reach a maximal path cover (path merging, path unbalancing and rotation)
can only decrease the number of paths. The desired lower bound on ρ(G) follows by Lemma 2.8.
Remark 3.4. 1. For small d, the bound of ρ ≥ d/(2d − 1) which holds for every maximal matching
is stronger than the bound in Corollary 3.3.
2. The proof of Corollary 3.3 extends to graphs that are nearly d-regular, by using Theorem 5 from [8].
3. For d-regular graphs, conjectures mentioned in [8] combined with our proof approach suggest that
ρ ≥ 5/9 − O(1/d).
3.2 Negative result
The following example shows that even in a regular graph with arbitrarily high degree, there may be no
linear order π that ensures to match more than a fraction 8/9 of the vertices.
Theorem 3.5. For every integers d,t ≥ 1, there is a regular bipartite graph Gd,t of even degree 2d and
n = 3dt vertices on each side such that ρ(Gd,t ) ≤ 8/9.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 15
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
Proof. Consider a regular bipartite graph G(U,V ; E) with even degree 2d, and 3d vertices on each side.
To define the edge set, let U = U1 ∪U2 ∪U3 with each Ui of cardinality d, and similarly V = V1 ∪V2 ∪V3
with each Vi of cardinality d. For every i 6= j, we have a complete bipartite graph between Ui and V j , and
for every i, there are no edges between Ui and Vi .
Let π be an arbitrary linear order over V , let S be the first 2d vertices in π, and let T be the last d
vertices. Let i be such that |Vi ∩ T | is largest (breaking ties arbitrarily). Without loss of generality we
may assume that i = 3, and then |V3 ∩ T | ≥ d/3. Hall’s condition implies that there is a perfect matching
between U1 ∪U2 and S (and more generally, between U1 ∪U2 and any 2d vertices from V ). Hence one
can choose a linear order σ over U whose first 2d vertices are U1 ∪U2 that will match the vertices of S
one by one. Thereafter, the vertices of T ∩V3 will remain unmatched.
To get the graph Gd,t claimed in the theorem, take t disjoint copies of G(U,V ; E) above.
4 Random linear order
In this section we consider scenarios in which the maximizing player is unaware of the graph structure.
In such scenarios, the best she can do is impose a random linear order over the vertices in V .
We first show that there exists a graph G ∈ Gn for which a random linear order does not match
significantly more than half of the vertices.
Proposition 4.1. There exists a bipartite graph G(U,V ; E) ∈ Gn such that a random linear order gets
ρ(G) = 1/2 + o(1) almost surely.
Proof. Consider the graph G(U,V ; E), where U = (U1 ,U2 ), V = (V1 ,V2 ), and each of U1 ,U2 ,V1 ,V2 is of
size n/2. The set of edges constitutes a perfect matching between U1 and V1 , a perfect matching between
U2 and V2 , and a bi-clique between U1 and V2 . Let π be a random linear order. Rename the vertices in V1
such that v1 j is the j-th highest vertex from V1 in the linear order π, and u1 j is v1 j ’s match in the perfect
matching between U1 and V1 . Consider an arrival order σ in which vertex u1 j is the j-th vertex (and
U2 arrives after U1 in an arbitrary order). All vertices of U1 will be matched (as they arrive first, there
are only n/2 of them, and each of them has more than n/2 neighbors in V2 ). Vertices in V1 can only be
matched with vertices of U1 .
Let k denote the number of vertices in V1 that are matched, and let v1` be the highest index (i. e.,
lowest ranked) vertex in V1 to be matched (that is, all vertices v1 j with j > ` are unmatched). Necessarily,
v1` is matched with u1` . This can happen only if every vertex from V2 that precedes v1` according to π is
matched at the time that u1` arrives. As k − 1 vertices of V1 are matched before u1` arrives, there can be
at most ` − k vertices from V2 that precede v1` in the linear order π. Hence, for k vertices from V1 to be
matched, the linear order π should be such that for some ` in the range k ≤ ` ≤ n/2, in the prefix of π of
length 2` − k, there are at least ` vertices from V1 and at most ` − k vertices from V2 . Such an ` is said to
be good.
We claim that the probability that a particular ` is good is smaller than the probability that in 2` − k
random tosses of an unbiased coin, at most ` − k tosses come up heads. To see this, note that the prefix
of π is sampled from V without repetition; the random coin version is equivalent to sampling from V
with repetition, where in every sample, regardless of past samples, there is probability 1/2 of sampling a
vertex from V1 (coin coming up tails), and probability 1/2 of sampling a vertex from V2 (coin coming
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 16
M AX -M IN G REEDY M ATCHING
up heads). In both sampling methods, the expectation of the number of vertices from V2 in the prefix is
` − (k/2). The probability of deviating by more than k/2 from the expectation is larger when sampling
with repetitions than when sampling without repetition.
Now, by standard bounds on binomial coefficients (or alternatively, by standard Bernstein bounds5
this probability is at most
2 2
e−k /2(2`−k) ≤ e−k /4` . (4.1)
√
A union bound over all values of ` (in the range k ≤ ` ≤ n/2) shows that if k ≥ 2 n log n, it is highly
unlikely that a good ` exists. Consequently, with overwhelming probability, the size of the matching is
(1/2 + o(1))n, whereas OPT = n.
In the above example, if the vertices of V with degree 1 are placed in the prefix of π, then the matching
obtained is optimal. This might suggest that prioritizing low-degree vertices in π (and randomizing within
sets of vertices of comparable degrees) leads to good performance. However, the example above can be
transformed into one where all vertices in V have the same degree, and moreover, each vertex has a degree
√
of Ω( n). To see this, consider a graph where vertices are partitioned into sets of perfect matchings
√
of size n, {(U11 ,V11 ), . . . , (U1√n ,V1√n ), (U21 ,V21 ), . . . , (U2√n ,V2√n )}. Each V1i is also connected in a
√
bi-clique to U2i , and in addition, there are sets U 0 ,V 0 of size n each connected to the vertices of the
other side to balance out the degrees. A similar argument shows that in this graph, a random linear order
performs badly as well.
In contrast to the last examples, in some classes of graphs, a random linear order guarantees to match
a fraction of the vertices that is bounded away from a half. This is the case, for example, in Hamiltonian
graphs. The formal statement and proof are deferred to Section 6.
5 Finding a perfect π
A linear order π over V is said to be perfect if for every linear order σ over U, |MG [σ , π]| = n. A vertex
v ∈ V is good with respect to a set of vertices S ⊂ V if there is no perfect matching between N(v) and S.
Given a linear order π over V , let π(v) be the set of vertices preceding v in π.
Observation 5.1. π is perfect if and only if every vertex v ∈ V is good with respect to π(v).
Proof. Suppose there exists a vertex v ∈ V that is not good. Then, consider a linear order σ where the
vertices in N(v) are placed first, in an order corresponding to the rank (according to π) of their partners in
the perfect matching between N(v) and π(v). In such a σ , v will not be matched. Now suppose that all
vertices in V are good. Then, for every σ , for every v ∈ V , there exists a vertex u ∈ U that is not matched
to a vertex in π(v); therefore v will surely be matched.
We present an algorithm that finds a perfect π if one exists, and claims that no such π exists otherwise.
Checking whether vi is good can be done in polynomial time by running a maximum matching
algorithm on N(vi ) and Si .
5 These concentration inequalities, commonly misattributed to Chernoff, were published by Sergei N. Bernstein in 1924 and
1937. (See the Wikipedia entry “Bernstein inequalities (probability theory).”)
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 17
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
An algorithm for finding a perfect π:
1. Let S1 = V .
2. For i = 1, . . . , n:
(a) Find an arbitrary good vertex vi ∈ Si with respect to Si \ {vi }, and place it in rank n − i + 1 in
π.
(b) Set Si+1 = Si \ {vi }.
Lemma 5.2. If there exists a perfect π, then the algorithm is guaranteed to find a good vi in every
iteration i.
Proof. Consider some perfect linear order π (not necessarily the one produced by our algorithm), and the
suffix Vi−1 = vi−1 , vi−2 , . . . , v1 of vertices chosen in the first i − 1 iterations of the algorithm. (Of course,
there must be a good v1 at the first iteration, otherwise there is no perfect π.) Let π 0 be the linear order
that places vi−1 , vi−2 , . . . , v1 as the lowest-ranked vertices in the same order as the algorithm picked them,
and places all other vertices of V \Vi−1 in a higher rank than Vi−1 according to their internal order in π.
Since every v j , 1 ≤ j ≤ i − 1, is good with respect to V \ {v1 , . . . , v j }, clearly v j is good with respect
to π 0 (v j ) (since π 0 (v j ) = V \ {v1 , . . . , v j }). Now consider a vertex v ∈ V \Vi−1 . This vertex is good with
respect to π(v), and since π 0 (v) ⊆ π(v), it is clear that v is good with respect to π 0 (v). It follows that π 0 is
perfect as well.
Let v0i be the vertex ranked in position n − i + 1 in π 0 . Since π 0 is perfect, this vertex is good with
respect to π 0 (v0i ). But since π 0 (v0i ) ∪ {v0i } is exactly the set Si in iteration i, it is guaranteed that the
algorithm can find a good vi in this iteration.
Let π be the linear order computed by the algorithm. Since every vertex v is good with respect to
π(v), it follows from Observation 5.1 that π is perfect, and Proposition 1.1 follows.
6 Hamiltonian bipartite graphs
In this section we establish two results about Hamiltonian graphs. First, we show that ρ ≥ 5/9. Note that,
since for the case of a Hamiltonian graph there exists a path cover using only a single path (i. e., p = 1),
Lemma 2.8 directly implies that ρ ≥ 5/9 − 1/9n. Theorem 6.1 improves this bound to 5/9. Second, we
show that for Hamiltonian graphs, even a random linear order π ensures a ratio that is bounded away
from 1/2. (This is in contrast to general graphs, see Section 4.)
Theorem 6.1. For Hamiltonian graphs, ρ ≥ 5/9.
Proof. Consider a Hamiltonian graph G and a Hamiltonian cycle u1 , v1 , u2 , v2 , . . . , un , vn , u1 in G that
passes through the vertices in the order listed. Let Vo = {vi : i = 2` + 1, ` ∈ N, i ≤ n} be the set of odd
labeled vertices of the cycle, and Ve = V \Vo .
We first claim that if the number of vertices is even (|Vo | = |Ve | = n/2), then π = Ve ,Vo (and in fact,
also π = Vo ,Ve ) ensures that ρ ≥ 5/9. Let ne and no be the number of vertices of Ve and Vo , respectively,
matched in MG [σ , π] defined using π = (Ve ,Vo ) and an arbitrary σ . Similarly to the proof of Lemma 2.8,
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 18
M AX -M IN G REEDY M ATCHING
it is easy to see that each vertex in Ve contributes two distinct neighbors to N(Ve ), and each vertex in Vo
contributes two distinct neighbors to N(Vo ). (The difference from the proof of Lemma 2.8 is that this
property also holds for v1 ∈ Vo and vn ∈ Ve , and this follows because v1 and vn contribute u1 to N(Vo ) and
N(Ve ), respectively.) The number of unmatched vertices in Ve , namely |Ve | − ne , satisfies
2(|Ve | − ne ) ≤ ne , (6.1)
because the neighbors of the unmatched vertices in Ve must be matched to vertices in Ve , as they precede
the vertices in Vo in π. Likewise, the number of unmatched vertices in No , namely |Vo | − no , satisfies
2(|Vo | − no ) ≤ ne + no . (6.2)
Adding two times the first inequality and three times the second, we get
5
4|Ve | + 6|Vo | ≤ 9(no + ne ) ⇒ · n ≤ no + ne . (6.3)
9
As |V | = n and |MG [σ , π]| = no + ne , this implies that ρ ≥ 5/9.
We now handle the case where n is odd. Lemma 2.8 ensures that 59 · n − 91 of the vertices are matched
by π4 when the path cover is of a single path. If 59 · n − 91 is not integral, then d 59 · n − 19 e is at least
5 5 5 1
9 · n, thus ρ ≥ 9 . Therefore, it only remains to handle the case where 9 · n − 9 is integral; namely
where n = 18` + 11 for some integer ` (recall that n is odd in this case). In this case, we show that
π = Ve ,Vo ensures that |M[σ , π]| > 59 · n for every σ . Since n = 18` + 11, it follows that |Vo | = 9` + 6
and |Ve | = 9` + 5. As in the case where n is even, every vertex in Ve contributes two distinct neighbors to
N(Ve ). As for Vo , every vertex in Vo \ {v1 , vn } also contributes two distinct neighbors to N(Vo ), and v1
and vn contribute (together) to N(Vo ) three additional distinct vertices (since they share a vertex along the
Hamiltonian cycles). Using the same reasoning as before, it follows that
1
2(|Ve | − ne ) ≤ ne ⇒ 18` + 10 ≤ 3 · ne ⇒ ne ≥ 6` + 3 . (6.4)
3
Since ne is integral, this implies that
ne ≥ 6` + 4. (6.5)
Again, for |Vo | − no we have 2(|Vo | − no ) − 1 ≤ no + ne . Rearranging gives us
ne + 3no ≥ 18` + 11. (6.6)
Adding twice Inequality (6.5) to the last inequality yields
1 1 5
ne + no ≥ 10` + 6 > 10` + 6 = · |V |, (6.7)
3 9 9
which implies ρ > 95 . This concludes the proof.
Next, we show that for the case of a Hamiltonian graph, a random linear order yields a ρ > 1/2.
Theorem 6.2. Consider choosing a linear order π at random. For every Hamiltonian graph G, we have
Eπ [minσ [|MG [σ , π]|]] > 0.5012.
Since the proof is quite involved, we first give a proof overview before providing a formal proof.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 19
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
6.1 Proof overview
We first provide a high-level overview of our proof.
A linear order π (over V ) is said to be safe for a set S ⊂ V if for every linear order σ (over U) the
greedy process matches at least one vertex in S (i. e., no σ leaves all vertices in S unmatched). Fix some
constant ε. In order to establish that ρ ≥ (1/2 + ε), we need to show that there exists a linear order π
that is safe for every set S of size (1/2 − ε)n. Our proof approach is the following: we show that for a
linear order π chosen at random, the expected number (expectation taken over choice of π) of sets of size
(1/2 − ε)n for which π is unsafe is smaller than 1. This implies that there exists a linear order π that is
safe for all sets of size (1/2 − ε)n, as desired.
First, we define a collection of sets that can potentially remain unmatched (“bad” sets). Let Bε denote
the set of all sets S ⊂ U of size (1/2 − ε)n such that there exists a linear order π that is unsafe for S.
Second, for a given set S and a linear order π we identify a sufficient condition for π to be safe for S.
Let S0 ⊂ S be the lowest αn vertices in S (according to π), let v0 be the last vertex in S0 (i. e., the vertex
with rank αn in S0 ), and let P be the set of vertices in V − S0 that precede v0 in π. We claim that if the size
of P is smaller than the size of N(S0 ) (the neighbors of S0 ), then π is safe for S. To see this, assume by
way of contradiction that π is unsafe for S0 . This implies that every vertex in N(S0 ) is matched to a vertex
in V − S0 . Since there are strictly less than |N(S0 )| vertices in V − S0 that precede v0 , at least one of the
vertices in N(S0 ) must be matched to a vertex higher than v0 . But, this vertex has a neighbor in S0 with
lower rank, contradicting the greedy process.
We now proceed by establishing the following three lemmas:
• Few bad sets lemma: the size of Bε is at most nB = nB (ε).
• Expansion lemma: given a set S ⊂ V and parameters α, β , the probability (over a random choice
of π) that the lowest αn vertices in S have less than β n neighbors is at most p = p(α, β ).
• Good order lemma: given a set S ⊂ V and parameters α, β , the probability (over a random choice
of π) that the (αn)th lowest vertex in S is higher than β n vertices in V \ S is at most q = q(α, β ).
The three lemmas are combined as follows. For a given set S, due to the sufficient condition identified
above, it follows from the union bound that the probability that a random linear order π is unsafe for S is
at most p + q. Applying the union bound once more over all bad sets (at most nB sets, as implied by the
few bad sets lemma), implies that the probability that a random linear order π is unsafe for some set of
size (1/2 − ε)n is at most nB (p + q). Thus, to conclude the proof, it remains to find parameters such that
nB (p + q) < 1.
The good order lemma is independent of the graph structure. In contrast, the expansion lemma and
the few bad sets lemma rely heavily on the structure of the graph. As it turns out, Hamiltonian graphs
have properties that enable us to establish the two lemmas with good parameters.
6.2 Full proof of Theorem 6.2
We use H(·) to denote the binary entropy function, i. e., given p ∈ (0, 1),
H(p) = −p log2 p − (1 − p) log2 (1 − p). (6.8)
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 20
M AX -M IN G REEDY M ATCHING
Fact 6.3 (Stirling’s Approximation). As n → ∞,
√ n n
n! = (1 + o(1)) 2πn . (6.9)
e
Using Stirling’s Approximation, one can derive the following bound.
Fact 6.4. For n and k = pn for some constant p ∈ (0, 1), as n → ∞,
n
= 2(H(p)+o(1))n . (6.10)
k
We first establish the good order lemma, which is independent of the graph structure.
Lemma 6.5 (Good order lemma). Let α < β < 1, ρ = 21 + ε for some ε > 0 and ρ̄ = 1 − ρ such that
β ρ
α > ρ̄ . Let S ⊂ V be a set of size ρ̄n. The probability that in a random linear order π there are at least
β n vertices of V \ S before αn vertices from S is at most
α β
2−(H(α+β )−H( ρ̄ )ρ̄−H( ρ )ρ−o(1))n .
Proof. We first analyze the case that in the first (α + β)n vertices in π there are exactly αn vertices from
ρ̄n ρn
S. The number of possibilities for this case is αn βn
.
0
Let β 0 = β + x and α 0 = α − x. By the conditions on α, β and ε, we have that αβ 0 ≥ αβ ≥ ρρ̄ . Therefore,
(ρ̄ − α 0 ) β0
β 0 ρ̄ ≥ α 0 ρ ⇒ β 0 ρ̄ − α 0 β 0 ≥ α 0 ρ − α 0 β 0 ⇒ · ≥1 (6.11)
α0 (ρ − β 0 )
ρ̄n ρn
(ρ̄n − α 0 n + 1) β 0 n + 1 α 0n β 0n
⇒ · > 1 ⇐⇒ ρ̄n ρn > 1. (6.12)
α 0n (ρn − β 0 n) α 0 n−1 β 0 n+1
> αρ̄n0 n βρn0 n for every α 0 < α and β 0 > β such that α + β = α 0 + β 0 . Therefore,
ρ̄n ρn
It follows that αn βn
the probability to have at most αn vertices from S in the first (α + β )n vertices in π is at most
ρ̄n ρn α β
αn · αn βn 2(H( ρ̄ )ρ̄+H( ρ )ρ+o(1))n
n
= (6.13)
(α+β )n 2(H(α+β )+o(1))n
α β
= 2−(H(α+β )−H( ρ̄ )ρ̄−H( ρ )ρ−o(1))n , (6.14)
where the first equality follows by Fact 6.4.
Let ρ = 1/2 + ε for some constant ε > 0, and ρ̄ = 1 − ρ = 1/2 − ε. The next lemma will be used in
order to prove the few bad sets lemma and the expansion lemma. It uses the existence of a Hamiltonian
cycle in the graph in order to claim that most sets will have a large number of neighbors. Therefore, a
random set will have a large expansion. In addition, there will be few sets of size (1/2 − ε)n with fewer
than (1/2 + ε)n neighbors (i. e., few bad sets).
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 21
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
Lemma 6.6. Let α ∈ (0, 1/2) and β ∈ (α, 1) be two constants such that δ = β − α < α/2. The number
of sets S of size αn where |N(S)| ≤ β n is at most
2(αH(δ /α)+(1−α)H(δ /(1−α))+o(1))n .
Proof. Consider a Hamiltonian cycle H = (v1 , u1 , v2 , u2 , . . . , vn , un , v1 ), where {vi }i∈[n] = V and {ui }i∈[n] =
U. Let S be a set of vertices from V of cardinality αn. Note that in the cycle H, each vertex v of S has two
neighbors, where one of these neighbors is joined with an adjacent vertex from V in the cycle. Therefore,
the number of neighbors of a sequence of k consecutive vertices of V in H is k + 1. Thus, the set N(S) is
of size αn plus the number of consecutive blocks of vertices from V chosen.
We bound the number of ways to pick at most δ n consecutive blocks of vertices from V . We first
bound the number of ways to pick exactly δ n such blocks. In this case, the αn chosen elements have to
be within δ n blocks. The number of ways to partition αn elements to δ n non-empty blocks is αn−1 δ n−1 .
After deciding the number of elements in each block, we need to figure out their location along the
Hamiltonian cycle. (1 − α)n elements reside outside of the blocks of the chosen αn elements. We need
to choose the location of the first block in H (for which there are n possibilities), and then the number of
elements between each pair of consecutive blocks where two blocks are separated by at least one element.
The latter is equivalent to dividing (1 − α)n elements into δ n non-empty segments for which there are
(1−α)n−1 (1−α)n−1
δ n−1
possibilities. Overall, there are n αn−1
δ n−1 δ n−1
such possibilities6 .
For δ 0 < δ , one can similarly prove the bound of
αn − 1 (1 − α)n − 1
n 0 (6.15)
δ n−1 δ 0n − 1
which is smaller than
αn − 1 (1 − α)n − 1
n (6.16)
δn−1 δn−1
by our conditions on α and δ . Overall, we can bound the number of ways to pick at most δ n consecutive
blocks of vertices from V by
2 αn − 1 (1 − α)n − 1 2 αn (1 − α)n
δn < δn (6.17)
δn−1 δn−1 δn δn
δ
δ (H( (1−α) )+o(1))(1−α)n
= 2o(1)n · 2(H( α )+o(1))αn · 2 (6.18)
δ
(αH( αδ )+(1−α)H( (1−α) )+o(1))n
= 2 , (6.19)
where the first equality follows Fact 6.4.
The expansion and few bad sets lemmas are obtained as direct corollaries of Lemma 6.6.
6 Notice there is some overcounting in this argument, but this bound suffices for our purpose.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 22
M AX -M IN G REEDY M ATCHING
Lemma 6.7 (Few bad sets lemma for Hamiltonian graphs). Let ε be a constant such that ε < 0.1. The
number of bad sets in any Hamiltonian graph is at most
ρ̄H( 2ε 2ε
ρ̄ )+ρH( ρ )+o(1) n
|Bε | ≤ 2 .
Proof. Notice that if a set S of size ρ̄n = (1/2 − ε)n has more than ρn neighbors, it cannot be left
unmatched, since at least
one of its neighbors
will not be matched to V \ S. By Lemma 6.6, the number of
ρ̄H( 2ε 2ε
ρ̄ )+ρH( ρ )+o(1) n
such sets is at most 2 .
We note that this lemma is not true for general graphs. An example of a graph that admits 2n/4 bad
sets is given in Proposition 6.9.
Lemma 6.8 (Expansion Lemma for Hamiltonian graphs). Consider a set S ⊂ V of size ρ̄n and parameters
α, β . The probability that the lowest αn vertices in S have fewer than β n neighbors is at most
δ
−H( αρ̄ )+αH( αδ )+(1−α)H( (1−α) )+o(1) ρ̄n
2 .
Proof. Consider a set S of size ρ̄n, and the first αn vertices in S in a random linear order. This set is just
a random subset of S of size αn. The number of choices of such subset is
ρ̄n α
= 2(H( ρ̄ )+o(1))ρ̄n .
αn
Notice that we can apply Lemma 6.6 with set S and bound the number of subsets of S with “small”
expansion, even though S is a subset of V , because the same proof applies with respect to a subset of
vertices in only one side of a Hamiltonian graph. Therefore, the number of subsets of size αn of S with at
most β n neighbors is at most
(αH( αδ )+(1−α)H( (1−α)
δ
)+o(1))ρ̄n
2 .
Combining the above, we get that the probability that a random set of αn vertices of S have at most β n
neighbors is at most
(−H( αρ̄ )+αH( αδ )+(1−α)H( (1−α)
δ
)+o(1))ρ̄n
2 .
Now that we have established the three lemmas, we are ready to prove Theorem 6.2.
Proof of Theorem 6.2. Setting ε = 0.0012, α = 0.245 and β = 0.3675 (and ρ = 21 + ε, ρ̄ = 1 − ρ), we
get that these parameters satisfy the conditions for Lemmas 6.5, 6.8 and 6.7.
Applying Lemma 6.7, we get that the size of Bε is at most nB ≤ 20.044n . Applying Lemma 6.8, we
get that the probability that the lowest αn vertices of a set of size ρ̄n have fewer than β n neighbors is at
most p ≤ 2−0.86n . Applying Lemma 6.5, we get that the probability that for a set S of size ρ̄n the αn-th
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 23
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
vertex in a random π comes after β n vertices of V − S is at most q ≤ 2−0.45n . Combining these three
bounds, we get that the probability there exists a set of size ρ̄n unmatched by a random π is at most
nB (p + q) < 1, therefore, there must be a π that matches at least one vertex in each set of size ρ̄n, and the
proof follows.
This approach can also be used to show that a random linear order is guaranteed to to match more
than half of the vertices in every regular graph. On the other hand, Theorem 9.1 in Section 9 shows that
one cannot hope to get ρ > 3/4 with a random linear order in regular graphs.
𝑢1 𝑣1
𝑢2 𝑣2
𝑢3 𝑣3
𝑢4 𝑣4
𝐺′
Figure 4: The graph G0 admits two bad sets, namely {v1 , v2 } and {v1 , v3 }.
The following proposition gives an example of a bipartite graph that admits many bad sets.
Proposition 6.9. There exists a bipartite graph G(U,V ; E) with n vertices on each side, which admits
2n/4 bad sets.
Proof. Consider the bipartite graph G0 (with four vertices on each side) depicted in Figure 4. The sets
V1 = {v1 , v3 } and V2 = {v1 , v2 } are bad sets. Indeed, under π = {v4 , v3 , v2 , v1 }, the set {v1 , v2 } remains
unmatched if u1 and u2 arrive before u3 and u4 . Similarly, under π = {v4 , v2 , v3 , v1 }, the set {v1 , v3 }
remains unmatched if u1 and u2 arrive before u3 and u4 . Now, consider the graph G that is composed of
n/4 disjoint copies of G0 . Since each copy admits two bad sets, G admits 2n/4 bad sets.
7 Iterative process
A natural approach for establishing the existence of a good linear order π is the following iterative process
of “upgrading” unmatched vertices. Given a linear order π : V → [n] and a linear order σ : U → [n], let
MG [σ , π] be the result of the greedy matching where vertices in U arrive in order σ (from high to low)
and each vertex u ∈ U is matched to its highest (under π) neighbor (or left unmatched if all its neighbors
are already matched).
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 24
M AX -M IN G REEDY M ATCHING
𝑢1 𝑣1 𝑢5 𝑣5 𝑢7 𝑣7 𝑢8 𝑣8
𝑢2 𝑣2 𝑢6 𝑣6 𝑢8 𝑣8 𝑢4 𝑣4
𝑢3 𝑣3 𝑢7 𝑣7 𝑢3 𝑣3 𝑢6 𝑣6
𝑢4 𝑣4 𝑢8 𝑣8 𝑢4 𝑣4 𝑢2 𝑣2
𝑢5 𝑣5 𝑢1 𝑣1 𝑢5 𝑣5 𝑢7 𝑣7
𝑢6 𝑣6 𝑢2 𝑣2 𝑢6 𝑣6 𝑢3 𝑣3
𝑉𝐻1
𝑢7 𝑣7 𝑢3 𝑣3 𝑢1 𝑣1 𝑢5 𝑣5
𝑢8 𝑣8 𝑢4 𝑣4 𝑢2 𝑣2 𝑢1 𝑣1
Figure 5: An iterative process where unmatched vertices are given priority. In every iteration thick edges
are in the matching; gray vertices are unmatched.
Fix an arbitrary linear order π1 on V , and let σ1 be a linear order on U minimizing the greedy
matching.7 Let M1 = MG [σ1 , π1 ] be the result of the greedy matching under linear order σ1 and π1 . If
|M1 |/n is some constant greater than 1/2, then terminate with linear order π1 . Otherwise, partition V into
the set VH1 of unmatched vertices (H for high, as they will be placed high in the next iteration) and the set
VL1 of matched vertices (L for low, as they will be placed low in the next iteration).
Consider now a linear order π2 in which VH1 precedes VL1 (preserving the internal order between
vertices in VH1 and similarly between vertices in VL1 ), and let σ2 be a linear order on U minimizing
the resulting greedy matching. Let M2 = MG [σ2 , π2 ]. If |M2 |/n is some constant greater than 1/2, then
terminate with linear order π2 . Else, partition V into the set VH2 of unmatched vertices and the set VL2 of
matched vertices, and consider a linear order π3 in which VH2 precedes VL2 (preserving internal orders).
Continue this iterative process until the linear order πk obtained ensures a matching greater than a half.
The intuition behind this approach is that the unmatched vertices need some “help” in order to be
matched, and we provide this help in the form of prioritizing them over matched vertices. One might
hope that this process will reach a good linear order within a constant number of iterations. Unfortunately,
we show an example where the process goes through log n iterations before it first obtains a linear order
7 It is unclear whether σ
1 can be computed in polynomial time. The related problem of computing a minimum maximal
matching in bipartite graphs is known to be NP-hard [2]. However, here we consider the existence problem.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 25
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
ensuring a matching that exceeds n/2.
The construction of the graph is inductive. The base is G0 (U0 ,V0 ; E0 ), with two vertices u, v and a
single edge between them. For every i = 1, 2, . . ., Gi (Ui ,Vi ; Ei ) is such that |Ui | = |Vi | = 2i ; it is obtained
by taking two (disjoint) copies of Gi−1 , with additional edges of the form (u j , v j ) for every u j from one
copy of Gi−1 to v j in the second copy of Gi−1 . An example of G3 is presented in Figure 5(a). The iterative
process is depicted in Figure 5(a)-(d). In all iterations preceding the last one, exactly n/2 vertices are
matched in the worst σ .
8 Stable matching
The max-min greedy matching problem is also related to the stable matching problem [10] with partial
preferences. In a stable matching scenario, every vertex in U has a preference order over the vertices in
V , and every vertex in V has a preference order over the vertices in U. Given a matching M, a pair of
vertices u ∈ U, v ∈ V is said to constitute a blocking pair if u and v prefer each other over their partners
in M. A matching is said to be stable if no pair of vertices u, v constitutes a blocking pair. The stable
matching problem is extended to partial preferences by including an option of being unmatched in the
preference order, which can be preferred over being matched to some other vertex. This implies that if
being unmatched is preferred over being matched to v by some vertex u, then u being matched to v cannot
be stable.
Consider a graph G and linear orders π and σ over V and U, respectively. In the corresponding stable
matching with partial preferences instance, a vertex v ∈ V sets its preferences over vertices in N(v) ⊆ U
according to the ranking in π, and prefers being unmatched over vertices in U \ N(v). The analogous
preferences are set for vertices in U with respect to vertices in V and σ . We show the following.
Proposition 8.1. The partial preference orders defined by the graph G and linear orders π, σ imply
the existence of a unique stable matching. Moreover, the outcome of the greedy matching process is the
unique stable matching.
Proof. First, we show that the preferences defined by G, π and σ imply a unique stable matching. Let π
and σ be the preference orders defined by π and σ , where a higher ranking implies a higher preference.
Let u1 σ u2 σ . . . σ un and v1 π u2 π . . . π vn be the U-side and V -side vertices ordered according
to σ and π , respectively. Consider two different matchings, M1 and M2 that are stable with respect
to the preferences defined by G, π and σ . Consider iterating over the U-side vertices according to their
ordering until we reach a vertex ui with a different outcome in M1 and M2 . There are two scenarios:
• ui is matched to v j in M1 and to vk for k 6= j in M2 . Assume without loss that k < j; that is, vk π v j
and also vk ui v j . In this case we claim that (ui , vk ) is a blocking pair in M1 . To see this, we first
notice vk is not matched to any u` with ` < i in M1 . Otherwise, ui would not have been the first
U-side vertex for which M1 and M2 differ. Therefore, either vk is matched to some u` in M1 for
which ui σ u` (and therefore ui vk u` ), or vk is unmatched in M1 . In both cases, since vk ui v j ,
then both ui and vk strictly improve their outcome in M1 by matching to each other.
• ui is matched in one of the matchings and is unmatched in the other. Without loss of generality,
ui is matched to vk in M2 and is unmatched in M1 . As in the first scenario, since the matchings
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 26
M AX -M IN G REEDY M ATCHING
are identical until we reach ui , either vk is unmatched in M1 , or it is matched to some u` for which
ui vk u` . This again implies that (ui , vk ) is a blocking pair in M1 as both vertices improve their
outcome by matching to each other.
To show that the greedy matching process results in the unique stable matching, we argue there are
no blocking pairs. Let M be the resulting matching, and suppose towards a contradiction that (ui , v j ) is
a blocking pair. This means that (i) the edge (ui , v j ) exists in G, and (ii) v j is not matched to a higher
ranked vertex than ui in M. But this implies that when it is ui ’s turn in the greedy matching process,
v j is an option. Therefore, it would not end up with an outcome, inferior to being matched to v j , a
contradiction.
Thus, the max-min greedy matching problem is equivalent to choosing a linear order π over V such
that for every linear order σ over U, the unique stable matching with respect to π and σ obtains a large
matching.
9 Additional results for regular graphs
The following theorem shows that one cannot hope to get ρ > 3/4 with a random linear order in regular
graphs.
Theorem 9.1. For every ε > 0 and sufficiently large d, there are d-regular graphs G for which a random
linear order π results in ρ ≤ 34 + ε.
Proof. Consider a d-regular bipartite graph G(U,V ; E), where U = U1 ∪U2 , V = V1 ∪V2 , |U1 | = |V1 | = d,
|U2 | = |V2 | = d − 1, and |U| = |V | = 2d − 1 = n. The edge set is (U1 × V2 ) ∪ (U2 × V1 ) ∪ M, where M
is a perfect matching between U1 and V1 . Hence the degree of every vertex is d, and (U2 ,V2 ) forms a
balanced bipartite independent set.
Let Q1 ⊂ V (a random variable) be the set of first d vertices under the random linear order π, and let
Q2 = V \ Q1 . Then, E[|V2 ∩ Q2 |] = ( d−1 2 n
n ) n > 4 − 1. Moreover, as the value of |V2 ∩ Q2 | is concentrated
around its mean, then for sufficiently large d (say, d = Ω 1/ε 2 ) ), the actual value of |V2 ∩ Q2 | is above
(1 − ε)n/4 with high probability. Hence the bounds we prove hold with high probability, and not just in
expectation.
Observe that there is a perfect matching M 0 between U1 and Q1 : For every vertex u ∈ U1 , if its
matched vertex under M is in V1 ∩ Q1 then match u to this vertex, and otherwise match u to an arbitrary
vertex in V2 ∩ Q1 . The number of vertices in U1 whose partner under M is not in Q1 equals |V2 ∩ Q1 |, and
so this gives a perfect matching. For 1 ≤ j ≤ d, let u j denote the vertex in U1 that is matched to the jth
vertex in Q1 under M 0 according to π. Choose a linear order σ over U that begins with u1 , . . . , ud , and is
followed by the vertices of U2 (unlike the vertices of U1 , the vertices of U2 can be arranged in an arbitrary
order). With this σ , all vertices of U1 will be matched with Q1 , and consequently no vertex of V2 ∩ Q2
will be matched. This leaves (1 − ε)n/4 vertices unmatched, proving the theorem.
We also establish a few impossibility results for regular graphs of low degree.
Theorem 9.2. The following hold.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 27
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
• There exists a 3-regular bipartite graph G for which ρ(G) = 75 .
10
• There exists a 4-regular bipartite graph G for which ρ(G) = 13 .
The proof relies on the incidence graphs of finite projective planes. A projective plane consists of
a set of lines and a set of points, where every two lines intersect in a single point, every two points are
incident to a single line, and there are four points, no three of which are on a line. A projective plane
defines a bipartite graph G(U,V ; E), called its incidence graph, where every vertex u ∈ U corresponds to
a point in the plane, every vertex v ∈ V corresponds to a line, and there exists an edge between u and v if
the point corresponding to u is incident to the line corresponding to v.
Proof. For the first result, we show that ρ = 57 for incidence graph of the Fano plane. The Fano plane
is a projective plane consisting of 7 points and 7 lines, with 3 points on every line and 3 lines through
every point. Let G(U,V ; E) be the incidence graph of the Fano plane. This is a 3-regular bipartite graph.
Let N(V 0 ) denote the set of neighbors of a set V 0 ⊂ V . For every set V 0 ⊂ V of size |V 0 | = 2 we have
|N(V 0 )| = 5. We show below that for every such V 0 there exists a perfect matching between N(V 0 ) and
V \V 0 . Hence one can choose a linear order σ over U whose first 5 vertices are N(V 0 ) that will match the
vertices of V \V 0 one by one. Thereafter, the vertices of V 0 will remain unmatched. By Hall’s condition, it
suffices to show that for every set U 0 ⊂ N(V 0 ) of size |U 0 | ≤ 5 we have |N(U 0 )| ≥ |U 0 | + 2 (so that Hall’s
condition holds with respect to the set V \V 0 ). Indeed, for every set U 0 of size 1, |N(U 0 )| = 3, for every
set U 0 of size 2, |N(U 0 )| = 5, for every set U 0 of size ≥ 3, |N(U 0 )| ≥ 6, and for every set U 0 of size 5,
|N(U 0 )| = 7. These statements can be quickly verified using the symmetries of the Fano plane. It follows
that ρ(G) = 5/7.
The second result follows by a similar argument. It is known that there exists a projective plane
consisting of 13 points and 13 lines, with 4 points on every line and 4 lines through every point. We claim
that ρ = 10 13 for the incidence graph G(U,V ; E) of this projective plane. By the properties of a projective
plane, for every set V 0 ⊂ V such that |V 0 | = 3, it holds that |N(V 0 )| ∈ {9, 10}. We show below that for
every such V 0 there exists a perfect matching between N(V 0 ) (and possibly an additional vertex u in case
|N(V 0 )| = 9) and V \V 0 . Hence one can choose a linear order σ over U whose first 10 vertices are N(V 0 )
(possibly with the additional vertex) that will match the vertices of V \V 0 one by one. Thereafter, the
vertices of V 0 will remain unmatched. By Hall’s condition, it suffices to show that for every set U 0 ⊂ N(V 0 )
such that |U 0 | ≤ 10 it holds that |N(U 0 )| ≥ |U 0 | + 3 (so that Hall’s condition holds with respect to the set
V \ V 0 ). Indeed, for every set U 0 of size 1, |N(U 0 )| = 4, for every set U 0 of size ≥ 2, |N(U 0 )| ≥ 7, for
every set U 0 of size ≥ 5, |N(U 0 )| ≥ 11, for every set U 0 of size 9, |N(U 0 )| ≥ 12, and for every set U 0 of
size ≥ 10, |N(U 0 )| = 13. It follows that ρ(G) = 10/13.
10 Open problems
In this paper we proved various bounds regarding the max-min greedy matching problem. Our main
result was in showing that for every bipartite graph G, one can efficiently compute a linear order π such
that for every σ , ρ is greater than a constant strictly greater than 1/2 (namely, greater than 0.51). In [4],
they present a G such that for every π, there is a σ such that ρ ≤ 2/3. The main open question left by
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 28
M AX -M IN G REEDY M ATCHING
this paper is to close the gap between 0.51 and 2/3. Moreover, is it possible to compute the optimal π
efficiently?
In addition to our result for general bipartite graphs, we also have results for interesting families
of bipartite graphs. Specifically, we show that for regular graphs and for Hamiltonian graphs, we
are able to compute
√ linear orders with improved bounds. Namely, we show that for regular graphs,
ρ ≥ 5/9 − O(1/ d), and for Hamiltonian graphs, ρ ≥ 5/9. Moreover, as opposed to general graphs, for
these families of graphs, a random linear order guarantees that ρ is greater than a constant strictly greater
than 1/2 (by some tiny quantity). However, there are substantial gaps remaining for these families of
graphs as well. The 2/3 example from [4] is of a Hamiltonian graph, while the only upper bound known
on the value of ρ for regular graphs is 8/9. It will be interesting to see what are the best achievable
bounds on ρ, and what are the best guarantees that a random π can achieve.
Finally, the results in our paper can be interpreted as welfare bounds that a seller can achieve by
pricing items in full information markets with binary unit-demand valuations. One can ask the same
question for more general classes of valuations; for instance, general unit-demand valuations. In this more
general version of the problem, the bipartite graph is now weighted, and the seller, knowing the graph,
sets prices over the right hand side. Then, the left hand side arrives in some order, and each arriving
“buyer” on the left hand side chooses an available “item” on the right hand side that maximizes the weight
of the edge minus the price of the item. For this more general problem, it is still unknown if the seller can
set prices that guarantee that the weight of the resulting weighted matching is at least a ρ-fraction of the
maximum weight matching for some constant ρ > 1/2. In fact, 2/3 might actually be the correct answer
for this more general problem.
Acknowledgments
A substantial part of this work was conducted in Microsoft Research. We are grateful to Amos Fiat and
Sella Nevo for numerous discussions that contributed significantly to the ideas presented in this paper.
We also thank Robert Kleinberg for helpful discussions.
References
[1] A LLAN B ORODIN , D ENIS PANKRATOV, AND A MIRALI S ALEHI -A BARI: On conceptually simple
algorithms for variants of online bipartite matching. Theory Computing Sys., 63(8):1781–1818,
2019. Preliminary version in WAOA’17. [doi:10.1007/s00224-019-09916-0] 4
[2] M IROSLAV C HLEBÍK AND JANKA C HLEBÍKOVÁ: Approximation hardness of edge dominating set
problems. J. Combinat. Optim., 11(3):279–290, 2006. [doi:10.1007/s10878-006-7908-0] 25
[3] I LAN R EUVEN C OHEN AND DAVID WAJC: Randomized online matching in regular graphs. In
Proc. 29th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’18), pp. 960–979. SIAM, 2018.
[doi:10.1137/1.9781611975031.62] 6
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 29
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
[4] V INCENT C OHEN -A DDAD , A LON E DEN , M ICHAL F ELDMAN , AND A MOS F IAT: The invisible
hand of dynamic market pricing. In Proc. 17th ACM Conf. Econ. Comput. (EC’16), pp. 383–400.
ACM Press, 2016. [doi:10.1145/2940716.2940730] 3, 8, 28, 29
[5] PAUL D ÜTTING , M ICHAL F ELDMAN , T HOMAS K ESSELHEIM , AND B RENDAN L UCIER: Prophet
inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. In Proc. 58th
FOCS, pp. 540–551. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.56, arXiv:1612.03161] 7
[6] A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN: Max-min greedy matching. In Proc.
22nd Internat. Conf. on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’19), pp.
7:1–23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-
RANDOM.2019.7] 1
[7] T OMER E ZRA , M ICHAL F ELDMAN , T IM ROUGHGARDEN , AND WARUT S UKSOMPONG: Pricing
multi-unit markets. ACM Trans. Econ. Comput., 7(4):20:1–29, 2020. [doi:10.1145/3373715] 7
[8] U RIEL F EIGE , R. R AVI , AND M OHIT S INGH: Short tours through large linear forests. In Proc.
17th Integer Prog. Combinat. Optim. (IPCO’14), volume 8494 of LNCS, pp. 273–284. Springer,
2014. [doi:10.1007/978-3-319-07557-0_23] 15
[9] M ICHAL F ELDMAN , N ICK G RAVIN , AND B RENDAN L UCIER: Combinatorial auctions via posted
prices. In Proc. 26th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’15), pp. 123–135.
SIAM, 2015. [doi:10.1137/1.9781611973730.10] 5, 7
[10] DAVID G ALE AND L LOYD S. S HAPLEY: College admissions and the stability of marriage. Amer.
Math. Monthly, 69(1):9–15, 1962. [doi:10.2307/2312726] 3, 26
[11] G AGAN G OEL AND A RANYAK M EHTA: Online budgeted matching in random input models with
applications to Adwords. In Proc. 19th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’08),
pp. 982–991. SIAM, 2008. ACM DL. 6, 7
[12] C HINMAY K ARANDE , A RANYAK M EHTA , AND P USHKAR T RIPATHI: Online bipartite match-
ing with unknown distributions. In Proc. 43rd STOC, pp. 587–596. ACM Press, 2011.
[doi:10.1145/1993636.1993715] 7
[13] R ICHARD M. K ARP, U MESH V. VAZIRANI , AND V IJAY V. VAZIRANI: An optimal algo-
rithm for on-line bipartite matching. In Proc. 22nd STOC, pp. 352–358. ACM Press, 1990.
[doi:10.1145/100216.100262] 2, 6
[14] B RENDAN L UCIER: An economic view of prophet inequalities. SIGecom Exchanges, 16(1):24–47,
2017. [doi:10.1145/3144722.3144725] 7
[15] M OHAMMAD M AHDIAN AND Q IQI YAN: Online bipartite matching with random arrivals: An
approach based on strongly factor-revealing LPs. In Proc. 43rd STOC, pp. 597–606. ACM Press,
2011. [doi:10.1145/1993636.1993716] 7
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 30
M AX -M IN G REEDY M ATCHING
[16] VAHIDEH H. M ANSHADI , S HAYAN OVEIS G HARAN , AND A MIN S ABERI: Online stochastic
matching: Online actions based on offline statistics. Math. Oper. Res., 37(4):559–573, 2012.
[doi:10.1287/moor.1120.0551] 7
[17] A RANYAK M EHTA: Online matching and ad allocation. Found. Trends Theor. Comp. Sci., 8(4):265–
368, 2013. [doi:10.1561/0400000057] 2
[18] J OSEPH NAOR AND DAVID WAJC: Near-optimum online ad allocation for targeted adver-
tising. ACM Trans. Econ. Comput., 6(3–4):16:1–20, 2018. Preliminary version in EC’15.
[doi:10.1145/3105447] 14
[19] R ENATO PAES L EME AND S AM C HIU - WAI W ONG: Computing Walrasian equilibria: Fast al-
gorithms and structural properties. Math. Programming, 179:343–384, 2018/2020. Preliminary
version in SODA’17. [doi:10.1007/s10107-018-1334-9] 8
AUTHORS
Alon Eden
Postdoctoral Fellow
School of Engineering and Applied Sciences
Harvard University
Cambridge, MA, USA
aloneden seas harvard edu
https://aloneden.github.io
Uriel Feige
Professor
Department of Computer Science and Applied Mathematics
The Weizmann Institute
Rehovot, Israel
uriel feige weizmann ac il
http://www.wisdom.weizmann.ac.il/~feige
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 31
A LON E DEN , U RIEL F EIGE , AND M ICHAL F ELDMAN
Michal Feldman
Professor
Department of Computer Science
Tel Aviv University
Tel Aviv, Israel
and
Microsoft Research Israel
Herzliya, Israel
michal feldman cs tau ac il
http://www.cs.tau.ac.il/~mfeldman
ABOUT THE AUTHORS
A LON E DEN is a postdoctoral fellow in the Harvard EconCS group under the supervision
of Yiling Chen and David Parkes. He received his Ph. D. in Computer Science from Tel
Aviv University in 2019 under the supervision of Michal Feldman and Amos Fiat. He
was awarded the Michael B. Maschler Prize of the Israeli Chapter of the Game Theory
Society for the best Ph. D. thesis of 2019. He received a Best Paper award at SAGT’17
and a Best Paper with Lead Student Author award at EC’19. He enjoys traveling outdoors
with his family.
Born in Jerusalem, U RIEL F EIGE earned his B. Sc. from the Technion, and his M. Sc.
and Ph. D. from the Weizmann Institute of Science, both under the guidance of Adi
Shamir. After conducting postdoctoral research at Princeton University and at the IBM
T.J. Watson Research Center, he joined the Weizmann Institute in 1992. From 2004-
2007, he took leave from the Weizmann Institute to work with the Theory Group at
Microsoft Research, and he continues to serve as a visiting researcher in Microsoft
Research, Herzliya. His main research areas are algorithms, computational complexity,
and algorithmic game theory. His work was recognized by some awards, including the
2001 Gödel Prize and the 2005 SIAM Outstanding Paper Prize. He enjoys playing the
piano, some sports activities, and spending time with his family.
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 32
M AX -M IN G REEDY M ATCHING
M ICHAL F ELDMAN is a Professor of Computer Science in the Blavatnik School of Computer
Science at Tel Aviv University and a visiting scholar at Microsoft Research (MSR)
Herzliya. Her research spans computer science, economics, game theory and operations
research. She received her Ph. D. from the University of California at Berkeley in 2005.
She was a visiting professor at Harvard University and Microsoft Research New England
(2011-13). She is an Associate Editor of Games and Economic Behavior, Mathematics
of Operations Research, ACM Transactions on Economics and Computation, and the
Journal of Computer and System Sciences. She served as Vice Chair of ACM SIGecom,
and PC chair of the leading conference on Economics and Computation (ACM EC 2015).
She received multiple Best Paper Awards, and the TAU Rector’s Award for excellence in
teaching. She is an alumna of the Global Young Academy of Sciences, and the Israeli
Young Academy of Sciences (and its management committee). She is the recipient of
coveted international grants and fellowships, including two ERC grants of the European
Research Council, Marie Curie IOF, Alon, ISF and Amazon Research Awards. She was
listed in Forbes’ list of the 50 most influential women in Israel (2016), and in the The
Marker’s list of 40 under 40 (2014).
T HEORY OF C OMPUTING, Volume 18 (6), 2022, pp. 1–33 33