|
|
Optimal bundles for sponsored search auctions via bracketing scheme |
Zheng-Dong XIA, Tian-Ming BU(), Wen-Hui GONG |
Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200233, China |
|
|
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
|
Corresponding Author(s):
Tian-Ming BU
|
Just Accepted Date: 14 April 2017
Online First Date: 25 May 2018
Issue Date: 08 April 2019
|
|
1 |
Interactive Advertising Bureau. Iab Internet advertising revenue report 2013 full year results. Technical Report, 2014
|
2 |
D CFain, J O Pedersen. Sponsored search: a brief history. Bulletin of the American Society for Information Science and Technology, 2006, 32(2): 12–13
https://doi.org/10.1002/bult.1720320206
|
3 |
B JJansen, TMullen. Sponsored search: an overview of the concept, history, and technology. International Journal of Electronic Business, 2008, 6(2): 114–131
https://doi.org/10.1504/IJEB.2008.018068
|
4 |
TQin, WChen, T YLiu. Sponsored search auctions: recent advances and future directions. ACM Transactions on Intelligent Systems and Technology, 2015, 5(4): 60
https://doi.org/10.1145/2668108
|
5 |
EEven-Dar, MKearns, JWortman. Sponsored search with contexts. In: Proceedings of the 3rd International Workshop on Internet and Network Economics. 2007, 312–317
https://doi.org/10.1007/978-3-540-77105-0_32
|
6 |
AGhosh, H Nazerzadeh, MSundararajan. Computing optimal bundles for sponsored search. In: Proceedings of the 3rd International Workshop on Internet and Network Economics. 2007, 576–583
https://doi.org/10.1007/978-3-540-77105-0_63
|
7 |
YEmek, M Feldman, IGamzu, MTennenholtz. Revenue maximization in probabilistic single-item auctions via signaling. In: Proceedings of the 7th Ad Auctions Workshop. 2011
|
8 |
BMiltersen, O Sheffet. Send mixed signals: earn more, work less. In: Proceedings of the 13th ACM Conference on Electronic Commerce. 2012, 234–247
https://doi.org/10.1145/2229012.2229033
|
9 |
SDughmi, N Immorlica, ARoth. Constrained signaling for welfare and revenue maximization. ACM SIGecom Exchanges, 2013, 12(1): 53–56
https://doi.org/10.1145/2509013.2509022
|
10 |
SDughmi, N Immorlica, ARoth. Constrained signaling in auction design. In: Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms. 2014, 1341–1357
https://doi.org/10.1137/1.9781611973402.99
|
11 |
SDughmi. On the hardness of signaling. In: Proceedings of the 55th ITEE Annual Symposium on Foundations of Computer Science. 2014, 354–363
|
12 |
CChen, TQin. k-anonymous signaling scheme. 2013, arXiv preprint arXiv:1311.6638
|
13 |
M YGuo, A Deligkas. Revenue maximization via hiding item attributes. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence. 2013
|
14 |
PPapadimitriou, H Garcia-Molina, ADasdan, SKolay. Output url bidding. In: Proceedings of the 37th International Conference on Very Large Data Bases. 2010, 161–172
https://doi.org/10.14778/1929861.1929863
|
15 |
ADasdan, K Santanu, PPapadimitriou, HGarcia-Molina. Output bidding: a new search advertising model complementary to keyword bidding. In: Proceedings of the 5th Workshop on Ad Auctions. 2009
|
16 |
M RGarey, D S Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman. 1979
|
17 |
KLeyton-Brown, M Pearson, YShoham. Towards a universal test suite for combinatorial auction algorithms. In: Proceedings of the 2nd ACM Conference on Electronic Commerce. 2000, 66–76
https://doi.org/10.1145/352871.352879
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|