Abstract:
Most sponsored search auctions use the Generalized Second Price (GSP) rule. Given the GSP rule, they try to give an optimal allocation, an easy task when the only need is to allocate ads to slots. However, when other practical conditions must be fulfilled -such as budget constraints, exploration of the performance of new ads, etc.- optimal allocations are hard to obtain. We provide a method to optimally allocate ads to slots under the practical conditions mentioned above. Our auctions are stochastic, and can be applied in tandem with different pricing rules, among which we highlight two: an intuitive generalization of GSP and VCG payments. © 2009 Springer Berlin Heidelberg.
Registro:
Documento: |
Artículo
|
Título: | Optimal auctions capturing constraints in sponsored search |
Autor: | Feuerstein, E.; Heiber, P.A.; Lopez-Rosenfeld, M.; Mydlarz, M. |
Ciudad: | San Francisco, CA |
Filiación: | Departamento de Computación, FCEyN, Universidad de Buenos Aires, Argentina Yahoo Research, Santiago, Chile
|
Palabras clave: | Budget constraint; Optimal allocation; Optimal auction; Pricing rules; Sponsored search auctions; Optimization; Commerce |
Año: | 2009
|
Volumen: | 5564 LNCS
|
Página de inicio: | 188
|
Página de fin: | 201
|
DOI: |
http://dx.doi.org/10.1007/978-3-642-02158-9_17 |
Título revista: | 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009
|
Título revista abreviado: | Lect. Notes Comput. Sci.
|
ISSN: | 03029743
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5564LNCS_n_p188_Feuerstein |
Referencias:
- Abrams, Z., (2006) Revenue maximization when bidders have budgets, pp. 1074-1082. , SODA, pp
- Abrams, Z., Mendelevitch, O., Tomlin, J., Optimal delivery of sponsored search advertisements subject to budget constraints (2007) ACM Conference on Electronic Commerce, pp. 272-278
- Aggarwal, G., Goel, A., Motwani, R., Truthful auctions for pricing search keywords (2006) ACM Conference on Electronic Commerce, pp. 1-7
- Bhargava, H.K., Feng, J., Paid placement strategies for internet search engines (2002) WWW 2002: Proceedings of the 11th international conference on World Wide Web
- Birkhoff, G., (1946) Tres observaciones sobre el algebra lineal, pp. 147-151. , Univ. Nac. Tucumán. Revista
- Borgs, C., Chayes, J., Etesami, O., Immorlica, N., Jain, K., Mahdian, M., Dynamics of bid optimization in online advertisement auctions (2007) 16th International World Wide Web Conference (WWW
- Borgs, C., Chayes, J.T., Immorlica, N., Mahdian, M., Saberi, A., Multi-unit auctions with budget-constrained bidders (2005) ACM Conference on Electronic Commerce, pp. 44-51
- Carrasco, J.J., Fain, D.C., Lang, K.J., Zhukov, L., Clustering of bipartite advertiser-keyword graph (2003) Workshop on Large Scale Clustering at IEEE International Conference on Data Mining
- Clarke, E.H., Multipart pricing of public goods (1971) Public Choice, 17-33
- Edelman, B.G., Ostrovsky, M., Schwarz, M., (2005) Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords, , http://ssrn.com/abstract=861164, Stanford Graduate School of Business Research Paper No. 1917 Available at SSRN
- Edmonds, J., Paths, trees, and flowers (1965) Canad. J. Math, 17, pp. 449-467
- Feuerstein, E., Heiber, P., Martínez-Viademonte, J., Baeza-Yates, R., New stochastic algorithms for placing ads in sponsored search (2007) Proc. 5th Latin American Web Congress (LA-WEB
- Feuerstein, E., Heiber, P., Mydlarz, M., Truthful stochastic and deterministic auctions for sponsored search (2008) Proc. 6th Latin American Web Congress (LA-WEB
- Ghosh, A., Mahdian, M., Externalities in online advertising (2008) 17th International World Wide Web Conference (WWW
- Gunawardana, A., Meek, C., Aggregators and contextual effects in search ad markets (2008) WWW Workshop on Targeting and Ranking for Online Advertising
- Klemperer, P., Auction theory: A guide to the literature (1999) Journal of Economic Surveys, 13 (3), pp. 227-286
- Lavi, R., Swamy, C., Truthful and near-optimal mechanism design via linear programming (2005) FOCS, pp. 595-604
- Lovász, L., Plummer, M.D., Matching Theory (1986) Annals of Discrete Mathematics, , North-Holland, Amsterdam
- Mahdian, M., Nazerzadeh, H., Saberi, A., Allocating online advertisement space with unreliable estimates (2007) ACM Conference on Electronic Commerce, pp. 288-294
- Meek, C., Chickering, D.M., Wilson, D.B., Stochastic and contingent-payment auctions (2005) Workshop on Sponsored Search Auctions - ACM Conference on Electronic Commerce (EC
- Mehta, A., Saberi, A., Vazirani, U., Vazirani, V., Adwords and generalized online matching (2005) Proc. Symposium on Foundations of Computer Science
- Myerson, R., Optimal auction design (1981) Mathematics of Operations Research, 6, pp. 58-73
- Nakamura, A., Abe, N.: Improvements to the linear programming based scheduling of web advertisements: World wide web electronic commerce, security and privacy. In: zurko, M.e., greenwald, a. (guest eds.) Electronic Commerce Research, 5, pp. 75-98 (2005); (2007) Algorithmic Game Theory, , Nisan, N, Roughgarden, T, Tardos, É, Vazirani, V.V, eds, Cambridge University Press, Cambridge
- Pandey, S., Olston, C., Handling advertisements of unknown quality in search advertising (2006) Proc. Twentieth Annual Conference on Neural Information Processing Systems (NIPS), , Vancouver, Canada
- Penemberg, A., Click fraud threatens web (2004) Wired news, , October 13
- Schrijver, A., (1986) Theory of Linear and Integer Programming, , John Wiley & Sons, Chichester
- Vickrey, W., Counterspeculation, auctions, and competitive sealed tenders (1961) The Journal of Finance, 16 (1), pp. 8-37
- Wiggins, R., Tomlin, J., (2007), Bid optimization for internet graphical ad auction systems via special ordered sets. Yahoo! Research Technical Report YR-2007-004; Zhu, X., Goldberg, A., Van Gael, J., Andrzejewski, D., Improving diversity in ranking using absorbing random walks (2007) Human Language Technologies: The Annual Conference of the North American Chapter of the Association for Computational Linguistics, , NAAC-HLT
Citas:
---------- APA ----------
Feuerstein, E., Heiber, P.A., Lopez-Rosenfeld, M. & Mydlarz, M.
(2009)
. Optimal auctions capturing constraints in sponsored search. 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009, 5564 LNCS, 188-201.
http://dx.doi.org/10.1007/978-3-642-02158-9_17---------- CHICAGO ----------
Feuerstein, E., Heiber, P.A., Lopez-Rosenfeld, M., Mydlarz, M.
"Optimal auctions capturing constraints in sponsored search"
. 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009 5564 LNCS
(2009) : 188-201.
http://dx.doi.org/10.1007/978-3-642-02158-9_17---------- MLA ----------
Feuerstein, E., Heiber, P.A., Lopez-Rosenfeld, M., Mydlarz, M.
"Optimal auctions capturing constraints in sponsored search"
. 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009, vol. 5564 LNCS, 2009, pp. 188-201.
http://dx.doi.org/10.1007/978-3-642-02158-9_17---------- VANCOUVER ----------
Feuerstein, E., Heiber, P.A., Lopez-Rosenfeld, M., Mydlarz, M. Optimal auctions capturing constraints in sponsored search. Lect. Notes Comput. Sci. 2009;5564 LNCS:188-201.
http://dx.doi.org/10.1007/978-3-642-02158-9_17