More Web Proxy on the site http://driver.im/

research-article

Machine learning in an auction environment

Authors:

Patrick Hummel,

Preston McAfeeAuthors Info & Claims

WWW '14: Proceedings of the 23rd international conference on World wide web

Pages 7 - 18

https://doi.org/10.1145/2566486.2567974

Published: 07 April 2014 Publication History

Abstract

We consider a model of repeated online auctions in which an ad with an uncertain click-through rate faces a random distribution of competing bids in each auction and there is discounting of payoffs. We formulate the optimal solution to this explore/exploit problem as a dynamic programming problem and show that efficiency is maximized by making a bid for each advertiser equal to the advertiser's expected value for the advertising opportunity plus a term proportional to the variance in this value divided by the number of impressions the advertiser has received thus far. We then use this result to illustrate that the value of incorporating active exploration into a machine learning system in an auction environment is exceedingly small.

References

[1]

D. Agarwal, B.-C. Chen, and P. Elango. Explore/exploit schemes for web content optimization. In Proceedings of the 9th Industrial Conference on Data Mining (ICDM), pages 1--10, 2009.

Digital Library

[2]

P. Aghion, P. Bolton, C. Harris, and B. Jullien. Optimal learning by experimentation. Review of Economic Studies, 58(4):621--654, 1991.

[3]

P. Aghion, M. P. Espinosa, and B. Jullien. Dynamic duopoly with learning through market experimentation. Economic Theory, 3(3):517--539, 1993.

[4]

N. Anthonisen. On learning to cooperate. Journal of Economic Theory, 107(2):253--287, 2002.

[5]

P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multi-armed bandit problem. Machine Learning, 47(2--3):235--256, 2002.

Digital Library

[6]

P. Auer, N. Cesa-Bianchi, and P. Fischer. The nonstochastic multi-armed bandit problem. SIAM Journal on Computing, 32(1):48--77, 2003.

Digital Library

[7]

M. Babaioff, Y. Sharma, and A. Slivkins. Characterizing truthful multi-armed bandit mechanisms. In Proceedings of the 10th ACM Conference on Electronic Commerce (EC), pages 79--88, 2009.

Digital Library

[8]

A. Banerjee and D. Fudenberg. Word-of-mouth learning. Games and Economic Behavior, 46(1):1--22, 2004.

[9]

J. S. Banks and R. K. Sundaram. Denumerable-armed bandits. Econometrica, 60(5):1071--1096, 1992.

[10]

E. Bax, A. Kuratti, P. McAfee, and J. Romero. Comparing predicted prices in auctions for online advertising. International Journal of Industrial Organization, 30(1):80--88, 2011.

[11]

D. Bergemann and J. Valimkaki. Learning and strategic pricing. Econometrica, 64(5):1125--1149, 1996.

[12]

D. Bergemann and J. Valimkaki. Market diffusion with two-sided learning. RAND Journal of Economics, 28(4):773--795, 1997.

[13]

D. Bergemann and J. Valimkaki. Experimentation in markets. Review of Economic Studies, 67(2):213--234, 2000.

[14]

D. Bergemann and J. Valimkaki. Stationary multi-choice bandit problems. Journal of Economic Dynamics and Control, 25(1):1585--1594, 2001.

[15]

P. Bolton and C. Harris. Strategic experimentation. Econometrica, 67(2):349--374, 1999.

[16]

M. Brezzi and T. L. Lai. Optimal learning and experimentation in bandit problems. Journal of Economic Dynamics and Control, 27(1):87--108, 2002.

[17]

S. Callander. Searching for good policies. American Political Science Review, 105(4):643--662, 2011.

[18]

N. R. Devanur and S. M. Kakade. The price of truthfulness for pay-per-click auctions. In Proceedings of the 10th ACM Conference on Electronic Commerce (EC), pages 99--106, 2009.

Digital Library

[19]

A. Fishman and R. Rob. Experimentation and competition. Journal of Economic Theory, 78(2):299--320, 1998.

[20]

D. Gale. What have we learned from social learning? European Economic Review, 40(3--5):617--628, 1996.

[21]

D. Gale and R. W. Rosenthal. Experimentation, imitation, and stochastic stability. Journal of Economic Theory, 84(1):1--40, 1999.

[22]

J. C. Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society, Series B, 41(2):148--177, 1979.

[23]

P. Hummel and R. P. McAfee. Machine learning in an auction environment. Google Inc. Typescript, 2013.

[24]

K. Iyer, R. Johari, and M. Sundarajan. Mean field equilibria of dynamic auctions with learning. Cornell University Typescript, 2013.

[25]

G. Keller and S. Rady. Optimal experimentation in a changing environment. Review of Economic Studies, 66(3):475--503, 1999.

[26]

G. Keller and S. Rady. Strategic experimentation with poisson bandits. Theoretical Economics, 5(2):275--311, 2010.

[27]

G. Keller, S. Rady, and M. Cripps. Strategic experimentation with experimental bandits. Econometrica, 73(1):39--68, 2005.

[28]

S. Lahaie and R. P. McAfee. Efficient ranking in sponsored search. In Proceedings of the 7th International Workshop on Internet and Network Economics (WINE), pages 254--265, 2011.

Digital Library

[29]

T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4--22, 1985.

Digital Library

[30]

R. A. Lewis. Where's the 'wear-out?' online display ads and the impact of frequency. Massachusetts Institute of Technology Typescript, 2010.

[31]

S.-M. Li, M. Mahdian, and R. P. McAfee. Value of learning in sponsored search auctions. In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE), pages 294--305, 2010.

Digital Library

[32]

