文章基本信息

标题：Max-Min Greedy Matching
本地全文：下载
作者：Alon Eden ; Uriel Feige ; Michal Feldman 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2022
卷号：18
页码：1-33
DOI：10.4086/toc.2022.v018a006
语种：English
出版社：University of Chicago
摘要：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 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.
关键词：online matching;pricing mechanism;markets