Max-Min Greedy Matching
share
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.
READ FULL TEXT