Optimal bundles for sponsored search auctions via bracketing scheme

Abstract

Sponsored search auction has been recently studied and auctioneer’s revenue is an important consideration in probabilistic single-item second-price auctions. Some papers have analyzed the revenue maximization problem on different methods to bundle contexts. In this paper, we propose a more flexible and natural method which is called the bracketing method. We prove that finding a bracketing scheme that maximizes the auctioneer’s revenue is strongly NP-hard. Then, a heuristic algorithm is given. Experiments on three test cases show that the revenue of the optimal bracketing scheme is very close to the optimal revenue without any bundling constraint, and the heuristic algorithm performs very well. Finally, we consider a simpler model that for each row in the valuation matrix, the non-zero cells have the same value. We prove that the revenue maximization problem with K-anonymous signaling scheme and cardinality constrained signaling scheme in this simpler model are both NP-hard.

Keywords

sponsored search auction / revenue maximization / bracketing scheme / NP-hardness

References

[1] Interactive Advertising Bureau. Iab Internet advertising revenue report 2013 full year results. Technical Report, 2014

[2] Fain D C, Pedersen J O. Sponsored search: a brief history. Bulletin of the American Society for Information Science and Technology, 2006, 32(2): 12–13

[3] Jansen B J, Mullen T. Sponsored search: an overview of the concept, history, and technology. International Journal of Electronic Business, 2008, 6(2): 114–131

[4] Qin T, Chen W, Liu T Y. Sponsored search auctions: recent advances and future directions. ACM Transactions on Intelligent Systems and Technology, 2015, 5(4): 60

[5] Even-Dar E, Kearns M, Wortman J. Sponsored search with contexts. In: Proceedings of the 3rd International Workshop on Internet and Network Economics. 2007, 312–317

[6] Ghosh A, Nazerzadeh H, Sundararajan M. Computing optimal bundles for sponsored search. In: Proceedings of the 3rd International Workshop on Internet and Network Economics. 2007, 576–583

[7] Emek Y, Feldman M, Gamzu I, Tennenholtz M. Revenue maximization in probabilistic single-item auctions via signaling. In: Proceedings of the 7th Ad Auctions Workshop. 2011

[8] Miltersen B, Sheffet O. Send mixed signals: earn more, work less. In: Proceedings of the 13th ACM Conference on Electronic Commerce. 2012, 234–247

[9] Dughmi S, Immorlica N, Roth A. Constrained signaling for welfare and revenue maximization. ACM SIGecom Exchanges, 2013, 12(1): 53–56

[10] Dughmi S, Immorlica N, Roth A. Constrained signaling in auction design. In: Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms. 2014, 1341–1357

[11] Dughmi S. On the hardness of signaling. In: Proceedings of the 55th ITEE Annual Symposium on Foundations of Computer Science. 2014, 354–363

[12] Chen C, Qin T. k-anonymous signaling scheme. 2013, arXiv preprint arXiv:1311.6638

[13] Guo M Y, Deligkas A. Revenue maximization via hiding item attributes. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 2013

[14] Papadimitriou P, Garcia-Molina H, Dasdan A, Kolay S. Output url bidding. In: Proceedings of the 37th International Conference on Very Large Data Bases. 2010, 161–172

[15] Dasdan A, Santanu K, Papadimitriou P, Garcia-Molina H. Output bidding: a new search advertising model complementary to keyword bidding. In: Proceedings of the 5th Workshop on Ad Auctions. 2009

[16] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman. 1979

[17] Leyton-Brown K, Pearson M, Shoham Y. Towards a universal test suite for combinatorial auction algorithms. In: Proceedings of the 2nd ACM Conference on Electronic Commerce. 2000, 66–76

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature