  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 lowest (under
$\pi$) yet unmatched neighbor in $V$ (or left unmatched, if all its neighbors
are already matched). The obtained matching is maximal, thus matches at least a
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 a half of the vertices? Can such a
permutation be computed in polynomial time?
  The main result of this paper is an affirmative answer for this question: we
show that there exists a polytime 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. Interestingly, even for regular
graphs with arbitrarily large degree (implying a large number of disjoint
perfect matchings), there is no $\pi$ ensuring to match more than a fraction
$8/9$ of the vertices.
  The max-min greedy matching problem solves an open problem regarding the
welfare guarantees attainable by pricing in sequential markets with binary
unit-demand valuations. In addition, it has implications for the size of the
unique stable matching in markets with global preferences, subject to the graph
structure.

Computer Science and Game Theory;Data Structures and Algorithms