Online Bipartite Matching via Smoothness
share
The analysis of online bipartite matching of Eden et al. (2021) is a smoothness proof (Syrgkanis and Tardos, 2013). Moreover, it can be interpreted as combining a λ = 1-1/e value covering (which holds for single-dimensional agents and randomized auctions) and μ = 1 revenue covering (Hartline et al., 2014). Note that value covering is a fact about single-dimensional agents and has nothing to do with the underlying feasibility setting. Thus, the essential new result from Eden et al. (2021) is that online bipartite matching is μ=1 revenue covered.
READ FULL TEXT