Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking

Pan Xu

The randomized primal-dual framework of Devanur, Jain, and Kleinberg (SODA 2013) splits each unit matching gain between endpoint dual variables according to the matched offline ran…