Stochastic models for budget optimization in search-based advertising

S. Muthukrishnan, Martin Pál, Zoya Svitkina

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    Internet search companies sell advertisement slots based on users' search queries via an auction. Advertisers have to determine how to place bids on the keywords of their interest in order to maximize their return for a given budget: this is the budget optimization problem. The solution depends on the distribution of future queries. In this paper, we formulate stochastic versions of the budget optimization problem based on natural probabilistic models of distribution over future queries, and address two questions that arise. Evaluation. Given a solution, can we evaluate the expected value of the objective function? Optimization. Can we find a solution that maximizes the objective function in expectation? Our main results are approximation and complexity results for these two problems in our three stochastic models. In particular, our algorithmic results show that simple prefix strategies that bid on all cheap keywords up to some level are either optimal or good approximations for many cases; we show other cases to be NP-hard.

    Original languageEnglish (US)
    Title of host publicationInternet and Network Economics - Third International Workshop, WINE 2007, Proceedings
    PublisherSpringer Verlag
    Number of pages12
    ISBN (Print)9783540771043
    StatePublished - 2007
    Event3rd International Workshop on Internet and Network Economics, WINE 2007 - San Diego, CA, United States
    Duration: Dec 12 2007Dec 14 2007

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume4858 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference3rd International Workshop on Internet and Network Economics, WINE 2007
    Country/TerritoryUnited States
    CitySan Diego, CA

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Stochastic models for budget optimization in search-based advertising'. Together they form a unique fingerprint.

    Cite this