Theory of Computing
-------------------
Title : Max-Min Greedy Matching
Authors : Alon Eden, Uriel Feige, and Michal Feldman
Volume : 18
Number : 6
Pages : 1-33
URL : https://theoryofcomputing.org/articles/v018a006
Abstract
--------
A bipartite graph $G(U,V;E)$ that admits a perfect matching is given.
One player imposes a permutation $\pi$ over $V$, the other player
imposes a permutation $\sigma$ over $U$. In the greedy matching
algorithm, vertices of $U$ arrive in order $\sigma$ and each vertex is
matched to the highest (under $\pi$) 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 $\pi$, and the second (min) player responds with
the worst possible $\sigma$ for $\pi$. Does there exist a permutation
$\pi$ ensuring to match strictly more than half of the vertices? Can
such a permutation 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 $\pi$ for which for every $\sigma$ at least $\rho > 0.51$
fraction of the vertices of $V$ are matched. We provide additional
lower and upper bounds for 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.
----------------
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).