Max-Min Greedy Matching

Abstract

A bipartite graph $G(U,V;E)$ that admits a perfect matching is given. One player imposes a permutation $π$ over $V$, the other player imposes a permutation $σ$ over $U$. In the greedy matching algorithm, vertices of $U$ arrive in order $σ$ and each vertex is matched to the lowest (under $π$) 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 $π$, and the second (min) player responds with the worst possible $σ$ for $π$, does there exist a permutation $π$ 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 $π$ for which for every $σ$ at least $ρ> 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 $π$ 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.