2021/07/22 by Vijay V. Vazirani, Vazirani, Vijay V. · 2 citations
Computer Science · Decision Sciences · #Auction Theory and Applications #Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Internet Traffic Analysis and Secure E-voting #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2107.10777
openalex publication_date 2021/07/22 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Motivated by recent insights into the online bipartite matching problem (OBM), our goal was to extend the optimal algorithm for it, namely Ranking, all the way to the special case of adwords problem, called Small, in which bids are small compared to budgets; the latter has been of considerable practical significance in ad auctions \citeMSVV. The attractive feature of our approach was that it would yield a \em budget-oblivious algorithm, i.e., the algorithm would not need to know budgets of advertisers and therefore could be used in autobidding platforms. We were successful in obtaining an optimal, budget-oblivious algorithm for Single-Valued, under which each advertiser can make bids of one value only. However, our next extension, to Small, failed because of a fundamental reason, namely failure of the \em No-Surpassing Property. Since the probabilistic ideas underlying our algorithm are quite substantial, we have stated them formally, after assuming the No-Surpassing Property, and we leave the open problem of removing this assumption. With the help of two undergrads, we conducted extensive experiments on our algorithm on randomly generated instances. Our findings are that the No-Surpassing Property fails less than 2% of the time and that the performance of our algorithms for Single-Valued and Small are comparable to that of \citeMSVV. If further experiments confirm this, our algorithm may be useful as such in practice, especially because of its budget-obliviousness.