L. J. Mirman, L. Samuelson, and A. Urbano. Monopoly experimentation. International Economic Review, 34(3):549--563, 1993.

[33]

G. Moscarini and L. Smith. The optimal level of experimentation. Econometrica, 69(6):1629--1644, 2001.

[34]

M. Ostrovsky and M. Schwarz. Reserve prices in internet advertising auctions: A field experiment. Stanford University Typescript, 2009.

[35]

M. Rothschild. A two-armed bandit theory of market pricing. Journal of Economic Theory, 9(2):185--202, 1974.

[36]

A. Rusitchini and A. Wolinsky. Learning about variable demand in the long run. Journal of Economic Dynamics and Control, 19(5--7):1283--1292, 1995.

[37]

K. H. Schlag. Why imitate, and if so how? a boundedly rational approach to multi-armed bandits. Journal of Economic Theory, 78(1):130--156, 1998.

[38]

B. Strulovici. Learning while voting: Determinant of collective experimentation. Econometrica, 78(3):933--971, 2010.

[39]

X. Vives. Learning from others: A welfare analysis. Games and Economic Behavior, 20(2):177--200, 1997.

[40]

M. L. Weitzman. Optimal search for the best alternative. Econometrica, 47(3):641--654, 1979.

[41]

J. Wortman, Y. Vorobeychik, L. Li, and J. Langford. Maintaining equilibria during exploration in sponsored search auctions. In Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE), pages 119--130, 2007.

Digital Library

Cited By

Souza PDragoni M(2024)Knowledge extraction in auction verification employing techniques from machine learning and fuzzy neural networks.2024 IEEE International Conference on Evolving and Adaptive Intelligent Systems (EAIS)10.1109/EAIS58494.2024.10569109(1-8)Online publication date: 23-May-2024
https://doi.org/10.1109/EAIS58494.2024.10569109
Zhiyanov ADrutsa ADaumé HSingh A(2020)Bisection-based pricing for repeated contextual auctions against strategic buyerProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3526001(11469-11480)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3526001
Drutsa ADaumé HSingh A(2020)Reserve pricing in repeated second-price auctions with strategic biddersProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525189(2678-2689)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525189
Show More Cited By

Index Terms

Machine learning in an auction environment
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics

Recommendations

Machine learning in an auction environment

We consider a model of repeated online auctions in which an ad with an uncertain click-through rate faces a random distribution of competing bids in each auction and there is discounting of payoffs. We formulate the optimal solution to this explore/...
Pricing Rule in a Clock Auction

We analyze a discrete clock auction with lowest-accepted-bid (LAB) pricing and provisional winners, as adopted by India for its 3G spectrum auction. In a perfect Bayesian equilibrium, the provisional winner shades her bid, whereas provisional losers do ...
On the design of sponsored keyword advertising slot auctions: An analysis of a generalized second-price auction approach

The generalized second-priceauction mechanism is commonly used in research in the context of keyword advertising slot auctioning. The mechanism sets the clearing prices for advertising slots on a search engine's Web pages such that the advertiser will ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '14: Proceedings of the 23rd international conference on World wide web

April 2014

926 pages

ISBN:9781450327442

DOI:10.1145/2566486

General Chair:
Chin-Wan Chung
Korea Advanced Institute of Science and Technology, Korea
,
Program Chairs:
Andrei Broder
Google Inc., USA
,
Kyuseok Shim
Seoul National University, Korea
,
Torsten Suel
New York University, USA

Copyright © 2014 Copyright is held by the International World Wide Web Conference Committee (IW3C2).

Sponsors

IW3C2: International World Wide Web Conference Committee

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 April 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WWW '14

Sponsor:

IW3C2

WWW '14: 23rd International World Wide Web Conference

April 7 - 11, 2014

Seoul, Korea

Acceptance Rates

WWW '14 Paper Acceptance Rate 84 of 645 submissions, 13%;

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
474
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Souza PDragoni M(2024)Knowledge extraction in auction verification employing techniques from machine learning and fuzzy neural networks.2024 IEEE International Conference on Evolving and Adaptive Intelligent Systems (EAIS)10.1109/EAIS58494.2024.10569109(1-8)Online publication date: 23-May-2024
https://doi.org/10.1109/EAIS58494.2024.10569109
Zhiyanov ADrutsa ADaumé HSingh A(2020)Bisection-based pricing for repeated contextual auctions against strategic buyerProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3526001(11469-11480)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3526001
Drutsa ADaumé HSingh A(2020)Reserve pricing in repeated second-price auctions with strategic biddersProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525189(2678-2689)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525189
Drutsa ADaumé HSingh A(2020)Optimal non-parametric learning in repeated contextual auctions with strategic buyerProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525188(2668-2677)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525188
Vanunts ADrutsa AWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Optimal pricing in repeated posted-price auctions with different patience of the seller and the buyerProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454372(941-953)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454372
Drutsa ABarrett RCummings RAgichtein EGabrilovich E(2017)Horizon-Independent Optimal Pricing in Repeated Auctions with Truthful and Strategic BuyersProceedings of the 26th International Conference on World Wide Web10.1145/3038912.3052700(33-42)Online publication date: 3-Apr-2017
https://dl.acm.org/doi/10.1145/3038912.3052700
Banerjee SJohari RZhou Z(2016)The Importance of Exploration in Online MarketplacesIEEE Internet Computing10.1109/MIC.2015.13920:1(20-26)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1109/MIC.2015.139
Choi WSayedi A(undefined)Learning in Search AdvertisingSSRN Electronic Journal10.2139/ssrn.3116363
https://doi.org/10.2139/ssrn.3116363

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents